Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/modules/include/utlist.h

1/*␊
2Copyright (c) 2007-2013, Troy D. Hanson http://uthash.sourceforge.net␊
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␊
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) \␊
103 LL_SORT2(list, cmp, next)␊
104␊
105#define LL_SORT2(list, cmp, next) \␊
106do { \␊
107 LDECLTYPE(list) _ls_p; \␊
108 LDECLTYPE(list) _ls_q; \␊
109 LDECLTYPE(list) _ls_e; \␊
110 LDECLTYPE(list) _ls_tail; \␊
111 LDECLTYPE(list) _ls_oldhead; \␊
112 LDECLTYPE(list) _tmp; \␊
113 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊
114 if (list) { \␊
115 _ls_insize = 1; \␊
116 _ls_looping = 1; \␊
117 while (_ls_looping) { \␊
118 _CASTASGN(_ls_p,list); \␊
119 _CASTASGN(_ls_oldhead,list); \␊
120 list = NULL; \␊
121 _ls_tail = NULL; \␊
122 _ls_nmerges = 0; \␊
123 while (_ls_p) { \␊
124 _ls_nmerges++; \␊
125 _ls_q = _ls_p; \␊
126 _ls_psize = 0; \␊
127 for (_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); \␊
130 if (!_ls_q) break; \␊
131 } \␊
132 _ls_qsize = _ls_insize; \␊
133 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊
134 if (_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 } \␊
147 if (_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); \␊
157 if (_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) \␊
167 DL_SORT2(list, cmp, prev, next)␊
168␊
169#define DL_SORT2(list, cmp, prev, next) \␊
170do { \␊
171 LDECLTYPE(list) _ls_p; \␊
172 LDECLTYPE(list) _ls_q; \␊
173 LDECLTYPE(list) _ls_e; \␊
174 LDECLTYPE(list) _ls_tail; \␊
175 LDECLTYPE(list) _ls_oldhead; \␊
176 LDECLTYPE(list) _tmp; \␊
177 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊
178 if (list) { \␊
179 _ls_insize = 1; \␊
180 _ls_looping = 1; \␊
181 while (_ls_looping) { \␊
182 _CASTASGN(_ls_p,list); \␊
183 _CASTASGN(_ls_oldhead,list); \␊
184 list = NULL; \␊
185 _ls_tail = NULL; \␊
186 _ls_nmerges = 0; \␊
187 while (_ls_p) { \␊
188 _ls_nmerges++; \␊
189 _ls_q = _ls_p; \␊
190 _ls_psize = 0; \␊
191 for (_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); \␊
194 if (!_ls_q) break; \␊
195 } \␊
196 _ls_qsize = _ls_insize; \␊
197 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊
198 if (_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 } \␊
211 if (_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); \␊
223 if (_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) \␊
232 CDL_SORT2(list, cmp, prev, next)␊
233␊
234#define CDL_SORT2(list, cmp, prev, next) \␊
235do { \␊
236 LDECLTYPE(list) _ls_p; \␊
237 LDECLTYPE(list) _ls_q; \␊
238 LDECLTYPE(list) _ls_e; \␊
239 LDECLTYPE(list) _ls_tail; \␊
240 LDECLTYPE(list) _ls_oldhead; \␊
241 LDECLTYPE(list) _tmp; \␊
242 LDECLTYPE(list) _tmp2; \␊
243 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊
244 if (list) { \␊
245 _ls_insize = 1; \␊
246 _ls_looping = 1; \␊
247 while (_ls_looping) { \␊
248 _CASTASGN(_ls_p,list); \␊
249 _CASTASGN(_ls_oldhead,list); \␊
250 list = NULL; \␊
251 _ls_tail = NULL; \␊
252 _ls_nmerges = 0; \␊
253 while (_ls_p) { \␊
254 _ls_nmerges++; \␊
255 _ls_q = _ls_p; \␊
256 _ls_psize = 0; \␊
257 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊
258 _ls_psize++; \␊
259 _SV(_ls_q,list); \␊
260 if (_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); \␊
266 if (!_ls_q) break; \␊
267 } \␊
268 _ls_qsize = _ls_insize; \␊
269 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊
270 if (_ls_psize == 0) { \␊
271 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \␊
272 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \␊
273 if (_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--; \␊
277 if (_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--; \␊
281 if (_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--; \␊
285 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \␊
286 } \␊
287 if (_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); \␊
300 if (_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) \␊
312 LL_PREPEND2(head,add,next)␊
313␊
314#define LL_PREPEND2(head,add,next) \␊
315do { \␊
316 (add)->next = head; \␊
317 head = add; \␊
318} while (0)␊
319␊
320#define LL_CONCAT(head1,head2) \␊
321 LL_CONCAT2(head1,head2,next)␊
322␊
323#define LL_CONCAT2(head1,head2,next) \␊
324do { \␊
325 LDECLTYPE(head1) _tmp; \␊
326 if (head1) { \␊
327 _tmp = head1; \␊
328 while (_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) \␊
336 LL_APPEND2(head,add,next)␊
337␊
338#define LL_APPEND2(head,add,next) \␊
339do { \␊
340 LDECLTYPE(head) _tmp; \␊
341 (add)->next=NULL; \␊
342 if (head) { \␊
343 _tmp = head; \␊
344 while (_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) \␊
352 LL_DELETE2(head,del,next)␊
353␊
354#define LL_DELETE2(head,del,next) \␊
355do { \␊
356 LDECLTYPE(head) _tmp; \␊
357 if ((head) == (del)) { \␊
358 (head)=(head)->next; \␊
359 } else { \␊
360 _tmp = head; \␊
361 while (_tmp->next && (_tmp->next != (del))) { \␊
362 _tmp = _tmp->next; \␊
363 } \␊
364 if (_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) \␊
372 LL_APPEND2_VS2008(head,add,next)␊
373␊
374#define LL_APPEND2_VS2008(head,add,next) \␊
375do { \␊
376 if (head) { \␊
377 (add)->next = head; /* use add->next as a temp variable */ \␊
378 while ((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) \␊
387 LL_DELETE2_VS2008(head,del,next)␊
388␊
389#define LL_DELETE2_VS2008(head,del,next) \␊
390do { \␊
391 if ((head) == (del)) { \␊
392 (head)=(head)->next; \␊
393 } else { \␊
394 char *_tmp = (char*)(head); \␊
395 while ((head)->next && ((head)->next != (del))) { \␊
396 head = (head)->next; \␊
397 } \␊
398 if ((head)->next) { \␊
399 (head)->next = ((del)->next); \␊
400 } \␊
401 { \␊
402 char **_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) \␊
422 LL_FOREACH2(head,el,next)␊
423␊
424#define LL_FOREACH2(head,el,next) \␊
425 for(el=head;el;el=(el)->next)␊
426␊
427#define LL_FOREACH_SAFE(head,el,tmp) \␊
428 LL_FOREACH_SAFE2(head,el,tmp,next)␊
429␊
430#define LL_FOREACH_SAFE2(head,el,tmp,next) \␊
431 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)␊
432␊
433#define LL_SEARCH_SCALAR(head,out,field,val) \␊
434 LL_SEARCH_SCALAR2(head,out,field,val,next)␊
435␊
436#define LL_SEARCH_SCALAR2(head,out,field,val,next) \␊
437do { \␊
438 LL_FOREACH2(head,out,next) { \␊
439 if ((out)->field == (val)) break; \␊
440 } \␊
441} while(0) ␊
442␊
443#define LL_SEARCH(head,out,elt,cmp) \␊
444 LL_SEARCH2(head,out,elt,cmp,next)␊
445␊
446#define LL_SEARCH2(head,out,elt,cmp,next) \␊
447do { \␊
448 LL_FOREACH2(head,out,next) { \␊
449 if ((cmp(out,elt))==0) break; \␊
450 } \␊
451} while(0) ␊
452␊
453#define LL_REPLACE_ELEM(head, el, add) \␊
454do { \␊
455 LDECLTYPE(head) _tmp; \␊
456 assert(head != NULL); \␊
457 assert(el != NULL); \␊
458 assert(add != NULL); \␊
459 (add)->next = (el)->next; \␊
460 if ((head) == (el)) { \␊
461 (head) = (add); \␊
462 } else { \␊
463 _tmp = head; \␊
464 while (_tmp->next && (_tmp->next != (el))) { \␊
465 _tmp = _tmp->next; \␊
466 } \␊
467 if (_tmp->next) { \␊
468 _tmp->next = (add); \␊
469 } \␊
470 } \␊
471} while (0)␊
472␊
473#define LL_PREPEND_ELEM(head, el, add) \␊
474do { \␊
475 LDECLTYPE(head) _tmp; \␊
476 assert(head != NULL); \␊
477 assert(el != NULL); \␊
478 assert(add != NULL); \␊
479 (add)->next = (el); \␊
480 if ((head) == (el)) { \␊
481 (head) = (add); \␊
482 } else { \␊
483 _tmp = head; \␊
484 while (_tmp->next && (_tmp->next != (el))) { \␊
485 _tmp = _tmp->next; \␊
486 } \␊
487 if (_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) \␊
498 DL_PREPEND2(head,add,prev,next)␊
499␊
500#define DL_PREPEND2(head,add,prev,next) \␊
501do { \␊
502 (add)->next = head; \␊
503 if (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) \␊
513 DL_APPEND2(head,add,prev,next)␊
514␊
515#define DL_APPEND2(head,add,prev,next) \␊
516do { \␊
517 if (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) \␊
530 DL_CONCAT2(head1,head2,prev,next)␊
531␊
532#define DL_CONCAT2(head1,head2,prev,next) \␊
533do { \␊
534 LDECLTYPE(head1) _tmp; \␊
535 if (head2) { \␊
536 if (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) \␊
548 DL_DELETE2(head,del,prev,next)␊
549␊
550#define DL_DELETE2(head,del,prev,next) \␊
551do { \␊
552 assert((del)->prev != NULL); \␊
553 if ((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; \␊
560 if ((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) \␊
570 DL_FOREACH2(head,el,next)␊
571␊
572#define DL_FOREACH2(head,el,next) \␊
573 for(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) \␊
577 DL_FOREACH_SAFE2(head,el,tmp,next)␊
578␊
579#define DL_FOREACH_SAFE2(head,el,tmp,next) \␊
580 for((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 { \␊
590 assert(head != NULL); \␊
591 assert(el != NULL); \␊
592 assert(add != NULL); \␊
593 if ((head) == (el)) { \␊
594 (head) = (add); \␊
595 (add)->next = (el)->next; \␊
596 if ((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); \␊
606 if ((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 { \␊
616 assert(head != NULL); \␊
617 assert(el != NULL); \␊
618 assert(add != NULL); \␊
619 (add)->next = (el); \␊
620 (add)->prev = (el)->prev; \␊
621 (el)->prev = (add); \␊
622 if ((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) \␊
634 CDL_PREPEND2(head,add,prev,next)␊
635␊
636#define CDL_PREPEND2(head,add,prev,next) \␊
637do { \␊
638 if (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) \␊
651 CDL_DELETE2(head,del,prev,next)␊
652␊
653#define CDL_DELETE2(head,del,prev,next) \␊
654do { \␊
655 if ( ((head)==(del)) && ((head)->next == (head))) { \␊
656 (head) = 0L; \␊
657 } else { \␊
658 (del)->next->prev = (del)->prev; \␊
659 (del)->prev->next = (del)->next; \␊
660 if ((del) == (head)) (head)=(del)->next; \␊
661 } \␊
662} while (0) ␊
663␊
664#define CDL_FOREACH(head,el) \␊
665 CDL_FOREACH2(head,el,next)␊
666␊
667#define CDL_FOREACH2(head,el,next) \␊
668 for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) ␊
669␊
670#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \␊
671 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)␊
672␊
673#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \␊
674 for((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) \␊
679 CDL_SEARCH_SCALAR2(head,out,field,val,next)␊
680␊
681#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \␊
682do { \␊
683 CDL_FOREACH2(head,out,next) { \␊
684 if ((out)->field == (val)) break; \␊
685 } \␊
686} while(0) ␊
687␊
688#define CDL_SEARCH(head,out,elt,cmp) \␊
689 CDL_SEARCH2(head,out,elt,cmp,next)␊
690␊
691#define CDL_SEARCH2(head,out,elt,cmp,next) \␊
692do { \␊
693 CDL_FOREACH2(head,out,next) { \␊
694 if ((cmp(out,elt))==0) break; \␊
695 } \␊
696} while(0) ␊
697␊
698#define CDL_REPLACE_ELEM(head, el, add) \␊
699do { \␊
700 assert(head != NULL); \␊
701 assert(el != NULL); \␊
702 assert(add != NULL); \␊
703 if ((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); \␊
712 if ((head) == (el)) { \␊
713 (head) = (add); \␊
714 } \␊
715 } \␊
716} while (0)␊
717␊
718#define CDL_PREPEND_ELEM(head, el, add) \␊
719do { \␊
720 assert(head != NULL); \␊
721 assert(el != NULL); \␊
722 assert(add != NULL); \␊
723 (add)->next = (el); \␊
724 (add)->prev = (el)->prev; \␊
725 (el)->prev = (add); \␊
726 (add)->prev->next = (add); \␊
727 if ((head) == (el)) { \␊
728 (head) = (add); \␊
729 } \␊
730} while (0) \␊
731␊
732#endif /* UTLIST_H */␊
733␊
734

Archive Download this file

Revision: 2182