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