| 1 | /*␊ |
| 2 | Copyright (c) 2008-2012, Troy D. Hanson http://uthash.sourceforge.net␊ |
| 3 | All rights reserved.␊ |
| 4 | ␊ |
| 5 | Redistribution and use in source and binary forms, with or without␊ |
| 6 | modification, are permitted provided that the following conditions are met:␊ |
| 7 | ␊ |
| 8 | * Redistributions of source code must retain the above copyright␊ |
| 9 | notice, this list of conditions and the following disclaimer.␊ |
| 10 | ␊ |
| 11 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS␊ |
| 12 | IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED␊ |
| 13 | TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A␊ |
| 14 | PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER␊ |
| 15 | OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,␊ |
| 16 | EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,␊ |
| 17 | PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR␊ |
| 18 | PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF␊ |
| 19 | LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING␊ |
| 20 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS␊ |
| 21 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.␊ |
| 22 | */␊ |
| 23 | ␊ |
| 24 | /* a dynamic array implementation using macros ␊ |
| 25 | * see http://uthash.sourceforge.net/utarray␊ |
| 26 | */␊ |
| 27 | #ifndef UTARRAY_H␊ |
| 28 | #define UTARRAY_H␊ |
| 29 | ␊ |
| 30 | #define UTARRAY_VERSION 1.9.6␊ |
| 31 | ␊ |
| 32 | #ifdef __GNUC__␊ |
| 33 | #define _UNUSED_ __attribute__ ((__unused__)) ␊ |
| 34 | #else␊ |
| 35 | #define _UNUSED_ ␊ |
| 36 | #endif␊ |
| 37 | ␊ |
| 38 | #include "libsaio.h"␊ |
| 39 | ␊ |
| 40 | #ifndef utarray_oom␊ |
| 41 | #define utarray_oom() longjmp(uterror,-1)␊ |
| 42 | #endif␊ |
| 43 | #ifndef __utarray_malloc␊ |
| 44 | #define __utarray_malloc(sz) malloc(sz) /* malloc fcn */␊ |
| 45 | #endif␊ |
| 46 | #ifndef __utarray_free␊ |
| 47 | #define __utarray_free(ptr) free(ptr) /* free fcn */␊ |
| 48 | #endif␊ |
| 49 | #ifndef __utarray_realloc␊ |
| 50 | #define __utarray_realloc(ptr,sz) realloc(ptr,sz) /* realloc fcn */␊ |
| 51 | #endif␊ |
| 52 | typedef void (ctor_f)(void *dst, const void *src);␊ |
| 53 | typedef void (dtor_f)(void *elt);␊ |
| 54 | typedef void (init_f)(void *elt);␊ |
| 55 | typedef struct {␊ |
| 56 | size_t sz;␊ |
| 57 | init_f *init;␊ |
| 58 | ctor_f *copy;␊ |
| 59 | dtor_f *dtor;␊ |
| 60 | } UT_icd;␊ |
| 61 | ␊ |
| 62 | typedef struct {␊ |
| 63 | unsigned i,n;/* i: index of next available slot, n: num slots */␊ |
| 64 | UT_icd icd; /* initializer, copy and destructor functions */␊ |
| 65 | char *d; /* n slots of size icd->sz*/␊ |
| 66 | } UT_array;␊ |
| 67 | ␊ |
| 68 | #define utarray_init(a,_icd) do { \␊ |
| 69 | memset(a,0,sizeof(UT_array)); \␊ |
| 70 | (a)->icd=*_icd; \␊ |
| 71 | } while(0)␊ |
| 72 | ␊ |
| 73 | #define utarray_done(a) do { \␊ |
| 74 | if ((a)->n) { \␊ |
| 75 | if ((a)->icd.dtor) { \␊ |
| 76 | size_t _ut_i; \␊ |
| 77 | for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \␊ |
| 78 | (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \␊ |
| 79 | } \␊ |
| 80 | } \␊ |
| 81 | __utarray_free((a)->d); \␊ |
| 82 | } \␊ |
| 83 | (a)->n=0; \␊ |
| 84 | } while(0)␊ |
| 85 | ␊ |
| 86 | #define utarray_new(a,_icd) do { \␊ |
| 87 | a=(UT_array*)utarray_malloc(sizeof(UT_array)); \␊ |
| 88 | utarray_init(a,_icd); \␊ |
| 89 | } while(0)␊ |
| 90 | ␊ |
| 91 | #define utarray_free(a) do { \␊ |
| 92 | utarray_done(a); \␊ |
| 93 | __utarray_free(a); \␊ |
| 94 | } while(0)␊ |
| 95 | ␊ |
| 96 | #define utarray_reserve(a,by) do { \␊ |
| 97 | if (((a)->i+by) > ((a)->n)) { \␊ |
| 98 | while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \␊ |
| 99 | if ( ((a)->d=(char*)__utarray_realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) utarray_oom(); \␊ |
| 100 | } \␊ |
| 101 | } while(0)␊ |
| 102 | ␊ |
| 103 | #define utarray_push_back(a,p) do { \␊ |
| 104 | utarray_reserve(a,1); \␊ |
| 105 | if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \␊ |
| 106 | else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \␊ |
| 107 | } while(0)␊ |
| 108 | ␊ |
| 109 | #define utarray_pop_back(a) do { \␊ |
| 110 | if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \␊ |
| 111 | else { (a)->i--; } \␊ |
| 112 | } while(0)␊ |
| 113 | ␊ |
| 114 | #define utarray_extend_back(a) do { \␊ |
| 115 | utarray_reserve(a,1); \␊ |
| 116 | if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \␊ |
| 117 | else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \␊ |
| 118 | (a)->i++; \␊ |
| 119 | } while(0)␊ |
| 120 | ␊ |
| 121 | #define utarray_len(a) ((a)->i)␊ |
| 122 | ␊ |
| 123 | #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)␊ |
| 124 | #define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) )))␊ |
| 125 | ␊ |
| 126 | #define utarray_insert(a,p,j) do { \␊ |
| 127 | utarray_reserve(a,1); \␊ |
| 128 | if (j > (a)->i) break; \␊ |
| 129 | if ((j) < (a)->i) { \␊ |
| 130 | memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \␊ |
| 131 | ((a)->i - (j))*((a)->icd.sz)); \␊ |
| 132 | } \␊ |
| 133 | if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \␊ |
| 134 | else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \␊ |
| 135 | (a)->i++; \␊ |
| 136 | } while(0)␊ |
| 137 | ␊ |
| 138 | #define utarray_inserta(a,w,j) do { \␊ |
| 139 | if (utarray_len(w) == 0) break; \␊ |
| 140 | if (j > (a)->i) break; \␊ |
| 141 | utarray_reserve(a,utarray_len(w)); \␊ |
| 142 | if ((j) < (a)->i) { \␊ |
| 143 | memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \␊ |
| 144 | _utarray_eltptr(a,j), \␊ |
| 145 | ((a)->i - (j))*((a)->icd.sz)); \␊ |
| 146 | } \␊ |
| 147 | if ((a)->icd.copy) { \␊ |
| 148 | size_t _ut_i; \␊ |
| 149 | for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \␊ |
| 150 | (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \␊ |
| 151 | } \␊ |
| 152 | } else { \␊ |
| 153 | memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \␊ |
| 154 | utarray_len(w)*((a)->icd.sz)); \␊ |
| 155 | } \␊ |
| 156 | (a)->i += utarray_len(w); \␊ |
| 157 | } while(0)␊ |
| 158 | ␊ |
| 159 | #define utarray_resize(dst,num) do { \␊ |
| 160 | size_t _ut_i; \␊ |
| 161 | if (dst->i > (size_t)(num)) { \␊ |
| 162 | if ((dst)->icd.dtor) { \␊ |
| 163 | for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \␊ |
| 164 | (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \␊ |
| 165 | } \␊ |
| 166 | } \␊ |
| 167 | } else if (dst->i < (size_t)(num)) { \␊ |
| 168 | utarray_reserve(dst,num-dst->i); \␊ |
| 169 | if ((dst)->icd.init) { \␊ |
| 170 | for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \␊ |
| 171 | (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \␊ |
| 172 | } \␊ |
| 173 | } else { \␊ |
| 174 | memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \␊ |
| 175 | } \␊ |
| 176 | } \␊ |
| 177 | dst->i = num; \␊ |
| 178 | } while(0)␊ |
| 179 | ␊ |
| 180 | #define utarray_concat(dst,src) do { \␊ |
| 181 | utarray_inserta((dst),(src),utarray_len(dst)); \␊ |
| 182 | } while(0)␊ |
| 183 | ␊ |
| 184 | #define utarray_erase(a,pos,len) do { \␊ |
| 185 | if ((a)->icd.dtor) { \␊ |
| 186 | size_t _ut_i; \␊ |
| 187 | for(_ut_i=0; _ut_i < len; _ut_i++) { \␊ |
| 188 | (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \␊ |
| 189 | } \␊ |
| 190 | } \␊ |
| 191 | if ((a)->i > (pos+len)) { \␊ |
| 192 | memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \␊ |
| 193 | (((a)->i)-(pos+len))*((a)->icd.sz)); \␊ |
| 194 | } \␊ |
| 195 | (a)->i -= (len); \␊ |
| 196 | } while(0)␊ |
| 197 | ␊ |
| 198 | #define utarray_renew(a,u) do { \␊ |
| 199 | if (a) utarray_clear(a); \␊ |
| 200 | else utarray_new((a),(u)); \␊ |
| 201 | } while(0)␊ |
| 202 | ␊ |
| 203 | #define utarray_clear(a) do { \␊ |
| 204 | if ((a)->i > 0) { \␊ |
| 205 | if ((a)->icd.dtor) { \␊ |
| 206 | size_t _ut_i; \␊ |
| 207 | for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \␊ |
| 208 | (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \␊ |
| 209 | } \␊ |
| 210 | } \␊ |
| 211 | (a)->i = 0; \␊ |
| 212 | } \␊ |
| 213 | } while(0)␊ |
| 214 | ␊ |
| 215 | #define utarray_sort(a,cmp) do { \␊ |
| 216 | qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \␊ |
| 217 | } while(0)␊ |
| 218 | ␊ |
| 219 | #define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)␊ |
| 220 | ␊ |
| 221 | #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)␊ |
| 222 | #define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : ((((a)->i) > (utarray_eltidx(a,e)+1)) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL))␊ |
| 223 | #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))␊ |
| 224 | #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)␊ |
| 225 | #define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(a)->icd.sz) : -1)␊ |
| 226 | ␊ |
| 227 | /* last we pre-define a few icd for common utarrays of ints and strings */␊ |
| 228 | static void utarray_str_cpy(void *dst, const void *src) {␊ |
| 229 | char **_src = (char**)src, **_dst = (char**)dst;␊ |
| 230 | *_dst = (*_src == NULL) ? NULL : strdup(*_src);␊ |
| 231 | }␊ |
| 232 | static void utarray_str_dtor(void *elt) {␊ |
| 233 | char **eltc = (char**)elt;␊ |
| 234 | if (*eltc) __utarray_free(*eltc);␊ |
| 235 | }␊ |
| 236 | static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};␊ |
| 237 | static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL};␊ |
| 238 | static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL};␊ |
| 239 | ␊ |
| 240 | ␊ |
| 241 | #endif /* UTARRAY_H */␊ |
| 242 | |
