Kestrel Interface
Loading...
Searching...
No Matches
kest_list.h
Go to the documentation of this file.
1#ifndef KEST_DYNAMIC_ARRAY_H_
2#define KEST_DYNAMIC_ARRAY_H_
3
4#define DECLARE_LIST(X) \
5typedef struct X##_list { \
6 X* entries; \
7 int count; \
8 int capacity; \
9 kest_allocator alloc; \
10} X##_list; \
11\
12int X##_list_init(X##_list *list); \
13int X##_list_init_with_allocator(X##_list *list, const kest_allocator *alloc); \
14int X##_list_init_reserved(X##_list *list, size_t n); \
15int X##_list_init_reserved_with_allocator(X##_list *list, size_t n, const kest_allocator *alloc); \
16int X##_list_reserve(X##_list *list, size_t n); \
17int X##_list_append(X##_list *list, X x); \
18int X##_list_append_ref(X##_list *list, const X *x); \
19int X##_list_destroy(X##_list *list); \
20int X##_list_destroy_all(X##_list *list, void (*destructor)(X *x)); \
21int X##_list_contains(X##_list *list, X x, int (*cmp)(const X*, const X*)); \
22int X##_list_contains_ref(X##_list *list, const X *x, int (*cmp)(const X*, const X*)); \
23int X##_list_index_of(X##_list *list, X x, int (*cmp)(const X*, const X*)); \
24int X##_list_index_of_ref(X##_list *list, const X *x, int (*cmp)(const X*, const X*));\
25X *X##_list_head(X##_list *list);\
26X *X##_list_tail(X##_list *list);\
27int X##_list_pop_tail(X##_list *list);\
28int X##_list_pop_destroy_tail(X##_list *list, void (*destructor)(X *x));\
29int X##_list_append_list(X##_list *list, X##_list *a);\
30int X##_list_drain_destroy(X##_list *list, void (*destructor)(X *x));\
31int X##_list_drain(X##_list *list);
32
33#define IMPLEMENT_LIST(X) \
34\
35int X##_list_init(X##_list *list) \
36{ \
37 return X##_list_init_with_allocator(list, NULL); \
38} \
39\
40int X##_list_init_with_allocator(X##_list *list, const kest_allocator *alloc) \
41{ \
42 if (!list) return ERR_NULL_PTR; \
43\
44 list->entries = NULL; \
45 list->count = 0; \
46 list->capacity = 0; \
47 list->alloc = alloc ? *alloc : (kest_allocator){0}; \
48\
49 return NO_ERROR; \
50} \
51\
52int X##_list_init_reserved(X##_list *list, size_t n) \
53{ \
54 return X##_list_init_reserved_with_allocator(list, n, NULL); \
55} \
56\
57int X##_list_init_reserved_with_allocator(X##_list *list, size_t n, const kest_allocator *alloc) \
58{ \
59 int r = X##_list_init_with_allocator(list, alloc); \
60 if (r != NO_ERROR) return r; \
61\
62 if (n == 0) return NO_ERROR; \
63\
64 list->entries = kest_allocator_alloc(&list->alloc, sizeof(X) * n); \
65 if (!list->entries) return ERR_ALLOC_FAIL; \
66\
67 memset(list->entries, 0, sizeof(X) * n); \
68 list->capacity = n; \
69\
70 return NO_ERROR; \
71} \
72\
73int X##_list_reserve(X##_list *list, size_t n) \
74{ \
75 if (!list) return ERR_NULL_PTR; \
76 if (!n) return NO_ERROR; \
77\
78 if (list->count + n <= list->capacity) \
79 return NO_ERROR; \
80\
81 size_t cap_needed = list->count + n - 1; \
82 cap_needed |= cap_needed >> 1; \
83 cap_needed |= cap_needed >> 2; \
84 cap_needed |= cap_needed >> 4; \
85 cap_needed |= cap_needed >> 8; \
86 cap_needed |= cap_needed >> 16; \
87 if (sizeof(size_t) > 4) cap_needed |= cap_needed >> 32; \
88 cap_needed += 1; \
89\
90 if (!list->entries) \
91 { \
92 list->entries = kest_allocator_alloc(&list->alloc, sizeof(X) * cap_needed); \
93 if (!list->entries) \
94 { \
95 list->count = 0; \
96 list->capacity = 0; \
97 return ERR_ALLOC_FAIL; \
98 } \
99 memset(list->entries, 0, sizeof(X) * cap_needed); \
100 } \
101 else \
102 { \
103 X *new_array = kest_allocator_realloc(&list->alloc, list->entries, sizeof(X) * cap_needed); \
104 if (!new_array) return ERR_ALLOC_FAIL; \
105\
106 list->entries = new_array; \
107 memset(&list->entries[list->count], 0, sizeof(X) * (cap_needed - list->count)); \
108 } \
109\
110 list->capacity = cap_needed; \
111 return NO_ERROR; \
112} \
113\
114int X##_list_append(X##_list *list, X x) \
115{ \
116 return X##_list_append_ref(list, &x); \
117} \
118\
119int X##_list_append_ref(X##_list *list, const X *x) \
120{ \
121 if (!list) return ERR_NULL_PTR; \
122 if (!x) return ERR_BAD_ARGS; \
123\
124 int r = X##_list_reserve(list, 1); \
125 if (r != NO_ERROR) return r; \
126\
127 memcpy(&list->entries[list->count], x, sizeof(X)); \
128 list->count++; \
129\
130 return NO_ERROR; \
131} \
132\
133int X##_list_destroy(X##_list *list) \
134{ \
135 if (!list) return ERR_NULL_PTR; \
136\
137 if (list->entries) \
138 kest_allocator_free(&list->alloc, list->entries); \
139\
140 list->entries = NULL; \
141 list->count = 0; \
142 list->capacity = 0; \
143\
144 return NO_ERROR; \
145} \
146\
147int X##_list_destroy_all(X##_list *list, void (*destructor)(X *x)) \
148{ \
149 if (!list) return ERR_NULL_PTR; \
150\
151 if (!list->entries) \
152 { \
153 list->count = 0; \
154 list->capacity = 0; \
155 return NO_ERROR; \
156 } \
157\
158 if (destructor) \
159 { \
160 for (int i = 0; i < list->count; i++) \
161 destructor(&list->entries[i]); \
162 } \
163\
164 kest_allocator_free(&list->alloc, list->entries); \
165\
166 list->entries = NULL; \
167 list->count = 0; \
168 list->capacity = 0; \
169\
170 return NO_ERROR; \
171} \
172\
173int X##_list_contains(X##_list *list, X x, int (*cmp)(const X*, const X*)) \
174{ \
175 return X##_list_contains_ref(list, &x, cmp); \
176} \
177\
178int X##_list_contains_ref(X##_list *list, const X *x, int (*cmp)(const X*, const X*)) \
179{ \
180 if (!list || !list->entries) return 0; \
181\
182 for (int i = 0; i < list->count && i < list->capacity; i++) \
183 { \
184 if (cmp) \
185 { \
186 if (cmp(&list->entries[i], x) == 0) return 1; \
187 } \
188 else \
189 { \
190 if (memcmp(&list->entries[i], x, sizeof(X)) == 0) return 1; \
191 } \
192 } \
193 return 0; \
194} \
195\
196int X##_list_index_of(X##_list *list, X x, int (*cmp)(const X*, const X*)) \
197{ \
198 return X##_list_index_of_ref(list, &x, cmp); \
199} \
200\
201int X##_list_index_of_ref(X##_list *list, const X *x, int (*cmp)(const X*, const X*)) \
202{ \
203 if (!list || !list->entries) return -1; \
204\
205 for (int i = 0; i < list->count && i < list->capacity; i++) \
206 { \
207 if (cmp) \
208 { \
209 if (cmp(&list->entries[i], x) == 0) return i; \
210 } \
211 else \
212 { \
213 if (memcmp(&list->entries[i], x, sizeof(X)) == 0) return i; \
214 } \
215 } \
216 return -1; \
217}\
218\
219X *X##_list_head(X##_list *list)\
220{\
221 if (!list)\
222 return NULL;\
223 \
224 if (!list->entries)\
225 return NULL;\
226 \
227 if (list->count < 1) return NULL;\
228 \
229 return &list->entries[0];\
230}\
231X *X##_list_tail(X##_list *list)\
232{\
233 if (!list)\
234 return NULL;\
235 \
236 if (!list->entries)\
237 return NULL;\
238 \
239 if (list->count < 1 || list->capacity < list->count) return NULL;\
240 \
241 return &list->entries[list->count - 1];\
242}\
243\
244int X##_list_pop_destroy_tail(X##_list *list, void (*destructor)(X *x))\
245{\
246 if (!list)\
247 return ERR_NULL_PTR;\
248 \
249 if (list->count > 0)\
250 {\
251 list->count--;\
252 destructor(&list->entries[list->count]);\
253 }\
254 \
255 return NO_ERROR;\
256}\
257\
258int X##_list_pop_tail(X##_list *list)\
259{\
260 if (!list)\
261 return ERR_NULL_PTR;\
262 \
263 if (list->count > 0)\
264 list->count--;\
265 \
266 return NO_ERROR;\
267}\
268\
269int X##_list_append_list(X##_list *list, X##_list *a)\
270{\
271 if (!list || !a)\
272 return ERR_NULL_PTR;\
273 \
274 if (a->count == 0)\
275 return NO_ERROR;\
276 \
277 if (!a->entries)\
278 return ERR_BAD_ARGS;\
279 \
280 X##_list_reserve(list, a->count);\
281 \
282 memcpy(&list->entries[list->count], a->entries, sizeof(X) * a->count);\
283 \
284 list->count += a->count;\
285 \
286 return NO_ERROR;\
287}\
288\
289int X##_list_drain_destroy(X##_list *list, void (*destructor)(X *x))\
290{\
291 if (!list)\
292 return ERR_NULL_PTR;\
293 \
294 \
295 for (int i = 0; i < list->count; i++)\
296 {\
297 if (destructor)\
298 destructor(&list->entries[i]);\
299 }\
300 list->count = 0;\
301 \
302 return NO_ERROR;\
303}\
304\
305int X##_list_drain(X##_list *list)\
306{\
307 if (!list)\
308 return ERR_NULL_PTR;\
309 \
310 list->count = 0;\
311 \
312 return NO_ERROR;\
313}
314
315#define DECLARE_PTR_LIST(X) \
316typedef struct X##_ptr_list { \
317 X** entries; \
318 int count; \
319 int capacity; \
320 kest_allocator alloc; \
321} X##_ptr_list; \
322\
323int X##_ptr_list_init(X##_ptr_list *list); \
324int X##_ptr_list_init_with_allocator(X##_ptr_list *list, const kest_allocator *alloc); \
325int X##_ptr_list_reserve(X##_ptr_list *list, size_t n); \
326int X##_ptr_list_append(X##_ptr_list *list, X *x); \
327int X##_ptr_list_destroy(X##_ptr_list *list); \
328int X##_ptr_list_destroy_all(X##_ptr_list *list, void (*destructor)(X *x)); \
329int X##_ptr_list_contains(X##_ptr_list *list, X *x); \
330int X##_ptr_list_index_of(X##_ptr_list *list, X *x); \
331X **X##_ptr_list_head(X##_ptr_list *list);\
332X **X##_ptr_list_tail(X##_ptr_list *list);\
333int X##_ptr_list_pop_tail(X##_ptr_list *list);\
334int X##_ptr_list_append_list(X##_ptr_list *list, X##_ptr_list *a);\
335int X##_ptr_list_drain_destroy(X##_ptr_list *list, void (*destructor)(X *x));\
336int X##_ptr_list_drain(X##_ptr_list *list);
337
338
339#define IMPLEMENT_PTR_LIST(X) \
340\
341int X##_ptr_list_init(X##_ptr_list *list) \
342{ \
343 return X##_ptr_list_init_with_allocator(list, NULL); \
344} \
345\
346int X##_ptr_list_init_with_allocator(X##_ptr_list *list, const kest_allocator *alloc) \
347{ \
348 if (!list) return ERR_NULL_PTR; \
349\
350 list->entries = NULL; \
351 list->count = 0; \
352 list->capacity = 0; \
353 list->alloc = alloc ? *alloc : (kest_allocator){0}; \
354\
355 return NO_ERROR; \
356} \
357\
358int X##_ptr_list_reserve(X##_ptr_list *list, size_t n) \
359{ \
360 if (!list) return ERR_NULL_PTR; \
361 if (!n) return NO_ERROR; \
362\
363 if (list->count + n <= list->capacity) \
364 return NO_ERROR; \
365\
366 size_t cap_needed = list->count + n - 1; \
367 cap_needed |= cap_needed >> 1; \
368 cap_needed |= cap_needed >> 2; \
369 cap_needed |= cap_needed >> 4; \
370 cap_needed |= cap_needed >> 8; \
371 cap_needed |= cap_needed >> 16; \
372 if (sizeof(size_t) > 4) cap_needed |= cap_needed >> 32; \
373 cap_needed += 1; \
374\
375 if (!list->entries) \
376 { \
377 list->entries = kest_allocator_alloc(&list->alloc, sizeof(X*) * cap_needed); \
378 if (!list->entries) return ERR_ALLOC_FAIL; \
379 memset(list->entries, 0, sizeof(X*) * cap_needed); \
380 } \
381 else \
382 { \
383 X **new_array = kest_allocator_realloc(&list->alloc, list->entries, sizeof(X*) * cap_needed); \
384 if (!new_array) return ERR_ALLOC_FAIL; \
385\
386 list->entries = new_array; \
387 memset(&list->entries[list->count], 0, sizeof(X*) * (cap_needed - list->count)); \
388 } \
389\
390 list->capacity = cap_needed; \
391 return NO_ERROR; \
392} \
393\
394int X##_ptr_list_append(X##_ptr_list *list, X *x) \
395{ \
396 if (!list) return ERR_NULL_PTR; \
397\
398 int r = X##_ptr_list_reserve(list, 1); \
399 if (r != NO_ERROR) return r; \
400\
401 list->entries[list->count++] = x; \
402 return NO_ERROR; \
403} \
404\
405int X##_ptr_list_destroy(X##_ptr_list *list) \
406{ \
407 if (!list) return ERR_NULL_PTR; \
408\
409 if (list->entries) \
410 kest_allocator_free(&list->alloc, list->entries); \
411\
412 list->entries = NULL; \
413 list->count = 0; \
414 list->capacity = 0; \
415\
416 return NO_ERROR; \
417} \
418\
419int X##_ptr_list_destroy_all(X##_ptr_list *list, void (*destructor)(X *x)) \
420{ \
421 if (!list) return ERR_NULL_PTR; \
422\
423 if (!list->entries) \
424 { \
425 list->count = 0; \
426 list->capacity = 0; \
427 return NO_ERROR; \
428 } \
429\
430 if (destructor) \
431 { \
432 for (int i = 0; i < list->count; i++) \
433 if (list->entries[i]) destructor(list->entries[i]); \
434 } \
435 else \
436 { \
437 for (int i = 0; i < list->count; i++) \
438 if (list->entries[i]) kest_allocator_free(&list->alloc, list->entries[i]); \
439 } \
440\
441 kest_allocator_free(&list->alloc, list->entries); \
442\
443 list->entries = NULL; \
444 list->count = 0; \
445 list->capacity = 0; \
446\
447 return NO_ERROR; \
448} \
449\
450int X##_ptr_list_contains(X##_ptr_list *list, X *x) \
451{ \
452 if (!list || !list->entries) return 0; \
453\
454 for (int i = 0; i < list->count; i++) \
455 if (list->entries[i] == x) return 1; \
456\
457 return 0; \
458} \
459\
460int X##_ptr_list_index_of(X##_ptr_list *list, X *x) \
461{ \
462 if (!list || !list->entries) return -1; \
463\
464 for (int i = 0; i < list->count; i++) \
465 if (list->entries[i] == x) return i; \
466\
467 return -1; \
468}\
469X **X##_ptr_list_head(X##_ptr_list *list)\
470{\
471 if (!list)\
472 return NULL;\
473 \
474 if (!list->entries)\
475 return NULL;\
476 \
477 if (list->count < 1) return NULL;\
478 \
479 return &list->entries[0];\
480}\
481X **X##_ptr_list_tail(X##_ptr_list *list)\
482{\
483 if (!list)\
484 return NULL;\
485 \
486 if (!list->entries)\
487 return NULL;\
488 \
489 if (list->count < 1 || list->capacity < list->count) return NULL;\
490 \
491 return &list->entries[list->count - 1];\
492}\
493\
494int X##_ptr_list_pop_destroy_tail(X##_ptr_list *list, void (*destructor)(X *x))\
495{\
496 if (!list)\
497 return ERR_NULL_PTR;\
498 \
499 if (list->count > 0)\
500 {\
501 list->count--;\
502 destructor(list->entries[list->count]);\
503 }\
504 \
505 return NO_ERROR;\
506}\
507\
508int X##_ptr_list_pop_tail(X##_ptr_list *list)\
509{\
510 if (!list)\
511 return ERR_NULL_PTR;\
512 \
513 if (list->count > 0)\
514 list->count--;\
515 \
516 return NO_ERROR;\
517}\
518\
519int X##_ptr_list_append_list(X##_ptr_list *list, X##_ptr_list *a)\
520{\
521 if (!list || !a)\
522 return ERR_NULL_PTR;\
523 \
524 \
525 if (a->count == 0)\
526 return NO_ERROR;\
527 \
528 if (!a->entries)\
529 return ERR_BAD_ARGS;\
530 \
531 X##_ptr_list_reserve(list, a->count);\
532 \
533 memcpy(&list->entries[list->count], a->entries, sizeof(X*) * a->count);\
534 \
535 list->count += a->count;\
536 \
537 return NO_ERROR;\
538}\
539\
540int X##_ptr_list_drain_destroy(X##_ptr_list *list, void (*destructor)(X *x))\
541{\
542 if (!list)\
543 return ERR_NULL_PTR;\
544 \
545 \
546 for (int i = 0; i < list->count; i++)\
547 {\
548 if (destructor && list->entries[i])\
549 destructor(list->entries[i]);\
550 }\
551 list->count = 0;\
552 \
553 return NO_ERROR;\
554}\
555\
556int X##_ptr_list_drain(X##_ptr_list *list)\
557{\
558 if (!list)\
559 return ERR_NULL_PTR;\
560 \
561 list->count = 0;\
562 \
563 return NO_ERROR;\
564}
565
566#endif