Halide 22.0.0 Halide compiler and libraries

linked_list.h
Go to the documentation of this file.
1#ifndef HALIDE_RUNTIME_LINKED_LIST_H
2#define HALIDE_RUNTIME_LINKED_LIST_H
3
4#include "../HalideRuntime.h"
5#include "memory_arena.h"
6
7 namespace Halide {
8 namespace Runtime {
9 namespace Internal {
10
11// Doubly linked list container
12// -- Implemented using MemoryArena for allocation
13 class LinkedList {
14 public:
15 // Disable copy support
16 LinkedList(const LinkedList &) = delete;
17 LinkedList &operator=(const LinkedList &) = delete;
18
19 // Default initial capacity
20 static constexpr uint32_t default_capacity = uint32_t(32); // smallish
21
22 // List entry
23 struct EntryType {
24 void *value = nullptr;
25 EntryType *prev_ptr = nullptr;
26 EntryType *next_ptr = nullptr;
27 };
28
29 LinkedList(void *user_context, uint32_t entry_size, uint32_t capacity = default_capacity,
30 const SystemMemoryAllocatorFns &allocator = default_allocator());
31 ~LinkedList();
32
33 void initialize(void *user_context, uint32_t entry_size, uint32_t capacity = default_capacity,
34 const SystemMemoryAllocatorFns &allocator = default_allocator());
35
36 EntryType *front();
37 EntryType *back();
38
39 const EntryType *front() const;
40 const EntryType *back() const;
41
42 EntryType *prepend(void *user_context);
43 EntryType *prepend(void *user_context, const void *value);
44
45 EntryType *append(void *user_context);
46 EntryType *append(void *user_context, const void *value);
47
48 void pop_front(void *user_context);
49 void pop_back(void *user_context);
50
51 EntryType *insert_before(void *user_context, EntryType *entry_ptr);
52 EntryType *insert_before(void *user_context, EntryType *entry_ptr, const void *value);
53
54 EntryType *insert_after(void *user_context, EntryType *entry_ptr);
55 EntryType *insert_after(void *user_context, EntryType *entry_ptr, const void *value);
56
57 void remove(void *user_context, EntryType *entry_ptr);
58 void clear(void *user_context);
59 void destroy(void *user_context);
60
61 size_t size() const;
62 bool empty() const;
63
64 const SystemMemoryAllocatorFns &current_allocator() const;
65 static const SystemMemoryAllocatorFns &default_allocator();
66
67 private:
68 EntryType *reserve(void *user_context);
69 void reclaim(void *user_context, EntryType *entry_ptr);
70
71 MemoryArena *link_arena = nullptr;
72 MemoryArena *data_arena = nullptr;
73 EntryType *front_ptr = nullptr;
74 EntryType *back_ptr = nullptr;
75 size_t entry_count = 0;
76};
77
78 LinkedList::LinkedList(void *user_context, uint32_t entry_size, uint32_t capacity,
79 const SystemMemoryAllocatorFns &sma) {
80 uint32_t arena_capacity = max(capacity, MemoryArena::default_capacity);
81 link_arena = MemoryArena::create(user_context, {sizeof(EntryType), arena_capacity, 0}, sma);
82 data_arena = MemoryArena::create(user_context, {entry_size, arena_capacity, 0}, sma);
83 front_ptr = nullptr;
84 back_ptr = nullptr;
85 entry_count = 0;
86}
87
88 LinkedList::~LinkedList() {
89 destroy(nullptr);
90}
91
92 void LinkedList::initialize(void *user_context, uint32_t entry_size, uint32_t capacity,
93 const SystemMemoryAllocatorFns &sma) {
94 uint32_t arena_capacity = max(capacity, MemoryArena::default_capacity);
95 link_arena = MemoryArena::create(user_context, {sizeof(EntryType), arena_capacity, 0}, sma);
96 data_arena = MemoryArena::create(user_context, {entry_size, arena_capacity, 0}, sma);
97 front_ptr = nullptr;
98 back_ptr = nullptr;
99 entry_count = 0;
100}
101
102 void LinkedList::destroy(void *user_context) {
103 clear(nullptr);
104 if (link_arena) {
105 MemoryArena::destroy(nullptr, link_arena);
106 }
107 if (data_arena) {
108 MemoryArena::destroy(nullptr, data_arena);
109 }
110 link_arena = nullptr;
111 data_arena = nullptr;
112 front_ptr = nullptr;
113 back_ptr = nullptr;
114 entry_count = 0;
115}
116
117 typename LinkedList::EntryType *LinkedList::front() {
118 return front_ptr;
119}
120
121 typename LinkedList::EntryType *LinkedList::back() {
122 return back_ptr;
123}
124
125 const typename LinkedList::EntryType *LinkedList::front() const {
126 return front_ptr;
127}
128
129 const typename LinkedList::EntryType *LinkedList::back() const {
130 return back_ptr;
131}
132
133 typename LinkedList::EntryType *
134 LinkedList::prepend(void *user_context) {
135 EntryType *entry_ptr = reserve(user_context);
136 if (empty()) {
137 front_ptr = entry_ptr;
138 back_ptr = entry_ptr;
139 entry_count = 1;
140 } else {
141 entry_ptr->next_ptr = front_ptr;
142 front_ptr->prev_ptr = entry_ptr;
143 front_ptr = entry_ptr;
144 ++entry_count;
145 }
146 return entry_ptr;
147}
148
149 typename LinkedList::EntryType *
150 LinkedList::append(void *user_context) {
151 EntryType *entry_ptr = reserve(user_context);
152 if (empty()) {
153 front_ptr = entry_ptr;
154 back_ptr = entry_ptr;
155 entry_count = 1;
156 } else {
157 entry_ptr->prev_ptr = back_ptr;
158 back_ptr->next_ptr = entry_ptr;
159 back_ptr = entry_ptr;
160 ++entry_count;
161 }
162 return entry_ptr;
163}
164
165 typename LinkedList::EntryType *
166 LinkedList::prepend(void *user_context, const void *value) {
167 EntryType *entry_ptr = prepend(user_context);
168 memcpy(entry_ptr->value, value, data_arena->current_config().entry_size);
169 return entry_ptr;
170}
171
172 typename LinkedList::EntryType *
173 LinkedList::append(void *user_context, const void *value) {
174 EntryType *entry_ptr = append(user_context);
175 memcpy(entry_ptr->value, value, data_arena->current_config().entry_size);
176 return entry_ptr;
177}
178
179 void LinkedList::pop_front(void *user_context) {
180 halide_debug_assert(user_context, (entry_count > 0));
181 EntryType *remove_ptr = front_ptr;
182 EntryType *next_ptr = remove_ptr->next_ptr;
183 if (next_ptr != nullptr) {
184 next_ptr->prev_ptr = nullptr;
185 }
186 front_ptr = next_ptr;
187 reclaim(user_context, remove_ptr);
188 --entry_count;
189}
190
191 void LinkedList::pop_back(void *user_context) {
192 halide_debug_assert(user_context, (entry_count > 0));
193 EntryType *remove_ptr = back_ptr;
194 EntryType *prev_ptr = remove_ptr->prev_ptr;
195 if (prev_ptr != nullptr) {
196 prev_ptr->next_ptr = nullptr;
197 }
198 back_ptr = prev_ptr;
199 reclaim(user_context, remove_ptr);
200 --entry_count;
201}
202
203 void LinkedList::clear(void *user_context) {
204 if (empty() == false) {
205 EntryType *remove_ptr = back_ptr;
206 while (remove_ptr != nullptr) {
207 EntryType *prev_ptr = remove_ptr->prev_ptr;
208 reclaim(user_context, remove_ptr);
209 remove_ptr = prev_ptr;
210 }
211 front_ptr = nullptr;
212 back_ptr = nullptr;
213 entry_count = 0;
214 }
215}
216
217 void LinkedList::remove(void *user_context, EntryType *entry_ptr) {
218 halide_debug_assert(user_context, (entry_ptr != nullptr));
219 halide_debug_assert(user_context, (entry_count > 0));
220
221 if (entry_ptr->prev_ptr != nullptr) {
222 entry_ptr->prev_ptr->next_ptr = entry_ptr->next_ptr;
223 } else {
224 halide_debug_assert(user_context, (front_ptr == entry_ptr));
225 front_ptr = entry_ptr->next_ptr;
226 }
227
228 if (entry_ptr->next_ptr != nullptr) {
229 entry_ptr->next_ptr->prev_ptr = entry_ptr->prev_ptr;
230 } else {
231 halide_debug_assert(user_context, (back_ptr == entry_ptr));
232 back_ptr = entry_ptr->prev_ptr;
233 }
234
235 reclaim(user_context, entry_ptr);
236 --entry_count;
237}
238
239 typename LinkedList::EntryType *
240 LinkedList::insert_before(void *user_context, EntryType *entry_ptr) {
241 if (entry_ptr != nullptr) {
242 EntryType *prev_ptr = entry_ptr->prev_ptr;
243 EntryType *new_ptr = reserve(user_context);
244 new_ptr->prev_ptr = prev_ptr;
245 new_ptr->next_ptr = entry_ptr;
246 entry_ptr->prev_ptr = new_ptr;
247 if (prev_ptr != nullptr) {
248 prev_ptr->next_ptr = new_ptr;
249 } else {
250 halide_debug_assert(user_context, (front_ptr == entry_ptr));
251 front_ptr = new_ptr;
252 }
253 ++entry_count;
254 return new_ptr;
255 } else {
256 return append(user_context);
257 }
258}
259
260 typename LinkedList::EntryType *
261 LinkedList::insert_after(void *user_context, EntryType *entry_ptr) {
262 if (entry_ptr != nullptr) {
263 EntryType *next_ptr = entry_ptr->next_ptr;
264 EntryType *new_ptr = reserve(user_context);
265 new_ptr->next_ptr = next_ptr;
266 new_ptr->prev_ptr = entry_ptr;
267 entry_ptr->next_ptr = new_ptr;
268 if (next_ptr != nullptr) {
269 next_ptr->prev_ptr = new_ptr;
270 } else {
271 halide_debug_assert(user_context, (back_ptr == entry_ptr));
272 back_ptr = new_ptr;
273 }
274 ++entry_count;
275 return new_ptr;
276 } else {
277 return prepend(user_context);
278 }
279}
280
281 typename LinkedList::EntryType *
282 LinkedList::insert_before(void *user_context, EntryType *entry_ptr, const void *value) {
283 EntryType *new_ptr = insert_before(user_context, entry_ptr);
284 memcpy(new_ptr->value, value, data_arena->current_config().entry_size);
285 return new_ptr;
286}
287
288 typename LinkedList::EntryType *
289 LinkedList::insert_after(void *user_context, EntryType *entry_ptr, const void *value) {
290 EntryType *new_ptr = insert_after(user_context, entry_ptr);
291 memcpy(new_ptr->value, value, data_arena->current_config().entry_size);
292 return new_ptr;
293}
294
295 size_t LinkedList::size() const {
296 return entry_count;
297}
298
299 bool LinkedList::empty() const {
300 return entry_count == 0;
301}
302
303 const SystemMemoryAllocatorFns &
304 LinkedList::current_allocator() const {
305 return link_arena->current_allocator();
306}
307
308 const SystemMemoryAllocatorFns &
309 LinkedList::default_allocator() {
310 return MemoryArena::default_allocator();
311}
312
313 typename LinkedList::EntryType *
314LinkedList::reserve(void *user_context) {
315 EntryType *entry_ptr = static_cast<EntryType *>(
316 link_arena->reserve(user_context, true));
317 entry_ptr->value = data_arena->reserve(user_context, true);
318 entry_ptr->next_ptr = nullptr;
319 entry_ptr->prev_ptr = nullptr;
320 return entry_ptr;
321}
322
323 void LinkedList::reclaim(void *user_context, EntryType *entry_ptr) {
324 void *value_ptr = entry_ptr->value;
325 entry_ptr->value = nullptr;
326 entry_ptr->next_ptr = nullptr;
327 entry_ptr->prev_ptr = nullptr;
328 data_arena->reclaim(user_context, value_ptr);
329 link_arena->reclaim(user_context, entry_ptr);
330}
331
332// --
333
334} // namespace Internal
335} // namespace Runtime
336} // namespace Halide
337
338#endif // HALIDE_RUNTIME_LINKED_LIST_H
Halide::Runtime::Internal::LinkedList
Definition: linked_list.h:13
Halide::Runtime::Internal::LinkedList::initialize
void initialize(void *user_context, uint32_t entry_size, uint32_t capacity=default_capacity, const SystemMemoryAllocatorFns &allocator=default_allocator())
Definition: linked_list.h:92
Halide::Runtime::Internal::LinkedList::prepend
EntryType * prepend(void *user_context)
Definition: linked_list.h:134
Halide::Runtime::Internal::LinkedList::current_allocator
const SystemMemoryAllocatorFns & current_allocator() const
Definition: linked_list.h:304
Halide::Runtime::Internal::LinkedList::back
EntryType * back()
Definition: linked_list.h:121
Halide::Runtime::Internal::LinkedList::append
EntryType * append(void *user_context)
Definition: linked_list.h:150
Halide::Runtime::Internal::LinkedList::empty
bool empty() const
Definition: linked_list.h:299
Halide::Runtime::Internal::LinkedList::clear
void clear(void *user_context)
Definition: linked_list.h:203
Halide::Runtime::Internal::LinkedList::pop_front
void pop_front(void *user_context)
Definition: linked_list.h:179
Halide::Runtime::Internal::LinkedList::operator=
LinkedList & operator=(const LinkedList &)=delete
Halide::Runtime::Internal::LinkedList::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition: linked_list.h:309
Halide::Runtime::Internal::LinkedList::insert_after
EntryType * insert_after(void *user_context, EntryType *entry_ptr)
Definition: linked_list.h:261
Halide::Runtime::Internal::LinkedList::remove
void remove(void *user_context, EntryType *entry_ptr)
Definition: linked_list.h:217
Halide::Runtime::Internal::LinkedList::pop_back
void pop_back(void *user_context)
Definition: linked_list.h:191
Halide::Runtime::Internal::LinkedList::size
size_t size() const
Definition: linked_list.h:295
Halide::Runtime::Internal::LinkedList::destroy
void destroy(void *user_context)
Definition: linked_list.h:102
Halide::Runtime::Internal::LinkedList::default_capacity
static constexpr uint32_t default_capacity
Definition: linked_list.h:20
Halide::Runtime::Internal::LinkedList::LinkedList
LinkedList(const LinkedList &)=delete
Halide::Runtime::Internal::LinkedList::~LinkedList
~LinkedList()
Definition: linked_list.h:88
Halide::Runtime::Internal::LinkedList::insert_before
EntryType * insert_before(void *user_context, EntryType *entry_ptr)
Definition: linked_list.h:240
Halide::Runtime::Internal::LinkedList::front
EntryType * front()
Definition: linked_list.h:117
Halide::Runtime::Internal::MemoryArena
Definition: memory_arena.h:17
Halide::Runtime::Internal::MemoryArena::reserve
void * reserve(void *user_context, bool initialize=false)
Definition: memory_arena.h:155
Halide::Runtime::Internal::MemoryArena::create
static MemoryArena * create(void *user_context, const Config &config, const SystemMemoryAllocatorFns &allocator=default_allocator())
Definition: memory_arena.h:101
Halide::Runtime::Internal::MemoryArena::current_config
const Config & current_config() const
Definition: memory_arena.h:287
Halide::Runtime::Internal::MemoryArena::default_capacity
static constexpr uint32_t default_capacity
Definition: memory_arena.h:24
Halide::Runtime::Internal::MemoryArena::current_allocator
const SystemMemoryAllocatorFns & current_allocator() const
Definition: memory_arena.h:298
Halide::Runtime::Internal::MemoryArena::destroy
static void destroy(void *user_context, MemoryArena *arena)
Definition: memory_arena.h:115
Halide::Runtime::Internal::MemoryArena::reclaim
void reclaim(void *user_context, void *ptr)
Definition: memory_arena.h:182
Halide::Runtime::Internal::MemoryArena::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition: memory_arena.h:303
memory_arena.h
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::max
Expr max(const FuncRef &a, const FuncRef &b)
Definition: Func.h:614
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:290
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition: runtime_internal.h:25
Halide::Runtime::Internal::LinkedList::EntryType
Definition: linked_list.h:23
Halide::Runtime::Internal::LinkedList::EntryType::prev_ptr
EntryType * prev_ptr
Definition: linked_list.h:25
Halide::Runtime::Internal::LinkedList::EntryType::next_ptr
EntryType * next_ptr
Definition: linked_list.h:26
Halide::Runtime::Internal::LinkedList::EntryType::value
void * value
Definition: linked_list.h:24
Halide::Runtime::Internal::MemoryArena::Config::entry_size
uint32_t entry_size
Definition: memory_arena.h:28
Halide::Runtime::Internal::SystemMemoryAllocatorFns
Definition: memory_resources.h:193
user_context
void * user_context
Definition: vulkan_resources.h:178
allocator
VulkanMemoryAllocator * allocator
Definition: vulkan_resources.h:179