1 /* 2 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 3 * Copyright (c) 1997,1999 by Internet Software Consortium. 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 15 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 /* $FreeBSD$ */ 19 20 #ifndef LIST_H 21 #define LIST_H 1 22 #ifdef _LIBC 23 #include <assert.h> 24 #define INSIST(cond) assert(cond) 25 #else 26 #include <isc/assertions.h> 27 #endif 28 29 #define LIST(type) struct { type *head, *tail; } 30 #define INIT_LIST(list) \ 31 do { (list).head = NULL; (list).tail = NULL; } while (0) 32 33 #define LINK(type) struct { type *prev, *next; } 34 #define INIT_LINK_TYPE(elt, link, type) \ 35 do { \ 36 (elt)->link.prev = (type *)(-1); \ 37 (elt)->link.next = (type *)(-1); \ 38 } while (0) 39 #define INIT_LINK(elt, link) \ 40 INIT_LINK_TYPE(elt, link, void) 41 #define LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 42 43 #define HEAD(list) ((list).head) 44 #define TAIL(list) ((list).tail) 45 #define EMPTY(list) ((list).head == NULL) 46 47 #define PREPEND(list, elt, link) \ 48 do { \ 49 INSIST(!LINKED(elt, link));\ 50 if ((list).head != NULL) \ 51 (list).head->link.prev = (elt); \ 52 else \ 53 (list).tail = (elt); \ 54 (elt)->link.prev = NULL; \ 55 (elt)->link.next = (list).head; \ 56 (list).head = (elt); \ 57 } while (0) 58 59 #define APPEND(list, elt, link) \ 60 do { \ 61 INSIST(!LINKED(elt, link));\ 62 if ((list).tail != NULL) \ 63 (list).tail->link.next = (elt); \ 64 else \ 65 (list).head = (elt); \ 66 (elt)->link.prev = (list).tail; \ 67 (elt)->link.next = NULL; \ 68 (list).tail = (elt); \ 69 } while (0) 70 71 #define UNLINK_TYPE(list, elt, link, type) \ 72 do { \ 73 INSIST(LINKED(elt, link));\ 74 if ((elt)->link.next != NULL) \ 75 (elt)->link.next->link.prev = (elt)->link.prev; \ 76 else \ 77 (list).tail = (elt)->link.prev; \ 78 if ((elt)->link.prev != NULL) \ 79 (elt)->link.prev->link.next = (elt)->link.next; \ 80 else \ 81 (list).head = (elt)->link.next; \ 82 INIT_LINK_TYPE(elt, link, type); \ 83 } while (0) 84 #define UNLINK(list, elt, link) \ 85 UNLINK_TYPE(list, elt, link, void) 86 87 #define PREV(elt, link) ((elt)->link.prev) 88 #define NEXT(elt, link) ((elt)->link.next) 89 90 #define INSERT_BEFORE(list, before, elt, link) \ 91 do { \ 92 INSIST(!LINKED(elt, link));\ 93 if ((before)->link.prev == NULL) \ 94 PREPEND(list, elt, link); \ 95 else { \ 96 (elt)->link.prev = (before)->link.prev; \ 97 (before)->link.prev = (elt); \ 98 (elt)->link.prev->link.next = (elt); \ 99 (elt)->link.next = (before); \ 100 } \ 101 } while (0) 102 103 #define INSERT_AFTER(list, after, elt, link) \ 104 do { \ 105 INSIST(!LINKED(elt, link));\ 106 if ((after)->link.next == NULL) \ 107 APPEND(list, elt, link); \ 108 else { \ 109 (elt)->link.next = (after)->link.next; \ 110 (after)->link.next = (elt); \ 111 (elt)->link.next->link.prev = (elt); \ 112 (elt)->link.prev = (after); \ 113 } \ 114 } while (0) 115 116 #define ENQUEUE(list, elt, link) APPEND(list, elt, link) 117 #define DEQUEUE(list, elt, link) UNLINK(list, elt, link) 118 119 #endif /* LIST_H */ 120