19
|
1 /* |
|
2 Copyright (c) 2007-2021, Troy D. Hanson http://troydhanson.github.com/uthash/ |
|
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 2.3.0 |
|
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++ source) this code uses whatever method is needed |
|
65 or, for VS2008 where neither is available, uses casting workarounds. */ |
|
66 #if !defined(LDECLTYPE) && !defined(NO_DECLTYPE) |
|
67 #if defined(_MSC_VER) /* MS compiler */ |
|
68 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ |
|
69 #define LDECLTYPE(x) decltype(x) |
|
70 #else /* VS2008 or older (or VS2010 in C mode) */ |
|
71 #define NO_DECLTYPE |
|
72 #endif |
|
73 #elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) |
|
74 #define NO_DECLTYPE |
|
75 #else /* GNU, Sun and other compilers */ |
|
76 #define LDECLTYPE(x) __typeof(x) |
|
77 #endif |
|
78 #endif |
|
79 |
|
80 /* for VS2008 we use some workarounds to get around the lack of decltype, |
|
81 * namely, we always reassign our tmp variable to the list head if we need |
|
82 * to dereference its prev/next pointers, and save/restore the real head.*/ |
|
83 #ifdef NO_DECLTYPE |
|
84 #define IF_NO_DECLTYPE(x) x |
|
85 #define LDECLTYPE(x) char* |
|
86 #define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } |
|
87 #define UTLIST_NEXT(elt,list,next) ((char*)((list)->next)) |
|
88 #define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } |
|
89 /* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */ |
|
90 #define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } |
|
91 #define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } |
|
92 #define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } |
|
93 #else |
|
94 #define IF_NO_DECLTYPE(x) |
|
95 #define UTLIST_SV(elt,list) |
|
96 #define UTLIST_NEXT(elt,list,next) ((elt)->next) |
|
97 #define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to) |
|
98 /* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */ |
|
99 #define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) |
|
100 #define UTLIST_RS(list) |
|
101 #define UTLIST_CASTASGN(a,b) (a)=(b) |
|
102 #endif |
|
103 |
|
104 /****************************************************************************** |
|
105 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * |
|
106 * Unwieldy variable names used here to avoid shadowing passed-in variables. * |
|
107 *****************************************************************************/ |
|
108 #define LL_SORT(list, cmp) \ |
|
109 LL_SORT2(list, cmp, next) |
|
110 |
|
111 #define LL_SORT2(list, cmp, next) \ |
|
112 do { \ |
|
113 LDECLTYPE(list) _ls_p; \ |
|
114 LDECLTYPE(list) _ls_q; \ |
|
115 LDECLTYPE(list) _ls_e; \ |
|
116 LDECLTYPE(list) _ls_tail; \ |
|
117 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ |
|
118 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ |
|
119 if (list) { \ |
|
120 _ls_insize = 1; \ |
|
121 _ls_looping = 1; \ |
|
122 while (_ls_looping) { \ |
|
123 UTLIST_CASTASGN(_ls_p,list); \ |
|
124 (list) = NULL; \ |
|
125 _ls_tail = NULL; \ |
|
126 _ls_nmerges = 0; \ |
|
127 while (_ls_p) { \ |
|
128 _ls_nmerges++; \ |
|
129 _ls_q = _ls_p; \ |
|
130 _ls_psize = 0; \ |
|
131 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ |
|
132 _ls_psize++; \ |
|
133 UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ |
|
134 if (!_ls_q) break; \ |
|
135 } \ |
|
136 _ls_qsize = _ls_insize; \ |
|
137 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ |
|
138 if (_ls_psize == 0) { \ |
|
139 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ |
|
140 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ |
|
141 } else if (_ls_qsize == 0 || !_ls_q) { \ |
|
142 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ |
|
143 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ |
|
144 } else if (cmp(_ls_p,_ls_q) <= 0) { \ |
|
145 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ |
|
146 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ |
|
147 } else { \ |
|
148 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ |
|
149 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ |
|
150 } \ |
|
151 if (_ls_tail) { \ |
|
152 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ |
|
153 } else { \ |
|
154 UTLIST_CASTASGN(list,_ls_e); \ |
|
155 } \ |
|
156 _ls_tail = _ls_e; \ |
|
157 } \ |
|
158 _ls_p = _ls_q; \ |
|
159 } \ |
|
160 if (_ls_tail) { \ |
|
161 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ |
|
162 } \ |
|
163 if (_ls_nmerges <= 1) { \ |
|
164 _ls_looping=0; \ |
|
165 } \ |
|
166 _ls_insize *= 2; \ |
|
167 } \ |
|
168 } \ |
|
169 } while (0) |
|
170 |
|
171 |
|
172 #define DL_SORT(list, cmp) \ |
|
173 DL_SORT2(list, cmp, prev, next) |
|
174 |
|
175 #define DL_SORT2(list, cmp, prev, next) \ |
|
176 do { \ |
|
177 LDECLTYPE(list) _ls_p; \ |
|
178 LDECLTYPE(list) _ls_q; \ |
|
179 LDECLTYPE(list) _ls_e; \ |
|
180 LDECLTYPE(list) _ls_tail; \ |
|
181 IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ |
|
182 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ |
|
183 if (list) { \ |
|
184 _ls_insize = 1; \ |
|
185 _ls_looping = 1; \ |
|
186 while (_ls_looping) { \ |
|
187 UTLIST_CASTASGN(_ls_p,list); \ |
|
188 (list) = NULL; \ |
|
189 _ls_tail = NULL; \ |
|
190 _ls_nmerges = 0; \ |
|
191 while (_ls_p) { \ |
|
192 _ls_nmerges++; \ |
|
193 _ls_q = _ls_p; \ |
|
194 _ls_psize = 0; \ |
|
195 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ |
|
196 _ls_psize++; \ |
|
197 UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ |
|
198 if (!_ls_q) break; \ |
|
199 } \ |
|
200 _ls_qsize = _ls_insize; \ |
|
201 while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \ |
|
202 if (_ls_psize == 0) { \ |
|
203 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ |
|
204 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ |
|
205 } else if ((_ls_qsize == 0) || (!_ls_q)) { \ |
|
206 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ |
|
207 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ |
|
208 } else if (cmp(_ls_p,_ls_q) <= 0) { \ |
|
209 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ |
|
210 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ |
|
211 } else { \ |
|
212 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ |
|
213 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ |
|
214 } \ |
|
215 if (_ls_tail) { \ |
|
216 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ |
|
217 } else { \ |
|
218 UTLIST_CASTASGN(list,_ls_e); \ |
|
219 } \ |
|
220 UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ |
|
221 _ls_tail = _ls_e; \ |
|
222 } \ |
|
223 _ls_p = _ls_q; \ |
|
224 } \ |
|
225 UTLIST_CASTASGN((list)->prev, _ls_tail); \ |
|
226 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ |
|
227 if (_ls_nmerges <= 1) { \ |
|
228 _ls_looping=0; \ |
|
229 } \ |
|
230 _ls_insize *= 2; \ |
|
231 } \ |
|
232 } \ |
|
233 } while (0) |
|
234 |
|
235 #define CDL_SORT(list, cmp) \ |
|
236 CDL_SORT2(list, cmp, prev, next) |
|
237 |
|
238 #define CDL_SORT2(list, cmp, prev, next) \ |
|
239 do { \ |
|
240 LDECLTYPE(list) _ls_p; \ |
|
241 LDECLTYPE(list) _ls_q; \ |
|
242 LDECLTYPE(list) _ls_e; \ |
|
243 LDECLTYPE(list) _ls_tail; \ |
|
244 LDECLTYPE(list) _ls_oldhead; \ |
|
245 LDECLTYPE(list) _tmp; \ |
|
246 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ |
|
247 if (list) { \ |
|
248 _ls_insize = 1; \ |
|
249 _ls_looping = 1; \ |
|
250 while (_ls_looping) { \ |
|
251 UTLIST_CASTASGN(_ls_p,list); \ |
|
252 UTLIST_CASTASGN(_ls_oldhead,list); \ |
|
253 (list) = NULL; \ |
|
254 _ls_tail = NULL; \ |
|
255 _ls_nmerges = 0; \ |
|
256 while (_ls_p) { \ |
|
257 _ls_nmerges++; \ |
|
258 _ls_q = _ls_p; \ |
|
259 _ls_psize = 0; \ |
|
260 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ |
|
261 _ls_psize++; \ |
|
262 UTLIST_SV(_ls_q,list); \ |
|
263 if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) { \ |
|
264 _ls_q = NULL; \ |
|
265 } else { \ |
|
266 _ls_q = UTLIST_NEXT(_ls_q,list,next); \ |
|
267 } \ |
|
268 UTLIST_RS(list); \ |
|
269 if (!_ls_q) break; \ |
|
270 } \ |
|
271 _ls_qsize = _ls_insize; \ |
|
272 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ |
|
273 if (_ls_psize == 0) { \ |
|
274 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ |
|
275 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ |
|
276 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ |
|
277 } else if (_ls_qsize == 0 || !_ls_q) { \ |
|
278 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ |
|
279 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ |
|
280 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ |
|
281 } else if (cmp(_ls_p,_ls_q) <= 0) { \ |
|
282 _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ |
|
283 UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ |
|
284 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ |
|
285 } else { \ |
|
286 _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ |
|
287 UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ |
|
288 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ |
|
289 } \ |
|
290 if (_ls_tail) { \ |
|
291 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ |
|
292 } else { \ |
|
293 UTLIST_CASTASGN(list,_ls_e); \ |
|
294 } \ |
|
295 UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ |
|
296 _ls_tail = _ls_e; \ |
|
297 } \ |
|
298 _ls_p = _ls_q; \ |
|
299 } \ |
|
300 UTLIST_CASTASGN((list)->prev,_ls_tail); \ |
|
301 UTLIST_CASTASGN(_tmp,list); \ |
|
302 UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list); \ |
|
303 if (_ls_nmerges <= 1) { \ |
|
304 _ls_looping=0; \ |
|
305 } \ |
|
306 _ls_insize *= 2; \ |
|
307 } \ |
|
308 } \ |
|
309 } while (0) |
|
310 |
|
311 /****************************************************************************** |
|
312 * singly linked list macros (non-circular) * |
|
313 *****************************************************************************/ |
|
314 #define LL_PREPEND(head,add) \ |
|
315 LL_PREPEND2(head,add,next) |
|
316 |
|
317 #define LL_PREPEND2(head,add,next) \ |
|
318 do { \ |
|
319 (add)->next = (head); \ |
|
320 (head) = (add); \ |
|
321 } while (0) |
|
322 |
|
323 #define LL_CONCAT(head1,head2) \ |
|
324 LL_CONCAT2(head1,head2,next) |
|
325 |
|
326 #define LL_CONCAT2(head1,head2,next) \ |
|
327 do { \ |
|
328 LDECLTYPE(head1) _tmp; \ |
|
329 if (head1) { \ |
|
330 _tmp = (head1); \ |
|
331 while (_tmp->next) { _tmp = _tmp->next; } \ |
|
332 _tmp->next=(head2); \ |
|
333 } else { \ |
|
334 (head1)=(head2); \ |
|
335 } \ |
|
336 } while (0) |
|
337 |
|
338 #define LL_APPEND(head,add) \ |
|
339 LL_APPEND2(head,add,next) |
|
340 |
|
341 #define LL_APPEND2(head,add,next) \ |
|
342 do { \ |
|
343 LDECLTYPE(head) _tmp; \ |
|
344 (add)->next=NULL; \ |
|
345 if (head) { \ |
|
346 _tmp = (head); \ |
|
347 while (_tmp->next) { _tmp = _tmp->next; } \ |
|
348 _tmp->next=(add); \ |
|
349 } else { \ |
|
350 (head)=(add); \ |
|
351 } \ |
|
352 } while (0) |
|
353 |
|
354 #define LL_INSERT_INORDER(head,add,cmp) \ |
|
355 LL_INSERT_INORDER2(head,add,cmp,next) |
|
356 |
|
357 #define LL_INSERT_INORDER2(head,add,cmp,next) \ |
|
358 do { \ |
|
359 LDECLTYPE(head) _tmp; \ |
|
360 if (head) { \ |
|
361 LL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ |
|
362 LL_APPEND_ELEM2(head, _tmp, add, next); \ |
|
363 } else { \ |
|
364 (head) = (add); \ |
|
365 (head)->next = NULL; \ |
|
366 } \ |
|
367 } while (0) |
|
368 |
|
369 #define LL_LOWER_BOUND(head,elt,like,cmp) \ |
|
370 LL_LOWER_BOUND2(head,elt,like,cmp,next) |
|
371 |
|
372 #define LL_LOWER_BOUND2(head,elt,like,cmp,next) \ |
|
373 do { \ |
|
374 if ((head) == NULL || (cmp(head, like)) >= 0) { \ |
|
375 (elt) = NULL; \ |
|
376 } else { \ |
|
377 for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ |
|
378 if (cmp((elt)->next, like) >= 0) { \ |
|
379 break; \ |
|
380 } \ |
|
381 } \ |
|
382 } \ |
|
383 } while (0) |
|
384 |
|
385 #define LL_DELETE(head,del) \ |
|
386 LL_DELETE2(head,del,next) |
|
387 |
|
388 #define LL_DELETE2(head,del,next) \ |
|
389 do { \ |
|
390 LDECLTYPE(head) _tmp; \ |
|
391 if ((head) == (del)) { \ |
|
392 (head)=(head)->next; \ |
|
393 } else { \ |
|
394 _tmp = (head); \ |
|
395 while (_tmp->next && (_tmp->next != (del))) { \ |
|
396 _tmp = _tmp->next; \ |
|
397 } \ |
|
398 if (_tmp->next) { \ |
|
399 _tmp->next = (del)->next; \ |
|
400 } \ |
|
401 } \ |
|
402 } while (0) |
|
403 |
|
404 #define LL_COUNT(head,el,counter) \ |
|
405 LL_COUNT2(head,el,counter,next) \ |
|
406 |
|
407 #define LL_COUNT2(head,el,counter,next) \ |
|
408 do { \ |
|
409 (counter) = 0; \ |
|
410 LL_FOREACH2(head,el,next) { ++(counter); } \ |
|
411 } while (0) |
|
412 |
|
413 #define LL_FOREACH(head,el) \ |
|
414 LL_FOREACH2(head,el,next) |
|
415 |
|
416 #define LL_FOREACH2(head,el,next) \ |
|
417 for ((el) = (head); el; (el) = (el)->next) |
|
418 |
|
419 #define LL_FOREACH_SAFE(head,el,tmp) \ |
|
420 LL_FOREACH_SAFE2(head,el,tmp,next) |
|
421 |
|
422 #define LL_FOREACH_SAFE2(head,el,tmp,next) \ |
|
423 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) |
|
424 |
|
425 #define LL_SEARCH_SCALAR(head,out,field,val) \ |
|
426 LL_SEARCH_SCALAR2(head,out,field,val,next) |
|
427 |
|
428 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \ |
|
429 do { \ |
|
430 LL_FOREACH2(head,out,next) { \ |
|
431 if ((out)->field == (val)) break; \ |
|
432 } \ |
|
433 } while (0) |
|
434 |
|
435 #define LL_SEARCH(head,out,elt,cmp) \ |
|
436 LL_SEARCH2(head,out,elt,cmp,next) |
|
437 |
|
438 #define LL_SEARCH2(head,out,elt,cmp,next) \ |
|
439 do { \ |
|
440 LL_FOREACH2(head,out,next) { \ |
|
441 if ((cmp(out,elt))==0) break; \ |
|
442 } \ |
|
443 } while (0) |
|
444 |
|
445 #define LL_REPLACE_ELEM2(head, el, add, next) \ |
|
446 do { \ |
|
447 LDECLTYPE(head) _tmp; \ |
|
448 assert((head) != NULL); \ |
|
449 assert((el) != NULL); \ |
|
450 assert((add) != NULL); \ |
|
451 (add)->next = (el)->next; \ |
|
452 if ((head) == (el)) { \ |
|
453 (head) = (add); \ |
|
454 } else { \ |
|
455 _tmp = (head); \ |
|
456 while (_tmp->next && (_tmp->next != (el))) { \ |
|
457 _tmp = _tmp->next; \ |
|
458 } \ |
|
459 if (_tmp->next) { \ |
|
460 _tmp->next = (add); \ |
|
461 } \ |
|
462 } \ |
|
463 } while (0) |
|
464 |
|
465 #define LL_REPLACE_ELEM(head, el, add) \ |
|
466 LL_REPLACE_ELEM2(head, el, add, next) |
|
467 |
|
468 #define LL_PREPEND_ELEM2(head, el, add, next) \ |
|
469 do { \ |
|
470 if (el) { \ |
|
471 LDECLTYPE(head) _tmp; \ |
|
472 assert((head) != NULL); \ |
|
473 assert((add) != NULL); \ |
|
474 (add)->next = (el); \ |
|
475 if ((head) == (el)) { \ |
|
476 (head) = (add); \ |
|
477 } else { \ |
|
478 _tmp = (head); \ |
|
479 while (_tmp->next && (_tmp->next != (el))) { \ |
|
480 _tmp = _tmp->next; \ |
|
481 } \ |
|
482 if (_tmp->next) { \ |
|
483 _tmp->next = (add); \ |
|
484 } \ |
|
485 } \ |
|
486 } else { \ |
|
487 LL_APPEND2(head, add, next); \ |
|
488 } \ |
|
489 } while (0) \ |
|
490 |
|
491 #define LL_PREPEND_ELEM(head, el, add) \ |
|
492 LL_PREPEND_ELEM2(head, el, add, next) |
|
493 |
|
494 #define LL_APPEND_ELEM2(head, el, add, next) \ |
|
495 do { \ |
|
496 if (el) { \ |
|
497 assert((head) != NULL); \ |
|
498 assert((add) != NULL); \ |
|
499 (add)->next = (el)->next; \ |
|
500 (el)->next = (add); \ |
|
501 } else { \ |
|
502 LL_PREPEND2(head, add, next); \ |
|
503 } \ |
|
504 } while (0) \ |
|
505 |
|
506 #define LL_APPEND_ELEM(head, el, add) \ |
|
507 LL_APPEND_ELEM2(head, el, add, next) |
|
508 |
|
509 #ifdef NO_DECLTYPE |
|
510 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ |
|
511 |
|
512 #undef LL_CONCAT2 |
|
513 #define LL_CONCAT2(head1,head2,next) \ |
|
514 do { \ |
|
515 char *_tmp; \ |
|
516 if (head1) { \ |
|
517 _tmp = (char*)(head1); \ |
|
518 while ((head1)->next) { (head1) = (head1)->next; } \ |
|
519 (head1)->next = (head2); \ |
|
520 UTLIST_RS(head1); \ |
|
521 } else { \ |
|
522 (head1)=(head2); \ |
|
523 } \ |
|
524 } while (0) |
|
525 |
|
526 #undef LL_APPEND2 |
|
527 #define LL_APPEND2(head,add,next) \ |
|
528 do { \ |
|
529 if (head) { \ |
|
530 (add)->next = head; /* use add->next as a temp variable */ \ |
|
531 while ((add)->next->next) { (add)->next = (add)->next->next; } \ |
|
532 (add)->next->next=(add); \ |
|
533 } else { \ |
|
534 (head)=(add); \ |
|
535 } \ |
|
536 (add)->next=NULL; \ |
|
537 } while (0) |
|
538 |
|
539 #undef LL_INSERT_INORDER2 |
|
540 #define LL_INSERT_INORDER2(head,add,cmp,next) \ |
|
541 do { \ |
|
542 if ((head) == NULL || (cmp(head, add)) >= 0) { \ |
|
543 (add)->next = (head); \ |
|
544 (head) = (add); \ |
|
545 } else { \ |
|
546 char *_tmp = (char*)(head); \ |
|
547 while ((head)->next != NULL && (cmp((head)->next, add)) < 0) { \ |
|
548 (head) = (head)->next; \ |
|
549 } \ |
|
550 (add)->next = (head)->next; \ |
|
551 (head)->next = (add); \ |
|
552 UTLIST_RS(head); \ |
|
553 } \ |
|
554 } while (0) |
|
555 |
|
556 #undef LL_DELETE2 |
|
557 #define LL_DELETE2(head,del,next) \ |
|
558 do { \ |
|
559 if ((head) == (del)) { \ |
|
560 (head)=(head)->next; \ |
|
561 } else { \ |
|
562 char *_tmp = (char*)(head); \ |
|
563 while ((head)->next && ((head)->next != (del))) { \ |
|
564 (head) = (head)->next; \ |
|
565 } \ |
|
566 if ((head)->next) { \ |
|
567 (head)->next = ((del)->next); \ |
|
568 } \ |
|
569 UTLIST_RS(head); \ |
|
570 } \ |
|
571 } while (0) |
|
572 |
|
573 #undef LL_REPLACE_ELEM2 |
|
574 #define LL_REPLACE_ELEM2(head, el, add, next) \ |
|
575 do { \ |
|
576 assert((head) != NULL); \ |
|
577 assert((el) != NULL); \ |
|
578 assert((add) != NULL); \ |
|
579 if ((head) == (el)) { \ |
|
580 (head) = (add); \ |
|
581 } else { \ |
|
582 (add)->next = head; \ |
|
583 while ((add)->next->next && ((add)->next->next != (el))) { \ |
|
584 (add)->next = (add)->next->next; \ |
|
585 } \ |
|
586 if ((add)->next->next) { \ |
|
587 (add)->next->next = (add); \ |
|
588 } \ |
|
589 } \ |
|
590 (add)->next = (el)->next; \ |
|
591 } while (0) |
|
592 |
|
593 #undef LL_PREPEND_ELEM2 |
|
594 #define LL_PREPEND_ELEM2(head, el, add, next) \ |
|
595 do { \ |
|
596 if (el) { \ |
|
597 assert((head) != NULL); \ |
|
598 assert((add) != NULL); \ |
|
599 if ((head) == (el)) { \ |
|
600 (head) = (add); \ |
|
601 } else { \ |
|
602 (add)->next = (head); \ |
|
603 while ((add)->next->next && ((add)->next->next != (el))) { \ |
|
604 (add)->next = (add)->next->next; \ |
|
605 } \ |
|
606 if ((add)->next->next) { \ |
|
607 (add)->next->next = (add); \ |
|
608 } \ |
|
609 } \ |
|
610 (add)->next = (el); \ |
|
611 } else { \ |
|
612 LL_APPEND2(head, add, next); \ |
|
613 } \ |
|
614 } while (0) \ |
|
615 |
|
616 #endif /* NO_DECLTYPE */ |
|
617 |
|
618 /****************************************************************************** |
|
619 * doubly linked list macros (non-circular) * |
|
620 *****************************************************************************/ |
|
621 #define DL_PREPEND(head,add) \ |
|
622 DL_PREPEND2(head,add,prev,next) |
|
623 |
|
624 #define DL_PREPEND2(head,add,prev,next) \ |
|
625 do { \ |
|
626 (add)->next = (head); \ |
|
627 if (head) { \ |
|
628 (add)->prev = (head)->prev; \ |
|
629 (head)->prev = (add); \ |
|
630 } else { \ |
|
631 (add)->prev = (add); \ |
|
632 } \ |
|
633 (head) = (add); \ |
|
634 } while (0) |
|
635 |
|
636 #define DL_APPEND(head,add) \ |
|
637 DL_APPEND2(head,add,prev,next) |
|
638 |
|
639 #define DL_APPEND2(head,add,prev,next) \ |
|
640 do { \ |
|
641 if (head) { \ |
|
642 (add)->prev = (head)->prev; \ |
|
643 (head)->prev->next = (add); \ |
|
644 (head)->prev = (add); \ |
|
645 (add)->next = NULL; \ |
|
646 } else { \ |
|
647 (head)=(add); \ |
|
648 (head)->prev = (head); \ |
|
649 (head)->next = NULL; \ |
|
650 } \ |
|
651 } while (0) |
|
652 |
|
653 #define DL_INSERT_INORDER(head,add,cmp) \ |
|
654 DL_INSERT_INORDER2(head,add,cmp,prev,next) |
|
655 |
|
656 #define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ |
|
657 do { \ |
|
658 LDECLTYPE(head) _tmp; \ |
|
659 if (head) { \ |
|
660 DL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ |
|
661 DL_APPEND_ELEM2(head, _tmp, add, prev, next); \ |
|
662 } else { \ |
|
663 (head) = (add); \ |
|
664 (head)->prev = (head); \ |
|
665 (head)->next = NULL; \ |
|
666 } \ |
|
667 } while (0) |
|
668 |
|
669 #define DL_LOWER_BOUND(head,elt,like,cmp) \ |
|
670 DL_LOWER_BOUND2(head,elt,like,cmp,next) |
|
671 |
|
672 #define DL_LOWER_BOUND2(head,elt,like,cmp,next) \ |
|
673 do { \ |
|
674 if ((head) == NULL || (cmp(head, like)) >= 0) { \ |
|
675 (elt) = NULL; \ |
|
676 } else { \ |
|
677 for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ |
|
678 if ((cmp((elt)->next, like)) >= 0) { \ |
|
679 break; \ |
|
680 } \ |
|
681 } \ |
|
682 } \ |
|
683 } while (0) |
|
684 |
|
685 #define DL_CONCAT(head1,head2) \ |
|
686 DL_CONCAT2(head1,head2,prev,next) |
|
687 |
|
688 #define DL_CONCAT2(head1,head2,prev,next) \ |
|
689 do { \ |
|
690 LDECLTYPE(head1) _tmp; \ |
|
691 if (head2) { \ |
|
692 if (head1) { \ |
|
693 UTLIST_CASTASGN(_tmp, (head2)->prev); \ |
|
694 (head2)->prev = (head1)->prev; \ |
|
695 (head1)->prev->next = (head2); \ |
|
696 UTLIST_CASTASGN((head1)->prev, _tmp); \ |
|
697 } else { \ |
|
698 (head1)=(head2); \ |
|
699 } \ |
|
700 } \ |
|
701 } while (0) |
|
702 |
|
703 #define DL_DELETE(head,del) \ |
|
704 DL_DELETE2(head,del,prev,next) |
|
705 |
|
706 #define DL_DELETE2(head,del,prev,next) \ |
|
707 do { \ |
|
708 assert((head) != NULL); \ |
|
709 assert((del)->prev != NULL); \ |
|
710 if ((del)->prev == (del)) { \ |
|
711 (head)=NULL; \ |
|
712 } else if ((del)==(head)) { \ |
|
713 (del)->next->prev = (del)->prev; \ |
|
714 (head) = (del)->next; \ |
|
715 } else { \ |
|
716 (del)->prev->next = (del)->next; \ |
|
717 if ((del)->next) { \ |
|
718 (del)->next->prev = (del)->prev; \ |
|
719 } else { \ |
|
720 (head)->prev = (del)->prev; \ |
|
721 } \ |
|
722 } \ |
|
723 } while (0) |
|
724 |
|
725 #define DL_COUNT(head,el,counter) \ |
|
726 DL_COUNT2(head,el,counter,next) \ |
|
727 |
|
728 #define DL_COUNT2(head,el,counter,next) \ |
|
729 do { \ |
|
730 (counter) = 0; \ |
|
731 DL_FOREACH2(head,el,next) { ++(counter); } \ |
|
732 } while (0) |
|
733 |
|
734 #define DL_FOREACH(head,el) \ |
|
735 DL_FOREACH2(head,el,next) |
|
736 |
|
737 #define DL_FOREACH2(head,el,next) \ |
|
738 for ((el) = (head); el; (el) = (el)->next) |
|
739 |
|
740 /* this version is safe for deleting the elements during iteration */ |
|
741 #define DL_FOREACH_SAFE(head,el,tmp) \ |
|
742 DL_FOREACH_SAFE2(head,el,tmp,next) |
|
743 |
|
744 #define DL_FOREACH_SAFE2(head,el,tmp,next) \ |
|
745 for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) |
|
746 |
|
747 /* these are identical to their singly-linked list counterparts */ |
|
748 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR |
|
749 #define DL_SEARCH LL_SEARCH |
|
750 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 |
|
751 #define DL_SEARCH2 LL_SEARCH2 |
|
752 |
|
753 #define DL_REPLACE_ELEM2(head, el, add, prev, next) \ |
|
754 do { \ |
|
755 assert((head) != NULL); \ |
|
756 assert((el) != NULL); \ |
|
757 assert((add) != NULL); \ |
|
758 if ((head) == (el)) { \ |
|
759 (head) = (add); \ |
|
760 (add)->next = (el)->next; \ |
|
761 if ((el)->next == NULL) { \ |
|
762 (add)->prev = (add); \ |
|
763 } else { \ |
|
764 (add)->prev = (el)->prev; \ |
|
765 (add)->next->prev = (add); \ |
|
766 } \ |
|
767 } else { \ |
|
768 (add)->next = (el)->next; \ |
|
769 (add)->prev = (el)->prev; \ |
|
770 (add)->prev->next = (add); \ |
|
771 if ((el)->next == NULL) { \ |
|
772 (head)->prev = (add); \ |
|
773 } else { \ |
|
774 (add)->next->prev = (add); \ |
|
775 } \ |
|
776 } \ |
|
777 } while (0) |
|
778 |
|
779 #define DL_REPLACE_ELEM(head, el, add) \ |
|
780 DL_REPLACE_ELEM2(head, el, add, prev, next) |
|
781 |
|
782 #define DL_PREPEND_ELEM2(head, el, add, prev, next) \ |
|
783 do { \ |
|
784 if (el) { \ |
|
785 assert((head) != NULL); \ |
|
786 assert((add) != NULL); \ |
|
787 (add)->next = (el); \ |
|
788 (add)->prev = (el)->prev; \ |
|
789 (el)->prev = (add); \ |
|
790 if ((head) == (el)) { \ |
|
791 (head) = (add); \ |
|
792 } else { \ |
|
793 (add)->prev->next = (add); \ |
|
794 } \ |
|
795 } else { \ |
|
796 DL_APPEND2(head, add, prev, next); \ |
|
797 } \ |
|
798 } while (0) \ |
|
799 |
|
800 #define DL_PREPEND_ELEM(head, el, add) \ |
|
801 DL_PREPEND_ELEM2(head, el, add, prev, next) |
|
802 |
|
803 #define DL_APPEND_ELEM2(head, el, add, prev, next) \ |
|
804 do { \ |
|
805 if (el) { \ |
|
806 assert((head) != NULL); \ |
|
807 assert((add) != NULL); \ |
|
808 (add)->next = (el)->next; \ |
|
809 (add)->prev = (el); \ |
|
810 (el)->next = (add); \ |
|
811 if ((add)->next) { \ |
|
812 (add)->next->prev = (add); \ |
|
813 } else { \ |
|
814 (head)->prev = (add); \ |
|
815 } \ |
|
816 } else { \ |
|
817 DL_PREPEND2(head, add, prev, next); \ |
|
818 } \ |
|
819 } while (0) \ |
|
820 |
|
821 #define DL_APPEND_ELEM(head, el, add) \ |
|
822 DL_APPEND_ELEM2(head, el, add, prev, next) |
|
823 |
|
824 #ifdef NO_DECLTYPE |
|
825 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ |
|
826 |
|
827 #undef DL_INSERT_INORDER2 |
|
828 #define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ |
|
829 do { \ |
|
830 if ((head) == NULL) { \ |
|
831 (add)->prev = (add); \ |
|
832 (add)->next = NULL; \ |
|
833 (head) = (add); \ |
|
834 } else if ((cmp(head, add)) >= 0) { \ |
|
835 (add)->prev = (head)->prev; \ |
|
836 (add)->next = (head); \ |
|
837 (head)->prev = (add); \ |
|
838 (head) = (add); \ |
|
839 } else { \ |
|
840 char *_tmp = (char*)(head); \ |
|
841 while ((head)->next && (cmp((head)->next, add)) < 0) { \ |
|
842 (head) = (head)->next; \ |
|
843 } \ |
|
844 (add)->prev = (head); \ |
|
845 (add)->next = (head)->next; \ |
|
846 (head)->next = (add); \ |
|
847 UTLIST_RS(head); \ |
|
848 if ((add)->next) { \ |
|
849 (add)->next->prev = (add); \ |
|
850 } else { \ |
|
851 (head)->prev = (add); \ |
|
852 } \ |
|
853 } \ |
|
854 } while (0) |
|
855 #endif /* NO_DECLTYPE */ |
|
856 |
|
857 /****************************************************************************** |
|
858 * circular doubly linked list macros * |
|
859 *****************************************************************************/ |
|
860 #define CDL_APPEND(head,add) \ |
|
861 CDL_APPEND2(head,add,prev,next) |
|
862 |
|
863 #define CDL_APPEND2(head,add,prev,next) \ |
|
864 do { \ |
|
865 if (head) { \ |
|
866 (add)->prev = (head)->prev; \ |
|
867 (add)->next = (head); \ |
|
868 (head)->prev = (add); \ |
|
869 (add)->prev->next = (add); \ |
|
870 } else { \ |
|
871 (add)->prev = (add); \ |
|
872 (add)->next = (add); \ |
|
873 (head) = (add); \ |
|
874 } \ |
|
875 } while (0) |
|
876 |
|
877 #define CDL_PREPEND(head,add) \ |
|
878 CDL_PREPEND2(head,add,prev,next) |
|
879 |
|
880 #define CDL_PREPEND2(head,add,prev,next) \ |
|
881 do { \ |
|
882 if (head) { \ |
|
883 (add)->prev = (head)->prev; \ |
|
884 (add)->next = (head); \ |
|
885 (head)->prev = (add); \ |
|
886 (add)->prev->next = (add); \ |
|
887 } else { \ |
|
888 (add)->prev = (add); \ |
|
889 (add)->next = (add); \ |
|
890 } \ |
|
891 (head) = (add); \ |
|
892 } while (0) |
|
893 |
|
894 #define CDL_INSERT_INORDER(head,add,cmp) \ |
|
895 CDL_INSERT_INORDER2(head,add,cmp,prev,next) |
|
896 |
|
897 #define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ |
|
898 do { \ |
|
899 LDECLTYPE(head) _tmp; \ |
|
900 if (head) { \ |
|
901 CDL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ |
|
902 CDL_APPEND_ELEM2(head, _tmp, add, prev, next); \ |
|
903 } else { \ |
|
904 (head) = (add); \ |
|
905 (head)->next = (head); \ |
|
906 (head)->prev = (head); \ |
|
907 } \ |
|
908 } while (0) |
|
909 |
|
910 #define CDL_LOWER_BOUND(head,elt,like,cmp) \ |
|
911 CDL_LOWER_BOUND2(head,elt,like,cmp,next) |
|
912 |
|
913 #define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \ |
|
914 do { \ |
|
915 if ((head) == NULL || (cmp(head, like)) >= 0) { \ |
|
916 (elt) = NULL; \ |
|
917 } else { \ |
|
918 for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \ |
|
919 if ((cmp((elt)->next, like)) >= 0) { \ |
|
920 break; \ |
|
921 } \ |
|
922 } \ |
|
923 } \ |
|
924 } while (0) |
|
925 |
|
926 #define CDL_DELETE(head,del) \ |
|
927 CDL_DELETE2(head,del,prev,next) |
|
928 |
|
929 #define CDL_DELETE2(head,del,prev,next) \ |
|
930 do { \ |
|
931 if (((head)==(del)) && ((head)->next == (head))) { \ |
|
932 (head) = NULL; \ |
|
933 } else { \ |
|
934 (del)->next->prev = (del)->prev; \ |
|
935 (del)->prev->next = (del)->next; \ |
|
936 if ((del) == (head)) (head)=(del)->next; \ |
|
937 } \ |
|
938 } while (0) |
|
939 |
|
940 #define CDL_COUNT(head,el,counter) \ |
|
941 CDL_COUNT2(head,el,counter,next) \ |
|
942 |
|
943 #define CDL_COUNT2(head, el, counter,next) \ |
|
944 do { \ |
|
945 (counter) = 0; \ |
|
946 CDL_FOREACH2(head,el,next) { ++(counter); } \ |
|
947 } while (0) |
|
948 |
|
949 #define CDL_FOREACH(head,el) \ |
|
950 CDL_FOREACH2(head,el,next) |
|
951 |
|
952 #define CDL_FOREACH2(head,el,next) \ |
|
953 for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) |
|
954 |
|
955 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ |
|
956 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) |
|
957 |
|
958 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ |
|
959 for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ |
|
960 (el) && ((tmp2) = (el)->next, 1); \ |
|
961 (el) = ((el) == (tmp1) ? NULL : (tmp2))) |
|
962 |
|
963 #define CDL_SEARCH_SCALAR(head,out,field,val) \ |
|
964 CDL_SEARCH_SCALAR2(head,out,field,val,next) |
|
965 |
|
966 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \ |
|
967 do { \ |
|
968 CDL_FOREACH2(head,out,next) { \ |
|
969 if ((out)->field == (val)) break; \ |
|
970 } \ |
|
971 } while (0) |
|
972 |
|
973 #define CDL_SEARCH(head,out,elt,cmp) \ |
|
974 CDL_SEARCH2(head,out,elt,cmp,next) |
|
975 |
|
976 #define CDL_SEARCH2(head,out,elt,cmp,next) \ |
|
977 do { \ |
|
978 CDL_FOREACH2(head,out,next) { \ |
|
979 if ((cmp(out,elt))==0) break; \ |
|
980 } \ |
|
981 } while (0) |
|
982 |
|
983 #define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ |
|
984 do { \ |
|
985 assert((head) != NULL); \ |
|
986 assert((el) != NULL); \ |
|
987 assert((add) != NULL); \ |
|
988 if ((el)->next == (el)) { \ |
|
989 (add)->next = (add); \ |
|
990 (add)->prev = (add); \ |
|
991 (head) = (add); \ |
|
992 } else { \ |
|
993 (add)->next = (el)->next; \ |
|
994 (add)->prev = (el)->prev; \ |
|
995 (add)->next->prev = (add); \ |
|
996 (add)->prev->next = (add); \ |
|
997 if ((head) == (el)) { \ |
|
998 (head) = (add); \ |
|
999 } \ |
|
1000 } \ |
|
1001 } while (0) |
|
1002 |
|
1003 #define CDL_REPLACE_ELEM(head, el, add) \ |
|
1004 CDL_REPLACE_ELEM2(head, el, add, prev, next) |
|
1005 |
|
1006 #define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ |
|
1007 do { \ |
|
1008 if (el) { \ |
|
1009 assert((head) != NULL); \ |
|
1010 assert((add) != NULL); \ |
|
1011 (add)->next = (el); \ |
|
1012 (add)->prev = (el)->prev; \ |
|
1013 (el)->prev = (add); \ |
|
1014 (add)->prev->next = (add); \ |
|
1015 if ((head) == (el)) { \ |
|
1016 (head) = (add); \ |
|
1017 } \ |
|
1018 } else { \ |
|
1019 CDL_APPEND2(head, add, prev, next); \ |
|
1020 } \ |
|
1021 } while (0) |
|
1022 |
|
1023 #define CDL_PREPEND_ELEM(head, el, add) \ |
|
1024 CDL_PREPEND_ELEM2(head, el, add, prev, next) |
|
1025 |
|
1026 #define CDL_APPEND_ELEM2(head, el, add, prev, next) \ |
|
1027 do { \ |
|
1028 if (el) { \ |
|
1029 assert((head) != NULL); \ |
|
1030 assert((add) != NULL); \ |
|
1031 (add)->next = (el)->next; \ |
|
1032 (add)->prev = (el); \ |
|
1033 (el)->next = (add); \ |
|
1034 (add)->next->prev = (add); \ |
|
1035 } else { \ |
|
1036 CDL_PREPEND2(head, add, prev, next); \ |
|
1037 } \ |
|
1038 } while (0) |
|
1039 |
|
1040 #define CDL_APPEND_ELEM(head, el, add) \ |
|
1041 CDL_APPEND_ELEM2(head, el, add, prev, next) |
|
1042 |
|
1043 #ifdef NO_DECLTYPE |
|
1044 /* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ |
|
1045 |
|
1046 #undef CDL_INSERT_INORDER2 |
|
1047 #define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ |
|
1048 do { \ |
|
1049 if ((head) == NULL) { \ |
|
1050 (add)->prev = (add); \ |
|
1051 (add)->next = (add); \ |
|
1052 (head) = (add); \ |
|
1053 } else if ((cmp(head, add)) >= 0) { \ |
|
1054 (add)->prev = (head)->prev; \ |
|
1055 (add)->next = (head); \ |
|
1056 (add)->prev->next = (add); \ |
|
1057 (head)->prev = (add); \ |
|
1058 (head) = (add); \ |
|
1059 } else { \ |
|
1060 char *_tmp = (char*)(head); \ |
|
1061 while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \ |
|
1062 (head) = (head)->next; \ |
|
1063 } \ |
|
1064 (add)->prev = (head); \ |
|
1065 (add)->next = (head)->next; \ |
|
1066 (add)->next->prev = (add); \ |
|
1067 (head)->next = (add); \ |
|
1068 UTLIST_RS(head); \ |
|
1069 } \ |
|
1070 } while (0) |
|
1071 #endif /* NO_DECLTYPE */ |
|
1072 |
|
1073 #endif /* UTLIST_H */ |