1*5ac3bc71Schristos /* $NetBSD: utarray.h,v 1.5 2024/03/03 17:37:29 christos Exp $ */
2e81373b4Schristos
3bb7a167aSjkoshy /*-
4bb7a167aSjkoshy Copyright (c) 2008-2021, Troy D. Hanson http://troydhanson.github.com/uthash/
59dd9d0cfSchristos All rights reserved.
69dd9d0cfSchristos
79dd9d0cfSchristos Redistribution and use in source and binary forms, with or without
89dd9d0cfSchristos modification, are permitted provided that the following conditions are met:
99dd9d0cfSchristos
109dd9d0cfSchristos * Redistributions of source code must retain the above copyright
119dd9d0cfSchristos notice, this list of conditions and the following disclaimer.
129dd9d0cfSchristos
139dd9d0cfSchristos THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
149dd9d0cfSchristos IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
159dd9d0cfSchristos TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
169dd9d0cfSchristos PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
179dd9d0cfSchristos OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
189dd9d0cfSchristos EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
199dd9d0cfSchristos PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
209dd9d0cfSchristos PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
219dd9d0cfSchristos LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
229dd9d0cfSchristos NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
239dd9d0cfSchristos SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
249dd9d0cfSchristos */
259dd9d0cfSchristos
269dd9d0cfSchristos /* a dynamic array implementation using macros
279dd9d0cfSchristos */
289dd9d0cfSchristos #ifndef UTARRAY_H
299dd9d0cfSchristos #define UTARRAY_H
309dd9d0cfSchristos
31bb7a167aSjkoshy #define UTARRAY_VERSION 2.3.0
329dd9d0cfSchristos
339dd9d0cfSchristos #include <stddef.h> /* size_t */
349dd9d0cfSchristos #include <string.h> /* memset, etc */
359dd9d0cfSchristos #include <stdlib.h> /* exit */
369dd9d0cfSchristos
371b4a9ac5Sjkoshy #ifdef __GNUC__
381b4a9ac5Sjkoshy #define UTARRAY_UNUSED __attribute__((__unused__))
391b4a9ac5Sjkoshy #else
401b4a9ac5Sjkoshy #define UTARRAY_UNUSED
411b4a9ac5Sjkoshy #endif
421b4a9ac5Sjkoshy
431b4a9ac5Sjkoshy #ifdef oom
441b4a9ac5Sjkoshy #error "The name of macro 'oom' has been changed to 'utarray_oom'. Please update your code."
451b4a9ac5Sjkoshy #define utarray_oom() oom()
461b4a9ac5Sjkoshy #endif
471b4a9ac5Sjkoshy
481b4a9ac5Sjkoshy #ifndef utarray_oom
491b4a9ac5Sjkoshy #define utarray_oom() exit(-1)
509dd9d0cfSchristos #endif
519dd9d0cfSchristos
529dd9d0cfSchristos typedef void (ctor_f)(void *dst, const void *src);
539dd9d0cfSchristos typedef void (dtor_f)(void *elt);
549dd9d0cfSchristos typedef void (init_f)(void *elt);
559dd9d0cfSchristos typedef struct {
569dd9d0cfSchristos size_t sz;
579dd9d0cfSchristos init_f *init;
589dd9d0cfSchristos ctor_f *copy;
599dd9d0cfSchristos dtor_f *dtor;
609dd9d0cfSchristos } UT_icd;
619dd9d0cfSchristos
629dd9d0cfSchristos typedef struct {
639dd9d0cfSchristos unsigned i,n;/* i: index of next available slot, n: num slots */
649dd9d0cfSchristos UT_icd icd; /* initializer, copy and destructor functions */
659dd9d0cfSchristos char *d; /* n slots of size icd->sz*/
669dd9d0cfSchristos } UT_array;
679dd9d0cfSchristos
689dd9d0cfSchristos #define utarray_init(a,_icd) do { \
699dd9d0cfSchristos memset(a,0,sizeof(UT_array)); \
701b4a9ac5Sjkoshy (a)->icd = *(_icd); \
719dd9d0cfSchristos } while(0)
729dd9d0cfSchristos
739dd9d0cfSchristos #define utarray_done(a) do { \
749dd9d0cfSchristos if ((a)->n) { \
759dd9d0cfSchristos if ((a)->icd.dtor) { \
761b4a9ac5Sjkoshy unsigned _ut_i; \
779dd9d0cfSchristos for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
789dd9d0cfSchristos (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \
799dd9d0cfSchristos } \
809dd9d0cfSchristos } \
819dd9d0cfSchristos free((a)->d); \
829dd9d0cfSchristos } \
839dd9d0cfSchristos (a)->n=0; \
849dd9d0cfSchristos } while(0)
859dd9d0cfSchristos
869dd9d0cfSchristos #define utarray_new(a,_icd) do { \
871b4a9ac5Sjkoshy (a) = (UT_array*)malloc(sizeof(UT_array)); \
881b4a9ac5Sjkoshy if ((a) == NULL) { \
891b4a9ac5Sjkoshy utarray_oom(); \
901b4a9ac5Sjkoshy } \
919dd9d0cfSchristos utarray_init(a,_icd); \
929dd9d0cfSchristos } while(0)
939dd9d0cfSchristos
949dd9d0cfSchristos #define utarray_free(a) do { \
959dd9d0cfSchristos utarray_done(a); \
969dd9d0cfSchristos free(a); \
979dd9d0cfSchristos } while(0)
989dd9d0cfSchristos
999dd9d0cfSchristos #define utarray_reserve(a,by) do { \
1001b4a9ac5Sjkoshy if (((a)->i+(by)) > (a)->n) { \
1011b4a9ac5Sjkoshy char *utarray_tmp; \
1021b4a9ac5Sjkoshy while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \
1031b4a9ac5Sjkoshy utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \
1041b4a9ac5Sjkoshy if (utarray_tmp == NULL) { \
1051b4a9ac5Sjkoshy utarray_oom(); \
1061b4a9ac5Sjkoshy } \
1071b4a9ac5Sjkoshy (a)->d=utarray_tmp; \
1089dd9d0cfSchristos } \
1099dd9d0cfSchristos } while(0)
1109dd9d0cfSchristos
1119dd9d0cfSchristos #define utarray_push_back(a,p) do { \
1129dd9d0cfSchristos utarray_reserve(a,1); \
1139dd9d0cfSchristos if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \
1149dd9d0cfSchristos else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \
1159dd9d0cfSchristos } while(0)
1169dd9d0cfSchristos
1179dd9d0cfSchristos #define utarray_pop_back(a) do { \
1189dd9d0cfSchristos if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \
1199dd9d0cfSchristos else { (a)->i--; } \
1209dd9d0cfSchristos } while(0)
1219dd9d0cfSchristos
1229dd9d0cfSchristos #define utarray_extend_back(a) do { \
1239dd9d0cfSchristos utarray_reserve(a,1); \
1249dd9d0cfSchristos if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \
1259dd9d0cfSchristos else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \
1269dd9d0cfSchristos (a)->i++; \
1279dd9d0cfSchristos } while(0)
1289dd9d0cfSchristos
1299dd9d0cfSchristos #define utarray_len(a) ((a)->i)
1309dd9d0cfSchristos
1319dd9d0cfSchristos #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)
1321b4a9ac5Sjkoshy #define _utarray_eltptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j))))
1339dd9d0cfSchristos
1349dd9d0cfSchristos #define utarray_insert(a,p,j) do { \
1351b4a9ac5Sjkoshy if ((j) > (a)->i) utarray_resize(a,j); \
1369dd9d0cfSchristos utarray_reserve(a,1); \
1379dd9d0cfSchristos if ((j) < (a)->i) { \
1389dd9d0cfSchristos memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \
1399dd9d0cfSchristos ((a)->i - (j))*((a)->icd.sz)); \
1409dd9d0cfSchristos } \
1419dd9d0cfSchristos if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \
1429dd9d0cfSchristos else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \
1439dd9d0cfSchristos (a)->i++; \
1449dd9d0cfSchristos } while(0)
1459dd9d0cfSchristos
1469dd9d0cfSchristos #define utarray_inserta(a,w,j) do { \
1479dd9d0cfSchristos if (utarray_len(w) == 0) break; \
1481b4a9ac5Sjkoshy if ((j) > (a)->i) utarray_resize(a,j); \
1499dd9d0cfSchristos utarray_reserve(a,utarray_len(w)); \
1509dd9d0cfSchristos if ((j) < (a)->i) { \
1519dd9d0cfSchristos memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \
1529dd9d0cfSchristos _utarray_eltptr(a,j), \
1539dd9d0cfSchristos ((a)->i - (j))*((a)->icd.sz)); \
1549dd9d0cfSchristos } \
1559dd9d0cfSchristos if ((a)->icd.copy) { \
1561b4a9ac5Sjkoshy unsigned _ut_i; \
1579dd9d0cfSchristos for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \
1581b4a9ac5Sjkoshy (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \
1599dd9d0cfSchristos } \
1609dd9d0cfSchristos } else { \
1619dd9d0cfSchristos memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \
1629dd9d0cfSchristos utarray_len(w)*((a)->icd.sz)); \
1639dd9d0cfSchristos } \
1649dd9d0cfSchristos (a)->i += utarray_len(w); \
1659dd9d0cfSchristos } while(0)
1669dd9d0cfSchristos
1679dd9d0cfSchristos #define utarray_resize(dst,num) do { \
1681b4a9ac5Sjkoshy unsigned _ut_i; \
1691b4a9ac5Sjkoshy if ((dst)->i > (unsigned)(num)) { \
1709dd9d0cfSchristos if ((dst)->icd.dtor) { \
1711b4a9ac5Sjkoshy for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) { \
1721b4a9ac5Sjkoshy (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i)); \
1739dd9d0cfSchristos } \
1749dd9d0cfSchristos } \
1751b4a9ac5Sjkoshy } else if ((dst)->i < (unsigned)(num)) { \
1761b4a9ac5Sjkoshy utarray_reserve(dst, (num) - (dst)->i); \
1779dd9d0cfSchristos if ((dst)->icd.init) { \
1781b4a9ac5Sjkoshy for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) { \
1791b4a9ac5Sjkoshy (dst)->icd.init(_utarray_eltptr(dst, _ut_i)); \
1809dd9d0cfSchristos } \
1819dd9d0cfSchristos } else { \
1821b4a9ac5Sjkoshy memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \
1839dd9d0cfSchristos } \
1849dd9d0cfSchristos } \
1851b4a9ac5Sjkoshy (dst)->i = (num); \
1869dd9d0cfSchristos } while(0)
1879dd9d0cfSchristos
1889dd9d0cfSchristos #define utarray_concat(dst,src) do { \
1891b4a9ac5Sjkoshy utarray_inserta(dst, src, utarray_len(dst)); \
1909dd9d0cfSchristos } while(0)
1919dd9d0cfSchristos
1929dd9d0cfSchristos #define utarray_erase(a,pos,len) do { \
1939dd9d0cfSchristos if ((a)->icd.dtor) { \
1941b4a9ac5Sjkoshy unsigned _ut_i; \
1951b4a9ac5Sjkoshy for (_ut_i = 0; _ut_i < (len); _ut_i++) { \
1961b4a9ac5Sjkoshy (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i)); \
1979dd9d0cfSchristos } \
1989dd9d0cfSchristos } \
1991b4a9ac5Sjkoshy if ((a)->i > ((pos) + (len))) { \
2001b4a9ac5Sjkoshy memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)), \
2011b4a9ac5Sjkoshy ((a)->i - ((pos) + (len))) * (a)->icd.sz); \
2029dd9d0cfSchristos } \
2039dd9d0cfSchristos (a)->i -= (len); \
2049dd9d0cfSchristos } while(0)
2059dd9d0cfSchristos
2069dd9d0cfSchristos #define utarray_renew(a,u) do { \
2079dd9d0cfSchristos if (a) utarray_clear(a); \
2081b4a9ac5Sjkoshy else utarray_new(a, u); \
2099dd9d0cfSchristos } while(0)
2109dd9d0cfSchristos
2119dd9d0cfSchristos #define utarray_clear(a) do { \
2129dd9d0cfSchristos if ((a)->i > 0) { \
2139dd9d0cfSchristos if ((a)->icd.dtor) { \
2141b4a9ac5Sjkoshy unsigned _ut_i; \
2159dd9d0cfSchristos for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
2161b4a9ac5Sjkoshy (a)->icd.dtor(_utarray_eltptr(a, _ut_i)); \
2179dd9d0cfSchristos } \
2189dd9d0cfSchristos } \
2199dd9d0cfSchristos (a)->i = 0; \
2209dd9d0cfSchristos } \
2219dd9d0cfSchristos } while(0)
2229dd9d0cfSchristos
2239dd9d0cfSchristos #define utarray_sort(a,cmp) do { \
2249dd9d0cfSchristos qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \
2259dd9d0cfSchristos } while(0)
2269dd9d0cfSchristos
2279dd9d0cfSchristos #define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)
2289dd9d0cfSchristos
2299dd9d0cfSchristos #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)
2301b4a9ac5Sjkoshy #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))
2311b4a9ac5Sjkoshy #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) != 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))
2329dd9d0cfSchristos #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)
2331b4a9ac5Sjkoshy #define utarray_eltidx(a,e) (((char*)(e) - (a)->d) / (a)->icd.sz)
2349dd9d0cfSchristos
2359dd9d0cfSchristos /* last we pre-define a few icd for common utarrays of ints and strings */
utarray_str_cpy(void * dst,const void * src)2369dd9d0cfSchristos static void utarray_str_cpy(void *dst, const void *src) {
237bb7a167aSjkoshy char *const *srcc = (char *const *)src;
238bb7a167aSjkoshy char **dstc = (char**)dst;
239bb7a167aSjkoshy *dstc = (*srcc == NULL) ? NULL : strdup(*srcc);
2409dd9d0cfSchristos }
utarray_str_dtor(void * elt)2419dd9d0cfSchristos static void utarray_str_dtor(void *elt) {
2429dd9d0cfSchristos char **eltc = (char**)elt;
2431b4a9ac5Sjkoshy if (*eltc != NULL) free(*eltc);
2449dd9d0cfSchristos }
2451b4a9ac5Sjkoshy static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
2461b4a9ac5Sjkoshy static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL};
2471b4a9ac5Sjkoshy static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL};
2489dd9d0cfSchristos
2499dd9d0cfSchristos
2509dd9d0cfSchristos #endif /* UTARRAY_H */
251