2 * Copyright (C) 2004, 2006, 2007, 2011, 2012 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1997-2002 Internet Software Consortium.
5 * Permission to use, copy, modify, and/or 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.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
22 #include <isc/boolean.h>
23 #include <isc/assertions.h>
25 #ifdef ISC_LIST_CHECKINIT
26 #define ISC_LINK_INSIST(x) ISC_INSIST(x)
28 #define ISC_LINK_INSIST(x)
31 #define ISC_LIST(type) struct { type *head, *tail; }
32 #define ISC_LIST_INIT(list) \
33 do { (list).head = NULL; (list).tail = NULL; } while (0)
35 #define ISC_LINK(type) struct { type *prev, *next; }
36 #define ISC_LINK_INIT_TYPE(elt, link, type) \
38 (elt)->link.prev = (type *)(-1); \
39 (elt)->link.next = (type *)(-1); \
41 #define ISC_LINK_INIT(elt, link) \
42 ISC_LINK_INIT_TYPE(elt, link, void)
43 #define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1))
45 #define ISC_LIST_HEAD(list) ((list).head)
46 #define ISC_LIST_TAIL(list) ((list).tail)
47 #define ISC_LIST_EMPTY(list) ISC_TF((list).head == NULL)
49 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \
51 if ((list).head != NULL) \
52 (list).head->link.prev = (elt); \
54 (list).tail = (elt); \
55 (elt)->link.prev = NULL; \
56 (elt)->link.next = (list).head; \
57 (list).head = (elt); \
60 #define ISC_LIST_PREPEND(list, elt, link) \
62 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \
63 __ISC_LIST_PREPENDUNSAFE(list, elt, link); \
66 #define ISC_LIST_INITANDPREPEND(list, elt, link) \
67 __ISC_LIST_PREPENDUNSAFE(list, elt, link)
69 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \
71 if ((list).tail != NULL) \
72 (list).tail->link.next = (elt); \
74 (list).head = (elt); \
75 (elt)->link.prev = (list).tail; \
76 (elt)->link.next = NULL; \
77 (list).tail = (elt); \
80 #define ISC_LIST_APPEND(list, elt, link) \
82 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \
83 __ISC_LIST_APPENDUNSAFE(list, elt, link); \
86 #define ISC_LIST_INITANDAPPEND(list, elt, link) \
87 __ISC_LIST_APPENDUNSAFE(list, elt, link)
89 #define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \
91 if ((elt)->link.next != NULL) \
92 (elt)->link.next->link.prev = (elt)->link.prev; \
94 ISC_INSIST((list).tail == (elt)); \
95 (list).tail = (elt)->link.prev; \
97 if ((elt)->link.prev != NULL) \
98 (elt)->link.prev->link.next = (elt)->link.next; \
100 ISC_INSIST((list).head == (elt)); \
101 (list).head = (elt)->link.next; \
103 (elt)->link.prev = (type *)(-1); \
104 (elt)->link.next = (type *)(-1); \
107 #define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \
108 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void)
110 #define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \
112 ISC_LINK_INSIST(ISC_LINK_LINKED(elt, link)); \
113 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \
115 #define ISC_LIST_UNLINK(list, elt, link) \
116 ISC_LIST_UNLINK_TYPE(list, elt, link, void)
118 #define ISC_LIST_PREV(elt, link) ((elt)->link.prev)
119 #define ISC_LIST_NEXT(elt, link) ((elt)->link.next)
121 #define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \
123 if ((before)->link.prev == NULL) \
124 ISC_LIST_PREPEND(list, elt, link); \
126 (elt)->link.prev = (before)->link.prev; \
127 (before)->link.prev = (elt); \
128 (elt)->link.prev->link.next = (elt); \
129 (elt)->link.next = (before); \
133 #define ISC_LIST_INSERTBEFORE(list, before, elt, link) \
135 ISC_LINK_INSIST(ISC_LINK_LINKED(before, link)); \
136 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \
137 __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \
140 #define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \
142 if ((after)->link.next == NULL) \
143 ISC_LIST_APPEND(list, elt, link); \
145 (elt)->link.next = (after)->link.next; \
146 (after)->link.next = (elt); \
147 (elt)->link.next->link.prev = (elt); \
148 (elt)->link.prev = (after); \
152 #define ISC_LIST_INSERTAFTER(list, after, elt, link) \
154 ISC_LINK_INSIST(ISC_LINK_LINKED(after, link)); \
155 ISC_LINK_INSIST(!ISC_LINK_LINKED(elt, link)); \
156 __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \
159 #define ISC_LIST_APPENDLIST(list1, list2, link) \
161 if (ISC_LIST_EMPTY(list1)) \
163 else if (!ISC_LIST_EMPTY(list2)) { \
164 (list1).tail->link.next = (list2).head; \
165 (list2).head->link.prev = (list1).tail; \
166 (list1).tail = (list2).tail; \
168 (list2).head = NULL; \
169 (list2).tail = NULL; \
172 #define ISC_LIST_PREPENDLIST(list1, list2, link) \
174 if (ISC_LIST_EMPTY(list1)) \
176 else if (!ISC_LIST_EMPTY(list2)) { \
177 (list2).tail->link.next = (list1).head; \
178 (list1).head->link.prev = (list2).tail; \
179 (list1).head = (list2).head; \
181 (list2).head = NULL; \
182 (list2).tail = NULL; \
185 #define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link)
186 #define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \
187 __ISC_LIST_APPENDUNSAFE(list, elt, link)
188 #define ISC_LIST_DEQUEUE(list, elt, link) \
189 ISC_LIST_UNLINK_TYPE(list, elt, link, void)
190 #define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \
191 ISC_LIST_UNLINK_TYPE(list, elt, link, type)
192 #define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \
193 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void)
194 #define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \
195 __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type)
197 #endif /* ISC_LIST_H */