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  { \
129  SLIST_FIRST(head) = SLIST_END(head); \
130  }
131 
132 #define SLIST_INSERT_AFTER(slistelm, elm, field) \
133  do { \
134  (elm)->field.sle_next = (slistelm)->field.sle_next; \
135  (slistelm)->field.sle_next = (elm); \
136  } while (0)
137 
138 #define SLIST_INSERT_HEAD(head, elm, field) \
139  do { \
140  (elm)->field.sle_next = (head)->slh_first; \
141  (head)->slh_first = (elm); \
142  } while (0)
143 
144 #define SLIST_REMOVE_NEXT(head, elm, field) \
145  do { \
146  (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
147  } while (0)
148 
149 #define SLIST_REMOVE_HEAD(head, field) \
150  do { \
151  (head)->slh_first = (head)->slh_first->field.sle_next; \
152  } while (0)
153 
154 #define SLIST_REMOVE(head, elm, type, field) \
155  do { \
156  if ((head)->slh_first == (elm)) { \
157  SLIST_REMOVE_HEAD((head), field); \
158  } else { \
159  struct type *curelm = (head)->slh_first; \
160  \
161  while (curelm->field.sle_next != (elm)) \
162  curelm = curelm->field.sle_next; \
163  curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \
164  _Q_INVALIDATE((elm)->field.sle_next); \
165  } \
166  } while (0)
167 
168 /*
169  * List definitions.
170  */
171 #define LIST_HEAD(name, type) \
172  struct name { \
173  struct type *lh_first; /* first element */ \
174  }
175 
176 #define LIST_HEAD_INITIALIZER(head) \
177  { NULL }
178 
179 #define LIST_ENTRY(type) \
180  struct { \
181  struct type *le_next; /* next element */ \
182  struct type **le_prev; /* address of previous next element */ \
183  }
184 
185 /*
186  * List access methods
187  */
188 #define LIST_FIRST(head) ((head)->lh_first)
189 #define LIST_END(head) NULL
190 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
191 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
192 
193 #define LIST_FOREACH(var, head, field) \
194  for ((var) = LIST_FIRST(head); \
195  (var) != LIST_END(head); \
196  (var) = LIST_NEXT(var, field))
197 
198 /*
199  * List functions.
200  */
201 #define LIST_INIT(head) \
202  do { \
203  LIST_FIRST(head) = LIST_END(head); \
204  } while (0)
205 
206 #define LIST_INSERT_AFTER(listelm, elm, field) \
207  do { \
208  if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
209  (listelm)->field.le_next->field.le_prev = &(elm)->field.le_next; \
210  (listelm)->field.le_next = (elm); \
211  (elm)->field.le_prev = &(listelm)->field.le_next; \
212  } while (0)
213 
214 #define LIST_INSERT_BEFORE(listelm, elm, field) \
215  do { \
216  (elm)->field.le_prev = (listelm)->field.le_prev; \
217  (elm)->field.le_next = (listelm); \
218  *(listelm)->field.le_prev = (elm); \
219  (listelm)->field.le_prev = &(elm)->field.le_next; \
220  } while (0)
221 
222 #define LIST_INSERT_HEAD(head, elm, field) \
223  do { \
224  if (((elm)->field.le_next = (head)->lh_first) != NULL) \
225  (head)->lh_first->field.le_prev = &(elm)->field.le_next; \
226  (head)->lh_first = (elm); \
227  (elm)->field.le_prev = &(head)->lh_first; \
228  } while (0)
229 
230 #define LIST_REMOVE(elm, field) \
231  do { \
232  if ((elm)->field.le_next != NULL) \
233  (elm)->field.le_next->field.le_prev = (elm)->field.le_prev; \
234  *(elm)->field.le_prev = (elm)->field.le_next; \
235  _Q_INVALIDATE((elm)->field.le_prev); \
236  _Q_INVALIDATE((elm)->field.le_next); \
237  } while (0)
238 
239 #define LIST_REPLACE(elm, elm2, field) \
240  do { \
241  if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
242  (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next; \
243  (elm2)->field.le_prev = (elm)->field.le_prev; \
244  *(elm2)->field.le_prev = (elm2); \
245  _Q_INVALIDATE((elm)->field.le_prev); \
246  _Q_INVALIDATE((elm)->field.le_next); \
247  } while (0)
248 
249 /*
250  * Simple queue definitions.
251  */
252 #define SIMPLEQ_HEAD(name, type) \
253  struct name { \
254  struct type *sqh_first; /* first element */ \
255  struct type **sqh_last; /* addr of last next element */ \
256  }
257 
258 #define SIMPLEQ_HEAD_INITIALIZER(head) \
259  { NULL, &(head).sqh_first }
260 
261 #define SIMPLEQ_ENTRY(type) \
262  struct { \
263  struct type *sqe_next; /* next element */ \
264  }
265 
266 /*
267  * Simple queue access methods.
268  */
269 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
270 #define SIMPLEQ_END(head) NULL
271 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
272 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
273 
274 #define SIMPLEQ_FOREACH(var, head, field) \
275  for ((var) = SIMPLEQ_FIRST(head); \
276  (var) != SIMPLEQ_END(head); \
277  (var) = SIMPLEQ_NEXT(var, field))
278 
279 /*
280  * Simple queue functions.
281  */
282 #define SIMPLEQ_INIT(head) \
283  do { \
284  (head)->sqh_first = NULL; \
285  (head)->sqh_last = &(head)->sqh_first; \
286  } while (0)
287 
288 #define SIMPLEQ_INSERT_HEAD(head, elm, field) \
289  do { \
290  if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
291  (head)->sqh_last = &(elm)->field.sqe_next; \
292  (head)->sqh_first = (elm); \
293  } while (0)
294 
295 #define SIMPLEQ_INSERT_TAIL(head, elm, field) \
296  do { \
297  (elm)->field.sqe_next = NULL; \
298  *(head)->sqh_last = (elm); \
299  (head)->sqh_last = &(elm)->field.sqe_next; \
300  } while (0)
301 
302 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) \
303  do { \
304  if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
305  (head)->sqh_last = &(elm)->field.sqe_next; \
306  (listelm)->field.sqe_next = (elm); \
307  } while (0)
308 
309 #define SIMPLEQ_REMOVE_HEAD(head, field) \
310  do { \
311  if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
312  (head)->sqh_last = &(head)->sqh_first; \
313  } while (0)
314 
315 /*
316  * Tail queue definitions.
317  */
318 #define TAILQ_HEAD(name, type) \
319  struct name { \
320  struct type *tqh_first; /* first element */ \
321  struct type **tqh_last; /* addr of last next element */ \
322  }
323 
324 #define TAILQ_HEAD_INITIALIZER(head) \
325  { NULL, &(head).tqh_first }
326 
327 #define TAILQ_ENTRY(type) \
328  struct { \
329  struct type *tqe_next; /* next element */ \
330  struct type **tqe_prev; /* address of previous next element */ \
331  }
332 
333 /*
334  * tail queue access methods
335  */
336 #define TAILQ_FIRST(head) ((head)->tqh_first)
337 #define TAILQ_END(head) NULL
338 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
339 #define TAILQ_LAST(head, headname) \
340  (*(((struct headname *)((head)->tqh_last))->tqh_last))
341 /* XXX */
342 #define TAILQ_PREV(elm, headname, field) \
343  (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
344 #define TAILQ_EMPTY(head) \
345  (TAILQ_FIRST(head) == TAILQ_END(head))
346 
347 #define TAILQ_FOREACH(var, head, field) \
348  for ((var) = TAILQ_FIRST(head); \
349  (var) != TAILQ_END(head); \
350  (var) = TAILQ_NEXT(var, field))
351 
352 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
353  for ((var) = TAILQ_LAST(head, headname); \
354  (var) != TAILQ_END(head); \
355  (var) = TAILQ_PREV(var, headname, field))
356 
357 /*
358  * Tail queue functions.
359  */
360 #define TAILQ_INIT(head) \
361  do { \
362  (head)->tqh_first = NULL; \
363  (head)->tqh_last = &(head)->tqh_first; \
364  } while (0)
365 
366 #define TAILQ_INSERT_HEAD(head, elm, field) \
367  do { \
368  if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
369  (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \
370  else \
371  (head)->tqh_last = &(elm)->field.tqe_next; \
372  (head)->tqh_first = (elm); \
373  (elm)->field.tqe_prev = &(head)->tqh_first; \
374  } while (0)
375 
376 #define TAILQ_INSERT_TAIL(head, elm, field) \
377  do { \
378  (elm)->field.tqe_next = NULL; \
379  (elm)->field.tqe_prev = (head)->tqh_last; \
380  *(head)->tqh_last = (elm); \
381  (head)->tqh_last = &(elm)->field.tqe_next; \
382  } while (0)
383 
384 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) \
385  do { \
386  if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL) \
387  (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \
388  else \
389  (head)->tqh_last = &(elm)->field.tqe_next; \
390  (listelm)->field.tqe_next = (elm); \
391  (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
392  } while (0)
393 
394 #define TAILQ_INSERT_BEFORE(listelm, elm, field) \
395  do { \
396  (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
397  (elm)->field.tqe_next = (listelm); \
398  *(listelm)->field.tqe_prev = (elm); \
399  (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
400  } while (0)
401 
402 #define TAILQ_REMOVE(head, elm, field) \
403  do { \
404  if (((elm)->field.tqe_next) != NULL) \
405  (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \
406  else \
407  (head)->tqh_last = (elm)->field.tqe_prev; \
408  *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
409  _Q_INVALIDATE((elm)->field.tqe_prev); \
410  _Q_INVALIDATE((elm)->field.tqe_next); \
411  } while (0)
412 
413 #define TAILQ_REPLACE(head, elm, elm2, field) \
414  do { \
415  if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
416  (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next; \
417  else \
418  (head)->tqh_last = &(elm2)->field.tqe_next; \
419  (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
420  *(elm2)->field.tqe_prev = (elm2); \
421  _Q_INVALIDATE((elm)->field.tqe_prev); \
422  _Q_INVALIDATE((elm)->field.tqe_next); \
423  } while (0)
424 
425 /* Swaps two consecutive elements. 'second' *MUST* follow 'first' */
426 #define TAILQ_SWAP(first, second, head, field) \
427  do { \
428  *((first)->field.tqe_prev) = (second); \
429  (second)->field.tqe_prev = (first)->field.tqe_prev; \
430  (first)->field.tqe_prev = &((second)->field.tqe_next); \
431  (first)->field.tqe_next = (second)->field.tqe_next; \
432  if ((second)->field.tqe_next) \
433  (second)->field.tqe_next->field.tqe_prev = &((first)->field.tqe_next); \
434  (second)->field.tqe_next = first; \
435  if ((head)->tqh_last == &((second)->field.tqe_next)) \
436  (head)->tqh_last = &((first)->field.tqe_next); \
437  } while (0)
438 
439 /*
440  * Circular queue definitions.
441  */
442 #define CIRCLEQ_HEAD(name, type) \
443  struct name { \
444  struct type *cqh_first; /* first element */ \
445  struct type *cqh_last; /* last element */ \
446  }
447 
448 #define CIRCLEQ_HEAD_INITIALIZER(head) \
449  { \
450  CIRCLEQ_END(&head) \
451  , CIRCLEQ_END(&head) \
452  }
453 
454 #define CIRCLEQ_ENTRY(type) \
455  struct { \
456  struct type *cqe_next; /* next element */ \
457  struct type *cqe_prev; /* previous element */ \
458  }
459 
460 /*
461  * Circular queue access methods
462  */
463 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
464 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
465 #define CIRCLEQ_END(head) ((void *)(head))
466 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
467 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
468 #define CIRCLEQ_EMPTY(head) \
469  (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
470 
471 #define CIRCLEQ_FOREACH(var, head, field) \
472  for ((var) = CIRCLEQ_FIRST(head); \
473  (var) != CIRCLEQ_END(head); \
474  (var) = CIRCLEQ_NEXT(var, field))
475 
476 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
477  for ((var) = CIRCLEQ_LAST(head); \
478  (var) != CIRCLEQ_END(head); \
479  (var) = CIRCLEQ_PREV(var, field))
480 
481 /*
482  * Circular queue functions.
483  */
484 #define CIRCLEQ_INIT(head) \
485  do { \
486  (head)->cqh_first = CIRCLEQ_END(head); \
487  (head)->cqh_last = CIRCLEQ_END(head); \
488  } while (0)
489 
490 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) \
491  do { \
492  (elm)->field.cqe_next = (listelm)->field.cqe_next; \
493  (elm)->field.cqe_prev = (listelm); \
494  if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
495  (head)->cqh_last = (elm); \
496  else \
497  (listelm)->field.cqe_next->field.cqe_prev = (elm); \
498  (listelm)->field.cqe_next = (elm); \
499  } while (0)
500 
501 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) \
502  do { \
503  (elm)->field.cqe_next = (listelm); \
504  (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
505  if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
506  (head)->cqh_first = (elm); \
507  else \
508  (listelm)->field.cqe_prev->field.cqe_next = (elm); \
509  (listelm)->field.cqe_prev = (elm); \
510  } while (0)
511 
512 #define CIRCLEQ_INSERT_HEAD(head, elm, field) \
513  do { \
514  (elm)->field.cqe_next = (head)->cqh_first; \
515  (elm)->field.cqe_prev = CIRCLEQ_END(head); \
516  if ((head)->cqh_last == CIRCLEQ_END(head)) \
517  (head)->cqh_last = (elm); \
518  else \
519  (head)->cqh_first->field.cqe_prev = (elm); \
520  (head)->cqh_first = (elm); \
521  } while (0)
522 
523 #define CIRCLEQ_INSERT_TAIL(head, elm, field) \
524  do { \
525  (elm)->field.cqe_next = CIRCLEQ_END(head); \
526  (elm)->field.cqe_prev = (head)->cqh_last; \
527  if ((head)->cqh_first == CIRCLEQ_END(head)) \
528  (head)->cqh_first = (elm); \
529  else \
530  (head)->cqh_last->field.cqe_next = (elm); \
531  (head)->cqh_last = (elm); \
532  } while (0)
533 
534 #define CIRCLEQ_REMOVE(head, elm, field) \
535  do { \
536  if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
537  (head)->cqh_last = (elm)->field.cqe_prev; \
538  else \
539  (elm)->field.cqe_next->field.cqe_prev = (elm)->field.cqe_prev; \
540  if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
541  (head)->cqh_first = (elm)->field.cqe_next; \
542  else \
543  (elm)->field.cqe_prev->field.cqe_next = (elm)->field.cqe_next; \
544  _Q_INVALIDATE((elm)->field.cqe_prev); \
545  _Q_INVALIDATE((elm)->field.cqe_next); \
546  } while (0)
547 
548 #define CIRCLEQ_REPLACE(head, elm, elm2, field) \
549  do { \
550  if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == CIRCLEQ_END(head)) \
551  (head)->cqh_last = (elm2); \
552  else \
553  (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
554  if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == CIRCLEQ_END(head)) \
555  (head)->cqh_first = (elm2); \
556  else \
557  (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
558  _Q_INVALIDATE((elm)->field.cqe_prev); \
559  _Q_INVALIDATE((elm)->field.cqe_next); \
560  } while (0)
Generated by   doxygen 1.8.13