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 #ifndef LIST_H 19 #define LIST_H 1 20 #include <isc/assertions.h> 21 22 #define LIST(type) struct { type *head, *tail; } 23 #define INIT_LIST(list) \ 24 do { (list).head = NULL; (list).tail = NULL; } while (0) 25 26 #define LINK(type) struct { type *prev, *next; } 27 #define INIT_LINK_TYPE(elt, link, type) \ 28 do { \ 29 (elt)->link.prev = (type *)(-1); \ 30 (elt)->link.next = (type *)(-1); \ 31 } while (0) 32 #define INIT_LINK(elt, link) \ 33 INIT_LINK_TYPE(elt, link, void) 34 #define LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1) && \ 35 (void *)((elt)->link.next) != (void *)(-1)) 36 37 #define HEAD(list) ((list).head) 38 #define TAIL(list) ((list).tail) 39 #define EMPTY(list) ((list).head == NULL) 40 41 #define PREPEND(list, elt, link) \ 42 do { \ 43 INSIST(!LINKED(elt, link));\ 44 if ((list).head != NULL) \ 45 (list).head->link.prev = (elt); \ 46 else \ 47 (list).tail = (elt); \ 48 (elt)->link.prev = NULL; \ 49 (elt)->link.next = (list).head; \ 50 (list).head = (elt); \ 51 } while (0) 52 53 #define APPEND(list, elt, link) \ 54 do { \ 55 INSIST(!LINKED(elt, link));\ 56 if ((list).tail != NULL) \ 57 (list).tail->link.next = (elt); \ 58 else \ 59 (list).head = (elt); \ 60 (elt)->link.prev = (list).tail; \ 61 (elt)->link.next = NULL; \ 62 (list).tail = (elt); \ 63 } while (0) 64 65 #define UNLINK_TYPE(list, elt, link, type) \ 66 do { \ 67 INSIST(LINKED(elt, link));\ 68 if ((elt)->link.next != NULL) \ 69 (elt)->link.next->link.prev = (elt)->link.prev; \ 70 else { \ 71 INSIST((list).tail == (elt)); \ 72 (list).tail = (elt)->link.prev; \ 73 } \ 74 if ((elt)->link.prev != NULL) \ 75 (elt)->link.prev->link.next = (elt)->link.next; \ 76 else { \ 77 INSIST((list).head == (elt)); \ 78 (list).head = (elt)->link.next; \ 79 } \ 80 INIT_LINK_TYPE(elt, link, type); \ 81 } while (0) 82 #define UNLINK(list, elt, link) \ 83 UNLINK_TYPE(list, elt, link, void) 84 85 #define PREV(elt, link) ((elt)->link.prev) 86 #define NEXT(elt, link) ((elt)->link.next) 87 88 #define INSERT_BEFORE(list, before, elt, link) \ 89 do { \ 90 INSIST(!LINKED(elt, link));\ 91 if ((before)->link.prev == NULL) \ 92 PREPEND(list, elt, link); \ 93 else { \ 94 (elt)->link.prev = (before)->link.prev; \ 95 (before)->link.prev = (elt); \ 96 (elt)->link.prev->link.next = (elt); \ 97 (elt)->link.next = (before); \ 98 } \ 99 } while (0) 100 101 #define INSERT_AFTER(list, after, elt, link) \ 102 do { \ 103 INSIST(!LINKED(elt, link));\ 104 if ((after)->link.next == NULL) \ 105 APPEND(list, elt, link); \ 106 else { \ 107 (elt)->link.next = (after)->link.next; \ 108 (after)->link.next = (elt); \ 109 (elt)->link.next->link.prev = (elt); \ 110 (elt)->link.prev = (after); \ 111 } \ 112 } while (0) 113 114 #define ENQUEUE(list, elt, link) APPEND(list, elt, link) 115 #define DEQUEUE(list, elt, link) UNLINK(list, elt, link) 116 117 #endif /* LIST_H */ 118 /*! \file */ 119