1*2de3b87aSKai Wang /*
2*2de3b87aSKai Wang Copyright (c) 2008-2013, Troy D. Hanson http://uthash.sourceforge.net
3*2de3b87aSKai Wang All rights reserved.
4*2de3b87aSKai Wang
5*2de3b87aSKai Wang Redistribution and use in source and binary forms, with or without
6*2de3b87aSKai Wang modification, are permitted provided that the following conditions are met:
7*2de3b87aSKai Wang
8*2de3b87aSKai Wang * Redistributions of source code must retain the above copyright
9*2de3b87aSKai Wang notice, this list of conditions and the following disclaimer.
10*2de3b87aSKai Wang
11*2de3b87aSKai Wang THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12*2de3b87aSKai Wang IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13*2de3b87aSKai Wang TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14*2de3b87aSKai Wang PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15*2de3b87aSKai Wang OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16*2de3b87aSKai Wang EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17*2de3b87aSKai Wang PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18*2de3b87aSKai Wang PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19*2de3b87aSKai Wang LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20*2de3b87aSKai Wang NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21*2de3b87aSKai Wang SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22*2de3b87aSKai Wang */
23*2de3b87aSKai Wang
24*2de3b87aSKai Wang /* $Id: utarray.h 2694 2012-11-24 17:11:58Z kaiwang27 $ */
25*2de3b87aSKai Wang
26*2de3b87aSKai Wang /* a dynamic array implementation using macros
27*2de3b87aSKai Wang * see http://uthash.sourceforge.net/utarray
28*2de3b87aSKai Wang */
29*2de3b87aSKai Wang #ifndef UTARRAY_H
30*2de3b87aSKai Wang #define UTARRAY_H
31*2de3b87aSKai Wang
32*2de3b87aSKai Wang #define UTARRAY_VERSION 1.9.7
33*2de3b87aSKai Wang
34*2de3b87aSKai Wang #ifdef __GNUC__
35*2de3b87aSKai Wang #define _UNUSED_ __attribute__ ((__unused__))
36*2de3b87aSKai Wang #else
37*2de3b87aSKai Wang #define _UNUSED_
38*2de3b87aSKai Wang #endif
39*2de3b87aSKai Wang
40*2de3b87aSKai Wang #include <stddef.h> /* size_t */
41*2de3b87aSKai Wang #include <string.h> /* memset, etc */
42*2de3b87aSKai Wang #include <stdlib.h> /* exit */
43*2de3b87aSKai Wang
44*2de3b87aSKai Wang #ifndef oom
45*2de3b87aSKai Wang #define oom() exit(-1)
46*2de3b87aSKai Wang #endif
47*2de3b87aSKai Wang
48*2de3b87aSKai Wang typedef void (ctor_f)(void *dst, const void *src);
49*2de3b87aSKai Wang typedef void (dtor_f)(void *elt);
50*2de3b87aSKai Wang typedef void (init_f)(void *elt);
51*2de3b87aSKai Wang typedef struct {
52*2de3b87aSKai Wang size_t sz;
53*2de3b87aSKai Wang init_f *init;
54*2de3b87aSKai Wang ctor_f *copy;
55*2de3b87aSKai Wang dtor_f *dtor;
56*2de3b87aSKai Wang } UT_icd;
57*2de3b87aSKai Wang
58*2de3b87aSKai Wang typedef struct {
59*2de3b87aSKai Wang unsigned i,n;/* i: index of next available slot, n: num slots */
60*2de3b87aSKai Wang UT_icd icd; /* initializer, copy and destructor functions */
61*2de3b87aSKai Wang char *d; /* n slots of size icd->sz*/
62*2de3b87aSKai Wang } UT_array;
63*2de3b87aSKai Wang
64*2de3b87aSKai Wang #define utarray_init(a,_icd) do { \
65*2de3b87aSKai Wang memset(a,0,sizeof(UT_array)); \
66*2de3b87aSKai Wang (a)->icd=*_icd; \
67*2de3b87aSKai Wang } while(0)
68*2de3b87aSKai Wang
69*2de3b87aSKai Wang #define utarray_done(a) do { \
70*2de3b87aSKai Wang if ((a)->n) { \
71*2de3b87aSKai Wang if ((a)->icd.dtor) { \
72*2de3b87aSKai Wang size_t _ut_i; \
73*2de3b87aSKai Wang for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
74*2de3b87aSKai Wang (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \
75*2de3b87aSKai Wang } \
76*2de3b87aSKai Wang } \
77*2de3b87aSKai Wang free((a)->d); \
78*2de3b87aSKai Wang } \
79*2de3b87aSKai Wang (a)->n=0; \
80*2de3b87aSKai Wang } while(0)
81*2de3b87aSKai Wang
82*2de3b87aSKai Wang #define utarray_new(a,_icd) do { \
83*2de3b87aSKai Wang a=(UT_array*)malloc(sizeof(UT_array)); \
84*2de3b87aSKai Wang utarray_init(a,_icd); \
85*2de3b87aSKai Wang } while(0)
86*2de3b87aSKai Wang
87*2de3b87aSKai Wang #define utarray_free(a) do { \
88*2de3b87aSKai Wang utarray_done(a); \
89*2de3b87aSKai Wang free(a); \
90*2de3b87aSKai Wang } while(0)
91*2de3b87aSKai Wang
92*2de3b87aSKai Wang #define utarray_reserve(a,by) do { \
93*2de3b87aSKai Wang if (((a)->i+by) > ((a)->n)) { \
94*2de3b87aSKai Wang while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \
95*2de3b87aSKai Wang if ( ((a)->d=(char*)realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) oom(); \
96*2de3b87aSKai Wang } \
97*2de3b87aSKai Wang } while(0)
98*2de3b87aSKai Wang
99*2de3b87aSKai Wang #define utarray_push_back(a,p) do { \
100*2de3b87aSKai Wang utarray_reserve(a,1); \
101*2de3b87aSKai Wang if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \
102*2de3b87aSKai Wang else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \
103*2de3b87aSKai Wang } while(0)
104*2de3b87aSKai Wang
105*2de3b87aSKai Wang #define utarray_pop_back(a) do { \
106*2de3b87aSKai Wang if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \
107*2de3b87aSKai Wang else { (a)->i--; } \
108*2de3b87aSKai Wang } while(0)
109*2de3b87aSKai Wang
110*2de3b87aSKai Wang #define utarray_extend_back(a) do { \
111*2de3b87aSKai Wang utarray_reserve(a,1); \
112*2de3b87aSKai Wang if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \
113*2de3b87aSKai Wang else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \
114*2de3b87aSKai Wang (a)->i++; \
115*2de3b87aSKai Wang } while(0)
116*2de3b87aSKai Wang
117*2de3b87aSKai Wang #define utarray_len(a) ((a)->i)
118*2de3b87aSKai Wang
119*2de3b87aSKai Wang #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)
120*2de3b87aSKai Wang #define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) )))
121*2de3b87aSKai Wang
122*2de3b87aSKai Wang #define utarray_insert(a,p,j) do { \
123*2de3b87aSKai Wang utarray_reserve(a,1); \
124*2de3b87aSKai Wang if (j > (a)->i) break; \
125*2de3b87aSKai Wang if ((j) < (a)->i) { \
126*2de3b87aSKai Wang memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \
127*2de3b87aSKai Wang ((a)->i - (j))*((a)->icd.sz)); \
128*2de3b87aSKai Wang } \
129*2de3b87aSKai Wang if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \
130*2de3b87aSKai Wang else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \
131*2de3b87aSKai Wang (a)->i++; \
132*2de3b87aSKai Wang } while(0)
133*2de3b87aSKai Wang
134*2de3b87aSKai Wang #define utarray_inserta(a,w,j) do { \
135*2de3b87aSKai Wang if (utarray_len(w) == 0) break; \
136*2de3b87aSKai Wang if (j > (a)->i) break; \
137*2de3b87aSKai Wang utarray_reserve(a,utarray_len(w)); \
138*2de3b87aSKai Wang if ((j) < (a)->i) { \
139*2de3b87aSKai Wang memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \
140*2de3b87aSKai Wang _utarray_eltptr(a,j), \
141*2de3b87aSKai Wang ((a)->i - (j))*((a)->icd.sz)); \
142*2de3b87aSKai Wang } \
143*2de3b87aSKai Wang if ((a)->icd.copy) { \
144*2de3b87aSKai Wang size_t _ut_i; \
145*2de3b87aSKai Wang for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \
146*2de3b87aSKai Wang (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \
147*2de3b87aSKai Wang } \
148*2de3b87aSKai Wang } else { \
149*2de3b87aSKai Wang memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \
150*2de3b87aSKai Wang utarray_len(w)*((a)->icd.sz)); \
151*2de3b87aSKai Wang } \
152*2de3b87aSKai Wang (a)->i += utarray_len(w); \
153*2de3b87aSKai Wang } while(0)
154*2de3b87aSKai Wang
155*2de3b87aSKai Wang #define utarray_resize(dst,num) do { \
156*2de3b87aSKai Wang size_t _ut_i; \
157*2de3b87aSKai Wang if (dst->i > (size_t)(num)) { \
158*2de3b87aSKai Wang if ((dst)->icd.dtor) { \
159*2de3b87aSKai Wang for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \
160*2de3b87aSKai Wang (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \
161*2de3b87aSKai Wang } \
162*2de3b87aSKai Wang } \
163*2de3b87aSKai Wang } else if (dst->i < (size_t)(num)) { \
164*2de3b87aSKai Wang utarray_reserve(dst,num-dst->i); \
165*2de3b87aSKai Wang if ((dst)->icd.init) { \
166*2de3b87aSKai Wang for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \
167*2de3b87aSKai Wang (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \
168*2de3b87aSKai Wang } \
169*2de3b87aSKai Wang } else { \
170*2de3b87aSKai Wang memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \
171*2de3b87aSKai Wang } \
172*2de3b87aSKai Wang } \
173*2de3b87aSKai Wang dst->i = num; \
174*2de3b87aSKai Wang } while(0)
175*2de3b87aSKai Wang
176*2de3b87aSKai Wang #define utarray_concat(dst,src) do { \
177*2de3b87aSKai Wang utarray_inserta((dst),(src),utarray_len(dst)); \
178*2de3b87aSKai Wang } while(0)
179*2de3b87aSKai Wang
180*2de3b87aSKai Wang #define utarray_erase(a,pos,len) do { \
181*2de3b87aSKai Wang if ((a)->icd.dtor) { \
182*2de3b87aSKai Wang size_t _ut_i; \
183*2de3b87aSKai Wang for(_ut_i=0; _ut_i < len; _ut_i++) { \
184*2de3b87aSKai Wang (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \
185*2de3b87aSKai Wang } \
186*2de3b87aSKai Wang } \
187*2de3b87aSKai Wang if ((a)->i > (pos+len)) { \
188*2de3b87aSKai Wang memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \
189*2de3b87aSKai Wang (((a)->i)-(pos+len))*((a)->icd.sz)); \
190*2de3b87aSKai Wang } \
191*2de3b87aSKai Wang (a)->i -= (len); \
192*2de3b87aSKai Wang } while(0)
193*2de3b87aSKai Wang
194*2de3b87aSKai Wang #define utarray_renew(a,u) do { \
195*2de3b87aSKai Wang if (a) utarray_clear(a); \
196*2de3b87aSKai Wang else utarray_new((a),(u)); \
197*2de3b87aSKai Wang } while(0)
198*2de3b87aSKai Wang
199*2de3b87aSKai Wang #define utarray_clear(a) do { \
200*2de3b87aSKai Wang if ((a)->i > 0) { \
201*2de3b87aSKai Wang if ((a)->icd.dtor) { \
202*2de3b87aSKai Wang size_t _ut_i; \
203*2de3b87aSKai Wang for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
204*2de3b87aSKai Wang (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \
205*2de3b87aSKai Wang } \
206*2de3b87aSKai Wang } \
207*2de3b87aSKai Wang (a)->i = 0; \
208*2de3b87aSKai Wang } \
209*2de3b87aSKai Wang } while(0)
210*2de3b87aSKai Wang
211*2de3b87aSKai Wang #define utarray_sort(a,cmp) do { \
212*2de3b87aSKai Wang qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \
213*2de3b87aSKai Wang } while(0)
214*2de3b87aSKai Wang
215*2de3b87aSKai Wang #define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)
216*2de3b87aSKai Wang
217*2de3b87aSKai Wang #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)
218*2de3b87aSKai Wang #define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : (((int)((a)->i) > (utarray_eltidx(a,e)+1)) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL))
219*2de3b87aSKai Wang #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))
220*2de3b87aSKai Wang #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)
221*2de3b87aSKai Wang #define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (int)(((char*)(e) - (char*)((a)->d))/(a)->icd.sz) : -1)
222*2de3b87aSKai Wang
223*2de3b87aSKai Wang /* last we pre-define a few icd for common utarrays of ints and strings */
utarray_str_cpy(void * dst,const void * src)224*2de3b87aSKai Wang static void utarray_str_cpy(void *dst, const void *src) {
225*2de3b87aSKai Wang char *const*_src = (char*const*)src, **_dst = (char**)dst;
226*2de3b87aSKai Wang *_dst = (*_src == NULL) ? NULL : strdup(*_src);
227*2de3b87aSKai Wang }
utarray_str_dtor(void * elt)228*2de3b87aSKai Wang static void utarray_str_dtor(void *elt) {
229*2de3b87aSKai Wang char **eltc = (char**)elt;
230*2de3b87aSKai Wang if (*eltc) free(*eltc);
231*2de3b87aSKai Wang }
232*2de3b87aSKai Wang static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
233*2de3b87aSKai Wang static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL};
234*2de3b87aSKai Wang static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL};
235*2de3b87aSKai Wang
236*2de3b87aSKai Wang
237*2de3b87aSKai Wang #endif /* UTARRAY_H */
238