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