1290001Sglebius/* 2290001Sglebius * Copyright (C) 2004, 2006, 2007, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 3290001Sglebius * Copyright (C) 1997-2002 Internet Software Consortium. 4290001Sglebius * 5290001Sglebius * Permission to use, copy, modify, and/or distribute this software for any 6290001Sglebius * purpose with or without fee is hereby granted, provided that the above 7290001Sglebius * copyright notice and this permission notice appear in all copies. 8290001Sglebius * 9290001Sglebius * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10290001Sglebius * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11290001Sglebius * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12290001Sglebius * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13290001Sglebius * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14290001Sglebius * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15290001Sglebius * PERFORMANCE OF THIS SOFTWARE. 16290001Sglebius */ 17290001Sglebius 18290001Sglebius/* $Id$ */ 19290001Sglebius 20290001Sglebius#ifndef ISC_LIST_H 21290001Sglebius#define ISC_LIST_H 1 22290001Sglebius#include <isc/boolean.h> 23290001Sglebius#include <isc/assertions.h> 24290001Sglebius 25290001Sglebius#ifdef ISC_LIST_CHECKINIT 26290001Sglebius#define ISC_LINK_INSIST(x) ISC_INSIST(x) 27290001Sglebius#else 28290001Sglebius#define ISC_LINK_INSIST(x) 29290001Sglebius#endif 30290001Sglebius 31290001Sglebius#define ISC_LIST(type) struct { type *head, *tail; } 32290001Sglebius#define ISC_LIST_INIT(list) \ 33290001Sglebius do { (list).head = NULL; (list).tail = NULL; } while (0) 34290001Sglebius 35290001Sglebius#define ISC_LINK(type) struct { type *prev, *next; } 36290001Sglebius#define ISC_LINK_INIT_TYPE(elt, link, type) \ 37290001Sglebius do { \ 38290001Sglebius (elt)->link.prev = (type *)(-1); \ 39290001Sglebius (elt)->link.next = (type *)(-1); \ 40290001Sglebius } while (0) 41290001Sglebius#define ISC_LINK_INIT(elt, link) \ 42290001Sglebius ISC_LINK_INIT_TYPE(elt, link, void) 43290001Sglebius#define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 44290001Sglebius 45290001Sglebius#define ISC_LIST_HEAD(list) ((list).head) 46290001Sglebius#define ISC_LIST_TAIL(list) ((list).tail) 47290001Sglebius#define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL) 48290001Sglebius 49290001Sglebius#define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 50290001Sglebius do { \ 51290001Sglebius if ((list).head != NULL) \ 52290001Sglebius (list).head->link.prev = (elt); \ 53290001Sglebius else \ 54290001Sglebius (list).tail = (elt); \ 55290001Sglebius (elt)->link.prev = NULL; \ 56290001Sglebius (elt)->link.next = (list).head; \ 57290001Sglebius (list).head = (elt); \ 58290001Sglebius } while (0) 59290001Sglebius 60290001Sglebius#define ISC_LIST_PREPEND(list, elt, link) \ 61290001Sglebius do { \ 62290001Sglebius ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 63290001Sglebius __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 64290001Sglebius } while (0) 65290001Sglebius 66290001Sglebius#define ISC_LIST_INITANDPREPEND(list, elt, link) \ 67290001Sglebius __ISC_LIST_PREPENDUNSAFE(list, elt, link) 68290001Sglebius 69290001Sglebius#define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 70290001Sglebius do { \ 71290001Sglebius if ((list).tail != NULL) \ 72290001Sglebius (list).tail->link.next = (elt); \ 73290001Sglebius else \ 74290001Sglebius (list).head = (elt); \ 75290001Sglebius (elt)->link.prev = (list).tail; \ 76290001Sglebius (elt)->link.next = NULL; \ 77290001Sglebius (list).tail = (elt); \ 78290001Sglebius } while (0) 79290001Sglebius 80290001Sglebius#define ISC_LIST_APPEND(list, elt, link) \ 81290001Sglebius do { \ 82290001Sglebius ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 83290001Sglebius __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 84290001Sglebius } while (0) 85290001Sglebius 86290001Sglebius#define ISC_LIST_INITANDAPPEND(list, elt, link) \ 87290001Sglebius __ISC_LIST_APPENDUNSAFE(list, elt, link) 88290001Sglebius 89290001Sglebius#define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 90290001Sglebius do { \ 91290001Sglebius if ((elt)->link.next != NULL) \ 92290001Sglebius (elt)->link.next->link.prev = (elt)->link.prev; \ 93290001Sglebius else { \ 94290001Sglebius ISC_INSIST((list).tail == (elt)); \ 95290001Sglebius (list).tail = (elt)->link.prev; \ 96290001Sglebius } \ 97290001Sglebius if ((elt)->link.prev != NULL) \ 98290001Sglebius (elt)->link.prev->link.next = (elt)->link.next; \ 99290001Sglebius else { \ 100290001Sglebius ISC_INSIST((list).head == (elt)); \ 101290001Sglebius (list).head = (elt)->link.next; \ 102290001Sglebius } \ 103290001Sglebius (elt)->link.prev = (type *)(-1); \ 104290001Sglebius (elt)->link.next = (type *)(-1); \ 105290001Sglebius } while (0) 106290001Sglebius 107290001Sglebius#define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 108290001Sglebius __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 109290001Sglebius 110290001Sglebius#define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 111290001Sglebius do { \ 112290001Sglebius ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 113290001Sglebius __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 114290001Sglebius } while (0) 115290001Sglebius#define ISC_LIST_UNLINK(list, elt, link) \ 116290001Sglebius ISC_LIST_UNLINK_TYPE(list, elt, link, void) 117290001Sglebius 118290001Sglebius#define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 119290001Sglebius#define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 120290001Sglebius 121290001Sglebius#define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 122290001Sglebius do { \ 123290001Sglebius if ((before)->link.prev == NULL) \ 124290001Sglebius ISC_LIST_PREPEND(list, elt, link); \ 125290001Sglebius else { \ 126290001Sglebius (elt)->link.prev = (before)->link.prev; \ 127290001Sglebius (before)->link.prev = (elt); \ 128290001Sglebius (elt)->link.prev->link.next = (elt); \ 129290001Sglebius (elt)->link.next = (before); \ 130290001Sglebius } \ 131290001Sglebius } while (0) 132290001Sglebius 133290001Sglebius#define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 134290001Sglebius do { \ 135290001Sglebius ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 136290001Sglebius ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 137290001Sglebius __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 138290001Sglebius } while (0) 139290001Sglebius 140290001Sglebius#define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 141290001Sglebius do { \ 142290001Sglebius if ((after)->link.next == NULL) \ 143290001Sglebius ISC_LIST_APPEND(list, elt, link); \ 144290001Sglebius else { \ 145290001Sglebius (elt)->link.next = (after)->link.next; \ 146290001Sglebius (after)->link.next = (elt); \ 147290001Sglebius (elt)->link.next->link.prev = (elt); \ 148290001Sglebius (elt)->link.prev = (after); \ 149290001Sglebius } \ 150290001Sglebius } while (0) 151290001Sglebius 152290001Sglebius#define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 153290001Sglebius do { \ 154290001Sglebius ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 155290001Sglebius ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 156290001Sglebius __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 157290001Sglebius } while (0) 158290001Sglebius 159290001Sglebius#define ISC_LIST_APPENDLIST(list1, list2, link) \ 160290001Sglebius do { \ 161290001Sglebius if (ISC_LIST_EMPTY(list1)) \ 162290001Sglebius (list1) = (list2); \ 163290001Sglebius else if (!ISC_LIST_EMPTY(list2)) { \ 164290001Sglebius (list1).tail->link.next = (list2).head; \ 165290001Sglebius (list2).head->link.prev = (list1).tail; \ 166290001Sglebius (list1).tail = (list2).tail; \ 167290001Sglebius } \ 168290001Sglebius (list2).head = NULL; \ 169290001Sglebius (list2).tail = NULL; \ 170290001Sglebius } while (0) 171290001Sglebius 172290001Sglebius#define ISC_LIST_PREPENDLIST(list1, list2, link) \ 173290001Sglebius do { \ 174290001Sglebius if (ISC_LIST_EMPTY(list1)) \ 175290001Sglebius (list1) = (list2); \ 176290001Sglebius else if (!ISC_LIST_EMPTY(list2)) { \ 177290001Sglebius (list2).tail->link.next = (list1).head; \ 178290001Sglebius (list1).head->link.prev = (list2).tail; \ 179290001Sglebius (list1).head = (list2).head; \ 180290001Sglebius } \ 181290001Sglebius (list2).head = NULL; \ 182290001Sglebius (list2).tail = NULL; \ 183290001Sglebius } while (0) 184290001Sglebius 185290001Sglebius#define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 186290001Sglebius#define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 187290001Sglebius __ISC_LIST_APPENDUNSAFE(list, elt, link) 188290001Sglebius#define ISC_LIST_DEQUEUE(list, elt, link) \ 189290001Sglebius ISC_LIST_UNLINK_TYPE(list, elt, link, void) 190290001Sglebius#define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 191290001Sglebius ISC_LIST_UNLINK_TYPE(list, elt, link, type) 192290001Sglebius#define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 193290001Sglebius __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 194290001Sglebius#define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 195290001Sglebius __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 196290001Sglebius 197290001Sglebius#endif /* ISC_LIST_H */ 198