?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Drop main() prototype. Syncs with NetBSD-8
[minix.git] / minix / lib / libmagicrt / include / common / ut / utlist.h
blob6bccec7ada3a55e12f1a5d275acd07e9ec6e3203
1 /*
2 Copyright (c) 2007-2013, 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 1.9.8
28
29 #include <assert.h>
30
31 /*
32 * This file contains macros to manipulate singly and doubly-linked lists.
33 *
34 * 1. LL_ macros: singly-linked lists.
35 * 2. DL_ macros: doubly-linked lists.
36 * 3. CDL_ macros: circular doubly-linked lists.
37 *
38 * To use singly-linked lists, your structure must have a "next" pointer.
39 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
40 * Either way, the pointer to the head of the list must be initialized to NULL.
41 *
42 * ----------------.EXAMPLE -------------------------
43 * struct item {
44 * int id;
45 * struct item *prev, *next;
46 * }
47 *
48 * struct item *list = NULL:
49 *
50 * int main() {
51 * struct item *item;
52 * ... allocate and populate item ...
53 * DL_APPEND(list, item);
54 * }
55 * --------------------------------------------------
56 *
57 * For doubly-linked lists, the append and delete macros are O(1)
58 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
59 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
60 */
61
62 /* These macros use decltype or the earlier __typeof GNU extension.
63 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
64 when compiling c++ code), this code uses whatever method is needed
65 or, for VS2008 where neither is available, uses casting workarounds. */
66 #ifdef _MSC_VER /* MS compiler */
67 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
68 #define LDECLTYPE(x) decltype(x)
69 #else /* VS2008 or older (or VS2010 in C mode) */
70 #define NO_DECLTYPE
71 #define LDECLTYPE(x) char*
72 #endif
73 #else /* GNU, Sun and other compilers */
74 #define LDECLTYPE(x) __typeof(x)
75 #endif
76
77 /* for VS2008 we use some workarounds to get around the lack of decltype,
78 * namely, we always reassign our tmp variable to the list head if we need
79 * to dereference its prev/next pointers, and save/restore the real head.*/
80 #ifdef NO_DECLTYPE
81 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
82 #define _NEXT(elt,list,next) ((char*)((list)->next))
83 #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
84 /* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
85 #define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
86 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
87 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
88 #else
89 #define _SV(elt,list)
90 #define _NEXT(elt,list,next) ((elt)->next)
91 #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
92 /* #define _PREV(elt,list,prev) ((elt)->prev) */
93 #define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
94 #define _RS(list)
95 #define _CASTASGN(a,b) (a)=(b)
96 #endif
97
98 /******************************************************************************
99 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
100 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
101 *****************************************************************************/
102 #define LL_SORT(list, cmp) \
103 LL_SORT2(list, cmp, next)
104
105 #define LL_SORT2(list, cmp, next) \
106 do { \
107 LDECLTYPE(list) _ls_p; \
108 LDECLTYPE(list) _ls_q; \
109 LDECLTYPE(list) _ls_e; \
110 LDECLTYPE(list) _ls_tail; \
111 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
112 if (list) { \
113 _ls_insize = 1; \
114 _ls_looping = 1; \
115 while (_ls_looping) { \
116 _CASTASGN(_ls_p,list); \
117 list = NULL; \
118 _ls_tail = NULL; \
119 _ls_nmerges = 0; \
120 while (_ls_p) { \
121 _ls_nmerges++; \
122 _ls_q = _ls_p; \
123 _ls_psize = 0; \
124 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
125 _ls_psize++; \
126 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
127 if (!_ls_q) break; \
128 } \
129 _ls_qsize = _ls_insize; \
130 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
131 if (_ls_psize == 0) { \
132 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
133 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
134 } else if (_ls_qsize == 0 || !_ls_q) { \
135 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
136 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
137 } else if (cmp(_ls_p,_ls_q) <= 0) { \
138 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
139 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
140 } else { \
141 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
142 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
143 } \
144 if (_ls_tail) { \
145 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
146 } else { \
147 _CASTASGN(list,_ls_e); \
148 } \
149 _ls_tail = _ls_e; \
150 } \
151 _ls_p = _ls_q; \
152 } \
153 if (_ls_tail) { \
154 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
155 } \
156 if (_ls_nmerges <= 1) { \
157 _ls_looping=0; \
158 } \
159 _ls_insize *= 2; \
160 } \
161 } \
162 } while (0)
163
164
165 #define DL_SORT(list, cmp) \
166 DL_SORT2(list, cmp, prev, next)
167
168 #define DL_SORT2(list, cmp, prev, next) \
169 do { \
170 LDECLTYPE(list) _ls_p; \
171 LDECLTYPE(list) _ls_q; \
172 LDECLTYPE(list) _ls_e; \
173 LDECLTYPE(list) _ls_tail; \
174 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
175 if (list) { \
176 _ls_insize = 1; \
177 _ls_looping = 1; \
178 while (_ls_looping) { \
179 _CASTASGN(_ls_p,list); \
180 list = NULL; \
181 _ls_tail = NULL; \
182 _ls_nmerges = 0; \
183 while (_ls_p) { \
184 _ls_nmerges++; \
185 _ls_q = _ls_p; \
186 _ls_psize = 0; \
187 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
188 _ls_psize++; \
189 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
190 if (!_ls_q) break; \
191 } \
192 _ls_qsize = _ls_insize; \
193 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
194 if (_ls_psize == 0) { \
195 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
196 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
197 } else if (_ls_qsize == 0 || !_ls_q) { \
198 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
199 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
200 } else if (cmp(_ls_p,_ls_q) <= 0) { \
201 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
202 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
203 } else { \
204 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
205 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
206 } \
207 if (_ls_tail) { \
208 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
209 } else { \
210 _CASTASGN(list,_ls_e); \
211 } \
212 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
213 _ls_tail = _ls_e; \
214 } \
215 _ls_p = _ls_q; \
216 } \
217 _CASTASGN(list->prev, _ls_tail); \
218 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
219 if (_ls_nmerges <= 1) { \
220 _ls_looping=0; \
221 } \
222 _ls_insize *= 2; \
223 } \
224 } \
225 } while (0)
226
227 #define CDL_SORT(list, cmp) \
228 CDL_SORT2(list, cmp, prev, next)
229
230 #define CDL_SORT2(list, cmp, prev, next) \
231 do { \
232 LDECLTYPE(list) _ls_p; \
233 LDECLTYPE(list) _ls_q; \
234 LDECLTYPE(list) _ls_e; \
235 LDECLTYPE(list) _ls_tail; \
236 LDECLTYPE(list) _ls_oldhead; \
237 LDECLTYPE(list) _tmp; \
238 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
239 if (list) { \
240 _ls_insize = 1; \
241 _ls_looping = 1; \
242 while (_ls_looping) { \
243 _CASTASGN(_ls_p,list); \
244 _CASTASGN(_ls_oldhead,list); \
245 list = NULL; \
246 _ls_tail = NULL; \
247 _ls_nmerges = 0; \
248 while (_ls_p) { \
249 _ls_nmerges++; \
250 _ls_q = _ls_p; \
251 _ls_psize = 0; \
252 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
253 _ls_psize++; \
254 _SV(_ls_q,list); \
255 if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
256 _ls_q = NULL; \
257 } else { \
258 _ls_q = _NEXT(_ls_q,list,next); \
259 } \
260 _RS(list); \
261 if (!_ls_q) break; \
262 } \
263 _ls_qsize = _ls_insize; \
264 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
265 if (_ls_psize == 0) { \
266 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
267 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
268 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
269 } else if (_ls_qsize == 0 || !_ls_q) { \
270 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
271 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
272 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
273 } else if (cmp(_ls_p,_ls_q) <= 0) { \
274 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
275 _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
276 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
277 } else { \
278 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
279 _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
280 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
281 } \
282 if (_ls_tail) { \
283 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
284 } else { \
285 _CASTASGN(list,_ls_e); \
286 } \
287 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
288 _ls_tail = _ls_e; \
289 } \
290 _ls_p = _ls_q; \
291 } \
292 _CASTASGN(list->prev,_ls_tail); \
293 _CASTASGN(_tmp,list); \
294 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
295 if (_ls_nmerges <= 1) { \
296 _ls_looping=0; \
297 } \
298 _ls_insize *= 2; \
299 } \
300 } \
301 } while (0)
302
303 /******************************************************************************
304 * singly linked list macros (non-circular) *
305 *****************************************************************************/
306 #define LL_PREPEND(head,add) \
307 LL_PREPEND2(head,add,next)
308
309 #define LL_PREPEND2(head,add,next) \
310 do { \
311 (add)->next = head; \
312 head = add; \
313 } while (0)
314
315 #define LL_CONCAT(head1,head2) \
316 LL_CONCAT2(head1,head2,next)
317
318 #define LL_CONCAT2(head1,head2,next) \
319 do { \
320 LDECLTYPE(head1) _tmp; \
321 if (head1) { \
322 _tmp = head1; \
323 while (_tmp->next) { _tmp = _tmp->next; } \
324 _tmp->next=(head2); \
325 } else { \
326 (head1)=(head2); \
327 } \
328 } while (0)
329
330 #define LL_APPEND(head,add) \
331 LL_APPEND2(head,add,next)
332
333 #define LL_APPEND2(head,add,next) \
334 do { \
335 LDECLTYPE(head) _tmp; \
336 (add)->next=NULL; \
337 if (head) { \
338 _tmp = head; \
339 while (_tmp->next) { _tmp = _tmp->next; } \
340 _tmp->next=(add); \
341 } else { \
342 (head)=(add); \
343 } \
344 } while (0)
345
346 #define LL_DELETE(head,del) \
347 LL_DELETE2(head,del,next)
348
349 #define LL_DELETE2(head,del,next) \
350 do { \
351 LDECLTYPE(head) _tmp; \
352 if ((head) == (del)) { \
353 (head)=(head)->next; \
354 } else { \
355 _tmp = head; \
356 while (_tmp->next && (_tmp->next != (del))) { \
357 _tmp = _tmp->next; \
358 } \
359 if (_tmp->next) { \
360 _tmp->next = ((del)->next); \
361 } \
362 } \
363 } while (0)
364
365 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
366 #define LL_APPEND_VS2008(head,add) \
367 LL_APPEND2_VS2008(head,add,next)
368
369 #define LL_APPEND2_VS2008(head,add,next) \
370 do { \
371 if (head) { \
372 (add)->next = head; /* use add->next as a temp variable */ \
373 while ((add)->next->next) { (add)->next = (add)->next->next; } \
374 (add)->next->next=(add); \
375 } else { \
376 (head)=(add); \
377 } \
378 (add)->next=NULL; \
379 } while (0)
380
381 #define LL_DELETE_VS2008(head,del) \
382 LL_DELETE2_VS2008(head,del,next)
383
384 #define LL_DELETE2_VS2008(head,del,next) \
385 do { \
386 if ((head) == (del)) { \
387 (head)=(head)->next; \
388 } else { \
389 char *_tmp = (char*)(head); \
390 while ((head)->next && ((head)->next != (del))) { \
391 head = (head)->next; \
392 } \
393 if ((head)->next) { \
394 (head)->next = ((del)->next); \
395 } \
396 { \
397 char **_head_alias = (char**)&(head); \
398 *_head_alias = _tmp; \
399 } \
400 } \
401 } while (0)
402 #ifdef NO_DECLTYPE
403 #undef LL_APPEND
404 #define LL_APPEND LL_APPEND_VS2008
405 #undef LL_DELETE
406 #define LL_DELETE LL_DELETE_VS2008
407 #undef LL_DELETE2
408 #define LL_DELETE2_VS2008
409 #undef LL_APPEND2
410 #define LL_APPEND2 LL_APPEND2_VS2008
411 #undef LL_CONCAT /* no LL_CONCAT_VS2008 */
412 #undef DL_CONCAT /* no DL_CONCAT_VS2008 */
413 #endif
414 /* end VS2008 replacements */
415
416 #define LL_FOREACH(head,el) \
417 LL_FOREACH2(head,el,next)
418
419 #define LL_FOREACH2(head,el,next) \
420 for(el=head;el;el=(el)->next)
421
422 #define LL_FOREACH_SAFE(head,el,tmp) \
423 LL_FOREACH_SAFE2(head,el,tmp,next)
424
425 #define LL_FOREACH_SAFE2(head,el,tmp,next) \
426 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
427
428 #define LL_SEARCH_SCALAR(head,out,field,val) \
429 LL_SEARCH_SCALAR2(head,out,field,val,next)
430
431 #define LL_SEARCH_SCALAR2(head,out,field,val,next) \
432 do { \
433 LL_FOREACH2(head,out,next) { \
434 if ((out)->field == (val)) break; \
435 } \
436 } while(0)
437
438 #define LL_SEARCH(head,out,elt,cmp) \
439 LL_SEARCH2(head,out,elt,cmp,next)
440
441 #define LL_SEARCH2(head,out,elt,cmp,next) \
442 do { \
443 LL_FOREACH2(head,out,next) { \
444 if ((cmp(out,elt))==0) break; \
445 } \
446 } while(0)
447
448 #define LL_REPLACE_ELEM(head, el, add) \
449 do { \
450 LDECLTYPE(head) _tmp; \
451 assert(head != NULL); \
452 assert(el != NULL); \
453 assert(add != NULL); \
454 (add)->next = (el)->next; \
455 if ((head) == (el)) { \
456 (head) = (add); \
457 } else { \
458 _tmp = head; \
459 while (_tmp->next && (_tmp->next != (el))) { \
460 _tmp = _tmp->next; \
461 } \
462 if (_tmp->next) { \
463 _tmp->next = (add); \
464 } \
465 } \
466 } while (0)
467
468 #define LL_PREPEND_ELEM(head, el, add) \
469 do { \
470 LDECLTYPE(head) _tmp; \
471 assert(head != NULL); \
472 assert(el != 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 } while (0) \
487
488
489 /******************************************************************************
490 * doubly linked list macros (non-circular) *
491 *****************************************************************************/
492 #define DL_PREPEND(head,add) \
493 DL_PREPEND2(head,add,prev,next)
494
495 #define DL_PREPEND2(head,add,prev,next) \
496 do { \
497 (add)->next = head; \
498 if (head) { \
499 (add)->prev = (head)->prev; \
500 (head)->prev = (add); \
501 } else { \
502 (add)->prev = (add); \
503 } \
504 (head) = (add); \
505 } while (0)
506
507 #define DL_APPEND(head,add) \
508 DL_APPEND2(head,add,prev,next)
509
510 #define DL_APPEND2(head,add,prev,next) \
511 do { \
512 if (head) { \
513 (add)->prev = (head)->prev; \
514 (head)->prev->next = (add); \
515 (head)->prev = (add); \
516 (add)->next = NULL; \
517 } else { \
518 (head)=(add); \
519 (head)->prev = (head); \
520 (head)->next = NULL; \
521 } \
522 } while (0)
523
524 #define DL_CONCAT(head1,head2) \
525 DL_CONCAT2(head1,head2,prev,next)
526
527 #define DL_CONCAT2(head1,head2,prev,next) \
528 do { \
529 LDECLTYPE(head1) _tmp; \
530 if (head2) { \
531 if (head1) { \
532 _tmp = (head2)->prev; \
533 (head2)->prev = (head1)->prev; \
534 (head1)->prev->next = (head2); \
535 (head1)->prev = _tmp; \
536 } else { \
537 (head1)=(head2); \
538 } \
539 } \
540 } while (0)
541
542 #define DL_DELETE(head,del) \
543 DL_DELETE2(head,del,prev,next)
544
545 #define DL_DELETE2(head,del,prev,next) \
546 do { \
547 assert((del)->prev != NULL); \
548 if ((del)->prev == (del)) { \
549 (head)=NULL; \
550 } else if ((del)==(head)) { \
551 (del)->next->prev = (del)->prev; \
552 (head) = (del)->next; \
553 } else { \
554 (del)->prev->next = (del)->next; \
555 if ((del)->next) { \
556 (del)->next->prev = (del)->prev; \
557 } else { \
558 (head)->prev = (del)->prev; \
559 } \
560 } \
561 } while (0)
562
563
564 #define DL_FOREACH(head,el) \
565 DL_FOREACH2(head,el,next)
566
567 #define DL_FOREACH2(head,el,next) \
568 for(el=head;el;el=(el)->next)
569
570 /* this version is safe for deleting the elements during iteration */
571 #define DL_FOREACH_SAFE(head,el,tmp) \
572 DL_FOREACH_SAFE2(head,el,tmp,next)
573
574 #define DL_FOREACH_SAFE2(head,el,tmp,next) \
575 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
576
577 /* these are identical to their singly-linked list counterparts */
578 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
579 #define DL_SEARCH LL_SEARCH
580 #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
581 #define DL_SEARCH2 LL_SEARCH2
582
583 #define DL_REPLACE_ELEM(head, el, add) \
584 do { \
585 assert(head != NULL); \
586 assert(el != NULL); \
587 assert(add != NULL); \
588 if ((head) == (el)) { \
589 (head) = (add); \
590 (add)->next = (el)->next; \
591 if ((el)->next == NULL) { \
592 (add)->prev = (add); \
593 } else { \
594 (add)->prev = (el)->prev; \
595 (add)->next->prev = (add); \
596 } \
597 } else { \
598 (add)->next = (el)->next; \
599 (add)->prev = (el)->prev; \
600 (add)->prev->next = (add); \
601 if ((el)->next == NULL) { \
602 (head)->prev = (add); \
603 } else { \
604 (add)->next->prev = (add); \
605 } \
606 } \
607 } while (0)
608
609 #define DL_PREPEND_ELEM(head, el, add) \
610 do { \
611 assert(head != NULL); \
612 assert(el != NULL); \
613 assert(add != NULL); \
614 (add)->next = (el); \
615 (add)->prev = (el)->prev; \
616 (el)->prev = (add); \
617 if ((head) == (el)) { \
618 (head) = (add); \
619 } else { \
620 (add)->prev->next = (add); \
621 } \
622 } while (0) \
623
624
625 /******************************************************************************
626 * circular doubly linked list macros *
627 *****************************************************************************/
628 #define CDL_PREPEND(head,add) \
629 CDL_PREPEND2(head,add,prev,next)
630
631 #define CDL_PREPEND2(head,add,prev,next) \
632 do { \
633 if (head) { \
634 (add)->prev = (head)->prev; \
635 (add)->next = (head); \
636 (head)->prev = (add); \
637 (add)->prev->next = (add); \
638 } else { \
639 (add)->prev = (add); \
640 (add)->next = (add); \
641 } \
642 (head)=(add); \
643 } while (0)
644
645 #define CDL_DELETE(head,del) \
646 CDL_DELETE2(head,del,prev,next)
647
648 #define CDL_DELETE2(head,del,prev,next) \
649 do { \
650 if ( ((head)==(del)) && ((head)->next == (head))) { \
651 (head) = 0L; \
652 } else { \
653 (del)->next->prev = (del)->prev; \
654 (del)->prev->next = (del)->next; \
655 if ((del) == (head)) (head)=(del)->next; \
656 } \
657 } while (0)
658
659 #define CDL_FOREACH(head,el) \
660 CDL_FOREACH2(head,el,next)
661
662 #define CDL_FOREACH2(head,el,next) \
663 for(el=head;el;el=((el)->next==head ? 0L : (el)->next))
664
665 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
666 CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
667
668 #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
669 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
670 (el) && ((tmp2)=(el)->next, 1); \
671 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
672
673 #define CDL_SEARCH_SCALAR(head,out,field,val) \
674 CDL_SEARCH_SCALAR2(head,out,field,val,next)
675
676 #define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
677 do { \
678 CDL_FOREACH2(head,out,next) { \
679 if ((out)->field == (val)) break; \
680 } \
681 } while(0)
682
683 #define CDL_SEARCH(head,out,elt,cmp) \
684 CDL_SEARCH2(head,out,elt,cmp,next)
685
686 #define CDL_SEARCH2(head,out,elt,cmp,next) \
687 do { \
688 CDL_FOREACH2(head,out,next) { \
689 if ((cmp(out,elt))==0) break; \
690 } \
691 } while(0)
692
693 #define CDL_REPLACE_ELEM(head, el, add) \
694 do { \
695 assert(head != NULL); \
696 assert(el != NULL); \
697 assert(add != NULL); \
698 if ((el)->next == (el)) { \
699 (add)->next = (add); \
700 (add)->prev = (add); \
701 (head) = (add); \
702 } else { \
703 (add)->next = (el)->next; \
704 (add)->prev = (el)->prev; \
705 (add)->next->prev = (add); \
706 (add)->prev->next = (add); \
707 if ((head) == (el)) { \
708 (head) = (add); \
709 } \
710 } \
711 } while (0)
712
713 #define CDL_PREPEND_ELEM(head, el, add) \
714 do { \
715 assert(head != NULL); \
716 assert(el != NULL); \
717 assert(add != NULL); \
718 (add)->next = (el); \
719 (add)->prev = (el)->prev; \
720 (el)->prev = (add); \
721 (add)->prev->next = (add); \
722 if ((head) == (el)) { \
723 (head) = (add); \
724 } \
725 } while (0) \
726
727 #endif /* UTLIST_H */
728
MINIX 3 (repo.or.cz mirror)