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 <limits.h>
  33 #include "ralloc.h"
  34
  35 #ifdef __cplusplus
  36 extern "C" {
  37 #endif
  38
  39 /* A zero-initialized version of this is guaranteed to represent an
  40  * empty array.
  41  *
  42  * Also, size <= capacity and data != 0 if and only if capacity != 0
  43  * capacity will always be the allocation size of data
  44  */
  45 struct util_dynarray
  46 {
  47    void *mem_ctx;
  48    void *data;
  49    unsigned size;
  50    unsigned capacity;
  51 };
  52
  53 static inline void
  54 util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
  55 {
  56    memset(buf, 0, sizeof(*buf));
  57    buf->mem_ctx = mem_ctx;
  58 }
  59
  60 static inline void
  61 util_dynarray_fini(struct util_dynarray *buf)
  62 {
  63    if (buf->data) {
  64       if (buf->mem_ctx) {
  65          ralloc_free(buf->data);
  66       } else {
  67          free(buf->data);
  68       }
  69       util_dynarray_init(buf, buf->mem_ctx);
  70    }
  71 }
  72
  73 static inline void
  74 util_dynarray_clear(struct util_dynarray *buf)
  75 {
  76         buf->size = 0;
  77 }
  78
  79 #define DYN_ARRAY_INITIAL_SIZE 64
  80
  81 MUST_CHECK static inline void *
  82 util_dynarray_ensure_cap(struct util_dynarray *buf, unsigned newcap)
  83 {
  84    if (newcap > buf->capacity) {
  85       unsigned capacity = MAX3(DYN_ARRAY_INITIAL_SIZE, buf->capacity * 2, newcap);
  86       void *data;
  87
  88       if (buf->mem_ctx) {
  89          data = reralloc_size(buf->mem_ctx, buf->data, capacity);
  90       } else {
  91          data = realloc(buf->data, capacity);
  92       }
  93       if (!data)
  94          return 0;
  95
  96       buf->data = data;
  97       buf->capacity = capacity;
  98    }
  99
 100    return (void *)((char *)buf->data + buf->size);
 101 }
 102
 103 /* use util_dynarray_trim to reduce the allocated storage */
 104 MUST_CHECK static inline void *
 105 util_dynarray_resize_bytes(struct util_dynarray *buf, unsigned nelts, size_t eltsize)
 106 {
 107    if (unlikely(nelts > UINT_MAX / eltsize))
 108       return 0;
 109
 110    unsigned newsize = nelts * eltsize;
 111    void *p = util_dynarray_ensure_cap(buf, newsize);
 112    if (!p)
 113       return 0;
 114
 115    buf->size = newsize;
 116
 117    return p;
 118 }
 119
 120 static inline void
 121 util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx,
 122                     struct util_dynarray *from_buf)
 123 {
 124    util_dynarray_init(buf, mem_ctx);
 125    if (util_dynarray_resize_bytes(buf, from_buf->size, 1))
 126       memcpy(buf->data, from_buf->data, from_buf->size);
 127 }
 128
 129 MUST_CHECK static inline void *
 130 util_dynarray_grow_bytes(struct util_dynarray *buf, unsigned ngrow, size_t eltsize)
 131 {
 132    unsigned growbytes = ngrow * eltsize;
 133
 134    if (unlikely(ngrow > (UINT_MAX / eltsize) ||
 135                 growbytes > UINT_MAX - buf->size))
 136       return 0;
 137
 138    unsigned newsize = buf->size + growbytes;
 139    void *p = util_dynarray_ensure_cap(buf, newsize);
 140    if (!p)
 141       return 0;
 142
 143    buf->size = newsize;
 144
 145    return p;
 146 }
 147
 148 static inline void
 149 util_dynarray_trim(struct util_dynarray *buf)
 150 {
 151    if (buf->size != buf->capacity) {
 152       if (buf->size) {
 153          if (buf->mem_ctx) {
 154             buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
 155          } else {
 156             buf->data = realloc(buf->data, buf->size);
 157          }
 158          buf->capacity = buf->size;
 159       } else {
 160          if (buf->mem_ctx) {
 161             ralloc_free(buf->data);
 162          } else {
 163             free(buf->data);
 164          }
 165          buf->data = NULL;
 166          buf->capacity = 0;
 167       }
 168    }
 169 }
 170
 171 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow_bytes((buf), 1, sizeof(type)), &__v, sizeof(type));} while(0)
 172 /* Returns a pointer to the space of the first new element (in case of growth) or NULL on failure. */
 173 #define util_dynarray_resize(buf, type, nelts) util_dynarray_resize_bytes(buf, (nelts), sizeof(type))
 174 #define util_dynarray_grow(buf, type, ngrow) util_dynarray_grow_bytes(buf, (ngrow), sizeof(type))
 175 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
 176 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
 177 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
 178 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
 179 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
 180 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
 181 #define util_dynarray_begin(buf) ((buf)->data)
 182 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
 183 #define util_dynarray_num_elements(buf, type) ((buf)->size / sizeof(type))
 184
 185 #define util_dynarray_foreach(buf, type, elem) \
 186    for (type *elem = (type *)(buf)->data; \
 187         elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
 188
 189 #define util_dynarray_foreach_reverse(buf, type, elem)          \
 190    if ((buf)->size > 0)                                         \
 191       for (type *elem = util_dynarray_top_ptr(buf, type);       \
 192            elem;                                                \
 193            elem = elem > (type *)(buf)->data ? elem - 1 : NULL)
 194
 195 #define util_dynarray_delete_unordered(buf, type, v)                    \
 196    do {                                                                 \
 197       unsigned num_elements = (buf)->size / sizeof(type);               \
 198       unsigned i;                                                       \
 199       for (i = 0; i < num_elements; i++) {                              \
 200          type __v = *util_dynarray_element((buf), type, (i));           \
 201          if (v == __v) {                                                \
 202             memcpy(util_dynarray_element((buf), type, (i)),             \
 203                    util_dynarray_pop_ptr((buf), type), sizeof(type));   \
 204             break;                                                      \
 205          }                                                              \
 206       }                                                                 \
 207    } while (0)
 208
 209 #ifdef __cplusplus
 210 }
 211 #endif
 212
 213 #endif /* U_DYNARRAY_H */
 214