1/* Type-safe arrays which grow dynamically.
2 Copyright (C) 2017-2020 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19/* Pre-processor macros which act as parameters:
20
21 DYNARRAY_STRUCT
22 The struct tag of dynamic array to be defined.
23 DYNARRAY_ELEMENT
24 The type name of the element type. Elements are copied
25 as if by memcpy, and can change address as the dynamic
26 array grows.
27 DYNARRAY_PREFIX
28 The prefix of the functions which are defined.
29
30 The following parameters are optional:
31
32 DYNARRAY_ELEMENT_FREE
33 DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the
34 contents of elements. E is of type DYNARRAY_ELEMENT *.
35 DYNARRAY_ELEMENT_INIT
36 DYNARRAY_ELEMENT_INIT (E) is evaluated to initialize a new
37 element. E is of type DYNARRAY_ELEMENT *.
38 If DYNARRAY_ELEMENT_FREE but not DYNARRAY_ELEMENT_INIT is
39 defined, new elements are automatically zero-initialized.
40 Otherwise, new elements have undefined contents.
41 DYNARRAY_INITIAL_SIZE
42 The size of the statically allocated array (default:
43 at least 2, more elements if they fit into 128 bytes).
44 Must be a preprocessor constant. If DYNARRAY_INITIAL_SIZE is 0,
45 there is no statically allocated array at, and all non-empty
46 arrays are heap-allocated.
47 DYNARRAY_FINAL_TYPE
48 The name of the type which holds the final array. If not
49 defined, is PREFIX##finalize not provided. DYNARRAY_FINAL_TYPE
50 must be a struct type, with members of type DYNARRAY_ELEMENT and
51 size_t at the start (in this order).
52
53 These macros are undefined after this header file has been
54 included.
55
56 The following types are provided (their members are private to the
57 dynarray implementation):
58
59 struct DYNARRAY_STRUCT
60
61 The following functions are provided:
62
63 void DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *);
64 void DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *);
65 bool DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *);
66 void DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *);
67 size_t DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *);
68 DYNARRAY_ELEMENT *DYNARRAY_PREFIX##begin (const struct DYNARRAY_STRUCT *);
69 DYNARRAY_ELEMENT *DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUCT *);
70 DYNARRAY_ELEMENT *DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *, size_t);
71 void DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *, DYNARRAY_ELEMENT);
72 DYNARRAY_ELEMENT *DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *);
73 bool DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *, size_t);
74 void DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *);
75 void DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *);
76
77 The following functions are provided are provided if the
78 prerequisites are met:
79
80 bool DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
81 DYNARRAY_FINAL_TYPE *);
82 (if DYNARRAY_FINAL_TYPE is defined)
83 DYNARRAY_ELEMENT *DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
84 size_t *);
85 (if DYNARRAY_FINAL_TYPE is not defined)
86*/
87
88#include <malloc/dynarray.h>
89
90#include <errno.h>
91#include <stdlib.h>
92#include <string.h>
93
94#ifndef DYNARRAY_STRUCT
95# error "DYNARRAY_STRUCT must be defined"
96#endif
97
98#ifndef DYNARRAY_ELEMENT
99# error "DYNARRAY_ELEMENT must be defined"
100#endif
101
102#ifndef DYNARRAY_PREFIX
103# error "DYNARRAY_PREFIX must be defined"
104#endif
105
106#ifdef DYNARRAY_INITIAL_SIZE
107# if DYNARRAY_INITIAL_SIZE < 0
108# error "DYNARRAY_INITIAL_SIZE must be non-negative"
109# endif
110# if DYNARRAY_INITIAL_SIZE > 0
111# define DYNARRAY_HAVE_SCRATCH 1
112# else
113# define DYNARRAY_HAVE_SCRATCH 0
114# endif
115#else
116/* Provide a reasonable default which limits the size of
117 DYNARRAY_STRUCT. */
118# define DYNARRAY_INITIAL_SIZE \
119 (sizeof (DYNARRAY_ELEMENT) > 64 ? 2 : 128 / sizeof (DYNARRAY_ELEMENT))
120# define DYNARRAY_HAVE_SCRATCH 1
121#endif
122
123/* Public type definitions. */
124
125/* All fields of this struct are private to the implementation. */
126struct DYNARRAY_STRUCT
127{
128 union
129 {
130 struct dynarray_header dynarray_abstract;
131 struct
132 {
133 /* These fields must match struct dynarray_header. */
134 size_t used;
135 size_t allocated;
136 DYNARRAY_ELEMENT *array;
137 } dynarray_header;
138 };
139
140#if DYNARRAY_HAVE_SCRATCH
141 /* Initial inline allocation. */
142 DYNARRAY_ELEMENT scratch[DYNARRAY_INITIAL_SIZE];
143#endif
144};
145
146/* Internal use only: Helper macros. */
147
148/* Ensure macro-expansion of DYNARRAY_PREFIX. */
149#define DYNARRAY_CONCAT0(prefix, name) prefix##name
150#define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name)
151#define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name)
152
153/* Address of the scratch buffer if any. */
154#if DYNARRAY_HAVE_SCRATCH
155# define DYNARRAY_SCRATCH(list) (list)->scratch
156#else
157# define DYNARRAY_SCRATCH(list) NULL
158#endif
159
160/* Internal use only: Helper functions. */
161
162/* Internal function. Call DYNARRAY_ELEMENT_FREE with the array
163 elements. Name mangling needed due to the DYNARRAY_ELEMENT_FREE
164 macro expansion. */
165static inline void
166DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array,
167 size_t __dynarray_used)
168{
169#ifdef DYNARRAY_ELEMENT_FREE
170 for (size_t __dynarray_i = 0; __dynarray_i < __dynarray_used; ++__dynarray_i)
171 DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]);
172#endif /* DYNARRAY_ELEMENT_FREE */
173}
174
175/* Internal function. Free the non-scratch array allocation. */
176static inline void
177DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list)
178{
179#if DYNARRAY_HAVE_SCRATCH
180 if (list->dynarray_header.array != list->scratch)
181 free (list->dynarray_header.array);
182#else
183 free (list->dynarray_header.array);
184#endif
185}
186
187/* Public functions. */
188
189/* Initialize a dynamic array object. This must be called before any
190 use of the object. */
191__attribute__ ((nonnull (1)))
192static void
193DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
194{
195 list->dynarray_header.used = 0;
196 list->dynarray_header.allocated = DYNARRAY_INITIAL_SIZE;
197 list->dynarray_header.array = DYNARRAY_SCRATCH (list);
198}
199
200/* Deallocate the dynamic array and its elements. */
201__attribute__ ((unused, nonnull (1)))
202static void
203DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list)
204{
205 DYNARRAY_NAME (free__elements__)
206 (list->dynarray_header.array, list->dynarray_header.used);
207 DYNARRAY_NAME (free__array__) (list);
208 DYNARRAY_NAME (init) (list);
209}
210
211/* Return true if the dynamic array is in an error state. */
212__attribute__ ((nonnull (1)))
213static inline bool
214DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list)
215{
216 return list->dynarray_header.allocated == __dynarray_error_marker ();
217}
218
219/* Mark the dynamic array as failed. All elements are deallocated as
220 a side effect. */
221__attribute__ ((nonnull (1)))
222static void
223DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list)
224{
225 DYNARRAY_NAME (free__elements__)
226 (list->dynarray_header.array, list->dynarray_header.used);
227 DYNARRAY_NAME (free__array__) (list);
228 list->dynarray_header.array = DYNARRAY_SCRATCH (list);
229 list->dynarray_header.used = 0;
230 list->dynarray_header.allocated = __dynarray_error_marker ();
231}
232
233/* Return the number of elements which have been added to the dynamic
234 array. */
235__attribute__ ((nonnull (1)))
236static inline size_t
237DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list)
238{
239 return list->dynarray_header.used;
240}
241
242/* Return a pointer to the array element at INDEX. Terminate the
243 process if INDEX is out of bounds. */
244__attribute__ ((nonnull (1)))
245static inline DYNARRAY_ELEMENT *
246DYNARRAY_NAME (at) (struct DYNARRAY_STRUCT *list, size_t index)
247{
248 if (__glibc_unlikely (index >= DYNARRAY_NAME (size) (list)))
249 __libc_dynarray_at_failure (DYNARRAY_NAME (size) (list), index);
250 return list->dynarray_header.array + index;
251}
252
253/* Return a pointer to the first array element, if any. For a
254 zero-length array, the pointer can be NULL even though the dynamic
255 array has not entered the failure state. */
256__attribute__ ((nonnull (1)))
257static inline DYNARRAY_ELEMENT *
258DYNARRAY_NAME (begin) (struct DYNARRAY_STRUCT *list)
259{
260 return list->dynarray_header.array;
261}
262
263/* Return a pointer one element past the last array element. For a
264 zero-length array, the pointer can be NULL even though the dynamic
265 array has not entered the failure state. */
266__attribute__ ((nonnull (1)))
267static inline DYNARRAY_ELEMENT *
268DYNARRAY_NAME (end) (struct DYNARRAY_STRUCT *list)
269{
270 return list->dynarray_header.array + list->dynarray_header.used;
271}
272
273/* Internal function. Slow path for the add function below. */
274static void
275DYNARRAY_NAME (add__) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
276{
277 if (__glibc_unlikely
278 (!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract,
279 DYNARRAY_SCRATCH (list),
280 sizeof (DYNARRAY_ELEMENT))))
281 {
282 DYNARRAY_NAME (mark_failed) (list);
283 return;
284 }
285
286 /* Copy the new element and increase the array length. */
287 list->dynarray_header.array[list->dynarray_header.used++] = item;
288}
289
290/* Add ITEM at the end of the array, enlarging it by one element.
291 Mark *LIST as failed if the dynamic array allocation size cannot be
292 increased. */
293__attribute__ ((unused, nonnull (1)))
294static inline void
295DYNARRAY_NAME (add) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
296{
297 /* Do nothing in case of previous error. */
298 if (DYNARRAY_NAME (has_failed) (list))
299 return;
300
301 /* Enlarge the array if necessary. */
302 if (__glibc_unlikely (list->dynarray_header.used
303 == list->dynarray_header.allocated))
304 {
305 DYNARRAY_NAME (add__) (list, item);
306 return;
307 }
308
309 /* Copy the new element and increase the array length. */
310 list->dynarray_header.array[list->dynarray_header.used++] = item;
311}
312
313/* Internal function. Building block for the emplace functions below.
314 Assumes space for one more element in *LIST. */
315static inline DYNARRAY_ELEMENT *
316DYNARRAY_NAME (emplace__tail__) (struct DYNARRAY_STRUCT *list)
317{
318 DYNARRAY_ELEMENT *result
319 = &list->dynarray_header.array[list->dynarray_header.used];
320 ++list->dynarray_header.used;
321#if defined (DYNARRAY_ELEMENT_INIT)
322 DYNARRAY_ELEMENT_INIT (result);
323#elif defined (DYNARRAY_ELEMENT_FREE)
324 memset (result, 0, sizeof (*result));
325#endif
326 return result;
327}
328
329/* Internal function. Slow path for the emplace function below. */
330static DYNARRAY_ELEMENT *
331DYNARRAY_NAME (emplace__) (struct DYNARRAY_STRUCT *list)
332{
333 if (__glibc_unlikely
334 (!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract,
335 DYNARRAY_SCRATCH (list),
336 sizeof (DYNARRAY_ELEMENT))))
337 {
338 DYNARRAY_NAME (mark_failed) (list);
339 return NULL;
340 }
341 return DYNARRAY_NAME (emplace__tail__) (list);
342}
343
344/* Allocate a place for a new element in *LIST and return a pointer to
345 it. The pointer can be NULL if the dynamic array cannot be
346 enlarged due to a memory allocation failure. */
347__attribute__ ((unused, warn_unused_result, nonnull (1)))
348static
349/* Avoid inlining with the larger initialization code. */
350#if !(defined (DYNARRAY_ELEMENT_INIT) || defined (DYNARRAY_ELEMENT_FREE))
351inline
352#endif
353DYNARRAY_ELEMENT *
354DYNARRAY_NAME (emplace) (struct DYNARRAY_STRUCT *list)
355{
356 /* Do nothing in case of previous error. */
357 if (DYNARRAY_NAME (has_failed) (list))
358 return NULL;
359
360 /* Enlarge the array if necessary. */
361 if (__glibc_unlikely (list->dynarray_header.used
362 == list->dynarray_header.allocated))
363 return (DYNARRAY_NAME (emplace__) (list));
364 return DYNARRAY_NAME (emplace__tail__) (list);
365}
366
367/* Change the size of *LIST to SIZE. If SIZE is larger than the
368 existing size, new elements are added (which can be initialized).
369 Otherwise, the list is truncated, and elements are freed. Return
370 false on memory allocation failure (and mark *LIST as failed). */
371__attribute__ ((unused, nonnull (1)))
372static bool
373DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size)
374{
375 if (size > list->dynarray_header.used)
376 {
377 bool ok;
378#if defined (DYNARRAY_ELEMENT_INIT)
379 /* The new elements have to be initialized. */
380 size_t old_size = list->dynarray_header.used;
381 ok = __libc_dynarray_resize (&list->dynarray_abstract,
382 size, DYNARRAY_SCRATCH (list),
383 sizeof (DYNARRAY_ELEMENT));
384 if (ok)
385 for (size_t i = old_size; i < size; ++i)
386 {
387 DYNARRAY_ELEMENT_INIT (&list->dynarray_header.array[i]);
388 }
389#elif defined (DYNARRAY_ELEMENT_FREE)
390 /* Zero initialization is needed so that the elements can be
391 safely freed. */
392 ok = __libc_dynarray_resize_clear
393 (&list->dynarray_abstract, size,
394 DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT));
395#else
396 ok = __libc_dynarray_resize (&list->dynarray_abstract,
397 size, DYNARRAY_SCRATCH (list),
398 sizeof (DYNARRAY_ELEMENT));
399#endif
400 if (__glibc_unlikely (!ok))
401 DYNARRAY_NAME (mark_failed) (list);
402 return ok;
403 }
404 else
405 {
406 /* The list has shrunk in size. Free the removed elements. */
407 DYNARRAY_NAME (free__elements__)
408 (list->dynarray_header.array + size,
409 list->dynarray_header.used - size);
410 list->dynarray_header.used = size;
411 return true;
412 }
413}
414
415/* Remove the last element of LIST if it is present. */
416__attribute__ ((unused, nonnull (1)))
417static void
418DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
419{
420 /* used > 0 implies that the array is the non-failed state. */
421 if (list->dynarray_header.used > 0)
422 {
423 size_t new_length = list->dynarray_header.used - 1;
424#ifdef DYNARRAY_ELEMENT_FREE
425 DYNARRAY_ELEMENT_FREE (&list->dynarray_header.array[new_length]);
426#endif
427 list->dynarray_header.used = new_length;
428 }
429}
430
431/* Remove all elements from the list. The elements are freed, but the
432 list itself is not. */
433__attribute__ ((unused, nonnull (1)))
434static void
435DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list)
436{
437 /* free__elements__ does nothing if the list is in the failed
438 state. */
439 DYNARRAY_NAME (free__elements__)
440 (list->dynarray_header.array, list->dynarray_header.used);
441 list->dynarray_header.used = 0;
442}
443
444#ifdef DYNARRAY_FINAL_TYPE
445/* Transfer the dynamic array to a permanent location at *RESULT.
446 Returns true on success on false on allocation failure. In either
447 case, *LIST is re-initialized and can be reused. A NULL pointer is
448 stored in *RESULT if LIST refers to an empty list. On success, the
449 pointer in *RESULT is heap-allocated and must be deallocated using
450 free. */
451__attribute__ ((unused, warn_unused_result, nonnull (1, 2)))
452static bool
453DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list,
454 DYNARRAY_FINAL_TYPE *result)
455{
456 struct dynarray_finalize_result res;
457 if (__libc_dynarray_finalize (&list->dynarray_abstract,
458 DYNARRAY_SCRATCH (list),
459 sizeof (DYNARRAY_ELEMENT), &res))
460 {
461 /* On success, the result owns all the data. */
462 DYNARRAY_NAME (init) (list);
463 *result = (DYNARRAY_FINAL_TYPE) { res.array, res.length };
464 return true;
465 }
466 else
467 {
468 /* On error, we need to free all data. */
469 DYNARRAY_NAME (free) (list);
470 errno = ENOMEM;
471 return false;
472 }
473}
474#else /* !DYNARRAY_FINAL_TYPE */
475/* Transfer the dynamic array to a heap-allocated array and return a
476 pointer to it. The pointer is NULL if memory allocation fails, or
477 if the array is empty, so this function should be used only for
478 arrays which are known not be empty (usually because they always
479 have a sentinel at the end). If LENGTHP is not NULL, the array
480 length is written to *LENGTHP. *LIST is re-initialized and can be
481 reused. */
482__attribute__ ((unused, warn_unused_result, nonnull (1)))
483static DYNARRAY_ELEMENT *
484DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)
485{
486 struct dynarray_finalize_result res;
487 if (__libc_dynarray_finalize (&list->dynarray_abstract,
488 DYNARRAY_SCRATCH (list),
489 sizeof (DYNARRAY_ELEMENT), &res))
490 {
491 /* On success, the result owns all the data. */
492 DYNARRAY_NAME (init) (list);
493 if (lengthp != NULL)
494 *lengthp = res.length;
495 return res.array;
496 }
497 else
498 {
499 /* On error, we need to free all data. */
500 DYNARRAY_NAME (free) (list);
501 errno = ENOMEM;
502 return NULL;
503 }
504}
505#endif /* !DYNARRAY_FINAL_TYPE */
506
507/* Undo macro definitions. */
508
509#undef DYNARRAY_CONCAT0
510#undef DYNARRAY_CONCAT1
511#undef DYNARRAY_NAME
512#undef DYNARRAY_SCRATCH
513#undef DYNARRAY_HAVE_SCRATCH
514
515#undef DYNARRAY_STRUCT
516#undef DYNARRAY_ELEMENT
517#undef DYNARRAY_PREFIX
518#undef DYNARRAY_ELEMENT_FREE
519#undef DYNARRAY_ELEMENT_INIT
520#undef DYNARRAY_INITIAL_SIZE
521#undef DYNARRAY_FINAL_TYPE
522