Halide
pointer_table.h
Go to the documentation of this file.
1 #ifndef HALIDE_RUNTIME_POINTER_TABLE_H
2 #define HALIDE_RUNTIME_POINTER_TABLE_H
3 
4 #include "../HalideRuntime.h"
5 #include "memory_resources.h"
6 
7 namespace Halide {
8 namespace Runtime {
9 namespace Internal {
10 
11 // Dynamically resizable array for storing untyped pointers
12 // -- Implementation uses memcpy/memmove for copying
13 // -- Customizable allocator ... default uses NativeSystemAllocator
14 class PointerTable {
15 public:
16  static constexpr size_t default_capacity = 32; // smallish
17 
18  PointerTable(void *user_context, size_t initial_capacity = 0, const SystemMemoryAllocatorFns &sma = default_allocator());
19  PointerTable(const PointerTable &other);
20  ~PointerTable();
21 
22  void initialize(void *user_context, size_t initial_capacity = 0, const SystemMemoryAllocatorFns &sma = default_allocator());
23 
24  PointerTable &operator=(const PointerTable &other);
25  bool operator==(const PointerTable &other) const;
26  bool operator!=(const PointerTable &other) const;
27 
28  void reserve(void *user_context, size_t capacity, bool free_existing = false);
29  void resize(void *user_context, size_t entry_count, bool realloc = true);
30 
31  void assign(void *user_context, size_t index, const void *entry_ptr);
32  void insert(void *user_context, size_t index, const void *entry_ptr);
33  void prepend(void *user_context, const void *entry_ptr);
34  void append(void *user_context, const void *entry_ptr);
35  void remove(void *user_context, size_t index);
36 
37  void fill(void *user_context, const void **array, size_t array_size);
38  void insert(void *user_context, size_t index, const void **array, size_t array_size);
39  void replace(void *user_context, size_t index, const void **array, size_t array_size);
40  void prepend(void *user_context, const void **array, size_t array_size);
41  void append(void *user_context, const void **array, size_t array_size);
42  void remove(void *user_context, size_t index, size_t entry_count);
43 
44  void pop_front(void *user_context);
45  void pop_back(void *user_context);
46  void shrink_to_fit(void *user_context);
47  void clear(void *user_context);
48  void destroy(void *user_context);
49 
50  bool empty() const;
51  size_t size() const;
52 
53  void *operator[](size_t index);
54  void *operator[](size_t index) const;
55 
56  void **data();
57  const void **data() const;
58 
59  void *front();
60  void *back();
61 
64 
65 private:
66  void allocate(void *user_context, size_t capacity);
67 
68  void **ptr = nullptr;
69  size_t count = 0;
70  size_t capacity = 0;
71  SystemMemoryAllocatorFns allocator;
72 };
73 
74 PointerTable::PointerTable(void *user_context, size_t initial_capacity, const SystemMemoryAllocatorFns &sma)
75  : allocator(sma) {
76  halide_debug_assert(user_context, allocator.allocate != nullptr);
77  halide_debug_assert(user_context, allocator.deallocate != nullptr);
78  if (initial_capacity) {
79  reserve(user_context, initial_capacity);
80  }
81 }
82 
84  : PointerTable(nullptr, 0, other.allocator) {
85  if (other.capacity) {
86  ptr = static_cast<void **>(allocator.allocate(nullptr, other.capacity * sizeof(void *)));
87  capacity = other.capacity;
88  }
89  if (ptr && other.count != 0) {
90  count = other.count;
91  memcpy(this->ptr, other.ptr, count * sizeof(void *));
92  }
93 }
94 
96  destroy(nullptr);
97 }
98 
99 void PointerTable::destroy(void *user_context) {
100  halide_debug_assert(user_context, allocator.deallocate != nullptr);
101  if (ptr != nullptr) {
102  allocator.deallocate(user_context, ptr);
103  }
104  capacity = count = 0;
105  ptr = nullptr;
106 }
107 
108 void PointerTable::initialize(void *user_context, size_t initial_capacity, const SystemMemoryAllocatorFns &sma) {
109  allocator = sma;
110  capacity = count = 0;
111  ptr = nullptr;
112  if (initial_capacity) {
113  reserve(user_context, initial_capacity);
114  }
115 }
116 
118  if (&other != this) {
119  resize(nullptr, other.count);
120  if (count != 0 && other.ptr != nullptr) {
121  memcpy(ptr, other.ptr, count * sizeof(void *));
122  }
123  }
124  return *this;
125 }
126 
127 bool PointerTable::operator==(const PointerTable &other) const {
128  if (count != other.count) {
129  return false;
130  }
131  return memcmp(this->ptr, other.ptr, this->size() * sizeof(void *)) == 0;
132 }
133 
134 bool PointerTable::operator!=(const PointerTable &other) const {
135  return !(*this == other);
136 }
137 
138 void PointerTable::fill(void *user_context, const void **array, size_t array_size) {
139  if (array_size != 0) {
140  resize(user_context, array_size);
141  memcpy(this->ptr, array, array_size * sizeof(void *));
142  count = array_size;
143  }
144 }
145 
146 void PointerTable::assign(void *user_context, size_t index, const void *entry_ptr) {
147  halide_debug_assert(user_context, index < count);
148  ptr[index] = const_cast<void *>(entry_ptr);
149 }
150 
151 void PointerTable::prepend(void *user_context, const void *entry_ptr) {
152  insert(user_context, 0, &entry_ptr, 1);
153 }
154 
155 void PointerTable::append(void *user_context, const void *entry_ptr) {
156  append(user_context, &entry_ptr, 1);
157 }
158 
159 void PointerTable::pop_front(void *user_context) {
160  halide_debug_assert(user_context, count > 0);
161  remove(user_context, 0);
162 }
163 
164 void PointerTable::pop_back(void *user_context) {
165  halide_debug_assert(user_context, count > 0);
166  resize(user_context, size() - 1);
167 }
168 
169 void PointerTable::clear(void *user_context) {
170  resize(user_context, 0);
171 }
172 
173 void PointerTable::reserve(void *user_context, size_t new_capacity, bool free_existing) {
174  new_capacity = max(new_capacity, count);
175  if ((new_capacity < capacity) && !free_existing) {
176  new_capacity = capacity;
177  }
178  allocate(user_context, new_capacity);
179 }
180 
181 void PointerTable::resize(void *user_context, size_t entry_count, bool realloc) {
182  size_t current_size = capacity;
183  size_t requested_size = entry_count;
184  size_t minimum_size = default_capacity;
185  size_t actual_size = current_size;
186  count = requested_size;
187 
188 #ifdef DEBUG_RUNTIME_INTERNAL
189  debug(user_context) << "PointerTable: Resize ("
190  << "requested_size=" << (int32_t)requested_size << " "
191  << "current_size=" << (int32_t)current_size << " "
192  << "minimum_size=" << (int32_t)minimum_size << " "
193  << "sizeof(void*)=" << (int32_t)sizeof(void *) << " "
194  << "realloc=" << (realloc ? "true" : "false") << ")...\n";
195 #endif
196 
197  // increase capacity upto 1.5x existing (or at least min_capacity)
198  if (requested_size > current_size) {
199  actual_size = max(requested_size, max(current_size * 3 / 2, minimum_size));
200  } else if (!realloc) {
201  return;
202  }
203 
204  allocate(user_context, actual_size);
205 }
206 
207 void PointerTable::shrink_to_fit(void *user_context) {
208  if (capacity > count) {
209  void *new_ptr = nullptr;
210  if (count > 0) {
211  size_t bytes = count * sizeof(void *);
212  new_ptr = allocator.allocate(user_context, bytes);
213  memcpy(new_ptr, ptr, bytes);
214  }
215  allocator.deallocate(user_context, ptr);
216  capacity = count;
217  ptr = static_cast<void **>(new_ptr);
218  }
219 }
220 
221 void PointerTable::insert(void *user_context, size_t index, const void *entry_ptr) {
222  const void *addr = reinterpret_cast<const void *>(entry_ptr);
223  insert(user_context, index, &addr, 1);
224 }
225 
226 void PointerTable::remove(void *user_context, size_t index) {
227  remove(user_context, index, 1);
228 }
229 
230 void PointerTable::remove(void *user_context, size_t index, size_t entry_count) {
231  halide_debug_assert(user_context, index < count);
232  const size_t last_index = size();
233  if (index < (last_index - entry_count)) {
234  size_t dst_offset = index * sizeof(void *);
235  size_t src_offset = (index + entry_count) * sizeof(void *);
236  size_t bytes = (last_index - index - entry_count) * sizeof(void *);
237 
238 #ifdef DEBUG_RUNTIME_INTERNAL
239  debug(user_context) << "PointerTable: Remove ("
240  << "index=" << (int32_t)index << " "
241  << "entry_count=" << (int32_t)entry_count << " "
242  << "last_index=" << (int32_t)last_index << " "
243  << "src_offset=" << (int32_t)src_offset << " "
244  << "dst_offset=" << (int32_t)dst_offset << " "
245  << "bytes=" << (int32_t)bytes << ")...\n";
246 #endif
247  memmove(ptr + dst_offset, ptr + src_offset, bytes);
248  }
249  resize(user_context, last_index - entry_count);
250 }
251 
252 void PointerTable::replace(void *user_context, size_t index, const void **array, size_t array_size) {
253  halide_debug_assert(user_context, index < count);
254  size_t remaining = count - index;
255  size_t copy_count = min(remaining, array_size);
256 
257 #ifdef DEBUG_RUNTIME_INTERNAL
258  debug(user_context) << "PointerTable: Replace ("
259  << "index=" << (int32_t)index << " "
260  << "array_size=" << (int32_t)array_size << " "
261  << "remaining=" << (int32_t)remaining << " "
262  << "copy_count=" << (int32_t)copy_count << " "
263  << "capacity=" << (int32_t)capacity << ")...\n";
264 #endif
265 
266  halide_debug_assert(user_context, remaining > 0);
267  memcpy(ptr + index, array, copy_count * sizeof(void *));
268  count = max(count, index + copy_count);
269 }
270 
271 void PointerTable::insert(void *user_context, size_t index, const void **array, size_t array_size) {
272  halide_debug_assert(user_context, index <= count);
273  const size_t last_index = size();
274  resize(user_context, last_index + array_size);
275  if (index < last_index) {
276  size_t src_offset = index * sizeof(void *);
277  size_t dst_offset = (index + array_size) * sizeof(void *);
278  size_t bytes = (last_index - index) * sizeof(void *);
279  memmove(ptr + dst_offset, ptr + src_offset, bytes);
280  }
281  replace(user_context, index, array, array_size);
282 }
283 
284 void PointerTable::prepend(void *user_context, const void **array, size_t array_size) {
285  insert(user_context, 0, array, array_size);
286 }
287 
288 void PointerTable::append(void *user_context, const void **array, size_t array_size) {
289  const size_t last_index = size();
290  insert(user_context, last_index, array, array_size);
291 }
292 
293 bool PointerTable::empty() const {
294  return count == 0;
295 }
296 
297 size_t PointerTable::size() const {
298  return count;
299 }
300 
301 void *PointerTable::operator[](size_t index) {
302  halide_debug_assert(nullptr, index < capacity);
303  return ptr[index];
304 }
305 
306 void *PointerTable::operator[](size_t index) const {
307  halide_debug_assert(nullptr, index < capacity);
308  return ptr[index];
309 }
310 
312  return ptr;
313 }
314 
316  halide_debug_assert(nullptr, count > 0);
317  return ptr[0];
318 }
319 
321  halide_debug_assert(nullptr, count > 0);
322  size_t index = count - 1;
323  return ptr[index];
324 }
325 
326 const void **PointerTable::data() const {
327  return const_cast<const void **>(ptr);
328 }
329 
330 void PointerTable::allocate(void *user_context, size_t new_capacity) {
331  if (new_capacity != capacity) {
332  halide_debug_assert(user_context, allocator.allocate != nullptr);
333  size_t bytes = new_capacity * sizeof(void *);
334 
335 #ifdef DEBUG_RUNTIME_INTERNAL
336  debug(user_context) << "PointerTable: Allocating (bytes=" << (int32_t)bytes << " allocator=" << (void *)allocator.allocate << ")...\n";
337 #endif
338 
339  void *new_ptr = bytes ? allocator.allocate(user_context, bytes) : nullptr;
340  if (count != 0 && ptr != nullptr && new_ptr != nullptr) {
341  memcpy(new_ptr, ptr, count * sizeof(void *));
342  }
343  if (ptr != nullptr) {
344  halide_debug_assert(user_context, allocator.deallocate != nullptr);
345  allocator.deallocate(user_context, ptr);
346  }
347  capacity = new_capacity;
348  ptr = static_cast<void **>(new_ptr);
349  }
350 }
351 
352 const SystemMemoryAllocatorFns &
354  return this->allocator;
355 }
356 
359  static SystemMemoryAllocatorFns native_allocator = {
361  return native_allocator;
362 }
363 
364 // --
365 
366 } // namespace Internal
367 } // namespace Runtime
368 } // namespace Halide
369 
370 #endif // HALIDE_RUNTIME_POINTER_TABLE_H
Halide::Runtime::Internal::PointerTable::size
size_t size() const
Definition: pointer_table.h:297
int32_t
signed __INT32_TYPE__ int32_t
Definition: runtime_internal.h:24
Halide::Runtime::Internal::PointerTable::operator!=
bool operator!=(const PointerTable &other) const
Definition: pointer_table.h:134
Halide::Runtime::Internal::PointerTable::~PointerTable
~PointerTable()
Definition: pointer_table.h:95
Halide::Runtime::Internal::native_system_free
ALWAYS_INLINE void native_system_free(void *user_context, void *ptr)
Definition: memory_resources.h:189
Halide::Runtime::Internal::PointerTable::insert
void insert(void *user_context, size_t index, const void *entry_ptr)
Definition: pointer_table.h:221
memcmp
int memcmp(const void *s1, const void *s2, size_t n)
Halide::min
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:584
halide_debug_assert
#define halide_debug_assert(user_context, cond)
halide_debug_assert() is like halide_assert(), but only expands into a check when DEBUG_RUNTIME is de...
Definition: runtime_internal.h:281
Halide::Runtime::Internal::PointerTable::assign
void assign(void *user_context, size_t index, const void *entry_ptr)
Definition: pointer_table.h:146
Halide::Runtime::Internal::PointerTable
Definition: pointer_table.h:14
Halide::Runtime::Internal::PointerTable::back
void * back()
Definition: pointer_table.h:320
Halide::Runtime::Internal::SystemMemoryAllocatorFns::allocate
AllocateSystemFn allocate
Definition: memory_resources.h:194
Halide::Runtime::Internal::PointerTable::empty
bool empty() const
Definition: pointer_table.h:293
Halide::Runtime::Internal::PointerTable::remove
void remove(void *user_context, size_t index)
Definition: pointer_table.h:226
Halide::Runtime::Internal::PointerTable::pop_front
void pop_front(void *user_context)
Definition: pointer_table.h:159
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
memmove
void * memmove(void *dest, const void *src, size_t n)
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Runtime::Internal::PointerTable::resize
void resize(void *user_context, size_t entry_count, bool realloc=true)
Definition: pointer_table.h:181
Halide::Runtime::Internal::PointerTable::operator[]
void * operator[](size_t index)
Definition: pointer_table.h:301
Halide::Runtime::Internal::PointerTable::operator=
PointerTable & operator=(const PointerTable &other)
Definition: pointer_table.h:117
Halide::Runtime::Internal::PointerTable::clear
void clear(void *user_context)
Definition: pointer_table.h:169
Halide::Runtime::Internal::PointerTable::reserve
void reserve(void *user_context, size_t capacity, bool free_existing=false)
Definition: pointer_table.h:173
Halide::Runtime::Internal::SystemMemoryAllocatorFns::deallocate
DeallocateSystemFn deallocate
Definition: memory_resources.h:195
Halide::Runtime::Internal::PointerTable::append
void append(void *user_context, const void *entry_ptr)
Definition: pointer_table.h:155
Halide::Runtime::Internal::PointerTable::data
void ** data()
Definition: pointer_table.h:311
Halide::Runtime::Internal::PointerTable::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition: pointer_table.h:358
memory_resources.h
Halide::Runtime::Internal::native_system_malloc
ALWAYS_INLINE void * native_system_malloc(void *user_context, size_t bytes)
Definition: memory_resources.h:185
Halide::Runtime::Internal::PointerTable::fill
void fill(void *user_context, const void **array, size_t array_size)
Definition: pointer_table.h:138
Halide::Runtime::Internal::PointerTable::operator==
bool operator==(const PointerTable &other) const
Definition: pointer_table.h:127
Halide::Runtime::Internal::PointerTable::default_capacity
static constexpr size_t default_capacity
Definition: pointer_table.h:16
Halide::Runtime::Internal::PointerTable::pop_back
void pop_back(void *user_context)
Definition: pointer_table.h:164
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
Halide::Runtime::Internal::SystemMemoryAllocatorFns
Definition: memory_resources.h:193
Halide::Runtime::Internal::PointerTable::initialize
void initialize(void *user_context, size_t initial_capacity=0, const SystemMemoryAllocatorFns &sma=default_allocator())
Definition: pointer_table.h:108
Halide::Runtime::Internal::PointerTable::front
void * front()
Definition: pointer_table.h:315
Halide::Runtime::Internal::PointerTable::shrink_to_fit
void shrink_to_fit(void *user_context)
Definition: pointer_table.h:207
Halide::Runtime::Internal::PointerTable::prepend
void prepend(void *user_context, const void *entry_ptr)
Definition: pointer_table.h:151
Halide::max
Expr max(const FuncRef &a, const FuncRef &b)
Definition: Func.h:587
Halide::Runtime::Internal::PointerTable::PointerTable
PointerTable(void *user_context, size_t initial_capacity=0, const SystemMemoryAllocatorFns &sma=default_allocator())
Definition: pointer_table.h:74
Halide::Runtime::Internal::PointerTable::replace
void replace(void *user_context, size_t index, const void **array, size_t array_size)
Definition: pointer_table.h:252
Halide::Runtime::Internal::PointerTable::current_allocator
const SystemMemoryAllocatorFns & current_allocator() const
Definition: pointer_table.h:353
Halide::Runtime::Internal::PointerTable::destroy
void destroy(void *user_context)
Definition: pointer_table.h:99