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