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 (void *)((elt)->link.next) != (void *)(-1)) 43 44 #define HEAD(list) ((list).head) 45 #define TAIL(list) ((list).tail) 46 #define EMPTY(list) ((list).head == NULL) 47 48 #define PREPEND(list, elt, link) \ 49 do { \ 50 INSIST(!LINKED(elt, link));\ 51 if ((list).head != NULL) \ 52 (list).head->link.prev = (elt); \ 53 else \ 54 (list).tail = (elt); \ 55 (elt)->link.prev = NULL; \ 56 (elt)->link.next = (list).head; \ 57 (list).head = (elt); \ 58 } while (0) 59 60 #define APPEND(list, elt, link) \ 61 do { \ 62 INSIST(!LINKED(elt, link));\ 63 if ((list).tail != NULL) \ 64 (list).tail->link.next = (elt); \ 65 else \ 66 (list).head = (elt); \ 67 (elt)->link.prev = (list).tail; \ 68 (elt)->link.next = NULL; \ 69 (list).tail = (elt); \ 70 } while (0) 71 72 #define UNLINK_TYPE(list, elt, link, type) \ 73 do { \ 74 INSIST(LINKED(elt, link));\ 75 if ((elt)->link.next != NULL) \ 76 (elt)->link.next->link.prev = (elt)->link.prev; \ 77 else { \ 78 INSIST((list).tail == (elt)); \ 79 (list).tail = (elt)->link.prev; \ 80 } \ 81 if ((elt)->link.prev != NULL) \ 82 (elt)->link.prev->link.next = (elt)->link.next; \ 83 else { \ 84 INSIST((list).head == (elt)); \ 85 (list).head = (elt)->link.next; \ 86 } \ 87 INIT_LINK_TYPE(elt, link, type); \ 88 } while (0) 89 #define UNLINK(list, elt, link) \ 90 UNLINK_TYPE(list, elt, link, void) 91 92 #define PREV(elt, link) ((elt)->link.prev) 93 #define NEXT(elt, link) ((elt)->link.next) 94 95 #define INSERT_BEFORE(list, before, elt, link) \ 96 do { \ 97 INSIST(!LINKED(elt, link));\ 98 if ((before)->link.prev == NULL) \ 99 PREPEND(list, elt, link); \ 100 else { \ 101 (elt)->link.prev = (before)->link.prev; \ 102 (before)->link.prev = (elt); \ 103 (elt)->link.prev->link.next = (elt); \ 104 (elt)->link.next = (before); \ 105 } \ 106 } while (0) 107 108 #define INSERT_AFTER(list, after, elt, link) \ 109 do { \ 110 INSIST(!LINKED(elt, link));\ 111 if ((after)->link.next == NULL) \ 112 APPEND(list, elt, link); \ 113 else { \ 114 (elt)->link.next = (after)->link.next; \ 115 (after)->link.next = (elt); \ 116 (elt)->link.next->link.prev = (elt); \ 117 (elt)->link.prev = (after); \ 118 } \ 119 } while (0) 120 121 #define ENQUEUE(list, elt, link) APPEND(list, elt, link) 122 #define DEQUEUE(list, elt, link) UNLINK(list, elt, link) 123 124 #endif /* LIST_H */ 125 /*! \file */ 126