]> Git Repo - VerusCoin.git/blame - src/utlist.h
projects / VerusCoin.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #128 from miketout/dev
[VerusCoin.git] / src / utlist.h
CommitLineData
eebc32ea 1/*
2 Copyright (c) 2007-2014, Troy D. Hanson http://troydhanson.github.com/uthash/
3 All rights reserved.
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
9 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
10 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
11 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
12 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
13 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
14 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
15 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
16 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
17 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
18 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
19 */
20
21#ifndef UTLIST_H
22#define UTLIST_H
23
24#define UTLIST_VERSION 1.9.9
25
26#include <assert.h>
27
28/*
29 * This file contains macros to manipulate singly and doubly-linked lists.
30 *
31 * 1. LL_ macros: singly-linked lists.
32 * 2. DL_ macros: doubly-linked lists.
33 * 3. CDL_ macros: circular doubly-linked lists.
34 *
35 * To use singly-linked lists, your structure must have a "next" pointer.
36 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
37 * Either way, the pointer to the head of the list must be initialized to NULL.
38 *
39 * ----------------.EXAMPLE -------------------------
40 * struct item {
41 * int id;
42 * struct item *prev, *next;
43 * }
44 *
45 * struct item *list = NULL:
46 *
47 * int main() {
48 * struct item *item;
49 * ... allocate and populate item ...
50 * DL_APPEND(list, item);
51 * }
52 * --------------------------------------------------
53 *
54 * For doubly-linked lists, the append and delete macros are O(1)
55 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
56 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
57 */
58
59/* These macros use decltype or the earlier __typeof GNU extension.
60 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
61 when compiling c++ code), this code uses whatever method is needed
62 or, for VS2008 where neither is available, uses casting workarounds. */
63#ifdef _MSC_VER /* MS compiler */
64#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
65#define LDECLTYPE(x) decltype(x)
66#else /* VS2008 or older (or VS2010 in C mode) */
67#define NO_DECLTYPE
68#define LDECLTYPE(x) char*
69#endif
70#elif defined(__ICCARM__)
71#define NO_DECLTYPE
72#define LDECLTYPE(x) char*
73#else /* GNU, Sun and other compilers */
74#define LDECLTYPE(x) __typeof(x)
75#endif
76
77/* for VS2008 we use some workarounds to get around the lack of decltype,
78 * namely, we always reassign our tmp variable to the list head if we need
79 * to dereference its prev/next pointers, and save/restore the real head.*/
80#ifdef NO_DECLTYPE
81#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
82#define _NEXT(elt,list,next) ((char*)((list)->next))
83#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
84/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
85#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
86#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
87#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
88#else
89#define _SV(elt,list)
90#define _NEXT(elt,list,next) ((elt)->next)
91#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
92/* #define _PREV(elt,list,prev) ((elt)->prev) */
93#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
94#define _RS(list)
95#define _CASTASGN(a,b) (a)=(b)
96#endif
97
98/******************************************************************************
99 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
100 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
101 *****************************************************************************/
102#define LL_SORT(list, cmp) \
103LL_SORT2(list, cmp, next)
104
105#define LL_SORT2(list, cmp, next) \
106do { \
107LDECLTYPE(list) _ls_p; \
108LDECLTYPE(list) _ls_q; \
109LDECLTYPE(list) _ls_e; \
110LDECLTYPE(list) _ls_tail; \
111int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
112if (list) { \
113_ls_insize = 1; \
114_ls_looping = 1; \
115while (_ls_looping) { \
116_CASTASGN(_ls_p,list); \
117list = NULL; \
118_ls_tail = NULL; \
119_ls_nmerges = 0; \
120while (_ls_p) { \
121_ls_nmerges++; \
122_ls_q = _ls_p; \
123_ls_psize = 0; \
124for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
125_ls_psize++; \
126_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
127if (!_ls_q) break; \
128} \
129_ls_qsize = _ls_insize; \
130while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
131if (_ls_psize == 0) { \
132_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
133_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
134} else if (_ls_qsize == 0 || !_ls_q) { \
135_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
136_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
137} else if (cmp(_ls_p,_ls_q) <= 0) { \
138_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
139_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
140} else { \
141_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
142_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
143} \
144if (_ls_tail) { \
145_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
146} else { \
147_CASTASGN(list,_ls_e); \
148} \
149_ls_tail = _ls_e; \
150} \
151_ls_p = _ls_q; \
152} \
153if (_ls_tail) { \
154_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
155} \
156if (_ls_nmerges <= 1) { \
157_ls_looping=0; \
158} \
159_ls_insize *= 2; \
160} \
161} \
162} while (0)
163
164
165#define DL_SORT(list, cmp) \
166DL_SORT2(list, cmp, prev, next)
167
168#define DL_SORT2(list, cmp, prev, next) \
169do { \
170LDECLTYPE(list) _ls_p; \
171LDECLTYPE(list) _ls_q; \
172LDECLTYPE(list) _ls_e; \
173LDECLTYPE(list) _ls_tail; \
174int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
175if (list) { \
176_ls_insize = 1; \
177_ls_looping = 1; \
178while (_ls_looping) { \
179_CASTASGN(_ls_p,list); \
180list = NULL; \
181_ls_tail = NULL; \
182_ls_nmerges = 0; \
183while (_ls_p) { \
184_ls_nmerges++; \
185_ls_q = _ls_p; \
186_ls_psize = 0; \
187for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
188_ls_psize++; \
189_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
190if (!_ls_q) break; \
191} \
192_ls_qsize = _ls_insize; \
193while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
194if (_ls_psize == 0) { \
195_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
196_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
197} else if (_ls_qsize == 0 || !_ls_q) { \
198_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
199_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
200} else if (cmp(_ls_p,_ls_q) <= 0) { \
201_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
202_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
203} else { \
204_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
205_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
206} \
207if (_ls_tail) { \
208_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
209} else { \
210_CASTASGN(list,_ls_e); \
211} \
212_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
213_ls_tail = _ls_e; \
214} \
215_ls_p = _ls_q; \
216} \
217_CASTASGN(list->prev, _ls_tail); \
218_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
219if (_ls_nmerges <= 1) { \
220_ls_looping=0; \
221} \
222_ls_insize *= 2; \
223} \
224} \
225} while (0)
226
227#define CDL_SORT(list, cmp) \
228CDL_SORT2(list, cmp, prev, next)
229
230#define CDL_SORT2(list, cmp, prev, next) \
231do { \
232LDECLTYPE(list) _ls_p; \
233LDECLTYPE(list) _ls_q; \
234LDECLTYPE(list) _ls_e; \
235LDECLTYPE(list) _ls_tail; \
236LDECLTYPE(list) _ls_oldhead; \
237LDECLTYPE(list) _tmp; \
238int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
239if (list) { \
240_ls_insize = 1; \
241_ls_looping = 1; \
242while (_ls_looping) { \
243_CASTASGN(_ls_p,list); \
244_CASTASGN(_ls_oldhead,list); \
245list = NULL; \
246_ls_tail = NULL; \
247_ls_nmerges = 0; \
248while (_ls_p) { \
249_ls_nmerges++; \
250_ls_q = _ls_p; \
251_ls_psize = 0; \
252for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
253_ls_psize++; \
254_SV(_ls_q,list); \
255if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
256_ls_q = NULL; \
257} else { \
258_ls_q = _NEXT(_ls_q,list,next); \
259} \
260_RS(list); \
261if (!_ls_q) break; \
262} \
263_ls_qsize = _ls_insize; \
264while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
265if (_ls_psize == 0) { \
266_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
267_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
268if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
269} else if (_ls_qsize == 0 || !_ls_q) { \
270_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
271_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
272if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
273} else if (cmp(_ls_p,_ls_q) <= 0) { \
274_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
275_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
276if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
277} else { \
278_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
279_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
280if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
281} \
282if (_ls_tail) { \
283_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
284} else { \
285_CASTASGN(list,_ls_e); \
286} \
287_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
288_ls_tail = _ls_e; \
289} \
290_ls_p = _ls_q; \
291} \
292_CASTASGN(list->prev,_ls_tail); \
293_CASTASGN(_tmp,list); \
294_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
295if (_ls_nmerges <= 1) { \
296_ls_looping=0; \
297} \
298_ls_insize *= 2; \
299} \
300} \
301} while (0)
302
303/******************************************************************************
304 * singly linked list macros (non-circular) *
305 *****************************************************************************/
306#define LL_PREPEND(head,add) \
307LL_PREPEND2(head,add,next)
308
309#define LL_PREPEND2(head,add,next) \
310do { \
311(add)->next = head; \
312head = add; \
313} while (0)
314
315#define LL_CONCAT(head1,head2) \
316LL_CONCAT2(head1,head2,next)
317
318#define LL_CONCAT2(head1,head2,next) \
319do { \
320LDECLTYPE(head1) _tmp; \
321if (head1) { \
322_tmp = head1; \
323while (_tmp->next) { _tmp = _tmp->next; } \
324_tmp->next=(head2); \
325} else { \
326(head1)=(head2); \
327} \
328} while (0)
329
330#define LL_APPEND(head,add) \
331LL_APPEND2(head,add,next)
332
333#define LL_APPEND2(head,add,next) \
334do { \
335LDECLTYPE(head) _tmp; \
336(add)->next=NULL; \
337if (head) { \
338_tmp = head; \
339while (_tmp->next) { _tmp = _tmp->next; } \
340_tmp->next=(add); \
341} else { \
342(head)=(add); \
343} \
344} while (0)
345
346#define LL_DELETE(head,del) \
347LL_DELETE2(head,del,next)
348
349#define LL_DELETE2(head,del,next) \
350do { \
351LDECLTYPE(head) _tmp; \
352if ((head) == (del)) { \
353(head)=(head)->next; \
354} else { \
355_tmp = head; \
356while (_tmp->next && (_tmp->next != (del))) { \
357_tmp = _tmp->next; \
358} \
359if (_tmp->next) { \
360_tmp->next = ((del)->next); \
361} \
362} \
363} while (0)
364
365/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
366#define LL_APPEND_VS2008(head,add) \
367LL_APPEND2_VS2008(head,add,next)
368
369#define LL_APPEND2_VS2008(head,add,next) \
370do { \
371if (head) { \
372(add)->next = head; /* use add->next as a temp variable */ \
373while ((add)->next->next) { (add)->next = (add)->next->next; } \
374(add)->next->next=(add); \
375} else { \
376(head)=(add); \
377} \
378(add)->next=NULL; \
379} while (0)
380
381#define LL_DELETE_VS2008(head,del) \
382LL_DELETE2_VS2008(head,del,next)
383
384#define LL_DELETE2_VS2008(head,del,next) \
385do { \
386if ((head) == (del)) { \
387(head)=(head)->next; \
388} else { \
389char *_tmp = (char*)(head); \
390while ((head)->next && ((head)->next != (del))) { \
391head = (head)->next; \
392} \
393if ((head)->next) { \
394(head)->next = ((del)->next); \
395} \
396{ \
397char **_head_alias = (char**)&(head); \
398*_head_alias = _tmp; \
399} \
400} \
401} while (0)
402#ifdef NO_DECLTYPE
403#undef LL_APPEND
404#define LL_APPEND LL_APPEND_VS2008
405#undef LL_DELETE
406#define LL_DELETE LL_DELETE_VS2008
407#undef LL_DELETE2
408#define LL_DELETE2 LL_DELETE2_VS2008
409#undef LL_APPEND2
410#define LL_APPEND2 LL_APPEND2_VS2008
411#undef LL_CONCAT /* no LL_CONCAT_VS2008 */
412#undef DL_CONCAT /* no DL_CONCAT_VS2008 */
413#endif
414/* end VS2008 replacements */
415
416#define LL_COUNT(head,el,counter) \
417LL_COUNT2(head,el,counter,next) \
418
419#define LL_COUNT2(head,el,counter,next) \
420{ \
421counter = 0; \
422LL_FOREACH2(head,el,next){ ++counter; } \
423}
424
425#define LL_FOREACH(head,el) \
426LL_FOREACH2(head,el,next)
427
428#define LL_FOREACH2(head,el,next) \
429for(el=head;el;el=(el)->next)
430
431#define LL_FOREACH_SAFE(head,el,tmp) \
432LL_FOREACH_SAFE2(head,el,tmp,next)
433
434#define LL_FOREACH_SAFE2(head,el,tmp,next) \
435for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
436
437#define LL_SEARCH_SCALAR(head,out,field,val) \
438LL_SEARCH_SCALAR2(head,out,field,val,next)
439
440#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
441do { \
442LL_FOREACH2(head,out,next) { \
443if ((out)->field == (val)) break; \
444} \
445} while(0)
446
447#define LL_SEARCH(head,out,elt,cmp) \
448LL_SEARCH2(head,out,elt,cmp,next)
449
450#define LL_SEARCH2(head,out,elt,cmp,next) \
451do { \
452LL_FOREACH2(head,out,next) { \
453if ((cmp(out,elt))==0) break; \
454} \
455} while(0)
456
457#define LL_REPLACE_ELEM(head, el, add) \
458do { \
459LDECLTYPE(head) _tmp; \
460assert(head != NULL); \
461assert(el != NULL); \
462assert(add != NULL); \
463(add)->next = (el)->next; \
464if ((head) == (el)) { \
465(head) = (add); \
466} else { \
467_tmp = head; \
468while (_tmp->next && (_tmp->next != (el))) { \
469_tmp = _tmp->next; \
470} \
471if (_tmp->next) { \
472_tmp->next = (add); \
473} \
474} \
475} while (0)
476
477#define LL_PREPEND_ELEM(head, el, add) \
478do { \
479LDECLTYPE(head) _tmp; \
480assert(head != NULL); \
481assert(el != NULL); \
482assert(add != NULL); \
483(add)->next = (el); \
484if ((head) == (el)) { \
485(head) = (add); \
486} else { \
487_tmp = head; \
488while (_tmp->next && (_tmp->next != (el))) { \
489_tmp = _tmp->next; \
490} \
491if (_tmp->next) { \
492_tmp->next = (add); \
493} \
494} \
495} while (0) \
496
497
498/******************************************************************************
499 * doubly linked list macros (non-circular) *
500 *****************************************************************************/
501#define DL_PREPEND(head,add) \
502DL_PREPEND2(head,add,prev,next)
503
504#define DL_PREPEND2(head,add,prev,next) \
505do { \
506(add)->next = head; \
507if (head) { \
508(add)->prev = (head)->prev; \
509(head)->prev = (add); \
510} else { \
511(add)->prev = (add); \
512} \
513(head) = (add); \
514} while (0)
515
516#define DL_APPEND(head,add) \
517DL_APPEND2(head,add,prev,next)
518
519#define DL_APPEND2(head,add,prev,next) \
520do { \
521if (head) { \
522(add)->prev = (head)->prev; \
523(head)->prev->next = (add); \
524(head)->prev = (add); \
525(add)->next = NULL; \
526} else { \
527(head)=(add); \
528(head)->prev = (head); \
529(head)->next = NULL; \
530} \
531} while (0)
532
533#define DL_CONCAT(head1,head2) \
534DL_CONCAT2(head1,head2,prev,next)
535
536#define DL_CONCAT2(head1,head2,prev,next) \
537do { \
538LDECLTYPE(head1) _tmp; \
539if (head2) { \
540if (head1) { \
541_tmp = (head2)->prev; \
542(head2)->prev = (head1)->prev; \
543(head1)->prev->next = (head2); \
544(head1)->prev = _tmp; \
545} else { \
546(head1)=(head2); \
547} \
548} \
549} while (0)
550
551#define DL_DELETE(head,del) \
552DL_DELETE2(head,del,prev,next)
553
554#define DL_DELETE2(head,del,prev,next) \
555do { \
556assert((del)->prev != NULL); \
557if ((del)->prev == (del)) { \
558(head)=NULL; \
559} else if ((del)==(head)) { \
560(del)->next->prev = (del)->prev; \
561(head) = (del)->next; \
562} else { \
563(del)->prev->next = (del)->next; \
564if ((del)->next) { \
565(del)->next->prev = (del)->prev; \
566} else { \
567(head)->prev = (del)->prev; \
568} \
569} \
570} while (0)
571
572#define DL_COUNT(head,el,counter) \
573DL_COUNT2(head,el,counter,next) \
574
575#define DL_COUNT2(head,el,counter,next) \
576{ \
577counter = 0; \
578DL_FOREACH2(head,el,next){ ++counter; } \
579}
580
581#define DL_FOREACH(head,el) \
582DL_FOREACH2(head,el,next)
583
584#define DL_FOREACH2(head,el,next) \
585for(el=head;el;el=(el)->next)
586
587/* this version is safe for deleting the elements during iteration */
588#define DL_FOREACH_SAFE(head,el,tmp) \
589DL_FOREACH_SAFE2(head,el,tmp,next)
590
591#define DL_FOREACH_SAFE2(head,el,tmp,next) \
592for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
593
594/* these are identical to their singly-linked list counterparts */
595#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
596#define DL_SEARCH LL_SEARCH
597#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
598#define DL_SEARCH2 LL_SEARCH2
599
600#define DL_REPLACE_ELEM(head, el, add) \
601do { \
602assert(head != NULL); \
603assert(el != NULL); \
604assert(add != NULL); \
605if ((head) == (el)) { \
606(head) = (add); \
607(add)->next = (el)->next; \
608if ((el)->next == NULL) { \
609(add)->prev = (add); \
610} else { \
611(add)->prev = (el)->prev; \
612(add)->next->prev = (add); \
613} \
614} else { \
615(add)->next = (el)->next; \
616(add)->prev = (el)->prev; \
617(add)->prev->next = (add); \
618if ((el)->next == NULL) { \
619(head)->prev = (add); \
620} else { \
621(add)->next->prev = (add); \
622} \
623} \
624} while (0)
625
626#define DL_PREPEND_ELEM(head, el, add) \
627do { \
628assert(head != NULL); \
629assert(el != NULL); \
630assert(add != NULL); \
631(add)->next = (el); \
632(add)->prev = (el)->prev; \
633(el)->prev = (add); \
634if ((head) == (el)) { \
635(head) = (add); \
636} else { \
637(add)->prev->next = (add); \
638} \
639} while (0) \
640
641
642/******************************************************************************
643 * circular doubly linked list macros *
644 *****************************************************************************/
645#define CDL_PREPEND(head,add) \
646CDL_PREPEND2(head,add,prev,next)
647
648#define CDL_PREPEND2(head,add,prev,next) \
649do { \
650if (head) { \
651(add)->prev = (head)->prev; \
652(add)->next = (head); \
653(head)->prev = (add); \
654(add)->prev->next = (add); \
655} else { \
656(add)->prev = (add); \
657(add)->next = (add); \
658} \
659(head)=(add); \
660} while (0)
661
662#define CDL_DELETE(head,del) \
663CDL_DELETE2(head,del,prev,next)
664
665#define CDL_DELETE2(head,del,prev,next) \
666do { \
667if ( ((head)==(del)) && ((head)->next == (head))) { \
668(head) = 0L; \
669} else { \
670(del)->next->prev = (del)->prev; \
671(del)->prev->next = (del)->next; \
672if ((del) == (head)) (head)=(del)->next; \
673} \
674} while (0)
675
676#define CDL_COUNT(head,el,counter) \
677CDL_COUNT2(head,el,counter,next) \
678
679#define CDL_COUNT2(head, el, counter,next) \
680{ \
681counter = 0; \
682CDL_FOREACH2(head,el,next){ ++counter; } \
683}
684
685#define CDL_FOREACH(head,el) \
686CDL_FOREACH2(head,el,next)
687
688#define CDL_FOREACH2(head,el,next) \
689for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
690
691#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
692CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
693
694#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
695for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
696(el) && ((tmp2)=(el)->next, 1); \
697((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
698
699#define CDL_SEARCH_SCALAR(head,out,field,val) \
700CDL_SEARCH_SCALAR2(head,out,field,val,next)
701
702#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
703do { \
704CDL_FOREACH2(head,out,next) { \
705if ((out)->field == (val)) break; \
706} \
707} while(0)
708
709#define CDL_SEARCH(head,out,elt,cmp) \
710CDL_SEARCH2(head,out,elt,cmp,next)
711
712#define CDL_SEARCH2(head,out,elt,cmp,next) \
713do { \
714CDL_FOREACH2(head,out,next) { \
715if ((cmp(out,elt))==0) break; \
716} \
717} while(0)
718
719#define CDL_REPLACE_ELEM(head, el, add) \
720do { \
721assert(head != NULL); \
722assert(el != NULL); \
723assert(add != NULL); \
724if ((el)->next == (el)) { \
725(add)->next = (add); \
726(add)->prev = (add); \
727(head) = (add); \
728} else { \
729(add)->next = (el)->next; \
730(add)->prev = (el)->prev; \
731(add)->next->prev = (add); \
732(add)->prev->next = (add); \
733if ((head) == (el)) { \
734(head) = (add); \
735} \
736} \
737} while (0)
738
739#define CDL_PREPEND_ELEM(head, el, add) \
740do { \
741assert(head != NULL); \
742assert(el != NULL); \
743assert(add != NULL); \
744(add)->next = (el); \
745(add)->prev = (el)->prev; \
746(el)->prev = (add); \
747(add)->prev->next = (add); \
748if ((head) == (el)) { \
749(head) = (add); \
750} \
751} while (0) \
752
753#endif /* UTLIST_H */
Empty description
This page took 0.243263 seconds and 4 git commands to generate.