Graphviz 13.0.0~dev.20241220.2304
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
15#ifdef __GNUC__
16#define LIST_UNUSED __attribute__((unused))
17#else
18#define LIST_UNUSED /* nothing */
19#endif
20
26#define DEFINE_LIST(name, type) DEFINE_LIST_WITH_DTOR(name, type, name##_noop_)
27
34#define DEFINE_LIST_WITH_DTOR(name, type, dtor) \
35 \
36 \
41 typedef struct { \
42 type *base; /* start of the allocation for backing memory */ \
43 /* (base == NULL && capacity == 0) || (base != NULL && capacity > 0) */ \
44 size_t head; /* index of the first element */ \
45 /* (capacity == 0 && head == 0) || (capacity > 0 && head < capacity) */ \
46 size_t size; /* number of elements in the list */ \
47 /* size <= capacity */ \
48 size_t capacity; /* available storage slots */ \
49 } name##_t; \
50 \
51 /* default “do nothing” destructor */ \
52 static inline LIST_UNUSED void name##_noop_(type item) { (void)item; } \
53 \
54 \
55 static inline LIST_UNUSED size_t name##_size(const name##_t *list) { \
56 assert(list != NULL); \
57 return list->size; \
58 } \
59 \
60 \
61 static inline LIST_UNUSED bool name##_is_empty(const name##_t *list) { \
62 assert(list != NULL); \
63 return name##_size(list) == 0; \
64 } \
65 \
66 static inline int name##_try_append(name##_t *list, type item) { \
67 assert(list != NULL); \
68 \
69 /* do we need to expand the backing storage? */ \
70 if (list->size == list->capacity) { \
71 const size_t c = list->capacity == 0 ? 1 : (list->capacity * 2); \
72 \
73 /* will the calculation of the new size overflow? */ \
74 if (SIZE_MAX / c < sizeof(type)) { \
75 return ERANGE; \
76 } \
77 \
78 type *base = (type *)realloc(list->base, c * sizeof(type)); \
79 if (base == NULL) { \
80 return ENOMEM; \
81 } \
82 \
83 /* zero the new memory */ \
84 memset((char *)base + list->capacity * sizeof(type), 0, \
85 (c - list->capacity) * sizeof(type)); \
86 \
87 /* Do we need to shuffle the prefix upwards? E.g. */ \
88 /* */ \
89 /* ┌───┬───┬───┬───┐ */ \
90 /* old: │ 3 │ 4 │ 1 │ 2 │ */ \
91 /* └───┴───┴─┼─┴─┼─┘ */ \
92 /* │ └───────────────┐ */ \
93 /* └───────────────┐ │ */ \
94 /* ▼ ▼ */ \
95 /* ┌───┬───┬───┬───┬───┬───┬───┬───┐ */ \
96 /* new: │ 3 │ 4 │ │ │ │ │ 1 │ 2 │ */ \
97 /* └───┴───┴───┴───┴───┴───┴───┴───┘ */ \
98 if (list->head + list->size > list->capacity) { \
99 const size_t prefix = list->capacity - list->head; \
100 const size_t new_head = c - prefix; \
101 memmove(&base[new_head], &base[list->head], prefix * sizeof(type)); \
102 list->head = new_head; \
103 } \
104 \
105 list->base = base; \
106 list->capacity = c; \
107 } \
108 \
109 list->base[(list->head + list->size) % list->capacity] = item; \
110 ++list->size; \
111 \
112 return 0; \
113 } \
114 \
115 static inline void name##_append(name##_t *list, type item) { \
116 int rc = name##_try_append(list, item); \
117 if (rc != 0) { \
118 fprintf(stderr, "realloc failed: %s\n", strerror(rc)); \
119 graphviz_exit(EXIT_FAILURE); \
120 } \
121 } \
122 \
123 \
129 static inline type name##_get(const name##_t *list, size_t index) { \
130 assert(list != NULL); \
131 assert(index < list->size && "index out of bounds"); \
132 return list->base[(list->head + index) % list->capacity]; \
133 } \
134 \
135 \
147 static inline type *name##_at(name##_t *list, size_t index) { \
148 assert(list != NULL); \
149 assert(index < list->size && "index out of bounds"); \
150 return &list->base[(list->head + index) % list->capacity]; \
151 } \
152 \
153 \
154 static inline LIST_UNUSED type *name##_front(name##_t *list) { \
155 assert(list != NULL); \
156 assert(!name##_is_empty(list)); \
157 return name##_at(list, 0); \
158 } \
159 \
160 \
161 static inline LIST_UNUSED type *name##_back(name##_t *list) { \
162 assert(list != NULL); \
163 assert(!name##_is_empty(list)); \
164 return name##_at(list, name##_size(list) - 1); \
165 } \
166 \
167 \
173 static inline void name##_set(name##_t *list, size_t index, type item) { \
174 assert(list != NULL); \
175 assert(index < name##_size(list) && "index out of bounds"); \
176 type *target = name##_at(list, index); \
177 dtor(*target); \
178 *target = item; \
179 } \
180 \
181 \
186 static inline LIST_UNUSED void name##_remove(name##_t *list, \
187 const type item) { \
188 assert(list != NULL); \
189 \
190 for (size_t i = 0; i < list->size; ++i) { \
191 /* is this the element we are looking for? */ \
192 type *candidate = name##_at(list, i); \
193 if (memcmp(candidate, &item, sizeof(type)) == 0) { \
194 \
195 /* destroy the element we are about to remove */ \
196 dtor(*candidate); \
197 \
198 /* shrink the list */ \
199 for (size_t j = i + 1; j < list->size; ++j) { \
200 type *replacement = name##_at(list, j); \
201 *candidate = *replacement; \
202 candidate = replacement; \
203 } \
204 --list->size; \
205 return; \
206 } \
207 } \
208 } \
209 \
210 \
211 static inline LIST_UNUSED void name##_clear(name##_t *list) { \
212 assert(list != NULL); \
213 \
214 for (size_t i = 0; i < list->size; ++i) { \
215 dtor(name##_get(list, i)); \
216 } \
217 \
218 list->size = 0; \
219 \
220 /* opportunistically re-sync the list */ \
221 list->head = 0; \
222 } \
223 \
224 \
229 static inline LIST_UNUSED void name##_reserve(name##_t *list, \
230 size_t capacity) { \
231 assert(list != NULL); \
232 \
233 /* if we can already fit enough items, nothing to do */ \
234 if (list->capacity >= capacity) { \
235 return; \
236 } \
237 \
238 list->base = (type *)gv_recalloc(list->base, list->capacity, capacity, \
239 sizeof(type)); \
240 \
241 /* Do we need to shuffle the prefix upwards? E.g. */ \
242 /* */ \
243 /* ┌───┬───┬───┬───┐ */ \
244 /* old: │ 3 │ 4 │ 1 │ 2 │ */ \
245 /* └───┴───┴─┼─┴─┼─┘ */ \
246 /* │ └───────────────┐ */ \
247 /* └───────────────┐ │ */ \
248 /* ▼ ▼ */ \
249 /* ┌───┬───┬───┬───┬───┬───┬───┬───┐ */ \
250 /* new: │ 3 │ 4 │ │ │ │ │ 1 │ 2 │ */ \
251 /* └───┴───┴───┴───┴───┴───┴───┴───┘ */ \
252 if (list->head + list->size > list->capacity) { \
253 const size_t prefix = list->capacity - list->head; \
254 const size_t new_head = capacity - prefix; \
255 memmove(&list->base[new_head], &list->base[list->head], \
256 prefix * sizeof(type)); \
257 list->head = new_head; \
258 } \
259 \
260 list->capacity = capacity; \
261 } \
262 \
263 \
269 static inline LIST_UNUSED void name##_resize(name##_t *list, size_t size, \
270 type value) { \
271 assert(list != NULL); \
272 \
273 if (list->size < size) { \
274 /* we are expanding the list */ \
275 while (list->size < size) { \
276 name##_append(list, value); \
277 } \
278 } else if (list->size > size) { \
279 /* we are shrinking the list */ \
280 while (list->size > size) { \
281 dtor(name##_get(list, list->size - 1)); \
282 --list->size; \
283 } \
284 } \
285 } \
286 \
287 \
288 static inline LIST_UNUSED bool name##_contains( \
289 const name##_t *haystack, const type needle, \
290 bool (*eq)(const type a, const type b)) { \
291 assert(haystack != NULL); \
292 assert(eq != NULL); \
293 \
294 for (size_t i = 0; i < name##_size(haystack); ++i) { \
295 if (eq(name##_get(haystack, i), needle)) { \
296 return true; \
297 } \
298 } \
299 return false; \
300 } \
301 \
302 \
303 static inline LIST_UNUSED name##_t name##_copy(const name##_t *source) { \
304 assert(source != NULL); \
305 \
306 name##_t destination = {(type *)gv_calloc(source->capacity, sizeof(type)), \
307 0, 0, source->capacity}; \
308 for (size_t i = 0; i < source->size; ++i) { \
309 name##_append(&destination, name##_get(source, i)); \
310 } \
311 return destination; \
312 } \
313 \
314 \
315 \
316 \
317 \
318 \
319 \
320 \
321 \
322 \
323 \
324 \
325 \
326 \
327 \
328 static inline LIST_UNUSED bool name##_is_contiguous(const name##_t *list) { \
329 assert(list != NULL); \
330 return list->head + list->size <= list->capacity; \
331 } \
332 \
333 \
334 static inline void name##_sync(name##_t *list) { \
335 assert(list != NULL); \
336 \
337 /* Shuffle the list 1-1 until it is aligned. This is not efficient, but */ \
338 /* we assume this is a relatively rare operation. */ \
339 while (list->head != 0) { \
340 /* rotate the list leftwards by 1 */ \
341 assert(list->capacity > 0); \
342 type replacement = list->base[0]; \
343 for (size_t i = list->capacity - 1; i != SIZE_MAX; --i) { \
344 type temp = list->base[i]; \
345 list->base[i] = replacement; \
346 replacement = temp; \
347 } \
348 --list->head; \
349 } \
350 \
351 /* synchronization should have ensured the list no longer wraps */ \
352 assert(name##_is_contiguous(list)); \
353 } \
354 \
355 \
356 static inline LIST_UNUSED void name##_sort( \
357 name##_t *list, int (*cmp)(const type *a, const type *b)) { \
358 assert(list != NULL); \
359 assert(cmp != NULL); \
360 \
361 name##_sync(list); \
362 \
363 int (*compar)(const void *, const void *) = \
364 (int (*)(const void *, const void *))cmp; \
365 if (list->size > 0) { \
366 qsort(list->base, list->size, sizeof(type), compar); \
367 } \
368 } \
369 \
370 \
371 static inline LIST_UNUSED void name##_reverse(name##_t *list) { \
372 assert(list != NULL); \
373 \
374 for (size_t i = 0; i < name##_size(list) / 2; ++i) { \
375 type const temp1 = name##_get(list, i); \
376 type const temp2 = name##_get(list, name##_size(list) - i - 1); \
377 name##_set(list, i, temp2); \
378 name##_set(list, name##_size(list) - i - 1, temp1); \
379 } \
380 } \
381 \
382 \
383 static inline LIST_UNUSED void name##_shrink_to_fit(name##_t *list) { \
384 assert(list != NULL); \
385 \
386 name##_sync(list); \
387 \
388 if (list->capacity > list->size) { \
389 list->base = (type *)gv_recalloc(list->base, list->capacity, list->size, \
390 sizeof(type)); \
391 list->capacity = list->size; \
392 } \
393 } \
394 \
395 \
396 static inline LIST_UNUSED void name##_free(name##_t *list) { \
397 assert(list != NULL); \
398 name##_clear(list); \
399 free(list->base); \
400 memset(list, 0, sizeof(*list)); \
401 } \
402 \
403 \
404 static inline LIST_UNUSED void name##_push_back(name##_t *list, \
405 type value) { \
406 name##_append(list, value); \
407 } \
408 \
409 \
410 static inline LIST_UNUSED type name##_pop_front(name##_t *list) { \
411 assert(list != NULL); \
412 assert(list->size > 0); \
413 \
414 type value = name##_get(list, 0); \
415 \
416 /* do not call `dtor` because we are transferring ownership of the removed \
417 * element to the caller \
418 */ \
419 list->head = (list->head + 1) % list->capacity; \
420 --list->size; \
421 \
422 return value; \
423 } \
424 \
425 \
426 static inline LIST_UNUSED type name##_pop_back(name##_t *list) { \
427 assert(list != NULL); \
428 assert(list->size > 0); \
429 \
430 type value = name##_get(list, list->size - 1); \
431 \
432 /* do not call `dtor` because we are transferring ownership of the removed \
433 * element to the caller \
434 */ \
435 --list->size; \
436 \
437 return value; \
438 } \
439 \
440 \
450 static inline LIST_UNUSED name##_t name##_attach(type *data, size_t size) { \
451 assert(data != NULL || size == 0); \
452 name##_t list = {data, 0, size, size}; \
453 return list; \
454 } \
455 \
456 \
465 static inline LIST_UNUSED type *name##_detach(name##_t *list) { \
466 assert(list != NULL); \
467 name##_sync(list); \
468 type *data = list->base; \
469 memset(list, 0, sizeof(*list)); \
470 return data; \
471 }
alloc.h
Memory allocation wrappers that exit on failure.