1303233Sdim/*-
2303233Sdim * Copyright (c) 1991, 1993
3303233Sdim *	The Regents of the University of California.  All rights reserved.
4303233Sdim *
5303233Sdim * Redistribution and use in source and binary forms, with or without
6303233Sdim * modification, are permitted provided that the following conditions
7303233Sdim * are met:
8303233Sdim * 1. Redistributions of source code must retain the above copyright
9303233Sdim *    notice, this list of conditions and the following disclaimer.
10303233Sdim * 2. Redistributions in binary form must reproduce the above copyright
11303233Sdim *    notice, this list of conditions and the following disclaimer in the
12303233Sdim *    documentation and/or other materials provided with the distribution.
13303233Sdim * 4. Neither the name of the University nor the names of its contributors
14303233Sdim *    may be used to endorse or promote products derived from this software
15303233Sdim *    without specific prior written permission.
16303233Sdim *
17303233Sdim * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18303233Sdim * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19303233Sdim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20303233Sdim * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21303233Sdim * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22303233Sdim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23303233Sdim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24303233Sdim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25303233Sdim * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26303233Sdim * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27303233Sdim * SUCH DAMAGE.
28303233Sdim *
29303233Sdim *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30303233Sdim * $FreeBSD: src/sys/sys/queue.h,v 1.68 2006/10/24 11:20:29 ru Exp $
31303233Sdim */
32303233Sdim
33303233Sdim#ifndef _SYS_QUEUE_H_
34303233Sdim#define	_SYS_QUEUE_H_
35303233Sdim
36303233Sdim#include <sys/cdefs.h>
37303233Sdim
38303233Sdim/*
39303233Sdim * This file defines four types of data structures: singly-linked lists,
40303233Sdim * singly-linked tail queues, lists and tail queues.
41303233Sdim *
42303233Sdim * A singly-linked list is headed by a single forward pointer. The elements
43316423Sdim * are singly linked for minimum space and pointer manipulation overhead at
44303233Sdim * the expense of O(n) removal for arbitrary elements. New elements can be
45316423Sdim * added to the list after an existing element or at the head of the list.
46303233Sdim * Elements being removed from the head of the list should use the explicit
47316423Sdim * macro for this purpose for optimum efficiency. A singly-linked list may
48316423Sdim * only be traversed in the forward direction.  Singly-linked lists are ideal
49303233Sdim * for applications with large datasets and few or no removals or for
50303233Sdim * implementing a LIFO queue.
51303233Sdim *
52324023Sdim * A singly-linked tail queue is headed by a pair of pointers, one to the
53324023Sdim * head of the list and the other to the tail of the list. The elements are
54324023Sdim * singly linked for minimum space and pointer manipulation overhead at the
55324023Sdim * expense of O(n) removal for arbitrary elements. New elements can be added
56324023Sdim * to the list after an existing element, at the head of the list, or at the
57324023Sdim * end of the list. Elements being removed from the head of the tail queue
58324023Sdim * should use the explicit macro for this purpose for optimum efficiency.
59324023Sdim * A singly-linked tail queue may only be traversed in the forward direction.
60324023Sdim * Singly-linked tail queues are ideal for applications with large datasets
61324023Sdim * and few or no removals or for implementing a FIFO queue.
62324023Sdim *
63324023Sdim * A list is headed by a single forward pointer (or an array of forward
64324023Sdim * pointers for a hash table header). The elements are doubly linked
65324023Sdim * so that an arbitrary element can be removed without a need to
66324023Sdim * traverse the list. New elements can be added to the list before
67324023Sdim * or after an existing element or at the head of the list. A list
68324023Sdim * may only be traversed in the forward direction.
69324023Sdim *
70324023Sdim * A tail queue is headed by a pair of pointers, one to the head of the
71324023Sdim * list and the other to the tail of the list. The elements are doubly
72324023Sdim * linked so that an arbitrary element can be removed without a need to
73324023Sdim * traverse the list. New elements can be added to the list before or
74324023Sdim * after an existing element, at the head of the list, or at the end of
75324023Sdim * the list. A tail queue may be traversed in either direction.
76324023Sdim *
77324023Sdim * For details on the use of these macros, see the queue(3) manual page.
78324023Sdim *
79324023Sdim *
80324023Sdim *				SLIST	LIST	STAILQ	TAILQ
81324023Sdim * _HEAD			+	+	+	+
82324023Sdim * _HEAD_INITIALIZER		+	+	+	+
83324023Sdim * _ENTRY			+	+	+	+
84324023Sdim * _INIT			+	+	+	+
85324023Sdim * _EMPTY			+	+	+	+
86324023Sdim * _FIRST			+	+	+	+
87303233Sdim * _NEXT			+	+	+	+
88303233Sdim * _PREV			-	-	-	+
89303233Sdim * _LAST			-	-	+	+
90303233Sdim * _FOREACH			+	+	+	+
91316423Sdim * _FOREACH_SAFE		+	+	+	+
92316423Sdim * _FOREACH_REVERSE		-	-	-	+
93303233Sdim * _FOREACH_REVERSE_SAFE	-	-	-	+
94303233Sdim * _INSERT_HEAD			+	+	+	+
95324023Sdim * _INSERT_BEFORE		-	+	-	+
96324023Sdim * _INSERT_AFTER		+	+	+	+
97324023Sdim * _INSERT_TAIL			-	-	+	+
98324023Sdim * _CONCAT			-	-	+	+
99303233Sdim * _REMOVE_HEAD			+	-	+	-
100303233Sdim * _REMOVE			+	+	+	+
101303233Sdim *
102303233Sdim */
103303233Sdim#ifdef QUEUE_MACRO_DEBUG
104303233Sdim/* Store the last 2 places the queue element or head was altered */
105303233Sdimstruct qm_trace {
106303233Sdim	char * lastfile;
107303233Sdim	int lastline;
108303233Sdim	char * prevfile;
109303233Sdim	int prevline;
110303233Sdim};
111303233Sdim
112303233Sdim#define	TRACEBUF	struct qm_trace trace;
113303233Sdim#define	TRASHIT(x)	do {(x) = (void *)-1;} while (0)
114303233Sdim
115303233Sdim#define	QMD_TRACE_HEAD(head) do {					\
116303233Sdim	(head)->trace.prevline = (head)->trace.lastline;		\
117316423Sdim	(head)->trace.prevfile = (head)->trace.lastfile;		\
118