1258945Sroberto/* 2280849Scy * Copyright (C) 2004, 2006, 2007, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 3258945Sroberto * Copyright (C) 1997-2002 Internet Software Consortium. 4258945Sroberto * 5258945Sroberto * Permission to use, copy, modify, and/or distribute this software for any 6258945Sroberto * purpose with or without fee is hereby granted, provided that the above 7258945Sroberto * copyright notice and this permission notice appear in all copies. 8258945Sroberto * 9258945Sroberto * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10258945Sroberto * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11258945Sroberto * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12258945Sroberto * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13258945Sroberto * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14258945Sroberto * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15258945Sroberto * PERFORMANCE OF THIS SOFTWARE. 16258945Sroberto */ 17258945Sroberto 18280849Scy/* $Id$ */ 19258945Sroberto 20258945Sroberto#ifndef ISC_LIST_H 21258945Sroberto#define ISC_LIST_H 1 22258945Sroberto#include <isc/boolean.h> 23258945Sroberto#include <isc/assertions.h> 24258945Sroberto 25258945Sroberto#ifdef ISC_LIST_CHECKINIT 26258945Sroberto#define ISC_LINK_INSIST(x) ISC_INSIST(x) 27258945Sroberto#else 28258945Sroberto#define ISC_LINK_INSIST(x) 29258945Sroberto#endif 30258945Sroberto 31258945Sroberto#define ISC_LIST(type) struct { type *head, *tail; } 32258945Sroberto#define ISC_LIST_INIT(list) \ 33258945Sroberto do { (list).head = NULL; (list).tail = NULL; } while (0) 34258945Sroberto 35258945Sroberto#define ISC_LINK(type) struct { type *prev, *next; } 36258945Sroberto#define ISC_LINK_INIT_TYPE(elt, link, type) \ 37258945Sroberto do { \ 38258945Sroberto (elt)->link.prev = (type *)(-1); \ 39258945Sroberto (elt)->link.next = (type *)(-1); \ 40258945Sroberto } while (0) 41258945Sroberto#define ISC_LINK_INIT(elt, link) \ 42258945Sroberto ISC_LINK_INIT_TYPE(elt, link, void) 43258945Sroberto#define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 44258945Sroberto 45258945Sroberto#define ISC_LIST_HEAD(list) ((list).head) 46258945Sroberto#define ISC_LIST_TAIL(list) ((list).tail) 47258945Sroberto#define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL) 48258945Sroberto 49258945Sroberto#define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \ 50258945Sroberto do { \ 51258945Sroberto if ((list).head != NULL) \ 52258945Sroberto (list).head->link.prev = (elt); \ 53258945Sroberto else \ 54258945Sroberto (list).tail = (elt); \ 55258945Sroberto (elt)->link.prev = NULL; \ 56258945Sroberto (elt)->link.next = (list).head; \ 57258945Sroberto (list).head = (elt); \ 58258945Sroberto } while (0) 59258945Sroberto 60258945Sroberto#define ISC_LIST_PREPEND(list, elt, link) \ 61258945Sroberto do { \ 62258945Sroberto ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 63258945Sroberto __ISC_LIST_PREPENDUNSAFE(list, elt, link); \ 64258945Sroberto } while (0) 65258945Sroberto 66258945Sroberto#define ISC_LIST_INITANDPREPEND(list, elt, link) \ 67258945Sroberto __ISC_LIST_PREPENDUNSAFE(list, elt, link) 68258945Sroberto 69258945Sroberto#define __ISC_LIST_APPENDUNSAFE(list, elt, link) \ 70258945Sroberto do { \ 71258945Sroberto if ((list).tail != NULL) \ 72258945Sroberto (list).tail->link.next = (elt); \ 73258945Sroberto else \ 74258945Sroberto (list).head = (elt); \ 75258945Sroberto (elt)->link.prev = (list).tail; \ 76258945Sroberto (elt)->link.next = NULL; \ 77258945Sroberto (list).tail = (elt); \ 78258945Sroberto } while (0) 79258945Sroberto 80258945Sroberto#define ISC_LIST_APPEND(list, elt, link) \ 81258945Sroberto do { \ 82258945Sroberto ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 83258945Sroberto __ISC_LIST_APPENDUNSAFE(list, elt, link); \ 84258945Sroberto } while (0) 85258945Sroberto 86258945Sroberto#define ISC_LIST_INITANDAPPEND(list, elt, link) \ 87258945Sroberto __ISC_LIST_APPENDUNSAFE(list, elt, link) 88258945Sroberto 89258945Sroberto#define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \ 90258945Sroberto do { \ 91258945Sroberto if ((elt)->link.next != NULL) \ 92258945Sroberto (elt)->link.next->link.prev = (elt)->link.prev; \ 93258945Sroberto else { \ 94258945Sroberto ISC_INSIST((list).tail == (elt)); \ 95258945Sroberto (list).tail = (elt)->link.prev; \ 96258945Sroberto } \ 97258945Sroberto if ((elt)->link.prev != NULL) \ 98258945Sroberto (elt)->link.prev->link.next = (elt)->link.next; \ 99258945Sroberto else { \ 100258945Sroberto ISC_INSIST((list).head == (elt)); \ 101258945Sroberto (list).head = (elt)->link.next; \ 102258945Sroberto } \ 103258945Sroberto (elt)->link.prev = (type *)(-1); \ 104258945Sroberto (elt)->link.next = (type *)(-1); \ 105258945Sroberto } while (0) 106258945Sroberto 107258945Sroberto#define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \ 108258945Sroberto __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 109258945Sroberto 110258945Sroberto#define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \ 111258945Sroberto do { \ 112258945Sroberto ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \ 113258945Sroberto __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \ 114258945Sroberto } while (0) 115258945Sroberto#define ISC_LIST_UNLINK(list, elt, link) \ 116258945Sroberto ISC_LIST_UNLINK_TYPE(list, elt, link, void) 117258945Sroberto 118258945Sroberto#define ISC_LIST_PREV(elt, link) ((elt)->link.prev) 119258945Sroberto#define ISC_LIST_NEXT(elt, link) ((elt)->link.next) 120258945Sroberto 121258945Sroberto#define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \ 122258945Sroberto do { \ 123258945Sroberto if ((before)->link.prev == NULL) \ 124258945Sroberto ISC_LIST_PREPEND(list, elt, link); \ 125258945Sroberto else { \ 126258945Sroberto (elt)->link.prev = (before)->link.prev; \ 127258945Sroberto (before)->link.prev = (elt); \ 128258945Sroberto (elt)->link.prev->link.next = (elt); \ 129258945Sroberto (elt)->link.next = (before); \ 130258945Sroberto } \ 131258945Sroberto } while (0) 132258945Sroberto 133258945Sroberto#define ISC_LIST_INSERTBEFORE(list, before, elt, link) \ 134258945Sroberto do { \ 135258945Sroberto ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \ 136258945Sroberto ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 137258945Sroberto __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \ 138258945Sroberto } while (0) 139258945Sroberto 140258945Sroberto#define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \ 141258945Sroberto do { \ 142258945Sroberto if ((after)->link.next == NULL) \ 143258945Sroberto ISC_LIST_APPEND(list, elt, link); \ 144258945Sroberto else { \ 145258945Sroberto (elt)->link.next = (after)->link.next; \ 146258945Sroberto (after)->link.next = (elt); \ 147258945Sroberto (elt)->link.next->link.prev = (elt); \ 148258945Sroberto (elt)->link.prev = (after); \ 149258945Sroberto } \ 150258945Sroberto } while (0) 151258945Sroberto 152258945Sroberto#define ISC_LIST_INSERTAFTER(list, after, elt, link) \ 153258945Sroberto do { \ 154258945Sroberto ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \ 155258945Sroberto ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \ 156258945Sroberto __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \ 157258945Sroberto } while (0) 158258945Sroberto 159258945Sroberto#define ISC_LIST_APPENDLIST(list1, list2, link) \ 160258945Sroberto do { \ 161258945Sroberto if (ISC_LIST_EMPTY(list1)) \ 162258945Sroberto (list1) = (list2); \ 163258945Sroberto else if (!ISC_LIST_EMPTY(list2)) { \ 164258945Sroberto (list1).tail->link.next = (list2).head; \ 165258945Sroberto (list2).head->link.prev = (list1).tail; \ 166258945Sroberto (list1).tail = (list2).tail; \ 167258945Sroberto } \ 168258945Sroberto (list2).head = NULL; \ 169258945Sroberto (list2).tail = NULL; \ 170258945Sroberto } while (0) 171258945Sroberto 172280849Scy#define ISC_LIST_PREPENDLIST(list1, list2, link) \ 173280849Scy do { \ 174280849Scy if (ISC_LIST_EMPTY(list1)) \ 175280849Scy (list1) = (list2); \ 176280849Scy else if (!ISC_LIST_EMPTY(list2)) { \ 177280849Scy (list2).tail->link.next = (list1).head; \ 178280849Scy (list1).head->link.prev = (list2).tail; \ 179280849Scy (list1).head = (list2).head; \ 180280849Scy } \ 181280849Scy (list2).head = NULL; \ 182280849Scy (list2).tail = NULL; \ 183280849Scy } while (0) 184280849Scy 185258945Sroberto#define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link) 186258945Sroberto#define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \ 187258945Sroberto __ISC_LIST_APPENDUNSAFE(list, elt, link) 188258945Sroberto#define ISC_LIST_DEQUEUE(list, elt, link) \ 189258945Sroberto ISC_LIST_UNLINK_TYPE(list, elt, link, void) 190258945Sroberto#define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \ 191258945Sroberto ISC_LIST_UNLINK_TYPE(list, elt, link, type) 192258945Sroberto#define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \ 193258945Sroberto __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void) 194258945Sroberto#define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \ 195258945Sroberto __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) 196258945Sroberto 197258945Sroberto#endif /* ISC_LIST_H */ 198