1 /* 2 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") 3 * Copyright (c) 1997,1999 by Internet Software Consortium. 4 * 5 * Permission to use, copy, modify, and 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 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 15 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 /* $FreeBSD$ */ 19 20 #ifndef LIST_H 21 #define LIST_H 1 22 #ifdef _LIBC 23 #include <assert.h> 24 #define INSIST(cond) assert(cond) 25 #else 26 #include <isc/assertions.h> 27 #endif 28 29 #define LIST(type) struct { type *head, *tail; } 30 #define INIT_LIST(list) \ 31 do { (list).head = NULL; (list).tail = NULL; } while (0) 32 33 #define LINK(type) struct { type *prev, *next; } 34 #define INIT_LINK_TYPE(elt, link, type) \ 35 do { \ 36 (elt)->link.prev = (type *)(-1); \ 37 (elt)->link.next = (type *)(-1); \ 38 } while (0) 39 #define INIT_LINK(elt, link) \ 40 INIT_LINK_TYPE(elt, link, void) 41 #define LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1)) 42 43 #define HEAD(list) ((list).head) 44 #define TAIL(list) ((list).tail) 45 #define EMPTY(list) ((list).head == NULL) 46 47 #define PREPEND(list, elt, link) \ 48 do { \ 49 INSIST(!LINKED(elt, link));\ 50 if ((list).head != NULL) \ 51 (list).head->link.prev = (elt); \ 52 else \ 53 (list).tail = (elt); \ 54 (elt)->link.prev = NULL; \ 55 (elt)->link.next = (list).head; \ 56 (list).head = (elt); \ 57 } while (0) 58 59 #define APPEND(list, elt, link) \ 60 do { \ 61 INSIST(!LINKED(elt, link));\ 62 if ((list).tail != NULL) \ 63 (list).tail->link.next = (elt); \ 64 else \ 65 (list).head = (elt); \ 66 (elt)->link.prev = (list).tail; \ 67 (elt)->link.next = NULL; \ 68 (list).tail = (elt); \ 69 } while (0) 70 71 #define UNLINK_TYPE(list, elt, link, type) \ 72 do { \ 73 INSIST(LINKED(elt, link));\ 74 if ((elt)->link.next != NULL) \ 75 (elt)->link.next->link.prev = (elt)->link.prev; \ 76 else { \ 77 INSIST((list).tail == (elt)); \ 78 (list).tail = (elt)->link.prev; \ 79 } \ 80 if ((elt)->link.prev != NULL) \ 81 (elt)->link.prev->link.next = (elt)->link.next; \ 82 else { \ 83 INSIST((list).head == (elt)); \ 84 (list).head = (elt)->link.next; \ 85 } \ 86 INIT_LINK_TYPE(elt, link, type); \ 87 } while (0) 88 #define UNLINK(list, elt, link) \ 89 UNLINK_TYPE(list, elt, link, void) 90 91 #define PREV(elt, link) ((elt)->link.prev) 92 #define NEXT(elt, link) ((elt)->link.next) 93 94 #define INSERT_BEFORE(list, before, elt, link) \ 95 do { \ 96 INSIST(!LINKED(elt, link));\ 97 if ((before)->link.prev == NULL) \ 98 PREPEND(list, elt, link); \ 99 else { \ 100 (elt)->link.prev = (before)->link.prev; \ 101 (before)->link.prev = (elt); \ 102 (elt)->link.prev->link.next = (elt); \ 103 (elt)->link.next = (before); \ 104 } \ 105 } while (0) 106 107 #define INSERT_AFTER(list, after, elt, link) \ 108 do { \ 109 INSIST(!LINKED(elt, link));\ 110 if ((after)->link.next == NULL) \ 111 APPEND(list, elt, link); \ 112 else { \ 113 (elt)->link.next = (after)->link.next; \ 114 (after)->link.next = (elt); \ 115 (elt)->link.next->link.prev = (elt); \ 116 (elt)->link.prev = (after); \ 117 } \ 118 } while (0) 119 120 #define ENQUEUE(list, elt, link) APPEND(list, elt, link) 121 #define DEQUEUE(list, elt, link) UNLINK(list, elt, link) 122 123 #endif /* LIST_H */ 124 /*! \file */ 125