malloc/dynarray-skeleton.c

   1 /* Type-safe arrays which grow dynamically.
   2    Copyright (C) 2017 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    <http://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##at (struct DYNARRAY_STRUCT *, size_t);
  69      void DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *, DYNARRAY_ELEMENT);
  70      DYNARRAY_ELEMENT *DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *);
  71      bool DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *, size_t);
  72      void DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *);
  73      void DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *);
  74
  75    The following functions are provided are provided if the
  76    prerequisites are met:
  77
  78      bool DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
  79                                      DYNARRAY_FINAL_TYPE *);
  80        (if DYNARRAY_FINAL_TYPE is defined)
  81      DYNARRAY_ELEMENT *DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
  82                                                   size_t *);
  83        (if DYNARRAY_FINAL_TYPE is not defined)
  84 */
  85
  86 #include <malloc/dynarray.h>
  87
  88 #include <errno.h>
  89 #include <stdlib.h>
  90 #include <string.h>
  91
  92 #ifndef DYNARRAY_STRUCT
  93 # error "DYNARRAY_STRUCT must be defined"
  94 #endif
  95
  96 #ifndef DYNARRAY_ELEMENT
  97 # error "DYNARRAY_ELEMENT must be defined"
  98 #endif
  99
 100 #ifndef DYNARRAY_PREFIX
 101 # error "DYNARRAY_PREFIX must be defined"
 102 #endif
 103
 104 #ifdef DYNARRAY_INITIAL_SIZE
 105 # if DYNARRAY_INITIAL_SIZE < 0
 106 #  error "DYNARRAY_INITIAL_SIZE must be non-negative"
 107 # endif
 108 # if DYNARRAY_INITIAL_SIZE > 0
 109 #  define DYNARRAY_HAVE_SCRATCH 1
 110 # else
 111 #  define DYNARRAY_HAVE_SCRATCH 0
 112 # endif
 113 #else
 114 /* Provide a reasonable default which limits the size of
 115    DYNARRAY_STRUCT.  */
 116 # define DYNARRAY_INITIAL_SIZE \
 117   (sizeof (DYNARRAY_ELEMENT) > 64 ? 2 : 128 / sizeof (DYNARRAY_ELEMENT))
 118 # define DYNARRAY_HAVE_SCRATCH 1
 119 #endif
 120
 121 /* Public type definitions.  */
 122
 123 /* All fields of this struct are private to the implementation.  */
 124 struct DYNARRAY_STRUCT
 125 {
 126   union
 127   {
 128     struct dynarray_header dynarray_abstract;
 129     struct
 130     {
 131       /* These fields must match struct dynarray_header.  */
 132       size_t used;
 133       size_t allocated;
 134       DYNARRAY_ELEMENT *array;
 135     } dynarray_header;
 136   };
 137
 138 #if DYNARRAY_HAVE_SCRATCH
 139   /* Initial inline allocation.  */
 140   DYNARRAY_ELEMENT scratch[DYNARRAY_INITIAL_SIZE];
 141 #endif
 142 };
 143
 144 /* Internal use only: Helper macros.  */
 145
 146 /* Ensure macro-expansion of DYNARRAY_PREFIX.  */
 147 #define DYNARRAY_CONCAT0(prefix, name) prefix##name
 148 #define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name)
 149 #define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name)
 150
 151 /* Address of the scratch buffer if any.  */
 152 #if DYNARRAY_HAVE_SCRATCH
 153 # define DYNARRAY_SCRATCH(list) (list)->scratch
 154 #else
 155 # define DYNARRAY_SCRATCH(list) NULL
 156 #endif
 157
 158 /* Internal use only: Helper functions.  */
 159
 160 /* Internal function.  Call DYNARRAY_ELEMENT_FREE with the array
 161    elements.  Name mangling needed due to the DYNARRAY_ELEMENT_FREE
 162    macro expansion.  */
 163 static inline void
 164 DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array,
 165                                   size_t __dynarray_used)
 166 {
 167 #ifdef DYNARRAY_ELEMENT_FREE
 168   for (size_t __dynarray_i = 0; __dynarray_i < __dynarray_used; ++__dynarray_i)
 169     DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]);
 170 #endif /* DYNARRAY_ELEMENT_FREE */
 171 }
 172
 173 /* Internal function.  Free the non-scratch array allocation.  */
 174 static inline void
 175 DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list)
 176 {
 177 #if DYNARRAY_HAVE_SCRATCH
 178   if (list->dynarray_header.array != list->scratch)
 179     free (list->dynarray_header.array);
 180 #else
 181   free (list->dynarray_header.array);
 182 #endif
 183 }
 184
 185 /* Public functions.  */
 186
 187 /* Initialize a dynamic array object.  This must be called before any
 188    use of the object.  */
 189 __attribute__ ((nonnull (1)))
 190 static void
 191 DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
 192 {
 193   list->dynarray_header.used = 0;
 194   list->dynarray_header.allocated = DYNARRAY_INITIAL_SIZE;
 195   list->dynarray_header.array = DYNARRAY_SCRATCH (list);
 196 }
 197
 198 /* Deallocate the dynamic array and its elements.  */
 199 __attribute__ ((unused, nonnull (1)))
 200 static void
 201 DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list)
 202 {
 203   DYNARRAY_NAME (free__elements__)
 204     (list->dynarray_header.array, list->dynarray_header.used);
 205   DYNARRAY_NAME (free__array__) (list);
 206   DYNARRAY_NAME (init) (list);
 207 }
 208
 209 /* Return true if the dynamic array is in an error state.  */
 210 __attribute__ ((nonnull (1)))
 211 static inline bool
 212 DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list)
 213 {
 214   return list->dynarray_header.allocated == __dynarray_error_marker ();
 215 }
 216
 217 /* Mark the dynamic array as failed.  All elements are deallocated as
 218    a side effect.  */
 219 __attribute__ ((nonnull (1)))
 220 static void
 221 DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list)
 222 {
 223   DYNARRAY_NAME (free__elements__)
 224     (list->dynarray_header.array, list->dynarray_header.used);
 225   DYNARRAY_NAME (free__array__) (list);
 226   list->dynarray_header.array = DYNARRAY_SCRATCH (list);
 227   list->dynarray_header.used = 0;
 228   list->dynarray_header.allocated = __dynarray_error_marker ();
 229 }
 230
 231 /* Return the number of elements which have been added to the dynamic
 232    array.  */
 233 __attribute__ ((nonnull (1)))
 234 static inline size_t
 235 DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list)
 236 {
 237   return list->dynarray_header.used;
 238 }
 239
 240 /* Return a pointer to the array element at INDEX.  Terminate the
 241    process if INDEX is out of bounds.  */
 242 __attribute__ ((nonnull (1)))
 243 static inline DYNARRAY_ELEMENT *
 244 DYNARRAY_NAME (at) (struct DYNARRAY_STRUCT *list, size_t index)
 245 {
 246   if (__glibc_unlikely (index >= DYNARRAY_NAME (size) (list)))
 247     __libc_dynarray_at_failure (DYNARRAY_NAME (size) (list), index);
 248   return list->dynarray_header.array + index;
 249 }
 250
 251 /* Internal function.  Slow path for the add function below.  */
 252 static void
 253 DYNARRAY_NAME (add__) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
 254 {
 255   if (__glibc_unlikely
 256       (!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract,
 257                                          DYNARRAY_SCRATCH (list),
 258                                          sizeof (DYNARRAY_ELEMENT))))
 259     {
 260       DYNARRAY_NAME (mark_failed) (list);
 261       return;
 262     }
 263
 264   /* Copy the new element and increase the array length.  */
 265   list->dynarray_header.array[list->dynarray_header.used++] = item;
 266 }
 267
 268 /* Add ITEM at the end of the array, enlarging it by one element.
 269    Mark *LIST as failed if the dynamic array allocation size cannot be
 270    increased.  */
 271 __attribute__ ((unused, nonnull (1)))
 272 static inline void
 273 DYNARRAY_NAME (add) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
 274 {
 275   /* Do nothing in case of previous error.  */
 276   if (DYNARRAY_NAME (has_failed) (list))
 277     return;
 278
 279   /* Enlarge the array if necessary.  */
 280   if (__glibc_unlikely (list->dynarray_header.used
 281                         == list->dynarray_header.allocated))
 282     {
 283       DYNARRAY_NAME (add__) (list, item);
 284       return;
 285     }
 286
 287   /* Copy the new element and increase the array length.  */
 288   list->dynarray_header.array[list->dynarray_header.used++] = item;
 289 }
 290
 291 /* Internal function.  Building block for the emplace functions below.
 292    Assumes space for one more element in *LIST.  */
 293 static inline DYNARRAY_ELEMENT *
 294 DYNARRAY_NAME (emplace__tail__) (struct DYNARRAY_STRUCT *list)
 295 {
 296   DYNARRAY_ELEMENT *result
 297     = &list->dynarray_header.array[list->dynarray_header.used];
 298   ++list->dynarray_header.used;
 299 #if defined (DYNARRAY_ELEMENT_INIT)
 300   DYNARRAY_ELEMENT_INIT (result);
 301 #elif defined (DYNARRAY_ELEMENT_FREE)
 302   memset (result, 0, sizeof (*result));
 303 #endif
 304   return result;
 305 }
 306
 307 /* Internal function.  Slow path for the emplace function below.  */
 308 static DYNARRAY_ELEMENT *
 309 DYNARRAY_NAME (emplace__) (struct DYNARRAY_STRUCT *list)
 310 {
 311   if (__glibc_unlikely
 312       (!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract,
 313                                          DYNARRAY_SCRATCH (list),
 314                                          sizeof (DYNARRAY_ELEMENT))))
 315     {
 316       DYNARRAY_NAME (mark_failed) (list);
 317       return NULL;
 318     }
 319   return DYNARRAY_NAME (emplace__tail__) (list);
 320 }
 321
 322 /* Allocate a place for a new element in *LIST and return a pointer to
 323    it.  The pointer can be NULL if the dynamic array cannot be
 324    enlarged due to a memory allocation failure.  */
 325 __attribute__ ((unused, warn_unused_result, nonnull (1)))
 326 static
 327 /* Avoid inlining with the larger initialization code.  */
 328 #if !(defined (DYNARRAY_ELEMENT_INIT) || defined (DYNARRAY_ELEMENT_FREE))
 329 inline
 330 #endif
 331 DYNARRAY_ELEMENT *
 332 DYNARRAY_NAME (emplace) (struct DYNARRAY_STRUCT *list)
 333 {
 334   /* Do nothing in case of previous error.  */
 335   if (DYNARRAY_NAME (has_failed) (list))
 336     return NULL;
 337
 338   /* Enlarge the array if necessary.  */
 339   if (__glibc_unlikely (list->dynarray_header.used
 340                         == list->dynarray_header.allocated))
 341     return (DYNARRAY_NAME (emplace__) (list));
 342   return DYNARRAY_NAME (emplace__tail__) (list);
 343 }
 344
 345 /* Change the size of *LIST to SIZE.  If SIZE is larger than the
 346    existing size, new elements are added (which can be initialized).
 347    Otherwise, the list is truncated, and elements are freed.  Return
 348    false on memory allocation failure (and mark *LIST as failed).  */
 349 __attribute__ ((unused, nonnull (1)))
 350 static bool
 351 DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size)
 352 {
 353   if (size > list->dynarray_header.used)
 354     {
 355       bool ok;
 356 #if defined (DYNARRAY_ELEMENT_INIT)
 357       /* The new elements have to be initialized.  */
 358       size_t old_size = list->dynarray_header.used;
 359       ok = __libc_dynarray_resize (&list->dynarray_abstract,
 360                                    size, DYNARRAY_SCRATCH (list),
 361                                    sizeof (DYNARRAY_ELEMENT));
 362       if (ok)
 363         for (size_t i = old_size; i < size; ++i)
 364           {
 365             DYNARRAY_ELEMENT_INIT (&list->dynarray_header.array[i]);
 366           }
 367 #elif defined (DYNARRAY_ELEMENT_FREE)
 368       /* Zero initialization is needed so that the elements can be
 369          safely freed.  */
 370       ok = __libc_dynarray_resize_clear
 371         (&list->dynarray_abstract, size,
 372          DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT));
 373 #else
 374       ok =  __libc_dynarray_resize (&list->dynarray_abstract,
 375                                     size, DYNARRAY_SCRATCH (list),
 376                                     sizeof (DYNARRAY_ELEMENT));
 377 #endif
 378       if (__glibc_unlikely (!ok))
 379         DYNARRAY_NAME (mark_failed) (list);
 380       return ok;
 381     }
 382   else
 383     {
 384       /* The list has shrunk in size.  Free the removed elements.  */
 385       DYNARRAY_NAME (free__elements__)
 386         (list->dynarray_header.array + size,
 387          list->dynarray_header.used - size);
 388       list->dynarray_header.used = size;
 389       return true;
 390     }
 391 }
 392
 393 /* Remove the last element of LIST if it is present.  */
 394 __attribute__ ((unused, nonnull (1)))
 395 static void
 396 DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
 397 {
 398   /* used > 0 implies that the array is the non-failed state.  */
 399   if (list->dynarray_header.used > 0)
 400     {
 401       size_t new_length = list->dynarray_header.used - 1;
 402 #ifdef DYNARRAY_ELEMENT_FREE
 403       DYNARRAY_ELEMENT_FREE (&list->dynarray_header.array[new_length]);
 404 #endif
 405       list->dynarray_header.used = new_length;
 406     }
 407 }
 408
 409 /* Remove all elements from the list.  The elements are freed, but the
 410    list itself is not.  */
 411 __attribute__ ((unused, nonnull (1)))
 412 static void
 413 DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list)
 414 {
 415   /* free__elements__ does nothing if the list is in the failed
 416      state.  */
 417   DYNARRAY_NAME (free__elements__)
 418     (list->dynarray_header.array, list->dynarray_header.used);
 419   list->dynarray_header.used = 0;
 420 }
 421
 422 #ifdef DYNARRAY_FINAL_TYPE
 423 /* Transfer the dynamic array to a permanent location at *RESULT.
 424    Returns true on success on false on allocation failure.  In either
 425    case, *LIST is re-initialized and can be reused.  A NULL pointer is
 426    stored in *RESULT if LIST refers to an empty list.  On success, the
 427    pointer in *RESULT is heap-allocated and must be deallocated using
 428    free.  */
 429 __attribute__ ((unused, warn_unused_result, nonnull (1, 2)))
 430 static bool
 431 DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list,
 432                           DYNARRAY_FINAL_TYPE *result)
 433 {
 434   struct dynarray_finalize_result res;
 435   if (__libc_dynarray_finalize (&list->dynarray_abstract,
 436                                 DYNARRAY_SCRATCH (list),
 437                                 sizeof (DYNARRAY_ELEMENT), &res))
 438     {
 439       /* On success, the result owns all the data.  */
 440       DYNARRAY_NAME (init) (list);
 441       *result = (DYNARRAY_FINAL_TYPE) { res.array, res.length };
 442       return true;
 443     }
 444   else
 445     {
 446       /* On error, we need to free all data.  */
 447       DYNARRAY_NAME (free) (list);
 448       errno = ENOMEM;
 449       return false;
 450     }
 451 }
 452 #else /* !DYNARRAY_FINAL_TYPE */
 453 /* Transfer the dynamic array to a heap-allocated array and return a
 454    pointer to it.  The pointer is NULL if memory allocation fails, or
 455    if the array is empty, so this function should be used only for
 456    arrays which are known not be empty (usually because they always
 457    have a sentinel at the end).  If LENGTHP is not NULL, the array
 458    length is written to *LENGTHP.  *LIST is re-initialized and can be
 459    reused.  */
 460 __attribute__ ((unused, warn_unused_result, nonnull (1)))
 461 static DYNARRAY_ELEMENT *
 462 DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)
 463 {
 464   struct dynarray_finalize_result res;
 465   if (__libc_dynarray_finalize (&list->dynarray_abstract,
 466                                 DYNARRAY_SCRATCH (list),
 467                                 sizeof (DYNARRAY_ELEMENT), &res))
 468     {
 469       /* On success, the result owns all the data.  */
 470       DYNARRAY_NAME (init) (list);
 471       if (lengthp != NULL)
 472         *lengthp = res.length;
 473       return res.array;
 474     }
 475   else
 476     {
 477       /* On error, we need to free all data.  */
 478       DYNARRAY_NAME (free) (list);
 479       errno = ENOMEM;
 480       return NULL;
 481     }
 482 }
 483 #endif /* !DYNARRAY_FINAL_TYPE */
 484
 485 /* Undo macro definitions.  */
 486
 487 #undef DYNARRAY_CONCAT0
 488 #undef DYNARRAY_CONCAT1
 489 #undef DYNARRAY_NAME
 490 #undef DYNARRAY_SCRATCH
 491 #undef DYNARRAY_HAVE_SCRATCH
 492
 493 #undef DYNARRAY_STRUCT
 494 #undef DYNARRAY_ELEMENT
 495 #undef DYNARRAY_PREFIX
 496 #undef DYNARRAY_ELEMENT_FREE
 497 #undef DYNARRAY_ELEMENT_INIT
 498 #undef DYNARRAY_INITIAL_SIZE
 499 #undef DYNARRAY_FINAL_TYPE