lib/dynarray.h

   1 /* Type-safe arrays which grow dynamically.
   2    Copyright 2021 Free Software Foundation, Inc.
   3
   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.
   8
   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.
  13
  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/>.  */
  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 # include <libc-config.h>
 261
 262 /* Define auxiliary structs and declare auxiliary functions, common to all
 263    instantiations of dynarray.  */
 264 # include <malloc/dynarray.h>
 265
 266 /* Define the instantiation, specified through
 267      DYNARRAY_STRUCT
 268      DYNARRAY_ELEMENT
 269      DYNARRAY_PREFIX
 270    etc.  */
 271 # include <malloc/dynarray-skeleton.c>
 272
 273 #else
 274
 275 /* This file is being included from one of the malloc/dynarray_*.c files.  */
 276 # include <malloc/dynarray.h>
 277
 278 #endif
 279
 280 #endif /* _GL_DYNARRAY_H */