22#define DEFINE_LIST(name, type) DEFINE_LIST_WITH_DTOR(name, type, name##_noop_)
30#define DEFINE_LIST_WITH_DTOR(name, type, dtor) \
48 static inline UNUSED void name##_noop_(type item) { (void)item; } \
51 static inline size_t name##_size(const name##_t *list) { \
52 assert(list != NULL); \
57 static inline UNUSED bool name##_is_empty(const name##_t *list) { \
58 assert(list != NULL); \
59 return name##_size(list) == 0; \
62 static inline int name##_try_append(name##_t *list, type item) { \
63 assert(list != NULL); \
66 if (list->size == list->capacity) { \
67 const size_t c = list->capacity == 0 ? 1 : (list->capacity * 2); \
70 if (SIZE_MAX / c < sizeof(type)) { \
74 type *base = (type *)realloc(list->base, c * sizeof(type)); \
80 memset(&base[list->capacity], 0, (c - list->capacity) * sizeof(type)); \
83 ASAN_POISON(&base[list->capacity], (c - list->capacity) * sizeof(type)); \
97 if (list->head + list->size > list->capacity) { \
98 const size_t prefix = list->capacity - list->head; \
99 const size_t new_head = c - prefix; \
101 ASAN_UNPOISON(&base[new_head], prefix * sizeof(type)); \
102 memmove(&base[new_head], &base[list->head], prefix * sizeof(type)); \
104 ASAN_POISON(&base[list->size - prefix], \
105 (list->capacity - list->size) * sizeof(type)); \
106 list->head = new_head; \
110 list->capacity = c; \
113 const size_t new_slot = (list->head + list->size) % list->capacity; \
114 ASAN_UNPOISON(&list->base[new_slot], sizeof(type)); \
115 list->base[new_slot] = item; \
121 static inline void name##_append(name##_t *list, type item) { \
122 int rc = name##_try_append(list, item); \
124 fprintf(stderr, "realloc failed: %s\n", strerror(rc)); \
125 graphviz_exit(EXIT_FAILURE); \
135 static inline type name##_get(const name##_t *list, size_t index) { \
136 assert(list != NULL); \
137 assert(index < list->size && "index out of bounds"); \
138 return list->base[(list->head + index) % list->capacity]; \
153 static inline type *name##_at(name##_t *list, size_t index) { \
154 assert(list != NULL); \
155 assert(index < list->size && "index out of bounds"); \
156 return &list->base[(list->head + index) % list->capacity]; \
160 static inline UNUSED type *name##_front(name##_t *list) { \
161 assert(list != NULL); \
162 assert(!name##_is_empty(list)); \
163 return name##_at(list, 0); \
167 static inline UNUSED type *name##_back(name##_t *list) { \
168 assert(list != NULL); \
169 assert(!name##_is_empty(list)); \
170 return name##_at(list, name##_size(list) - 1); \
179 static inline void name##_set(name##_t *list, size_t index, type item) { \
180 assert(list != NULL); \
181 assert(index < name##_size(list) && "index out of bounds"); \
182 type *target = name##_at(list, index); \
192 static inline UNUSED void name##_remove(name##_t *list, const type item) { \
193 assert(list != NULL); \
195 for (size_t i = 0; i < list->size; ++i) { \
197 type *candidate = name##_at(list, i); \
198 if (memcmp(candidate, &item, sizeof(type)) == 0) { \
204 for (size_t j = i + 1; j < list->size; ++j) { \
205 type *replacement = name##_at(list, j); \
206 *candidate = *replacement; \
207 candidate = replacement; \
209 ASAN_POISON(name##_at(list, list->size - 1), sizeof(type)); \
217 static inline void name##_clear(name##_t *list) { \
218 assert(list != NULL); \
220 for (size_t i = 0; i < list->size; ++i) { \
221 dtor(name##_get(list, i)); \
222 ASAN_POISON(name##_at(list, i), sizeof(type)); \
236 static inline UNUSED void name##_reserve(name##_t *list, size_t capacity) { \
237 assert(list != NULL); \
240 if (list->capacity >= capacity) { \
244 list->base = (type *)gv_recalloc(list->base, list->capacity, capacity, \
259 if (list->head + list->size > list->capacity) { \
260 const size_t prefix = list->capacity - list->head; \
261 const size_t new_head = capacity - prefix; \
263 ASAN_UNPOISON(&list->base[new_head], prefix * sizeof(type)); \
264 memmove(&list->base[new_head], &list->base[list->head], \
265 prefix * sizeof(type)); \
267 ASAN_POISON(&list->base[list->size - prefix], \
268 (list->capacity - list->size) * sizeof(type)); \
269 list->head = new_head; \
272 list->capacity = capacity; \
276 static inline UNUSED bool name##_contains( \
277 const name##_t *haystack, const type needle, \
278 bool (*eq)(const type a, const type b)) { \
279 assert(haystack != NULL); \
280 assert(eq != NULL); \
282 for (size_t i = 0; i < name##_size(haystack); ++i) { \
283 if (eq(name##_get(haystack, i), needle)) { \
291 static inline UNUSED name##_t name##_copy(const name##_t *source) { \
292 assert(source != NULL); \
294 name##_t destination = {(type *)gv_calloc(source->capacity, sizeof(type)), \
295 0, 0, source->capacity}; \
296 for (size_t i = 0; i < source->size; ++i) { \
297 name##_append(&destination, name##_get(source, i)); \
299 return destination; \
316 static inline UNUSED bool name##_is_contiguous(const name##_t *list) { \
317 assert(list != NULL); \
318 return list->head + list->size <= list->capacity; \
322 static inline void name##_sync(name##_t *list) { \
323 assert(list != NULL); \
328 ASAN_UNPOISON(list->base, list->capacity * sizeof(type)); \
332 while (list->head != 0) { \
334 assert(list->capacity > 0); \
335 type replacement = list->base[0]; \
336 for (size_t i = list->capacity - 1; i != SIZE_MAX; --i) { \
337 type temp = list->base[i]; \
338 list->base[i] = replacement; \
339 replacement = temp; \
345 assert(name##_is_contiguous(list)); \
348 ASAN_POISON(&list->base[list->size], \
349 (list->capacity - list->size) * sizeof(type)); \
353 static inline UNUSED void name##_sort( \
354 name##_t *list, int (*cmp)(const type *a, const type *b)) { \
355 assert(list != NULL); \
356 assert(cmp != NULL); \
360 int (*compar)(const void *, const void *) = \
361 (int (*)(const void *, const void *))cmp; \
362 if (list->size > 0) { \
363 qsort(list->base, list->size, sizeof(type), compar); \
368 static inline UNUSED void name##_reverse(name##_t *list) { \
369 assert(list != NULL); \
371 for (size_t i = 0; i < name##_size(list) / 2; ++i) { \
372 type const temp1 = name##_get(list, i); \
373 type const temp2 = name##_get(list, name##_size(list) - i - 1); \
374 name##_set(list, i, temp2); \
375 name##_set(list, name##_size(list) - i - 1, temp1); \
380 static inline UNUSED void name##_shrink_to_fit(name##_t *list) { \
381 assert(list != NULL); \
385 if (list->capacity > list->size) { \
386 list->base = (type *)gv_recalloc(list->base, list->capacity, list->size, \
388 list->capacity = list->size; \
393 static inline UNUSED void name##_free(name##_t *list) { \
394 assert(list != NULL); \
395 name##_clear(list); \
397 memset(list, 0, sizeof(*list)); \
401 static inline UNUSED void name##_push_back(name##_t *list, type value) { \
402 name##_append(list, value); \
406 static inline UNUSED type name##_pop_front(name##_t *list) { \
407 assert(list != NULL); \
408 assert(list->size > 0); \
410 type value = name##_get(list, 0); \
415 ASAN_POISON(name##_at(list, 0), sizeof(type)); \
416 list->head = (list->head + 1) % list->capacity; \
423 static inline UNUSED type name##_pop_back(name##_t *list) { \
424 assert(list != NULL); \
425 assert(list->size > 0); \
427 type value = name##_get(list, list->size - 1); \
432 ASAN_POISON(name##_at(list, list->size - 1), sizeof(type)); \
447 static inline UNUSED type *name##_detach(name##_t *list) { \
448 assert(list != NULL); \
450 type *data = list->base; \
451 memset(list, 0, sizeof(*list)); \
Memory allocation wrappers that exit on failure.
macros for interacting with Address Sanitizer
abstraction for squashing compiler warnings for unused symbols