lib/arraylist.h

   1 /* Auto-reallocating array for arbitrary member types. */
   2 /*
   3  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* Usage:
  19  *
  20  * ARRAYLIST(any_type_t) list;
  21  * // OR
  22  * typedef ARRAYLIST(any_type_t) any_type_list_t;
  23  * any_type_list_t list;
  24  *
  25  * // pass the number of (at first unused) members to add on each realloc:
  26  * ARRAYLIST_INIT(list, 128);
  27  * any_type_t *x;
  28  * while (bar) {
  29  *         // This enlarges the allocated array as needed;
  30  *         // list.head may change due to realloc:
  31  *         ARRAYLIST_ADD(x, list);
  32  *         if (!x)
  33  *                 return ENOMEM;
  34  *         *x = random_foo_value;
  35  * }
  36  * for (i = 0; i < list.len; i++)
  37  *         printf("%s", foo_to_str(list.head[i]));
  38  * ARRAYLIST_FREE(list);
  39  */
  40
  41 #include "got_compat.h"
  42
  43 #define ARRAYLIST(MEMBER_TYPE) \
  44         struct { \
  45                 MEMBER_TYPE *head; \
  46                 MEMBER_TYPE *p; \
  47                 unsigned int len; \
  48                 unsigned int allocated; \
  49                 unsigned int alloc_blocksize; \
  50         }
  51
  52 #define ARRAYLIST_INIT(ARRAY_LIST, ALLOC_BLOCKSIZE) do { \
  53                 (ARRAY_LIST).head = NULL; \
  54                 (ARRAY_LIST).len = 0; \
  55                 (ARRAY_LIST).allocated = 0; \
  56                 (ARRAY_LIST).alloc_blocksize = ALLOC_BLOCKSIZE; \
  57         } while(0)
  58
  59 #define ARRAYLIST_ADD(NEW_ITEM_P, ARRAY_LIST) do { \
  60                 if ((ARRAY_LIST).len && !(ARRAY_LIST).allocated) { \
  61                         NEW_ITEM_P = NULL; \
  62                         break; \
  63                 } \
  64                 if ((ARRAY_LIST).head == NULL \
  65                     || (ARRAY_LIST).allocated < (ARRAY_LIST).len + 1) { \
  66                         (ARRAY_LIST).p = recallocarray((ARRAY_LIST).head, \
  67                                 (ARRAY_LIST).len, \
  68                                 (ARRAY_LIST).allocated + \
  69                                 ((ARRAY_LIST).allocated ? \
  70                                 (ARRAY_LIST).allocated / 2 : \
  71                                 (ARRAY_LIST).alloc_blocksize ? \
  72                                 (ARRAY_LIST).alloc_blocksize : 8), \
  73                                 sizeof(*(ARRAY_LIST).head)); \
  74                         if ((ARRAY_LIST).p == NULL) { \
  75                                 NEW_ITEM_P = NULL; \
  76                                 break; \
  77                         } \
  78                         (ARRAY_LIST).allocated += \
  79                                 (ARRAY_LIST).allocated ? \
  80                                 (ARRAY_LIST).allocated / 2 : \
  81                                 (ARRAY_LIST).alloc_blocksize ? \
  82                                 (ARRAY_LIST).alloc_blocksize : 8, \
  83                         (ARRAY_LIST).head = (ARRAY_LIST).p; \
  84                         (ARRAY_LIST).p = NULL; \
  85                 }; \
  86                 if ((ARRAY_LIST).head == NULL \
  87                     || (ARRAY_LIST).allocated < (ARRAY_LIST).len + 1) { \
  88                         NEW_ITEM_P = NULL; \
  89                         break; \
  90                 } \
  91                 (NEW_ITEM_P) = &(ARRAY_LIST).head[(ARRAY_LIST).len]; \
  92                 (ARRAY_LIST).len++; \
  93         } while (0)
  94
  95 #define ARRAYLIST_INSERT(NEW_ITEM_P, ARRAY_LIST, AT_IDX) do { \
  96                 int _at_idx = (AT_IDX); \
  97                 ARRAYLIST_ADD(NEW_ITEM_P, ARRAY_LIST); \
  98                 if ((NEW_ITEM_P) \
  99                     && _at_idx >= 0 \
 100                     && _at_idx < (ARRAY_LIST).len) { \
 101                         memmove(&(ARRAY_LIST).head[_at_idx + 1], \
 102                                 &(ARRAY_LIST).head[_at_idx], \
 103                                 ((ARRAY_LIST).len - 1 - _at_idx) \
 104                                         * sizeof(*(ARRAY_LIST).head)); \
 105                         (NEW_ITEM_P) = &(ARRAY_LIST).head[_at_idx]; \
 106                 }; \
 107         } while (0)
 108
 109 #define ARRAYLIST_CLEAR(ARRAY_LIST) \
 110         (ARRAY_LIST).len = 0
 111
 112 #define ARRAYLIST_FREE(ARRAY_LIST) \
 113         do { \
 114                 if ((ARRAY_LIST).head && (ARRAY_LIST).allocated) \
 115                         free((ARRAY_LIST).head); \
 116                 ARRAYLIST_INIT(ARRAY_LIST, (ARRAY_LIST).alloc_blocksize); \
 117         } while(0)
 118
 119 #define ARRAYLIST_FOREACH(ITEM_P, ARRAY_LIST) \
 120         for ((ITEM_P) = (ARRAY_LIST).head; \
 121              (ITEM_P) - (ARRAY_LIST).head < (ARRAY_LIST).len; \
 122              (ITEM_P)++)
 123
 124 #define ARRAYLIST_IDX(ITEM_P, ARRAY_LIST) ((ITEM_P) - (ARRAY_LIST).head)