PX4 Firmware
PX4 Autopilot Software http://px4.io
utlist.h
Go to the documentation of this file.
1
/*
2
Copyright (c) 2007-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
#ifndef UTLIST_H
25
#define UTLIST_H
26
27
#define UTLIST_VERSION 1.9.6
28
29
#include <assert.h>
30
31
/*
32
* This file contains macros to manipulate singly and doubly-linked lists.
33
*
34
* 1. LL_ macros: singly-linked lists.
35
* 2. DL_ macros: doubly-linked lists.
36
* 3. CDL_ macros: circular doubly-linked lists.
37
*
38
* To use singly-linked lists, your structure must have a "next" pointer.
39
* To use doubly-linked lists, your structure must "prev" and "next" pointers.
40
* Either way, the pointer to the head of the list must be initialized to NULL.
41
*
42
* ----------------.EXAMPLE -------------------------
43
* struct item {
44
* int id;
45
* struct item *prev, *next;
46
* }
47
*
48
* struct item *list = NULL:
49
*
50
* int main() {
51
* struct item *item;
52
* ... allocate and populate item ...
53
* DL_APPEND(list, item);
54
* }
55
* --------------------------------------------------
56
*
57
* For doubly-linked lists, the append and delete macros are O(1)
58
* For singly-linked lists, append and delete are O(n) but prepend is O(1)
59
* The sort macro is O(n log(n)) for all types of single/double/circular lists.
60
*/
61
62
/* These macros use decltype or the earlier __typeof GNU extension.
63
As decltype is only available in newer compilers (VS2010 or gcc 4.3+
64
when compiling c++ code), this code uses whatever method is needed
65
or, for VS2008 where neither is available, uses casting workarounds. */
66
#ifdef _MSC_VER
/* MS compiler */
67
#if _MSC_VER >= 1600 && defined(__cplusplus)
/* VS2010 or newer in C++ mode */
68
#define LDECLTYPE(x) decltype(x)
69
#else
/* VS2008 or older (or VS2010 in C mode) */
70
#define NO_DECLTYPE
71
#define LDECLTYPE(x) char*
72
#endif
73
#else
/* GNU, Sun and other compilers */
74
#define LDECLTYPE(x) __typeof(x)
75
#endif
76
77
/* for VS2008 we use some workarounds to get around the lack of decltype,
78
* namely, we always reassign our tmp variable to the list head if we need
79
* to dereference its prev/next pointers, and save/restore the real head.*/
80
#ifdef NO_DECLTYPE
81
#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
82
#define _NEXT(elt,list) ((char*)((list)->next))
83
#define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
84
#define _PREV(elt,list) ((char*)((list)->prev))
85
#define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
86
#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
87
#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
88
#else
89
#define _SV(elt,list)
90
#define _NEXT(elt,list) ((elt)->next)
91
#define _NEXTASGN(elt,list,to) ((elt)->next)=(to)
92
#define _PREV(elt,list) ((elt)->prev)
93
#define _PREVASGN(elt,list,to) ((elt)->prev)=(to)
94
#define _RS(list)
95
#define _CASTASGN(a,b) (a)=(b)
96
#endif
97
98
/******************************************************************************
99
* The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
100
* Unwieldy variable names used here to avoid shadowing passed-in variables. *
101
*****************************************************************************/
102
#define LL_SORT(list, cmp) \
103
do { \
104
LDECLTYPE(list) _ls_p; \
105
LDECLTYPE(list) _ls_q; \
106
LDECLTYPE(list) _ls_e; \
107
LDECLTYPE(list) _ls_tail; \
108
LDECLTYPE(list) _ls_oldhead; \
109
LDECLTYPE(list) _tmp; \
110
int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
111
if (list) { \
112
_ls_insize = 1; \
113
_ls_looping = 1; \
114
while (_ls_looping) { \
115
_CASTASGN(_ls_p,list); \
116
_CASTASGN(_ls_oldhead,list); \
117
list = NULL; \
118
_ls_tail = NULL; \
119
_ls_nmerges = 0; \
120
while (_ls_p) { \
121
_ls_nmerges++; \
122
_ls_q = _ls_p; \
123
_ls_psize = 0; \
124
for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
125
_ls_psize++; \
126
_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
127
if (!_ls_q) break; \
128
} \
129
_ls_qsize = _ls_insize; \
130
while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
131
if (_ls_psize == 0) { \
132
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
133
} else if (_ls_qsize == 0 || !_ls_q) { \
134
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
135
} else if (cmp(_ls_p,_ls_q) <= 0) { \
136
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
137
} else { \
138
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
139
} \
140
if (_ls_tail) { \
141
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
142
} else { \
143
_CASTASGN(list,_ls_e); \
144
} \
145
_ls_tail = _ls_e; \
146
} \
147
_ls_p = _ls_q; \
148
} \
149
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
150
if (_ls_nmerges <= 1) { \
151
_ls_looping=0; \
152
} \
153
_ls_insize *= 2; \
154
} \
155
} else _tmp=NULL;
/* quiet gcc unused variable warning */
\
156
} while (0)
157
158
#define DL_SORT(list, cmp) \
159
do { \
160
LDECLTYPE(list) _ls_p; \
161
LDECLTYPE(list) _ls_q; \
162
LDECLTYPE(list) _ls_e; \
163
LDECLTYPE(list) _ls_tail; \
164
LDECLTYPE(list) _ls_oldhead; \
165
LDECLTYPE(list) _tmp; \
166
int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
167
if (list) { \
168
_ls_insize = 1; \
169
_ls_looping = 1; \
170
while (_ls_looping) { \
171
_CASTASGN(_ls_p,list); \
172
_CASTASGN(_ls_oldhead,list); \
173
list = NULL; \
174
_ls_tail = NULL; \
175
_ls_nmerges = 0; \
176
while (_ls_p) { \
177
_ls_nmerges++; \
178
_ls_q = _ls_p; \
179
_ls_psize = 0; \
180
for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
181
_ls_psize++; \
182
_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
183
if (!_ls_q) break; \
184
} \
185
_ls_qsize = _ls_insize; \
186
while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
187
if (_ls_psize == 0) { \
188
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
189
} else if (_ls_qsize == 0 || !_ls_q) { \
190
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
191
} else if (cmp(_ls_p,_ls_q) <= 0) { \
192
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
193
} else { \
194
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
195
} \
196
if (_ls_tail) { \
197
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
198
} else { \
199
_CASTASGN(list,_ls_e); \
200
} \
201
_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
202
_ls_tail = _ls_e; \
203
} \
204
_ls_p = _ls_q; \
205
} \
206
_CASTASGN(list->prev, _ls_tail); \
207
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
208
if (_ls_nmerges <= 1) { \
209
_ls_looping=0; \
210
} \
211
_ls_insize *= 2; \
212
} \
213
} else _tmp=NULL;
/* quiet gcc unused variable warning */
\
214
} while (0)
215
216
#define CDL_SORT(list, cmp) \
217
do { \
218
LDECLTYPE(list) _ls_p; \
219
LDECLTYPE(list) _ls_q; \
220
LDECLTYPE(list) _ls_e; \
221
LDECLTYPE(list) _ls_tail; \
222
LDECLTYPE(list) _ls_oldhead; \
223
LDECLTYPE(list) _tmp; \
224
LDECLTYPE(list) _tmp2; \
225
int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
226
if (list) { \
227
_ls_insize = 1; \
228
_ls_looping = 1; \
229
while (_ls_looping) { \
230
_CASTASGN(_ls_p,list); \
231
_CASTASGN(_ls_oldhead,list); \
232
list = NULL; \
233
_ls_tail = NULL; \
234
_ls_nmerges = 0; \
235
while (_ls_p) { \
236
_ls_nmerges++; \
237
_ls_q = _ls_p; \
238
_ls_psize = 0; \
239
for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
240
_ls_psize++; \
241
_SV(_ls_q,list); \
242
if (_NEXT(_ls_q,list) == _ls_oldhead) { \
243
_ls_q = NULL; \
244
} else { \
245
_ls_q = _NEXT(_ls_q,list); \
246
} \
247
_RS(list); \
248
if (!_ls_q) break; \
249
} \
250
_ls_qsize = _ls_insize; \
251
while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
252
if (_ls_psize == 0) { \
253
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
254
if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
255
} else if (_ls_qsize == 0 || !_ls_q) { \
256
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
257
if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
258
} else if (cmp(_ls_p,_ls_q) <= 0) { \
259
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
260
if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
261
} else { \
262
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
263
if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
264
} \
265
if (_ls_tail) { \
266
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
267
} else { \
268
_CASTASGN(list,_ls_e); \
269
} \
270
_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
271
_ls_tail = _ls_e; \
272
} \
273
_ls_p = _ls_q; \
274
} \
275
_CASTASGN(list->prev,_ls_tail); \
276
_CASTASGN(_tmp2,list); \
277
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \
278
if (_ls_nmerges <= 1) { \
279
_ls_looping=0; \
280
} \
281
_ls_insize *= 2; \
282
} \
283
} else _tmp=NULL;
/* quiet gcc unused variable warning */
\
284
} while (0)
285
286
/******************************************************************************
287
* singly linked list macros (non-circular) *
288
*****************************************************************************/
289
#define LL_PREPEND(head,add) \
290
do { \
291
(add)->next = head; \
292
head = add; \
293
} while (0)
294
295
#define LL_CONCAT(head1,head2) \
296
do { \
297
LDECLTYPE(head1) _tmp; \
298
if (head1) { \
299
_tmp = head1; \
300
while (_tmp->next) { _tmp = _tmp->next; } \
301
_tmp->next=(head2); \
302
} else { \
303
(head1)=(head2); \
304
} \
305
} while (0)
306
307
#define LL_APPEND(head,add) \
308
do { \
309
LDECLTYPE(head) _tmp; \
310
(add)->next=NULL; \
311
if (head) { \
312
_tmp = head; \
313
while (_tmp->next) { _tmp = _tmp->next; } \
314
_tmp->next=(add); \
315
} else { \
316
(head)=(add); \
317
} \
318
} while (0)
319
320
#define LL_DELETE(head,del) \
321
do { \
322
LDECLTYPE(head) _tmp; \
323
if ((head) == (del)) { \
324
(head)=(head)->next; \
325
} else { \
326
_tmp = head; \
327
while (_tmp->next && (_tmp->next != (del))) { \
328
_tmp = _tmp->next; \
329
} \
330
if (_tmp->next) { \
331
_tmp->next = ((del)->next); \
332
} \
333
} \
334
} while (0)
335
336
/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
337
#define LL_APPEND_VS2008(head,add) \
338
do { \
339
if (head) { \
340
(add)->next = head;
/* use add->next as a temp variable */
\
341
while ((add)->next->next) { (add)->next = (add)->next->next; } \
342
(add)->next->next=(add); \
343
} else { \
344
(head)=(add); \
345
} \
346
(add)->next=NULL; \
347
} while (0)
348
349
#define LL_DELETE_VS2008(head,del) \
350
do { \
351
if ((head) == (del)) { \
352
(head)=(head)->next; \
353
} else { \
354
char *_tmp = (char*)(head); \
355
while ((head)->next && ((head)->next != (del))) { \
356
head = (head)->next; \
357
} \
358
if ((head)->next) { \
359
(head)->next = ((del)->next); \
360
} \
361
{ \
362
char **_head_alias = (char**)&(head); \
363
*_head_alias = _tmp; \
364
} \
365
} \
366
} while (0)
367
#ifdef NO_DECLTYPE
368
#undef LL_APPEND
369
#define LL_APPEND LL_APPEND_VS2008
370
#undef LL_DELETE
371
#define LL_DELETE LL_DELETE_VS2008
372
#undef LL_CONCAT
/* no LL_CONCAT_VS2008 */
373
#undef DL_CONCAT
/* no DL_CONCAT_VS2008 */
374
#endif
375
/* end VS2008 replacements */
376
377
#define LL_FOREACH(head,el) \
378
for(el=head;el;el=(el)->next)
379
380
#define LL_FOREACH_SAFE(head,el,tmp) \
381
for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
382
383
#define LL_SEARCH_SCALAR(head,out,field,val) \
384
do { \
385
LL_FOREACH(head,out) { \
386
if ((out)->field == (val)) break; \
387
} \
388
} while(0)
389
390
#define LL_SEARCH(head,out,elt,cmp) \
391
do { \
392
LL_FOREACH(head,out) { \
393
if ((cmp(out,elt))==0) break; \
394
} \
395
} while(0)
396
397
/******************************************************************************
398
* doubly linked list macros (non-circular) *
399
*****************************************************************************/
400
#define DL_PREPEND(head,add) \
401
do { \
402
(add)->next = head; \
403
if (head) { \
404
(add)->prev = (head)->prev; \
405
(head)->prev = (add); \
406
} else { \
407
(add)->prev = (add); \
408
} \
409
(head) = (add); \
410
} while (0)
411
412
#define DL_APPEND(head,add) \
413
do { \
414
if (head) { \
415
(add)->prev = (head)->prev; \
416
(head)->prev->next = (add); \
417
(head)->prev = (add); \
418
(add)->next = NULL; \
419
} else { \
420
(head)=(add); \
421
(head)->prev = (head); \
422
(head)->next = NULL; \
423
} \
424
} while (0)
425
426
#define DL_CONCAT(head1,head2) \
427
do { \
428
LDECLTYPE(head1) _tmp; \
429
if (head2) { \
430
if (head1) { \
431
_tmp = (head2)->prev; \
432
(head2)->prev = (head1)->prev; \
433
(head1)->prev->next = (head2); \
434
(head1)->prev = _tmp; \
435
} else { \
436
(head1)=(head2); \
437
} \
438
} \
439
} while (0)
440
441
#define DL_DELETE(head,del) \
442
do { \
443
assert((del)->prev != NULL); \
444
if ((del)->prev == (del)) { \
445
(head)=NULL; \
446
} else if ((del)==(head)) { \
447
(del)->next->prev = (del)->prev; \
448
(head) = (del)->next; \
449
} else { \
450
(del)->prev->next = (del)->next; \
451
if ((del)->next) { \
452
(del)->next->prev = (del)->prev; \
453
} else { \
454
(head)->prev = (del)->prev; \
455
} \
456
} \
457
} while (0)
458
459
460
#define DL_FOREACH(head,el) \
461
for(el=head;el;el=(el)->next)
462
463
/* this version is safe for deleting the elements during iteration */
464
#define DL_FOREACH_SAFE(head,el,tmp) \
465
for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
466
467
/* these are identical to their singly-linked list counterparts */
468
#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
469
#define DL_SEARCH LL_SEARCH
470
471
/******************************************************************************
472
* circular doubly linked list macros *
473
*****************************************************************************/
474
#define CDL_PREPEND(head,add) \
475
do { \
476
if (head) { \
477
(add)->prev = (head)->prev; \
478
(add)->next = (head); \
479
(head)->prev = (add); \
480
(add)->prev->next = (add); \
481
} else { \
482
(add)->prev = (add); \
483
(add)->next = (add); \
484
} \
485
(head)=(add); \
486
} while (0)
487
488
#define CDL_DELETE(head,del) \
489
do { \
490
if ( ((head)==(del)) && ((head)->next == (head))) { \
491
(head) = 0L; \
492
} else { \
493
(del)->next->prev = (del)->prev; \
494
(del)->prev->next = (del)->next; \
495
if ((del) == (head)) (head)=(del)->next; \
496
} \
497
} while (0)
498
499
#define CDL_FOREACH(head,el) \
500
for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
501
502
#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
503
for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
504
(el) && ((tmp2)=(el)->next, 1); \
505
((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
506
507
#define CDL_SEARCH_SCALAR(head,out,field,val) \
508
do { \
509
CDL_FOREACH(head,out) { \
510
if ((out)->field == (val)) break; \
511
} \
512
} while(0)
513
514
#define CDL_SEARCH(head,out,elt,cmp) \
515
do { \
516
CDL_FOREACH(head,out) { \
517
if ((cmp(out,elt))==0) break; \
518
} \
519
} while(0)
520
521
#endif
/* UTLIST_H */
522
src
lib
systemlib
uthash
utlist.h
Generated by
1.8.13
1.8.13 1.8.13