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