Graphviz 12.0.1~dev.20240716.0800
Loading...
Searching...
No Matches
list.h
Go to the documentation of this file.
1
3#pragma once
4
5#include <assert.h>
6#include <cgraph/alloc.h>
7#include <cgraph/exit.h>
8#include <errno.h>
9#include <stdbool.h>
10#include <stdint.h>
11#include <stdio.h>
12#include <stdlib.h>
13#include <string.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, NULL)
27
34#define DEFINE_LIST_WITH_DTOR(name, type, dtor) \
35 \
36 \
41 typedef struct { \
42 type *data; /* backing storage */ \
43 size_t size; /* number of elements in the list */ \
44 size_t capacity; /* available storage slots */ \
45 } name##_t; \
46 \
47 \
48 static inline LIST_UNUSED size_t name##_size(const name##_t *list) { \
49 assert(list != NULL); \
50 return list->size; \
51 } \
52 \
53 \
54 static inline LIST_UNUSED bool name##_is_empty(const name##_t *list) { \
55 assert(list != NULL); \
56 return name##_size(list) == 0; \
57 } \
58 \
59 static inline int name##_try_append(name##_t *list, type item) { \
60 assert(list != NULL); \
61 \
62 /* do we need to expand the backing storage? */ \
63 if (list->size == list->capacity) { \
64 const size_t c = list->capacity == 0 ? 1 : (list->capacity * 2); \
65 \
66 /* will the calculation of the new size overflow? */ \
67 if (SIZE_MAX / c < sizeof(type)) { \
68 return ERANGE; \
69 } \
70 \
71 type *data = (type *)realloc(list->data, c * sizeof(type)); \
72 if (data == NULL) { \
73 return ENOMEM; \
74 } \
75 \
76 /* zero the new memory */ \
77 memset((char *)data + list->capacity * sizeof(type), 0, \
78 (c - list->capacity) * sizeof(type)); \
79 \
80 list->data = data; \
81 list->capacity = c; \
82 } \
83 \
84 list->data[list->size] = item; \
85 ++list->size; \
86 \
87 return 0; \
88 } \
89 \
90 static inline LIST_UNUSED void name##_append(name##_t *list, type item) { \
91 int rc = name##_try_append(list, item); \
92 if (rc != 0) { \
93 fprintf(stderr, "realloc failed: %s\n", strerror(rc)); \
94 graphviz_exit(EXIT_FAILURE); \
95 } \
96 } \
97 \
98 \
104 static inline LIST_UNUSED type name##_get(const name##_t *list, \
105 size_t index) { \
106 assert(list != NULL); \
107 assert(index < list->size && "index out of bounds"); \
108 return list->data[index]; \
109 } \
110 \
111 \
117 static inline LIST_UNUSED void name##_set(name##_t *list, size_t index, \
118 type item) { \
119 assert(list != NULL); \
120 assert(index < list->size && "index out of bounds"); \
121 void (*dtor_)(type) = (void (*)(type))(dtor); \
122 if (dtor_ != NULL) { \
123 dtor_(list->data[index]); \
124 } \
125 list->data[index] = item; \
126 } \
127 \
128 \
133 static inline LIST_UNUSED void name##_remove(name##_t *list, \
134 const type item) { \
135 assert(list != NULL); \
136 \
137 for (size_t i = 0; i < list->size; ++i) { \
138 /* is this the element we are looking for? */ \
139 if (memcmp(&list->data[i], &item, sizeof(type)) == 0) { \
140 \
141 /* destroy the element we are about to remove */ \
142 void (*dtor_)(type) = (void (*)(type))(dtor); \
143 if (dtor_ != NULL) { \
144 dtor_(list->data[i]); \
145 } \
146 \
147 /* shrink the list */ \
148 size_t remainder = (list->size - i - 1) * sizeof(type); \
149 memmove(&list->data[i], &list->data[i + 1], remainder); \
150 --list->size; \
151 return; \
152 } \
153 } \
154 } \
155 \
156 \
168 static inline LIST_UNUSED type *name##_at(name##_t *list, size_t index) { \
169 assert(list != NULL); \
170 assert(index < list->size && "index out of bounds"); \
171 return &list->data[index]; \
172 } \
173 \
174 \
175 static inline LIST_UNUSED void name##_clear(name##_t *list) { \
176 assert(list != NULL); \
177 \
178 void (*dtor_)(type) = (void (*)(type))(dtor); \
179 if (dtor_ != NULL) { \
180 for (size_t i = 0; i < list->size; ++i) { \
181 dtor_(list->data[i]); \
182 } \
183 } \
184 \
185 list->size = 0; \
186 } \
187 \
188 \
193 static inline LIST_UNUSED void name##_reserve(name##_t *list, \
194 size_t capacity) { \
195 assert(list != NULL); \
196 \
197 /* if we can already fit enough items, nothing to do */ \
198 if (list->capacity >= capacity) { \
199 return; \
200 } \
201 \
202 list->data = (type *)gv_recalloc(list->data, list->capacity, capacity, \
203 sizeof(type)); \
204 list->capacity = capacity; \
205 } \
206 \
207 \
213 static inline LIST_UNUSED void name##_resize(name##_t *list, size_t size, \
214 type value) { \
215 assert(list != NULL); \
216 \
217 if (list->size < size) { \
218 /* we are expanding the list */ \
219 while (list->size < size) { \
220 name##_append(list, value); \
221 } \
222 } else if (list->size > size) { \
223 /* we are shrinking the list */ \
224 while (list->size > size) { \
225 void (*dtor_)(type) = (void (*)(type))(dtor); \
226 if (dtor_ != NULL) { \
227 dtor_(list->data[list->size - 1]); \
228 } \
229 --list->size; \
230 } \
231 } \
232 } \
233 \
234 \
235 static inline LIST_UNUSED bool name##_contains( \
236 const name##_t *haystack, const type needle, \
237 bool (*eq)(const type a, const type b)) { \
238 assert(haystack != NULL); \
239 assert(eq != NULL); \
240 \
241 for (size_t i = 0; i < haystack->size; ++i) { \
242 if (eq(haystack->data[i], needle)) { \
243 return true; \
244 } \
245 } \
246 return false; \
247 } \
248 \
249 \
250 static inline LIST_UNUSED name##_t name##_copy(const name##_t *source) { \
251 assert(source != NULL); \
252 \
253 name##_t destination = {(type *)gv_calloc(source->capacity, sizeof(type)), \
254 source->size, source->capacity}; \
255 memcpy(destination.data, source->data, source->size * sizeof(type)); \
256 return destination; \
257 } \
258 \
259 \
260 static inline LIST_UNUSED void name##_sort( \
261 name##_t *list, int (*cmp)(const type *a, const type *b)) { \
262 assert(list != NULL); \
263 assert(cmp != NULL); \
264 \
265 int (*compar)(const void *, const void *) = \
266 (int (*)(const void *, const void *))cmp; \
267 if (list->size > 0) { \
268 qsort(list->data, list->size, sizeof(type), compar); \
269 } \
270 } \
271 \
272 \
273 static inline LIST_UNUSED void name##_reverse(name##_t *list) { \
274 assert(list != NULL); \
275 \
276 if (list->size == 0) { \
277 return; \
278 } \
279 \
280 size_t left = 0; \
281 size_t right = list->size - 1; \
282 while (left < right) { \
283 type temp = list->data[left]; \
284 list->data[left] = list->data[right]; \
285 list->data[right] = temp; \
286 ++left; \
287 --right; \
288 } \
289 } \
290 \
291 \
292 static inline LIST_UNUSED void name##_shrink_to_fit(name##_t *list) { \
293 assert(list != NULL); \
294 \
295 if (list->capacity > list->size) { \
296 list->data = (type *)gv_recalloc(list->data, list->capacity, list->size, \
297 sizeof(type)); \
298 list->capacity = list->size; \
299 } \
300 } \
301 \
302 \
303 static inline LIST_UNUSED void name##_free(name##_t *list) { \
304 assert(list != NULL); \
305 name##_clear(list); \
306 free(list->data); \
307 memset(list, 0, sizeof(*list)); \
308 } \
309 \
310 \
311 static inline LIST_UNUSED void name##_push(name##_t *list, type value) { \
312 name##_append(list, value); \
313 } \
314 \
315 \
316 static inline LIST_UNUSED type name##_pop(name##_t *list) { \
317 assert(list != NULL); \
318 assert(list->size > 0); \
319 \
320 type value = list->data[list->size - 1]; \
321 \
322 /* do not call `dtor` because we are transferring ownership of the removed \
323 * element to the caller \
324 */ \
325 --list->size; \
326 \
327 return value; \
328 } \
329 \
330 \
340 static inline LIST_UNUSED name##_t name##_attach(type *data, size_t size) { \
341 assert(data != NULL || size == 0); \
342 name##_t list = {data, size, size}; \
343 return list; \
344 } \
345 \
346 \
355 static inline LIST_UNUSED type *name##_detach(name##_t *list) { \
356 assert(list != NULL); \
357 type *data = list->data; \
358 memset(list, 0, sizeof(*list)); \
359 return data; \
360 }
alloc.h
Memory allocation wrappers that exit on failure.