1 /* Type-safe arrays which grow dynamically.
2 Copyright 2021 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17 /* Written by Paul Eggert and Bruno Haible, 2021. */
19 #ifndef _GL_DYNARRAY_H
20 #define _GL_DYNARRAY_H
22 /* Before including this file, you need to define:
25 The struct tag of dynamic array to be defined.
28 The type name of the element type. Elements are copied
29 as if by memcpy, and can change address as the dynamic
33 The prefix of the functions which are defined.
35 The following parameters are optional:
38 DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the
39 contents of elements. E is of type DYNARRAY_ELEMENT *.
42 DYNARRAY_ELEMENT_INIT (E) is evaluated to initialize a new
43 element. E is of type DYNARRAY_ELEMENT *.
44 If DYNARRAY_ELEMENT_FREE but not DYNARRAY_ELEMENT_INIT is
45 defined, new elements are automatically zero-initialized.
46 Otherwise, new elements have undefined contents.
49 The size of the statically allocated array (default:
50 at least 2, more elements if they fit into 128 bytes).
51 Must be a preprocessor constant. If DYNARRAY_INITIAL_SIZE is 0,
52 there is no statically allocated array at, and all non-empty
53 arrays are heap-allocated.
56 The name of the type which holds the final array. If not
57 defined, is PREFIX##finalize not provided. DYNARRAY_FINAL_TYPE
58 must be a struct type, with members of type DYNARRAY_ELEMENT and
59 size_t at the start (in this order).
61 These macros are undefined after this header file has been
64 The following types are provided (their members are private to the
65 dynarray implementation):
67 struct DYNARRAY_STRUCT
69 The following functions are provided:
72 /* Initialize a dynamic array object. This must be called before any
76 DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *list);
79 /* Deallocate the dynamic array and its elements. */
82 DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *list);
85 /* Return true if the dynamic array is in an error state. */
88 DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *list);
91 /* Mark the dynamic array as failed. All elements are deallocated as
95 DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *list);
98 /* Return the number of elements which have been added to the dynamic
102 DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *list);
105 /* Return a pointer to the first array element, if any. For a
106 zero-length array, the pointer can be NULL even though the dynamic
107 array has not entered the failure state. */
109 static DYNARRAY_ELEMENT *
110 DYNARRAY_PREFIX##begin (const struct DYNARRAY_STRUCT *list);
113 /* Return a pointer one element past the last array element. For a
114 zero-length array, the pointer can be NULL even though the dynamic
115 array has not entered the failure state. */
117 static DYNARRAY_ELEMENT *
118 DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUCT *list);
121 /* Return a pointer to the array element at INDEX. Terminate the
122 process if INDEX is out of bounds. */
124 static DYNARRAY_ELEMENT *
125 DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *list, size_t index);
128 /* Add ITEM at the end of the array, enlarging it by one element.
129 Mark *LIST as failed if the dynamic array allocation size cannot be
133 DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *list,
134 DYNARRAY_ELEMENT item);
137 /* Allocate a place for a new element in *LIST and return a pointer to
138 it. The pointer can be NULL if the dynamic array cannot be
139 enlarged due to a memory allocation failure. */
141 static DYNARRAY_ELEMENT *
142 DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *list);
145 /* Change the size of *LIST to SIZE. If SIZE is larger than the
146 existing size, new elements are added (which can be initialized).
147 Otherwise, the list is truncated, and elements are freed. Return
148 false on memory allocation failure (and mark *LIST as failed). */
151 DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *list, size_t size);
154 /* Remove the last element of LIST if it is present. */
157 DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *list);
160 /* Remove all elements from the list. The elements are freed, but the
161 list itself is not. */
164 DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *list);
167 #if defined DYNARRAY_FINAL_TYPE
168 /* Transfer the dynamic array to a permanent location at *RESULT.
169 Returns true on success on false on allocation failure. In either
170 case, *LIST is re-initialized and can be reused. A NULL pointer is
171 stored in *RESULT if LIST refers to an empty list. On success, the
172 pointer in *RESULT is heap-allocated and must be deallocated using
176 DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *list,
177 DYNARRAY_FINAL_TYPE *result);
179 #else /* !defined DYNARRAY_FINAL_TYPE */
180 /* Transfer the dynamic array to a heap-allocated array and return a
181 pointer to it. The pointer is NULL if memory allocation fails, or
182 if the array is empty, so this function should be used only for
183 arrays which are known not be empty (usually because they always
184 have a sentinel at the end). If LENGTHP is not NULL, the array
185 length is written to *LENGTHP. *LIST is re-initialized and can be
188 static DYNARRAY_ELEMENT *
189 DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *list,
194 /* A minimal example which provides a growing list of integers can be
199 // Pointer to result array followed by its length,
200 // as required by DYNARRAY_FINAL_TYPE.
205 #define DYNARRAY_STRUCT dynarray_int
206 #define DYNARRAY_ELEMENT int
207 #define DYNARRAY_PREFIX dynarray_int_
208 #define DYNARRAY_FINAL_TYPE struct int_array
209 #include <malloc/dynarray-skeleton.c>
211 To create a three-element array with elements 1, 2, 3, use this
214 struct dynarray_int dyn;
215 dynarray_int_init (&dyn);
216 for (int i = 1; i <= 3; ++i)
218 int *place = dynarray_int_emplace (&dyn);
219 assert (place != NULL);
222 struct int_array result;
223 bool ok = dynarray_int_finalize (&dyn, &result);
225 assert (result.length == 3);
226 assert (result.array[0] == 1);
227 assert (result.array[1] == 2);
228 assert (result.array[2] == 3);
231 If the elements contain resources which must be freed, define
232 DYNARRAY_ELEMENT_FREE appropriately, like this:
240 #define DYNARRAY_STRUCT dynarray_str
241 #define DYNARRAY_ELEMENT char *
242 #define DYNARRAY_ELEMENT_FREE(ptr) free (*ptr)
243 #define DYNARRAY_PREFIX dynarray_str_
244 #define DYNARRAY_FINAL_TYPE struct str_array
245 #include <malloc/dynarray-skeleton.c>
249 /* The implementation is imported from glibc. */
251 /* Avoid possible conflicts with symbols exported by the GNU libc. */
252 #define __libc_dynarray_at_failure gl_dynarray_at_failure
253 #define __libc_dynarray_emplace_enlarge gl_dynarray_emplace_enlarge
254 #define __libc_dynarray_finalize gl_dynarray_finalize
255 #define __libc_dynarray_resize_clear gl_dynarray_resize_clear
256 #define __libc_dynarray_resize gl_dynarray_resize
258 #if defined DYNARRAY_STRUCT || defined DYNARRAY_ELEMENT || defined DYNARRAY_PREFIX
260 # include <libc-config.h>
262 /* Define auxiliary structs and declare auxiliary functions, common to all
263 instantiations of dynarray. */
264 # include <malloc/dynarray.h>
266 /* Define the instantiation, specified through
271 # include <malloc/dynarray-skeleton.c>
275 /* This file is being included from one of the malloc/dynarray_*.c files. */
276 # include <malloc/dynarray.h>
280 #endif /* _GL_DYNARRAY_H */