Halide 19.0.0
Halide compiler and libraries
Loading...
Searching...
No Matches
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
7namespace Halide {
8namespace Runtime {
9namespace Internal {
10
11// Dynamically resizable array for storing untyped pointers
12// -- Implementation uses memcpy/memmove for copying
13// -- Customizable allocator ... default uses NativeSystemAllocator
15public:
16 static constexpr size_t default_capacity = 32; // smallish
17
18 explicit PointerTable(void *user_context, size_t initial_capacity = 0, const SystemMemoryAllocatorFns &sma = default_allocator());
19 PointerTable(const PointerTable &other);
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
65private:
66 void allocate(void *user_context, size_t capacity);
67
68 void **ptr = nullptr;
69 size_t count = 0;
70 size_t capacity = 0;
72};
73
74PointerTable::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
98
99void 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
108void 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
127bool 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
134bool PointerTable::operator!=(const PointerTable &other) const {
135 return !(*this == other);
136}
137
138void 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
146void 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
151void PointerTable::prepend(void *user_context, const void *entry_ptr) {
152 insert(user_context, 0, &entry_ptr, 1);
153}
154
155void PointerTable::append(void *user_context, const void *entry_ptr) {
156 append(user_context, &entry_ptr, 1);
157}
158
159void PointerTable::pop_front(void *user_context) {
160 halide_debug_assert(user_context, count > 0);
161 remove(user_context, 0);
162}
163
164void PointerTable::pop_back(void *user_context) {
165 halide_debug_assert(user_context, count > 0);
166 resize(user_context, size() - 1);
167}
168
169void PointerTable::clear(void *user_context) {
170 resize(user_context, 0);
171}
172
173void 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
181void 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
207void 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
221void 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
226void PointerTable::remove(void *user_context, size_t index) {
227 remove(user_context, index, 1);
228}
229
230void 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
252void 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
271void 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
284void PointerTable::prepend(void *user_context, const void **array, size_t array_size) {
285 insert(user_context, 0, array, array_size);
286}
287
288void 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
294 return count == 0;
295}
296
297size_t PointerTable::size() const {
298 return count;
299}
300
301void *PointerTable::operator[](size_t index) {
302 halide_debug_assert(nullptr, index < capacity);
303 return ptr[index];
304}
305
306void *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
326const void **PointerTable::data() const {
327 return const_cast<const void **>(ptr);
328}
329
330void 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
352const 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
This file declares the routines used by Halide internally in its runtime.
const SystemMemoryAllocatorFns & current_allocator() const
void fill(void *user_context, const void **array, size_t array_size)
PointerTable(void *user_context, size_t initial_capacity=0, const SystemMemoryAllocatorFns &sma=default_allocator())
void remove(void *user_context, size_t index)
void initialize(void *user_context, size_t initial_capacity=0, const SystemMemoryAllocatorFns &sma=default_allocator())
static const SystemMemoryAllocatorFns & default_allocator()
void shrink_to_fit(void *user_context)
bool operator==(const PointerTable &other) const
void prepend(void *user_context, const void *entry_ptr)
static constexpr size_t default_capacity
void replace(void *user_context, size_t index, const void **array, size_t array_size)
void reserve(void *user_context, size_t capacity, bool free_existing=false)
PointerTable & operator=(const PointerTable &other)
void resize(void *user_context, size_t entry_count, bool realloc=true)
void append(void *user_context, const void *entry_ptr)
void insert(void *user_context, size_t index, const void *entry_ptr)
bool operator!=(const PointerTable &other) const
void assign(void *user_context, size_t index, const void *entry_ptr)
ALWAYS_INLINE void * native_system_malloc(void *user_context, size_t bytes)
ALWAYS_INLINE void native_system_free(void *user_context, void *ptr)
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
@ Internal
Not visible externally, similar to 'static' linkage in C.
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition Func.h:597
Expr max(const FuncRef &a, const FuncRef &b)
Definition Func.h:600
void * memmove(void *dest, const void *src, size_t n)
#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...
signed __INT32_TYPE__ int32_t
void * memcpy(void *s1, const void *s2, size_t n)
int memcmp(const void *s1, const void *s2, size_t n)