utarray.h (13456B)
1 /* 2 Copyright (c) 2008-2022, Troy D. Hanson https://troydhanson.github.io/uthash/ 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 */ 26 #ifndef UTARRAY_H 27 #define UTARRAY_H 28 29 #define UTARRAY_VERSION 2.3.0 30 31 #include <stddef.h> /* size_t */ 32 #include <string.h> /* memset, etc */ 33 #include <stdlib.h> /* exit */ 34 35 #ifdef __GNUC__ 36 #define UTARRAY_UNUSED __attribute__((__unused__)) 37 #else 38 #define UTARRAY_UNUSED 39 #endif 40 41 #ifdef oom 42 #error "The name of macro 'oom' has been changed to 'utarray_oom'. Please update your code." 43 #define utarray_oom() oom() 44 #endif 45 46 #ifndef utarray_oom 47 #define utarray_oom() exit(-1) 48 #endif 49 50 typedef void (ctor_f)(void *dst, const void *src); 51 typedef void (dtor_f)(void *elt); 52 typedef void (init_f)(void *elt); 53 typedef struct { 54 size_t sz; 55 init_f *init; 56 ctor_f *copy; 57 dtor_f *dtor; 58 } UT_icd; 59 60 typedef struct { 61 unsigned i,n;/* i: index of next available slot, n: num slots */ 62 UT_icd icd; /* initializer, copy and destructor functions */ 63 char *d; /* n slots of size icd->sz*/ 64 } UT_array; 65 66 #define utarray_init(a,_icd) do { \ 67 memset(a,0,sizeof(UT_array)); \ 68 (a)->icd = *(_icd); \ 69 } while(0) 70 71 #define utarray_done(a) do { \ 72 if ((a)->n) { \ 73 if ((a)->icd.dtor) { \ 74 unsigned _ut_i; \ 75 for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ 76 (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ 77 } \ 78 } \ 79 free((a)->d); \ 80 } \ 81 (a)->n=0; \ 82 } while(0) 83 84 #define utarray_new(a,_icd) do { \ 85 (a) = (UT_array*)malloc(sizeof(UT_array)); \ 86 if ((a) == NULL) { \ 87 utarray_oom(); \ 88 } \ 89 utarray_init(a,_icd); \ 90 } while(0) 91 92 #define utarray_free(a) do { \ 93 utarray_done(a); \ 94 free(a); \ 95 } while(0) 96 97 #define utarray_reserve(a,by) do { \ 98 if (((a)->i+(by)) > (a)->n) { \ 99 char *utarray_tmp; \ 100 while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ 101 utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \ 102 if (utarray_tmp == NULL) { \ 103 utarray_oom(); \ 104 } \ 105 (a)->d=utarray_tmp; \ 106 } \ 107 } while(0) 108 109 #define utarray_push_back(a,p) do { \ 110 utarray_reserve(a,1); \ 111 if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \ 112 else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \ 113 } while(0) 114 115 #define utarray_pop_back(a) do { \ 116 if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \ 117 else { (a)->i--; } \ 118 } while(0) 119 120 #define utarray_extend_back(a) do { \ 121 utarray_reserve(a,1); \ 122 if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \ 123 else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \ 124 (a)->i++; \ 125 } while(0) 126 127 #define utarray_len(a) ((a)->i) 128 129 #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) 130 #define _utarray_eltptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j)))) 131 132 #define utarray_insert(a,p,j) do { \ 133 if ((j) > (a)->i) utarray_resize(a,j); \ 134 utarray_reserve(a,1); \ 135 if ((j) < (a)->i) { \ 136 memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ 137 ((a)->i - (j))*((a)->icd.sz)); \ 138 } \ 139 if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \ 140 else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \ 141 (a)->i++; \ 142 } while(0) 143 144 #define utarray_inserta(a,w,j) do { \ 145 if (utarray_len(w) == 0) break; \ 146 if ((j) > (a)->i) utarray_resize(a,j); \ 147 utarray_reserve(a,utarray_len(w)); \ 148 if ((j) < (a)->i) { \ 149 memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ 150 _utarray_eltptr(a,j), \ 151 ((a)->i - (j))*((a)->icd.sz)); \ 152 } \ 153 if ((a)->icd.copy) { \ 154 unsigned _ut_i; \ 155 for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ 156 (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \ 157 } \ 158 } else { \ 159 memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ 160 utarray_len(w)*((a)->icd.sz)); \ 161 } \ 162 (a)->i += utarray_len(w); \ 163 } while(0) 164 165 #define utarray_resize(dst,num) do { \ 166 unsigned _ut_i; \ 167 if ((dst)->i > (unsigned)(num)) { \ 168 if ((dst)->icd.dtor) { \ 169 for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) { \ 170 (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i)); \ 171 } \ 172 } \ 173 } else if ((dst)->i < (unsigned)(num)) { \ 174 utarray_reserve(dst, (num) - (dst)->i); \ 175 if ((dst)->icd.init) { \ 176 for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) { \ 177 (dst)->icd.init(_utarray_eltptr(dst, _ut_i)); \ 178 } \ 179 } else { \ 180 memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \ 181 } \ 182 } \ 183 (dst)->i = (num); \ 184 } while(0) 185 186 #define utarray_concat(dst,src) do { \ 187 utarray_inserta(dst, src, utarray_len(dst)); \ 188 } while(0) 189 190 #define utarray_erase(a,pos,len) do { \ 191 if ((a)->icd.dtor) { \ 192 unsigned _ut_i; \ 193 for (_ut_i = 0; _ut_i < (len); _ut_i++) { \ 194 (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i)); \ 195 } \ 196 } \ 197 if ((a)->i > ((pos) + (len))) { \ 198 memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)), \ 199 ((a)->i - ((pos) + (len))) * (a)->icd.sz); \ 200 } \ 201 (a)->i -= (len); \ 202 } while(0) 203 204 #define utarray_renew(a,u) do { \ 205 if (a) utarray_clear(a); \ 206 else utarray_new(a, u); \ 207 } while(0) 208 209 #define utarray_clear(a) do { \ 210 if ((a)->i > 0) { \ 211 if ((a)->icd.dtor) { \ 212 unsigned _ut_i; \ 213 for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ 214 (a)->icd.dtor(_utarray_eltptr(a, _ut_i)); \ 215 } \ 216 } \ 217 (a)->i = 0; \ 218 } \ 219 } while(0) 220 221 #define utarray_sort(a,cmp) do { \ 222 qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \ 223 } while(0) 224 225 #define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp) 226 227 #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL) 228 #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)) 229 #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) != 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) 230 #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) 231 #define utarray_eltidx(a,e) (((char*)(e) - (a)->d) / (a)->icd.sz) 232 233 /* last we pre-define a few icd for common utarrays of ints and strings */ 234 static void utarray_str_cpy(void *dst, const void *src) { 235 char *const *srcc = (char *const *)src; 236 char **dstc = (char**)dst; 237 *dstc = (*srcc == NULL) ? NULL : strdup(*srcc); 238 } 239 static void utarray_str_dtor(void *elt) { 240 char **eltc = (char**)elt; 241 if (*eltc != NULL) free(*eltc); 242 } 243 static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; 244 static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL}; 245 static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL}; 246 247 248 #endif /* UTARRAY_H */