1 /* $NetBSD: utarray.h,v 1.5 2024/03/03 17:37:29 christos Exp $ */
2
3 /*-
4 Copyright (c) 2008-2021, Troy D. Hanson http://troydhanson.github.com/uthash/
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, 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
13 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
14 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
15 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
16 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
17 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
21 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
22 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23 SOFTWARE, 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
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 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 */
utarray_str_cpy(void * dst,const void * src)236 static 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 }
utarray_str_dtor(void * elt)241 static void utarray_str_dtor(void *elt) {
242 char **eltc = (char**)elt;
243 if (*eltc != NULL) free(*eltc);
244 }
245 static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
246 static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL};
247 static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL};
248
249
250 #endif /* UTARRAY_H */
251