Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/modules/include/sys/queue.h

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 */␊
145struct 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)␉␉␉␉␉␉\␊
180struct name {␉␉␉␉␉␉␉␉\␊
181␉struct type *slh_first;␉/* first element */␉␉␉\␊
182}␊
183␊
184#define␉SLIST_HEAD_INITIALIZER(head)␉␉␉␉␉\␊
185␉{ NULL }␊
186␊
187#define␉SLIST_ENTRY(type)␉␉␉␉␉␉\␊
188struct {␉␉␉␉␉␉␉␉\␊
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)␉␉␉␉␉␉\␊
256struct 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)␉␉␉␉␉␉\␊
265struct {␉␉␉␉␉␉␉␉\␊
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)␉␉␉␉␉␉\␊
374struct name {␉␉␉␉␉␉␉␉\␊
375␉struct type *lh_first;␉/* first element */␉␉␉\␊
376}␊
377␊
378#define␉LIST_HEAD_INITIALIZER(head)␉␉␉␉␉\␊
379␉{ NULL }␊
380␊
381#define␉LIST_ENTRY(type)␉␉␉␉␉␉\␊
382struct {␉␉␉␉␉␉␉␉\␊
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)␉␉␉␉␉␉\␊
486struct 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)␉␉␉␉␉␉\␊
496struct {␉␉␉␉␉␉␉␉\␊
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)␉␉␉␉␉\␊
633struct name {␉␉␉␉␉␉␉␉\␊
634␉struct type *cqh_first;␉␉/* first element */␉␉\␊
635␉struct type *cqh_last;␉␉/* last element */␉␉\␊
636}␊
637␊
638#define CIRCLEQ_ENTRY(type)␉␉␉␉␉␉\␊
639struct {␉␉␉␉␉␉␉␉\␊
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␊
729struct quehead {␊
730␉struct quehead *qh_link;␊
731␉struct quehead *qh_rlink;␊
732};␊
733␊
734#ifdef __GNUC__␊
735␊
736static __inline void␊
737insque(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␊
748static __inline void␊
749remque(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␊
760void␉insque(void *a, void *b);␊
761void␉remque(void *a);␊
762␊
763#endif /* __GNUC__ */␊
764␊
765#endif␊
766#endif /* _KERNEL */␊
767␊
768#endif /* !_SYS_QUEUE_H_ */␊
769

Archive Download this file

Revision: 2182