PX4 Firmware
PX4 Autopilot Software http://px4.io
utarray.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2008-2012, 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.6
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 // FIXME: this needs to be checked: we need to handle OOM properly instead of just exiting
43 #define oom() system_exit(-1)
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  size_t _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  utarray_init(a,_icd); \
82 } while(0)
83 
84 #define utarray_free(a) do { \
85  utarray_done(a); \
86  free(a); \
87 } while(0)
88 
89 #define utarray_reserve(a,by) do { \
90  if (((a)->i+by) > ((a)->n)) { \
91  while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \
92  if ( ((a)->d=(char*)realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) oom(); \
93  } \
94 } while(0)
95 
96 #define utarray_push_back(a,p) do { \
97  utarray_reserve(a,1); \
98  if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \
99  else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \
100 } while(0)
101 
102 #define utarray_pop_back(a) do { \
103  if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \
104  else { (a)->i--; } \
105 } while(0)
106 
107 #define utarray_extend_back(a) do { \
108  utarray_reserve(a,1); \
109  if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \
110  else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \
111  (a)->i++; \
112 } while(0)
113 
114 #define utarray_len(a) ((a)->i)
115 
116 #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)
117 #define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) )))
118 
119 #define utarray_insert(a,p,j) do { \
120  utarray_reserve(a,1); \
121  if (j > (a)->i) break; \
122  if ((j) < (a)->i) { \
123  memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \
124  ((a)->i - (j))*((a)->icd.sz)); \
125  } \
126  if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \
127  else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \
128  (a)->i++; \
129 } while(0)
130 
131 #define utarray_inserta(a,w,j) do { \
132  if (utarray_len(w) == 0) break; \
133  if (j > (a)->i) break; \
134  utarray_reserve(a,utarray_len(w)); \
135  if ((j) < (a)->i) { \
136  memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \
137  _utarray_eltptr(a,j), \
138  ((a)->i - (j))*((a)->icd.sz)); \
139  } \
140  if ((a)->icd.copy) { \
141  size_t _ut_i; \
142  for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \
143  (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \
144  } \
145  } else { \
146  memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \
147  utarray_len(w)*((a)->icd.sz)); \
148  } \
149  (a)->i += utarray_len(w); \
150 } while(0)
151 
152 #define utarray_resize(dst,num) do { \
153  size_t _ut_i; \
154  if (dst->i > (size_t)(num)) { \
155  if ((dst)->icd.dtor) { \
156  for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \
157  (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \
158  } \
159  } \
160  } else if (dst->i < (size_t)(num)) { \
161  utarray_reserve(dst,num-dst->i); \
162  if ((dst)->icd.init) { \
163  for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \
164  (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \
165  } \
166  } else { \
167  memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \
168  } \
169  } \
170  dst->i = num; \
171 } while(0)
172 
173 #define utarray_concat(dst,src) do { \
174  utarray_inserta((dst),(src),utarray_len(dst)); \
175 } while(0)
176 
177 #define utarray_erase(a,pos,len) do { \
178  if ((a)->icd.dtor) { \
179  size_t _ut_i; \
180  for(_ut_i=0; _ut_i < len; _ut_i++) { \
181  (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \
182  } \
183  } \
184  if ((a)->i > (pos+len)) { \
185  memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \
186  (((a)->i)-(pos+len))*((a)->icd.sz)); \
187  } \
188  (a)->i -= (len); \
189 } while(0)
190 
191 #define utarray_renew(a,u) do { \
192  if (a) utarray_clear(a); \
193  else utarray_new((a),(u)); \
194 } while(0)
195 
196 #define utarray_clear(a) do { \
197  if ((a)->i > 0) { \
198  if ((a)->icd.dtor) { \
199  size_t _ut_i; \
200  for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \
201  (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \
202  } \
203  } \
204  (a)->i = 0; \
205  } \
206 } while(0)
207 
208 #define utarray_sort(a,cmp) do { \
209  qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \
210 } while(0)
211 
212 #define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)
213 
214 #define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)
215 #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))
216 #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))
217 #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)
218 #define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(a)->icd.sz) : -1)
219 
220 /* last we pre-define a few icd for common utarrays of ints and strings */
221 static void utarray_str_cpy(void *dst, const void *src) {
222  char **_src = (char**)src, **_dst = (char**)dst;
223  *_dst = (*_src == NULL) ? NULL : strdup(*_src);
224 }
225 static void utarray_str_dtor(void *elt) {
226  char **eltc = (char**)elt;
227  if (*eltc) free(*eltc);
228 }
229 static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
230 static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL};
231 static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL};
232 
233 
234 #endif /* UTARRAY_H */
_UNUSED_
#define _UNUSED_
Definition: utarray.h:35
utarray_str_dtor
static void utarray_str_dtor(void *elt)
Definition: utarray.h:225
UT_icd::dtor
dtor_f * dtor
Definition: utarray.h:52
UT_icd::sz
size_t sz
Definition: utarray.h:49
init_f
void() init_f(void *elt)
Definition: utarray.h:47
UT_array
Definition: utarray.h:55
UT_array::icd
UT_icd icd
Definition: utarray.h:57
dtor_f
void() dtor_f(void *elt)
Definition: utarray.h:46
UT_icd::copy
ctor_f * copy
Definition: utarray.h:51
UT_array::n
unsigned n
Definition: utarray.h:56
UT_array::d
char * d
Definition: utarray.h:58
UT_icd::init
init_f * init
Definition: utarray.h:50
ctor_f
void() ctor_f(void *dst, const void *src)
Definition: utarray.h:45
utarray_str_cpy
static void utarray_str_cpy(void *dst, const void *src)
Definition: utarray.h:221
UT_icd
Definition: utarray.h:48