src/util/u_dynarray.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2010 Luca Barbieri
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining
   6  * a copy of this software and associated documentation files (the
   7  * "Software"), to deal in the Software without restriction, including
   8  * without limitation the rights to use, copy, modify, merge, publish,
   9  * distribute, sublicense, and/or sell copies of the Software, and to
  10  * permit persons to whom the Software is furnished to do so, subject to
  11  * the following conditions:
  12  *
  13  * The above copyright notice and this permission notice (including the
  14  * next paragraph) shall be included in all copies or substantial
  15  * portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20  * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
  21  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  22  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  23  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 #ifndef U_DYNARRAY_H
  28 #define U_DYNARRAY_H
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include "ralloc.h"
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38 /* A zero-initialized version of this is guaranteed to represent an
  39  * empty array.
  40  *
  41  * Also, size <= capacity and data != 0 if and only if capacity != 0
  42  * capacity will always be the allocation size of data
  43  */
  44 struct util_dynarray
  45 {
  46    void *mem_ctx;
  47    void *data;
  48    unsigned size;
  49    unsigned capacity;
  50 };
  51
  52 static inline void
  53 util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
  54 {
  55    memset(buf, 0, sizeof(*buf));
  56    buf->mem_ctx = mem_ctx;
  57 }
  58
  59 static inline void
  60 util_dynarray_fini(struct util_dynarray *buf)
  61 {
  62    if (buf->data) {
  63       if (buf->mem_ctx) {
  64          ralloc_free(buf->data);
  65       } else {
  66          free(buf->data);
  67       }
  68       util_dynarray_init(buf, buf->mem_ctx);
  69    }
  70 }
  71
  72 static inline void
  73 util_dynarray_clear(struct util_dynarray *buf)
  74 {
  75         buf->size = 0;
  76 }
  77
  78 #define DYN_ARRAY_INITIAL_SIZE 64
  79
  80 static inline void *
  81 util_dynarray_ensure_cap(struct util_dynarray *buf, unsigned newcap)
  82 {
  83    if (newcap > buf->capacity) {
  84       if (buf->capacity == 0)
  85          buf->capacity = DYN_ARRAY_INITIAL_SIZE;
  86
  87       while (newcap > buf->capacity)
  88          buf->capacity *= 2;
  89
  90       if (buf->mem_ctx) {
  91          buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->capacity);
  92       } else {
  93          buf->data = realloc(buf->data, buf->capacity);
  94       }
  95    }
  96
  97    return (void *)((char *)buf->data + buf->size);
  98 }
  99
 100 static inline void *
 101 util_dynarray_grow_cap(struct util_dynarray *buf, int diff)
 102 {
 103    return util_dynarray_ensure_cap(buf, buf->size + diff);
 104 }
 105
 106 /* use util_dynarray_trim to reduce the allocated storage */
 107 static inline void *
 108 util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
 109 {
 110    void *p = util_dynarray_ensure_cap(buf, newsize);
 111    buf->size = newsize;
 112
 113    return p;
 114 }
 115
 116 static inline void
 117 util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx,
 118                     struct util_dynarray *from_buf)
 119 {
 120    util_dynarray_init(buf, mem_ctx);
 121    util_dynarray_resize(buf, from_buf->size);
 122    memcpy(buf->data, from_buf->data, from_buf->size);
 123 }
 124
 125 static inline void *
 126 util_dynarray_grow(struct util_dynarray *buf, int diff)
 127 {
 128    return util_dynarray_resize(buf, buf->size + diff);
 129 }
 130
 131 static inline void
 132 util_dynarray_trim(struct util_dynarray *buf)
 133 {
 134    if (buf->size != buf->capacity) {
 135       if (buf->size) {
 136          if (buf->mem_ctx) {
 137             buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
 138          } else {
 139             buf->data = realloc(buf->data, buf->size);
 140          }
 141          buf->capacity = buf->size;
 142       } else {
 143          if (buf->mem_ctx) {
 144             ralloc_free(buf->data);
 145          } else {
 146             free(buf->data);
 147          }
 148          buf->data = NULL;
 149          buf->capacity = 0;
 150       }
 151    }
 152 }
 153
 154 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
 155 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
 156 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
 157 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
 158 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
 159 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
 160 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
 161 #define util_dynarray_begin(buf) ((buf)->data)
 162 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
 163 #define util_dynarray_num_elements(buf, type) ((buf)->size / sizeof(type))
 164
 165 #define util_dynarray_foreach(buf, type, elem) \
 166    for (type *elem = (type *)(buf)->data; \
 167         elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
 168
 169 #define util_dynarray_foreach_reverse(buf, type, elem)          \
 170    if ((buf)->size > 0)                                         \
 171       for (type *elem = util_dynarray_top_ptr(buf, type);       \
 172            elem;                                                \
 173            elem = elem > (type *)(buf)->data ? elem - 1 : NULL)
 174
 175 #define util_dynarray_delete_unordered(buf, type, v)                    \
 176    do {                                                                 \
 177       unsigned num_elements = (buf)->size / sizeof(type);               \
 178       unsigned i;                                                       \
 179       for (i = 0; i < num_elements; i++) {                              \
 180          type __v = *util_dynarray_element((buf), type, (i));           \
 181          if (v == __v) {                                                \
 182             memcpy(util_dynarray_element((buf), type, (i)),             \
 183                    util_dynarray_pop_ptr((buf), type), sizeof(type));   \
 184             break;                                                      \
 185          }                                                              \
 186       }                                                                 \
 187    } while (0)
 188
 189 #ifdef __cplusplus
 190 }
 191 #endif
 192
 193 #endif /* U_DYNARRAY_H */
 194