Debian Codegraph @

libdrgn/vector.h

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 /**
5 * @file
6 *
7 * Dynamic arrays.
8 *
9 * See @ref Vectors.
10 */
11
12 #ifndef DRGN_VECTOR_H
13 #define DRGN_VECTOR_H
14
15 #include <stdbool.h>
16 #include <stdlib.h> // IWYU pragma: keep
17 #include <string.h> // IWYU pragma: keep
18
19 #include "generics.h"
20 #include "minmax.h"
21 #include "util.h"
22 #include "pp.h"
23
24 /**
25 * @ingroup Internals
26 *
27 * @defgroup Vectors Vectors
28 *
29 * Dynamic arrays (a.k.a.\ vectors).
30 *
31 * This is an implementation of generic, strongly-typed vectors.
32 *
33 * A vector is defined with @ref DEFINE_VECTOR(). Each generated vector
34 * interface is prefixed with a given name; the interface documented here uses
35 * the example name @c vector.
36 *
37 * @{
38 */
39
40 #ifdef DOXYGEN
41 /**
42 * @struct vector
43 *
44 * Vector instance.
45 *
46 * There are no requirements on how this is allocated; it may be global, on the
47 * stack, allocated by @c malloc(), embedded in another structure, etc.
48 */
49 struct vector;
50
51 /**
52 * Initialize a @ref vector.
53 *
54 * The new vector is empty.
55 *
56 * @sa VECTOR_INIT
57 */
58 void vector_init(struct vector *vector);
59
60 /** Free memory allocated by a @ref vector. */
61 void vector_deinit(struct vector *vector);
62
63 /** Return the number of entries in a @ref vector. */
64 size_type vector_size(const struct vector *vector);
65
66 /** Return whether a @ref vector is empty. */
67 bool vector_empty(const struct vector *vector);
68
69 /**
70 * Maximum possible number of entries in a @ref vector.
71 *
72 * Attempts to increase the size or capacity beyond this will fail.
73 */
74 const size_type vector_max_size;
75
76 /**
77 * Update the number of entries in a @ref vector.
78 *
79 * If @p size is greater than the current capacity, this increases the capacity
80 * to at least @p size and reallocates the entries.
81 *
82 * If @p size is greater than the current size, the entries between the old size
83 * and the new size are uninitialized.
84 *
85 * @return @c true on success, @c false on failure.
86 */
87 bool vector_resize(struct vector *vector, size_t size);
88
89 /**
90 * Set the size of a @ref vector to zero.
91 *
92 * This does not change the capacity or free the entries.
93 */
94 void vector_clear(struct vector *vector);
95
96 /** Return the number of allocated entries in a @ref vector. */
97 size_type vector_capacity(const struct vector *vector);
98
99 /**
100 * Increase the capacity of a @ref vector.
101 *
102 * If @p capacity is greater than the current capacity, this increases the
103 * capacity to at least @p capacity and reallocates the entries. Otherwise, it
104 * does nothing.
105 *
106 * @return @c true on success, @c false on failure.
107 */
108 bool vector_reserve(struct vector *vector, size_t capacity);
109
110 /**
111 * Increase the capacity of a @ref vector to accomodate at least one append.
112 *
113 * If the current capacity is equal to the current size, this increases the
114 * capacity by at least one and reallocates the entries. Otherwise, it does
115 * nothing.
116 *
117 * @return @c true on success, @c false on failure.
118 */
119 bool vector_reserve_for_append(struct vector *vector);
120
121 /**
122 * Increase the capacity of a @ref vector to accomodate at least @p n appends.
123 *
124 * If the current capacity minus the current size is not at least @p n, this
125 * increases the capacity by at least @p n and reallocates the entries.
126 * Otherwise, it does nothing.
127 *
128 * @return @c true on success, @c false on failure.
129 */
130 bool vector_reserve_for_extend(struct vector *vector, size_t n);
131
132 /**
133 * Free unused memory in a @ref vector.
134 *
135 * This may reduce the capacity and reallocate the entries. It may also do
136 * nothing.
137 */
138 void vector_shrink_to_fit(struct vector *vector);
139
140 /**
141 * Steal the array of entries from a @ref vector.
142 *
143 * This returns the internal array of entries. The vector can no longer be used
144 * except to be passed to @ref vector_deinit(), which will do nothing.
145 *
146 * This is undefined if the vector type was defined with a non-zero @c
147 * inline_size.
148 *
149 * This can be used to build an array when the size isn't known ahead of time
150 * but won't change after the array is built. For example:
151 *
152 * ```
153 * DEFINE_VECTOR(int_vector, int);
154 *
155 * bool primes_less_than(int n, int **array_ret, size_t *size_ret)
156 * {
157 *
158 * _cleanup_(int_vector_deinit) struct int_vector vector = VECTOR_INIT;
159 * for (int i = 2; i < n; i++) {
160 * if (is_prime(i) && !int_vector_push(&vector, &i))
161 * return false;
162 * }
163 * int_vector_shrink_to_fit(&vector);
164 * int_vector_steal(&vector, array_ret, size_ret);
165 * return true;
166 * }
167 * ```
168 *
169 * As demonstrated here, it may be desirable to call @ref vector_shrink_to_fit()
170 * first.
171 *
172 * @param[out] entries_ret Returned array. This must be freed with @c free().
173 * @param[out] size_ret Returned number of entries in array. May be @c NULL.
174 */
175 void vector_steal(struct vector *vector, entry_type **entries_ret,
176 size_type *size_ret);
177
178 /**
179 * Return the array of entries in a @ref vector.
180 *
181 * The vector may be empty, in which case this is equal to `vector_end(vector)`.
182 */
183 entry_type *vector_begin(struct vector *vector);
184
185 /**
186 * Return one past the last entry in a @ref vector.
187 *
188 * The vector may be empty, in which case this is equal to
189 * `vector_begin(vector)`.
190 */
191 entry_type *vector_end(struct vector *vector);
192
193 /**
194 * Return the first entry in a @ref vector.
195 *
196 * This is equivalent to `vector_at(vector, 0)`. The vector must not be empty
197 * (in contrast to @ref vector_begin()).
198 */
199 entry_type *vector_first(struct vector *vector);
200
201 /**
202 * Return the last entry in a @ref vector.
203 *
204 * This is equivalent to `vector_at(vector, vector_size(vector) - 1)`. The
205 * vector must not be empty.
206 */
207 entry_type *vector_last(struct vector *vector);
208
209 /**
210 * Return the entry at the given index in a @ref vector.
211 *
212 * @param[in] i Entry index. Must be less than the size of the vector.
213 */
214 entry_type *vector_at(struct vector *vector, size_t i);
215
216 /**
217 * Append to a @ref vector.
218 *
219 * This increases vector's size by one. If the current capacity is equal to the
220 * current size, this increases the capacity by at least one and reallocates the
221 * entries.
222 *
223 * @return @c true on success, @c false on failure.
224 */
225 bool vector_append(struct vector *vector, const entry_type *entry);
226
227 /**
228 * Append an uninitialized entry to a @ref vector.
229 *
230 * Like @ref vector_append(), but return a pointer to the new (uninitialized)
231 * entry.
232 *
233 * @return The new entry on success, @c NULL on failure.
234 */
235 entry_type *vector_append_entry(struct vector *vector);
236
237 /**
238 * Append all of the entries from one vector to another.
239 *
240 * @param[in] dst Vector to append to.
241 * @param[in] src Source vector. This is not modified.
242 * @return @c true on success, @c false on failure.
243 */
244 bool vector_extend(struct vector *dst, const struct vector *src);
245
246 /**
247 * Remove and return the last entry in a @ref vector.
248 *
249 * The vector must not be empty. This decreases the size by one. It does not
250 * change the capacity or reallocate the entries.
251 *
252 * @return A pointer to the removed entry, which remains valid until another
253 * entry is inserted in its place or the entries are reallocated.
254 */
255 entry_type *vector_pop(struct vector *vector);
256 #endif
257
258 /**
259 * Inline as many entries as possible without making the vector type larger than
260 * if @c inline_size was 0.
261 *
262 * This can be passed as the @c inline_size argument to @ref DEFINE_VECTOR().
263 */
264 #define vector_inline_minimal -1
265
266 /**
267 * Define a vector type without defining its functions.
268 *
269 * This is useful when the vector type must be defined in one place (e.g., a
270 * header) but the interface is defined elsewhere (e.g., a source file) with
271 * @ref DEFINE_VECTOR_FUNCTIONS(). Otherwise, just use @ref DEFINE_VECTOR().
272 *
273 * This takes the same arguments as @ref DEFINE_VECTOR().
274 */
275 #define DEFINE_VECTOR_TYPE(...) \
276 PP_OVERLOAD(DEFINE_VECTOR_TYPE_I, __VA_ARGS__)(__VA_ARGS__)
277 #define DEFINE_VECTOR_TYPE_I2(vector, entry_type) \
278 DEFINE_VECTOR_TYPE_I3(vector, entry_type, 0)
279 #define DEFINE_VECTOR_TYPE_I3(vector, entry_type, inline_size) \
280 DEFINE_VECTOR_TYPE_I4(vector, entry_type, inline_size, size_t)
281 #define DEFINE_VECTOR_TYPE_I4(vector, entry_type, inline_size, size_type) \
282 typedef typeof(entry_type) vector##_entry_type; \
283 \
284 typedef typeof(size_type) vector##_size_type; \
285 _Static_assert((vector##_size_type)-1 > 0, "size_type must be unsigned"); \
286 _Static_assert((vector##_size_type)-1 <= SIZE_MAX, \
287 "size_type must not be larger than size_t"); \
288 \
289 enum { vector##_inline_size_arg = (inline_size) }; \
290 /* \
291 * If the vector was defined with a zero inline size, then we don't want to \
292 * require the complete definition of the entry type, so we do this to stub it \
293 * out. \
294 */ \
295 typedef_if(vector##_inline_entry_type, vector##_inline_size_arg == 0, void *, \
296 vector##_entry_type); \
297 enum { \
298 vector##_inline_size = \
299 vector##_inline_size_arg == vector_inline_minimal \
300 ? sizeof(void *) / sizeof(vector##_inline_entry_type) \
301 : vector##_inline_size_arg, \
302 /* Used to avoid a zero-length array. */ \
303 vector##_inline_size_non_zero = \
304 vector##_inline_size == 0 ? 1 : vector##_inline_size, \
305 }; \
306 \
307 struct vector { \
308 union { \
309 vector##_entry_type *_data; \
310 /* \
311 * If the vector has no inline entries, then we want this to \
312 * degrade to (entry_type *) instead of (entry_type [0]) so that\
313 * the vector is not over-aligned to alignof(entry_type) and to \
314 * avoid zero-length arrays. \
315 */ \
316 type_if(vector##_inline_size == 0, vector##_entry_type *, \
317 vector##_inline_entry_type [vector##_inline_size_non_zero])\
318 _idata; \
319 }; \
320 vector##_size_type _size; \
321 vector##_size_type _capacity; \
322 }; \
323 struct DEFINE_VECTOR_needs_semicolon
324
325 /**
326 * Define the functions for a vector.
327 *
328 * The vector type must have already been defined with @ref
329 * DEFINE_VECTOR_TYPE().
330 *
331 * Unless the type and function definitions must be in separate places, use @ref
332 * DEFINE_VECTOR() instead.
333 *
334 * @sa DEFINE_VECTOR()
335 */
336 #define DEFINE_VECTOR_FUNCTIONS(vector) \
337 __attribute__((__unused__)) \
338 static void vector##_init(struct vector *vector) \
339 { \
340 if (vector##_inline_size == 0) \
341 vector->_data = NULL; \
342 vector->_size = vector->_capacity = 0; \
343 } \
344 \
345 static bool vector##_is_inline(const struct vector *vector) \
346 { \
347 return vector##_inline_size > 0 && vector->_capacity == 0; \
348 } \
349 \
350 __attribute__((__unused__)) \
351 static void vector##_deinit(struct vector *vector) \
352 { \
353 if (!vector##_is_inline(vector)) \
354 free(vector->_data); \
355 } \
356 \
357 __attribute__((__unused__)) \
358 static vector##_size_type vector##_size(const struct vector *vector) \
359 { \
360 return vector->_size; \
361 } \
362 \
363 __attribute__((__unused__)) \
364 static bool vector##_empty(const struct vector *vector) \
365 { \
366 return vector->_size == 0; \
367 } \
368 \
369 static const vector##_size_type vector##_max_size = \
370 /* The redundant cast works around llvm/llvm-project#38137. */ \
371 (vector##_size_type)min_iconst(PTRDIFF_MAX / sizeof(vector##_entry_type),\
372 (vector##_size_type)-1); \
373 \
374 static vector##_size_type vector##_capacity(const struct vector *vector) \
375 { \
376 if (vector##_is_inline(vector)) \
377 return vector##_inline_size; \
378 return vector->_capacity; \
379 } \
380 \
381 static bool vector##_reallocate(struct vector *vector, size_t capacity) \
382 { \
383 void *new_data; \
384 if (vector##_is_inline(vector)) { \
385 new_data = malloc(capacity * sizeof(vector##_entry_type)); \
386 if (!new_data) \
387 return false; \
388 memcpy(new_data, vector->_idata, \
389 vector##_size(vector) * sizeof(vector##_entry_type)); \
390 } else { \
391 new_data = realloc(vector->_data, \
392 capacity * sizeof(vector##_entry_type)); \
393 if (!new_data) \
394 return false; \
395 } \
396 vector->_data = new_data; \
397 vector->_capacity = capacity; \
398 return true; \
399 } \
400 \
401 static bool vector##_reserve_for_extend(struct vector *vector, size_t n) \
402 { \
403 vector##_size_type size = vector##_size(vector); \
404 /* \
405 * Cast to size_t to avoid -Wsign-error if size_type is promoted to int.\
406 */ \
407 if (n <= (size_t)(vector##_capacity(vector) - size)) \
408 return true; \
409 if (n > (size_t)(vector##_max_size - size)) \
410 return false; \
411 vector##_size_type new_capacity = size + (n > size ? n : size); \
412 if (new_capacity < size || new_capacity > vector##_max_size) \
413 new_capacity = vector##_max_size; \
414 return vector##_reallocate(vector, new_capacity); \
415 } \
416 \
417 __attribute__((__unused__)) \
418 static bool vector##_resize(struct vector *vector, size_t size) \
419 { \
420 if (vector->_size < size \
421 && !vector##_reserve_for_extend(vector, size - vector->_size)) \
422 return false; \
423 vector->_size = size; \
424 return true; \
425 } \
426 \
427 __attribute__((__unused__)) \
428 static void vector##_clear(struct vector *vector) \
429 { \
430 vector->_size = 0; \
431 } \
432 \
433 __attribute__((__unused__)) \
434 static bool vector##_reserve(struct vector *vector, size_t capacity) \
435 { \
436 if (capacity <= vector##_capacity(vector)) \
437 return true; \
438 if (capacity > vector##_max_size) \
439 return false; \
440 return vector##_reallocate(vector, capacity); \
441 } \
442 \
443 static bool vector##_reserve_for_append(struct vector *vector) \
444 { \
445 return vector##_reserve_for_extend(vector, 1); \
446 } \
447 \
448 __attribute__((__unused__)) \
449 static void vector##_shrink_to_fit(struct vector *vector) \
450 { \
451 vector##_size_type size = vector##_size(vector); \
452 if (vector->_capacity <= size) \
453 return; \
454 if (size > vector##_inline_size) { \
455 vector##_reallocate(vector, size); \
456 } else if (vector##_inline_size > 0) { \
457 void *old_data = vector->_data; \
458 memcpy(vector->_idata, old_data, \
459 size * sizeof(vector##_entry_type)); \
460 free(old_data); \
461 vector->_capacity = 0; \
462 } else { \
463 free(vector->_data); \
464 vector->_data = NULL; \
465 vector->_capacity = 0; \
466 } \
467 } \
468 \
469 /* \
470 * If the vector was defined with a non-zero inline size, make vector_steal() \
471 * fail at compile time by having it take a dummy type incompatible with struct \
472 * vector (but close enough to the real thing so the function body compiles). \
473 */ \
474 struct vector##_steal_is_undefined_for_non_zero_inline_size { \
475 void *_data; \
476 vector##_size_type _size; \
477 }; \
478 __attribute__((__unused__)) \
479 static void vector##_steal(type_if(vector##_inline_size_arg == 0, \
480 struct vector, \
481 struct vector##_steal_is_undefined_for_non_zero_inline_size)\
482 *vector, \
483 vector##_entry_type **entries_ret, \
484 vector##_size_type *size_ret) \
485 { \
486 *entries_ret = vector->_data; \
487 if (size_ret) \
488 *size_ret = vector->_size; \
489 vector->_data = NULL; \
490 } \
491 \
492 static vector##_entry_type *vector##_begin(struct vector *vector) \
493 { \
494 if (vector##_is_inline(vector)) \
495 return vector->_idata; \
496 return vector->_data; \
497 } \
498 \
499 __attribute__((__unused__)) \
500 static vector##_entry_type *vector##_end(struct vector *vector) \
501 { \
502 return add_to_possibly_null_pointer(vector##_begin(vector), \
503 vector##_size(vector)); \
504 } \
505 \
506 __attribute__((__unused__)) \
507 static vector##_entry_type *vector##_first(struct vector *vector) \
508 { \
509 return vector##_begin(vector); \
510 } \
511 \
512 __attribute__((__unused__)) \
513 static vector##_entry_type *vector##_last(struct vector *vector) \
514 { \
515 return vector##_begin(vector) + vector##_size(vector) - 1; \
516 } \
517 \
518 __attribute__((__unused__)) \
519 static vector##_entry_type *vector##_at(struct vector *vector, size_t i) \
520 { \
521 return vector##_begin(vector) + i; \
522 } \
523 \
524 static vector##_entry_type *vector##_append_entry(struct vector *vector) \
525 { \
526 if (!vector##_reserve_for_append(vector)) \
527 return NULL; \
528 return vector##_begin(vector) + vector->_size++; \
529 } \
530 \
531 __attribute__((__unused__)) \
532 static bool vector##_append(struct vector *vector, \
533 const vector##_entry_type *entry) \
534 { \
535 vector##_entry_type *new_entry = vector##_append_entry(vector); \
536 if (!new_entry) \
537 return false; \
538 memcpy(new_entry, entry, sizeof(*entry)); \
539 return true; \
540 } \
541 \
542 __attribute__((__unused__)) \
543 static bool vector##_extend(struct vector *dst, const struct vector *src) \
544 { \
545 if (src->_size == 0) \
546 return true; \
547 if (!vector##_reserve_for_extend(dst, src->_size)) \
548 return false; \
549 memcpy(vector##_end(dst), vector##_begin((struct vector *)src), \
550 src->_size * sizeof(vector##_entry_type)); \
551 dst->_size += src->_size; \
552 return true; \
553 } \
554 \
555 __attribute__((__unused__)) \
556 static vector##_entry_type *vector##_pop(struct vector *vector) \
557 { \
558 return vector##_begin(vector) + --vector->_size; \
559 } \
560 struct DEFINE_VECTOR_needs_semicolon
561
562 /**
563 * Define a vector interface.
564 *
565 * This macro defines a vector type along with its functions. It accepts a
566 * variable number of arguments:
567 *
568 * ```
569 * DEFINE_VECTOR(vector, entry_type);
570 * DEFINE_VECTOR(vector, entry_type, inline_size);
571 * DEFINE_VECTOR(vector, entry_type, inline_size, size_type);
572 * ```
573 *
574 * @param[in] vector Name of the type to define. This is prefixed to all of the
575 * types and functions defined for that type.
576 * @param[in] entry_type Type of entries in the vector.
577 * @param[in] inline_size Number of entries to store directly in the vector type
578 * instead of as a separate allocation, or @ref vector_inline_minimal. The
579 * default is 0. If this is not 0, then the complete definition of @p entry_type
580 * must be available.
581 * @param[in] size_type Unsigned integer type to use to store size and capacity.
582 * The default is `size_t`.
583 */
584 #define DEFINE_VECTOR(vector, ...) \
585 DEFINE_VECTOR_TYPE(vector, __VA_ARGS__); \
586 DEFINE_VECTOR_FUNCTIONS(vector)
587
588 /**
589 * Empty vector initializer.
590 *
591 * This can be used to initialize a vector when declaring it.
592 *
593 * @sa vector_init()
594 */
595 #define VECTOR_INIT { { 0 } }
596
597 /**
598 * Define and initialize an empty @ref vector of type @p vector_type named @p
599 * vector that is automatically deinitialized when it goes out of scope.
600 */
601 #define VECTOR(vector_type, vector) \
602 __attribute__((__cleanup__(vector_type##_deinit))) \
603 struct vector_type vector = VECTOR_INIT
604
605 /**
606 * Iterate over every entry in a @ref vector.
607 *
608 * This is roughly equivalent to
609 *
610 * ```
611 * for (entry_type *it = vector_begin(vector), *end = vector_end(vector);
612 * it != end; it++)
613 * ```
614 *
615 * Except that @p vector is only evaluated once.
616 *
617 * @param[in] vector_type Name of vector type.
618 * @param[out] it Name of iteration variable.
619 * @param[in] vector Vector to iterate over.
620 */
621 #define vector_for_each(vector_type, it, vector) \
622 for (vector_type##_entry_type *it, \
623 *it##__end = ({ \
624 struct vector_type *it##__vector = (vector); \
625 it = vector_type##_begin(it##__vector); \
626 vector_type##_end(it##__vector); \
627 }); \
628 it != it##__end; it++)
629
630 /** @} */
631
632 #endif /* DRGN_VECTOR_H */