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