1 | /*␊ |
2 | Copyright (c) 2007-2012, 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.6␊ |
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) ((char*)((list)->next))␊ |
83 | #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }␊ |
84 | #define _PREV(elt,list) ((char*)((list)->prev))␊ |
85 | #define _PREVASGN(elt,list,to) { 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) ((elt)->next)␊ |
91 | #define _NEXTASGN(elt,list,to) ((elt)->next)=(to)␊ |
92 | #define _PREV(elt,list) ((elt)->prev)␊ |
93 | #define _PREVASGN(elt,list,to) ((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 | do { \␊ |
104 | LDECLTYPE(list) _ls_p; \␊ |
105 | LDECLTYPE(list) _ls_q; \␊ |
106 | LDECLTYPE(list) _ls_e; \␊ |
107 | LDECLTYPE(list) _ls_tail; \␊ |
108 | LDECLTYPE(list) _ls_oldhead; \␊ |
109 | LDECLTYPE(list) _tmp; \␊ |
110 | int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊ |
111 | if (list) { \␊ |
112 | _ls_insize = 1; \␊ |
113 | _ls_looping = 1; \␊ |
114 | while (_ls_looping) { \␊ |
115 | _CASTASGN(_ls_p,list); \␊ |
116 | _CASTASGN(_ls_oldhead,list); \␊ |
117 | list = NULL; \␊ |
118 | _ls_tail = NULL; \␊ |
119 | _ls_nmerges = 0; \␊ |
120 | while (_ls_p) { \␊ |
121 | _ls_nmerges++; \␊ |
122 | _ls_q = _ls_p; \␊ |
123 | _ls_psize = 0; \␊ |
124 | for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊ |
125 | _ls_psize++; \␊ |
126 | _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \␊ |
127 | if (!_ls_q) break; \␊ |
128 | } \␊ |
129 | _ls_qsize = _ls_insize; \␊ |
130 | while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊ |
131 | if (_ls_psize == 0) { \␊ |
132 | _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊ |
133 | } else if (_ls_qsize == 0 || !_ls_q) { \␊ |
134 | _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊ |
135 | } else if (cmp(_ls_p,_ls_q) <= 0) { \␊ |
136 | _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊ |
137 | } else { \␊ |
138 | _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊ |
139 | } \␊ |
140 | if (_ls_tail) { \␊ |
141 | _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \␊ |
142 | } else { \␊ |
143 | _CASTASGN(list,_ls_e); \␊ |
144 | } \␊ |
145 | _ls_tail = _ls_e; \␊ |
146 | } \␊ |
147 | _ls_p = _ls_q; \␊ |
148 | } \␊ |
149 | _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \␊ |
150 | if (_ls_nmerges <= 1) { \␊ |
151 | _ls_looping=0; \␊ |
152 | } \␊ |
153 | _ls_insize *= 2; \␊ |
154 | } \␊ |
155 | } else _tmp=NULL; /* quiet gcc unused variable warning */ \␊ |
156 | } while (0)␊ |
157 | ␊ |
158 | #define DL_SORT(list, cmp) \␊ |
159 | do { \␊ |
160 | LDECLTYPE(list) _ls_p; \␊ |
161 | LDECLTYPE(list) _ls_q; \␊ |
162 | LDECLTYPE(list) _ls_e; \␊ |
163 | LDECLTYPE(list) _ls_tail; \␊ |
164 | LDECLTYPE(list) _ls_oldhead; \␊ |
165 | LDECLTYPE(list) _tmp; \␊ |
166 | int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊ |
167 | if (list) { \␊ |
168 | _ls_insize = 1; \␊ |
169 | _ls_looping = 1; \␊ |
170 | while (_ls_looping) { \␊ |
171 | _CASTASGN(_ls_p,list); \␊ |
172 | _CASTASGN(_ls_oldhead,list); \␊ |
173 | list = NULL; \␊ |
174 | _ls_tail = NULL; \␊ |
175 | _ls_nmerges = 0; \␊ |
176 | while (_ls_p) { \␊ |
177 | _ls_nmerges++; \␊ |
178 | _ls_q = _ls_p; \␊ |
179 | _ls_psize = 0; \␊ |
180 | for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊ |
181 | _ls_psize++; \␊ |
182 | _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \␊ |
183 | if (!_ls_q) break; \␊ |
184 | } \␊ |
185 | _ls_qsize = _ls_insize; \␊ |
186 | while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊ |
187 | if (_ls_psize == 0) { \␊ |
188 | _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊ |
189 | } else if (_ls_qsize == 0 || !_ls_q) { \␊ |
190 | _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊ |
191 | } else if (cmp(_ls_p,_ls_q) <= 0) { \␊ |
192 | _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊ |
193 | } else { \␊ |
194 | _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊ |
195 | } \␊ |
196 | if (_ls_tail) { \␊ |
197 | _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \␊ |
198 | } else { \␊ |
199 | _CASTASGN(list,_ls_e); \␊ |
200 | } \␊ |
201 | _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \␊ |
202 | _ls_tail = _ls_e; \␊ |
203 | } \␊ |
204 | _ls_p = _ls_q; \␊ |
205 | } \␊ |
206 | _CASTASGN(list->prev, _ls_tail); \␊ |
207 | _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \␊ |
208 | if (_ls_nmerges <= 1) { \␊ |
209 | _ls_looping=0; \␊ |
210 | } \␊ |
211 | _ls_insize *= 2; \␊ |
212 | } \␊ |
213 | } else _tmp=NULL; /* quiet gcc unused variable warning */ \␊ |
214 | } while (0)␊ |
215 | ␊ |
216 | #define CDL_SORT(list, cmp) \␊ |
217 | do { \␊ |
218 | LDECLTYPE(list) _ls_p; \␊ |
219 | LDECLTYPE(list) _ls_q; \␊ |
220 | LDECLTYPE(list) _ls_e; \␊ |
221 | LDECLTYPE(list) _ls_tail; \␊ |
222 | LDECLTYPE(list) _ls_oldhead; \␊ |
223 | LDECLTYPE(list) _tmp; \␊ |
224 | LDECLTYPE(list) _tmp2; \␊ |
225 | int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \␊ |
226 | if (list) { \␊ |
227 | _ls_insize = 1; \␊ |
228 | _ls_looping = 1; \␊ |
229 | while (_ls_looping) { \␊ |
230 | _CASTASGN(_ls_p,list); \␊ |
231 | _CASTASGN(_ls_oldhead,list); \␊ |
232 | list = NULL; \␊ |
233 | _ls_tail = NULL; \␊ |
234 | _ls_nmerges = 0; \␊ |
235 | while (_ls_p) { \␊ |
236 | _ls_nmerges++; \␊ |
237 | _ls_q = _ls_p; \␊ |
238 | _ls_psize = 0; \␊ |
239 | for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \␊ |
240 | _ls_psize++; \␊ |
241 | _SV(_ls_q,list); \␊ |
242 | if (_NEXT(_ls_q,list) == _ls_oldhead) { \␊ |
243 | _ls_q = NULL; \␊ |
244 | } else { \␊ |
245 | _ls_q = _NEXT(_ls_q,list); \␊ |
246 | } \␊ |
247 | _RS(list); \␊ |
248 | if (!_ls_q) break; \␊ |
249 | } \␊ |
250 | _ls_qsize = _ls_insize; \␊ |
251 | while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \␊ |
252 | if (_ls_psize == 0) { \␊ |
253 | _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊ |
254 | if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \␊ |
255 | } else if (_ls_qsize == 0 || !_ls_q) { \␊ |
256 | _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊ |
257 | if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \␊ |
258 | } else if (cmp(_ls_p,_ls_q) <= 0) { \␊ |
259 | _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \␊ |
260 | if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \␊ |
261 | } else { \␊ |
262 | _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \␊ |
263 | if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \␊ |
264 | } \␊ |
265 | if (_ls_tail) { \␊ |
266 | _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \␊ |
267 | } else { \␊ |
268 | _CASTASGN(list,_ls_e); \␊ |
269 | } \␊ |
270 | _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \␊ |
271 | _ls_tail = _ls_e; \␊ |
272 | } \␊ |
273 | _ls_p = _ls_q; \␊ |
274 | } \␊ |
275 | _CASTASGN(list->prev,_ls_tail); \␊ |
276 | _CASTASGN(_tmp2,list); \␊ |
277 | _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \␊ |
278 | if (_ls_nmerges <= 1) { \␊ |
279 | _ls_looping=0; \␊ |
280 | } \␊ |
281 | _ls_insize *= 2; \␊ |
282 | } \␊ |
283 | } else _tmp=NULL; /* quiet gcc unused variable warning */ \␊ |
284 | } while (0)␊ |
285 | ␊ |
286 | /******************************************************************************␊ |
287 | * singly linked list macros (non-circular) *␊ |
288 | *****************************************************************************/␊ |
289 | #define LL_PREPEND(head,add) \␊ |
290 | do { \␊ |
291 | (add)->next = head; \␊ |
292 | head = add; \␊ |
293 | } while (0)␊ |
294 | ␊ |
295 | #define LL_CONCAT(head1,head2) \␊ |
296 | do { \␊ |
297 | LDECLTYPE(head1) _tmp; \␊ |
298 | if (head1) { \␊ |
299 | _tmp = head1; \␊ |
300 | while (_tmp->next) { _tmp = _tmp->next; } \␊ |
301 | _tmp->next=(head2); \␊ |
302 | } else { \␊ |
303 | (head1)=(head2); \␊ |
304 | } \␊ |
305 | } while (0)␊ |
306 | ␊ |
307 | #define LL_APPEND(head,add) \␊ |
308 | do { \␊ |
309 | LDECLTYPE(head) _tmp; \␊ |
310 | (add)->next=NULL; \␊ |
311 | if (head) { \␊ |
312 | _tmp = head; \␊ |
313 | while (_tmp->next) { _tmp = _tmp->next; } \␊ |
314 | _tmp->next=(add); \␊ |
315 | } else { \␊ |
316 | (head)=(add); \␊ |
317 | } \␊ |
318 | } while (0)␊ |
319 | ␊ |
320 | #define LL_DELETE(head,del) \␊ |
321 | do { \␊ |
322 | LDECLTYPE(head) _tmp; \␊ |
323 | if ((head) == (del)) { \␊ |
324 | (head)=(head)->next; \␊ |
325 | } else { \␊ |
326 | _tmp = head; \␊ |
327 | while (_tmp->next && (_tmp->next != (del))) { \␊ |
328 | _tmp = _tmp->next; \␊ |
329 | } \␊ |
330 | if (_tmp->next) { \␊ |
331 | _tmp->next = ((del)->next); \␊ |
332 | } \␊ |
333 | } \␊ |
334 | } while (0)␊ |
335 | ␊ |
336 | /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */␊ |
337 | #define LL_APPEND_VS2008(head,add) \␊ |
338 | do { \␊ |
339 | if (head) { \␊ |
340 | (add)->next = head; /* use add->next as a temp variable */ \␊ |
341 | while ((add)->next->next) { (add)->next = (add)->next->next; } \␊ |
342 | (add)->next->next=(add); \␊ |
343 | } else { \␊ |
344 | (head)=(add); \␊ |
345 | } \␊ |
346 | (add)->next=NULL; \␊ |
347 | } while (0)␊ |
348 | ␊ |
349 | #define LL_DELETE_VS2008(head,del) \␊ |
350 | do { \␊ |
351 | if ((head) == (del)) { \␊ |
352 | (head)=(head)->next; \␊ |
353 | } else { \␊ |
354 | char *_tmp = (char*)(head); \␊ |
355 | while ((head)->next && ((head)->next != (del))) { \␊ |
356 | head = (head)->next; \␊ |
357 | } \␊ |
358 | if ((head)->next) { \␊ |
359 | (head)->next = ((del)->next); \␊ |
360 | } \␊ |
361 | { \␊ |
362 | char **_head_alias = (char**)&(head); \␊ |
363 | *_head_alias = _tmp; \␊ |
364 | } \␊ |
365 | } \␊ |
366 | } while (0)␊ |
367 | #ifdef NO_DECLTYPE␊ |
368 | #undef LL_APPEND␊ |
369 | #define LL_APPEND LL_APPEND_VS2008␊ |
370 | #undef LL_DELETE␊ |
371 | #define LL_DELETE LL_DELETE_VS2008␊ |
372 | #undef LL_CONCAT /* no LL_CONCAT_VS2008 */␊ |
373 | #undef DL_CONCAT /* no DL_CONCAT_VS2008 */␊ |
374 | #endif␊ |
375 | /* end VS2008 replacements */␊ |
376 | ␊ |
377 | #define LL_FOREACH(head,el) \␊ |
378 | for(el=head;el;el=(el)->next)␊ |
379 | ␊ |
380 | #define LL_FOREACH_SAFE(head,el,tmp) \␊ |
381 | for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)␊ |
382 | ␊ |
383 | #define LL_SEARCH_SCALAR(head,out,field,val) \␊ |
384 | do { \␊ |
385 | LL_FOREACH(head,out) { \␊ |
386 | if ((out)->field == (val)) break; \␊ |
387 | } \␊ |
388 | } while(0) ␊ |
389 | ␊ |
390 | #define LL_SEARCH(head,out,elt,cmp) \␊ |
391 | do { \␊ |
392 | LL_FOREACH(head,out) { \␊ |
393 | if ((cmp(out,elt))==0) break; \␊ |
394 | } \␊ |
395 | } while(0) ␊ |
396 | ␊ |
397 | /******************************************************************************␊ |
398 | * doubly linked list macros (non-circular) *␊ |
399 | *****************************************************************************/␊ |
400 | #define DL_PREPEND(head,add) \␊ |
401 | do { \␊ |
402 | (add)->next = head; \␊ |
403 | if (head) { \␊ |
404 | (add)->prev = (head)->prev; \␊ |
405 | (head)->prev = (add); \␊ |
406 | } else { \␊ |
407 | (add)->prev = (add); \␊ |
408 | } \␊ |
409 | (head) = (add); \␊ |
410 | } while (0)␊ |
411 | ␊ |
412 | #define DL_APPEND(head,add) \␊ |
413 | do { \␊ |
414 | if (head) { \␊ |
415 | (add)->prev = (head)->prev; \␊ |
416 | (head)->prev->next = (add); \␊ |
417 | (head)->prev = (add); \␊ |
418 | (add)->next = NULL; \␊ |
419 | } else { \␊ |
420 | (head)=(add); \␊ |
421 | (head)->prev = (head); \␊ |
422 | (head)->next = NULL; \␊ |
423 | } \␊ |
424 | } while (0) ␊ |
425 | ␊ |
426 | #define DL_CONCAT(head1,head2) \␊ |
427 | do { \␊ |
428 | LDECLTYPE(head1) _tmp; \␊ |
429 | if (head2) { \␊ |
430 | if (head1) { \␊ |
431 | _tmp = (head2)->prev; \␊ |
432 | (head2)->prev = (head1)->prev; \␊ |
433 | (head1)->prev->next = (head2); \␊ |
434 | (head1)->prev = _tmp; \␊ |
435 | } else { \␊ |
436 | (head1)=(head2); \␊ |
437 | } \␊ |
438 | } \␊ |
439 | } while (0) ␊ |
440 | ␊ |
441 | #define DL_DELETE(head,del) \␊ |
442 | do { \␊ |
443 | assert((del)->prev != NULL); \␊ |
444 | if ((del)->prev == (del)) { \␊ |
445 | (head)=NULL; \␊ |
446 | } else if ((del)==(head)) { \␊ |
447 | (del)->next->prev = (del)->prev; \␊ |
448 | (head) = (del)->next; \␊ |
449 | } else { \␊ |
450 | (del)->prev->next = (del)->next; \␊ |
451 | if ((del)->next) { \␊ |
452 | (del)->next->prev = (del)->prev; \␊ |
453 | } else { \␊ |
454 | (head)->prev = (del)->prev; \␊ |
455 | } \␊ |
456 | } \␊ |
457 | } while (0) ␊ |
458 | ␊ |
459 | ␊ |
460 | #define DL_FOREACH(head,el) \␊ |
461 | for(el=head;el;el=(el)->next)␊ |
462 | ␊ |
463 | /* this version is safe for deleting the elements during iteration */␊ |
464 | #define DL_FOREACH_SAFE(head,el,tmp) \␊ |
465 | for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)␊ |
466 | ␊ |
467 | /* these are identical to their singly-linked list counterparts */␊ |
468 | #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR␊ |
469 | #define DL_SEARCH LL_SEARCH␊ |
470 | ␊ |
471 | /******************************************************************************␊ |
472 | * circular doubly linked list macros *␊ |
473 | *****************************************************************************/␊ |
474 | #define CDL_PREPEND(head,add) \␊ |
475 | do { \␊ |
476 | if (head) { \␊ |
477 | (add)->prev = (head)->prev; \␊ |
478 | (add)->next = (head); \␊ |
479 | (head)->prev = (add); \␊ |
480 | (add)->prev->next = (add); \␊ |
481 | } else { \␊ |
482 | (add)->prev = (add); \␊ |
483 | (add)->next = (add); \␊ |
484 | } \␊ |
485 | (head)=(add); \␊ |
486 | } while (0)␊ |
487 | ␊ |
488 | #define CDL_DELETE(head,del) \␊ |
489 | do { \␊ |
490 | if ( ((head)==(del)) && ((head)->next == (head))) { \␊ |
491 | (head) = 0L; \␊ |
492 | } else { \␊ |
493 | (del)->next->prev = (del)->prev; \␊ |
494 | (del)->prev->next = (del)->next; \␊ |
495 | if ((del) == (head)) (head)=(del)->next; \␊ |
496 | } \␊ |
497 | } while (0) ␊ |
498 | ␊ |
499 | #define CDL_FOREACH(head,el) \␊ |
500 | for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) ␊ |
501 | ␊ |
502 | #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \␊ |
503 | for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \␊ |
504 | (el) && ((tmp2)=(el)->next, 1); \␊ |
505 | ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))␊ |
506 | ␊ |
507 | #define CDL_SEARCH_SCALAR(head,out,field,val) \␊ |
508 | do { \␊ |
509 | CDL_FOREACH(head,out) { \␊ |
510 | if ((out)->field == (val)) break; \␊ |
511 | } \␊ |
512 | } while(0) ␊ |
513 | ␊ |
514 | #define CDL_SEARCH(head,out,elt,cmp) \␊ |
515 | do { \␊ |
516 | CDL_FOREACH(head,out) { \␊ |
517 | if ((cmp(out,elt))==0) break; \␊ |
518 | } \␊ |
519 | } while(0) ␊ |
520 | ␊ |
521 | #endif /* UTLIST_H */␊ |
522 | ␊ |
523 | |