1 /* Type-safe arrays which grow dynamically.
2 Copyright 2021-2023 Free Software Foundation, Inc.
3
4 This file is free software: you can redistribute it and/or modify
5 it under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 2.1 of the
7 License, or (at your option) any later version.
8
9 This file 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 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
16
17 /* Written by Paul Eggert and Bruno Haible, 2021. */
18
19 #ifndef _GL_DYNARRAY_H
20 #define _GL_DYNARRAY_H
21
22 /* Before including this file, you need to define:
23
24 DYNARRAY_STRUCT
25 The struct tag of dynamic array to be defined.
26
27 DYNARRAY_ELEMENT
28 The type name of the element type. Elements are copied
29 as if by memcpy, and can change address as the dynamic
30 array grows.
31
32 DYNARRAY_PREFIX
33 The prefix of the functions which are defined.
34
35 The following parameters are optional:
36
37 DYNARRAY_ELEMENT_FREE
38 DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the
39 contents of elements. E is of type DYNARRAY_ELEMENT *.
40
41 DYNARRAY_ELEMENT_INIT
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.
47
48 DYNARRAY_INITIAL_SIZE
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.
54
55 DYNARRAY_FINAL_TYPE
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).
60
61 These macros are undefined after this header file has been
62 included.
63
64 The following types are provided (their members are private to the
65 dynarray implementation):
66
67 struct DYNARRAY_STRUCT
68
69 The following functions are provided:
70 */
71
72 /* Initialize a dynamic array object. This must be called before any
73 use of the object. */
74 #if 0
75 static void
76 DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *list);
77 #endif
78
79 /* Deallocate the dynamic array and its elements. */
80 #if 0
81 static void
82 DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *list);
83 #endif
84
85 /* Return true if the dynamic array is in an error state. */
86 #if 0
87 static bool
88 DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *list);
89 #endif
90
91 /* Mark the dynamic array as failed. All elements are deallocated as
92 a side effect. */
93 #if 0
94 static void
95 DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *list);
96 #endif
97
98 /* Return the number of elements which have been added to the dynamic
99 array. */
100 #if 0
101 static size_t
102 DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *list);
103 #endif
104
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. */
108 #if 0
109 static DYNARRAY_ELEMENT *
110 DYNARRAY_PREFIX##begin (const struct DYNARRAY_STRUCT *list);
111 #endif
112
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. */
116 #if 0
117 static DYNARRAY_ELEMENT *
118 DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUCT *list);
119 #endif
120
121 /* Return a pointer to the array element at INDEX. Terminate the
122 process if INDEX is out of bounds. */
123 #if 0
124 static DYNARRAY_ELEMENT *
125 DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *list, size_t index);
126 #endif
127
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
130 increased. */
131 #if 0
132 static void
133 DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *list,
134 DYNARRAY_ELEMENT item);
135 #endif
136
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. */
140 #if 0
141 static DYNARRAY_ELEMENT *
142 DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *list);
143 #endif
144
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). */
149 #if 0
150 static bool
151 DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *list, size_t size);
152 #endif
153
154 /* Remove the last element of LIST if it is present. */
155 #if 0
156 static void
157 DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *list);
158 #endif
159
160 /* Remove all elements from the list. The elements are freed, but the
161 list itself is not. */
162 #if 0
163 static void
164 DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *list);
165 #endif
166
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
173 free. */
174 #if 0
175 static bool
176 DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *list,
177 DYNARRAY_FINAL_TYPE *result);
178 #endif
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
186 reused. */
187 #if 0
188 static DYNARRAY_ELEMENT *
189 DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *list,
190 size_t *lengthp);
191 #endif
192 #endif
193
194 /* A minimal example which provides a growing list of integers can be
195 defined like this:
196
197 struct int_array
198 {
199 // Pointer to result array followed by its length,
200 // as required by DYNARRAY_FINAL_TYPE.
201 int *array;
202 size_t length;
203 };
204
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>
210
211 To create a three-element array with elements 1, 2, 3, use this
212 code:
213
214 struct dynarray_int dyn;
215 dynarray_int_init (&dyn);
216 for (int i = 1; i <= 3; ++i)
217 {
218 int *place = dynarray_int_emplace (&dyn);
219 assert (place != NULL);
220 *place = i;
221 }
222 struct int_array result;
223 bool ok = dynarray_int_finalize (&dyn, &result);
224 assert (ok);
225 assert (result.length == 3);
226 assert (result.array[0] == 1);
227 assert (result.array[1] == 2);
228 assert (result.array[2] == 3);
229 free (result.array);
230
231 If the elements contain resources which must be freed, define
232 DYNARRAY_ELEMENT_FREE appropriately, like this:
233
234 struct str_array
235 {
236 char **array;
237 size_t length;
238 };
239
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>
246 */
247
248
249 /* The implementation is imported from glibc. */
250
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
257
258 #if defined DYNARRAY_STRUCT || defined DYNARRAY_ELEMENT || defined DYNARRAY_PREFIX
259
260 # ifndef _GL_LIKELY
261 /* Rely on __builtin_expect, as provided by the module 'builtin-expect'. */
262 # define _GL_LIKELY(cond) __builtin_expect ((cond), 1)
263 # define _GL_UNLIKELY(cond) __builtin_expect ((cond), 0)
264 # endif
265
266 /* Define auxiliary structs and declare auxiliary functions, common to all
267 instantiations of dynarray. */
268 # include <malloc/dynarray.gl.h>
269
270 /* Define the instantiation, specified through
271 DYNARRAY_STRUCT
272 DYNARRAY_ELEMENT
273 DYNARRAY_PREFIX
274 etc. */
275 # include <malloc/dynarray-skeleton.gl.h>
276
277 #else
278
279 /* This file is being included from one of the malloc/dynarray_*.c files. */
280 # include <malloc/dynarray.h>
281
282 #endif
283
284 #endif /* _GL_DYNARRAY_H */