1 /*
2 Copyright (c) 2008-2010, 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
31
32 #ifdef __GNUC__
33 #define _UNUSED_ __attribute__ ((__unused__))
34 #else
35 #define _UNUSED_
36 #endif
37
38 #include <stddef.h> /* size_t */
39 #include <string.h> /* memset, etc */
40 #include <stdlib.h> /* exit */
41
42 #define oom() exit(-1)
43
44 typedef void (ctor_f)(void *dst, const void *src);
45 typedef void (dtor_f)(void *elt);
46 typedef void (init_f)(void *elt);
47 typedef struct {
48 size_t sz;
49 init_f *init;
50 ctor_f *copy;
51 dtor_f *dtor;
52 } UT_icd;
53
54 typedef struct {
55 unsigned i, n; /* i: index of next available slot, n: num slots */
56 const UT_icd *icd; /* initializer, copy and destructor functions */
57 char *d; /* n slots of size icd->sz*/
58 } UT_array;
59
60 #define utarray_init(a, _icd) do { \
61 memset(a, 0, sizeof(UT_array)); \
62 (a)->icd = _icd; \
63 } while(0)
64
65 #define utarray_done(a) do { \
66 if ((a)->n) { \
67 if ((a)->icd->dtor) { \
68 size_t _ut_i; \
69 for(_ut_i = 0;_ut_i < (a)->i;_ut_i++) { \
70 (a)->icd->dtor(utarray_eltptr(a, _ut_i)); \
71 } \
72 } \
73 free((a)->d); \
74 } \
75 (a)->n = 0; \
76 } while(0)
77
78 #define utarray_steal(a, p) do { \
79 if (!(a)->n) { \
80 p = NULL; \
81 break; \
82 } \
83 p = (a)->d; \
84 (a)->d = NULL; \
85 (a)->n = (a)->i = 0; \
86 } while(0)
87
88 #define utarray_new(a, _icd) do { \
89 a = (UT_array*)malloc(sizeof(UT_array)); \
90 utarray_init(a, _icd); \
91 } while(0)
92
93 #define utarray_free(a) do { \
94 utarray_done(a); \
95 free(a); \
96 } while(0)
97
98 #define utarray_reserve(a, by) do { \
99 if (((a)->i + by) > ((a)->n)) { \
100 while(((a)->i + by) > ((a)->n)) { \
101 (a)->n = ((a)->n ? (2 * (a)->n) : 8); \
102 } \
103 if (!((a)->d = (char*)realloc((a)->d, (a)->n * (a)->icd->sz))) { \
104 oom(); \
105 } \
106 } \
107 } while(0)
108
109 #define utarray_push_back(a, p) do { \
110 utarray_reserve(a, 1); \
111 if ((a)->icd->copy) { \
112 (a)->icd->copy(_utarray_eltptr(a, (a)->i++), p); \
113 } else { \
114 memcpy(_utarray_eltptr(a, (a)->i++), p, (a)->icd->sz); \
115 }; \
116 } while(0)
117
118 #define utarray_pop_back(a) do { \
119 if ((a)->icd->dtor) { \
120 (a)->icd->dtor(_utarray_eltptr(a, --((a)->i))); \
121 } else { \
122 (a)->i--; \
123 } \
124 } while(0)
125
126 #define utarray_extend_back(a) do { \
127 utarray_reserve(a, 1); \
128 if ((a)->icd->init) { \
129 (a)->icd->init(_utarray_eltptr(a, (a)->i)); \
130 } else { \
131 memset(_utarray_eltptr(a, (a)->i), 0, (a)->icd->sz); \
132 } \
133 (a)->i++; \
134 } while(0)
135
136 #define utarray_len(a) ((a)->i)
137
138 #define utarray_eltptr(a, j) (((j) < (a)->i) ? _utarray_eltptr(a, j) : NULL)
139 #define _utarray_eltptr(a, j) ((char*)((a)->d + ((a)->icd->sz * (j))))
140
141 #define utarray_push_front(a, p) do { \
142 utarray_reserve(a, 1); \
143 if (0 < (a)->i) { \
144 memmove(_utarray_eltptr(a, 1), _utarray_eltptr(a, 0), \
145 ((a)->i) * ((a)->icd->sz)); \
146 } \
147 if ((a)->icd->copy) { \
148 (a)->icd->copy(_utarray_eltptr(a, 0), p); \
149 } else { \
150 memcpy(_utarray_eltptr(a, 0), p, (a)->icd->sz); \
151 }; \
152 (a)->i++; \
153 } while(0)
154
155 #define utarray_insert(a, p, j) do { \
156 utarray_reserve(a, 1); \
157 if (j > (a)->i) \
158 break; \
159 if ((j) < (a)->i) { \
160 memmove(_utarray_eltptr(a, (j) + 1), _utarray_eltptr(a, j), \
161 ((a)->i - (j)) * ((a)->icd->sz)); \
162 } \
163 if ((a)->icd->copy) { \
164 (a)->icd->copy(_utarray_eltptr(a, j), p); \
165 } else { \
166 memcpy(_utarray_eltptr(a, j), p, (a)->icd->sz); \
167 }; \
168 (a)->i++; \
169 } while(0)
170
171 #define utarray_move(a, f, t) do { \
172 if (f >= (a)->i) \
173 break; \
174 if (t >= (a)->i) \
175 break; \
176 if (f == t) \
177 break; \
178 void *_temp = malloc((a)->icd->sz); \
179 if (f > t) { \
180 memcpy(_temp, _utarray_eltptr(a, f), (a)->icd->sz); \
181 memmove(_utarray_eltptr(a, t + 1), _utarray_eltptr(a, t), \
182 (a)->icd->sz * (f - (t))); \
183 memcpy(_utarray_eltptr(a, t), _temp, (a)->icd->sz); \
184 } else { \
185 memcpy(_temp, _utarray_eltptr(a, f), (a)->icd->sz); \
186 memmove(_utarray_eltptr(a, f), _utarray_eltptr(a, f + 1), \
187 (a)->icd->sz * (t - (f))); \
188 memcpy(_utarray_eltptr(a, t), _temp, (a)->icd->sz); \
189 } \
190 free(_temp); \
191 } while(0)
192
193 #define utarray_inserta(a, w, j) do { \
194 if (utarray_len(w) == 0) \
195 break; \
196 if (j > (a)->i) \
197 break; \
198 utarray_reserve(a, utarray_len(w)); \
199 if ((j) < (a)->i) { \
200 memmove(_utarray_eltptr(a, (j) + utarray_len(w)), \
201 _utarray_eltptr(a, j), \
202 ((a)->i - (j)) * ((a)->icd->sz)); \
203 } \
204 if ((a)->icd->copy) { \
205 size_t _ut_i; \
206 for(_ut_i = 0;_ut_i < (w)->i;_ut_i++) { \
207 (a)->icd->copy(_utarray_eltptr(a, j + _ut_i), \
208 _utarray_eltptr(w, _ut_i)); \
209 } \
210 } else { \
211 memcpy(_utarray_eltptr(a, j), _utarray_eltptr(w, 0), \
212 utarray_len(w) * ((a)->icd->sz)); \
213 } \
214 (a)->i += utarray_len(w); \
215 } while(0)
216
217 #define utarray_resize(dst, num) do { \
218 size_t _ut_i; \
219 if ((dst)->i > (size_t)(num)) { \
220 if ((dst)->icd->dtor) { \
221 for (_ut_i = num;_ut_i < (dst)->i;_ut_i++) { \
222 (dst)->icd->dtor(utarray_eltptr(dst, _ut_i)); \
223 } \
224 } \
225 } else if ((dst)->i < (size_t)(num)) { \
226 utarray_reserve(dst, num - (dst)->i); \
227 if ((dst)->icd->init) { \
228 for (_ut_i = (dst)->i;_ut_i < num;_ut_i++) { \
229 (dst)->icd->init(utarray_eltptr(dst, _ut_i)); \
230 } \
231 } else { \
232 memset(_utarray_eltptr(dst, (dst)->i), 0, \
233 (dst)->icd->sz * (num - (dst)->i)); \
234 } \
235 } \
236 (dst)->i = num; \
237 } while(0)
238
239 #define utarray_concat(dst, src) do { \
240 utarray_inserta(dst, src, utarray_len(dst)); \
241 } while(0)
242
243 #define utarray_erase(a, pos, len) do { \
244 if ((a)->icd->dtor) { \
245 size_t _ut_i; \
246 for(_ut_i = 0;_ut_i < len;_ut_i++) { \
247 (a)->icd->dtor(utarray_eltptr(a, pos + _ut_i)); \
248 } \
249 } \
250 if ((a)->i > (pos + len)) { \
251 memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, pos + len), \
252 (((a)->i) - (pos + len)) * ((a)->icd->sz)); \
253 } \
254 (a)->i -= (len); \
255 } while(0)
256
257 /**
258 * this actually steal the content away, doesn't destroy the content
259 * so the name doesn't actually accurate, use it carefully.
260 */
261 #define utarray_remove_quick(a, pos) do { \
262 if ((a)->i - 1 != (pos)) \
263 memcpy(_utarray_eltptr(a, pos), _utarray_eltptr(a, (a)->i - 1), \
264 (a)->icd->sz); \
265 (a)->i--; \
266 } while(0)
267
268 /**
269 * this is the "real" remove_quick with destroy,
270 */
271 #define utarray_remove_quick_full(a, pos) do { \
272 if ((a)->icd->dtor) { \
273 (a)->icd->dtor(utarray_eltptr(a, pos)); \
274 } \
275 if ((a)->i - 1 != (pos)) \
276 memcpy(_utarray_eltptr(a, pos), _utarray_eltptr(a, (a)->i - 1), \
277 (a)->icd->sz); \
278 (a)->i--; \
279 } while(0)
280
281 #define utarray_clear(a) do { \
282 if ((a)->i > 0) { \
283 if ((a)->icd->dtor) { \
284 size_t _ut_i; \
285 for(_ut_i = 0;_ut_i < (a)->i;_ut_i++) { \
286 (a)->icd->dtor(utarray_eltptr(a, _ut_i)); \
287 } \
288 } \
289 (a)->i = 0; \
290 } \
291 } while(0)
292
293 #define utarray_sort(a, cmp) do { \
294 qsort((a)->d, (a)->i, (a)->icd->sz, cmp); \
295 } while(0)
296
297 #define utarray_sort_range(a, cmp, from, to) do { \
298 if ((from) >= (to) || (from) >= (a)->i || (to) > (a)->i) \
299 break; \
300 qsort(_utarray_eltptr(a, from), (to) - (from), (a)->icd->sz, cmp); \
301 } while(0)
302
303 void fcitx_qsort_r(void *base_, size_t nmemb, size_t size,
304 int (*compar)(const void *, const void *, void *),
305 void *thunk);
306 void fcitx_msort_r(void *base_, size_t nmemb, size_t size,
307 int (*compar)(const void *, const void *, void *),
308 void *thunk);
309
310 #define utarray_sort_r(a, cmp, arg) do { \
311 fcitx_qsort_r((a)->d, (a)->i, (a)->icd->sz, cmp, arg); \
312 } while(0)
313
314 #define utarray_msort_r(a, cmp, arg) do { \
315 fcitx_msort_r((a)->d, (a)->i, (a)->icd->sz, cmp, arg); \
316 } while(0)
317
318 #define utarray_eltidx(a, e) (((char*)(e) >= (char*)((a)->d)) ? \
319 (((char*)(e) - (char*)((a)->d)) / (a)->icd->sz) : \
320 -1)
321 #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a, 0)) : NULL)
322 #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a, (a)->i - 1)) : NULL)
323 #define utarray_next(a, e) (((e) == NULL) ? utarray_front(a) : \
324 ((((a)->i) > (utarray_eltidx(a, e) + 1)) ? \
325 _utarray_eltptr(a, utarray_eltidx(a, e) + 1) : \
326 NULL))
327 static inline void*
utarray_prev(UT_array * a,void * e)328 utarray_prev(UT_array *a, void *e)
329 {
330 if (!e)
331 return utarray_back(a);
332 int idx = utarray_eltidx(a, e) - 1;
333 if (idx < 0)
334 return NULL;
335 return _utarray_eltptr(a, idx);
336 }
337
338 /* last we pre-define a few icd for common utarrays of ints and strings */
utarray_str_cpy(void * dst,const void * src)339 static void utarray_str_cpy(void *dst, const void *src)
340 {
341 char **_src = (char**)src, **_dst = (char**)dst;
342 *_dst = (*_src == NULL) ? NULL : strdup(*_src);
343 }
utarray_str_dtor(void * elt)344 static void utarray_str_dtor(void *elt)
345 {
346 char **eltc = (char**)elt;
347 if (*eltc)
348 free(*eltc);
349 }
350
351 static const UT_icd ut_str_icd _UNUSED_ = {
352 sizeof(char*), NULL, utarray_str_cpy, utarray_str_dtor
353 };
354 static const UT_icd ut_int_icd _UNUSED_ = {
355 sizeof(int), NULL, NULL, NULL
356 };
357
358 #define utarray_custom_bsearch(key, a, acc, cmp) \
359 fcitx_utils_custom_bsearch(key, (a)->d, (a)->i, (a)->icd->sz, acc, cmp)
360
361 #define utarray_foreach(key, array, type) \
362 type *key; \
363 for (key = (type*)utarray_front(array);key; \
364 key = (type*)utarray_next((array), key))
365
366 static inline UT_array*
utarray_clone(const UT_array * from)367 utarray_clone(const UT_array *from)
368 {
369 UT_array *to;
370 utarray_new(to, from->icd);
371 if (utarray_len(from) == 0)
372 return to;
373 utarray_reserve(to, utarray_len(from));
374 if (to->icd->copy) {
375 size_t i;
376 for(i = 0;i < from->i;i++) {
377 to->icd->copy(_utarray_eltptr(to, i), _utarray_eltptr(from, i));
378 }
379 } else {
380 memcpy(_utarray_eltptr(to, 0), _utarray_eltptr(from, 0),
381 utarray_len(from) * (to->icd->sz));
382 }
383 to->i = utarray_len(from);
384 return to;
385 }
386
387 #endif /* UTARRAY_H */
388
389 // kate: indent-mode cstyle; space-indent on; indent-width 0;
390