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