Mercurial > embed
comparison libutlist/utlist.h @ 103:2cb5c5c33ff1
utlist: import 2.3.0
author | David Demelier <markand@malikania.fr> |
---|---|
date | Wed, 15 Jun 2022 10:25:09 +0200 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
102:f6e4a0d002a7 | 103:2cb5c5c33ff1 |
---|---|
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 */ |