xref: /openbsd/usr.bin/dig/lib/isc/include/isc/list.h (revision 1fb015a8)
1 /*
2  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3  *
4  * Permission to use, copy, modify, and/or distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14  * PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 /* $Id: list.h,v 1.3 2020/09/14 08:40:44 florian Exp $ */
18 
19 #ifndef ISC_LIST_H
20 #define ISC_LIST_H 1
21 #include <isc/assertions.h>
22 
23 #define ISC_LIST(type) struct { type *head, *tail; }
24 #define ISC_LIST_INIT(list) \
25 	do { (list).head = NULL; (list).tail = NULL; } while (0)
26 
27 #define ISC_LINK(type) struct { type *prev, *next; }
28 #define ISC_LINK_INIT_TYPE(elt, link, type) \
29 	do { \
30 		(elt)->link.prev = (type *)(-1); \
31 		(elt)->link.next = (type *)(-1); \
32 	} while (0)
33 #define ISC_LINK_INIT(elt, link) \
34 	ISC_LINK_INIT_TYPE(elt, link, void)
35 #define ISC_LINK_LINKED(elt, link) ((void *)((elt)->link.prev) != (void *)(-1))
36 
37 #define ISC_LIST_HEAD(list) ((list).head)
38 #define ISC_LIST_TAIL(list) ((list).tail)
39 #define ISC_LIST_EMPTY(list) ((list).head == NULL)
40 
41 #define __ISC_LIST_PREPENDUNSAFE(list, elt, link) \
42 	do { \
43 		if ((list).head != NULL) \
44 			(list).head->link.prev = (elt); \
45 		else \
46 			(list).tail = (elt); \
47 		(elt)->link.prev = NULL; \
48 		(elt)->link.next = (list).head; \
49 		(list).head = (elt); \
50 	} while (0)
51 
52 #define ISC_LIST_PREPEND(list, elt, link) \
53 	do { \
54 		__ISC_LIST_PREPENDUNSAFE(list, elt, link); \
55 	} while (0)
56 
57 #define ISC_LIST_INITANDPREPEND(list, elt, link) \
58 		__ISC_LIST_PREPENDUNSAFE(list, elt, link)
59 
60 #define __ISC_LIST_APPENDUNSAFE(list, elt, link) \
61 	do { \
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 ISC_LIST_APPEND(list, elt, link) \
72 	do { \
73 		__ISC_LIST_APPENDUNSAFE(list, elt, link); \
74 	} while (0)
75 
76 #define ISC_LIST_INITANDAPPEND(list, elt, link) \
77 		__ISC_LIST_APPENDUNSAFE(list, elt, link)
78 
79 #define __ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type) \
80 	do { \
81 		if ((elt)->link.next != NULL) \
82 			(elt)->link.next->link.prev = (elt)->link.prev; \
83 		else { \
84 			ISC_INSIST((list).tail == (elt)); \
85 			(list).tail = (elt)->link.prev; \
86 		} \
87 		if ((elt)->link.prev != NULL) \
88 			(elt)->link.prev->link.next = (elt)->link.next; \
89 		else { \
90 			ISC_INSIST((list).head == (elt)); \
91 			(list).head = (elt)->link.next; \
92 		} \
93 		(elt)->link.prev = (type *)(-1); \
94 		(elt)->link.next = (type *)(-1); \
95 		ISC_INSIST((list).head != (elt)); \
96 		ISC_INSIST((list).tail != (elt)); \
97 	} while (0)
98 
99 #define __ISC_LIST_UNLINKUNSAFE(list, elt, link) \
100 	__ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void)
101 
102 #define ISC_LIST_UNLINK_TYPE(list, elt, link, type) \
103 	do { \
104 		__ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type); \
105 	} while (0)
106 #define ISC_LIST_UNLINK(list, elt, link) \
107 	ISC_LIST_UNLINK_TYPE(list, elt, link, void)
108 
109 #define ISC_LIST_PREV(elt, link) ((elt)->link.prev)
110 #define ISC_LIST_NEXT(elt, link) ((elt)->link.next)
111 
112 #define __ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link) \
113 	do { \
114 		if ((before)->link.prev == NULL) \
115 			ISC_LIST_PREPEND(list, elt, link); \
116 		else { \
117 			(elt)->link.prev = (before)->link.prev; \
118 			(before)->link.prev = (elt); \
119 			(elt)->link.prev->link.next = (elt); \
120 			(elt)->link.next = (before); \
121 		} \
122 	} while (0)
123 
124 #define ISC_LIST_INSERTBEFORE(list, before, elt, link) \
125 	do { \
126 		__ISC_LIST_INSERTBEFOREUNSAFE(list, before, elt, link); \
127 	} while (0)
128 
129 #define __ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link) \
130 	do { \
131 		if ((after)->link.next == NULL) \
132 			ISC_LIST_APPEND(list, elt, link); \
133 		else { \
134 			(elt)->link.next = (after)->link.next; \
135 			(after)->link.next = (elt); \
136 			(elt)->link.next->link.prev = (elt); \
137 			(elt)->link.prev = (after); \
138 		} \
139 	} while (0)
140 
141 #define ISC_LIST_INSERTAFTER(list, after, elt, link) \
142 	do { \
143 		__ISC_LIST_INSERTAFTERUNSAFE(list, after, elt, link); \
144 	} while (0)
145 
146 #define ISC_LIST_APPENDLIST(list1, list2, link) \
147 	do { \
148 		if (ISC_LIST_EMPTY(list1)) \
149 			(list1) = (list2); \
150 		else if (!ISC_LIST_EMPTY(list2)) { \
151 			(list1).tail->link.next = (list2).head; \
152 			(list2).head->link.prev = (list1).tail; \
153 			(list1).tail = (list2).tail; \
154 		} \
155 		(list2).head = NULL; \
156 		(list2).tail = NULL; \
157 	} while (0)
158 
159 #define ISC_LIST_PREPENDLIST(list1, list2, link) \
160 	do { \
161 		if (ISC_LIST_EMPTY(list1)) \
162 			(list1) = (list2); \
163 		else if (!ISC_LIST_EMPTY(list2)) { \
164 			(list2).tail->link.next = (list1).head; \
165 			(list1).head->link.prev = (list2).tail; \
166 			(list1).head = (list2).head; \
167 		} \
168 		(list2).head = NULL; \
169 		(list2).tail = NULL; \
170 	} while (0)
171 
172 #define ISC_LIST_ENQUEUE(list, elt, link) ISC_LIST_APPEND(list, elt, link)
173 #define __ISC_LIST_ENQUEUEUNSAFE(list, elt, link) \
174 	__ISC_LIST_APPENDUNSAFE(list, elt, link)
175 #define ISC_LIST_DEQUEUE(list, elt, link) \
176 	 ISC_LIST_UNLINK_TYPE(list, elt, link, void)
177 #define ISC_LIST_DEQUEUE_TYPE(list, elt, link, type) \
178 	 ISC_LIST_UNLINK_TYPE(list, elt, link, type)
179 #define __ISC_LIST_DEQUEUEUNSAFE(list, elt, link) \
180 	__ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, void)
181 #define __ISC_LIST_DEQUEUEUNSAFE_TYPE(list, elt, link, type) \
182 	__ISC_LIST_UNLINKUNSAFE_TYPE(list, elt, link, type)
183 
184 #endif /* ISC_LIST_H */
185