libcoap  4.1.2
utlist.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2007-2014, 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 1.9.9
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 #elif defined(__ICCARM__)
74 #define NO_DECLTYPE
75 #define LDECLTYPE(x) char*
76 #else /* GNU, Sun and other compilers */
77 #define LDECLTYPE(x) __typeof(x)
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 _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
85 #define _NEXT(elt,list,next) ((char*)((list)->next))
86 #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
87 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
88 #define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
89 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
90 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
91 #else
92 #define _SV(elt,list)
93 #define _NEXT(elt,list,next) ((elt)->next)
94 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
95 /* #define _PREV(elt,list,prev) ((elt)->prev) */
96 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
97 #define _RS(list)
98 #define _CASTASGN(a,b) (a)=(b)
99 #endif
100 
101 /******************************************************************************
102  * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
103  * Unwieldy variable names used here to avoid shadowing passed-in variables. *
104  *****************************************************************************/
105 #define LL_SORT(list, cmp) \
106  LL_SORT2(list, cmp, next)
107 
108 #define LL_SORT2(list, cmp, next) \
109 do { \
110  LDECLTYPE(list) _ls_p; \
111  LDECLTYPE(list) _ls_q; \
112  LDECLTYPE(list) _ls_e; \
113  LDECLTYPE(list) _ls_tail; \
114  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
115  if (list) { \
116  _ls_insize = 1; \
117  _ls_looping = 1; \
118  while (_ls_looping) { \
119  _CASTASGN(_ls_p,list); \
120  list = NULL; \
121  _ls_tail = NULL; \
122  _ls_nmerges = 0; \
123  while (_ls_p) { \
124  _ls_nmerges++; \
125  _ls_q = _ls_p; \
126  _ls_psize = 0; \
127  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
128  _ls_psize++; \
129  _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
130  if (!_ls_q) break; \
131  } \
132  _ls_qsize = _ls_insize; \
133  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
134  if (_ls_psize == 0) { \
135  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
136  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
137  } else if (_ls_qsize == 0 || !_ls_q) { \
138  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
139  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
140  } else if (cmp(_ls_p,_ls_q) <= 0) { \
141  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
142  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
143  } else { \
144  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
145  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
146  } \
147  if (_ls_tail) { \
148  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
149  } else { \
150  _CASTASGN(list,_ls_e); \
151  } \
152  _ls_tail = _ls_e; \
153  } \
154  _ls_p = _ls_q; \
155  } \
156  if (_ls_tail) { \
157  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
158  } \
159  if (_ls_nmerges <= 1) { \
160  _ls_looping=0; \
161  } \
162  _ls_insize *= 2; \
163  } \
164  } \
165 } while (0)
166 
167 
168 #define DL_SORT(list, cmp) \
169  DL_SORT2(list, cmp, prev, next)
170 
171 #define DL_SORT2(list, cmp, prev, next) \
172 do { \
173  LDECLTYPE(list) _ls_p; \
174  LDECLTYPE(list) _ls_q; \
175  LDECLTYPE(list) _ls_e; \
176  LDECLTYPE(list) _ls_tail; \
177  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
178  if (list) { \
179  _ls_insize = 1; \
180  _ls_looping = 1; \
181  while (_ls_looping) { \
182  _CASTASGN(_ls_p,list); \
183  list = NULL; \
184  _ls_tail = NULL; \
185  _ls_nmerges = 0; \
186  while (_ls_p) { \
187  _ls_nmerges++; \
188  _ls_q = _ls_p; \
189  _ls_psize = 0; \
190  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
191  _ls_psize++; \
192  _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
193  if (!_ls_q) break; \
194  } \
195  _ls_qsize = _ls_insize; \
196  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
197  if (_ls_psize == 0) { \
198  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
199  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
200  } else if (_ls_qsize == 0 || !_ls_q) { \
201  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
202  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
203  } else if (cmp(_ls_p,_ls_q) <= 0) { \
204  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
205  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
206  } else { \
207  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
208  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
209  } \
210  if (_ls_tail) { \
211  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
212  } else { \
213  _CASTASGN(list,_ls_e); \
214  } \
215  _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
216  _ls_tail = _ls_e; \
217  } \
218  _ls_p = _ls_q; \
219  } \
220  _CASTASGN(list->prev, _ls_tail); \
221  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
222  if (_ls_nmerges <= 1) { \
223  _ls_looping=0; \
224  } \
225  _ls_insize *= 2; \
226  } \
227  } \
228 } while (0)
229 
230 #define CDL_SORT(list, cmp) \
231  CDL_SORT2(list, cmp, prev, next)
232 
233 #define CDL_SORT2(list, cmp, prev, next) \
234 do { \
235  LDECLTYPE(list) _ls_p; \
236  LDECLTYPE(list) _ls_q; \
237  LDECLTYPE(list) _ls_e; \
238  LDECLTYPE(list) _ls_tail; \
239  LDECLTYPE(list) _ls_oldhead; \
240  LDECLTYPE(list) _tmp; \
241  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
242  if (list) { \
243  _ls_insize = 1; \
244  _ls_looping = 1; \
245  while (_ls_looping) { \
246  _CASTASGN(_ls_p,list); \
247  _CASTASGN(_ls_oldhead,list); \
248  list = NULL; \
249  _ls_tail = NULL; \
250  _ls_nmerges = 0; \
251  while (_ls_p) { \
252  _ls_nmerges++; \
253  _ls_q = _ls_p; \
254  _ls_psize = 0; \
255  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
256  _ls_psize++; \
257  _SV(_ls_q,list); \
258  if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
259  _ls_q = NULL; \
260  } else { \
261  _ls_q = _NEXT(_ls_q,list,next); \
262  } \
263  _RS(list); \
264  if (!_ls_q) break; \
265  } \
266  _ls_qsize = _ls_insize; \
267  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
268  if (_ls_psize == 0) { \
269  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
270  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
271  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
272  } else if (_ls_qsize == 0 || !_ls_q) { \
273  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
274  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
275  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
276  } else if (cmp(_ls_p,_ls_q) <= 0) { \
277  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
278  _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
279  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
280  } else { \
281  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
282  _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
283  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
284  } \
285  if (_ls_tail) { \
286  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
287  } else { \
288  _CASTASGN(list,_ls_e); \
289  } \
290  _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
291  _ls_tail = _ls_e; \
292  } \
293  _ls_p = _ls_q; \
294  } \
295  _CASTASGN(list->prev,_ls_tail); \
296  _CASTASGN(_tmp,list); \
297  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
298  if (_ls_nmerges <= 1) { \
299  _ls_looping=0; \
300  } \
301  _ls_insize *= 2; \
302  } \
303  } \
304 } while (0)
305 
306 /******************************************************************************
307  * singly linked list macros (non-circular) *
308  *****************************************************************************/
309 #define LL_PREPEND(head,add) \
310  LL_PREPEND2(head,add,next)
311 
312 #define LL_PREPEND2(head,add,next) \
313 do { \
314  (add)->next = head; \
315  head = add; \
316 } while (0)
317 
318 #define LL_CONCAT(head1,head2) \
319  LL_CONCAT2(head1,head2,next)
320 
321 #define LL_CONCAT2(head1,head2,next) \
322 do { \
323  LDECLTYPE(head1) _tmp; \
324  if (head1) { \
325  _tmp = head1; \
326  while (_tmp->next) { _tmp = _tmp->next; } \
327  _tmp->next=(head2); \
328  } else { \
329  (head1)=(head2); \
330  } \
331 } while (0)
332 
333 #define LL_APPEND(head,add) \
334  LL_APPEND2(head,add,next)
335 
336 #define LL_APPEND2(head,add,next) \
337 do { \
338  LDECLTYPE(head) _tmp; \
339  (add)->next=NULL; \
340  if (head) { \
341  _tmp = head; \
342  while (_tmp->next) { _tmp = _tmp->next; } \
343  _tmp->next=(add); \
344  } else { \
345  (head)=(add); \
346  } \
347 } while (0)
348 
349 #define LL_DELETE(head,del) \
350  LL_DELETE2(head,del,next)
351 
352 #define LL_DELETE2(head,del,next) \
353 do { \
354  LDECLTYPE(head) _tmp; \
355  if ((head) == (del)) { \
356  (head)=(head)->next; \
357  } else { \
358  _tmp = head; \
359  while (_tmp->next && (_tmp->next != (del))) { \
360  _tmp = _tmp->next; \
361  } \
362  if (_tmp->next) { \
363  _tmp->next = ((del)->next); \
364  } \
365  } \
366 } while (0)
367 
368 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
369 #define LL_APPEND_VS2008(head,add) \
370  LL_APPEND2_VS2008(head,add,next)
371 
372 #define LL_APPEND2_VS2008(head,add,next) \
373 do { \
374  if (head) { \
375  (add)->next = head; /* use add->next as a temp variable */ \
376  while ((add)->next->next) { (add)->next = (add)->next->next; } \
377  (add)->next->next=(add); \
378  } else { \
379  (head)=(add); \
380  } \
381  (add)->next=NULL; \
382 } while (0)
383 
384 #define LL_DELETE_VS2008(head,del) \
385  LL_DELETE2_VS2008(head,del,next)
386 
387 #define LL_DELETE2_VS2008(head,del,next) \
388 do { \
389  if ((head) == (del)) { \
390  (head)=(head)->next; \
391  } else { \
392  char *_tmp = (char*)(head); \
393  while ((head)->next && ((head)->next != (del))) { \
394  head = (head)->next; \
395  } \
396  if ((head)->next) { \
397  (head)->next = ((del)->next); \
398  } \
399  { \
400  char **_head_alias = (char**)&(head); \
401  *_head_alias = _tmp; \
402  } \
403  } \
404 } while (0)
405 #ifdef NO_DECLTYPE
406 #undef LL_APPEND
407 #define LL_APPEND LL_APPEND_VS2008
408 #undef LL_DELETE
409 #define LL_DELETE LL_DELETE_VS2008
410 #undef LL_DELETE2
411 #define LL_DELETE2 LL_DELETE2_VS2008
412 #undef LL_APPEND2
413 #define LL_APPEND2 LL_APPEND2_VS2008
414 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */
415 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */
416 #endif
417 /* end VS2008 replacements */
418 
419 #define LL_COUNT(head,el,counter) \
420  LL_COUNT2(head,el,counter,next) \
421 
422 #define LL_COUNT2(head,el,counter,next) \
423 { \
424  counter = 0; \
425  LL_FOREACH2(head,el,next){ ++counter; } \
426 }
427 
428 #define LL_FOREACH(head,el) \
429  LL_FOREACH2(head,el,next)
430 
431 #define LL_FOREACH2(head,el,next) \
432  for(el=head;el;el=(el)->next)
433 
434 #define LL_FOREACH_SAFE(head,el,tmp) \
435  LL_FOREACH_SAFE2(head,el,tmp,next)
436 
437 #define LL_FOREACH_SAFE2(head,el,tmp,next) \
438  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
439 
440 #define LL_SEARCH_SCALAR(head,out,field,val) \
441  LL_SEARCH_SCALAR2(head,out,field,val,next)
442 
443 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \
444 do { \
445  LL_FOREACH2(head,out,next) { \
446  if ((out)->field == (val)) break; \
447  } \
448 } while(0)
449 
450 #define LL_SEARCH(head,out,elt,cmp) \
451  LL_SEARCH2(head,out,elt,cmp,next)
452 
453 #define LL_SEARCH2(head,out,elt,cmp,next) \
454 do { \
455  LL_FOREACH2(head,out,next) { \
456  if ((cmp(out,elt))==0) break; \
457  } \
458 } while(0)
459 
460 #define LL_REPLACE_ELEM(head, el, add) \
461 do { \
462  LDECLTYPE(head) _tmp; \
463  assert(head != NULL); \
464  assert(el != NULL); \
465  assert(add != NULL); \
466  (add)->next = (el)->next; \
467  if ((head) == (el)) { \
468  (head) = (add); \
469  } else { \
470  _tmp = head; \
471  while (_tmp->next && (_tmp->next != (el))) { \
472  _tmp = _tmp->next; \
473  } \
474  if (_tmp->next) { \
475  _tmp->next = (add); \
476  } \
477  } \
478 } while (0)
479 
480 #define LL_PREPEND_ELEM(head, el, add) \
481 do { \
482  LDECLTYPE(head) _tmp; \
483  assert(head != NULL); \
484  assert(el != NULL); \
485  assert(add != NULL); \
486  (add)->next = (el); \
487  if ((head) == (el)) { \
488  (head) = (add); \
489  } else { \
490  _tmp = head; \
491  while (_tmp->next && (_tmp->next != (el))) { \
492  _tmp = _tmp->next; \
493  } \
494  if (_tmp->next) { \
495  _tmp->next = (add); \
496  } \
497  } \
498 } while (0) \
499 
500 
501 /******************************************************************************
502  * doubly linked list macros (non-circular) *
503  *****************************************************************************/
504 #define DL_PREPEND(head,add) \
505  DL_PREPEND2(head,add,prev,next)
506 
507 #define DL_PREPEND2(head,add,prev,next) \
508 do { \
509  (add)->next = head; \
510  if (head) { \
511  (add)->prev = (head)->prev; \
512  (head)->prev = (add); \
513  } else { \
514  (add)->prev = (add); \
515  } \
516  (head) = (add); \
517 } while (0)
518 
519 #define DL_APPEND(head,add) \
520  DL_APPEND2(head,add,prev,next)
521 
522 #define DL_APPEND2(head,add,prev,next) \
523 do { \
524  if (head) { \
525  (add)->prev = (head)->prev; \
526  (head)->prev->next = (add); \
527  (head)->prev = (add); \
528  (add)->next = NULL; \
529  } else { \
530  (head)=(add); \
531  (head)->prev = (head); \
532  (head)->next = NULL; \
533  } \
534 } while (0)
535 
536 #define DL_CONCAT(head1,head2) \
537  DL_CONCAT2(head1,head2,prev,next)
538 
539 #define DL_CONCAT2(head1,head2,prev,next) \
540 do { \
541  LDECLTYPE(head1) _tmp; \
542  if (head2) { \
543  if (head1) { \
544  _tmp = (head2)->prev; \
545  (head2)->prev = (head1)->prev; \
546  (head1)->prev->next = (head2); \
547  (head1)->prev = _tmp; \
548  } else { \
549  (head1)=(head2); \
550  } \
551  } \
552 } while (0)
553 
554 #define DL_DELETE(head,del) \
555  DL_DELETE2(head,del,prev,next)
556 
557 #define DL_DELETE2(head,del,prev,next) \
558 do { \
559  assert((del)->prev != NULL); \
560  if ((del)->prev == (del)) { \
561  (head)=NULL; \
562  } else if ((del)==(head)) { \
563  (del)->next->prev = (del)->prev; \
564  (head) = (del)->next; \
565  } else { \
566  (del)->prev->next = (del)->next; \
567  if ((del)->next) { \
568  (del)->next->prev = (del)->prev; \
569  } else { \
570  (head)->prev = (del)->prev; \
571  } \
572  } \
573 } while (0)
574 
575 #define DL_COUNT(head,el,counter) \
576  DL_COUNT2(head,el,counter,next) \
577 
578 #define DL_COUNT2(head,el,counter,next) \
579 { \
580  counter = 0; \
581  DL_FOREACH2(head,el,next){ ++counter; } \
582 }
583 
584 #define DL_FOREACH(head,el) \
585  DL_FOREACH2(head,el,next)
586 
587 #define DL_FOREACH2(head,el,next) \
588  for(el=head;el;el=(el)->next)
589 
590 /* this version is safe for deleting the elements during iteration */
591 #define DL_FOREACH_SAFE(head,el,tmp) \
592  DL_FOREACH_SAFE2(head,el,tmp,next)
593 
594 #define DL_FOREACH_SAFE2(head,el,tmp,next) \
595  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
596 
597 /* these are identical to their singly-linked list counterparts */
598 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
599 #define DL_SEARCH LL_SEARCH
600 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
601 #define DL_SEARCH2 LL_SEARCH2
602 
603 #define DL_REPLACE_ELEM(head, el, add) \
604 do { \
605  assert(head != NULL); \
606  assert(el != NULL); \
607  assert(add != NULL); \
608  if ((head) == (el)) { \
609  (head) = (add); \
610  (add)->next = (el)->next; \
611  if ((el)->next == NULL) { \
612  (add)->prev = (add); \
613  } else { \
614  (add)->prev = (el)->prev; \
615  (add)->next->prev = (add); \
616  } \
617  } else { \
618  (add)->next = (el)->next; \
619  (add)->prev = (el)->prev; \
620  (add)->prev->next = (add); \
621  if ((el)->next == NULL) { \
622  (head)->prev = (add); \
623  } else { \
624  (add)->next->prev = (add); \
625  } \
626  } \
627 } while (0)
628 
629 #define DL_PREPEND_ELEM(head, el, add) \
630 do { \
631  assert(head != NULL); \
632  assert(el != NULL); \
633  assert(add != NULL); \
634  (add)->next = (el); \
635  (add)->prev = (el)->prev; \
636  (el)->prev = (add); \
637  if ((head) == (el)) { \
638  (head) = (add); \
639  } else { \
640  (add)->prev->next = (add); \
641  } \
642 } while (0) \
643 
644 
645 /******************************************************************************
646  * circular doubly linked list macros *
647  *****************************************************************************/
648 #define CDL_PREPEND(head,add) \
649  CDL_PREPEND2(head,add,prev,next)
650 
651 #define CDL_PREPEND2(head,add,prev,next) \
652 do { \
653  if (head) { \
654  (add)->prev = (head)->prev; \
655  (add)->next = (head); \
656  (head)->prev = (add); \
657  (add)->prev->next = (add); \
658  } else { \
659  (add)->prev = (add); \
660  (add)->next = (add); \
661  } \
662 (head)=(add); \
663 } while (0)
664 
665 #define CDL_DELETE(head,del) \
666  CDL_DELETE2(head,del,prev,next)
667 
668 #define CDL_DELETE2(head,del,prev,next) \
669 do { \
670  if ( ((head)==(del)) && ((head)->next == (head))) { \
671  (head) = 0L; \
672  } else { \
673  (del)->next->prev = (del)->prev; \
674  (del)->prev->next = (del)->next; \
675  if ((del) == (head)) (head)=(del)->next; \
676  } \
677 } while (0)
678 
679 #define CDL_COUNT(head,el,counter) \
680  CDL_COUNT2(head,el,counter,next) \
681 
682 #define CDL_COUNT2(head, el, counter,next) \
683 { \
684  counter = 0; \
685  CDL_FOREACH2(head,el,next){ ++counter; } \
686 }
687 
688 #define CDL_FOREACH(head,el) \
689  CDL_FOREACH2(head,el,next)
690 
691 #define CDL_FOREACH2(head,el,next) \
692  for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
693 
694 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
695  CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
696 
697 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
698  for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
699  (el) && ((tmp2)=(el)->next, 1); \
700  ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
701 
702 #define CDL_SEARCH_SCALAR(head,out,field,val) \
703  CDL_SEARCH_SCALAR2(head,out,field,val,next)
704 
705 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
706 do { \
707  CDL_FOREACH2(head,out,next) { \
708  if ((out)->field == (val)) break; \
709  } \
710 } while(0)
711 
712 #define CDL_SEARCH(head,out,elt,cmp) \
713  CDL_SEARCH2(head,out,elt,cmp,next)
714 
715 #define CDL_SEARCH2(head,out,elt,cmp,next) \
716 do { \
717  CDL_FOREACH2(head,out,next) { \
718  if ((cmp(out,elt))==0) break; \
719  } \
720 } while(0)
721 
722 #define CDL_REPLACE_ELEM(head, el, add) \
723 do { \
724  assert(head != NULL); \
725  assert(el != NULL); \
726  assert(add != NULL); \
727  if ((el)->next == (el)) { \
728  (add)->next = (add); \
729  (add)->prev = (add); \
730  (head) = (add); \
731  } else { \
732  (add)->next = (el)->next; \
733  (add)->prev = (el)->prev; \
734  (add)->next->prev = (add); \
735  (add)->prev->next = (add); \
736  if ((head) == (el)) { \
737  (head) = (add); \
738  } \
739  } \
740 } while (0)
741 
742 #define CDL_PREPEND_ELEM(head, el, add) \
743 do { \
744  assert(head != NULL); \
745  assert(el != NULL); \
746  assert(add != NULL); \
747  (add)->next = (el); \
748  (add)->prev = (el)->prev; \
749  (el)->prev = (add); \
750  (add)->prev->next = (add); \
751  if ((head) == (el)) { \
752  (head) = (add); \
753  } \
754 } while (0) \
755 
756 #endif /* UTLIST_H */
757