Loading...
Searching...
No Matches
utlist.h
Go to the documentation of this file.
1/*
2Copyright (c) 2007-2014, Troy D. Hanson http://troydhanson.github.com/uthash/
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, 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
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22*/
23
37#ifndef UTLIST_H
38#define UTLIST_H
39
41#define UTLIST_VERSION 1.9.9
42#include <stddef.h>
43
44#include <assert.h>
45
46#ifdef __cplusplus
47extern "C" {
48#endif
49
50/*
51 * This file contains macros to manipulate singly and doubly-linked lists.
52 *
53 * 1. LL_ macros: singly-linked lists.
54 * 2. DL_ macros: doubly-linked lists.
55 * 3. CDL_ macros: circular doubly-linked lists.
56 *
57 * To use singly-linked lists, your structure must have a "next" pointer.
58 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
59 * Either way, the pointer to the head of the list must be initialized to NULL.
60 *
61 * ----------------.EXAMPLE -------------------------
62 * struct item {
63 * int id;
64 * struct item *prev, *next;
65 * }
66 *
67 * struct item *list = NULL:
68 *
69 * int main() {
70 * struct item *item;
71 * ... allocate and populate item ...
72 * DL_APPEND(list, item);
73 * }
74 * --------------------------------------------------
75 *
76 * For doubly-linked lists, the append and delete macros are O(1)
77 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
78 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
79 */
80
94#ifdef _MSC_VER /* MS compiler */
95#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
96#define LDECLTYPE(x) decltype(x)
97#else /* VS2008 or older (or VS2010 in C mode) */
98#define NO_DECLTYPE
99#define LDECLTYPE(x) char*
100#endif
101#elif defined(__ICCARM__)
102#define NO_DECLTYPE
103#define LDECLTYPE(x) char*
104#else /* GNU, Sun and other compilers */
105#define LDECLTYPE(x) __typeof(x)
106#endif
107
108#ifdef NO_DECLTYPE
109#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
110#define _NEXT(elt,list,next) ((char*)((list)->next))
111#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
112/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
113#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
114#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
115#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
116#else
117#define _SV(elt,list)
118#define _NEXT(elt,list,next) ((elt)->next)
119#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
120/* #define _PREV(elt,list,prev) ((elt)->prev) */
121#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
122#define _RS(list)
123#define _CASTASGN(a,b) (a)=(b)
124#endif
134#define LL_SORT(list, cmp) \
135 LL_SORT2(list, cmp, next)
136
137#define LL_SORT2(list, cmp, next) \
138do { \
139 LDECLTYPE(list) _ls_p; \
140 LDECLTYPE(list) _ls_q; \
141 LDECLTYPE(list) _ls_e; \
142 LDECLTYPE(list) _ls_tail; \
143 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
144 if (list) { \
145 _ls_insize = 1; \
146 _ls_looping = 1; \
147 while (_ls_looping) { \
148 _CASTASGN(_ls_p,list); \
149 list = NULL; \
150 _ls_tail = NULL; \
151 _ls_nmerges = 0; \
152 while (_ls_p) { \
153 _ls_nmerges++; \
154 _ls_q = _ls_p; \
155 _ls_psize = 0; \
156 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
157 _ls_psize++; \
158 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
159 if (!_ls_q) break; \
160 } \
161 _ls_qsize = _ls_insize; \
162 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
163 if (_ls_psize == 0) { \
164 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
165 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
166 } else if (_ls_qsize == 0 || !_ls_q) { \
167 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
168 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
169 } else if (cmp(_ls_p,_ls_q) <= 0) { \
170 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
171 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
172 } else { \
173 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
174 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
175 } \
176 if (_ls_tail) { \
177 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
178 } else { \
179 _CASTASGN(list,_ls_e); \
180 } \
181 _ls_tail = _ls_e; \
182 } \
183 _ls_p = _ls_q; \
184 } \
185 if (_ls_tail) { \
186 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
187 } \
188 if (_ls_nmerges <= 1) { \
189 _ls_looping=0; \
190 } \
191 _ls_insize *= 2; \
192 } \
193 } \
194} while (0)
195
196#define DL_SORT(list, cmp) \
197 DL_SORT2(list, cmp, prev, next)
198
199#define DL_SORT2(list, cmp, prev, next) \
200do { \
201 LDECLTYPE(list) _ls_p; \
202 LDECLTYPE(list) _ls_q; \
203 LDECLTYPE(list) _ls_e; \
204 LDECLTYPE(list) _ls_tail; \
205 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
206 if (list) { \
207 _ls_insize = 1; \
208 _ls_looping = 1; \
209 while (_ls_looping) { \
210 _CASTASGN(_ls_p,list); \
211 list = NULL; \
212 _ls_tail = NULL; \
213 _ls_nmerges = 0; \
214 while (_ls_p) { \
215 _ls_nmerges++; \
216 _ls_q = _ls_p; \
217 _ls_psize = 0; \
218 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
219 _ls_psize++; \
220 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
221 if (!_ls_q) break; \
222 } \
223 _ls_qsize = _ls_insize; \
224 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
225 if (_ls_psize == 0) { \
226 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
227 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
228 } else if (_ls_qsize == 0 || !_ls_q) { \
229 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
230 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
231 } else if (cmp(_ls_p,_ls_q) <= 0) { \
232 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
233 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
234 } else { \
235 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
236 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
237 } \
238 if (_ls_tail) { \
239 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
240 } else { \
241 _CASTASGN(list,_ls_e); \
242 } \
243 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
244 _ls_tail = _ls_e; \
245 } \
246 _ls_p = _ls_q; \
247 } \
248 _CASTASGN(list->prev, _ls_tail); \
249 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
250 if (_ls_nmerges <= 1) { \
251 _ls_looping=0; \
252 } \
253 _ls_insize *= 2; \
254 } \
255 } \
256} while (0)
257
258#define CDL_SORT(list, cmp) \
259 CDL_SORT2(list, cmp, prev, next)
260
261#define CDL_SORT2(list, cmp, prev, next) \
262do { \
263 LDECLTYPE(list) _ls_p; \
264 LDECLTYPE(list) _ls_q; \
265 LDECLTYPE(list) _ls_e; \
266 LDECLTYPE(list) _ls_tail; \
267 LDECLTYPE(list) _ls_oldhead; \
268 LDECLTYPE(list) _tmp; \
269 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
270 if (list) { \
271 _ls_insize = 1; \
272 _ls_looping = 1; \
273 while (_ls_looping) { \
274 _CASTASGN(_ls_p,list); \
275 _CASTASGN(_ls_oldhead,list); \
276 list = NULL; \
277 _ls_tail = NULL; \
278 _ls_nmerges = 0; \
279 while (_ls_p) { \
280 _ls_nmerges++; \
281 _ls_q = _ls_p; \
282 _ls_psize = 0; \
283 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
284 _ls_psize++; \
285 _SV(_ls_q,list); \
286 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
287 _ls_q = NULL; \
288 } else { \
289 _ls_q = _NEXT(_ls_q,list,next); \
290 } \
291 _RS(list); \
292 if (!_ls_q) break; \
293 } \
294 _ls_qsize = _ls_insize; \
295 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
296 if (_ls_psize == 0) { \
297 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
298 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
299 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
300 } else if (_ls_qsize == 0 || !_ls_q) { \
301 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
302 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
303 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
304 } else if (cmp(_ls_p,_ls_q) <= 0) { \
305 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
306 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
307 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
308 } else { \
309 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
310 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
311 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
312 } \
313 if (_ls_tail) { \
314 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
315 } else { \
316 _CASTASGN(list,_ls_e); \
317 } \
318 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
319 _ls_tail = _ls_e; \
320 } \
321 _ls_p = _ls_q; \
322 } \
323 _CASTASGN(list->prev,_ls_tail); \
324 _CASTASGN(_tmp,list); \
325 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
326 if (_ls_nmerges <= 1) { \
327 _ls_looping=0; \
328 } \
329 _ls_insize *= 2; \
330 } \
331 } \
332} while (0)
340#define LL_PREPEND(head,add) \
341 LL_PREPEND2(head,add,next)
342
344#define LL_PREPEND2(head,add,next) \
345do { \
346 (add)->next = head; \
347 head = add; \
348} while (0)
349
351#define LL_CONCAT(head1,head2) \
352 LL_CONCAT2(head1,head2,next)
353
355#define LL_CONCAT2(head1,head2,next) \
356do { \
357 LDECLTYPE(head1) _tmp; \
358 if (head1) { \
359 _tmp = head1; \
360 while (_tmp->next) { _tmp = _tmp->next; } \
361 _tmp->next=(head2); \
362 } else { \
363 (head1)=(head2); \
364 } \
365} while (0)
366
368#define LL_APPEND(head,add) \
369 LL_APPEND2(head,add,next)
370
372#define LL_APPEND2(head,add,next) \
373do { \
374 LDECLTYPE(head) _tmp; \
375 (add)->next=NULL; \
376 if (head) { \
377 _tmp = head; \
378 while (_tmp->next) { _tmp = _tmp->next; } \
379 _tmp->next=(add); \
380 } else { \
381 (head)=(add); \
382 } \
383} while (0)
384
386#define LL_DELETE(head,del) \
387 LL_DELETE2(head,del,next)
388
390#define LL_DELETE2(head,del,next) \
391do { \
392 LDECLTYPE(head) _tmp; \
393 if ((head) == (del)) { \
394 (head)=(head)->next; \
395 } else { \
396 _tmp = head; \
397 while (_tmp->next && (_tmp->next != (del))) { \
398 _tmp = _tmp->next; \
399 } \
400 if (_tmp->next) { \
401 _tmp->next = ((del)->next); \
402 } \
403 } \
404} while (0)
405
406/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
407#define LL_APPEND_VS2008(head,add) \
408 LL_APPEND2_VS2008(head,add,next)
409
410#define LL_APPEND2_VS2008(head,add,next) \
411do { \
412 if (head) { \
413 (add)->next = head; /* use add->next as a temp variable */ \
414 while ((add)->next->next) { (add)->next = (add)->next->next; } \
415 (add)->next->next=(add); \
416 } else { \
417 (head)=(add); \
418 } \
419 (add)->next=NULL; \
420} while (0)
421
422#define LL_DELETE_VS2008(head,del) \
423 LL_DELETE2_VS2008(head,del,next)
424
425#define LL_DELETE2_VS2008(head,del,next) \
426do { \
427 if ((head) == (del)) { \
428 (head)=(head)->next; \
429 } else { \
430 char *_tmp = (char*)(head); \
431 while ((head)->next && ((head)->next != (del))) { \
432 head = (head)->next; \
433 } \
434 if ((head)->next) { \
435 (head)->next = ((del)->next); \
436 } \
437 { \
438 char **_head_alias = (char**)&(head); \
439 *_head_alias = _tmp; \
440 } \
441 } \
442} while (0)
443#ifdef NO_DECLTYPE
444#undef LL_APPEND
445#define LL_APPEND LL_APPEND_VS2008
446#undef LL_DELETE
447#define LL_DELETE LL_DELETE_VS2008
448#undef LL_DELETE2
449#define LL_DELETE2 LL_DELETE2_VS2008
450#undef LL_APPEND2
451#define LL_APPEND2 LL_APPEND2_VS2008
452#undef LL_CONCAT /* no LL_CONCAT_VS2008 */
453#undef DL_CONCAT /* no DL_CONCAT_VS2008 */
454#endif
455/* end VS2008 replacements */
456
458#define LL_COUNT(head,el,counter) \
459 LL_COUNT2(head,el,counter,next) \
460
462#define LL_COUNT2(head,el,counter,next) \
463{ \
464 counter = 0; \
465 LL_FOREACH2(head,el,next){ ++counter; } \
466}
467
469#define LL_FOREACH(head,el) \
470 LL_FOREACH2(head,el,next)
471
473#define LL_FOREACH2(head,el,next) \
474 for(el=head;el;el=(el)->next)
475
480#define LL_FOREACH_SAFE(head,el,tmp) \
481 LL_FOREACH_SAFE2(head,el,tmp,next)
482
484#define LL_FOREACH_SAFE2(head,el,tmp,next) \
485 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
486
488#define LL_SEARCH_SCALAR(head,out,field,val) \
489 LL_SEARCH_SCALAR2(head,out,field,val,next)
490
492#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
493do { \
494 LL_FOREACH2(head,out,next) { \
495 if ((out)->field == (val)) break; \
496 } \
497} while(0)
498
500#define LL_SEARCH(head,out,elt,cmp) \
501 LL_SEARCH2(head,out,elt,cmp,next)
502
504#define LL_SEARCH2(head,out,elt,cmp,next) \
505do { \
506 LL_FOREACH2(head,out,next) { \
507 if ((cmp(out,elt))==0) break; \
508 } \
509} while(0)
510
512#define LL_REPLACE_ELEM(head, el, add) \
513do { \
514 LDECLTYPE(head) _tmp; \
515 assert(head != NULL); \
516 assert(el != NULL); \
517 assert(add != NULL); \
518 (add)->next = (el)->next; \
519 if ((head) == (el)) { \
520 (head) = (add); \
521 } else { \
522 _tmp = head; \
523 while (_tmp->next && (_tmp->next != (el))) { \
524 _tmp = _tmp->next; \
525 } \
526 if (_tmp->next) { \
527 _tmp->next = (add); \
528 } \
529 } \
530} while (0)
531
533#define LL_PREPEND_ELEM(head, el, add) \
534do { \
535 LDECLTYPE(head) _tmp; \
536 assert(head != NULL); \
537 assert(el != NULL); \
538 assert(add != NULL); \
539 (add)->next = (el); \
540 if ((head) == (el)) { \
541 (head) = (add); \
542 } else { \
543 _tmp = head; \
544 while (_tmp->next && (_tmp->next != (el))) { \
545 _tmp = _tmp->next; \
546 } \
547 if (_tmp->next) { \
548 _tmp->next = (add); \
549 } \
550 } \
551} while (0)
559#define DL_PREPEND(head,add) \
560 DL_PREPEND2(head,add,prev,next)
561
563#define DL_PREPEND2(head,add,prev,next) \
564do { \
565 (add)->next = head; \
566 if (head) { \
567 (add)->prev = (head)->prev; \
568 (head)->prev = (add); \
569 } else { \
570 (add)->prev = (add); \
571 } \
572 (head) = (add); \
573} while (0)
574
576#define DL_APPEND(head,add) \
577 DL_APPEND2(head,add,prev,next)
578
580#define DL_APPEND2(head,add,prev,next) \
581do { \
582 if (head) { \
583 (add)->prev = (head)->prev; \
584 (head)->prev->next = (add); \
585 (head)->prev = (add); \
586 (add)->next = NULL; \
587 } else { \
588 (head)=(add); \
589 (head)->prev = (head); \
590 (head)->next = NULL; \
591 } \
592} while (0)
593
595#define DL_CONCAT(head1,head2) \
596 DL_CONCAT2(head1,head2,prev,next)
597
599#define DL_CONCAT2(head1,head2,prev,next) \
600do { \
601 LDECLTYPE(head1) _tmp; \
602 if (head2) { \
603 if (head1) { \
604 _tmp = (head2)->prev; \
605 (head2)->prev = (head1)->prev; \
606 (head1)->prev->next = (head2); \
607 (head1)->prev = _tmp; \
608 } else { \
609 (head1)=(head2); \
610 } \
611 } \
612} while (0)
613
615#define DL_DELETE(head,del) \
616 DL_DELETE2(head,del,prev,next)
617
619#define DL_DELETE2(head,del,prev,next) \
620do { \
621 assert((del)->prev != NULL); \
622 if ((del)->prev == (del)) { \
623 (head)=NULL; \
624 } else if ((del)==(head)) { \
625 (del)->next->prev = (del)->prev; \
626 (head) = (del)->next; \
627 } else { \
628 (del)->prev->next = (del)->next; \
629 if ((del)->next) { \
630 (del)->next->prev = (del)->prev; \
631 } else { \
632 (head)->prev = (del)->prev; \
633 } \
634 } \
635} while (0)
636
638#define DL_COUNT(head,el,counter) \
639 DL_COUNT2(head,el,counter,next) \
640
642#define DL_COUNT2(head,el,counter,next) \
643{ \
644 counter = 0; \
645 DL_FOREACH2(head,el,next){ ++counter; } \
646}
647
649#define DL_FOREACH(head,el) \
650 DL_FOREACH2(head,el,next)
651
653#define DL_FOREACH2(head,el,next) \
654 for(el=head;el;el=(el)->next)
655
660#define DL_FOREACH_SAFE(head,el,tmp) \
661 DL_FOREACH_SAFE2(head,el,tmp,next)
662
664#define DL_FOREACH_SAFE2(head,el,tmp,next) \
665 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
666
671#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
672
677#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
678
683#define DL_SEARCH LL_SEARCH
684
689#define DL_SEARCH2 LL_SEARCH2
690
692#define DL_REPLACE_ELEM(head, el, add) \
693do { \
694 assert(head != NULL); \
695 assert(el != NULL); \
696 assert(add != NULL); \
697 if ((head) == (el)) { \
698 (head) = (add); \
699 (add)->next = (el)->next; \
700 if ((el)->next == NULL) { \
701 (add)->prev = (add); \
702 } else { \
703 (add)->prev = (el)->prev; \
704 (add)->next->prev = (add); \
705 } \
706 } else { \
707 (add)->next = (el)->next; \
708 (add)->prev = (el)->prev; \
709 (add)->prev->next = (add); \
710 if ((el)->next == NULL) { \
711 (head)->prev = (add); \
712 } else { \
713 (add)->next->prev = (add); \
714 } \
715 } \
716} while (0)
717
719#define DL_PREPEND_ELEM(head, el, add) \
720do { \
721 assert(head != NULL); \
722 assert(el != NULL); \
723 assert(add != NULL); \
724 (add)->next = (el); \
725 (add)->prev = (el)->prev; \
726 (el)->prev = (add); \
727 if ((head) == (el)) { \
728 (head) = (add); \
729 } else { \
730 (add)->prev->next = (add); \
731 } \
732} while (0)
740#define CDL_PREPEND(head,add) \
741 CDL_PREPEND2(head,add,prev,next)
742
744#define CDL_PREPEND2(head,add,prev,next) \
745do { \
746 if (head) { \
747 (add)->prev = (head)->prev; \
748 (add)->next = (head); \
749 (head)->prev = (add); \
750 (add)->prev->next = (add); \
751 } else { \
752 (add)->prev = (add); \
753 (add)->next = (add); \
754 } \
755(head)=(add); \
756} while (0)
757
759#define CDL_DELETE(head,del) \
760 CDL_DELETE2(head,del,prev,next)
761
763#define CDL_DELETE2(head,del,prev,next) \
764do { \
765 if ( ((head)==(del)) && ((head)->next == (head))) { \
766 (head) = 0L; \
767 } else { \
768 (del)->next->prev = (del)->prev; \
769 (del)->prev->next = (del)->next; \
770 if ((del) == (head)) (head)=(del)->next; \
771 } \
772} while (0)
773
775#define CDL_COUNT(head,el,counter) \
776 CDL_COUNT2(head,el,counter,next) \
777
779#define CDL_COUNT2(head, el, counter,next) \
780{ \
781 counter = 0; \
782 CDL_FOREACH2(head,el,next){ ++counter; } \
783}
784
786#define CDL_FOREACH(head,el) \
787 CDL_FOREACH2(head,el,next)
788
790#define CDL_FOREACH2(head,el,next) \
791 for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
792
797#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
798 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
799
801#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
802 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
803 (el) && ((tmp2)=(el)->next, 1); \
804 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
805
807#define CDL_SEARCH_SCALAR(head,out,field,val) \
808 CDL_SEARCH_SCALAR2(head,out,field,val,next)
809
811#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
812do { \
813 CDL_FOREACH2(head,out,next) { \
814 if ((out)->field == (val)) break; \
815 } \
816} while(0)
817
819#define CDL_SEARCH(head,out,elt,cmp) \
820 CDL_SEARCH2(head,out,elt,cmp,next)
821
823#define CDL_SEARCH2(head,out,elt,cmp,next) \
824do { \
825 CDL_FOREACH2(head,out,next) { \
826 if ((cmp(out,elt))==0) break; \
827 } \
828} while(0)
829
831#define CDL_REPLACE_ELEM(head, el, add) \
832do { \
833 assert(head != NULL); \
834 assert(el != NULL); \
835 assert(add != NULL); \
836 if ((el)->next == (el)) { \
837 (add)->next = (add); \
838 (add)->prev = (add); \
839 (head) = (add); \
840 } else { \
841 (add)->next = (el)->next; \
842 (add)->prev = (el)->prev; \
843 (add)->next->prev = (add); \
844 (add)->prev->next = (add); \
845 if ((head) == (el)) { \
846 (head) = (add); \
847 } \
848 } \
849} while (0)
850
852#define CDL_PREPEND_ELEM(head, el, add) \
853do { \
854 assert(head != NULL); \
855 assert(el != NULL); \
856 assert(add != NULL); \
857 (add)->next = (el); \
858 (add)->prev = (el)->prev; \
859 (el)->prev = (add); \
860 (add)->prev->next = (add); \
861 if ((head) == (el)) { \
862 (head) = (add); \
863 } \
864} while (0)
867#ifdef __cplusplus
868}
869#endif
870
871#endif /* UTLIST_H */
assert.h
POSIX.1-2008 compliant version of the assert macro.