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