Mercurial > irccd

comparison extern/libutlist/utlist.h @ 1067:f8fc0d12853d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
misc: remove usage of BSD sys/queue.h (peer)
author David Demelier <markand@malikania.fr>
date Mon, 12 Jul 2021 21:03:26 +0200
parents
children
comparison
equal deleted inserted replaced
1066:1da37177a428 1067:f8fc0d12853d
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 */