Graphviz 13.0.0~dev.20250121.0651
Loading...
Searching...
No Matches
list.h
Go to the documentation of this file.
1
3#pragma once
4
5#include <assert.h>
6#include <errno.h>
7#include <stdbool.h>
8#include <stdint.h>
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12#include <util/alloc.h>
13#include <util/exit.h>
14#include <util/unused.h>
15
21#define DEFINE_LIST(name, type) DEFINE_LIST_WITH_DTOR(name, type, name##_noop_)
22
29#define DEFINE_LIST_WITH_DTOR(name, type, dtor) \
30 \
31 \
36 typedef struct { \
37 type *base; /* start of the allocation for backing memory */ \
38 /* (base == NULL && capacity == 0) || (base != NULL && capacity > 0) */ \
39 size_t head; /* index of the first element */ \
40 /* (capacity == 0 && head == 0) || (capacity > 0 && head < capacity) */ \
41 size_t size; /* number of elements in the list */ \
42 /* size <= capacity */ \
43 size_t capacity; /* available storage slots */ \
44 } name##_t; \
45 \
46 /* default “do nothing” destructor */ \
47 static inline UNUSED void name##_noop_(type item) { (void)item; } \
48 \
49 \
50 static inline size_t name##_size(const name##_t *list) { \
51 assert(list != NULL); \
52 return list->size; \
53 } \
54 \
55 \
56 static inline UNUSED bool name##_is_empty(const name##_t *list) { \
57 assert(list != NULL); \
58 return name##_size(list) == 0; \
59 } \
60 \
61 static inline int name##_try_append(name##_t *list, type item) { \
62 assert(list != NULL); \
63 \
64 /* do we need to expand the backing storage? */ \
65 if (list->size == list->capacity) { \
66 const size_t c = list->capacity == 0 ? 1 : (list->capacity * 2); \
67 \
68 /* will the calculation of the new size overflow? */ \
69 if (SIZE_MAX / c < sizeof(type)) { \
70 return ERANGE; \
71 } \
72 \
73 type *base = (type *)realloc(list->base, c * sizeof(type)); \
74 if (base == NULL) { \
75 return ENOMEM; \
76 } \
77 \
78 /* zero the new memory */ \
79 memset((char *)base + list->capacity * sizeof(type), 0, \
80 (c - list->capacity) * sizeof(type)); \
81 \
82 /* Do we need to shuffle the prefix upwards? E.g. */ \
83 /* */ \
84 /* ┌───┬───┬───┬───┐ */ \
85 /* old: │ 3 │ 4 │ 1 │ 2 │ */ \
86 /* └───┴───┴─┼─┴─┼─┘ */ \
87 /* │ └───────────────┐ */ \
88 /* └───────────────┐ │ */ \
89 /* ▼ ▼ */ \
90 /* ┌───┬───┬───┬───┬───┬───┬───┬───┐ */ \
91 /* new: │ 3 │ 4 │ │ │ │ │ 1 │ 2 │ */ \
92 /* └───┴───┴───┴───┴───┴───┴───┴───┘ */ \
93 if (list->head + list->size > list->capacity) { \
94 const size_t prefix = list->capacity - list->head; \
95 const size_t new_head = c - prefix; \
96 memmove(&base[new_head], &base[list->head], prefix * sizeof(type)); \
97 list->head = new_head; \
98 } \
99 \
100 list->base = base; \
101 list->capacity = c; \
102 } \
103 \
104 list->base[(list->head + list->size) % list->capacity] = item; \
105 ++list->size; \
106 \
107 return 0; \
108 } \
109 \
110 static inline void name##_append(name##_t *list, type item) { \
111 int rc = name##_try_append(list, item); \
112 if (rc != 0) { \
113 fprintf(stderr, "realloc failed: %s\n", strerror(rc)); \
114 graphviz_exit(EXIT_FAILURE); \
115 } \
116 } \
117 \
118 \
124 static inline type name##_get(const name##_t *list, size_t index) { \
125 assert(list != NULL); \
126 assert(index < list->size && "index out of bounds"); \
127 return list->base[(list->head + index) % list->capacity]; \
128 } \
129 \
130 \
142 static inline type *name##_at(name##_t *list, size_t index) { \
143 assert(list != NULL); \
144 assert(index < list->size && "index out of bounds"); \
145 return &list->base[(list->head + index) % list->capacity]; \
146 } \
147 \
148 \
149 static inline UNUSED type *name##_front(name##_t *list) { \
150 assert(list != NULL); \
151 assert(!name##_is_empty(list)); \
152 return name##_at(list, 0); \
153 } \
154 \
155 \
156 static inline UNUSED type *name##_back(name##_t *list) { \
157 assert(list != NULL); \
158 assert(!name##_is_empty(list)); \
159 return name##_at(list, name##_size(list) - 1); \
160 } \
161 \
162 \
168 static inline void name##_set(name##_t *list, size_t index, type item) { \
169 assert(list != NULL); \
170 assert(index < name##_size(list) && "index out of bounds"); \
171 type *target = name##_at(list, index); \
172 dtor(*target); \
173 *target = item; \
174 } \
175 \
176 \
181 static inline UNUSED void name##_remove(name##_t *list, const type item) { \
182 assert(list != NULL); \
183 \
184 for (size_t i = 0; i < list->size; ++i) { \
185 /* is this the element we are looking for? */ \
186 type *candidate = name##_at(list, i); \
187 if (memcmp(candidate, &item, sizeof(type)) == 0) { \
188 \
189 /* destroy the element we are about to remove */ \
190 dtor(*candidate); \
191 \
192 /* shrink the list */ \
193 for (size_t j = i + 1; j < list->size; ++j) { \
194 type *replacement = name##_at(list, j); \
195 *candidate = *replacement; \
196 candidate = replacement; \
197 } \
198 --list->size; \
199 return; \
200 } \
201 } \
202 } \
203 \
204 \
205 static inline void name##_clear(name##_t *list) { \
206 assert(list != NULL); \
207 \
208 for (size_t i = 0; i < list->size; ++i) { \
209 dtor(name##_get(list, i)); \
210 } \
211 \
212 list->size = 0; \
213 \
214 /* opportunistically re-sync the list */ \
215 list->head = 0; \
216 } \
217 \
218 \
223 static inline UNUSED void name##_reserve(name##_t *list, size_t capacity) { \
224 assert(list != NULL); \
225 \
226 /* if we can already fit enough items, nothing to do */ \
227 if (list->capacity >= capacity) { \
228 return; \
229 } \
230 \
231 list->base = (type *)gv_recalloc(list->base, list->capacity, capacity, \
232 sizeof(type)); \
233 \
234 /* Do we need to shuffle the prefix upwards? E.g. */ \
235 /* */ \
236 /* ┌───┬───┬───┬───┐ */ \
237 /* old: │ 3 │ 4 │ 1 │ 2 │ */ \
238 /* └───┴───┴─┼─┴─┼─┘ */ \
239 /* │ └───────────────┐ */ \
240 /* └───────────────┐ │ */ \
241 /* ▼ ▼ */ \
242 /* ┌───┬───┬───┬───┬───┬───┬───┬───┐ */ \
243 /* new: │ 3 │ 4 │ │ │ │ │ 1 │ 2 │ */ \
244 /* └───┴───┴───┴───┴───┴───┴───┴───┘ */ \
245 if (list->head + list->size > list->capacity) { \
246 const size_t prefix = list->capacity - list->head; \
247 const size_t new_head = capacity - prefix; \
248 memmove(&list->base[new_head], &list->base[list->head], \
249 prefix * sizeof(type)); \
250 list->head = new_head; \
251 } \
252 \
253 list->capacity = capacity; \
254 } \
255 \
256 \
262 static inline UNUSED void name##_resize(name##_t *list, size_t size, \
263 type value) { \
264 assert(list != NULL); \
265 \
266 if (list->size < size) { \
267 /* we are expanding the list */ \
268 while (list->size < size) { \
269 name##_append(list, value); \
270 } \
271 } else if (list->size > size) { \
272 /* we are shrinking the list */ \
273 while (list->size > size) { \
274 dtor(name##_get(list, list->size - 1)); \
275 --list->size; \
276 } \
277 } \
278 } \
279 \
280 \
281 static inline UNUSED bool name##_contains( \
282 const name##_t *haystack, const type needle, \
283 bool (*eq)(const type a, const type b)) { \
284 assert(haystack != NULL); \
285 assert(eq != NULL); \
286 \
287 for (size_t i = 0; i < name##_size(haystack); ++i) { \
288 if (eq(name##_get(haystack, i), needle)) { \
289 return true; \
290 } \
291 } \
292 return false; \
293 } \
294 \
295 \
296 static inline UNUSED name##_t name##_copy(const name##_t *source) { \
297 assert(source != NULL); \
298 \
299 name##_t destination = {(type *)gv_calloc(source->capacity, sizeof(type)), \
300 0, 0, source->capacity}; \
301 for (size_t i = 0; i < source->size; ++i) { \
302 name##_append(&destination, name##_get(source, i)); \
303 } \
304 return destination; \
305 } \
306 \
307 \
308 \
309 \
310 \
311 \
312 \
313 \
314 \
315 \
316 \
317 \
318 \
319 \
320 \
321 static inline UNUSED bool name##_is_contiguous(const name##_t *list) { \
322 assert(list != NULL); \
323 return list->head + list->size <= list->capacity; \
324 } \
325 \
326 \
327 static inline void name##_sync(name##_t *list) { \
328 assert(list != NULL); \
329 \
330 /* Shuffle the list 1-1 until it is aligned. This is not efficient, but */ \
331 /* we assume this is a relatively rare operation. */ \
332 while (list->head != 0) { \
333 /* rotate the list leftwards by 1 */ \
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; \
340 } \
341 --list->head; \
342 } \
343 \
344 /* synchronization should have ensured the list no longer wraps */ \
345 assert(name##_is_contiguous(list)); \
346 } \
347 \
348 \
349 static inline UNUSED void name##_sort( \
350 name##_t *list, int (*cmp)(const type *a, const type *b)) { \
351 assert(list != NULL); \
352 assert(cmp != NULL); \
353 \
354 name##_sync(list); \
355 \
356 int (*compar)(const void *, const void *) = \
357 (int (*)(const void *, const void *))cmp; \
358 if (list->size > 0) { \
359 qsort(list->base, list->size, sizeof(type), compar); \
360 } \
361 } \
362 \
363 \
364 static inline UNUSED void name##_reverse(name##_t *list) { \
365 assert(list != NULL); \
366 \
367 for (size_t i = 0; i < name##_size(list) / 2; ++i) { \
368 type const temp1 = name##_get(list, i); \
369 type const temp2 = name##_get(list, name##_size(list) - i - 1); \
370 name##_set(list, i, temp2); \
371 name##_set(list, name##_size(list) - i - 1, temp1); \
372 } \
373 } \
374 \
375 \
376 static inline UNUSED void name##_shrink_to_fit(name##_t *list) { \
377 assert(list != NULL); \
378 \
379 name##_sync(list); \
380 \
381 if (list->capacity > list->size) { \
382 list->base = (type *)gv_recalloc(list->base, list->capacity, list->size, \
383 sizeof(type)); \
384 list->capacity = list->size; \
385 } \
386 } \
387 \
388 \
389 static inline UNUSED void name##_free(name##_t *list) { \
390 assert(list != NULL); \
391 name##_clear(list); \
392 free(list->base); \
393 memset(list, 0, sizeof(*list)); \
394 } \
395 \
396 \
397 static inline UNUSED void name##_push_back(name##_t *list, type value) { \
398 name##_append(list, value); \
399 } \
400 \
401 \
402 static inline UNUSED type name##_pop_front(name##_t *list) { \
403 assert(list != NULL); \
404 assert(list->size > 0); \
405 \
406 type value = name##_get(list, 0); \
407 \
408 /* do not call `dtor` because we are transferring ownership of the removed \
409 * element to the caller \
410 */ \
411 list->head = (list->head + 1) % list->capacity; \
412 --list->size; \
413 \
414 return value; \
415 } \
416 \
417 \
418 static inline UNUSED type name##_pop_back(name##_t *list) { \
419 assert(list != NULL); \
420 assert(list->size > 0); \
421 \
422 type value = name##_get(list, list->size - 1); \
423 \
424 /* do not call `dtor` because we are transferring ownership of the removed \
425 * element to the caller \
426 */ \
427 --list->size; \
428 \
429 return value; \
430 } \
431 \
432 \
442 static inline UNUSED name##_t name##_attach(type *data, size_t size) { \
443 assert(data != NULL || size == 0); \
444 name##_t list = {data, 0, size, size}; \
445 return list; \
446 } \
447 \
448 \
457 static inline UNUSED type *name##_detach(name##_t *list) { \
458 assert(list != NULL); \
459 name##_sync(list); \
460 type *data = list->base; \
461 memset(list, 0, sizeof(*list)); \
462 return data; \
463 }
alloc.h
Memory allocation wrappers that exit on failure.
unused.h
abstraction for squashing compiler warnings for unused symbols