| 1 | /* Type-safe arrays which grow dynamically.
|
|---|
| 2 | Copyright (C) 2017-2021 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. */
|
|---|
| 126 | struct 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 | } u;
|
|---|
| 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 | /* Use DYNARRAY_FREE instead of DYNARRAY_NAME (free),
|
|---|
| 154 | so that Gnulib does not change 'free' to 'rpl_free'. */
|
|---|
| 155 | #define DYNARRAY_FREE DYNARRAY_CONCAT1 (DYNARRAY_NAME (f), ree)
|
|---|
| 156 |
|
|---|
| 157 | /* Address of the scratch buffer if any. */
|
|---|
| 158 | #if DYNARRAY_HAVE_SCRATCH
|
|---|
| 159 | # define DYNARRAY_SCRATCH(list) (list)->scratch
|
|---|
| 160 | #else
|
|---|
| 161 | # define DYNARRAY_SCRATCH(list) NULL
|
|---|
| 162 | #endif
|
|---|
| 163 |
|
|---|
| 164 | /* Internal use only: Helper functions. */
|
|---|
| 165 |
|
|---|
| 166 | /* Internal function. Call DYNARRAY_ELEMENT_FREE with the array
|
|---|
| 167 | elements. Name mangling needed due to the DYNARRAY_ELEMENT_FREE
|
|---|
| 168 | macro expansion. */
|
|---|
| 169 | static inline void
|
|---|
| 170 | DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array,
|
|---|
| 171 | size_t __dynarray_used)
|
|---|
| 172 | {
|
|---|
| 173 | #ifdef DYNARRAY_ELEMENT_FREE
|
|---|
| 174 | for (size_t __dynarray_i = 0; __dynarray_i < __dynarray_used; ++__dynarray_i)
|
|---|
| 175 | DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]);
|
|---|
| 176 | #endif /* DYNARRAY_ELEMENT_FREE */
|
|---|
| 177 | }
|
|---|
| 178 |
|
|---|
| 179 | /* Internal function. Free the non-scratch array allocation. */
|
|---|
| 180 | static inline void
|
|---|
| 181 | DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list)
|
|---|
| 182 | {
|
|---|
| 183 | #if DYNARRAY_HAVE_SCRATCH
|
|---|
| 184 | if (list->u.dynarray_header.array != list->scratch)
|
|---|
| 185 | free (list->u.dynarray_header.array);
|
|---|
| 186 | #else
|
|---|
| 187 | free (list->u.dynarray_header.array);
|
|---|
| 188 | #endif
|
|---|
| 189 | }
|
|---|
| 190 |
|
|---|
| 191 | /* Public functions. */
|
|---|
| 192 |
|
|---|
| 193 | /* Initialize a dynamic array object. This must be called before any
|
|---|
| 194 | use of the object. */
|
|---|
| 195 | __attribute_nonnull__ ((1))
|
|---|
| 196 | static void
|
|---|
| 197 | DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
|
|---|
| 198 | {
|
|---|
| 199 | list->u.dynarray_header.used = 0;
|
|---|
| 200 | list->u.dynarray_header.allocated = DYNARRAY_INITIAL_SIZE;
|
|---|
| 201 | list->u.dynarray_header.array = DYNARRAY_SCRATCH (list);
|
|---|
| 202 | }
|
|---|
| 203 |
|
|---|
| 204 | /* Deallocate the dynamic array and its elements. */
|
|---|
| 205 | __attribute_maybe_unused__ __attribute_nonnull__ ((1))
|
|---|
| 206 | static void
|
|---|
| 207 | DYNARRAY_FREE (struct DYNARRAY_STRUCT *list)
|
|---|
| 208 | {
|
|---|
| 209 | DYNARRAY_NAME (free__elements__)
|
|---|
| 210 | (list->u.dynarray_header.array, list->u.dynarray_header.used);
|
|---|
| 211 | DYNARRAY_NAME (free__array__) (list);
|
|---|
| 212 | DYNARRAY_NAME (init) (list);
|
|---|
| 213 | }
|
|---|
| 214 |
|
|---|
| 215 | /* Return true if the dynamic array is in an error state. */
|
|---|
| 216 | __attribute_nonnull__ ((1))
|
|---|
| 217 | static inline bool
|
|---|
| 218 | DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list)
|
|---|
| 219 | {
|
|---|
| 220 | return list->u.dynarray_header.allocated == __dynarray_error_marker ();
|
|---|
| 221 | }
|
|---|
| 222 |
|
|---|
| 223 | /* Mark the dynamic array as failed. All elements are deallocated as
|
|---|
| 224 | a side effect. */
|
|---|
| 225 | __attribute_nonnull__ ((1))
|
|---|
| 226 | static void
|
|---|
| 227 | DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list)
|
|---|
| 228 | {
|
|---|
| 229 | DYNARRAY_NAME (free__elements__)
|
|---|
| 230 | (list->u.dynarray_header.array, list->u.dynarray_header.used);
|
|---|
| 231 | DYNARRAY_NAME (free__array__) (list);
|
|---|
| 232 | list->u.dynarray_header.array = DYNARRAY_SCRATCH (list);
|
|---|
| 233 | list->u.dynarray_header.used = 0;
|
|---|
| 234 | list->u.dynarray_header.allocated = __dynarray_error_marker ();
|
|---|
| 235 | }
|
|---|
| 236 |
|
|---|
| 237 | /* Return the number of elements which have been added to the dynamic
|
|---|
| 238 | array. */
|
|---|
| 239 | __attribute_nonnull__ ((1))
|
|---|
| 240 | static inline size_t
|
|---|
| 241 | DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list)
|
|---|
| 242 | {
|
|---|
| 243 | return list->u.dynarray_header.used;
|
|---|
| 244 | }
|
|---|
| 245 |
|
|---|
| 246 | /* Return a pointer to the array element at INDEX. Terminate the
|
|---|
| 247 | process if INDEX is out of bounds. */
|
|---|
| 248 | __attribute_nonnull__ ((1))
|
|---|
| 249 | static inline DYNARRAY_ELEMENT *
|
|---|
| 250 | DYNARRAY_NAME (at) (struct DYNARRAY_STRUCT *list, size_t index)
|
|---|
| 251 | {
|
|---|
| 252 | if (__glibc_unlikely (index >= DYNARRAY_NAME (size) (list)))
|
|---|
| 253 | __libc_dynarray_at_failure (DYNARRAY_NAME (size) (list), index);
|
|---|
| 254 | return list->u.dynarray_header.array + index;
|
|---|
| 255 | }
|
|---|
| 256 |
|
|---|
| 257 | /* Return a pointer to the first array element, if any. For a
|
|---|
| 258 | zero-length array, the pointer can be NULL even though the dynamic
|
|---|
| 259 | array has not entered the failure state. */
|
|---|
| 260 | __attribute_nonnull__ ((1))
|
|---|
| 261 | static inline DYNARRAY_ELEMENT *
|
|---|
| 262 | DYNARRAY_NAME (begin) (struct DYNARRAY_STRUCT *list)
|
|---|
| 263 | {
|
|---|
| 264 | return list->u.dynarray_header.array;
|
|---|
| 265 | }
|
|---|
| 266 |
|
|---|
| 267 | /* Return a pointer one element past the last array element. For a
|
|---|
| 268 | zero-length array, the pointer can be NULL even though the dynamic
|
|---|
| 269 | array has not entered the failure state. */
|
|---|
| 270 | __attribute_nonnull__ ((1))
|
|---|
| 271 | static inline DYNARRAY_ELEMENT *
|
|---|
| 272 | DYNARRAY_NAME (end) (struct DYNARRAY_STRUCT *list)
|
|---|
| 273 | {
|
|---|
| 274 | return list->u.dynarray_header.array + list->u.dynarray_header.used;
|
|---|
| 275 | }
|
|---|
| 276 |
|
|---|
| 277 | /* Internal function. Slow path for the add function below. */
|
|---|
| 278 | static void
|
|---|
| 279 | DYNARRAY_NAME (add__) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
|
|---|
| 280 | {
|
|---|
| 281 | if (__glibc_unlikely
|
|---|
| 282 | (!__libc_dynarray_emplace_enlarge (&list->u.dynarray_abstract,
|
|---|
| 283 | DYNARRAY_SCRATCH (list),
|
|---|
| 284 | sizeof (DYNARRAY_ELEMENT))))
|
|---|
| 285 | {
|
|---|
| 286 | DYNARRAY_NAME (mark_failed) (list);
|
|---|
| 287 | return;
|
|---|
| 288 | }
|
|---|
| 289 |
|
|---|
| 290 | /* Copy the new element and increase the array length. */
|
|---|
| 291 | list->u.dynarray_header.array[list->u.dynarray_header.used++] = item;
|
|---|
| 292 | }
|
|---|
| 293 |
|
|---|
| 294 | /* Add ITEM at the end of the array, enlarging it by one element.
|
|---|
| 295 | Mark *LIST as failed if the dynamic array allocation size cannot be
|
|---|
| 296 | increased. */
|
|---|
| 297 | __attribute_nonnull__ ((1))
|
|---|
| 298 | static inline void
|
|---|
| 299 | DYNARRAY_NAME (add) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
|
|---|
| 300 | {
|
|---|
| 301 | /* Do nothing in case of previous error. */
|
|---|
| 302 | if (DYNARRAY_NAME (has_failed) (list))
|
|---|
| 303 | return;
|
|---|
| 304 |
|
|---|
| 305 | /* Enlarge the array if necessary. */
|
|---|
| 306 | if (__glibc_unlikely (list->u.dynarray_header.used
|
|---|
| 307 | == list->u.dynarray_header.allocated))
|
|---|
| 308 | {
|
|---|
| 309 | DYNARRAY_NAME (add__) (list, item);
|
|---|
| 310 | return;
|
|---|
| 311 | }
|
|---|
| 312 |
|
|---|
| 313 | /* Copy the new element and increase the array length. */
|
|---|
| 314 | list->u.dynarray_header.array[list->u.dynarray_header.used++] = item;
|
|---|
| 315 | }
|
|---|
| 316 |
|
|---|
| 317 | /* Internal function. Building block for the emplace functions below.
|
|---|
| 318 | Assumes space for one more element in *LIST. */
|
|---|
| 319 | static inline DYNARRAY_ELEMENT *
|
|---|
| 320 | DYNARRAY_NAME (emplace__tail__) (struct DYNARRAY_STRUCT *list)
|
|---|
| 321 | {
|
|---|
| 322 | DYNARRAY_ELEMENT *result
|
|---|
| 323 | = &list->u.dynarray_header.array[list->u.dynarray_header.used];
|
|---|
| 324 | ++list->u.dynarray_header.used;
|
|---|
| 325 | #if defined (DYNARRAY_ELEMENT_INIT)
|
|---|
| 326 | DYNARRAY_ELEMENT_INIT (result);
|
|---|
| 327 | #elif defined (DYNARRAY_ELEMENT_FREE)
|
|---|
| 328 | memset (result, 0, sizeof (*result));
|
|---|
| 329 | #endif
|
|---|
| 330 | return result;
|
|---|
| 331 | }
|
|---|
| 332 |
|
|---|
| 333 | /* Internal function. Slow path for the emplace function below. */
|
|---|
| 334 | static DYNARRAY_ELEMENT *
|
|---|
| 335 | DYNARRAY_NAME (emplace__) (struct DYNARRAY_STRUCT *list)
|
|---|
| 336 | {
|
|---|
| 337 | if (__glibc_unlikely
|
|---|
| 338 | (!__libc_dynarray_emplace_enlarge (&list->u.dynarray_abstract,
|
|---|
| 339 | DYNARRAY_SCRATCH (list),
|
|---|
| 340 | sizeof (DYNARRAY_ELEMENT))))
|
|---|
| 341 | {
|
|---|
| 342 | DYNARRAY_NAME (mark_failed) (list);
|
|---|
| 343 | return NULL;
|
|---|
| 344 | }
|
|---|
| 345 | return DYNARRAY_NAME (emplace__tail__) (list);
|
|---|
| 346 | }
|
|---|
| 347 |
|
|---|
| 348 | /* Allocate a place for a new element in *LIST and return a pointer to
|
|---|
| 349 | it. The pointer can be NULL if the dynamic array cannot be
|
|---|
| 350 | enlarged due to a memory allocation failure. */
|
|---|
| 351 | __attribute_maybe_unused__ __attribute_warn_unused_result__
|
|---|
| 352 | __attribute_nonnull__ ((1))
|
|---|
| 353 | static
|
|---|
| 354 | /* Avoid inlining with the larger initialization code. */
|
|---|
| 355 | #if !(defined (DYNARRAY_ELEMENT_INIT) || defined (DYNARRAY_ELEMENT_FREE))
|
|---|
| 356 | inline
|
|---|
| 357 | #endif
|
|---|
| 358 | DYNARRAY_ELEMENT *
|
|---|
| 359 | DYNARRAY_NAME (emplace) (struct DYNARRAY_STRUCT *list)
|
|---|
| 360 | {
|
|---|
| 361 | /* Do nothing in case of previous error. */
|
|---|
| 362 | if (DYNARRAY_NAME (has_failed) (list))
|
|---|
| 363 | return NULL;
|
|---|
| 364 |
|
|---|
| 365 | /* Enlarge the array if necessary. */
|
|---|
| 366 | if (__glibc_unlikely (list->u.dynarray_header.used
|
|---|
| 367 | == list->u.dynarray_header.allocated))
|
|---|
| 368 | return (DYNARRAY_NAME (emplace__) (list));
|
|---|
| 369 | return DYNARRAY_NAME (emplace__tail__) (list);
|
|---|
| 370 | }
|
|---|
| 371 |
|
|---|
| 372 | /* Change the size of *LIST to SIZE. If SIZE is larger than the
|
|---|
| 373 | existing size, new elements are added (which can be initialized).
|
|---|
| 374 | Otherwise, the list is truncated, and elements are freed. Return
|
|---|
| 375 | false on memory allocation failure (and mark *LIST as failed). */
|
|---|
| 376 | __attribute_maybe_unused__ __attribute_nonnull__ ((1))
|
|---|
| 377 | static bool
|
|---|
| 378 | DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size)
|
|---|
| 379 | {
|
|---|
| 380 | if (size > list->u.dynarray_header.used)
|
|---|
| 381 | {
|
|---|
| 382 | bool ok;
|
|---|
| 383 | #if defined (DYNARRAY_ELEMENT_INIT)
|
|---|
| 384 | /* The new elements have to be initialized. */
|
|---|
| 385 | size_t old_size = list->u.dynarray_header.used;
|
|---|
| 386 | ok = __libc_dynarray_resize (&list->u.dynarray_abstract,
|
|---|
| 387 | size, DYNARRAY_SCRATCH (list),
|
|---|
| 388 | sizeof (DYNARRAY_ELEMENT));
|
|---|
| 389 | if (ok)
|
|---|
| 390 | for (size_t i = old_size; i < size; ++i)
|
|---|
| 391 | {
|
|---|
| 392 | DYNARRAY_ELEMENT_INIT (&list->u.dynarray_header.array[i]);
|
|---|
| 393 | }
|
|---|
| 394 | #elif defined (DYNARRAY_ELEMENT_FREE)
|
|---|
| 395 | /* Zero initialization is needed so that the elements can be
|
|---|
| 396 | safely freed. */
|
|---|
| 397 | ok = __libc_dynarray_resize_clear
|
|---|
| 398 | (&list->u.dynarray_abstract, size,
|
|---|
| 399 | DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT));
|
|---|
| 400 | #else
|
|---|
| 401 | ok = __libc_dynarray_resize (&list->u.dynarray_abstract,
|
|---|
| 402 | size, DYNARRAY_SCRATCH (list),
|
|---|
| 403 | sizeof (DYNARRAY_ELEMENT));
|
|---|
| 404 | #endif
|
|---|
| 405 | if (__glibc_unlikely (!ok))
|
|---|
| 406 | DYNARRAY_NAME (mark_failed) (list);
|
|---|
| 407 | return ok;
|
|---|
| 408 | }
|
|---|
| 409 | else
|
|---|
| 410 | {
|
|---|
| 411 | /* The list has shrunk in size. Free the removed elements. */
|
|---|
| 412 | DYNARRAY_NAME (free__elements__)
|
|---|
| 413 | (list->u.dynarray_header.array + size,
|
|---|
| 414 | list->u.dynarray_header.used - size);
|
|---|
| 415 | list->u.dynarray_header.used = size;
|
|---|
| 416 | return true;
|
|---|
| 417 | }
|
|---|
| 418 | }
|
|---|
| 419 |
|
|---|
| 420 | /* Remove the last element of LIST if it is present. */
|
|---|
| 421 | __attribute_maybe_unused__ __attribute_nonnull__ ((1))
|
|---|
| 422 | static void
|
|---|
| 423 | DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
|
|---|
| 424 | {
|
|---|
| 425 | /* used > 0 implies that the array is the non-failed state. */
|
|---|
| 426 | if (list->u.dynarray_header.used > 0)
|
|---|
| 427 | {
|
|---|
| 428 | size_t new_length = list->u.dynarray_header.used - 1;
|
|---|
| 429 | #ifdef DYNARRAY_ELEMENT_FREE
|
|---|
| 430 | DYNARRAY_ELEMENT_FREE (&list->u.dynarray_header.array[new_length]);
|
|---|
| 431 | #endif
|
|---|
| 432 | list->u.dynarray_header.used = new_length;
|
|---|
| 433 | }
|
|---|
| 434 | }
|
|---|
| 435 |
|
|---|
| 436 | /* Remove all elements from the list. The elements are freed, but the
|
|---|
| 437 | list itself is not. */
|
|---|
| 438 | __attribute_maybe_unused__ __attribute_nonnull__ ((1))
|
|---|
| 439 | static void
|
|---|
| 440 | DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list)
|
|---|
| 441 | {
|
|---|
| 442 | /* free__elements__ does nothing if the list is in the failed
|
|---|
| 443 | state. */
|
|---|
| 444 | DYNARRAY_NAME (free__elements__)
|
|---|
| 445 | (list->u.dynarray_header.array, list->u.dynarray_header.used);
|
|---|
| 446 | list->u.dynarray_header.used = 0;
|
|---|
| 447 | }
|
|---|
| 448 |
|
|---|
| 449 | #ifdef DYNARRAY_FINAL_TYPE
|
|---|
| 450 | /* Transfer the dynamic array to a permanent location at *RESULT.
|
|---|
| 451 | Returns true on success on false on allocation failure. In either
|
|---|
| 452 | case, *LIST is re-initialized and can be reused. A NULL pointer is
|
|---|
| 453 | stored in *RESULT if LIST refers to an empty list. On success, the
|
|---|
| 454 | pointer in *RESULT is heap-allocated and must be deallocated using
|
|---|
| 455 | free. */
|
|---|
| 456 | __attribute_maybe_unused__ __attribute_warn_unused_result__
|
|---|
| 457 | __attribute_nonnull__ ((1, 2))
|
|---|
| 458 | static bool
|
|---|
| 459 | DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list,
|
|---|
| 460 | DYNARRAY_FINAL_TYPE *result)
|
|---|
| 461 | {
|
|---|
| 462 | struct dynarray_finalize_result res;
|
|---|
| 463 | if (__libc_dynarray_finalize (&list->u.dynarray_abstract,
|
|---|
| 464 | DYNARRAY_SCRATCH (list),
|
|---|
| 465 | sizeof (DYNARRAY_ELEMENT), &res))
|
|---|
| 466 | {
|
|---|
| 467 | /* On success, the result owns all the data. */
|
|---|
| 468 | DYNARRAY_NAME (init) (list);
|
|---|
| 469 | *result = (DYNARRAY_FINAL_TYPE) { res.array, res.length };
|
|---|
| 470 | return true;
|
|---|
| 471 | }
|
|---|
| 472 | else
|
|---|
| 473 | {
|
|---|
| 474 | /* On error, we need to free all data. */
|
|---|
| 475 | DYNARRAY_FREE (list);
|
|---|
| 476 | errno = ENOMEM;
|
|---|
| 477 | return false;
|
|---|
| 478 | }
|
|---|
| 479 | }
|
|---|
| 480 | #else /* !DYNARRAY_FINAL_TYPE */
|
|---|
| 481 | /* Transfer the dynamic array to a heap-allocated array and return a
|
|---|
| 482 | pointer to it. The pointer is NULL if memory allocation fails, or
|
|---|
| 483 | if the array is empty, so this function should be used only for
|
|---|
| 484 | arrays which are known not be empty (usually because they always
|
|---|
| 485 | have a sentinel at the end). If LENGTHP is not NULL, the array
|
|---|
| 486 | length is written to *LENGTHP. *LIST is re-initialized and can be
|
|---|
| 487 | reused. */
|
|---|
| 488 | __attribute_maybe_unused__ __attribute_warn_unused_result__
|
|---|
| 489 | __attribute_nonnull__ ((1))
|
|---|
| 490 | static DYNARRAY_ELEMENT *
|
|---|
| 491 | DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)
|
|---|
| 492 | {
|
|---|
| 493 | struct dynarray_finalize_result res;
|
|---|
| 494 | if (__libc_dynarray_finalize (&list->u.dynarray_abstract,
|
|---|
| 495 | DYNARRAY_SCRATCH (list),
|
|---|
| 496 | sizeof (DYNARRAY_ELEMENT), &res))
|
|---|
| 497 | {
|
|---|
| 498 | /* On success, the result owns all the data. */
|
|---|
| 499 | DYNARRAY_NAME (init) (list);
|
|---|
| 500 | if (lengthp != NULL)
|
|---|
| 501 | *lengthp = res.length;
|
|---|
| 502 | return res.array;
|
|---|
| 503 | }
|
|---|
| 504 | else
|
|---|
| 505 | {
|
|---|
| 506 | /* On error, we need to free all data. */
|
|---|
| 507 | DYNARRAY_FREE (list);
|
|---|
| 508 | errno = ENOMEM;
|
|---|
| 509 | return NULL;
|
|---|
| 510 | }
|
|---|
| 511 | }
|
|---|
| 512 | #endif /* !DYNARRAY_FINAL_TYPE */
|
|---|
| 513 |
|
|---|
| 514 | /* Undo macro definitions. */
|
|---|
| 515 |
|
|---|
| 516 | #undef DYNARRAY_CONCAT0
|
|---|
| 517 | #undef DYNARRAY_CONCAT1
|
|---|
| 518 | #undef DYNARRAY_NAME
|
|---|
| 519 | #undef DYNARRAY_SCRATCH
|
|---|
| 520 | #undef DYNARRAY_HAVE_SCRATCH
|
|---|
| 521 |
|
|---|
| 522 | #undef DYNARRAY_STRUCT
|
|---|
| 523 | #undef DYNARRAY_ELEMENT
|
|---|
| 524 | #undef DYNARRAY_PREFIX
|
|---|
| 525 | #undef DYNARRAY_ELEMENT_FREE
|
|---|
| 526 | #undef DYNARRAY_ELEMENT_INIT
|
|---|
| 527 | #undef DYNARRAY_INITIAL_SIZE
|
|---|
| 528 | #undef DYNARRAY_FINAL_TYPE
|
|---|