1/* $NetBSD: list.h,v 1.5 2020/05/25 20:47:21 christos Exp $ */ 2 3/* 4 * Copyright (C) 2004, 2006, 2007, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 5 * Copyright (C) 1997-2002 Internet Software Consortium. 6 * 7 * Permission to use, copy, modify, and/or distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 13 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 17 * PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20/* Id */ 21 22#ifndef ISC_LIST_H 23#define ISC_LIST_H 1 24#include <isc/boolean.h> 25#include <isc/assertions.h> 26 27#ifdef ISC_LIST_CHECKINIT 28#define ISC_LINK_INSIST(x) ISC_INSIST(x) 29#else 30#define ISC_LINK_INSIST(x) 31#endif 32 33#define ISC_LIST(type) struct { type *head, *tail; } 34#define ISC_LIST_INIT(list) \ 35 do { (list).head = NULL; (list).tail = NULL; } while (0) 36 37#define ISC_LINK(type) struct { type *prev, *next; } 38#define ISC_LINK_INIT_TYPE(elt, link, type) \ 39 do { \ 40 (elt)->link.prev = (type *)(-1); \ 41 (elt)->link.next = (type *)(-1); \ 42 } while (0) 43#define ISC_LINK_INIT(elt, link) \ 44 ISC_LINK_INIT_TYPE(elt, link, void) 45#define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 46 47#define ISC_LIST_HEAD(list) ((list).head) 48#define ISC_LIST_TAIL(list) ((list).tail) 49#define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL) 50 51#define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 52 do { \ 53 if ((list).head != NULL) \ 54 (list).head->link.prev = (elt); \ 55 else \ 56 (list).tail = (elt); \ 57 (elt)->link.prev = NULL; \ 58 (elt)->link.next = (list).head; \ 59 (list).head = (elt); \ 60 } while (0) 61 62#define ISC_LIST_PREPEND(list, elt, link) \ 63 do { \ 64 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 65 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 66 } while (0) 67 68#define ISC_LIST_INITANDPREPEND(list, elt, link) \ 69 __ISC_LIST_PREPENDUNSAFE(list, elt, link) 70 71#define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 72 do { \ 73 if ((list).tail != NULL) \ 74 (list).tail->link.next = (elt); \ 75 else \ 76 (list).head = (elt); \ 77 (elt)->link.prev = (list).tail; \ 78 (elt)->link.next = NULL; \ 79 (list).tail = (elt); \ 80 } while (0) 81 82#define ISC_LIST_APPEND(list, elt, link) \ 83 do { \ 84 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 85 __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 86 } while (0) 87 88#define ISC_LIST_INITANDAPPEND(list, elt, link) \ 89 __ISC_LIST_APPENDUNSAFE(list, elt, link) 90 91#define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 92 do { \ 93 if ((elt)->link.next != NULL) \ 94 (elt)->link.next->link.prev = (elt)->link.prev; \ 95 else { \ 96 ISC_INSIST((list).tail == (elt)); \ 97 (list).tail = (elt)->link.prev; \ 98 } \ 99 if ((elt)->link.prev != NULL) \ 100 (elt)->link.prev->link.next = (elt)->link.next; \ 101 else { \ 102 ISC_INSIST((list).head == (elt)); \ 103 (list).head = (elt)->link.next; \ 104 } \ 105 (elt)->link.prev = (type *)(-1); \ 106 (elt)->link.next = (type *)(-1); \ 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