fanf 00/09/07 03:16:58
Modified: src/include bsd_queue.h
Log:
Throw away the macros that we don't need, and include the relevant bit
of the manual page.
Revision Changes Path
1.3 +139 -427 apache-2.0/src/include/bsd_queue.h
Index: bsd_queue.h
===================================================================
RCS file: /home/cvs/apache-2.0/src/include/bsd_queue.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -u -r1.2 -r1.3
--- bsd_queue.h 2000/09/07 10:03:44 1.2
+++ bsd_queue.h 2000/09/07 10:16:57 1.3
@@ -34,395 +34,151 @@
* $FreeBSD: src/sys/sys/queue.h,v 1.40 2000/08/03 17:31:56 hsu Exp $
*/
-#ifndef _SYS_QUEUE_H_
-#define _SYS_QUEUE_H_
+#ifndef BSD_QUEUE_H
+#define BSD_QUEUE_H
-#include <struct.h>
-
/*
- * This file defines five types of data structures: singly-linked lists,
- * singly-linked tail queues, lists, tail queues, and circular queues.
+ * This file defines macros for circular queues.
*
- * A singly-linked list is headed by a single forward pointer. The elements
- * are singly linked for minimum space and pointer manipulation overhead at
- * the expense of O(n) removal for arbitrary elements. New elements can be
- * added to the list after an existing element or at the head of the list.
- * Elements being removed from the head of the list should use the explicit
- * macro for this purpose for optimum efficiency. A singly-linked list may
- * only be traversed in the forward direction. Singly-linked lists are ideal
- * for applications with large datasets and few or no removals or for
- * implementing a LIFO queue.
- *
- * A singly-linked tail queue is headed by a pair of pointers, one to the
- * head of the list and the other to the tail of the list. The elements are
- * singly linked for minimum space and pointer manipulation overhead at the
- * expense of O(n) removal for arbitrary elements. New elements can be added
- * to the list after an existing element, at the head of the list, or at the
- * end of the list. Elements being removed from the head of the tail queue
- * should use the explicit macro for this purpose for optimum efficiency.
- * A singly-linked tail queue may only be traversed in the forward direction.
- * Singly-linked tail queues are ideal for applications with large datasets
- * and few or no removals or for implementing a FIFO queue.
- *
- * A list is headed by a single forward pointer (or an array of forward
- * pointers for a hash table header). The elements are doubly linked
- * so that an arbitrary element can be removed without a need to
- * traverse the list. New elements can be added to the list before
- * or after an existing element or at the head of the list. A list
- * may only be traversed in the forward direction.
- *
- * A tail queue is headed by a pair of pointers, one to the head of the
- * list and the other to the tail of the list. The elements are doubly
- * linked so that an arbitrary element can be removed without a need to
- * traverse the list. New elements can be added to the list before or
- * after an existing element, at the head of the list, or at the end of
- * the list. A tail queue may be traversed in either direction. Tail
- * queues may be concatenated.
- *
- * A circle queue is headed by a pair of pointers, one to the head of the
- * list and the other to the tail of the list. The elements are doubly
- * linked so that an arbitrary element can be removed without a need to
- * traverse the list. New elements can be added to the list before or after
- * an existing element, at the head of the list, or at the end of the list.
- * A circle queue may be traversed in either direction, but has a more
- * complex end of list detection. Circle queues may be concatenated.
- *
- * For details on the use of these macros, see the queue(3) manual page.
- *
- *
- * SLIST LIST STAILQ TAILQ CIRCLEQ
- * _HEAD + + + + +
- * _HEAD_INITIALIZER + + + + +
- * _ENTRY + + + + +
- * _INIT + + + + +
- * _EMPTY + + + + +
- * _FIRST + + + + +
- * _NEXT + + + + +
- * _PREV - - - + +
- * _LAST - - + + +
- * _FOREACH + + + + +
- * _FOREACH_REVERSE - - - + +
- * _INSERT_HEAD + + + + +
- * _INSERT_BEFORE - + - + +
- * _INSERT_AFTER + + + + +
- * _INSERT_TAIL - - + + +
- * _REMOVE_HEAD + - + - -
- * _REMOVE + + + + +
- * _CONCAT - - - + +
+ * The queue(3) manual page says:
*
+ * CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head)
+ *
+ * CIRCLEQ_ENTRY(TYPE)
+ *
+ * CIRCLEQ_FIRST(CIRCLEQ_HEAD *head)
+ *
+ * CIRCLEQ_FOREACH(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_FOREACH_REVERSE(TYPE *var, CIRCLEQ_HEAD *head,
+ * CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_HEAD(HEADNAME, TYPE)
+ *
+ * CIRCLEQ_INIT(CIRCLEQ_HEAD *head)
+ *
+ * CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
+ * CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm,
+ * CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_LAST(CIRCLEQ_HEAD *head)
+ *
+ * CIRCLEQ_NEXT(TYPE *elm, CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLE_PREV(TYPE *elm, CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME)
+ *
+ * CIRCLEQ_CONCAT(CIRCLEQ_HEAD *queue1, CIRCLEQ_HEAD *queue2,
+ * CIRCLEQ_ENTRY NAME)
+ *
+ * DESCRIPTION
+ *
+ * A circular queue is headed by a structure defined by the CIRCLEQ_HEAD
+ * macro. This structure contains a pair of pointers, one to the first
ele-
+ * ment in the circular queue and the other to the last element in the cir-
+ * cular queue. The elements are doubly linked so that an arbitrary
element
+ * can be removed without traversing the queue. New elements can be added
+ * to the queue after an existing element, before an existing element, at
+ * the head of the queue, or at the end of the queue. A CIRCLEQ_HEAD
struc-
+ * ture is declared as follows:
+ *
+ * CIRCLEQ_HEAD(HEADNAME, TYPE) head;
+ *
+ * where HEADNAME is the name of the structure to be defined, and TYPE is
+ * the type of the elements to be linked into the circular queue. A
pointer
+ * to the head of the circular queue can later be declared as:
+ *
+ * struct HEADNAME *headp;
+ *
+ * (The names head and headp are user selectable.)
+ *
+ * The macro CIRCLEQ_EMPTY evaluates to true if there are no items on the
+ * circle queue.
+ *
+ * The macro CIRCLEQ_ENTRY declares a structure that connects the elements
+ * in the circular queue.
+ *
+ * The macro CIRCLEQ_FIRST returns the first item on the circle queue.
+ *
+ * The macro CICRLEQ_FOREACH traverses the circle queue referenced by head
+ * in the forward direction, assigning each element in turn to var.
+ *
+ * The macro CICRLEQ_FOREACH_REVERSE traverses the circle queue referenced
+ * by head in the reverse direction, assigning each element in turn to var.
+ *
+ * The macro CIRCLEQ_INIT initializes the circular queue referenced by
head.
+ *
+ * The macro CIRCLEQ_INSERT_HEAD inserts the new element elm at the head of
+ * the circular queue.
+ *
+ * The macro CIRCLEQ_INSERT_TAIL inserts the new element elm at the end of
+ * the circular queue.
+ *
+ * The macro CIRCLEQ_INSERT_AFTER inserts the new element elm after the
ele-
+ * ment listelm.
+ *
+ * The macro CIRCLEQ_INSERT_BEFORE inserts the new element elm before the
+ * element listelm.
+ *
+ * The macro CIRCLEQ_LAST returns the last item on the circle queue.
+ *
+ * EXAMPLE
+ *
+ * CIRCLEQ_HEAD(circleq, entry) head;
+ * struct circleq *headp; // Circular queue head.
+ * struct entry {
+ * ...
+ * CIRCLEQ_ENTRY(entry) entries; // Circular queue.
+ * ...
+ * } *n1, *n2, *np;
+ *
+ * CIRCLEQ_INIT(&head); // Initialize the circular
queue.
+ *
+ * n1 = malloc(sizeof(struct entry)); // Insert at the head.
+ * CIRCLEQ_INSERT_HEAD(&head, n1, entries);
+ *
+ * n1 = malloc(sizeof(struct entry)); // Insert at the tail.
+ * CIRCLEQ_INSERT_TAIL(&head, n1, entries);
+ *
+ * n2 = malloc(sizeof(struct entry)); // Insert after.
+ * CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
+ *
+ * n2 = malloc(sizeof(struct entry)); // Insert before.
+ * CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
+ *
+ * CIRCLEQ_REMOVE(&head, n1, entries); // Deletion.
+ * free(n1);
+ * // Forward traversal.
+ * CIRCLEQ_FOREACH(np, &head, entries)
+ * np-> ...
+ * // Reverse traversal.
+ * CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
+ * np-> ...
+ * // CircleQ Deletion.
+ * while (CIRCLEQ_FIRST(&head) != (void *)&head) {
+ * n1 = CIRCLEQ_HEAD(&head);
+ * CIRCLEQ_REMOVE(&head, n1, entries);
+ * free(n1);
+ * }
+ * // Faster CircleQ Deletion.
+ * n1 = CIRCLEQ_FIRST(&head);
+ * while (n1 != (void *)&head) {
+ * n2 = CIRCLEQ_NEXT(n1, entries);
+ * free(n1);
+ * n1 = n2;
+ * }
+ * CIRCLEQ_INIT(&head);
+ *
*/
/*
- * Singly-linked List declarations.
- */
-#define SLIST_HEAD(name, type)
\
-struct name {
\
- struct type *slh_first; /* first element */ \
-}
-
-#define SLIST_HEAD_INITIALIZER(head)
\
- { NULL }
-
-#define SLIST_ENTRY(type)
\
-struct { \
- struct type *sle_next; /* next element */ \
-}
-
-/*
- * Singly-linked List functions.
- */
-#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
-
-#define SLIST_FIRST(head) ((head)->slh_first)
-
-#define SLIST_FOREACH(var, head, field)
\
- for ((var) = SLIST_FIRST((head)); \
- (var); \
- (var) = SLIST_NEXT((var), field))
-
-#define SLIST_INIT(head) do {
\
- SLIST_FIRST((head)) = NULL; \
-} while (0)
-
-#define SLIST_INSERT_AFTER(slistelm, elm, field) do {
\
- SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
- SLIST_NEXT((slistelm), field) = (elm); \
-} while (0)
-
-#define SLIST_INSERT_HEAD(head, elm, field) do {
\
- SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
- SLIST_FIRST((head)) = (elm); \
-} while (0)
-
-#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
-
-#define SLIST_REMOVE(head, elm, type, field) do {
\
- if (SLIST_FIRST((head)) == (elm)) { \
- SLIST_REMOVE_HEAD((head), field); \
- } \
- else { \
- struct type *curelm = SLIST_FIRST((head)); \
- while (SLIST_NEXT(curelm, field) != (elm)) \
- curelm = SLIST_NEXT(curelm, field); \
- SLIST_NEXT(curelm, field) = \
- SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
- } \
-} while (0)
-
-#define SLIST_REMOVE_HEAD(head, field) do {
\
- SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
-} while (0)
-
-/*
- * Singly-linked Tail queue declarations.
- */
-#define STAILQ_HEAD(name, type)
\
-struct name {
\
- struct type *stqh_first;/* first element */ \
- struct type **stqh_last;/* addr of last next element */ \
-}
-
-#define STAILQ_HEAD_INITIALIZER(head)
\
- { NULL, &(head).stqh_first }
-
-#define STAILQ_ENTRY(type)
\
-struct { \
- struct type *stqe_next; /* next element */ \
-}
-
-/*
- * Singly-linked Tail queue functions.
- */
-#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
-
-#define STAILQ_FIRST(head) ((head)->stqh_first)
-
-#define STAILQ_FOREACH(var, head, field)
\
- for((var) = STAILQ_FIRST((head)); \
- (var); \
- (var) = STAILQ_NEXT((var), field))
-
-#define STAILQ_INIT(head) do {
\
- STAILQ_FIRST((head)) = NULL; \
- (head)->stqh_last = &STAILQ_FIRST((head)); \
-} while (0)
-
-#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {
\
- if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
- (head)->stqh_last = &STAILQ_NEXT((elm), field); \
- STAILQ_NEXT((tqelm), field) = (elm); \
-} while (0)
-
-#define STAILQ_INSERT_HEAD(head, elm, field) do {
\
- if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
- (head)->stqh_last = &STAILQ_NEXT((elm), field); \
- STAILQ_FIRST((head)) = (elm); \
-} while (0)
-
-#define STAILQ_INSERT_TAIL(head, elm, field) do {
\
- STAILQ_NEXT((elm), field) = NULL; \
- *(head)->stqh_last = (elm); \
- (head)->stqh_last = &STAILQ_NEXT((elm), field); \
-} while (0)
-
-#define STAILQ_LAST(head, type, field)
\
- (STAILQ_EMPTY((head)) ? \
- NULL : \
- strbase(type, (head)->stqh_last, field))
-
-#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
-
-#define STAILQ_REMOVE(head, elm, type, field) do {
\
- if (STAILQ_FIRST((head)) == (elm)) { \
- STAILQ_REMOVE_HEAD((head), field); \
- } \
- else { \
- struct type *curelm = STAILQ_FIRST((head)); \
- while (STAILQ_NEXT(curelm, field) != (elm)) \
- curelm = STAILQ_NEXT(curelm, field); \
- if ((STAILQ_NEXT(curelm, field) = \
- STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
- (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
- } \
-} while (0)
-
-#define STAILQ_REMOVE_HEAD(head, field) do {
\
- if ((STAILQ_FIRST((head)) = \
- STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
- (head)->stqh_last = &STAILQ_FIRST((head)); \
-} while (0)
-
-#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {
\
- if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
- (head)->stqh_last = &STAILQ_FIRST((head)); \
-} while (0)
-
-/*
- * List declarations.
- */
-#define LIST_HEAD(name, type)
\
-struct name {
\
- struct type *lh_first; /* first element */ \
-}
-
-#define LIST_HEAD_INITIALIZER(head)
\
- { NULL }
-
-#define LIST_ENTRY(type)
\
-struct { \
- struct type *le_next; /* next element */ \
- struct type **le_prev; /* address of previous next element */ \
-}
-
-/*
- * List functions.
- */
-
-#define LIST_EMPTY(head) ((head)->lh_first == NULL)
-
-#define LIST_FIRST(head) ((head)->lh_first)
-
-#define LIST_FOREACH(var, head, field)
\
- for ((var) = LIST_FIRST((head)); \
- (var); \
- (var) = LIST_NEXT((var), field))
-
-#define LIST_INIT(head) do {
\
- LIST_FIRST((head)) = NULL; \
-} while (0)
-
-#define LIST_INSERT_AFTER(listelm, elm, field) do {
\
- if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
- LIST_NEXT((listelm), field)->field.le_prev = \
- &LIST_NEXT((elm), field); \
- LIST_NEXT((listelm), field) = (elm); \
- (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
-} while (0)
-
-#define LIST_INSERT_BEFORE(listelm, elm, field) do {
\
- (elm)->field.le_prev = (listelm)->field.le_prev; \
- LIST_NEXT((elm), field) = (listelm); \
- *(listelm)->field.le_prev = (elm); \
- (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
-} while (0)
-
-#define LIST_INSERT_HEAD(head, elm, field) do {
\
- if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
- LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
- LIST_FIRST((head)) = (elm); \
- (elm)->field.le_prev = &LIST_FIRST((head)); \
-} while (0)
-
-#define LIST_NEXT(elm, field) ((elm)->field.le_next)
-
-#define LIST_REMOVE(elm, field) do {
\
- if (LIST_NEXT((elm), field) != NULL) \
- LIST_NEXT((elm), field)->field.le_prev = \
- (elm)->field.le_prev; \
- *(elm)->field.le_prev = LIST_NEXT((elm), field); \
-} while (0)
-
-/*
- * Tail queue declarations.
- */
-#define TAILQ_HEAD(name, type)
\
-struct name {
\
- struct type *tqh_first; /* first element */ \
- struct type **tqh_last; /* addr of last next element */ \
-}
-
-#define TAILQ_HEAD_INITIALIZER(head)
\
- { NULL, &(head).tqh_first }
-
-#define TAILQ_ENTRY(type)
\
-struct { \
- struct type *tqe_next; /* next element */ \
- struct type **tqe_prev; /* address of previous next element */ \
-}
-
-/*
- * Tail queue functions.
- */
-#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
-
-#define TAILQ_FIRST(head) ((head)->tqh_first)
-
-#define TAILQ_FOREACH(var, head, field)
\
- for ((var) = TAILQ_FIRST((head)); \
- (var); \
- (var) = TAILQ_NEXT((var), field))
-
-#define TAILQ_FOREACH_REVERSE(var, head, headname, field)
\
- for ((var) = TAILQ_LAST((head), headname); \
- (var); \
- (var) = TAILQ_PREV((var), headname, field))
-
-#define TAILQ_INIT(head) do {
\
- TAILQ_FIRST((head)) = NULL; \
- (head)->tqh_last = &TAILQ_FIRST((head)); \
-} while (0)
-
-#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {
\
- if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
- TAILQ_NEXT((elm), field)->field.tqe_prev = \
- &TAILQ_NEXT((elm), field); \
- else \
- (head)->tqh_last = &TAILQ_NEXT((elm), field); \
- TAILQ_NEXT((listelm), field) = (elm); \
- (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
-} while (0)
-
-#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {
\
- (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
- TAILQ_NEXT((elm), field) = (listelm); \
- *(listelm)->field.tqe_prev = (elm); \
- (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
-} while (0)
-
-#define TAILQ_INSERT_HEAD(head, elm, field) do {
\
- if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
- TAILQ_FIRST((head))->field.tqe_prev = \
- &TAILQ_NEXT((elm), field); \
- else \
- (head)->tqh_last = &TAILQ_NEXT((elm), field); \
- TAILQ_FIRST((head)) = (elm); \
- (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
-} while (0)
-
-#define TAILQ_INSERT_TAIL(head, elm, field) do {
\
- TAILQ_NEXT((elm), field) = NULL; \
- (elm)->field.tqe_prev = (head)->tqh_last; \
- *(head)->tqh_last = (elm); \
- (head)->tqh_last = &TAILQ_NEXT((elm), field); \
-} while (0)
-
-#define TAILQ_LAST(head, headname)
\
- (*(((struct headname *)((head)->tqh_last))->tqh_last))
-
-#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
-
-#define TAILQ_PREV(elm, headname, field)
\
- (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
-
-#define TAILQ_REMOVE(head, elm, field) do {
\
- if ((TAILQ_NEXT((elm), field)) != NULL) \
- TAILQ_NEXT((elm), field)->field.tqe_prev = \
- (elm)->field.tqe_prev; \
- else \
- (head)->tqh_last = (elm)->field.tqe_prev; \
- *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
-} while (0)
-
-#define TAILQ_CONCAT(head1, head2, field) do {
\
- if (!TAILQ_EMPTY(head2)) { \
- *(head1)->tqh_last = (head2)->tqh_first; \
- (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
- (head1)->tqh_last = (head2)->tqh_last; \
- TAILQ_INIT(head2); \
- } \
-} while (0)
-
-/*
* Circular queue declarations.
*/
#define CIRCLEQ_HEAD(name, type)
\
@@ -539,49 +295,5 @@
CIRCLEQ_INIT((head2)); \
} \
} while (0)
-
-#ifdef _KERNEL
-
-/*
- * XXX insque() and remque() are an old way of handling certain queues.
- * They bogusly assumes that all queue heads look alike.
- */
-
-struct quehead {
- struct quehead *qh_link;
- struct quehead *qh_rlink;
-};
-
-#ifdef __GNUC__
-
-static __inline void
-insque(void *a, void *b)
-{
- struct quehead *element = a, *head = b;
-
- element->qh_link = head->qh_link;
- element->qh_rlink = head;
- head->qh_link = element;
- element->qh_link->qh_rlink = element;
-}
-
-static __inline void
-remque(void *a)
-{
- struct quehead *element = a;
-
- element->qh_link->qh_rlink = element->qh_rlink;
- element->qh_rlink->qh_link = element->qh_link;
- element->qh_rlink = 0;
-}
-
-#else /* !__GNUC__ */
-
-void insque __P((void *a, void *b));
-void remque __P((void *a));
-
-#endif /* __GNUC__ */
-
-#endif /* _KERNEL */
-#endif /* !_SYS_QUEUE_H_ */
+#endif /* !BSD_QUEUE_H */
