common/array.h

   1 /******************************************************************************/
   2 /*          pfixtools: a collection of postfix related tools                  */
   3 /*          ~~~~~~~~~                                                         */
   4 /*  ________________________________________________________________________  */
   5 /*                                                                            */
   6 /*  Redistribution and use in source and binary forms, with or without        */
   7 /*  modification, are permitted provided that the following conditions        */
   8 /*  are met:                                                                  */
   9 /*                                                                            */
  10 /*  1. Redistributions of source code must retain the above copyright         */
  11 /*     notice, this list of conditions and the following disclaimer.          */
  12 /*  2. Redistributions in binary form must reproduce the above copyright      */
  13 /*     notice, this list of conditions and the following disclaimer in the    */
  14 /*     documentation and/or other materials provided with the distribution.   */
  15 /*  3. The names of its contributors may not be used to endorse or promote    */
  16 /*     products derived from this software without specific prior written     */
  17 /*     permission.                                                            */
  18 /*                                                                            */
  19 /*  THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTORS ``AS IS'' AND ANY EXPRESS   */
  20 /*  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED         */
  21 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE    */
  22 /*  DISCLAIMED.  IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY         */
  23 /*  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL        */
  24 /*  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS   */
  25 /*  OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)     */
  26 /*  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,       */
  27 /*  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN  */
  28 /*  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE           */
  29 /*  POSSIBILITY OF SUCH DAMAGE.                                               */
  30 /*                                                                            */
  31 /*   Copyright (c) 2006-2008 the Authors                                      */
  32 /*   see AUTHORS and source files for details                                 */
  33 /******************************************************************************/
  34
  35 /*
  36  * Copyright © 2008 Florent Bruneau
  37  */
  38
  39 #ifndef PFIXTOOLS_ARRAY_H
  40 #define PFIXTOOLS_ARRAY_H
  41
  42 #include "common.h"
  43 #include "mem.h"
  44 #include <sys/mman.h>
  45
  46 #define PRIV_ARRAY(Type)                                                       \
  47     struct {                                                                   \
  48         Type    *data;                                                         \
  49         uint32_t len;                                                          \
  50         uint32_t size;                                                         \
  51         unsigned locked : 1;                                                   \
  52     }
  53
  54 /** Declare type PA(Type).
  55  */
  56 #define PARRAY(Type)                                                           \
  57     typedef PRIV_ARRAY(Type*) Type ## _ptr_array_t;                            \
  58     static inline Type ## _ptr_array_t *Type ## _ptr_array_new(void)           \
  59     {                                                                          \
  60         return p_new(Type ## _ptr_array_t, 1);                                 \
  61     }                                                                          \
  62                                                                                \
  63     static inline void Type ## _ptr_array_delete(Type ## _ptr_array_t **array) \
  64     {                                                                          \
  65         if (*array) {                                                          \
  66             if ((*array)->locked) {                                            \
  67                 array_unlock(**array);                                         \
  68             }                                                                  \
  69             array_wipe(**array);                                               \
  70             p_delete(array);                                                   \
  71         }                                                                      \
  72     }
  73
  74 /** Declare types A(Type) and PA(Type).
  75  */
  76 #define ARRAY(Type)                                                            \
  77     typedef PRIV_ARRAY(Type) Type ## _array_t;                                 \
  78                                                                                \
  79     static inline Type ## _array_t *Type ## _array_new(void)                   \
  80     {                                                                          \
  81         return p_new(Type ## _array_t, 1);                                     \
  82     }                                                                          \
  83                                                                                \
  84     static inline void Type ## _array_delete(Type ## _array_t **array)         \
  85     {                                                                          \
  86         if (*array) {                                                          \
  87             if ((*array)->locked) {                                            \
  88                 array_unlock(**array);                                         \
  89             }                                                                  \
  90             array_wipe(**array);                                               \
  91             p_delete(array);                                                   \
  92         }                                                                      \
  93     }                                                                          \
  94                                                                                \
  95     PARRAY(Type)
  96
  97 /** Type A(Type) is a dynamic array of elements of type @c Type.
  98  */
  99 #define A(Type) Type ## _array_t
 100
 101 /** Type PA(Type) is a dynamic array of pointers to type @c Type.
 102  */
 103 #define PA(Type) Type ## _ptr_array_t
 104
 105 #define ARRAY_INIT { NULL, 0, 0, false }
 106
 107 #define array_init(array) (array) = ARRAY_INIT
 108
 109 #define array_can_edit(array) (!(array).locked)
 110
 111 #define array_ensure_can_edit(array)                                           \
 112     assert(array_can_edit(array) && "Trying to edit array while it is locked")
 113
 114 #define array_wipe(array)                                                      \
 115     do {                                                                       \
 116         array_ensure_can_edit(array);                                          \
 117         p_delete(&(array).data);                                               \
 118         (array).len  = 0;                                                      \
 119         (array).size = 0;                                                      \
 120     } while (0)
 121
 122
 123 /******* MEMORY MANAGEMENT *******/
 124
 125 /** Return the len of the array (number of elements contained in the array).
 126  */
 127 #define array_len(array) ((array).len)
 128
 129 /** Return the capacity of the array (number of elements the array can contain
 130  * without growing its internal buffer).
 131  */
 132 #define array_size(array) ((array).size)
 133
 134 /** Return the number of free places in the array.
 135  */
 136 #define array_free_space(array) (array_size(array) - array_len(array))
 137
 138 /** Return the size of an element of the array.
 139  */
 140 #define array_elt_len(array) (sizeof(*(array).data))
 141
 142 /** Return the number of bytes used by the content of the array.
 143  */
 144 #define array_byte_len(array) ((array).len * array_elt_len(array))
 145
 146 /** Ensure the capacity of the array if *at least* @c goal *elements*.
 147  */
 148 #define array_ensure_capacity(array, goal)                                     \
 149     do {                                                                       \
 150         array_ensure_can_edit(array);                                          \
 151         if ((array).size < (goal)) {                                           \
 152             const typeof((array).size) required_size = (goal);                 \
 153             typeof((array).size) next_size = (array).size;                     \
 154             do {                                                               \
 155                 next_size = p_alloc_nr(next_size);                             \
 156             } while (next_size < required_size);                               \
 157             p_allocgrow(&(array).data, next_size, &(array).size);              \
 158         }                                                                      \
 159     } while (0)
 160
 161 /** Ensure the array contains place for *at least* @c delta more elements.
 162  */
 163 #define array_ensure_capacity_delta(array, delta)                              \
 164     array_ensure_capacity(array, (array).len + (delta))
 165
 166 /** Ensure the array can contain @c goal elements.
 167  */
 168 #define array_ensure_exact_capacity(array, goal)                               \
 169     if ((array).size < (goal)) {                                               \
 170         array_ensure_can_edit(array);                                          \
 171         p_allocgrow(&(array).data, (goal), &(array).size);                     \
 172     }
 173
 174 /** Shrink capacity of the array to MAX(len, @c cap).
 175  */
 176 #define array_shrink(array, cap)                                               \
 177     do {                                                                       \
 178         array_ensure_can_edit(array);                                          \
 179         if ((cap) < (array).size && (array).size != (array).len) {             \
 180             p_shrink(&(array).data, MAX((array).len, (cap)), &(array).size);   \
 181         }                                                                      \
 182     } while (0)
 183
 184 /** Ensure the capacity of the array does not exceed its len.
 185  */
 186 #define array_adjust(array) array_shrink(array, 0)
 187
 188 #define array_lock(array)                                                      \
 189     ((array).locked                                                            \
 190      || (mlock((array).data, array_byte_len(array)) == 0                       \
 191          && ((array).locked = true)))
 192
 193 #define array_unlock(array)                                                    \
 194     if ((array).locked) {                                                      \
 195         (void)munlock((array).data, array_byte_len(array));                    \
 196         (array).locked = false;                                                \
 197     }
 198
 199
 200 /******* ADDING ELEMENTS *******/
 201
 202 #define array_add(array, obj)                                                  \
 203     do {                                                                       \
 204         array_ensure_capacity_delta(array, 1);                                 \
 205         (array).data[(array).len++] = (obj);                                   \
 206     } while (0)
 207
 208 #define array_append(array, objs, Len)                                         \
 209     do {                                                                       \
 210         const typeof((array).len) __len = (Len);                               \
 211         array_ensure_capacity_delta(array, __len);                             \
 212         memcpy((array).data + (array).len, objs,                               \
 213                __len * sizeof(*(array).data));                                 \
 214         (array).len += __len;                                                  \
 215     } while (0)
 216
 217
 218 /******* ACCESSSING ELEMENTS ********/
 219
 220 /** Getting the n'th element of the array.
 221  */
 222 #define array_elt(array, n) ((array).data[(n)])
 223
 224 #define array_first(array) array_elt(array, 0)
 225 #define array_last(array) array_elt(array, (array).len - 1)
 226
 227 #define array_pop_last(array) array_elt(array, --((array).len))
 228
 229 /** Getting a pointer to the n'th element of the array.
 230  */
 231 #define array_ptr(array, n) ((array).data + (n))
 232
 233 #define array_start(array) array_ptr((array), 0)
 234 #define array_end(array) array_ptr((array), array_len(array))
 235
 236 /****** TRAVERSING AN ARRAY *******/
 237
 238 /** Gives the position of pointer ptr in the array.
 239  * This macro may only be used withing a loop. @ref foreach.
 240  */
 241 #define array_pos(array, ptr) ((ptr) - array_start(array))
 242
 243 /** Build a loop over the elements of an array.
 244  *
 245  * <code>
 246  * A(MyType) array;
 247  * ...
 248  * foreach (MyType* element, array) {
 249  *    do_something(element);
 250  * }}
 251  * </code>
 252  *
 253  * Warnings:
 254  *  * remember the loop must be ended with }} (the foreach macro contains
 255  *    a not-matched opening brace).
 256  *  * the macro uses a counter name __Ai, so you cannot build imbricated
 257  *    array enumerations. You SHOULD NOT use this counter in your code since
 258  *    it is part of the internal API and may change in the future.
 259  */
 260
 261 #define foreach(var, array)                                                    \
 262     for (uint32_t __Ai = 0 ; __Ai < (array).len ; ++__Ai) {                    \
 263         var = array_ptr(array, __Ai);
 264
 265 /** Execute @c action for each element of the array.
 266  *
 267  * <code>
 268  * static void do_something(MyType *element) { ... }
 269  *
 270  * A(MyType) array;
 271  * ...
 272  * array_foreach(array, do_something);
 273  * </code>
 274  */
 275 #define array_foreach(array, action)                                           \
 276     for (uint32_t __Ai = 0 ; __Ai < (array).len ; ++__Ai) {                    \
 277         action(array_ptr(array, __Ai));                                        \
 278     }
 279
 280 /** Wipe each element of the array using @c wipe, then wipe the array.
 281  */
 282 #define array_deep_wipe(array, wipe)                                           \
 283     do {                                                                       \
 284         array_foreach(array, wipe);                                            \
 285         array_wipe(array);                                                     \
 286     } while (0)
 287
 288
 289
 290 ARRAY(char)
 291 ARRAY(int)
 292 ARRAY(bool)
 293 ARRAY(uint16_t)
 294 ARRAY(uint32_t)
 295
 296 PARRAY(void)
 297
 298 #endif