BOROSOFTWAREAll work →
← scantool/utlist.h 1079 lines
1/* prevent uncrustify from parsing this file : *INDENT-OFF* */
2/*
3Copyright (c) 2007-2018, Troy D. Hanson http://troydhanson.github.com/uthash/
4All rights reserved.
5
6Redistribution and use in source and binary forms, with or without
7modification, are permitted provided that the following conditions are met:
8
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11
12THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
13IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
14TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
15PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
16OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
17EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
18PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
19PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
20LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
21NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23
24 * NOTE !! LL_APPEND() is virtually identical to LL_CONCAT, except
25 * _APPEND can *only* add a single element (it sets ->next=NULL !)
26 * Hence, there is no real reason to ever use _APPEND()...
27*/
28
29#ifndef UTLIST_H
30#define UTLIST_H
31
32#define UTLIST_VERSION 2.1.0
33
34#include <assert.h>
35
36/*
37 * This file contains macros to manipulate singly and doubly-linked lists.
38 *
39 * 1. LL_ macros: singly-linked lists.
40 * 2. DL_ macros: doubly-linked lists.
41 * 3. CDL_ macros: circular doubly-linked lists.
42 *
43 * To use singly-linked lists, your structure must have a "next" pointer.
44 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
45 * Either way, the pointer to the head of the list must be initialized to NULL.
46 *
47 * ----------------.EXAMPLE -------------------------
48 * struct item {
49 * int id;
50 * struct item *prev, *next;
51 * }
52 *
53 * struct item *list = NULL:
54 *
55 * int main() {
56 * struct item *item;
57 * ... allocate and populate item ...
58 * DL_APPEND(list, item);
59 * }
60 * --------------------------------------------------
61 *
62 * For doubly-linked lists, the append and delete macros are O(1)
63 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
64 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
65 */
66
67/* These macros use decltype or the earlier __typeof GNU extension.
68 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
69 when compiling c++ source) this code uses whatever method is needed
70 or, for VS2008 where neither is available, uses casting workarounds. */
71#if !defined(LDECLTYPE) && !defined(NO_DECLTYPE)
72#if defined(_MSC_VER) /* MS compiler */
73#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
74#define LDECLTYPE(x) decltype(x)
75#else /* VS2008 or older (or VS2010 in C mode) */
76#define NO_DECLTYPE
77#endif
78#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__)
79#define NO_DECLTYPE
80#else /* GNU, Sun and other compilers */
81#define LDECLTYPE(x) __typeof(x)
82#endif
83#endif
84
85/* for VS2008 we use some workarounds to get around the lack of decltype,
86 * namely, we always reassign our tmp variable to the list head if we need
87 * to dereference its prev/next pointers, and save/restore the real head.*/
88#ifdef NO_DECLTYPE
89#define IF_NO_DECLTYPE(x) x
90#define LDECLTYPE(x) char*
91#define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
92#define UTLIST_NEXT(elt,list,next) ((char*)((list)->next))
93#define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
94/* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */
95#define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
96#define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
97#define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
98#else
99#define IF_NO_DECLTYPE(x)
100#define UTLIST_SV(elt,list)
101#define UTLIST_NEXT(elt,list,next) ((elt)->next)
102#define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
103/* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */
104#define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
105#define UTLIST_RS(list)
106#define UTLIST_CASTASGN(a,b) (a)=(b)
107#endif
108
109/******************************************************************************
110 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
111 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
112 *****************************************************************************/
113#define LL_SORT(list, cmp) \
114 LL_SORT2(list, cmp, next)
115
116#define LL_SORT2(list, cmp, next) \
117do { \
118 LDECLTYPE(list) _ls_p; \
119 LDECLTYPE(list) _ls_q; \
120 LDECLTYPE(list) _ls_e; \
121 LDECLTYPE(list) _ls_tail; \
122 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \
123 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
124 if (list) { \
125 _ls_insize = 1; \
126 _ls_looping = 1; \
127 while (_ls_looping) { \
128 UTLIST_CASTASGN(_ls_p,list); \
129 (list) = NULL; \
130 _ls_tail = NULL; \
131 _ls_nmerges = 0; \
132 while (_ls_p) { \
133 _ls_nmerges++; \
134 _ls_q = _ls_p; \
135 _ls_psize = 0; \
136 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
137 _ls_psize++; \
138 UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \
139 if (!_ls_q) break; \
140 } \
141 _ls_qsize = _ls_insize; \
142 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
143 if (_ls_psize == 0) { \
144 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
145 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
146 } else if (_ls_qsize == 0 || !_ls_q) { \
147 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
148 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
149 } else if (cmp(_ls_p,_ls_q) <= 0) { \
150 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
151 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
152 } else { \
153 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
154 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
155 } \
156 if (_ls_tail) { \
157 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
158 } else { \
159 UTLIST_CASTASGN(list,_ls_e); \
160 } \
161 _ls_tail = _ls_e; \
162 } \
163 _ls_p = _ls_q; \
164 } \
165 if (_ls_tail) { \
166 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \
167 } \
168 if (_ls_nmerges <= 1) { \
169 _ls_looping=0; \
170 } \
171 _ls_insize *= 2; \
172 } \
173 } \
174} while (0)
175
176
177#define DL_SORT(list, cmp) \
178 DL_SORT2(list, cmp, prev, next)
179
180#define DL_SORT2(list, cmp, prev, next) \
181do { \
182 LDECLTYPE(list) _ls_p; \
183 LDECLTYPE(list) _ls_q; \
184 LDECLTYPE(list) _ls_e; \
185 LDECLTYPE(list) _ls_tail; \
186 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \
187 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
188 if (list) { \
189 _ls_insize = 1; \
190 _ls_looping = 1; \
191 while (_ls_looping) { \
192 UTLIST_CASTASGN(_ls_p,list); \
193 (list) = NULL; \
194 _ls_tail = NULL; \
195 _ls_nmerges = 0; \
196 while (_ls_p) { \
197 _ls_nmerges++; \
198 _ls_q = _ls_p; \
199 _ls_psize = 0; \
200 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
201 _ls_psize++; \
202 UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \
203 if (!_ls_q) break; \
204 } \
205 _ls_qsize = _ls_insize; \
206 while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \
207 if (_ls_psize == 0) { \
208 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
209 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
210 } else if ((_ls_qsize == 0) || (!_ls_q)) { \
211 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
212 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
213 } else if (cmp(_ls_p,_ls_q) <= 0) { \
214 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
215 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
216 } else { \
217 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
218 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
219 } \
220 if (_ls_tail) { \
221 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
222 } else { \
223 UTLIST_CASTASGN(list,_ls_e); \
224 } \
225 UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \
226 _ls_tail = _ls_e; \
227 } \
228 _ls_p = _ls_q; \
229 } \
230 UTLIST_CASTASGN((list)->prev, _ls_tail); \
231 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \
232 if (_ls_nmerges <= 1) { \
233 _ls_looping=0; \
234 } \
235 _ls_insize *= 2; \
236 } \
237 } \
238} while (0)
239
240#define CDL_SORT(list, cmp) \
241 CDL_SORT2(list, cmp, prev, next)
242
243#define CDL_SORT2(list, cmp, prev, next) \
244do { \
245 LDECLTYPE(list) _ls_p; \
246 LDECLTYPE(list) _ls_q; \
247 LDECLTYPE(list) _ls_e; \
248 LDECLTYPE(list) _ls_tail; \
249 LDECLTYPE(list) _ls_oldhead; \
250 LDECLTYPE(list) _tmp; \
251 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
252 if (list) { \
253 _ls_insize = 1; \
254 _ls_looping = 1; \
255 while (_ls_looping) { \
256 UTLIST_CASTASGN(_ls_p,list); \
257 UTLIST_CASTASGN(_ls_oldhead,list); \
258 (list) = NULL; \
259 _ls_tail = NULL; \
260 _ls_nmerges = 0; \
261 while (_ls_p) { \
262 _ls_nmerges++; \
263 _ls_q = _ls_p; \
264 _ls_psize = 0; \
265 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
266 _ls_psize++; \
267 UTLIST_SV(_ls_q,list); \
268 if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) { \
269 _ls_q = NULL; \
270 } else { \
271 _ls_q = UTLIST_NEXT(_ls_q,list,next); \
272 } \
273 UTLIST_RS(list); \
274 if (!_ls_q) break; \
275 } \
276 _ls_qsize = _ls_insize; \
277 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
278 if (_ls_psize == 0) { \
279 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
280 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
281 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
282 } else if (_ls_qsize == 0 || !_ls_q) { \
283 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
284 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
285 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
286 } else if (cmp(_ls_p,_ls_q) <= 0) { \
287 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \
288 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \
289 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
290 } else { \
291 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \
292 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \
293 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
294 } \
295 if (_ls_tail) { \
296 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \
297 } else { \
298 UTLIST_CASTASGN(list,_ls_e); \
299 } \
300 UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \
301 _ls_tail = _ls_e; \
302 } \
303 _ls_p = _ls_q; \
304 } \
305 UTLIST_CASTASGN((list)->prev,_ls_tail); \
306 UTLIST_CASTASGN(_tmp,list); \
307 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list); \
308 if (_ls_nmerges <= 1) { \
309 _ls_looping=0; \
310 } \
311 _ls_insize *= 2; \
312 } \
313 } \
314} while (0)
315
316/******************************************************************************
317 * singly linked list macros (non-circular) *
318 *****************************************************************************/
319#define LL_PREPEND(head,add) \
320 LL_PREPEND2(head,add,next)
321
322#define LL_PREPEND2(head,add,next) \
323do { \
324 (add)->next = (head); \
325 (head) = (add); \
326} while (0)
327
328#define LL_CONCAT(head1,head2) \
329 LL_CONCAT2(head1,head2,next)
330
331#define LL_CONCAT2(head1,head2,next) \
332do { \
333 LDECLTYPE(head1) _tmp; \
334 if (head1) { \
335 _tmp = (head1); \
336 while (_tmp->next) { _tmp = _tmp->next; } \
337 _tmp->next=(head2); \
338 } else { \
339 (head1)=(head2); \
340 } \
341} while (0)
342
343#define LL_APPEND(head,add) \
344 LL_APPEND2(head,add,next)
345
346#define LL_APPEND2(head,add,next) \
347do { \
348 LDECLTYPE(head) _tmp; \
349 (add)->next=NULL; \
350 if (head) { \
351 _tmp = (head); \
352 while (_tmp->next) { _tmp = _tmp->next; } \
353 _tmp->next=(add); \
354 } else { \
355 (head)=(add); \
356 } \
357} while (0)
358
359#define LL_INSERT_INORDER(head,add,cmp) \
360 LL_INSERT_INORDER2(head,add,cmp,next)
361
362#define LL_INSERT_INORDER2(head,add,cmp,next) \
363do { \
364 LDECLTYPE(head) _tmp; \
365 if (head) { \
366 LL_LOWER_BOUND2(head, _tmp, add, cmp, next); \
367 LL_APPEND_ELEM2(head, _tmp, add, next); \
368 } else { \
369 (head) = (add); \
370 (head)->next = NULL; \
371 } \
372} while (0)
373
374#define LL_LOWER_BOUND(head,elt,like,cmp) \
375 LL_LOWER_BOUND2(head,elt,like,cmp,next)
376
377#define LL_LOWER_BOUND2(head,elt,like,cmp,next) \
378 do { \
379 if ((head) == NULL || (cmp(head, like)) >= 0) { \
380 (elt) = NULL; \
381 } else { \
382 for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \
383 if (cmp((elt)->next, like) >= 0) { \
384 break; \
385 } \
386 } \
387 } \
388 } while (0)
389
390#define LL_DELETE(head,del) \
391 LL_DELETE2(head,del,next)
392
393#define LL_DELETE2(head,del,next) \
394do { \
395 LDECLTYPE(head) _tmp; \
396 if ((head) == (del)) { \
397 (head)=(head)->next; \
398 } else { \
399 _tmp = (head); \
400 while (_tmp->next && (_tmp->next != (del))) { \
401 _tmp = _tmp->next; \
402 } \
403 if (_tmp->next) { \
404 _tmp->next = (del)->next; \
405 } \
406 } \
407} while (0)
408
409#define LL_COUNT(head,el,counter) \
410 LL_COUNT2(head,el,counter,next) \
411
412#define LL_COUNT2(head,el,counter,next) \
413do { \
414 (counter) = 0; \
415 LL_FOREACH2(head,el,next) { ++(counter); } \
416} while (0)
417
418#define LL_FOREACH(head,el) \
419 LL_FOREACH2(head,el,next)
420
421#define LL_FOREACH2(head,el,next) \
422 for ((el) = (head); el; (el) = (el)->next)
423
424#define LL_FOREACH_SAFE(head,el,tmp) \
425 LL_FOREACH_SAFE2(head,el,tmp,next)
426
427#define LL_FOREACH_SAFE2(head,el,tmp,next) \
428 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
429
430#define LL_SEARCH_SCALAR(head,out,field,val) \
431 LL_SEARCH_SCALAR2(head,out,field,val,next)
432
433#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
434do { \
435 LL_FOREACH2(head,out,next) { \
436 if ((out)->field == (val)) break; \
437 } \
438} while (0)
439
440#define LL_SEARCH(head,out,elt,cmp) \
441 LL_SEARCH2(head,out,elt,cmp,next)
442
443#define LL_SEARCH2(head,out,elt,cmp,next) \
444do { \
445 LL_FOREACH2(head,out,next) { \
446 if ((cmp(out,elt))==0) break; \
447 } \
448} while (0)
449
450#define LL_REPLACE_ELEM2(head, el, add, next) \
451do { \
452 LDECLTYPE(head) _tmp; \
453 assert((head) != NULL); \
454 assert((el) != NULL); \
455 assert((add) != NULL); \
456 (add)->next = (el)->next; \
457 if ((head) == (el)) { \
458 (head) = (add); \
459 } else { \
460 _tmp = (head); \
461 while (_tmp->next && (_tmp->next != (el))) { \
462 _tmp = _tmp->next; \
463 } \
464 if (_tmp->next) { \
465 _tmp->next = (add); \
466 } \
467 } \
468} while (0)
469
470#define LL_REPLACE_ELEM(head, el, add) \
471 LL_REPLACE_ELEM2(head, el, add, next)
472
473#define LL_PREPEND_ELEM2(head, el, add, next) \
474do { \
475 if (el) { \
476 LDECLTYPE(head) _tmp; \
477 assert((head) != NULL); \
478 assert((add) != NULL); \
479 (add)->next = (el); \
480 if ((head) == (el)) { \
481 (head) = (add); \
482 } else { \
483 _tmp = (head); \
484 while (_tmp->next && (_tmp->next != (el))) { \
485 _tmp = _tmp->next; \
486 } \
487 if (_tmp->next) { \
488 _tmp->next = (add); \
489 } \
490 } \
491 } else { \
492 LL_APPEND2(head, add, next); \
493 } \
494} while (0) \
495
496#define LL_PREPEND_ELEM(head, el, add) \
497 LL_PREPEND_ELEM2(head, el, add, next)
498
499#define LL_APPEND_ELEM2(head, el, add, next) \
500do { \
501 if (el) { \
502 assert((head) != NULL); \
503 assert((add) != NULL); \
504 (add)->next = (el)->next; \
505 (el)->next = (add); \
506 } else { \
507 LL_PREPEND2(head, add, next); \
508 } \
509} while (0) \
510
511#define LL_APPEND_ELEM(head, el, add) \
512 LL_APPEND_ELEM2(head, el, add, next)
513
514#ifdef NO_DECLTYPE
515/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
516
517#undef LL_CONCAT2
518#define LL_CONCAT2(head1,head2,next) \
519do { \
520 char *_tmp; \
521 if (head1) { \
522 _tmp = (char*)(head1); \
523 while ((head1)->next) { (head1) = (head1)->next; } \
524 (head1)->next = (head2); \
525 UTLIST_RS(head1); \
526 } else { \
527 (head1)=(head2); \
528 } \
529} while (0)
530
531#undef LL_APPEND2
532#define LL_APPEND2(head,add,next) \
533do { \
534 if (head) { \
535 (add)->next = head; /* use add->next as a temp variable */ \
536 while ((add)->next->next) { (add)->next = (add)->next->next; } \
537 (add)->next->next=(add); \
538 } else { \
539 (head)=(add); \
540 } \
541 (add)->next=NULL; \
542} while (0)
543
544#undef LL_INSERT_INORDER2
545#define LL_INSERT_INORDER2(head,add,cmp,next) \
546do { \
547 if ((head) == NULL || (cmp(head, add)) >= 0) { \
548 (add)->next = (head); \
549 (head) = (add); \
550 } else { \
551 char *_tmp = (char*)(head); \
552 while ((head)->next != NULL && (cmp((head)->next, add)) < 0) { \
553 (head) = (head)->next; \
554 } \
555 (add)->next = (head)->next; \
556 (head)->next = (add); \
557 UTLIST_RS(head); \
558 } \
559} while (0)
560
561#undef LL_DELETE2
562#define LL_DELETE2(head,del,next) \
563do { \
564 if ((head) == (del)) { \
565 (head)=(head)->next; \
566 } else { \
567 char *_tmp = (char*)(head); \
568 while ((head)->next && ((head)->next != (del))) { \
569 (head) = (head)->next; \
570 } \
571 if ((head)->next) { \
572 (head)->next = ((del)->next); \
573 } \
574 UTLIST_RS(head); \
575 } \
576} while (0)
577
578#undef LL_REPLACE_ELEM2
579#define LL_REPLACE_ELEM2(head, el, add, next) \
580do { \
581 assert((head) != NULL); \
582 assert((el) != NULL); \
583 assert((add) != NULL); \
584 if ((head) == (el)) { \
585 (head) = (add); \
586 } else { \
587 (add)->next = head; \
588 while ((add)->next->next && ((add)->next->next != (el))) { \
589 (add)->next = (add)->next->next; \
590 } \
591 if ((add)->next->next) { \
592 (add)->next->next = (add); \
593 } \
594 } \
595 (add)->next = (el)->next; \
596} while (0)
597
598#undef LL_PREPEND_ELEM2
599#define LL_PREPEND_ELEM2(head, el, add, next) \
600do { \
601 if (el) { \
602 assert((head) != NULL); \
603 assert((add) != NULL); \
604 if ((head) == (el)) { \
605 (head) = (add); \
606 } else { \
607 (add)->next = (head); \
608 while ((add)->next->next && ((add)->next->next != (el))) { \
609 (add)->next = (add)->next->next; \
610 } \
611 if ((add)->next->next) { \
612 (add)->next->next = (add); \
613 } \
614 } \
615 (add)->next = (el); \
616 } else { \
617 LL_APPEND2(head, add, next); \
618 } \
619} while (0) \
620
621#endif /* NO_DECLTYPE */
622
623/******************************************************************************
624 * doubly linked list macros (non-circular) *
625 *****************************************************************************/
626#define DL_PREPEND(head,add) \
627 DL_PREPEND2(head,add,prev,next)
628
629#define DL_PREPEND2(head,add,prev,next) \
630do { \
631 (add)->next = (head); \
632 if (head) { \
633 (add)->prev = (head)->prev; \
634 (head)->prev = (add); \
635 } else { \
636 (add)->prev = (add); \
637 } \
638 (head) = (add); \
639} while (0)
640
641#define DL_APPEND(head,add) \
642 DL_APPEND2(head,add,prev,next)
643
644#define DL_APPEND2(head,add,prev,next) \
645do { \
646 if (head) { \
647 (add)->prev = (head)->prev; \
648 (head)->prev->next = (add); \
649 (head)->prev = (add); \
650 (add)->next = NULL; \
651 } else { \
652 (head)=(add); \
653 (head)->prev = (head); \
654 (head)->next = NULL; \
655 } \
656} while (0)
657
658#define DL_INSERT_INORDER(head,add,cmp) \
659 DL_INSERT_INORDER2(head,add,cmp,prev,next)
660
661#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \
662do { \
663 LDECLTYPE(head) _tmp; \
664 if (head) { \
665 DL_LOWER_BOUND2(head, _tmp, add, cmp, next); \
666 DL_APPEND_ELEM2(head, _tmp, add, prev, next); \
667 } else { \
668 (head) = (add); \
669 (head)->prev = (head); \
670 (head)->next = NULL; \
671 } \
672} while (0)
673
674#define DL_LOWER_BOUND(head,elt,like,cmp) \
675 DL_LOWER_BOUND2(head,elt,like,cmp,next)
676
677#define DL_LOWER_BOUND2(head,elt,like,cmp,next) \
678do { \
679 if ((head) == NULL || (cmp(head, like)) >= 0) { \
680 (elt) = NULL; \
681 } else { \
682 for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \
683 if ((cmp((elt)->next, like)) >= 0) { \
684 break; \
685 } \
686 } \
687 } \
688} while (0)
689
690#define DL_CONCAT(head1,head2) \
691 DL_CONCAT2(head1,head2,prev,next)
692
693#define DL_CONCAT2(head1,head2,prev,next) \
694do { \
695 LDECLTYPE(head1) _tmp; \
696 if (head2) { \
697 if (head1) { \
698 UTLIST_CASTASGN(_tmp, (head2)->prev); \
699 (head2)->prev = (head1)->prev; \
700 (head1)->prev->next = (head2); \
701 UTLIST_CASTASGN((head1)->prev, _tmp); \
702 } else { \
703 (head1)=(head2); \
704 } \
705 } \
706} while (0)
707
708#define DL_DELETE(head,del) \
709 DL_DELETE2(head,del,prev,next)
710
711#define DL_DELETE2(head,del,prev,next) \
712do { \
713 assert((head) != NULL); \
714 assert((del)->prev != NULL); \
715 if ((del)->prev == (del)) { \
716 (head)=NULL; \
717 } else if ((del)==(head)) { \
718 (del)->next->prev = (del)->prev; \
719 (head) = (del)->next; \
720 } else { \
721 (del)->prev->next = (del)->next; \
722 if ((del)->next) { \
723 (del)->next->prev = (del)->prev; \
724 } else { \
725 (head)->prev = (del)->prev; \
726 } \
727 } \
728} while (0)
729
730#define DL_COUNT(head,el,counter) \
731 DL_COUNT2(head,el,counter,next) \
732
733#define DL_COUNT2(head,el,counter,next) \
734do { \
735 (counter) = 0; \
736 DL_FOREACH2(head,el,next) { ++(counter); } \
737} while (0)
738
739#define DL_FOREACH(head,el) \
740 DL_FOREACH2(head,el,next)
741
742#define DL_FOREACH2(head,el,next) \
743 for ((el) = (head); el; (el) = (el)->next)
744
745/* this version is safe for deleting the elements during iteration */
746#define DL_FOREACH_SAFE(head,el,tmp) \
747 DL_FOREACH_SAFE2(head,el,tmp,next)
748
749#define DL_FOREACH_SAFE2(head,el,tmp,next) \
750 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
751
752/* these are identical to their singly-linked list counterparts */
753#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
754#define DL_SEARCH LL_SEARCH
755#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
756#define DL_SEARCH2 LL_SEARCH2
757
758#define DL_REPLACE_ELEM2(head, el, add, prev, next) \
759do { \
760 assert((head) != NULL); \
761 assert((el) != NULL); \
762 assert((add) != NULL); \
763 if ((head) == (el)) { \
764 (head) = (add); \
765 (add)->next = (el)->next; \
766 if ((el)->next == NULL) { \
767 (add)->prev = (add); \
768 } else { \
769 (add)->prev = (el)->prev; \
770 (add)->next->prev = (add); \
771 } \
772 } else { \
773 (add)->next = (el)->next; \
774 (add)->prev = (el)->prev; \
775 (add)->prev->next = (add); \
776 if ((el)->next == NULL) { \
777 (head)->prev = (add); \
778 } else { \
779 (add)->next->prev = (add); \
780 } \
781 } \
782} while (0)
783
784#define DL_REPLACE_ELEM(head, el, add) \
785 DL_REPLACE_ELEM2(head, el, add, prev, next)
786
787#define DL_PREPEND_ELEM2(head, el, add, prev, next) \
788do { \
789 if (el) { \
790 assert((head) != NULL); \
791 assert((add) != NULL); \
792 (add)->next = (el); \
793 (add)->prev = (el)->prev; \
794 (el)->prev = (add); \
795 if ((head) == (el)) { \
796 (head) = (add); \
797 } else { \
798 (add)->prev->next = (add); \
799 } \
800 } else { \
801 DL_APPEND2(head, add, prev, next); \
802 } \
803} while (0) \
804
805#define DL_PREPEND_ELEM(head, el, add) \
806 DL_PREPEND_ELEM2(head, el, add, prev, next)
807
808#define DL_APPEND_ELEM2(head, el, add, prev, next) \
809do { \
810 if (el) { \
811 assert((head) != NULL); \
812 assert((add) != NULL); \
813 (add)->next = (el)->next; \
814 (add)->prev = (el); \
815 (el)->next = (add); \
816 if ((add)->next) { \
817 (add)->next->prev = (add); \
818 } else { \
819 (head)->prev = (add); \
820 } \
821 } else { \
822 DL_PREPEND2(head, add, prev, next); \
823 } \
824} while (0) \
825
826#define DL_APPEND_ELEM(head, el, add) \
827 DL_APPEND_ELEM2(head, el, add, prev, next)
828
829#ifdef NO_DECLTYPE
830/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
831
832#undef DL_INSERT_INORDER2
833#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \
834do { \
835 if ((head) == NULL) { \
836 (add)->prev = (add); \
837 (add)->next = NULL; \
838 (head) = (add); \
839 } else if ((cmp(head, add)) >= 0) { \
840 (add)->prev = (head)->prev; \
841 (add)->next = (head); \
842 (head)->prev = (add); \
843 (head) = (add); \
844 } else { \
845 char *_tmp = (char*)(head); \
846 while ((head)->next && (cmp((head)->next, add)) < 0) { \
847 (head) = (head)->next; \
848 } \
849 (add)->prev = (head); \
850 (add)->next = (head)->next; \
851 (head)->next = (add); \
852 UTLIST_RS(head); \
853 if ((add)->next) { \
854 (add)->next->prev = (add); \
855 } else { \
856 (head)->prev = (add); \
857 } \
858 } \
859} while (0)
860#endif /* NO_DECLTYPE */
861
862/******************************************************************************
863 * circular doubly linked list macros *
864 *****************************************************************************/
865#define CDL_APPEND(head,add) \
866 CDL_APPEND2(head,add,prev,next)
867
868#define CDL_APPEND2(head,add,prev,next) \
869do { \
870 if (head) { \
871 (add)->prev = (head)->prev; \
872 (add)->next = (head); \
873 (head)->prev = (add); \
874 (add)->prev->next = (add); \
875 } else { \
876 (add)->prev = (add); \
877 (add)->next = (add); \
878 (head) = (add); \
879 } \
880} while (0)
881
882#define CDL_PREPEND(head,add) \
883 CDL_PREPEND2(head,add,prev,next)
884
885#define CDL_PREPEND2(head,add,prev,next) \
886do { \
887 if (head) { \
888 (add)->prev = (head)->prev; \
889 (add)->next = (head); \
890 (head)->prev = (add); \
891 (add)->prev->next = (add); \
892 } else { \
893 (add)->prev = (add); \
894 (add)->next = (add); \
895 } \
896 (head) = (add); \
897} while (0)
898
899#define CDL_INSERT_INORDER(head,add,cmp) \
900 CDL_INSERT_INORDER2(head,add,cmp,prev,next)
901
902#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \
903do { \
904 LDECLTYPE(head) _tmp; \
905 if (head) { \
906 CDL_LOWER_BOUND2(head, _tmp, add, cmp, next); \
907 CDL_APPEND_ELEM2(head, _tmp, add, prev, next); \
908 } else { \
909 (head) = (add); \
910 (head)->next = (head); \
911 (head)->prev = (head); \
912 } \
913} while (0)
914
915#define CDL_LOWER_BOUND(head,elt,like,cmp) \
916 CDL_LOWER_BOUND2(head,elt,like,cmp,next)
917
918#define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \
919do { \
920 if ((head) == NULL || (cmp(head, like)) >= 0) { \
921 (elt) = NULL; \
922 } else { \
923 for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \
924 if ((cmp((elt)->next, like)) >= 0) { \
925 break; \
926 } \
927 } \
928 } \
929} while (0)
930
931#define CDL_DELETE(head,del) \
932 CDL_DELETE2(head,del,prev,next)
933
934#define CDL_DELETE2(head,del,prev,next) \
935do { \
936 if (((head)==(del)) && ((head)->next == (head))) { \
937 (head) = NULL; \
938 } else { \
939 (del)->next->prev = (del)->prev; \
940 (del)->prev->next = (del)->next; \
941 if ((del) == (head)) (head)=(del)->next; \
942 } \
943} while (0)
944
945#define CDL_COUNT(head,el,counter) \
946 CDL_COUNT2(head,el,counter,next) \
947
948#define CDL_COUNT2(head, el, counter,next) \
949do { \
950 (counter) = 0; \
951 CDL_FOREACH2(head,el,next) { ++(counter); } \
952} while (0)
953
954#define CDL_FOREACH(head,el) \
955 CDL_FOREACH2(head,el,next)
956
957#define CDL_FOREACH2(head,el,next) \
958 for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next))
959
960#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
961 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
962
963#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
964 for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \
965 (el) && ((tmp2) = (el)->next, 1); \
966 (el) = ((el) == (tmp1) ? NULL : (tmp2)))
967
968#define CDL_SEARCH_SCALAR(head,out,field,val) \
969 CDL_SEARCH_SCALAR2(head,out,field,val,next)
970
971#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
972do { \
973 CDL_FOREACH2(head,out,next) { \
974 if ((out)->field == (val)) break; \
975 } \
976} while (0)
977
978#define CDL_SEARCH(head,out,elt,cmp) \
979 CDL_SEARCH2(head,out,elt,cmp,next)
980
981#define CDL_SEARCH2(head,out,elt,cmp,next) \
982do { \
983 CDL_FOREACH2(head,out,next) { \
984 if ((cmp(out,elt))==0) break; \
985 } \
986} while (0)
987
988#define CDL_REPLACE_ELEM2(head, el, add, prev, next) \
989do { \
990 assert((head) != NULL); \
991 assert((el) != NULL); \
992 assert((add) != NULL); \
993 if ((el)->next == (el)) { \
994 (add)->next = (add); \
995 (add)->prev = (add); \
996 (head) = (add); \
997 } else { \
998 (add)->next = (el)->next; \
999 (add)->prev = (el)->prev; \
1000 (add)->next->prev = (add); \
1001 (add)->prev->next = (add); \
1002 if ((head) == (el)) { \
1003 (head) = (add); \
1004 } \
1005 } \
1006} while (0)
1007
1008#define CDL_REPLACE_ELEM(head, el, add) \
1009 CDL_REPLACE_ELEM2(head, el, add, prev, next)
1010
1011#define CDL_PREPEND_ELEM2(head, el, add, prev, next) \
1012do { \
1013 if (el) { \
1014 assert((head) != NULL); \
1015 assert((add) != NULL); \
1016 (add)->next = (el); \
1017 (add)->prev = (el)->prev; \
1018 (el)->prev = (add); \
1019 (add)->prev->next = (add); \
1020 if ((head) == (el)) { \
1021 (head) = (add); \
1022 } \
1023 } else { \
1024 CDL_APPEND2(head, add, prev, next); \
1025 } \
1026} while (0)
1027
1028#define CDL_PREPEND_ELEM(head, el, add) \
1029 CDL_PREPEND_ELEM2(head, el, add, prev, next)
1030
1031#define CDL_APPEND_ELEM2(head, el, add, prev, next) \
1032do { \
1033 if (el) { \
1034 assert((head) != NULL); \
1035 assert((add) != NULL); \
1036 (add)->next = (el)->next; \
1037 (add)->prev = (el); \
1038 (el)->next = (add); \
1039 (add)->next->prev = (add); \
1040 } else { \
1041 CDL_PREPEND2(head, add, prev, next); \
1042 } \
1043} while (0)
1044
1045#define CDL_APPEND_ELEM(head, el, add) \
1046 CDL_APPEND_ELEM2(head, el, add, prev, next)
1047
1048#ifdef NO_DECLTYPE
1049/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
1050
1051#undef CDL_INSERT_INORDER2
1052#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \
1053do { \
1054 if ((head) == NULL) { \
1055 (add)->prev = (add); \
1056 (add)->next = (add); \
1057 (head) = (add); \
1058 } else if ((cmp(head, add)) >= 0) { \
1059 (add)->prev = (head)->prev; \
1060 (add)->next = (head); \
1061 (add)->prev->next = (add); \
1062 (head)->prev = (add); \
1063 (head) = (add); \
1064 } else { \
1065 char *_tmp = (char*)(head); \
1066 while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \
1067 (head) = (head)->next; \
1068 } \
1069 (add)->prev = (head); \
1070 (add)->next = (head)->next; \
1071 (add)->next->prev = (add); \
1072 (head)->next = (add); \
1073 UTLIST_RS(head); \
1074 } \
1075} while (0)
1076#endif /* NO_DECLTYPE */
1077
1078#endif /* UTLIST_H */
1079