Rev 4874 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 4874 | Rev 4921 | ||
---|---|---|---|
1 | /* |
1 | /*- |
2 | * Copyright (c) 1991, 1993 |
2 | * Copyright (c) 1991, 1993 |
3 | * The Regents of the University of California. All rights reserved. |
3 | * The Regents of the University of California. All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
7 | * are met: |
8 | * 1. Redistributions of source code must retain the above copyright |
8 | * 1. Redistributions of source code must retain the above copyright |
9 | * notice, this list of conditions and the following disclaimer. |
9 | * notice, this list of conditions and the following disclaimer. |
10 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * 2. Redistributions in binary form must reproduce the above copyright |
11 | * notice, this list of conditions and the following disclaimer in the |
11 | * notice, this list of conditions and the following disclaimer in the |
12 | * documentation and/or other materials provided with the distribution. |
12 | * documentation and/or other materials provided with the distribution. |
13 | * 3. All advertising materials mentioning features or use of this software |
- | |
14 | * must display the following acknowledgement: |
- | |
15 | * This product includes software developed by the University of |
- | |
16 | * California, Berkeley and its contributors. |
- | |
17 | * 4. Neither the name of the University nor the names of its contributors |
13 | * 4. Neither the name of the University nor the names of its contributors |
18 | * may be used to endorse or promote products derived from this software |
14 | * may be used to endorse or promote products derived from this software |
19 | * without specific prior written permission. |
15 | * without specific prior written permission. |
20 | * |
16 | * |
21 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
17 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
22 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
23 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
24 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
25 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
21 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
26 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
22 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
27 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
23 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
28 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
24 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
29 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
25 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
30 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
26 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
31 | * SUCH DAMAGE. |
27 | * SUCH DAMAGE. |
32 | * |
28 | * |
33 | * @(#)queue.h 8.5 (Berkeley) 8/20/94 |
29 | * @(#)queue.h 8.5 (Berkeley) 8/20/94 |
34 | * $FreeBSD: src/sys/sys/queue.h,v 1.48 2002/04/17 14:00:37 tmm Exp $ |
30 | * $FreeBSD$ |
35 | */ |
31 | */ |
36 | 32 | ||
37 | #ifndef _SYS_QUEUE_H_ |
33 | #ifndef _SYS_QUEUE_H_ |
38 | #define _SYS_QUEUE_H_ |
34 | #define _SYS_QUEUE_H_ |
39 | 35 | ||
40 | #include |
36 | #include |
41 | 37 | ||
42 | /* |
38 | /* |
43 | * This file defines four types of data structures: singly-linked lists, |
39 | * This file defines four types of data structures: singly-linked lists, |
44 | * singly-linked tail queues, lists and tail queues. |
40 | * singly-linked tail queues, lists and tail queues. |
45 | * |
41 | * |
46 | * A singly-linked list is headed by a single forward pointer. The elements |
42 | * A singly-linked list is headed by a single forward pointer. The elements |
47 | * are singly linked for minimum space and pointer manipulation overhead at |
43 | * are singly linked for minimum space and pointer manipulation overhead at |
48 | * the expense of O(n) removal for arbitrary elements. New elements can be |
44 | * the expense of O(n) removal for arbitrary elements. New elements can be |
49 | * added to the list after an existing element or at the head of the list. |
45 | * added to the list after an existing element or at the head of the list. |
50 | * Elements being removed from the head of the list should use the explicit |
46 | * Elements being removed from the head of the list should use the explicit |
51 | * macro for this purpose for optimum efficiency. A singly-linked list may |
47 | * macro for this purpose for optimum efficiency. A singly-linked list may |
52 | * only be traversed in the forward direction. Singly-linked lists are ideal |
48 | * only be traversed in the forward direction. Singly-linked lists are ideal |
53 | * for applications with large datasets and few or no removals or for |
49 | * for applications with large datasets and few or no removals or for |
54 | * implementing a LIFO queue. |
50 | * implementing a LIFO queue. |
55 | * |
51 | * |
56 | * A singly-linked tail queue is headed by a pair of pointers, one to the |
52 | * A singly-linked tail queue is headed by a pair of pointers, one to the |
57 | * head of the list and the other to the tail of the list. The elements are |
53 | * head of the list and the other to the tail of the list. The elements are |
58 | * singly linked for minimum space and pointer manipulation overhead at the |
54 | * singly linked for minimum space and pointer manipulation overhead at the |
59 | * expense of O(n) removal for arbitrary elements. New elements can be added |
55 | * expense of O(n) removal for arbitrary elements. New elements can be added |
60 | * to the list after an existing element, at the head of the list, or at the |
56 | * to the list after an existing element, at the head of the list, or at the |
61 | * end of the list. Elements being removed from the head of the tail queue |
57 | * end of the list. Elements being removed from the head of the tail queue |
62 | * should use the explicit macro for this purpose for optimum efficiency. |
58 | * should use the explicit macro for this purpose for optimum efficiency. |
63 | * A singly-linked tail queue may only be traversed in the forward direction. |
59 | * A singly-linked tail queue may only be traversed in the forward direction. |
64 | * Singly-linked tail queues are ideal for applications with large datasets |
60 | * Singly-linked tail queues are ideal for applications with large datasets |
65 | * and few or no removals or for implementing a FIFO queue. |
61 | * and few or no removals or for implementing a FIFO queue. |
66 | * |
62 | * |
67 | * A list is headed by a single forward pointer (or an array of forward |
63 | * A list is headed by a single forward pointer (or an array of forward |
68 | * pointers for a hash table header). The elements are doubly linked |
64 | * pointers for a hash table header). The elements are doubly linked |
69 | * so that an arbitrary element can be removed without a need to |
65 | * so that an arbitrary element can be removed without a need to |
70 | * traverse the list. New elements can be added to the list before |
66 | * traverse the list. New elements can be added to the list before |
71 | * or after an existing element or at the head of the list. A list |
67 | * or after an existing element or at the head of the list. A list |
72 | * may only be traversed in the forward direction. |
68 | * may be traversed in either direction. |
73 | * |
69 | * |
74 | * A tail queue is headed by a pair of pointers, one to the head of the |
70 | * A tail queue is headed by a pair of pointers, one to the head of the |
75 | * list and the other to the tail of the list. The elements are doubly |
71 | * list and the other to the tail of the list. The elements are doubly |
76 | * linked so that an arbitrary element can be removed without a need to |
72 | * linked so that an arbitrary element can be removed without a need to |
77 | * traverse the list. New elements can be added to the list before or |
73 | * traverse the list. New elements can be added to the list before or |
78 | * after an existing element, at the head of the list, or at the end of |
74 | * after an existing element, at the head of the list, or at the end of |
79 | * the list. A tail queue may be traversed in either direction. |
75 | * the list. A tail queue may be traversed in either direction. |
80 | * |
76 | * |
81 | * For details on the use of these macros, see the queue(3) manual page. |
77 | * For details on the use of these macros, see the queue(3) manual page. |
82 | * |
78 | * |
83 | * |
79 | * |
84 | * SLIST LIST STAILQ TAILQ |
80 | * SLIST LIST STAILQ TAILQ |
85 | * _HEAD + + + + |
81 | * _HEAD + + + + |
86 | * _HEAD_INITIALIZER + + + + |
82 | * _HEAD_INITIALIZER + + + + |
87 | * _ENTRY + + + + |
83 | * _ENTRY + + + + |
88 | * _INIT + + + + |
84 | * _INIT + + + + |
89 | * _EMPTY + + + + |
85 | * _EMPTY + + + + |
90 | * _FIRST + + + + |
86 | * _FIRST + + + + |
91 | * _NEXT + + + + |
87 | * _NEXT + + + + |
92 | * _PREV - - - + |
88 | * _PREV - + - + |
93 | * _LAST - - + + |
89 | * _LAST - - + + |
94 | * _FOREACH + + + + |
90 | * _FOREACH + + + + |
- | 91 | * _FOREACH_SAFE + + + + |
|
95 | * _FOREACH_REVERSE - - - + |
92 | * _FOREACH_REVERSE - - - + |
- | 93 | * _FOREACH_REVERSE_SAFE - - - + |
|
96 | * _INSERT_HEAD + + + + |
94 | * _INSERT_HEAD + + + + |
97 | * _INSERT_BEFORE - + - + |
95 | * _INSERT_BEFORE - + - + |
98 | * _INSERT_AFTER + + + + |
96 | * _INSERT_AFTER + + + + |
99 | * _INSERT_TAIL - - + + |
97 | * _INSERT_TAIL - - + + |
100 | * _CONCAT - - + + |
98 | * _CONCAT - - + + |
- | 99 | * _REMOVE_AFTER + - + - |
|
101 | * _REMOVE_HEAD + - + - |
100 | * _REMOVE_HEAD + - + - |
102 | * _REMOVE + + + + |
101 | * _REMOVE + + + + |
- | 102 | * _SWAP + + + + |
|
103 | * |
103 | * |
104 | */ |
104 | */ |
- | 105 | #ifdef QUEUE_MACRO_DEBUG |
|
- | 106 | /* Store the last 2 places the queue element or head was altered */ |
|
- | 107 | struct qm_trace { |
|
- | 108 | unsigned long lastline; |
|
- | 109 | unsigned long prevline; |
|
- | 110 | const char *lastfile; |
|
- | 111 | const char *prevfile; |
|
- | 112 | }; |
|
- | 113 | ||
- | 114 | #define TRACEBUF struct qm_trace trace; |
|
- | 115 | #define TRACEBUF_INITIALIZER { __FILE__, __LINE__, NULL, 0 } , |
|
- | 116 | #define TRASHIT(x) do {(x) = (void *)-1;} while (0) |
|
- | 117 | #define QMD_SAVELINK(name, link) void **name = (void *)&(link) |
|
- | 118 | ||
- | 119 | #define QMD_TRACE_HEAD(head) do { \ |
|
- | 120 | (head)->trace.prevline = (head)->trace.lastline; \ |
|
- | 121 | (head)->trace.prevfile = (head)->trace.lastfile; \ |
|
- | 122 | (head)->trace.lastline = __LINE__; \ |
|
- | 123 | (head)->trace.lastfile = __FILE__; \ |
|
- | 124 | } while (0) |
|
- | 125 | ||
- | 126 | #define QMD_TRACE_ELEM(elem) do { \ |
|
- | 127 | (elem)->trace.prevline = (elem)->trace.lastline; \ |
|
- | 128 | (elem)->trace.prevfile = (elem)->trace.lastfile; \ |
|
- | 129 | (elem)->trace.lastline = __LINE__; \ |
|
- | 130 | (elem)->trace.lastfile = __FILE__; \ |
|
- | 131 | } while (0) |
|
- | 132 | ||
- | 133 | #else |
|
- | 134 | #define QMD_TRACE_ELEM(elem) |
|
- | 135 | #define QMD_TRACE_HEAD(head) |
|
- | 136 | #define QMD_SAVELINK(name, link) |
|
- | 137 | #define TRACEBUF |
|
- | 138 | #define TRACEBUF_INITIALIZER |
|
- | 139 | #define TRASHIT(x) |
|
- | 140 | #endif /* QUEUE_MACRO_DEBUG */ |
|
105 | 141 | ||
106 | /* |
142 | /* |
107 | * Singly-linked List declarations. |
143 | * Singly-linked List declarations. |
108 | */ |
144 | */ |
109 | #define SLIST_HEAD(name, type) \ |
145 | #define SLIST_HEAD(name, type) \ |
110 | struct name { \ |
146 | struct name { \ |
111 | struct type *slh_first; /* first element */ \ |
147 | struct type *slh_first; /* first element */ \ |
112 | } |
148 | } |
113 | 149 | ||
114 | #define SLIST_HEAD_INITIALIZER(head) \ |
150 | #define SLIST_HEAD_INITIALIZER(head) \ |
115 | { NULL } |
151 | { NULL } |
116 | 152 | ||
117 | #define SLIST_ENTRY(type) \ |
153 | #define SLIST_ENTRY(type) \ |
118 | struct { \ |
154 | struct { \ |
119 | struct type *sle_next; /* next element */ \ |
155 | struct type *sle_next; /* next element */ \ |
120 | } |
156 | } |
121 | 157 | ||
122 | /* |
158 | /* |
123 | * Singly-linked List functions. |
159 | * Singly-linked List functions. |
124 | */ |
160 | */ |
125 | #define SLIST_EMPTY(head) ((head)->slh_first == NULL) |
161 | #define SLIST_EMPTY(head) ((head)->slh_first == NULL) |
126 | 162 | ||
127 | #define SLIST_FIRST(head) ((head)->slh_first) |
163 | #define SLIST_FIRST(head) ((head)->slh_first) |
128 | 164 | ||
129 | #define SLIST_FOREACH(var, head, field) \ |
165 | #define SLIST_FOREACH(var, head, field) \ |
130 | for ((var) = SLIST_FIRST((head)); \ |
166 | for ((var) = SLIST_FIRST((head)); \ |
131 | (var); \ |
167 | (var); \ |
132 | (var) = SLIST_NEXT((var), field)) |
168 | (var) = SLIST_NEXT((var), field)) |
- | 169 | ||
- | 170 | #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 171 | for ((var) = SLIST_FIRST((head)); \ |
|
- | 172 | (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ |
|
- | 173 | (var) = (tvar)) |
|
- | 174 | ||
- | 175 | #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ |
|
- | 176 | for ((varp) = &SLIST_FIRST((head)); \ |
|
- | 177 | ((var) = *(varp)) != NULL; \ |
|
- | 178 | (varp) = &SLIST_NEXT((var), field)) |
|
133 | 179 | ||
134 | #define SLIST_INIT(head) do { \ |
180 | #define SLIST_INIT(head) do { \ |
135 | SLIST_FIRST((head)) = NULL; \ |
181 | SLIST_FIRST((head)) = NULL; \ |
136 | } while (0) |
182 | } while (0) |
137 | 183 | ||
138 | #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ |
184 | #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ |
139 | SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ |
185 | SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ |
140 | SLIST_NEXT((slistelm), field) = (elm); \ |
186 | SLIST_NEXT((slistelm), field) = (elm); \ |
141 | } while (0) |
187 | } while (0) |
142 | 188 | ||
143 | #define SLIST_INSERT_HEAD(head, elm, field) do { \ |
189 | #define SLIST_INSERT_HEAD(head, elm, field) do { \ |
144 | SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ |
190 | SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ |
145 | SLIST_FIRST((head)) = (elm); \ |
191 | SLIST_FIRST((head)) = (elm); \ |
146 | } while (0) |
192 | } while (0) |
147 | 193 | ||
148 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) |
194 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) |
149 | 195 | ||
150 | #define SLIST_REMOVE(head, elm, type, field) do { \ |
196 | #define SLIST_REMOVE(head, elm, type, field) do { \ |
- | 197 | QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ |
|
151 | if (SLIST_FIRST((head)) == (elm)) { \ |
198 | if (SLIST_FIRST((head)) == (elm)) { \ |
152 | SLIST_REMOVE_HEAD((head), field); \ |
199 | SLIST_REMOVE_HEAD((head), field); \ |
153 | } \ |
200 | } \ |
154 | else { \ |
201 | else { \ |
155 | struct type *curelm = SLIST_FIRST((head)); \ |
202 | struct type *curelm = SLIST_FIRST((head)); \ |
156 | while (SLIST_NEXT(curelm, field) != (elm)) \ |
203 | while (SLIST_NEXT(curelm, field) != (elm)) \ |
157 | curelm = SLIST_NEXT(curelm, field); \ |
204 | curelm = SLIST_NEXT(curelm, field); \ |
158 | SLIST_NEXT(curelm, field) = \ |
205 | SLIST_REMOVE_AFTER(curelm, field); \ |
159 | SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ |
- | |
160 | } \ |
206 | } \ |
- | 207 | TRASHIT(*oldnext); \ |
|
- | 208 | } while (0) |
|
- | 209 | ||
- | 210 | #define SLIST_REMOVE_AFTER(elm, field) do { \ |
|
- | 211 | SLIST_NEXT(elm, field) = \ |
|
- | 212 | SLIST_NEXT(SLIST_NEXT(elm, field), field); \ |
|
161 | } while (0) |
213 | } while (0) |
162 | 214 | ||
163 | #define SLIST_REMOVE_HEAD(head, field) do { \ |
215 | #define SLIST_REMOVE_HEAD(head, field) do { \ |
164 | SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ |
216 | SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ |
165 | } while (0) |
217 | } while (0) |
- | 218 | ||
- | 219 | #define SLIST_SWAP(head1, head2, type) do { \ |
|
- | 220 | struct type *swap_first = SLIST_FIRST(head1); \ |
|
- | 221 | SLIST_FIRST(head1) = SLIST_FIRST(head2); \ |
|
- | 222 | SLIST_FIRST(head2) = swap_first; \ |
|
- | 223 | } while (0) |
|
166 | 224 | ||
167 | /* |
225 | /* |
168 | * Singly-linked Tail queue declarations. |
226 | * Singly-linked Tail queue declarations. |
169 | */ |
227 | */ |
170 | #define STAILQ_HEAD(name, type) \ |
228 | #define STAILQ_HEAD(name, type) \ |
171 | struct name { \ |
229 | struct name { \ |
172 | struct type *stqh_first;/* first element */ \ |
230 | struct type *stqh_first;/* first element */ \ |
173 | struct type **stqh_last;/* addr of last next element */ \ |
231 | struct type **stqh_last;/* addr of last next element */ \ |
174 | } |
232 | } |
175 | 233 | ||
176 | #define STAILQ_HEAD_INITIALIZER(head) \ |
234 | #define STAILQ_HEAD_INITIALIZER(head) \ |
177 | { NULL, &(head).stqh_first } |
235 | { NULL, &(head).stqh_first } |
178 | 236 | ||
179 | #define STAILQ_ENTRY(type) \ |
237 | #define STAILQ_ENTRY(type) \ |
180 | struct { \ |
238 | struct { \ |
181 | struct type *stqe_next; /* next element */ \ |
239 | struct type *stqe_next; /* next element */ \ |
182 | } |
240 | } |
183 | 241 | ||
184 | /* |
242 | /* |
185 | * Singly-linked Tail queue functions. |
243 | * Singly-linked Tail queue functions. |
186 | */ |
244 | */ |
187 | #define STAILQ_CONCAT(head1, head2) do { \ |
245 | #define STAILQ_CONCAT(head1, head2) do { \ |
188 | if (!STAILQ_EMPTY((head2))) { \ |
246 | if (!STAILQ_EMPTY((head2))) { \ |
189 | *(head1)->stqh_last = (head2)->stqh_first; \ |
247 | *(head1)->stqh_last = (head2)->stqh_first; \ |
190 | (head1)->stqh_last = (head2)->stqh_last; \ |
248 | (head1)->stqh_last = (head2)->stqh_last; \ |
191 | STAILQ_INIT((head2)); \ |
249 | STAILQ_INIT((head2)); \ |
192 | } \ |
250 | } \ |
193 | } while (0) |
251 | } while (0) |
194 | 252 | ||
195 | #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) |
253 | #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) |
196 | 254 | ||
197 | #define STAILQ_FIRST(head) ((head)->stqh_first) |
255 | #define STAILQ_FIRST(head) ((head)->stqh_first) |
198 | 256 | ||
199 | #define STAILQ_FOREACH(var, head, field) \ |
257 | #define STAILQ_FOREACH(var, head, field) \ |
200 | for((var) = STAILQ_FIRST((head)); \ |
258 | for((var) = STAILQ_FIRST((head)); \ |
201 | (var); \ |
259 | (var); \ |
202 | (var) = STAILQ_NEXT((var), field)) |
260 | (var) = STAILQ_NEXT((var), field)) |
- | 261 | ||
- | 262 | ||
- | 263 | #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 264 | for ((var) = STAILQ_FIRST((head)); \ |
|
- | 265 | (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ |
|
- | 266 | (var) = (tvar)) |
|
203 | 267 | ||
204 | #define STAILQ_INIT(head) do { \ |
268 | #define STAILQ_INIT(head) do { \ |
205 | STAILQ_FIRST((head)) = NULL; \ |
269 | STAILQ_FIRST((head)) = NULL; \ |
206 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
270 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
207 | } while (0) |
271 | } while (0) |
208 | 272 | ||
209 | #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ |
273 | #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ |
210 | if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ |
274 | if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ |
211 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
275 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
212 | STAILQ_NEXT((tqelm), field) = (elm); \ |
276 | STAILQ_NEXT((tqelm), field) = (elm); \ |
213 | } while (0) |
277 | } while (0) |
214 | 278 | ||
215 | #define STAILQ_INSERT_HEAD(head, elm, field) do { \ |
279 | #define STAILQ_INSERT_HEAD(head, elm, field) do { \ |
216 | if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ |
280 | if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ |
217 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
281 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
218 | STAILQ_FIRST((head)) = (elm); \ |
282 | STAILQ_FIRST((head)) = (elm); \ |
219 | } while (0) |
283 | } while (0) |
220 | 284 | ||
221 | #define STAILQ_INSERT_TAIL(head, elm, field) do { \ |
285 | #define STAILQ_INSERT_TAIL(head, elm, field) do { \ |
222 | STAILQ_NEXT((elm), field) = NULL; \ |
286 | STAILQ_NEXT((elm), field) = NULL; \ |
223 | *(head)->stqh_last = (elm); \ |
287 | *(head)->stqh_last = (elm); \ |
224 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
288 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
225 | } while (0) |
289 | } while (0) |
226 | 290 | ||
227 | #define STAILQ_LAST(head, type, field) \ |
291 | #define STAILQ_LAST(head, type, field) \ |
228 | (STAILQ_EMPTY((head)) ? \ |
292 | (STAILQ_EMPTY((head)) ? NULL : \ |
229 | NULL : \ |
- | |
230 | ((struct type *) \ |
- | |
231 | ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) |
293 | __containerof((head)->stqh_last, struct type, field.stqe_next)) |
232 | 294 | ||
233 | #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) |
295 | #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) |
234 | 296 | ||
235 | #define STAILQ_REMOVE(head, elm, type, field) do { \ |
297 | #define STAILQ_REMOVE(head, elm, type, field) do { \ |
- | 298 | QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ |
|
236 | if (STAILQ_FIRST((head)) == (elm)) { \ |
299 | if (STAILQ_FIRST((head)) == (elm)) { \ |
237 | STAILQ_REMOVE_HEAD((head), field); \ |
300 | STAILQ_REMOVE_HEAD((head), field); \ |
238 | } \ |
301 | } \ |
239 | else { \ |
302 | else { \ |
240 | struct type *curelm = STAILQ_FIRST((head)); \ |
303 | struct type *curelm = STAILQ_FIRST((head)); \ |
241 | while (STAILQ_NEXT(curelm, field) != (elm)) \ |
304 | while (STAILQ_NEXT(curelm, field) != (elm)) \ |
242 | curelm = STAILQ_NEXT(curelm, field); \ |
305 | curelm = STAILQ_NEXT(curelm, field); \ |
243 | if ((STAILQ_NEXT(curelm, field) = \ |
306 | STAILQ_REMOVE_AFTER(head, curelm, field); \ |
244 | STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ |
- | |
245 | (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ |
- | |
246 | } \ |
307 | } \ |
- | 308 | TRASHIT(*oldnext); \ |
|
- | 309 | } while (0) |
|
- | 310 | ||
- | 311 | #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ |
|
- | 312 | if ((STAILQ_NEXT(elm, field) = \ |
|
- | 313 | STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ |
|
- | 314 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
|
247 | } while (0) |
315 | } while (0) |
248 | 316 | ||
249 | #define STAILQ_REMOVE_HEAD(head, field) do { \ |
317 | #define STAILQ_REMOVE_HEAD(head, field) do { \ |
250 | if ((STAILQ_FIRST((head)) = \ |
318 | if ((STAILQ_FIRST((head)) = \ |
251 | STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ |
319 | STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ |
252 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
320 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
253 | } while (0) |
321 | } while (0) |
254 | 322 | ||
255 | #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ |
323 | #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ |
256 | if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ |
324 | if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ |
257 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
325 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
258 | } while (0) |
326 | } while (0) |
- | 327 | ||
- | 328 | #define STAILQ_SWAP(head1, head2, type) do { \ |
|
- | 329 | struct type *swap_first = STAILQ_FIRST(head1); \ |
|
- | 330 | struct type **swap_last = (head1)->stqh_last; \ |
|
- | 331 | STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ |
|
- | 332 | (head1)->stqh_last = (head2)->stqh_last; \ |
|
- | 333 | STAILQ_FIRST(head2) = swap_first; \ |
|
- | 334 | (head2)->stqh_last = swap_last; \ |
|
- | 335 | if (STAILQ_EMPTY(head1)) \ |
|
- | 336 | (head1)->stqh_last = &STAILQ_FIRST(head1); \ |
|
- | 337 | if (STAILQ_EMPTY(head2)) \ |
|
- | 338 | (head2)->stqh_last = &STAILQ_FIRST(head2); \ |
|
- | 339 | } while (0) |
|
- | 340 | ||
259 | 341 | ||
260 | /* |
342 | /* |
261 | * List declarations. |
343 | * List declarations. |
262 | */ |
344 | */ |
263 | #define LIST_HEAD(name, type) \ |
345 | #define LIST_HEAD(name, type) \ |
264 | struct name { \ |
346 | struct name { \ |
265 | struct type *lh_first; /* first element */ \ |
347 | struct type *lh_first; /* first element */ \ |
266 | } |
348 | } |
267 | 349 | ||
268 | #define LIST_HEAD_INITIALIZER(head) \ |
350 | #define LIST_HEAD_INITIALIZER(head) \ |
269 | { NULL } |
351 | { NULL } |
270 | 352 | ||
271 | #define LIST_ENTRY(type) \ |
353 | #define LIST_ENTRY(type) \ |
272 | struct { \ |
354 | struct { \ |
273 | struct type *le_next; /* next element */ \ |
355 | struct type *le_next; /* next element */ \ |
274 | struct type **le_prev; /* address of previous next element */ \ |
356 | struct type **le_prev; /* address of previous next element */ \ |
275 | } |
357 | } |
276 | 358 | ||
277 | /* |
359 | /* |
278 | * List functions. |
360 | * List functions. |
279 | */ |
361 | */ |
- | 362 | ||
- | 363 | #if (defined(_KERNEL) && defined(INVARIANTS)) |
|
- | 364 | #define QMD_LIST_CHECK_HEAD(head, field) do { \ |
|
- | 365 | if (LIST_FIRST((head)) != NULL && \ |
|
- | 366 | LIST_FIRST((head))->field.le_prev != \ |
|
- | 367 | &LIST_FIRST((head))) \ |
|
- | 368 | panic("Bad list head %p first->prev != head", (head)); \ |
|
- | 369 | } while (0) |
|
- | 370 | ||
- | 371 | #define QMD_LIST_CHECK_NEXT(elm, field) do { \ |
|
- | 372 | if (LIST_NEXT((elm), field) != NULL && \ |
|
- | 373 | LIST_NEXT((elm), field)->field.le_prev != \ |
|
- | 374 | &((elm)->field.le_next)) \ |
|
- | 375 | panic("Bad link elm %p next->prev != elm", (elm)); \ |
|
- | 376 | } while (0) |
|
- | 377 | ||
- | 378 | #define QMD_LIST_CHECK_PREV(elm, field) do { \ |
|
- | 379 | if (*(elm)->field.le_prev != (elm)) \ |
|
- | 380 | panic("Bad link elm %p prev->next != elm", (elm)); \ |
|
- | 381 | } while (0) |
|
- | 382 | #else |
|
- | 383 | #define QMD_LIST_CHECK_HEAD(head, field) |
|
- | 384 | #define QMD_LIST_CHECK_NEXT(elm, field) |
|
- | 385 | #define QMD_LIST_CHECK_PREV(elm, field) |
|
- | 386 | #endif /* (_KERNEL && INVARIANTS) */ |
|
280 | 387 | ||
281 | #define LIST_EMPTY(head) ((head)->lh_first == NULL) |
388 | #define LIST_EMPTY(head) ((head)->lh_first == NULL) |
282 | 389 | ||
283 | #define LIST_FIRST(head) ((head)->lh_first) |
390 | #define LIST_FIRST(head) ((head)->lh_first) |
284 | 391 | ||
285 | #define LIST_FOREACH(var, head, field) \ |
392 | #define LIST_FOREACH(var, head, field) \ |
286 | for ((var) = LIST_FIRST((head)); \ |
393 | for ((var) = LIST_FIRST((head)); \ |
287 | (var); \ |
394 | (var); \ |
288 | (var) = LIST_NEXT((var), field)) |
395 | (var) = LIST_NEXT((var), field)) |
- | 396 | ||
- | 397 | #define LIST_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 398 | for ((var) = LIST_FIRST((head)); \ |
|
- | 399 | (var) && ((tvar) = LIST_NEXT((var), field), 1); \ |
|
- | 400 | (var) = (tvar)) |
|
289 | 401 | ||
290 | #define LIST_INIT(head) do { \ |
402 | #define LIST_INIT(head) do { \ |
291 | LIST_FIRST((head)) = NULL; \ |
403 | LIST_FIRST((head)) = NULL; \ |
292 | } while (0) |
404 | } while (0) |
293 | 405 | ||
294 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \ |
406 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \ |
- | 407 | QMD_LIST_CHECK_NEXT(listelm, field); \ |
|
295 | if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ |
408 | if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ |
296 | LIST_NEXT((listelm), field)->field.le_prev = \ |
409 | LIST_NEXT((listelm), field)->field.le_prev = \ |
297 | &LIST_NEXT((elm), field); \ |
410 | &LIST_NEXT((elm), field); \ |
298 | LIST_NEXT((listelm), field) = (elm); \ |
411 | LIST_NEXT((listelm), field) = (elm); \ |
299 | (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ |
412 | (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ |
300 | } while (0) |
413 | } while (0) |
301 | 414 | ||
302 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ |
415 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ |
- | 416 | QMD_LIST_CHECK_PREV(listelm, field); \ |
|
303 | (elm)->field.le_prev = (listelm)->field.le_prev; \ |
417 | (elm)->field.le_prev = (listelm)->field.le_prev; \ |
304 | LIST_NEXT((elm), field) = (listelm); \ |
418 | LIST_NEXT((elm), field) = (listelm); \ |
305 | *(listelm)->field.le_prev = (elm); \ |
419 | *(listelm)->field.le_prev = (elm); \ |
306 | (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ |
420 | (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ |
307 | } while (0) |
421 | } while (0) |
308 | 422 | ||
309 | #define LIST_INSERT_HEAD(head, elm, field) do { \ |
423 | #define LIST_INSERT_HEAD(head, elm, field) do { \ |
- | 424 | QMD_LIST_CHECK_HEAD((head), field); \ |
|
310 | if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ |
425 | if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ |
311 | LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ |
426 | LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ |
312 | LIST_FIRST((head)) = (elm); \ |
427 | LIST_FIRST((head)) = (elm); \ |
313 | (elm)->field.le_prev = &LIST_FIRST((head)); \ |
428 | (elm)->field.le_prev = &LIST_FIRST((head)); \ |
314 | } while (0) |
429 | } while (0) |
315 | 430 | ||
316 | #define LIST_NEXT(elm, field) ((elm)->field.le_next) |
431 | #define LIST_NEXT(elm, field) ((elm)->field.le_next) |
- | 432 | ||
- | 433 | #define LIST_PREV(elm, head, type, field) \ |
|
- | 434 | ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ |
|
- | 435 | __containerof((elm)->field.le_prev, struct type, field.le_next)) |
|
317 | 436 | ||
- | 437 | #define LIST_REMOVE(elm, field) do { \ |
|
- | 438 | QMD_SAVELINK(oldnext, (elm)->field.le_next); \ |
|
- | 439 | QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ |
|
- | 440 | QMD_LIST_CHECK_NEXT(elm, field); \ |
|
318 | #define LIST_REMOVE(elm, field) do { \ |
441 | QMD_LIST_CHECK_PREV(elm, field); \ |
319 | if (LIST_NEXT((elm), field) != NULL) \ |
442 | if (LIST_NEXT((elm), field) != NULL) \ |
320 | LIST_NEXT((elm), field)->field.le_prev = \ |
443 | LIST_NEXT((elm), field)->field.le_prev = \ |
321 | (elm)->field.le_prev; \ |
444 | (elm)->field.le_prev; \ |
322 | *(elm)->field.le_prev = LIST_NEXT((elm), field); \ |
445 | *(elm)->field.le_prev = LIST_NEXT((elm), field); \ |
- | 446 | TRASHIT(*oldnext); \ |
|
- | 447 | TRASHIT(*oldprev); \ |
|
- | 448 | } while (0) |
|
- | 449 | ||
- | 450 | #define LIST_SWAP(head1, head2, type, field) do { \ |
|
- | 451 | struct type *swap_tmp = LIST_FIRST((head1)); \ |
|
- | 452 | LIST_FIRST((head1)) = LIST_FIRST((head2)); \ |
|
- | 453 | LIST_FIRST((head2)) = swap_tmp; \ |
|
- | 454 | if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ |
|
- | 455 | swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ |
|
- | 456 | if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ |
|
- | 457 | swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ |
|
323 | } while (0) |
458 | } while (0) |
324 | 459 | ||
325 | /* |
460 | /* |
326 | * Tail queue declarations. |
461 | * Tail queue declarations. |
327 | */ |
462 | */ |
328 | #define TAILQ_HEAD(name, type) \ |
463 | #define TAILQ_HEAD(name, type) \ |
329 | struct name { \ |
464 | struct name { \ |
330 | struct type *tqh_first; /* first element */ \ |
465 | struct type *tqh_first; /* first element */ \ |
331 | struct type **tqh_last; /* addr of last next element */ \ |
466 | struct type **tqh_last; /* addr of last next element */ \ |
- | 467 | TRACEBUF \ |
|
332 | } |
468 | } |
333 | 469 | ||
334 | #define TAILQ_HEAD_INITIALIZER(head) \ |
470 | #define TAILQ_HEAD_INITIALIZER(head) \ |
335 | { NULL, &(head).tqh_first } |
471 | { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } |
336 | 472 | ||
337 | #define TAILQ_ENTRY(type) \ |
473 | #define TAILQ_ENTRY(type) \ |
338 | struct { \ |
474 | struct { \ |
339 | struct type *tqe_next; /* next element */ \ |
475 | struct type *tqe_next; /* next element */ \ |
340 | struct type **tqe_prev; /* address of previous next element */ \ |
476 | struct type **tqe_prev; /* address of previous next element */ \ |
- | 477 | TRACEBUF \ |
|
341 | } |
478 | } |
342 | 479 | ||
343 | /* |
480 | /* |
344 | * Tail queue functions. |
481 | * Tail queue functions. |
345 | */ |
482 | */ |
- | 483 | #if (defined(_KERNEL) && defined(INVARIANTS)) |
|
- | 484 | #define QMD_TAILQ_CHECK_HEAD(head, field) do { \ |
|
- | 485 | if (!TAILQ_EMPTY(head) && \ |
|
- | 486 | TAILQ_FIRST((head))->field.tqe_prev != \ |
|
- | 487 | &TAILQ_FIRST((head))) \ |
|
- | 488 | panic("Bad tailq head %p first->prev != head", (head)); \ |
|
- | 489 | } while (0) |
|
- | 490 | ||
- | 491 | #define QMD_TAILQ_CHECK_TAIL(head, field) do { \ |
|
- | 492 | if (*(head)->tqh_last != NULL) \ |
|
- | 493 | panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ |
|
- | 494 | } while (0) |
|
- | 495 | ||
- | 496 | #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ |
|
- | 497 | if (TAILQ_NEXT((elm), field) != NULL && \ |
|
- | 498 | TAILQ_NEXT((elm), field)->field.tqe_prev != \ |
|
- | 499 | &((elm)->field.tqe_next)) \ |
|
- | 500 | panic("Bad link elm %p next->prev != elm", (elm)); \ |
|
- | 501 | } while (0) |
|
- | 502 | ||
- | 503 | #define QMD_TAILQ_CHECK_PREV(elm, field) do { \ |
|
- | 504 | if (*(elm)->field.tqe_prev != (elm)) \ |
|
- | 505 | panic("Bad link elm %p prev->next != elm", (elm)); \ |
|
- | 506 | } while (0) |
|
- | 507 | #else |
|
- | 508 | #define QMD_TAILQ_CHECK_HEAD(head, field) |
|
- | 509 | #define QMD_TAILQ_CHECK_TAIL(head, headname) |
|
- | 510 | #define QMD_TAILQ_CHECK_NEXT(elm, field) |
|
- | 511 | #define QMD_TAILQ_CHECK_PREV(elm, field) |
|
- | 512 | #endif /* (_KERNEL && INVARIANTS) */ |
|
- | 513 | ||
346 | #define TAILQ_CONCAT(head1, head2, field) do { \ |
514 | #define TAILQ_CONCAT(head1, head2, field) do { \ |
347 | if (!TAILQ_EMPTY(head2)) { \ |
515 | if (!TAILQ_EMPTY(head2)) { \ |
348 | *(head1)->tqh_last = (head2)->tqh_first; \ |
516 | *(head1)->tqh_last = (head2)->tqh_first; \ |
349 | (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ |
517 | (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ |
350 | (head1)->tqh_last = (head2)->tqh_last; \ |
518 | (head1)->tqh_last = (head2)->tqh_last; \ |
351 | TAILQ_INIT((head2)); \ |
519 | TAILQ_INIT((head2)); \ |
- | 520 | QMD_TRACE_HEAD(head1); \ |
|
- | 521 | QMD_TRACE_HEAD(head2); \ |
|
352 | } \ |
522 | } \ |
353 | } while (0) |
523 | } while (0) |
354 | 524 | ||
355 | #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) |
525 | #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) |
356 | 526 | ||
357 | #define TAILQ_FIRST(head) ((head)->tqh_first) |
527 | #define TAILQ_FIRST(head) ((head)->tqh_first) |
358 | 528 | ||
359 | #define TAILQ_FOREACH(var, head, field) \ |
529 | #define TAILQ_FOREACH(var, head, field) \ |
360 | for ((var) = TAILQ_FIRST((head)); \ |
530 | for ((var) = TAILQ_FIRST((head)); \ |
361 | (var); \ |
531 | (var); \ |
362 | (var) = TAILQ_NEXT((var), field)) |
532 | (var) = TAILQ_NEXT((var), field)) |
- | 533 | ||
- | 534 | #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 535 | for ((var) = TAILQ_FIRST((head)); \ |
|
- | 536 | (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ |
|
- | 537 | (var) = (tvar)) |
|
363 | 538 | ||
364 | #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ |
539 | #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ |
365 | for ((var) = TAILQ_LAST((head), headname); \ |
540 | for ((var) = TAILQ_LAST((head), headname); \ |
366 | (var); \ |
541 | (var); \ |
367 | (var) = TAILQ_PREV((var), headname, field)) |
542 | (var) = TAILQ_PREV((var), headname, field)) |
- | 543 | ||
- | 544 | #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ |
|
- | 545 | for ((var) = TAILQ_LAST((head), headname); \ |
|
- | 546 | (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ |
|
- | 547 | (var) = (tvar)) |
|
368 | 548 | ||
369 | #define TAILQ_INIT(head) do { \ |
549 | #define TAILQ_INIT(head) do { \ |
370 | TAILQ_FIRST((head)) = NULL; \ |
550 | TAILQ_FIRST((head)) = NULL; \ |
371 | (head)->tqh_last = &TAILQ_FIRST((head)); \ |
551 | (head)->tqh_last = &TAILQ_FIRST((head)); \ |
- | 552 | QMD_TRACE_HEAD(head); \ |
|
372 | } while (0) |
553 | } while (0) |
373 | 554 | ||
374 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
555 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
- | 556 | QMD_TAILQ_CHECK_NEXT(listelm, field); \ |
|
375 | if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ |
557 | if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ |
376 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
558 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
377 | &TAILQ_NEXT((elm), field); \ |
559 | &TAILQ_NEXT((elm), field); \ |
378 | else \ |
560 | else { \ |
379 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
561 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
- | 562 | QMD_TRACE_HEAD(head); \ |
|
- | 563 | } \ |
|
380 | TAILQ_NEXT((listelm), field) = (elm); \ |
564 | TAILQ_NEXT((listelm), field) = (elm); \ |
381 | (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ |
565 | (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ |
- | 566 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
- | 567 | QMD_TRACE_ELEM(&listelm->field); \ |
|
382 | } while (0) |
568 | } while (0) |
383 | 569 | ||
384 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ |
570 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ |
- | 571 | QMD_TAILQ_CHECK_PREV(listelm, field); \ |
|
385 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ |
572 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ |
386 | TAILQ_NEXT((elm), field) = (listelm); \ |
573 | TAILQ_NEXT((elm), field) = (listelm); \ |
387 | *(listelm)->field.tqe_prev = (elm); \ |
574 | *(listelm)->field.tqe_prev = (elm); \ |
388 | (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ |
575 | (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ |
- | 576 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
- | 577 | QMD_TRACE_ELEM(&listelm->field); \ |
|
389 | } while (0) |
578 | } while (0) |
390 | 579 | ||
391 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \ |
580 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \ |
- | 581 | QMD_TAILQ_CHECK_HEAD(head, field); \ |
|
392 | if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ |
582 | if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ |
393 | TAILQ_FIRST((head))->field.tqe_prev = \ |
583 | TAILQ_FIRST((head))->field.tqe_prev = \ |
394 | &TAILQ_NEXT((elm), field); \ |
584 | &TAILQ_NEXT((elm), field); \ |
395 | else \ |
585 | else \ |
396 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
586 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
397 | TAILQ_FIRST((head)) = (elm); \ |
587 | TAILQ_FIRST((head)) = (elm); \ |
398 | (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ |
588 | (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ |
- | 589 | QMD_TRACE_HEAD(head); \ |
|
- | 590 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
399 | } while (0) |
591 | } while (0) |
400 | 592 | ||
401 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \ |
593 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \ |
- | 594 | QMD_TAILQ_CHECK_TAIL(head, field); \ |
|
402 | TAILQ_NEXT((elm), field) = NULL; \ |
595 | TAILQ_NEXT((elm), field) = NULL; \ |
403 | (elm)->field.tqe_prev = (head)->tqh_last; \ |
596 | (elm)->field.tqe_prev = (head)->tqh_last; \ |
404 | *(head)->tqh_last = (elm); \ |
597 | *(head)->tqh_last = (elm); \ |
405 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
598 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
- | 599 | QMD_TRACE_HEAD(head); \ |
|
- | 600 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
406 | } while (0) |
601 | } while (0) |
407 | 602 | ||
408 | #define TAILQ_LAST(head, headname) \ |
603 | #define TAILQ_LAST(head, headname) \ |
409 | (*(((struct headname *)((head)->tqh_last))->tqh_last)) |
604 | (*(((struct headname *)((head)->tqh_last))->tqh_last)) |
410 | 605 | ||
411 | #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) |
606 | #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) |
412 | 607 | ||
413 | #define TAILQ_PREV(elm, headname, field) \ |
608 | #define TAILQ_PREV(elm, headname, field) \ |
414 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) |
609 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) |
415 | 610 | ||
416 | #define TAILQ_REMOVE(head, elm, field) do { \ |
611 | #define TAILQ_REMOVE(head, elm, field) do { \ |
- | 612 | QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ |
|
- | 613 | QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ |
|
- | 614 | QMD_TAILQ_CHECK_NEXT(elm, field); \ |
|
- | 615 | QMD_TAILQ_CHECK_PREV(elm, field); \ |
|
417 | if ((TAILQ_NEXT((elm), field)) != NULL) \ |
616 | if ((TAILQ_NEXT((elm), field)) != NULL) \ |
418 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
617 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
419 | (elm)->field.tqe_prev; \ |
618 | (elm)->field.tqe_prev; \ |
420 | else \ |
619 | else { \ |
421 | (head)->tqh_last = (elm)->field.tqe_prev; \ |
620 | (head)->tqh_last = (elm)->field.tqe_prev; \ |
- | 621 | QMD_TRACE_HEAD(head); \ |
|
- | 622 | } \ |
|
422 | *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ |
623 | *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ |
- | 624 | TRASHIT(*oldnext); \ |
|
- | 625 | TRASHIT(*oldprev); \ |
|
- | 626 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
423 | } while (0) |
627 | } while (0) |
- | 628 | ||
- | 629 | #define TAILQ_SWAP(head1, head2, type, field) do { \ |
|
- | 630 | struct type *swap_first = (head1)->tqh_first; \ |
|
- | 631 | struct type **swap_last = (head1)->tqh_last; \ |
|
- | 632 | (head1)->tqh_first = (head2)->tqh_first; \ |
|
- | 633 | (head1)->tqh_last = (head2)->tqh_last; \ |
|
- | 634 | (head2)->tqh_first = swap_first; \ |
|
- | 635 | (head2)->tqh_last = swap_last; \ |
|
- | 636 | if ((swap_first = (head1)->tqh_first) != NULL) \ |
|
- | 637 | swap_first->field.tqe_prev = &(head1)->tqh_first; \ |
|
- | 638 | else \ |
|
- | 639 | (head1)->tqh_last = &(head1)->tqh_first; \ |
|
- | 640 | if ((swap_first = (head2)->tqh_first) != NULL) \ |
|
- | 641 | swap_first->field.tqe_prev = &(head2)->tqh_first; \ |
|
- | 642 | else \ |
|
- | 643 | (head2)->tqh_last = &(head2)->tqh_first; \ |
|
424 | 644 | } while (0) |
|
425 | 645 | ||
426 | #ifdef _KERNEL |
646 | #ifdef _KERNEL |
427 | 647 | ||
428 | /* |
648 | /* |
429 | * XXX insque() and remque() are an old way of handling certain queues. |
649 | * XXX insque() and remque() are an old way of handling certain queues. |
430 | * They bogusly assumes that all queue heads look alike. |
650 | * They bogusly assumes that all queue heads look alike. |
431 | */ |
651 | */ |
432 | 652 | ||
433 | struct quehead { |
653 | struct quehead { |
434 | struct quehead *qh_link; |
654 | struct quehead *qh_link; |
435 | struct quehead *qh_rlink; |
655 | struct quehead *qh_rlink; |
436 | }; |
656 | }; |
437 | 657 | ||
438 | #ifdef __GNUC__ |
658 | #ifdef __GNUC__ |
439 | 659 | ||
440 | static __inline void |
660 | static __inline void |
441 | insque(void *a, void *b) |
661 | insque(void *a, void *b) |
442 | { |
662 | { |
443 | struct quehead *element = (struct quehead *)a, |
663 | struct quehead *element = (struct quehead *)a, |
444 | *head = (struct quehead *)b; |
664 | *head = (struct quehead *)b; |
445 | 665 | ||
446 | element->qh_link = head->qh_link; |
666 | element->qh_link = head->qh_link; |
447 | element->qh_rlink = head; |
667 | element->qh_rlink = head; |
448 | head->qh_link = element; |
668 | head->qh_link = element; |
449 | element->qh_link->qh_rlink = element; |
669 | element->qh_link->qh_rlink = element; |
450 | } |
670 | } |
451 | 671 | ||
452 | static __inline void |
672 | static __inline void |
453 | remque(void *a) |
673 | remque(void *a) |
454 | { |
674 | { |
455 | struct quehead *element = (struct quehead *)a; |
675 | struct quehead *element = (struct quehead *)a; |
456 | 676 | ||
457 | element->qh_link->qh_rlink = element->qh_rlink; |
677 | element->qh_link->qh_rlink = element->qh_rlink; |
458 | element->qh_rlink->qh_link = element->qh_link; |
678 | element->qh_rlink->qh_link = element->qh_link; |
459 | element->qh_rlink = 0; |
679 | element->qh_rlink = 0; |
460 | } |
680 | } |
461 | 681 | ||
462 | #else /* !__GNUC__ */ |
682 | #else /* !__GNUC__ */ |
463 | 683 | ||
464 | void insque(void *a, void *b); |
684 | void insque(void *a, void *b); |
465 | void remque(void *a); |
685 | void remque(void *a); |
466 | 686 | ||
467 | #endif /* __GNUC__ */ |
687 | #endif /* __GNUC__ */ |
468 | 688 | ||
469 | #endif /* _KERNEL */ |
689 | #endif /* _KERNEL */ |
470 | 690 | ||
471 | #endif /* !_SYS_QUEUE_H_ */ |
691 | #endif /* !_SYS_QUEUE_H_ */ |