1 | /*␊ |
2 | Copyright (c) 2008-2012, 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.6␊ |
31 | ␊ |
32 | #ifdef __GNUC__␊ |
33 | #define _UNUSED_ __attribute__ ((__unused__)) ␊ |
34 | #else␊ |
35 | #define _UNUSED_ ␊ |
36 | #endif␊ |
37 | ␊ |
38 | #include "libsaio.h"␊ |
39 | ␊ |
40 | #ifndef utarray_oom␊ |
41 | #define utarray_oom() longjmp(uterror,-1)␊ |
42 | #endif␊ |
43 | #ifndef __utarray_malloc␊ |
44 | #define __utarray_malloc(sz) malloc(sz) /* malloc fcn */␊ |
45 | #endif␊ |
46 | #ifndef __utarray_free␊ |
47 | #define __utarray_free(ptr) free(ptr) /* free fcn */␊ |
48 | #endif␊ |
49 | #ifndef __utarray_realloc␊ |
50 | #define __utarray_realloc(ptr,sz) realloc(ptr,sz) /* realloc fcn */␊ |
51 | #endif␊ |
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 | size_t _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 | __utarray_free((a)->d); \␊ |
82 | } \␊ |
83 | (a)->n=0; \␊ |
84 | } while(0)␊ |
85 | ␊ |
86 | #define utarray_new(a,_icd) do { \␊ |
87 | a=(UT_array*)utarray_malloc(sizeof(UT_array)); \␊ |
88 | utarray_init(a,_icd); \␊ |
89 | } while(0)␊ |
90 | ␊ |
91 | #define utarray_free(a) do { \␊ |
92 | utarray_done(a); \␊ |
93 | __utarray_free(a); \␊ |
94 | } while(0)␊ |
95 | ␊ |
96 | #define utarray_reserve(a,by) do { \␊ |
97 | if (((a)->i+by) > ((a)->n)) { \␊ |
98 | while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \␊ |
99 | if ( ((a)->d=(char*)__utarray_realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) utarray_oom(); \␊ |
100 | } \␊ |
101 | } while(0)␊ |
102 | ␊ |
103 | #define utarray_push_back(a,p) do { \␊ |
104 | utarray_reserve(a,1); \␊ |
105 | if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \␊ |
106 | else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \␊ |
107 | } while(0)␊ |
108 | ␊ |
109 | #define utarray_pop_back(a) do { \␊ |
110 | if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \␊ |
111 | else { (a)->i--; } \␊ |
112 | } while(0)␊ |
113 | ␊ |
114 | #define utarray_extend_back(a) do { \␊ |
115 | utarray_reserve(a,1); \␊ |
116 | if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \␊ |
117 | else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \␊ |
118 | (a)->i++; \␊ |
119 | } while(0)␊ |
120 | ␊ |
121 | #define utarray_len(a) ((a)->i)␊ |
122 | ␊ |
123 | #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)␊ |
124 | #define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) )))␊ |
125 | ␊ |
126 | #define utarray_insert(a,p,j) do { \␊ |
127 | utarray_reserve(a,1); \␊ |
128 | if (j > (a)->i) break; \␊ |
129 | if ((j) < (a)->i) { \␊ |
130 | memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \␊ |
131 | ((a)->i - (j))*((a)->icd.sz)); \␊ |
132 | } \␊ |
133 | if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \␊ |
134 | else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \␊ |
135 | (a)->i++; \␊ |
136 | } while(0)␊ |
137 | ␊ |
138 | #define utarray_inserta(a,w,j) do { \␊ |
139 | if (utarray_len(w) == 0) break; \␊ |
140 | if (j > (a)->i) break; \␊ |
141 | utarray_reserve(a,utarray_len(w)); \␊ |
142 | if ((j) < (a)->i) { \␊ |
143 | memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \␊ |
144 | _utarray_eltptr(a,j), \␊ |
145 | ((a)->i - (j))*((a)->icd.sz)); \␊ |
146 | } \␊ |
147 | if ((a)->icd.copy) { \␊ |
148 | size_t _ut_i; \␊ |
149 | for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \␊ |
150 | (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \␊ |
151 | } \␊ |
152 | } else { \␊ |
153 | memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \␊ |
154 | utarray_len(w)*((a)->icd.sz)); \␊ |
155 | } \␊ |
156 | (a)->i += utarray_len(w); \␊ |
157 | } while(0)␊ |
158 | ␊ |
159 | #define utarray_resize(dst,num) do { \␊ |
160 | size_t _ut_i; \␊ |
161 | if (dst->i > (size_t)(num)) { \␊ |
162 | if ((dst)->icd.dtor) { \␊ |
163 | for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \␊ |
164 | (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \␊ |
165 | } \␊ |
166 | } \␊ |
167 | } else if (dst->i < (size_t)(num)) { \␊ |
168 | utarray_reserve(dst,num-dst->i); \␊ |
169 | if ((dst)->icd.init) { \␊ |
170 | for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \␊ |
171 | (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \␊ |
172 | } \␊ |
173 | } else { \␊ |
174 | memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \␊ |
175 | } \␊ |
176 | } \␊ |
177 | dst->i = num; \␊ |
178 | } while(0)␊ |
179 | ␊ |
180 | #define utarray_concat(dst,src) do { \␊ |
181 | utarray_inserta((dst),(src),utarray_len(dst)); \␊ |
182 | } while(0)␊ |
183 | ␊ |
184 | #define utarray_erase(a,pos,len) do { \␊ |
185 | if ((a)->icd.dtor) { \␊ |
186 | size_t _ut_i; \␊ |
187 | for(_ut_i=0; _ut_i < len; _ut_i++) { \␊ |
188 | (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \␊ |
189 | } \␊ |
190 | } \␊ |
191 | if ((a)->i > (pos+len)) { \␊ |
192 | memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \␊ |
193 | (((a)->i)-(pos+len))*((a)->icd.sz)); \␊ |
194 | } \␊ |
195 | (a)->i -= (len); \␊ |
196 | } while(0)␊ |
197 | ␊ |
198 | #define utarray_renew(a,u) do { \␊ |
199 | if (a) utarray_clear(a); \␊ |
200 | else utarray_new((a),(u)); \␊ |
201 | } while(0)␊ |
202 | ␊ |
203 | #define utarray_clear(a) do { \␊ |
204 | if ((a)->i > 0) { \␊ |
205 | if ((a)->icd.dtor) { \␊ |
206 | size_t _ut_i; \␊ |
207 | for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \␊ |
208 | (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \␊ |
209 | } \␊ |
210 | } \␊ |
211 | (a)->i = 0; \␊ |
212 | } \␊ |
213 | } while(0)␊ |
214 | ␊ |
215 | #define utarray_sort(a,cmp) do { \␊ |
216 | qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \␊ |
217 | } while(0)␊ |
218 | ␊ |
219 | #define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)␊ |
220 | ␊ |
221 | #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)␊ |
222 | #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))␊ |
223 | #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))␊ |
224 | #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)␊ |
225 | #define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(a)->icd.sz) : -1)␊ |
226 | ␊ |
227 | /* last we pre-define a few icd for common utarrays of ints and strings */␊ |
228 | static void utarray_str_cpy(void *dst, const void *src) {␊ |
229 | char **_src = (char**)src, **_dst = (char**)dst;␊ |
230 | *_dst = (*_src == NULL) ? NULL : strdup(*_src);␊ |
231 | }␊ |
232 | static void utarray_str_dtor(void *elt) {␊ |
233 | char **eltc = (char**)elt;␊ |
234 | if (*eltc) __utarray_free(*eltc);␊ |
235 | }␊ |
236 | static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};␊ |
237 | static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL};␊ |
238 | static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL};␊ |
239 | ␊ |
240 | ␊ |
241 | #endif /* UTARRAY_H */␊ |
242 | |