Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/libsaio/utlist.h

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

Archive Download this file

Revision: HEAD