Merge from vendor branch GCC:
[dragonfly.git] / contrib / nvi / include / sys / queue.h
1 /* 
2  * Copyright (c) 1991, 1993
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
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
18  *    may be used to endorse or promote products derived from this software
19  *    without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * 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
31  * SUCH DAMAGE.
32  *
33  *      @(#)queue.h     8.5 (Berkeley) 8/20/94
34  */
35
36 #ifndef _SYS_QUEUE_H_
37 #define _SYS_QUEUE_H_
38
39 /*
40  * This file defines three types of data structures: lists, tail queues,
41  * and circular queues.
42  *
43  * A list is headed by a single forward pointer (or an array of forward
44  * pointers for a hash table header). The elements are doubly linked
45  * so that an arbitrary element can be removed without a need to
46  * traverse the list. New elements can be added to the list before
47  * or after an existing element or at the head of the list. A list
48  * may only be traversed in the forward direction.
49  *
50  * A tail queue is headed by a pair of pointers, one to the head of the
51  * list and the other to the tail of the list. The elements are doubly
52  * linked so that an arbitrary element can be removed without a need to
53  * traverse the list. New elements can be added to the list before or
54  * after an existing element, at the head of the list, or at the end of
55  * the list. A tail queue may only be traversed in the forward direction.
56  *
57  * A circle queue is headed by a pair of pointers, one to the head of the
58  * list and the other to the tail of the list. The elements are doubly
59  * linked so that an arbitrary element can be removed without a need to
60  * traverse the list. New elements can be added to the list before or after
61  * an existing element, at the head of the list, or at the end of the list.
62  * A circle queue may be traversed in either direction, but has a more
63  * complex end of list detection.
64  *
65  * For details on the use of these macros, see the queue(3) manual page.
66  */
67
68 /*
69  * List definitions.
70  */
71 #define LIST_HEAD(name, type)                                           \
72 struct name {                                                           \
73         struct type *lh_first;  /* first element */                     \
74 }
75
76 #define LIST_ENTRY(type)                                                \
77 struct {                                                                \
78         struct type *le_next;   /* next element */                      \
79         struct type **le_prev;  /* address of previous next element */  \
80 }
81
82 /*
83  * List functions.
84  */
85 #define LIST_INIT(head) {                                               \
86         (head)->lh_first = NULL;                                        \
87 }
88
89 #define LIST_INSERT_AFTER(listelm, elm, field) {                        \
90         if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
91                 (listelm)->field.le_next->field.le_prev =               \
92                     &(elm)->field.le_next;                              \
93         (listelm)->field.le_next = (elm);                               \
94         (elm)->field.le_prev = &(listelm)->field.le_next;               \
95 }
96
97 #define LIST_INSERT_BEFORE(listelm, elm, field) {                       \
98         (elm)->field.le_prev = (listelm)->field.le_prev;                \
99         (elm)->field.le_next = (listelm);                               \
100         *(listelm)->field.le_prev = (elm);                              \
101         (listelm)->field.le_prev = &(elm)->field.le_next;               \
102 }
103
104 #define LIST_INSERT_HEAD(head, elm, field) {                            \
105         if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
106                 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
107         (head)->lh_first = (elm);                                       \
108         (elm)->field.le_prev = &(head)->lh_first;                       \
109 }
110
111 #define LIST_REMOVE(elm, field) {                                       \
112         if ((elm)->field.le_next != NULL)                               \
113                 (elm)->field.le_next->field.le_prev =                   \
114                     (elm)->field.le_prev;                               \
115         *(elm)->field.le_prev = (elm)->field.le_next;                   \
116 }
117
118 /*
119  * Tail queue definitions.
120  */
121 #define TAILQ_HEAD(name, type)                                          \
122 struct name {                                                           \
123         struct type *tqh_first; /* first element */                     \
124         struct type **tqh_last; /* addr of last next element */         \
125 }
126
127 #define TAILQ_ENTRY(type)                                               \
128 struct {                                                                \
129         struct type *tqe_next;  /* next element */                      \
130         struct type **tqe_prev; /* address of previous next element */  \
131 }
132
133 /*
134  * Tail queue functions.
135  */
136 #define TAILQ_INIT(head) {                                              \
137         (head)->tqh_first = NULL;                                       \
138         (head)->tqh_last = &(head)->tqh_first;                          \
139 }
140
141 #define TAILQ_INSERT_HEAD(head, elm, field) {                           \
142         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
143                 (head)->tqh_first->field.tqe_prev =                     \
144                     &(elm)->field.tqe_next;                             \
145         else                                                            \
146                 (head)->tqh_last = &(elm)->field.tqe_next;              \
147         (head)->tqh_first = (elm);                                      \
148         (elm)->field.tqe_prev = &(head)->tqh_first;                     \
149 }
150
151 #define TAILQ_INSERT_TAIL(head, elm, field) {                           \
152         (elm)->field.tqe_next = NULL;                                   \
153         (elm)->field.tqe_prev = (head)->tqh_last;                       \
154         *(head)->tqh_last = (elm);                                      \
155         (head)->tqh_last = &(elm)->field.tqe_next;                      \
156 }
157
158 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) {                 \
159         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
160                 (elm)->field.tqe_next->field.tqe_prev =                 \
161                     &(elm)->field.tqe_next;                             \
162         else                                                            \
163                 (head)->tqh_last = &(elm)->field.tqe_next;              \
164         (listelm)->field.tqe_next = (elm);                              \
165         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
166 }
167
168 #define TAILQ_INSERT_BEFORE(listelm, elm, field) {                      \
169         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
170         (elm)->field.tqe_next = (listelm);                              \
171         *(listelm)->field.tqe_prev = (elm);                             \
172         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
173 }
174
175 #define TAILQ_REMOVE(head, elm, field) {                                \
176         if (((elm)->field.tqe_next) != NULL)                            \
177                 (elm)->field.tqe_next->field.tqe_prev =                 \
178                     (elm)->field.tqe_prev;                              \
179         else                                                            \
180                 (head)->tqh_last = (elm)->field.tqe_prev;               \
181         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
182 }
183
184 /*
185  * Circular queue definitions.
186  */
187 #define CIRCLEQ_HEAD(name, type)                                        \
188 struct name {                                                           \
189         struct type *cqh_first;         /* first element */             \
190         struct type *cqh_last;          /* last element */              \
191 }
192
193 #define CIRCLEQ_ENTRY(type)                                             \
194 struct {                                                                \
195         struct type *cqe_next;          /* next element */              \
196         struct type *cqe_prev;          /* previous element */          \
197 }
198
199 /*
200  * Circular queue functions.
201  */
202 #define CIRCLEQ_INIT(head) {                                            \
203         (head)->cqh_first = (void *)(head);                             \
204         (head)->cqh_last = (void *)(head);                              \
205 }
206
207 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) {               \
208         (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
209         (elm)->field.cqe_prev = (listelm);                              \
210         if ((listelm)->field.cqe_next == (void *)(head))                \
211                 (head)->cqh_last = (elm);                               \
212         else                                                            \
213                 (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
214         (listelm)->field.cqe_next = (elm);                              \
215 }
216
217 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) {              \
218         (elm)->field.cqe_next = (listelm);                              \
219         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
220         if ((listelm)->field.cqe_prev == (void *)(head))                \
221                 (head)->cqh_first = (elm);                              \
222         else                                                            \
223                 (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
224         (listelm)->field.cqe_prev = (elm);                              \
225 }
226
227 #define CIRCLEQ_INSERT_HEAD(head, elm, field) {                         \
228         (elm)->field.cqe_next = (head)->cqh_first;                      \
229         (elm)->field.cqe_prev = (void *)(head);                         \
230         if ((head)->cqh_last == (void *)(head))                         \
231                 (head)->cqh_last = (elm);                               \
232         else                                                            \
233                 (head)->cqh_first->field.cqe_prev = (elm);              \
234         (head)->cqh_first = (elm);                                      \
235 }
236
237 #define CIRCLEQ_INSERT_TAIL(head, elm, field) {                         \
238         (elm)->field.cqe_next = (void *)(head);                         \
239         (elm)->field.cqe_prev = (head)->cqh_last;                       \
240         if ((head)->cqh_first == (void *)(head))                        \
241                 (head)->cqh_first = (elm);                              \
242         else                                                            \
243                 (head)->cqh_last->field.cqe_next = (elm);               \
244         (head)->cqh_last = (elm);                                       \
245 }
246
247 #define CIRCLEQ_REMOVE(head, elm, field) {                              \
248         if ((elm)->field.cqe_next == (void *)(head))                    \
249                 (head)->cqh_last = (elm)->field.cqe_prev;               \
250         else                                                            \
251                 (elm)->field.cqe_next->field.cqe_prev =                 \
252                     (elm)->field.cqe_prev;                              \
253         if ((elm)->field.cqe_prev == (void *)(head))                    \
254                 (head)->cqh_first = (elm)->field.cqe_next;              \
255         else                                                            \
256                 (elm)->field.cqe_prev->field.cqe_next =                 \
257                     (elm)->field.cqe_next;                              \
258 }
259 #endif  /* !_SYS_QUEUE_H_ */