git.ozlabs.org Git - ccan/blob - ccan/darray/darray.h

   1 /*
   2         Copyright (c) 2009  Joseph A. Adams
   3         All rights reserved.
   4
   5         Redistribution and use in source and binary forms, with or without
   6         modification, are permitted provided that the following conditions
   7         are met:
   8         1. Redistributions of source code must retain the above copyright
   9            notice, this list of conditions and the following disclaimer.
  10         2. Redistributions in binary form must reproduce the above copyright
  11            notice, this list of conditions and the following disclaimer in the
  12            documentation and/or other materials provided with the distribution.
  13         3. The name of the author may not be used to endorse or promote products
  14            derived from this software without specific prior written permission.
  15
  16         THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17         IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18         OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19         IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20         INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21         NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22         DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23         THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24         (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25         THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26 */
  27
  28 #ifndef CCAN_DARRAY_H
  29 #define CCAN_DARRAY_H
  30
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include "config.h"
  34
  35 /*
  36  * SYNOPSIS
  37  *
  38  * Life cycle of a darray (dynamically-allocated array):
  39  *
  40  *     darray(int) a = darray_new();
  41  *     darray_free(a);
  42  *
  43  *     struct {darray(int) a;} foo;
  44  *     darray_init(foo.a);
  45  *     darray_free(foo.a);
  46  *
  47  * Typedefs for darrays of common types:
  48  *
  49  *     darray_char, darray_schar, darray_uchar
  50  *     darray_short, darray_int, darray_long
  51  *     darray_ushort, darray_uint, darray_ulong
  52  *
  53  * Access:
  54  *
  55  *     T      darray_item(darray(T) arr, size_t index);
  56  *     size_t darray_size(darray(T) arr);
  57  *     size_t darray_alloc(darray(T) arr);
  58  *     bool   darray_empty(darray(T) arr);
  59  *
  60  * Insertion (single item):
  61  *
  62  *     void   darray_append(darray(T) arr, T item);
  63  *     void   darray_prepend(darray(T) arr, T item);
  64  *     void   darray_push(darray(T) arr, T item); // same as darray_append
  65  *
  66  * Insertion (multiple items):
  67  *
  68  *     void   darray_append_items(darray(T) arr, T *items, size_t count);
  69  *     void   darray_prepend_items(darray(T) arr, T *items, size_t count);
  70  *
  71  *     void   darray_appends(darray(T) arr, [T item, [...]]);
  72  *     void   darray_prepends(darray(T) arr, [T item, [...]]);
  73  *
  74  *     // Same functionality as above, but does not require typeof.
  75  *     void   darray_appends_t(darray(T) arr, #T, [T item, [...]]);
  76  *     void   darray_prepends_t(darray(T) arr, #T, [T item, [...]]);
  77  *
  78  * Removal:
  79  *
  80  *     T      darray_pop(darray(T) arr | darray_size(arr) != 0);
  81  *     T*     darray_pop_check(darray(T*) arr);
  82  *
  83  * Replacement:
  84  *
  85  *     void   darray_from_items(darray(T) arr, T *items, size_t count);
  86  *     void   darray_from_c(darray(T) arr, T c_array[N]);
  87  *
  88  * String buffer:
  89  *
  90  *     void   darray_append_string(darray(char) arr, const char *str);
  91  *     void   darray_append_lit(darray(char) arr, char stringLiteral[N+1]);
  92  *
  93  *     void   darray_prepend_string(darray(char) arr, const char *str);
  94  *     void   darray_prepend_lit(darray(char) arr, char stringLiteral[N+1]);
  95  *
  96  *     void   darray_from_string(darray(T) arr, const char *str);
  97  *     void   darray_from_lit(darray(char) arr, char stringLiteral[N+1]);
  98  *
  99  * Size management:
 100  *
 101  *     void   darray_resize(darray(T) arr, size_t newSize);
 102  *     void   darray_resize0(darray(T) arr, size_t newSize);
 103  *
 104  *     void   darray_realloc(darray(T) arr, size_t newAlloc);
 105  *     void   darray_growalloc(darray(T) arr, size_t newAlloc);
 106  *
 107  *     void   darray_make_room(darray(T) arr, size_t room);
 108  *
 109  * Traversal:
 110  *
 111  *     darray_foreach(T *&i, darray(T) arr) {...}
 112  *     darray_foreach_reverse(T *&i, darray(T) arr) {...}
 113  *
 114  * Except for darray_foreach and darray_foreach_reverse,
 115  * all macros evaluate their non-darray arguments only once.
 116  */
 117
 118 /*** Life cycle ***/
 119
 120 #define darray(type) struct {type *item; size_t size; size_t alloc;}
 121
 122 #define darray_new() {0,0,0}
 123 #define darray_init(arr) do {(arr).item=0; (arr).size=0; (arr).alloc=0;} while(0)
 124 #define darray_free(arr) do {free((arr).item);} while(0)
 125
 126
 127 /*
 128  * Typedefs for darrays of common types.  These are useful
 129  * when you want to pass a pointer to an darray(T) around.
 130  *
 131  * The following will produce an incompatible pointer warning:
 132  *
 133  *     void foo(darray(int) *arr);
 134  *     darray(int) arr = darray_new();
 135  *     foo(&arr);
 136  *
 137  * The workaround:
 138  *
 139  *     void foo(darray_int *arr);
 140  *     darray_int arr = darray_new();
 141  *     foo(&arr);
 142  */
 143
 144 typedef darray(char)           darray_char;
 145 typedef darray(signed char)    darray_schar;
 146 typedef darray(unsigned char)  darray_uchar;
 147
 148 typedef darray(short)          darray_short;
 149 typedef darray(int)            darray_int;
 150 typedef darray(long)           darray_long;
 151
 152 typedef darray(unsigned short) darray_ushort;
 153 typedef darray(unsigned int)   darray_uint;
 154 typedef darray(unsigned long)  darray_ulong;
 155
 156
 157 /*** Access ***/
 158
 159 #define darray_item(arr, i) ((arr).item[i])
 160 #define darray_size(arr)    ((arr).size)
 161 #define darray_alloc(arr)   ((arr).alloc)
 162 #define darray_empty(arr)   ((arr).size == 0)
 163
 164
 165 /*** Insertion (single item) ***/
 166
 167 #define darray_append(arr, ...) do { \
 168                 darray_resize(arr, (arr).size+1); \
 169                 (arr).item[(arr).size-1] = (__VA_ARGS__); \
 170         } while(0)
 171 #define darray_prepend(arr, ...) do { \
 172                 darray_resize(arr, (arr).size+1); \
 173                 memmove((arr).item+1, (arr).item, ((arr).size-1)*sizeof(*(arr).item)); \
 174                 (arr).item[0] = (__VA_ARGS__); \
 175         } while(0)
 176 #define darray_push(arr, ...) darray_append(arr, __VA_ARGS__)
 177
 178
 179 /*** Insertion (multiple items) ***/
 180
 181 #define darray_append_items(arr, items, count) do { \
 182                 size_t __count = (count), __oldSize = (arr).size; \
 183                 darray_resize(arr, __oldSize + __count); \
 184                 memcpy((arr).item + __oldSize, items, __count * sizeof(*(arr).item)); \
 185         } while(0)
 186
 187 #define darray_prepend_items(arr, items, count) do { \
 188                 size_t __count = (count), __oldSize = (arr).size; \
 189                 darray_resize(arr, __count + __oldSize); \
 190                 memmove((arr).item + __count, (arr).item, __oldSize * sizeof(*(arr).item)); \
 191                 memcpy((arr).item, items, __count * sizeof(*(arr).item)); \
 192         } while(0)
 193
 194 #define darray_append_items_nullterminate(arr, items, count) do { \
 195                 size_t __count = (count), __oldSize = (arr).size; \
 196                 darray_resize(arr, __oldSize + __count + 1); \
 197                 memcpy((arr).item + __oldSize, items, __count * sizeof(*(arr).item)); \
 198                 (arr).item[--(arr).size] = 0; \
 199         } while(0)
 200
 201 #define darray_prepend_items_nullterminate(arr, items, count) do { \
 202                 size_t __count = (count), __oldSize = (arr).size; \
 203                 darray_resize(arr, __count + __oldSize + 1); \
 204                 memmove((arr).item + __count, (arr).item, __oldSize * sizeof(*(arr).item)); \
 205                 memcpy((arr).item, items, __count * sizeof(*(arr).item)); \
 206                 (arr).item[--(arr).size] = 0; \
 207         } while(0)
 208
 209 #if HAVE_TYPEOF
 210 #define darray_appends(arr, ...) darray_appends_t(arr, typeof((*(arr).item)), __VA_ARGS__)
 211 #define darray_prepends(arr, ...) darray_prepends_t(arr, typeof((*(arr).item)), __VA_ARGS__)
 212 #endif
 213
 214 #define darray_appends_t(arr, type, ...) do { \
 215                 type __src[] = {__VA_ARGS__}; \
 216                 darray_append_items(arr, __src, sizeof(__src)/sizeof(*__src)); \
 217         } while(0)
 218 #define darray_prepends_t(arr, type, ...) do { \
 219                 type __src[] = {__VA_ARGS__}; \
 220                 darray_prepend_items(arr, __src, sizeof(__src)/sizeof(*__src)); \
 221         } while(0)
 222
 223
 224 /*** Removal ***/
 225
 226 /* Warning: Do not call darray_pop on an empty darray. */
 227 #define darray_pop(arr) ((arr).item[--(arr).size])
 228 #define darray_pop_check(arr) ((arr).size ? darray_pop(arr) : NULL)
 229
 230
 231 /*** Replacement ***/
 232
 233 #define darray_from_items(arr, items, count) do {size_t __count = (count); darray_resize(arr, __count); memcpy((arr).item, items, __count*sizeof(*(arr).item));} while(0)
 234 #define darray_from_c(arr, c_array) darray_from_items(arr, c_array, sizeof(c_array)/sizeof(*(c_array)))
 235
 236
 237 /*** String buffer ***/
 238
 239 #define darray_append_string(arr, str) do {const char *__str = (str); darray_append_items(arr, __str, strlen(__str)+1); (arr).size--;} while(0)
 240 #define darray_append_lit(arr, stringLiteral) do {darray_append_items(arr, stringLiteral, sizeof(stringLiteral)); (arr).size--;} while(0)
 241
 242 #define darray_prepend_string(arr, str) do { \
 243                 const char *__str = (str); \
 244                 darray_prepend_items_nullterminate(arr, __str, strlen(__str)); \
 245         } while(0)
 246 #define darray_prepend_lit(arr, stringLiteral) \
 247         darray_prepend_items_nullterminate(arr, stringLiteral, sizeof(stringLiteral) - 1)
 248
 249 #define darray_from_string(arr, str) do {const char *__str = (str); darray_from_items(arr, __str, strlen(__str)+1); (arr).size--;} while(0)
 250 #define darray_from_lit(arr, stringLiteral) do {darray_from_items(arr, stringLiteral, sizeof(stringLiteral)); (arr).size--;} while(0)
 251
 252
 253 /*** Size management ***/
 254
 255 #define darray_resize(arr, newSize) darray_growalloc(arr, (arr).size = (newSize))
 256 #define darray_resize0(arr, newSize) do { \
 257                 size_t __oldSize = (arr).size, __newSize = (newSize); \
 258                 (arr).size = __newSize; \
 259                 if (__newSize > __oldSize) { \
 260                         darray_growalloc(arr, __newSize); \
 261                         memset(&(arr).item[__oldSize], 0, (__newSize - __oldSize) * sizeof(*(arr).item)); \
 262                 } \
 263         } while(0)
 264
 265 #define darray_realloc(arr, newAlloc) do { \
 266                 (arr).item = realloc((arr).item, ((arr).alloc = (newAlloc)) * sizeof(*(arr).item)); \
 267         } while(0)
 268 #define darray_growalloc(arr, need) do { \
 269                 size_t __need = (need); \
 270                 if (__need > (arr).alloc) \
 271                         darray_realloc(arr, darray_next_alloc((arr).alloc, __need)); \
 272         } while(0)
 273
 274 #if HAVE_STATEMENT_EXPR==1
 275 #define darray_make_room(arr, room) ({size_t newAlloc = (arr).size+(room); if ((arr).alloc<newAlloc) darray_realloc(arr, newAlloc); (arr).item+(arr).size; })
 276 #endif
 277
 278 static inline size_t darray_next_alloc(size_t alloc, size_t need)
 279 {
 280         if (alloc == 0)
 281                 alloc = 1;
 282         while (alloc < need)
 283                 alloc *= 2;
 284         return alloc;
 285 }
 286
 287
 288 /*** Traversal ***/
 289
 290 /*
 291  * darray_foreach(T *&i, darray(T) arr) {...}
 292  *
 293  * Traverse a darray.  `i` must be declared in advance as a pointer to an item.
 294  */
 295 #define darray_foreach(i, arr) \
 296         for ((i) = &(arr).item[0]; (i) < &(arr).item[(arr).size]; (i)++)
 297
 298 /*
 299  * darray_foreach_reverse(T *&i, darray(T) arr) {...}
 300  *
 301  * Like darray_foreach, but traverse in reverse order.
 302  */
 303 #define darray_foreach_reverse(i, arr) \
 304         for ((i) = &(arr).item[(arr).size]; (i)-- > &(arr).item[0]; )
 305
 306
 307 #endif /* CCAN_DARRAY_H */
 308
 309 /*
 310
 311 darray_growalloc(arr, newAlloc) sees if the darray can currently hold newAlloc items;
 312         if not, it increases the alloc to satisfy this requirement, allocating slack
 313         space to avoid having to reallocate for every size increment.
 314
 315 darray_from_string(arr, str) copies a string to an darray_char.
 316
 317 darray_push(arr, item) pushes an item to the end of the darray.
 318 darray_pop(arr) pops it back out.  Be sure there is at least one item in the darray before calling.
 319 darray_pop_check(arr) does the same as darray_pop, but returns NULL if there are no more items left in the darray.
 320
 321 darray_make_room(arr, room) ensures there's 'room' elements of space after the end of the darray, and it returns a pointer to this space.
 322 Currently requires HAVE_STATEMENT_EXPR, but I plan to remove this dependency by creating an inline function.
 323
 324 The following require HAVE_TYPEOF==1 :
 325
 326 darray_appends(arr, item0, item1...) appends a collection of comma-delimited items to the darray.
 327 darray_prepends(arr, item0, item1...) prepends a collection of comma-delimited items to the darray.\
 328
 329
 330 Examples:
 331
 332         darray(int)  arr;
 333         int        *i;
 334
 335         darray_appends(arr, 0,1,2,3,4);
 336         darray_appends(arr, -5,-4,-3,-2,-1);
 337         darray_foreach(i, arr)
 338                 printf("%d ", *i);
 339         printf("\n");
 340
 341         darray_free(arr);
 342
 343
 344         typedef struct {int n,d;} Fraction;
 345         darray(Fraction) fractions;
 346         Fraction        *i;
 347
 348         darray_appends(fractions, {3,4}, {3,5}, {2,1});
 349         darray_foreach(i, fractions)
 350                 printf("%d/%d\n", i->n, i->d);
 351
 352         darray_free(fractions);
 353 */