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