?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
modified: diffout.py
[GalaxyCodeBases.git] / c_cpp / lib / uthash / src / utlist.h
blobbb097a2668d0336de2c8b734608e977f02c88fbc
1 /*
2 Copyright (c) 2007-2017, 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.2
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 */
A place to share codes with mates