6 * Copyright (c) 1991, 1993
7 * The Regents of the University of California. All rights reserved.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by the University of
20 * California, Berkeley and its contributors.
21 * 4. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * @(#)queue.h 8.5 (Berkeley) 8/20/94
44 * This file defines three types of data structures: lists, tail queues,
45 * and circular queues.
47 * A list is headed by a single forward pointer (or an array of forward
48 * pointers for a hash table header). The elements are doubly linked
49 * so that an arbitrary element can be removed without a need to
50 * traverse the list. New elements can be added to the list before
51 * or after an existing element or at the head of the list. A list
52 * may only be traversed in the forward direction.
54 * A tail queue is headed by a pair of pointers, one to the head of the
55 * list and the other to the tail of the list. The elements are doubly
56 * linked so that an arbitrary element can be removed without a need to
57 * traverse the list. New elements can be added to the list before or
58 * after an existing element, at the head of the list, or at the end of
59 * the list. A tail queue may only be traversed in the forward direction.
61 * A circle queue is headed by a pair of pointers, one to the head of the
62 * list and the other to the tail of the list. The elements are doubly
63 * linked so that an arbitrary element can be removed without a need to
64 * traverse the list. New elements can be added to the list before or after
65 * an existing element, at the head of the list, or at the end of the list.
66 * A circle queue may be traversed in either direction, but has a more
67 * complex end of list detection.
69 * For details on the use of these macros, see the queue(3) manual page.
75 #define LIST_HEAD(name, type) \
77 struct type *lh_first; /* first element */ \
80 #define LIST_ENTRY(type) \
82 struct type *le_next; /* next element */ \
83 struct type **le_prev; /* address of previous next element */ \
89 #define LIST_INIT(head) { \
90 (head)->lh_first = NULL; \
93 #define LIST_INSERT_AFTER(listelm, elm, field) { \
94 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
95 (listelm)->field.le_next->field.le_prev = \
96 &(elm)->field.le_next; \
97 (listelm)->field.le_next = (elm); \
98 (elm)->field.le_prev = &(listelm)->field.le_next; \
101 #define LIST_INSERT_BEFORE(listelm, elm, field) { \
102 (elm)->field.le_prev = (listelm)->field.le_prev; \
103 (elm)->field.le_next = (listelm); \
104 *(listelm)->field.le_prev = (elm); \
105 (listelm)->field.le_prev = &(elm)->field.le_next; \
108 #define LIST_INSERT_HEAD(head, elm, field) { \
109 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
110 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
111 (head)->lh_first = (elm); \
112 (elm)->field.le_prev = &(head)->lh_first; \
115 #define LIST_REMOVE(elm, field) { \
116 if ((elm)->field.le_next != NULL) \
117 (elm)->field.le_next->field.le_prev = \
118 (elm)->field.le_prev; \
119 *(elm)->field.le_prev = (elm)->field.le_next; \
123 * Tail queue definitions.
125 #define TAILQ_HEAD(name, type) \
127 struct type *tqh_first; /* first element */ \
128 struct type **tqh_last; /* addr of last next element */ \
131 #define TAILQ_ENTRY(type) \
133 struct type *tqe_next; /* next element */ \
134 struct type **tqe_prev; /* address of previous next element */ \
138 * Tail queue functions.
140 #define TAILQ_INIT(head) { \
141 (head)->tqh_first = NULL; \
142 (head)->tqh_last = &(head)->tqh_first; \
145 #define TAILQ_INSERT_HEAD(head, elm, field) { \
146 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
147 (head)->tqh_first->field.tqe_prev = \
148 &(elm)->field.tqe_next; \
150 (head)->tqh_last = &(elm)->field.tqe_next; \
151 (head)->tqh_first = (elm); \
152 (elm)->field.tqe_prev = &(head)->tqh_first; \
155 #define TAILQ_INSERT_TAIL(head, elm, field) { \
156 (elm)->field.tqe_next = NULL; \
157 (elm)->field.tqe_prev = (head)->tqh_last; \
158 *(head)->tqh_last = (elm); \
159 (head)->tqh_last = &(elm)->field.tqe_next; \
162 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \
163 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
164 (elm)->field.tqe_next->field.tqe_prev = \
165 &(elm)->field.tqe_next; \
167 (head)->tqh_last = &(elm)->field.tqe_next; \
168 (listelm)->field.tqe_next = (elm); \
169 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
172 #define TAILQ_INSERT_BEFORE(listelm, elm, field) { \
173 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
174 (elm)->field.tqe_next = (listelm); \
175 *(listelm)->field.tqe_prev = (elm); \
176 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
179 #define TAILQ_REMOVE(head, elm, field) { \
180 if (((elm)->field.tqe_next) != NULL) \
181 (elm)->field.tqe_next->field.tqe_prev = \
182 (elm)->field.tqe_prev; \
184 (head)->tqh_last = (elm)->field.tqe_prev; \
185 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
189 * Circular queue definitions.
191 #define CIRCLEQ_HEAD(name, type) \
193 struct type *cqh_first; /* first element */ \
194 struct type *cqh_last; /* last element */ \
197 #define CIRCLEQ_ENTRY(type) \
199 struct type *cqe_next; /* next element */ \
200 struct type *cqe_prev; /* previous element */ \
204 * Circular queue functions.
206 #define CIRCLEQ_INIT(head) { \
207 (head)->cqh_first = (void *)(head); \
208 (head)->cqh_last = (void *)(head); \
211 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \
212 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
213 (elm)->field.cqe_prev = (listelm); \
214 if ((listelm)->field.cqe_next == (void *)(head)) \
215 (head)->cqh_last = (elm); \
217 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
218 (listelm)->field.cqe_next = (elm); \
221 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \
222 (elm)->field.cqe_next = (listelm); \
223 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
224 if ((listelm)->field.cqe_prev == (void *)(head)) \
225 (head)->cqh_first = (elm); \
227 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
228 (listelm)->field.cqe_prev = (elm); \
231 #define CIRCLEQ_INSERT_HEAD(head, elm, field) { \
232 (elm)->field.cqe_next = (head)->cqh_first; \
233 (elm)->field.cqe_prev = (void *)(head); \
234 if ((head)->cqh_last == (void *)(head)) \
235 (head)->cqh_last = (elm); \
237 (head)->cqh_first->field.cqe_prev = (elm); \
238 (head)->cqh_first = (elm); \
241 #define CIRCLEQ_INSERT_TAIL(head, elm, field) { \
242 (elm)->field.cqe_next = (void *)(head); \
243 (elm)->field.cqe_prev = (head)->cqh_last; \
244 if ((head)->cqh_first == (void *)(head)) \
245 (head)->cqh_first = (elm); \
247 (head)->cqh_last->field.cqe_next = (elm); \
248 (head)->cqh_last = (elm); \
251 #define CIRCLEQ_REMOVE(head, elm, field) { \
252 if ((elm)->field.cqe_next == (void *)(head)) \
253 (head)->cqh_last = (elm)->field.cqe_prev; \
255 (elm)->field.cqe_next->field.cqe_prev = \
256 (elm)->field.cqe_prev; \
257 if ((elm)->field.cqe_prev == (void *)(head)) \
258 (head)->cqh_first = (elm)->field.cqe_next; \
260 (elm)->field.cqe_prev->field.cqe_next = \
261 (elm)->field.cqe_next; \