1 /* 2 * Copyright (C) 1997-2001 Internet Software Consortium. 3 * 4 * Permission to use, copy, modify, and distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM 9 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 10 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL 11 * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, 12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING 13 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 14 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION 15 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 /* $Id: list.h,v 1.19 2002/05/09 07:09:30 marka Exp $ */ 19 20 #ifndef ISC_LIST_H 21 #define ISC_LIST_H 1 22 #include <isc/boolean.h> 23 #include <isc/assertions.h> 24 25 #ifdef ISC_LIST_CHECKINIT 26 #define ISC_LINK_INSIST(x) ISC_INSIST(x) 27 #else 28 #define ISC_LINK_INSIST(x) 29 #endif 30 31 #define ISC_LIST(type) struct { type *head, *tail; } 32 #define ISC_LIST_INIT(list) \ 33 do { (list).head = NULL; (list).tail = NULL; } while (0) 34 35 #define ISC_LINK(type) struct { type *prev, *next; } 36 #define ISC_LINK_INIT_TYPE(elt, link, type) \ 37 do { \ 38 (elt)->link.prev = (type *)(-1); \ 39 (elt)->link.next = (type *)(-1); \ 40 } while (0) 41 #define ISC_LINK_INIT(elt, link) \ 42 ISC_LINK_INIT_TYPE(elt, link, void) 43 #define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 44 45 #define ISC_LIST_HEAD(list) ((list).head) 46 #define ISC_LIST_TAIL(list) ((list).tail) 47 #define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL) 48 49 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 50 do { \ 51 if ((list).head != NULL) \ 52 (list).head->link.prev = (elt); \ 53 else \ 54 (list).tail = (elt); \ 55 (elt)->link.prev = NULL; \ 56 (elt)->link.next = (list).head; \ 57 (list).head = (elt); \ 58 } while (0) 59 60 #define ISC_LIST_PREPEND(list, elt, link) \ 61 do { \ 62 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 63 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 64 } while (0) 65 66 #define ISC_LIST_INITANDPREPEND(list, elt, link) \ 67 __ISC_LIST_PREPENDUNSAFE(list, elt, link) 68 69 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 70 do { \ 71 if ((list).tail != NULL) \ 72 (list).tail->link.next = (elt); \ 73 else \ 74 (list).head = (elt); \ 75 (elt)->link.prev = (list).tail; \ 76 (elt)->link.next = NULL; \ 77 (list).tail = (elt); \ 78 } while (0) 79 80 #define ISC_LIST_APPEND(list, elt, link) \ 81 do { \ 82 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 83 __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 84 } while (0) 85 86 #define ISC_LIST_INITANDAPPEND(list, elt, link) \ 87 __ISC_LIST_APPENDUNSAFE(list, elt, link) 88 89 #define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 90 do { \ 91 if ((elt)->link.next != NULL) \ 92 (elt)->link.next->link.prev = (elt)->link.prev; \ 93 else \ 94 (list).tail = (elt)->link.prev; \ 95 if ((elt)->link.prev != NULL) \ 96 (elt)->link.prev->link.next = (elt)->link.next; \ 97 else \ 98 (list).head = (elt)->link.next; \ 99 (elt)->link.prev = (type *)(-1); \ 100 (elt)->link.next = (type *)(-1); \ 101 } while (0) 102 103 #define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 104 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 105 106 #define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 107 do { \ 108 ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 109 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 110 } while (0) 111 #define ISC_LIST_UNLINK(list, elt, link) \ 112 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 113 114 #define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 115 #define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 116 117 #define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 118 do { \ 119 if ((before)->link.prev == NULL) \ 120 ISC_LIST_PREPEND(list, elt, link); \ 121 else { \ 122 (elt)->link.prev = (before)->link.prev; \ 123 (before)->link.prev = (elt); \ 124 (elt)->link.prev->link.next = (elt); \ 125 (elt)->link.next = (before); \ 126 } \ 127 } while (0) 128 129 #define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 130 do { \ 131 ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 132 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 133 __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 134 } while (0) 135 136 #define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 137 do { \ 138 if ((after)->link.next == NULL) \ 139 ISC_LIST_APPEND(list, elt, link); \ 140 else { \ 141 (elt)->link.next = (after)->link.next; \ 142 (after)->link.next = (elt); \ 143 (elt)->link.next->link.prev = (elt); \ 144 (elt)->link.prev = (after); \ 145 } \ 146 } while (0) 147 148 #define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 149 do { \ 150 ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 151 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 152 __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 153 } while (0) 154 155 #define ISC_LIST_APPENDLIST(list1, list2, link) \ 156 do { \ 157 if (ISC_LIST_EMPTY(list1)) \ 158 (list1) = (list2); \ 159 else if (!ISC_LIST_EMPTY(list2)) { \ 160 (list1).tail->link.next = (list2).head; \ 161 (list2).head->link.prev = (list1).tail; \ 162 (list1).tail = (list2).tail; \ 163 } \ 164 (list2).head = NULL; \ 165 (list2).tail = NULL; \ 166 } while (0) 167 168 #define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 169 #define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 170 __ISC_LIST_APPENDUNSAFE(list, elt, link) 171 #define ISC_LIST_DEQUEUE(list, elt, link) \ 172 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 173 #define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 174 ISC_LIST_UNLINK_TYPE(list, elt, link, type) 175 #define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 176 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 177 #define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 178 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 179 180 #endif /* ISC_LIST_H */ 181