Watt-32 tcp/ip  2.2 dev-rel.10
queue.h
Go to the documentation of this file.
1 
5 /*
6  * Copyright (c) 1991, 1993
7  * The Regents of the University of California. All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
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.
24  *
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
35  * SUCH DAMAGE.
36  *
37  * @(#)queue.h 8.5 (Berkeley) 8/20/94
38  */
39 
40 #ifndef __SYS_QUEUE_H
41 #define __SYS_QUEUE_H
42 
43 /*
44  * This file defines three types of data structures: lists, tail queues,
45  * and circular queues.
46  *
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.
53  *
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.
60  *
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.
68  *
69  * For details on the use of these macros, see the queue(3) manual page.
70  */
71 
72 /*
73  * List definitions.
74  */
75 #define LIST_HEAD(name, type) \
76  struct name { \
77  struct type *lh_first; /* first element */ \
78  }
79 
80 #define LIST_ENTRY(type) \
81  struct { \
82  struct type *le_next; /* next element */ \
83  struct type **le_prev; /* address of previous next element */ \
84  }
85 
86 /*
87  * List functions.
88  */
89 #define LIST_INIT(head) { \
90  (head)->lh_first = NULL; \
91  }
92 
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; \
99  }
100 
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; \
106  }
107 
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; \
113  }
114 
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; \
120  }
121 
122 /*
123  * Tail queue definitions.
124  */
125 #define TAILQ_HEAD(name, type) \
126  struct name { \
127  struct type *tqh_first; /* first element */ \
128  struct type **tqh_last; /* addr of last next element */ \
129  }
130 
131 #define TAILQ_ENTRY(type) \
132  struct { \
133  struct type *tqe_next; /* next element */ \
134  struct type **tqe_prev; /* address of previous next element */ \
135  }
136 
137 /*
138  * Tail queue functions.
139  */
140 #define TAILQ_INIT(head) { \
141  (head)->tqh_first = NULL; \
142  (head)->tqh_last = &(head)->tqh_first; \
143  }
144 
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; \
149  else \
150  (head)->tqh_last = &(elm)->field.tqe_next; \
151  (head)->tqh_first = (elm); \
152  (elm)->field.tqe_prev = &(head)->tqh_first; \
153  }
154 
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; \
160  }
161 
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; \
166  else \
167  (head)->tqh_last = &(elm)->field.tqe_next; \
168  (listelm)->field.tqe_next = (elm); \
169  (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
170  }
171 
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; \
177  }
178 
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; \
183  else \
184  (head)->tqh_last = (elm)->field.tqe_prev; \
185  *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
186  }
187 
188 /*
189  * Circular queue definitions.
190  */
191 #define CIRCLEQ_HEAD(name, type) \
192  struct name { \
193  struct type *cqh_first; /* first element */ \
194  struct type *cqh_last; /* last element */ \
195  }
196 
197 #define CIRCLEQ_ENTRY(type) \
198  struct { \
199  struct type *cqe_next; /* next element */ \
200  struct type *cqe_prev; /* previous element */ \
201  }
202 
203 /*
204  * Circular queue functions.
205  */
206 #define CIRCLEQ_INIT(head) { \
207  (head)->cqh_first = (void *)(head); \
208  (head)->cqh_last = (void *)(head); \
209  }
210 
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); \
216  else \
217  (listelm)->field.cqe_next->field.cqe_prev = (elm); \
218  (listelm)->field.cqe_next = (elm); \
219  }
220 
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); \
226  else \
227  (listelm)->field.cqe_prev->field.cqe_next = (elm); \
228  (listelm)->field.cqe_prev = (elm); \
229  }
230 
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); \
236  else \
237  (head)->cqh_first->field.cqe_prev = (elm); \
238  (head)->cqh_first = (elm); \
239 }
240 
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); \
246  else \
247  (head)->cqh_last->field.cqe_next = (elm); \
248  (head)->cqh_last = (elm); \
249 }
250 
251 #define CIRCLEQ_REMOVE(head, elm, field) { \
252  if ((elm)->field.cqe_next == (void *)(head)) \
253  (head)->cqh_last = (elm)->field.cqe_prev; \
254  else \
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; \
259  else \
260  (elm)->field.cqe_prev->field.cqe_next = \
261  (elm)->field.cqe_next; \
262 }
263 #endif