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) \␊ |
103 | LL_SORT2(list, cmp, next)␊ |
104 | ␊ |
105 | #define LL_SORT2(list, cmp, next) \␊ |
106 | do { \␊ |
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) \␊ |
170 | do { \␊ |
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) \␊ |
235 | do { \␊ |
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) \␊ |
315 | do { \␊ |
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) \␊ |
324 | do { \␊ |
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) \␊ |
339 | do { \␊ |
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) \␊ |
355 | do { \␊ |
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) \␊ |
375 | do { \␊ |
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) \␊ |
390 | do { \␊ |
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) \␊ |
437 | do { \␊ |
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) \␊ |
447 | do { \␊ |
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) \␊ |
454 | do { \␊ |
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) \␊ |
474 | do { \␊ |
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) \␊ |
501 | do { \␊ |
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) \␊ |
516 | do { \␊ |
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) \␊ |
533 | do { \␊ |
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) \␊ |
551 | do { \␊ |
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) \␊ |
589 | do { \␊ |
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) \␊ |
615 | do { \␊ |
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) \␊ |
637 | do { \␊ |
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) \␊ |
654 | do { \␊ |
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) \␊ |
682 | do { \␊ |
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) \␊ |
692 | do { \␊ |
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) \␊ |
699 | do { \␊ |
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) \␊ |
719 | do { \␊ |
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 | |