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 "ralloc.h"
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 /* A zero-initialized version of this is guaranteed to represent an
  38  * empty array.
  39  *
  40  * Also, size <= capacity and data != 0 if and only if capacity != 0
  41  * capacity will always be the allocation size of data
  42  */
  43 struct util_dynarray
  44 {
  45    void *mem_ctx;
  46    void *data;
  47    unsigned size;
  48    unsigned capacity;
  49 };
  50
  51 static inline void
  52 util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
  53 {
  54    memset(buf, 0, sizeof(*buf));
  55    buf->mem_ctx = mem_ctx;
  56 }
  57
  58 static inline void
  59 util_dynarray_fini(struct util_dynarray *buf)
  60 {
  61    if (buf->data) {
  62       if (buf->mem_ctx) {
  63          ralloc_free(buf->data);
  64       } else {
  65          free(buf->data);
  66       }
  67       util_dynarray_init(buf, buf->mem_ctx);
  68    }
  69 }
  70
  71 #define DYN_ARRAY_INITIAL_SIZE 64
  72
  73 /* use util_dynarray_trim to reduce the allocated storage */
  74 static inline void *
  75 util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
  76 {
  77    void *p;
  78    if (newsize > buf->capacity) {
  79       if (buf->capacity == 0)
  80          buf->capacity = DYN_ARRAY_INITIAL_SIZE;
  81
  82       while (newsize > buf->capacity)
  83          buf->capacity *= 2;
  84
  85       if (buf->mem_ctx) {
  86          buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->capacity);
  87       } else {
  88          buf->data = realloc(buf->data, buf->capacity);
  89       }
  90    }
  91
  92    p = (void *)((char *)buf->data + buf->size);
  93    buf->size = newsize;
  94
  95    return p;
  96 }
  97
  98 static inline void *
  99 util_dynarray_grow(struct util_dynarray *buf, int diff)
 100 {
 101    return util_dynarray_resize(buf, buf->size + diff);
 102 }
 103
 104 static inline void
 105 util_dynarray_trim(struct util_dynarray *buf)
 106 {
 107    if (buf->size != buf->capacity) {
 108       if (buf->size) {
 109          if (buf->mem_ctx) {
 110             buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
 111          } else {
 112             buf->data = realloc(buf->data, buf->size);
 113          }
 114          buf->capacity = buf->size;
 115       } else {
 116          if (buf->mem_ctx) {
 117             ralloc_free(buf->data);
 118          } else {
 119             free(buf->data);
 120          }
 121          buf->data = 0;
 122          buf->capacity = 0;
 123       }
 124    }
 125 }
 126
 127 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
 128 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
 129 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
 130 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
 131 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
 132 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
 133 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
 134 #define util_dynarray_begin(buf) ((buf)->data)
 135 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
 136
 137 #define util_dynarray_foreach(buf, type, elem) \
 138    for (type *elem = (type *)(buf)->data; \
 139         elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
 140
 141 #ifdef __cplusplus
 142 }
 143 #endif
 144
 145 #endif /* U_DYNARRAY_H */
 146