1135446Strhodes/* 2254897Serwin * Copyright (C) 2004, 2006, 2007, 2011-2013 Internet Systems Consortium, Inc. ("ISC") 3135446Strhodes * Copyright (C) 1997-2002 Internet Software Consortium. 4135446Strhodes * 5193149Sdougb * Permission to use, copy, modify, and/or distribute this software for any 6135446Strhodes * purpose with or without fee is hereby granted, provided that the above 7135446Strhodes * copyright notice and this permission notice appear in all copies. 8135446Strhodes * 9135446Strhodes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10135446Strhodes * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11135446Strhodes * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12135446Strhodes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13135446Strhodes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14135446Strhodes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15135446Strhodes * PERFORMANCE OF THIS SOFTWARE. 16135446Strhodes */ 17135446Strhodes 18234010Sdougb/* $Id$ */ 19135446Strhodes 20135446Strhodes#ifndef ISC_LIST_H 21135446Strhodes#define ISC_LIST_H 1 22135446Strhodes#include <isc/boolean.h> 23135446Strhodes#include <isc/assertions.h> 24135446Strhodes 25135446Strhodes#ifdef ISC_LIST_CHECKINIT 26135446Strhodes#define ISC_LINK_INSIST(x) ISC_INSIST(x) 27135446Strhodes#else 28135446Strhodes#define ISC_LINK_INSIST(x) 29135446Strhodes#endif 30135446Strhodes 31135446Strhodes#define ISC_LIST(type) struct { type *head, *tail; } 32135446Strhodes#define ISC_LIST_INIT(list) \ 33135446Strhodes do { (list).head = NULL; (list).tail = NULL; } while (0) 34135446Strhodes 35135446Strhodes#define ISC_LINK(type) struct { type *prev, *next; } 36135446Strhodes#define ISC_LINK_INIT_TYPE(elt, link, type) \ 37135446Strhodes do { \ 38135446Strhodes (elt)->link.prev = (type *)(-1); \ 39135446Strhodes (elt)->link.next = (type *)(-1); \ 40135446Strhodes } while (0) 41135446Strhodes#define ISC_LINK_INIT(elt, link) \ 42135446Strhodes ISC_LINK_INIT_TYPE(elt, link, void) 43135446Strhodes#define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 44135446Strhodes 45135446Strhodes#define ISC_LIST_HEAD(list) ((list).head) 46135446Strhodes#define ISC_LIST_TAIL(list) ((list).tail) 47135446Strhodes#define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL) 48135446Strhodes 49135446Strhodes#define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 50135446Strhodes do { \ 51135446Strhodes if ((list).head != NULL) \ 52135446Strhodes (list).head->link.prev = (elt); \ 53135446Strhodes else \ 54135446Strhodes (list).tail = (elt); \ 55135446Strhodes (elt)->link.prev = NULL; \ 56135446Strhodes (elt)->link.next = (list).head; \ 57135446Strhodes (list).head = (elt); \ 58135446Strhodes } while (0) 59135446Strhodes 60135446Strhodes#define ISC_LIST_PREPEND(list, elt, link) \ 61135446Strhodes do { \ 62135446Strhodes ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 63135446Strhodes __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 64135446Strhodes } while (0) 65135446Strhodes 66135446Strhodes#define ISC_LIST_INITANDPREPEND(list, elt, link) \ 67135446Strhodes __ISC_LIST_PREPENDUNSAFE(list, elt, link) 68135446Strhodes 69135446Strhodes#define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 70135446Strhodes do { \ 71135446Strhodes if ((list).tail != NULL) \ 72135446Strhodes (list).tail->link.next = (elt); \ 73135446Strhodes else \ 74135446Strhodes (list).head = (elt); \ 75135446Strhodes (elt)->link.prev = (list).tail; \ 76135446Strhodes (elt)->link.next = NULL; \ 77135446Strhodes (list).tail = (elt); \ 78135446Strhodes } while (0) 79135446Strhodes 80135446Strhodes#define ISC_LIST_APPEND(list, elt, link) \ 81135446Strhodes do { \ 82135446Strhodes ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 83135446Strhodes __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 84135446Strhodes } while (0) 85135446Strhodes 86135446Strhodes#define ISC_LIST_INITANDAPPEND(list, elt, link) \ 87135446Strhodes __ISC_LIST_APPENDUNSAFE(list, elt, link) 88135446Strhodes 89135446Strhodes#define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 90135446Strhodes do { \ 91135446Strhodes if ((elt)->link.next != NULL) \ 92135446Strhodes (elt)->link.next->link.prev = (elt)->link.prev; \ 93165071Sdougb else { \ 94165071Sdougb ISC_INSIST((list).tail == (elt)); \ 95135446Strhodes (list).tail = (elt)->link.prev; \ 96165071Sdougb } \ 97135446Strhodes if ((elt)->link.prev != NULL) \ 98135446Strhodes (elt)->link.prev->link.next = (elt)->link.next; \ 99165071Sdougb else { \ 100165071Sdougb ISC_INSIST((list).head == (elt)); \ 101135446Strhodes (list).head = (elt)->link.next; \ 102165071Sdougb } \ 103135446Strhodes (elt)->link.prev = (type *)(-1); \ 104135446Strhodes (elt)->link.next = (type *)(-1); \ 105254402Serwin ISC_INSIST((list).head != (elt)); \ 106254402Serwin ISC_INSIST((list).tail != (elt)); \ 107135446Strhodes } while (0) 108135446Strhodes 109135446Strhodes#define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 110135446Strhodes __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 111135446Strhodes 112135446Strhodes#define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 113135446Strhodes do { \ 114135446Strhodes ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 115135446Strhodes __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 116135446Strhodes } while (0) 117135446Strhodes#define ISC_LIST_UNLINK(list, elt, link) \ 118135446Strhodes ISC_LIST_UNLINK_TYPE(list, elt, link, void) 119135446Strhodes 120135446Strhodes#define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 121135446Strhodes#define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 122135446Strhodes 123135446Strhodes#define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 124135446Strhodes do { \ 125135446Strhodes if ((before)->link.prev == NULL) \ 126135446Strhodes ISC_LIST_PREPEND(list, elt, link); \ 127135446Strhodes else { \ 128135446Strhodes (elt)->link.prev = (before)->link.prev; \ 129135446Strhodes (before)->link.prev = (elt); \ 130135446Strhodes (elt)->link.prev->link.next = (elt); \ 131135446Strhodes (elt)->link.next = (before); \ 132135446Strhodes } \ 133135446Strhodes } while (0) 134135446Strhodes 135135446Strhodes#define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 136135446Strhodes do { \ 137135446Strhodes ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 138135446Strhodes ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 139135446Strhodes __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 140135446Strhodes } while (0) 141135446Strhodes 142135446Strhodes#define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 143135446Strhodes do { \ 144135446Strhodes if ((after)->link.next == NULL) \ 145135446Strhodes ISC_LIST_APPEND(list, elt, link); \ 146135446Strhodes else { \ 147135446Strhodes (elt)->link.next = (after)->link.next; \ 148135446Strhodes (after)->link.next = (elt); \ 149135446Strhodes (elt)->link.next->link.prev = (elt); \ 150135446Strhodes (elt)->link.prev = (after); \ 151135446Strhodes } \ 152135446Strhodes } while (0) 153135446Strhodes 154135446Strhodes#define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 155135446Strhodes do { \ 156135446Strhodes ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 157135446Strhodes ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 158135446Strhodes __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 159135446Strhodes } while (0) 160135446Strhodes 161135446Strhodes#define ISC_LIST_APPENDLIST(list1, list2, link) \ 162135446Strhodes do { \ 163135446Strhodes if (ISC_LIST_EMPTY(list1)) \ 164135446Strhodes (list1) = (list2); \ 165135446Strhodes else if (!ISC_LIST_EMPTY(list2)) { \ 166135446Strhodes (list1).tail->link.next = (list2).head; \ 167135446Strhodes (list2).head->link.prev = (list1).tail; \ 168135446Strhodes (list1).tail = (list2).tail; \ 169135446Strhodes } \ 170135446Strhodes (list2).head = NULL; \ 171135446Strhodes (list2).tail = NULL; \ 172135446Strhodes } while (0) 173135446Strhodes 174254897Serwin#define ISC_LIST_PREPENDLIST(list1, list2, link) \ 175254897Serwin do { \ 176254897Serwin if (ISC_LIST_EMPTY(list1)) \ 177254897Serwin (list1) = (list2); \ 178254897Serwin else if (!ISC_LIST_EMPTY(list2)) { \ 179254897Serwin (list2).tail->link.next = (list1).head; \ 180254897Serwin (list1).head->link.prev = (list2).tail; \ 181254897Serwin (list1).head = (list2).head; \ 182254897Serwin } \ 183254897Serwin (list2).head = NULL; \ 184254897Serwin (list2).tail = NULL; \ 185254897Serwin } while (0) 186254897Serwin 187135446Strhodes#define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 188135446Strhodes#define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 189135446Strhodes __ISC_LIST_APPENDUNSAFE(list, elt, link) 190135446Strhodes#define ISC_LIST_DEQUEUE(list, elt, link) \ 191135446Strhodes ISC_LIST_UNLINK_TYPE(list, elt, link, void) 192135446Strhodes#define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 193135446Strhodes ISC_LIST_UNLINK_TYPE(list, elt, link, type) 194135446Strhodes#define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 195135446Strhodes __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 196135446Strhodes#define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 197135446Strhodes __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 198135446Strhodes 199135446Strhodes#endif /* ISC_LIST_H */ 200