EE445M RTOS
Taken at the University of Texas Spring 2015
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_EDF_PREPEND(head,add) \
313 do { \
314  (add)->next = head; \
315  head = add; \
316 } while (0)
317 
318 #define LL_PREPEND2(head,add,next) \
319 do { \
320  (add)->next = head; \
321  head = add; \
322 } while (0)
323 
324 #define LL_CONCAT(head1,head2) \
325  LL_CONCAT2(head1,head2,next)
326 
327 #define LL_CONCAT2(head1,head2,next) \
328 do { \
329  LDECLTYPE(head1) _tmp; \
330  if (head1) { \
331  _tmp = head1; \
332  while (_tmp->next) { _tmp = _tmp->next; } \
333  _tmp->next=(head2); \
334  } else { \
335  (head1)=(head2); \
336  } \
337 } while (0)
338 
339 #define LL_APPEND(head,add) \
340  LL_APPEND2(head,add,next)
341 
342 #define LL_EDF_APPEND(head,add) \
343  LL_APPEND2(head,add,pri_next)
344 
345 #define LL_APPEND2(head,add,next) \
346 do { \
347  LDECLTYPE(head) _tmp; \
348  (add)->next=NULL; \
349  if (head) { \
350  _tmp = head; \
351  while (_tmp->next) { _tmp = _tmp->next; } \
352  _tmp->next=(add); \
353  } else { \
354  (head)=(add); \
355  } \
356 } while (0)
357 
358 #define LL_DELETE(head,del) \
359  LL_DELETE2(head,del,next)
360 
361 #define LL_EDF_DELETE(head,del) \
362  LL_DELETE2(head,del,pri_next)
363 
364 #define LL_DELETE2(head,del,next) \
365 do { \
366  LDECLTYPE(head) _tmp; \
367  if ((head) == (del)) { \
368  (head)=(head)->next; \
369  } else { \
370  _tmp = head; \
371  while (_tmp->next && (_tmp->next != (del))) { \
372  _tmp = _tmp->next; \
373  } \
374  if (_tmp->next) { \
375  _tmp->next = ((del)->next); \
376  } \
377  } \
378 } while (0)
379 
380 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
381 #define LL_APPEND_VS2008(head,add) \
382  LL_APPEND2_VS2008(head,add,next)
383 
384 #define LL_APPEND2_VS2008(head,add,next) \
385 do { \
386  if (head) { \
387  (add)->next = head; /* use add->next as a temp variable */ \
388  while ((add)->next->next) { (add)->next = (add)->next->next; } \
389  (add)->next->next=(add); \
390  } else { \
391  (head)=(add); \
392  } \
393  (add)->next=NULL; \
394 } while (0)
395 
396 #define LL_DELETE_VS2008(head,del) \
397  LL_DELETE2_VS2008(head,del,next)
398 
399 #define LL_DELETE2_VS2008(head,del,next) \
400 do { \
401  if ((head) == (del)) { \
402  (head)=(head)->next; \
403  } else { \
404  char *_tmp = (char*)(head); \
405  while ((head)->next && ((head)->next != (del))) { \
406  head = (head)->next; \
407  } \
408  if ((head)->next) { \
409  (head)->next = ((del)->next); \
410  } \
411  { \
412  char **_head_alias = (char**)&(head); \
413  *_head_alias = _tmp; \
414  } \
415  } \
416 } while (0)
417 #ifdef NO_DECLTYPE
418 #undef LL_APPEND
419 #define LL_APPEND LL_APPEND_VS2008
420 #undef LL_DELETE
421 #define LL_DELETE LL_DELETE_VS2008
422 #undef LL_DELETE2
423 #define LL_DELETE2 LL_DELETE2_VS2008
424 #undef LL_APPEND2
425 #define LL_APPEND2 LL_APPEND2_VS2008
426 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */
427 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */
428 #endif
429 /* end VS2008 replacements */
430 
431 #define LL_COUNT(head,el,counter) \
432  LL_COUNT2(head,el,counter,next) \
433 
434 #define LL_COUNT2(head,el,counter,next) \
435 { \
436  counter = 0; \
437  LL_FOREACH2(head,el,next){ ++counter; } \
438 }
439 
440 #define LL_FOREACH(head,el) \
441  LL_FOREACH2(head,el,next)
442 
443 #define LL_FOREACH2(head,el,next) \
444  for(el=head;el;el=(el)->next)
445 
446 #define LL_FOREACH_SAFE(head,el,tmp) \
447  LL_FOREACH_SAFE2(head,el,tmp,next)
448 
449 #define LL_FOREACH_SAFE2(head,el,tmp,next) \
450  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
451 
452 #define LL_SEARCH_SCALAR(head,out,field,val) \
453  LL_SEARCH_SCALAR2(head,out,field,val,next)
454 
455 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \
456 do { \
457  LL_FOREACH2(head,out,next) { \
458  if ((out)->field == (val)) break; \
459  } \
460 } while(0)
461 
462 #define LL_SEARCH(head,out,elt,cmp) \
463  LL_SEARCH2(head,out,elt,cmp,next)
464 
465 #define LL_SEARCH2(head,out,elt,cmp,next) \
466 do { \
467  LL_FOREACH2(head,out,next) { \
468  if ((cmp(out,elt))==0) break; \
469  } \
470 } while(0)
471 
472 #define LL_REPLACE_ELEM(head, el, add) \
473 do { \
474  LDECLTYPE(head) _tmp; \
475  (add)->next = (el)->next; \
476  if ((head) == (el)) { \
477  (head) = (add); \
478  } else { \
479  _tmp = head; \
480  while (_tmp->next && (_tmp->next != (el))) { \
481  _tmp = _tmp->next; \
482  } \
483  if (_tmp->next) { \
484  _tmp->next = (add); \
485  } \
486  } \
487 } while (0)
488 
489 #define LL_PREPEND_ELEM(head, el, add) \
490 do { \
491  LDECLTYPE(head) _tmp; \
492  (add)->next = (el); \
493  if ((head) == (el)) { \
494  (head) = (add); \
495  } else { \
496  _tmp = head; \
497  while (_tmp->next && (_tmp->next != (el))) { \
498  _tmp = _tmp->next; \
499  } \
500  if (_tmp->next) { \
501  _tmp->next = (add); \
502  } \
503  } \
504 } while (0) \
505 
506 
507 /******************************************************************************
508  * doubly linked list macros (non-circular) *
509  *****************************************************************************/
510 #define DL_PREPEND(head,add) \
511  DL_PREPEND2(head,add,prev,next)
512 
513 #define DL_EDF_PREPEND(head,add) \
514 do { \
515  (add)->pri_next = head; \
516  if (head) { \
517  (add)->pri_prev = (head)->pri_prev; \
518  (head)->pri_prev = (add); \
519  } \
520  (head) = (add); \
521 } while (0)
522 
523 #define DL_PREPEND2(head,add,prev,next) \
524 do { \
525  (add)->next = head; \
526  if (head) { \
527  (add)->prev = (head)->prev; \
528  (head)->prev = (add); \
529  } else { \
530  (add)->prev = (add); \
531  } \
532  (head) = (add); \
533 } while (0)
534 
535 #define DL_APPEND(head,add) \
536  DL_APPEND2(head,add,prev,next)
537 
538 #define DL_EDF_INSERT(head,add) \
539 do { \
540  if (head) { \
541  (add)->pri_next = (head)->pri_next; \
542  (head)->pri_next->pri_prev = (add); \
543  (head)->pri_next = (add); \
544  (add)->pri_prev = NULL; \
545  } else { \
546  (head)=(add); \
547  (head)->pri_prev = NULL; \
548  (head)->pri_next = NULL; \
549  } \
550 } while (0)
551 
552 #define DL_APPEND2(head,add,prev,next) \
553 do { \
554  if (head) { \
555  (add)->prev = (head)->prev; \
556  (head)->prev->next = (add); \
557  (head)->prev = (add); \
558  (add)->next = NULL; \
559  } else { \
560  (head)=(add); \
561  (head)->prev = (head); \
562  (head)->next = NULL; \
563  } \
564 } while (0)
565 
566 #define DL_CONCAT(head1,head2) \
567  DL_CONCAT2(head1,head2,prev,next)
568 
569 #define DL_CONCAT2(head1,head2,prev,next) \
570 do { \
571  LDECLTYPE(head1) _tmp; \
572  if (head2) { \
573  if (head1) { \
574  _tmp = (head2)->prev; \
575  (head2)->prev = (head1)->prev; \
576  (head1)->prev->next = (head2); \
577  (head1)->prev = _tmp; \
578  } else { \
579  (head1)=(head2); \
580  } \
581  } \
582 } while (0)
583 
584 #define DL_DELETE(head,del) \
585  DL_DELETE2(head,del,prev,next)
586 
587 #define DL_DELETE2(head,del,prev,next) \
588 do { \
589  if ((del)->prev == (del)) { \
590  (head)=NULL; \
591  } else if ((del)==(head)) { \
592  (del)->next->prev = (del)->prev; \
593  (head) = (del)->next; \
594  } else { \
595  (del)->prev->next = (del)->next; \
596  if ((del)->next) { \
597  (del)->next->prev = (del)->prev; \
598  } else { \
599  (head)->prev = (del)->prev; \
600  } \
601  } \
602 } while (0)
603 
604 #define DL_COUNT(head,el,counter) \
605  DL_COUNT2(head,el,counter,next) \
606 
607 #define DL_COUNT2(head,el,counter,next) \
608 { \
609  counter = 0; \
610  DL_FOREACH2(head,el,next){ ++counter; } \
611 }
612 
613 #define DL_FOREACH(head,el) \
614  DL_FOREACH2(head,el,next)
615 
616 #define DL_FOREACH2(head,el,next) \
617  for(el=head;el;el=(el)->next)
618 
619 /* this version is safe for deleting the elements during iteration */
620 #define DL_FOREACH_SAFE(head,el,tmp) \
621  DL_FOREACH_SAFE2(head,el,tmp,next)
622 
623 #define DL_FOREACH_SAFE2(head,el,tmp,next) \
624  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
625 
626 /* these are identical to their singly-linked list counterparts */
627 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
628 #define DL_SEARCH LL_SEARCH
629 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
630 #define DL_SEARCH2 LL_SEARCH2
631 
632 #define DL_REPLACE_ELEM(head, el, add) \
633 do { \
634  if ((head) == (el)) { \
635  (head) = (add); \
636  (add)->next = (el)->next; \
637  if ((el)->next == NULL) { \
638  (add)->prev = (add); \
639  } else { \
640  (add)->prev = (el)->prev; \
641  (add)->next->prev = (add); \
642  } \
643  } else { \
644  (add)->next = (el)->next; \
645  (add)->prev = (el)->prev; \
646  (add)->prev->next = (add); \
647  if ((el)->next == NULL) { \
648  (head)->prev = (add); \
649  } else { \
650  (add)->next->prev = (add); \
651  } \
652  } \
653 } while (0)
654 
655 #define DL_PREPEND_ELEM(head, el, add) \
656 do { \
657  (add)->next = (el); \
658  (add)->prev = (el)->prev; \
659  (el)->prev = (add); \
660  if ((head) == (el)) { \
661  (head) = (add); \
662  } else { \
663  (add)->prev->next = (add); \
664  } \
665 } while (0) \
666 
667 
668 /******************************************************************************
669  * circular doubly linked list macros *
670  *****************************************************************************/
671 #define CDL_PREPEND(head,add) \
672  CDL_PREPEND2(head,add,prev,next)
673 
674 #define CDL_PREPEND2(head,add,prev,next) \
675 do { \
676  if (head) { \
677  (add)->prev = (head)->prev; \
678  (add)->next = (head); \
679  (head)->prev = (add); \
680  (add)->prev->next = (add); \
681  } else { \
682  (add)->prev = (add); \
683  (add)->next = (add); \
684  } \
685 (head)=(add); \
686 } while (0)
687 
688 #define CDL_APPEND(head,add) \
689  CDL_APPEND2(head,add,prev,next)
690 
691 #define CDL_APPEND2(head,add,prev,next) \
692 do { \
693  if (head) { \
694  (add)->prev = (head)->prev; \
695  (add)->next = (head); \
696  (head)->prev = (add); \
697  (add)->prev->next = (add); \
698  } else { \
699  (add)->prev = (add); \
700  (add)->next = (add); \
701  (head)=(add); \
702  } \
703 } while (0)
704 
705 #define CDL_DELETE(head,del) \
706  CDL_DELETE2(head,del,prev,next)
707 
708 #define CDL_DELETE2(head,del,prev,next) \
709 do { \
710  if ( ((head)==(del)) && ((head)->next == (head))) { \
711  (head) = 0L; \
712  } else { \
713  (del)->next->prev = (del)->prev; \
714  (del)->prev->next = (del)->next; \
715  if ((del) == (head)) (head)=(del)->next; \
716  } \
717 } while (0)
718 
719 #define CDL_COUNT(head,el,counter) \
720  CDL_COUNT2(head,el,counter,next) \
721 
722 #define CDL_COUNT2(head, el, counter,next) \
723 { \
724  counter = 0; \
725  CDL_FOREACH2(head,el,next){ ++counter; } \
726 }
727 
728 #define CDL_FOREACH(head,el) \
729  CDL_FOREACH2(head,el,next)
730 
731 #define CDL_FOREACH2(head,el,next) \
732  for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
733 
734 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
735  CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
736 
737 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
738  for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
739  (el) && ((tmp2)=(el)->next, 1); \
740  ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
741 
742 #define CDL_SEARCH_SCALAR(head,out,field,val) \
743  CDL_SEARCH_SCALAR2(head,out,field,val,next)
744 
745 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
746 do { \
747  CDL_FOREACH2(head,out,next) { \
748  if ((out)->field == (val)) break; \
749  } \
750 } while(0)
751 
752 #define CDL_SEARCH(head,out,elt,cmp) \
753  CDL_SEARCH2(head,out,elt,cmp,next)
754 
755 #define CDL_SEARCH2(head,out,elt,cmp,next) \
756 do { \
757  CDL_FOREACH2(head,out,next) { \
758  if ((cmp(out,elt))==0) break; \
759  } \
760 } while(0)
761 
762 #define CDL_REPLACE_ELEM(head, el, add) \
763 do { \
764  if ((el)->next == (el)) { \
765  (add)->next = (add); \
766  (add)->prev = (add); \
767  (head) = (add); \
768  } else { \
769  (add)->next = (el)->next; \
770  (add)->prev = (el)->prev; \
771  (add)->next->prev = (add); \
772  (add)->prev->next = (add); \
773  if ((head) == (el)) { \
774  (head) = (add); \
775  } \
776  } \
777 } while (0)
778 
779 #define CDL_PREPEND_ELEM(head, el, add) \
780 do { \
781  (add)->next = (el); \
782  (add)->prev = (el)->prev; \
783  (el)->prev = (add); \
784  (add)->prev->next = (add); \
785  if ((head) == (el)) { \
786  (head) = (add); \
787  } \
788 } while (0) \
789 
790 #endif /* UTLIST_H */