1/* 2 * Copyright (C) 2004, 2006, 2007, 2011-2013 Internet Systems Consortium, Inc. ("ISC") 3 * Copyright (C) 1997-2002 Internet Software Consortium. 4 * 5 * Permission to use, copy, modify, and/or 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 WITH 10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15 * PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18/* $Id$ */ 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 ISC_INSIST((list).tail == (elt)); \ 95 (list).tail = (elt)->link.prev; \ 96 } \ 97 if ((elt)->link.prev != NULL) \ 98 (elt)->link.prev->link.next = (elt)->link.next; \ 99 else { \ 100 ISC_INSIST((list).head == (elt)); \ 101 (list).head = (elt)->link.next; \ 102 } \ 103 (elt)->link.prev = (type *)(-1); \ 104 (elt)->link.next = (type *)(-1); \ 105 ISC_INSIST((list).head != (elt)); \ 106 ISC_INSIST((list).tail != (elt)); \ 107 } while (0) 108 109#define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 110 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 111 112#define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 113 do { \ 114 ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 115 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 116 } while (0) 117#define ISC_LIST_UNLINK(list, elt, link) \ 118 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 119 120#define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 121#define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 122 123#define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 124 do { \ 125 if ((before)->link.prev == NULL) \ 126 ISC_LIST_PREPEND(list, elt, link); \ 127 else { \ 128 (elt)->link.prev = (before)->link.prev; \ 129 (before)->link.prev = (elt); \ 130 (elt)->link.prev->link.next = (elt); \ 131 (elt)->link.next = (before); \ 132 } \ 133 } while (0) 134 135#define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 136 do { \ 137 ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 138 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 139 __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 140 } while (0) 141 142#define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 143 do { \ 144 if ((after)->link.next == NULL) \ 145 ISC_LIST_APPEND(list, elt, link); \ 146 else { \ 147 (elt)->link.next = (after)->link.next; \ 148 (after)->link.next = (elt); \ 149 (elt)->link.next->link.prev = (elt); \ 150 (elt)->link.prev = (after); \ 151 } \ 152 } while (0) 153 154#define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 155 do { \ 156 ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 157 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 158 __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 159 } while (0) 160 161#define ISC_LIST_APPENDLIST(list1, list2, link) \ 162 do { \ 163 if (ISC_LIST_EMPTY(list1)) \ 164 (list1) = (list2); \ 165 else if (!ISC_LIST_EMPTY(list2)) { \ 166 (list1).tail->link.next = (list2).head; \ 167 (list2).head->link.prev = (list1).tail; \ 168 (list1).tail = (list2).tail; \ 169 } \ 170 (list2).head = NULL; \ 171 (list2).tail = NULL; \ 172 } while (0) 173 174#define ISC_LIST_PREPENDLIST(list1, list2, link) \ 175 do { \ 176 if (ISC_LIST_EMPTY(list1)) \ 177 (list1) = (list2); \ 178 else if (!ISC_LIST_EMPTY(list2)) { \ 179 (list2).tail->link.next = (list1).head; \ 180 (list1).head->link.prev = (list2).tail; \ 181 (list1).head = (list2).head; \ 182 } \ 183 (list2).head = NULL; \ 184 (list2).tail = NULL; \ 185 } while (0) 186 187#define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 188#define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 189 __ISC_LIST_APPENDUNSAFE(list, elt, link) 190#define ISC_LIST_DEQUEUE(list, elt, link) \ 191 ISC_LIST_UNLINK_TYPE(list, elt, link, void) 192#define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 193 ISC_LIST_UNLINK_TYPE(list, elt, link, type) 194#define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 195 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 196#define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 197 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 198 199#endif /* ISC_LIST_H */ 200