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