ucw/gary.h

   1 /*
   2  *      UCW Library -- A simple growing array of an arbitrary type
   3  *
   4  *      (c) 2010--2014 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #ifndef _UCW_GARY_H
   8 #define _UCW_GARY_H
   9
  10 #include <ucw/alloc.h>
  11
  12 #ifdef CONFIG_UCW_CLEAN_ABI
  13 #define gary_empty_hdr ucw_gary_empty_hdr
  14 #define gary_fix ucw_gary_fix
  15 #define gary_init ucw_gary_init
  16 #define gary_push_helper ucw_gary_push_helper
  17 #define gary_set_size ucw_gary_set_size
  18 #endif
  19
  20 struct gary_hdr {
  21   size_t num_elts;
  22   size_t have_space;
  23   size_t elt_size;
  24   struct ucw_allocator *allocator;
  25 };
  26
  27 #define GARY_HDR_SIZE ALIGN_TO(sizeof(struct gary_hdr), CPU_STRUCT_ALIGN)
  28 #define GARY_HDR(ptr) ((struct gary_hdr *)((byte*)(ptr) - GARY_HDR_SIZE))
  29 #define GARY_BODY(ptr) ((byte *)(ptr) + GARY_HDR_SIZE)
  30
  31 /**
  32  * Create a new growing array, initially containing @n elements,
  33  * and let @ptr point to its first element. The memory used by the
  34  * array is allocated by <<basics:xmalloc()>>.
  35  **/
  36 #define GARY_INIT(ptr, n) (ptr) = gary_init(sizeof(*(ptr)), (n), &ucw_allocator_std)
  37
  38 /**
  39  * Create a growing array like GARY_INIT() does, but all newly
  40  * allocated elements will be automatically zeroed.
  41  **/
  42 #define GARY_INIT_ZERO(ptr, n) (ptr) = gary_init(sizeof(*(ptr)), (n), &ucw_allocator_zeroed)
  43
  44 /**
  45  * Create a growing array like GARY_INIT() does, but based upon the given
  46  * <<alloc:,generic allocator>>.
  47  **/
  48 #define GARY_INIT_ALLOC(ptr, n, a) (ptr) = gary_init(sizeof(*(ptr)), (n), (a))
  49
  50 /**
  51  * Create a growing array, initially containing 0 elements, but with enough
  52  * space to keep @n of them without needing reallocation. The @ptr variable
  53  * will point to the first element of the array.
  54  **/
  55 #define GARY_INIT_SPACE(ptr, n) do { GARY_INIT(ptr, n); (GARY_HDR(ptr))->num_elts = 0; } while (0)
  56
  57 /** A combination of GARY_INIT_ZERO() and GARY_INIT_SPACE(). **/
  58 #define GARY_INIT_SPACE_ZERO(ptr, n) do { GARY_INIT_ZERO(ptr, n); (GARY_HDR(ptr))->num_elts = 0; } while (0)
  59
  60 /** A combination of GARY_INIT_ALLOC() and GARY_INIT_SPACE(). **/
  61 #define GARY_INIT_SPACE_ALLOC(ptr, n, a) do { GARY_INIT_ALLOC(ptr, n, a); (GARY_HDR(ptr))->num_elts = 0; } while (0)
  62
  63 /** Destroy a growing array and free memory used by it. If @ptr is NULL, nothing happens. **/
  64 #define GARY_FREE(ptr) gary_free(ptr)
  65
  66 /** Return the current number elements of the given growing array. **/
  67 #define GARY_SIZE(ptr) (GARY_HDR(ptr)->num_elts)
  68
  69 /**
  70  * Resize the given growing array to @n elements.
  71  * The @ptr can change, if the array has to be re-allocated.
  72  **/
  73 #define GARY_RESIZE(ptr, n) ((ptr) = gary_set_size((ptr), (n)))
  74
  75 /** Create a new growing array, or resize it if it already exists. **/
  76 #define GARY_INIT_OR_RESIZE(ptr, n) (ptr) = (ptr) ? gary_set_size((ptr), (n)) : gary_init(sizeof(*(ptr)), (n), &ucw_allocator_std)
  77
  78 /**
  79  * Push @n elements to a growing array. That is, make space for @n more elements
  80  * at the end of the array and return a pointer to the first of these elements.
  81  * The @ptr can change, if the array has to be re-allocated.
  82  **/
  83 #define GARY_PUSH_MULTI(ptr, n) ({                                      \
  84   struct gary_hdr *_h = GARY_HDR(ptr);                                  \
  85   typeof(*(ptr)) *_c = &(ptr)[_h->num_elts];                            \
  86   size_t _n = n;                                                        \
  87   _h->num_elts += _n;                                                   \
  88   if (_h->num_elts > _h->have_space)                                    \
  89     (ptr) = gary_push_helper((ptr), _n, (byte **) &_c);                 \
  90   _c; })
  91
  92 /**
  93  * Push a single element at the end of a growing array and return a pointer to it.
  94  * The @ptr can change, if the array has to be re-allocated.
  95  **/
  96 #define GARY_PUSH(ptr) GARY_PUSH_MULTI(ptr, 1)
  97
  98 /**
  99  * Pop @n elements from the end of a growing array.
 100  * The @ptr can change, if the array has to be re-allocated.
 101  **/
 102 #define GARY_POP_MULTI(ptr, n) GARY_HDR(ptr)->num_elts -= (n)
 103
 104 /**
 105  * Pop a single element from the end of a growing array.
 106  * The @ptr can change, if the array has to be re-allocated.
 107  **/
 108 #define GARY_POP(ptr) GARY_POP_MULTI(ptr, 1)
 109
 110 /**
 111  * Fix size of a growing array, returning all unused memory to the
 112  * system (or more precisely, to the underlying allocator).
 113  * The @ptr can change.
 114  **/
 115 #define GARY_FIX(ptr) (ptr) = gary_fix((ptr))
 116
 117 /* Internal functions */
 118 void *gary_init(size_t elt_size, size_t num_elts, struct ucw_allocator *allocator);
 119 void *gary_set_size(void *array, size_t n);
 120 void *gary_push_helper(void *array, size_t n, byte **cptr);
 121 void *gary_fix(void *array);
 122
 123 static inline void gary_free(void *ptr)
 124 {
 125   if (ptr)
 126     {
 127       struct gary_hdr *h = GARY_HDR(ptr);
 128       h->allocator->free(h->allocator, h);
 129     }
 130 }
 131
 132 /* A forever empty gary. Used internally. */
 133
 134 extern struct gary_hdr gary_empty_hdr;
 135 #define GARY_FOREVER_EMPTY GARY_BODY(&gary_empty_hdr)
 136
 137 /* Type-agnostic interface. Currently it's recommended for internal use only. */
 138
 139 #define GARY_PUSH_GENERIC(ptr) ({                                       \
 140   struct gary_hdr *_h = GARY_HDR(ptr);                                  \
 141   void *_c = (byte *)(ptr) + _h->num_elts++ * _h->elt_size;             \
 142   if (_h->num_elts > _h->have_space)                                    \
 143     (ptr) = gary_push_helper((ptr), 1, (byte **) &_c);                  \
 144   _c; })
 145
 146 #endif