i3
queue.h
Go to the documentation of this file.
1 /* $OpenBSD: queue.h,v 1.1 2007/10/26 03:14:08 niallo Exp $ */
2 /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3 
4 /*
5  * Copyright (c) 1991, 1993
6  * The Regents of the University of California. All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in the
15  * documentation and/or other materials provided with the distribution.
16  * 3. Neither the name of the University nor the names of its contributors
17  * may be used to endorse or promote products derived from this software
18  * without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  *
32  * @(#)queue.h 8.5 (Berkeley) 8/20/94
33  */
34 
35 #pragma once
36 
37 /*
38  * This file defines five types of data structures: singly-linked lists,
39  * lists, simple queues, tail queues, and circular queues.
40  *
41  *
42  * A singly-linked list is headed by a single forward pointer. The elements
43  * are singly linked for minimum space and pointer manipulation overhead at
44  * the expense of O(n) removal for arbitrary elements. New elements can be
45  * added to the list after an existing element or at the head of the list.
46  * Elements being removed from the head of the list should use the explicit
47  * macro for this purpose for optimum efficiency. A singly-linked list may
48  * only be traversed in the forward direction. Singly-linked lists are ideal
49  * for applications with large datasets and few or no removals or for
50  * implementing a LIFO queue.
51  *
52  * A list is headed by a single forward pointer (or an array of forward
53  * pointers for a hash table header). The elements are doubly linked
54  * so that an arbitrary element can be removed without a need to
55  * traverse the list. New elements can be added to the list before
56  * or after an existing element or at the head of the list. A list
57  * may only be traversed in the forward direction.
58  *
59  * A simple queue is headed by a pair of pointers, one the head of the
60  * list and the other to the tail of the list. The elements are singly
61  * linked to save space, so elements can only be removed from the
62  * head of the list. New elements can be added to the list before or after
63  * an existing element, at the head of the list, or at the end of the
64  * list. A simple queue may only be traversed in the forward direction.
65  *
66  * A tail queue is headed by a pair of pointers, one to the head of the
67  * list and the other to the tail of the list. The elements are doubly
68  * linked so that an arbitrary element can be removed without a need to
69  * traverse the list. New elements can be added to the list before or
70  * after an existing element, at the head of the list, or at the end of
71  * the list. A tail queue may be traversed in either direction.
72  *
73  * A circle queue is headed by a pair of pointers, one to the head of the
74  * list and the other to the tail of the list. The elements are doubly
75  * linked so that an arbitrary element can be removed without a need to
76  * traverse the list. New elements can be added to the list before or after
77  * an existing element, at the head of the list, or at the end of the list.
78  * A circle queue may be traversed in either direction, but has a more
79  * complex end of list detection.
80  *
81  * For details on the use of these macros, see the queue(3) manual page.
82  */
83 
84 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
85 #define _Q_INVALIDATE(a) (a) = ((void *)-1)
86 #else
87 #define _Q_INVALIDATE(a)
88 #endif
89 
90 /*
91  * Singly-linked List definitions.
92  */
93 #define SLIST_HEAD(name, type) \
94 struct name { \
95  struct type *slh_first; /* first element */ \
96 }
97 
98 #define SLIST_HEAD_INITIALIZER(head) \
99  { NULL }
100 
101 #define SLIST_ENTRY(type) \
102 struct { \
103  struct type *sle_next; /* next element */ \
104 }
105 
106 /*
107  * Singly-linked List access methods.
108  */
109 #define SLIST_FIRST(head) ((head)->slh_first)
110 #define SLIST_END(head) NULL
111 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
112 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
113 
114 #define SLIST_FOREACH(var, head, field) \
115  for((var) = SLIST_FIRST(head); \
116  (var) != SLIST_END(head); \
117  (var) = SLIST_NEXT(var, field))
118 
119 #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
120  for ((varp) = &SLIST_FIRST((head)); \
121  ((var) = *(varp)) != SLIST_END(head); \
122  (varp) = &SLIST_NEXT((var), field))
123 
124 /*
125  * Singly-linked List functions.
126  */
127 #define SLIST_INIT(head) { \
128  SLIST_FIRST(head) = SLIST_END(head); \
129 }
130 
131 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
132  (elm)->field.sle_next = (slistelm)->field.sle_next; \
133  (slistelm)->field.sle_next = (elm); \
134 } while (0)
135 
136 #define SLIST_INSERT_HEAD(head, elm, field) do { \
137  (elm)->field.sle_next = (head)->slh_first; \
138  (head)->slh_first = (elm); \
139 } while (0)
140 
141 #define SLIST_REMOVE_NEXT(head, elm, field) do { \
142  (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
143 } while (0)
144 
145 #define SLIST_REMOVE_HEAD(head, field) do { \
146  (head)->slh_first = (head)->slh_first->field.sle_next; \
147 } while (0)
148 
149 #define SLIST_REMOVE(head, elm, type, field) do { \
150  if ((head)->slh_first == (elm)) { \
151  SLIST_REMOVE_HEAD((head), field); \
152  } else { \
153  struct type *curelm = (head)->slh_first; \
154  \
155  while (curelm->field.sle_next != (elm)) \
156  curelm = curelm->field.sle_next; \
157  curelm->field.sle_next = \
158  curelm->field.sle_next->field.sle_next; \
159  _Q_INVALIDATE((elm)->field.sle_next); \
160  } \
161 } while (0)
162 
163 /*
164  * List definitions.
165  */
166 #define LIST_HEAD(name, type) \
167 struct name { \
168  struct type *lh_first; /* first element */ \
169 }
170 
171 #define LIST_HEAD_INITIALIZER(head) \
172  { NULL }
173 
174 #define LIST_ENTRY(type) \
175 struct { \
176  struct type *le_next; /* next element */ \
177  struct type **le_prev; /* address of previous next element */ \
178 }
179 
180 /*
181  * List access methods
182  */
183 #define LIST_FIRST(head) ((head)->lh_first)
184 #define LIST_END(head) NULL
185 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
186 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
187 
188 #define LIST_FOREACH(var, head, field) \
189  for((var) = LIST_FIRST(head); \
190  (var)!= LIST_END(head); \
191  (var) = LIST_NEXT(var, field))
192 
193 /*
194  * List functions.
195  */
196 #define LIST_INIT(head) do { \
197  LIST_FIRST(head) = LIST_END(head); \
198 } while (0)
199 
200 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
201  if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
202  (listelm)->field.le_next->field.le_prev = \
203  &(elm)->field.le_next; \
204  (listelm)->field.le_next = (elm); \
205  (elm)->field.le_prev = &(listelm)->field.le_next; \
206 } while (0)
207 
208 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
209  (elm)->field.le_prev = (listelm)->field.le_prev; \
210  (elm)->field.le_next = (listelm); \
211  *(listelm)->field.le_prev = (elm); \
212  (listelm)->field.le_prev = &(elm)->field.le_next; \
213 } while (0)
214 
215 #define LIST_INSERT_HEAD(head, elm, field) do { \
216  if (((elm)->field.le_next = (head)->lh_first) != NULL) \
217  (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
218  (head)->lh_first = (elm); \
219  (elm)->field.le_prev = &(head)->lh_first; \
220 } while (0)
221 
222 #define LIST_REMOVE(elm, field) do { \
223  if ((elm)->field.le_next != NULL) \
224  (elm)->field.le_next->field.le_prev = \
225  (elm)->field.le_prev; \
226  *(elm)->field.le_prev = (elm)->field.le_next; \
227  _Q_INVALIDATE((elm)->field.le_prev); \
228  _Q_INVALIDATE((elm)->field.le_next); \
229 } while (0)
230 
231 #define LIST_REPLACE(elm, elm2, field) do { \
232  if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
233  (elm2)->field.le_next->field.le_prev = \
234  &(elm2)->field.le_next; \
235  (elm2)->field.le_prev = (elm)->field.le_prev; \
236  *(elm2)->field.le_prev = (elm2); \
237  _Q_INVALIDATE((elm)->field.le_prev); \
238  _Q_INVALIDATE((elm)->field.le_next); \
239 } while (0)
240 
241 /*
242  * Simple queue definitions.
243  */
244 #define SIMPLEQ_HEAD(name, type) \
245 struct name { \
246  struct type *sqh_first; /* first element */ \
247  struct type **sqh_last; /* addr of last next element */ \
248 }
249 
250 #define SIMPLEQ_HEAD_INITIALIZER(head) \
251  { NULL, &(head).sqh_first }
252 
253 #define SIMPLEQ_ENTRY(type) \
254 struct { \
255  struct type *sqe_next; /* next element */ \
256 }
257 
258 /*
259  * Simple queue access methods.
260  */
261 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
262 #define SIMPLEQ_END(head) NULL
263 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
264 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
265 
266 #define SIMPLEQ_FOREACH(var, head, field) \
267  for((var) = SIMPLEQ_FIRST(head); \
268  (var) != SIMPLEQ_END(head); \
269  (var) = SIMPLEQ_NEXT(var, field))
270 
271 /*
272  * Simple queue functions.
273  */
274 #define SIMPLEQ_INIT(head) do { \
275  (head)->sqh_first = NULL; \
276  (head)->sqh_last = &(head)->sqh_first; \
277 } while (0)
278 
279 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
280  if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
281  (head)->sqh_last = &(elm)->field.sqe_next; \
282  (head)->sqh_first = (elm); \
283 } while (0)
284 
285 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
286  (elm)->field.sqe_next = NULL; \
287  *(head)->sqh_last = (elm); \
288  (head)->sqh_last = &(elm)->field.sqe_next; \
289 } while (0)
290 
291 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
292  if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
293  (head)->sqh_last = &(elm)->field.sqe_next; \
294  (listelm)->field.sqe_next = (elm); \
295 } while (0)
296 
297 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
298  if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
299  (head)->sqh_last = &(head)->sqh_first; \
300 } while (0)
301 
302 /*
303  * Tail queue definitions.
304  */
305 #define TAILQ_HEAD(name, type) \
306 struct name { \
307  struct type *tqh_first; /* first element */ \
308  struct type **tqh_last; /* addr of last next element */ \
309 }
310 
311 #define TAILQ_HEAD_INITIALIZER(head) \
312  { NULL, &(head).tqh_first }
313 
314 #define TAILQ_ENTRY(type) \
315 struct { \
316  struct type *tqe_next; /* next element */ \
317  struct type **tqe_prev; /* address of previous next element */ \
318 }
319 
320 /*
321  * tail queue access methods
322  */
323 #define TAILQ_FIRST(head) ((head)->tqh_first)
324 #define TAILQ_END(head) NULL
325 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
326 #define TAILQ_LAST(head, headname) \
327  (*(((struct headname *)((head)->tqh_last))->tqh_last))
328 /* XXX */
329 #define TAILQ_PREV(elm, headname, field) \
330  (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
331 #define TAILQ_EMPTY(head) \
332  (TAILQ_FIRST(head) == TAILQ_END(head))
333 
334 #define TAILQ_FOREACH(var, head, field) \
335  for((var) = TAILQ_FIRST(head); \
336  (var) != TAILQ_END(head); \
337  (var) = TAILQ_NEXT(var, field))
338 
339 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
340  for((var) = TAILQ_LAST(head, headname); \
341  (var) != TAILQ_END(head); \
342  (var) = TAILQ_PREV(var, headname, field))
343 
344 /*
345  * Tail queue functions.
346  */
347 #define TAILQ_INIT(head) do { \
348  (head)->tqh_first = NULL; \
349  (head)->tqh_last = &(head)->tqh_first; \
350 } while (0)
351 
352 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
353  if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
354  (head)->tqh_first->field.tqe_prev = \
355  &(elm)->field.tqe_next; \
356  else \
357  (head)->tqh_last = &(elm)->field.tqe_next; \
358  (head)->tqh_first = (elm); \
359  (elm)->field.tqe_prev = &(head)->tqh_first; \
360 } while (0)
361 
362 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
363  (elm)->field.tqe_next = NULL; \
364  (elm)->field.tqe_prev = (head)->tqh_last; \
365  *(head)->tqh_last = (elm); \
366  (head)->tqh_last = &(elm)->field.tqe_next; \
367 } while (0)
368 
369 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
370  if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
371  (elm)->field.tqe_next->field.tqe_prev = \
372  &(elm)->field.tqe_next; \
373  else \
374  (head)->tqh_last = &(elm)->field.tqe_next; \
375  (listelm)->field.tqe_next = (elm); \
376  (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
377 } while (0)
378 
379 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
380  (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
381  (elm)->field.tqe_next = (listelm); \
382  *(listelm)->field.tqe_prev = (elm); \
383  (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
384 } while (0)
385 
386 #define TAILQ_REMOVE(head, elm, field) do { \
387  if (((elm)->field.tqe_next) != NULL) \
388  (elm)->field.tqe_next->field.tqe_prev = \
389  (elm)->field.tqe_prev; \
390  else \
391  (head)->tqh_last = (elm)->field.tqe_prev; \
392  *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
393  _Q_INVALIDATE((elm)->field.tqe_prev); \
394  _Q_INVALIDATE((elm)->field.tqe_next); \
395 } while (0)
396 
397 #define TAILQ_REPLACE(head, elm, elm2, field) do { \
398  if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
399  (elm2)->field.tqe_next->field.tqe_prev = \
400  &(elm2)->field.tqe_next; \
401  else \
402  (head)->tqh_last = &(elm2)->field.tqe_next; \
403  (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
404  *(elm2)->field.tqe_prev = (elm2); \
405  _Q_INVALIDATE((elm)->field.tqe_prev); \
406  _Q_INVALIDATE((elm)->field.tqe_next); \
407 } while (0)
408 
409 /* Swaps two consecutive elements. 'second' *MUST* follow 'first' */
410 #define TAILQ_SWAP(first, second, head, field) do { \
411  *((first)->field.tqe_prev) = (second); \
412  (second)->field.tqe_prev = (first)->field.tqe_prev; \
413  (first)->field.tqe_prev = &((second)->field.tqe_next); \
414  (first)->field.tqe_next = (second)->field.tqe_next; \
415  if ((second)->field.tqe_next) \
416  (second)->field.tqe_next->field.tqe_prev = &((first)->field.tqe_next); \
417  (second)->field.tqe_next = first; \
418  if ((head)->tqh_last == &((second)->field.tqe_next)) \
419  (head)->tqh_last = &((first)->field.tqe_next); \
420 } while (0)
421 
422 /*
423  * Circular queue definitions.
424  */
425 #define CIRCLEQ_HEAD(name, type) \
426 struct name { \
427  struct type *cqh_first; /* first element */ \
428  struct type *cqh_last; /* last element */ \
429 }
430 
431 #define CIRCLEQ_HEAD_INITIALIZER(head) \
432  { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
433 
434 #define CIRCLEQ_ENTRY(type) \
435 struct { \
436  struct type *cqe_next; /* next element */ \
437  struct type *cqe_prev; /* previous element */ \
438 }
439 
440 /*
441  * Circular queue access methods
442  */
443 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
444 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
445 #define CIRCLEQ_END(head) ((void *)(head))
446 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
447 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
448 #define CIRCLEQ_EMPTY(head) \
449  (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
450 
451 #define CIRCLEQ_FOREACH(var, head, field) \
452  for((var) = CIRCLEQ_FIRST(head); \
453  (var) != CIRCLEQ_END(head); \
454  (var) = CIRCLEQ_NEXT(var, field))
455 
456 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
457  for((var) = CIRCLEQ_LAST(head); \
458  (var) != CIRCLEQ_END(head); \
459  (var) = CIRCLEQ_PREV(var, field))
460 
461 /*
462  * Circular queue functions.
463  */
464 #define CIRCLEQ_INIT(head) do { \
465  (head)->cqh_first = CIRCLEQ_END(head); \
466  (head)->cqh_last = CIRCLEQ_END(head); \
467 } while (0)
468 
469 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
470  (elm)->field.cqe_next = (listelm)->field.cqe_next; \
471  (elm)->field.cqe_prev = (listelm); \
472  if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
473  (head)->cqh_last = (elm); \
474  else \
475  (listelm)->field.cqe_next->field.cqe_prev = (elm); \
476  (listelm)->field.cqe_next = (elm); \
477 } while (0)
478 
479 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
480  (elm)->field.cqe_next = (listelm); \
481  (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
482  if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
483  (head)->cqh_first = (elm); \
484  else \
485  (listelm)->field.cqe_prev->field.cqe_next = (elm); \
486  (listelm)->field.cqe_prev = (elm); \
487 } while (0)
488 
489 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
490  (elm)->field.cqe_next = (head)->cqh_first; \
491  (elm)->field.cqe_prev = CIRCLEQ_END(head); \
492  if ((head)->cqh_last == CIRCLEQ_END(head)) \
493  (head)->cqh_last = (elm); \
494  else \
495  (head)->cqh_first->field.cqe_prev = (elm); \
496  (head)->cqh_first = (elm); \
497 } while (0)
498 
499 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
500  (elm)->field.cqe_next = CIRCLEQ_END(head); \
501  (elm)->field.cqe_prev = (head)->cqh_last; \
502  if ((head)->cqh_first == CIRCLEQ_END(head)) \
503  (head)->cqh_first = (elm); \
504  else \
505  (head)->cqh_last->field.cqe_next = (elm); \
506  (head)->cqh_last = (elm); \
507 } while (0)
508 
509 #define CIRCLEQ_REMOVE(head, elm, field) do { \
510  if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
511  (head)->cqh_last = (elm)->field.cqe_prev; \
512  else \
513  (elm)->field.cqe_next->field.cqe_prev = \
514  (elm)->field.cqe_prev; \
515  if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
516  (head)->cqh_first = (elm)->field.cqe_next; \
517  else \
518  (elm)->field.cqe_prev->field.cqe_next = \
519  (elm)->field.cqe_next; \
520  _Q_INVALIDATE((elm)->field.cqe_prev); \
521  _Q_INVALIDATE((elm)->field.cqe_next); \
522 } while (0)
523 
524 #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
525  if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
526  CIRCLEQ_END(head)) \
527  (head)->cqh_last = (elm2); \
528  else \
529  (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
530  if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
531  CIRCLEQ_END(head)) \
532  (head)->cqh_first = (elm2); \
533  else \
534  (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
535  _Q_INVALIDATE((elm)->field.cqe_prev); \
536  _Q_INVALIDATE((elm)->field.cqe_next); \
537 } while (0)