Home | History | Annotate | Download | only in util 
      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 /* use util_dynarray_trim to reduce the allocated storage */
     81 static inline void *
     82 util_dynarray_resize(struct util_dynarray *buf, unsigned newsize)
     83 {
     84    void *p;
     85    if (newsize > buf->capacity) {
     86       if (buf->capacity == 0)
     87          buf->capacity = DYN_ARRAY_INITIAL_SIZE;
     88 
     89       while (newsize > buf->capacity)
     90          buf->capacity *= 2;
     91 
     92       if (buf->mem_ctx) {
     93          buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->capacity);
     94       } else {
     95          buf->data = realloc(buf->data, buf->capacity);
     96       }
     97    }
     98 
     99    p = (void *)((char *)buf->data + buf->size);
    100    buf->size = newsize;
    101 
    102    return p;
    103 }
    104 
    105 static inline void *
    106 util_dynarray_grow(struct util_dynarray *buf, int diff)
    107 {
    108    return util_dynarray_resize(buf, buf->size + diff);
    109 }
    110 
    111 static inline void
    112 util_dynarray_trim(struct util_dynarray *buf)
    113 {
    114    if (buf->size != buf->capacity) {
    115       if (buf->size) {
    116          if (buf->mem_ctx) {
    117             buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
    118          } else {
    119             buf->data = realloc(buf->data, buf->size);
    120          }
    121          buf->capacity = buf->size;
    122       } else {
    123          if (buf->mem_ctx) {
    124             ralloc_free(buf->data);
    125          } else {
    126             free(buf->data);
    127          }
    128          buf->data = 0;
    129          buf->capacity = 0;
    130       }
    131    }
    132 }
    133 
    134 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow((buf), sizeof(type)), &__v, sizeof(type));} while(0)
    135 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
    136 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
    137 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
    138 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
    139 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
    140 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
    141 #define util_dynarray_begin(buf) ((buf)->data)
    142 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
    143 
    144 #define util_dynarray_foreach(buf, type, elem) \
    145    for (type *elem = (type *)(buf)->data; \
    146         elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
    147 
    148 #define util_dynarray_delete_unordered(buf, type, v)                    \
    149    do {                                                                 \
    150       unsigned num_elements = (buf)->size / sizeof(type);               \
    151       unsigned i;                                                       \
    152       for (i = 0; i < num_elements; i++) {                              \
    153          type __v = *util_dynarray_element((buf), type, (i));           \
    154          if (v == __v) {                                                \
    155             memcpy(util_dynarray_element((buf), type, (i)),             \
    156                    util_dynarray_pop_ptr((buf), type), sizeof(type));   \
    157             break;                                                      \
    158          }                                                              \
    159       }                                                                 \
    160    } while (0)
    161 
    162 #ifdef __cplusplus
    163 }
    164 #endif
    165 
    166 #endif /* U_DYNARRAY_H */
    167 
    168