1 /* Type-safe arrays which grow dynamically. 2 Copyright 2021 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 */