1 /*
2 Copyright (c) 2008-2018, Troy D. Hanson http://troydhanson.github.com/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.1.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) ((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) ? (((char*)(e) - (a)->d)/(a)->icd.sz) : -1)
232
233 /* last we pre-define a few icd for common utarrays of ints and strings */
utarray_str_cpy(void * dst,const void * src)234 static void utarray_str_cpy(void *dst, const void *src) {
235 char **_src = (char**)src, **_dst = (char**)dst;
236 *_dst = (*_src == NULL) ? NULL : strdup(*_src);
237 }
utarray_str_dtor(void * elt)238 static void utarray_str_dtor(void *elt) {
239 char **eltc = (char**)elt;
240 if (*eltc != NULL) free(*eltc);
241 }
242 static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
243 static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL};
244 static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL};
245
246
247 #endif /* UTARRAY_H */
248