[gssapi-openssh.git] / openssh / openbsd-compat / sys-queue.h

/*	$OpenBSD: queue.h,v 1.22 2001/06/23 04:39:35 angelos Exp $	*/
/*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/

/*
 * Copyright (c) 1991, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)queue.h	8.5 (Berkeley) 8/20/94
 */

#ifndef	_FAKE_QUEUE_H_
#define	_FAKE_QUEUE_H_

/*
 * Ignore all <sys/queue.h> since older platforms have broken/incomplete
 * <sys/queue.h> that are too hard to work around.
 */
#undef SLIST_HEAD
#undef SLIST_HEAD_INITIALIZER
#undef SLIST_ENTRY
#undef SLIST_FIRST
#undef SLIST_END
#undef SLIST_EMPTY
#undef SLIST_NEXT
#undef SLIST_FOREACH
#undef SLIST_INIT
#undef SLIST_INSERT_AFTER
#undef SLIST_INSERT_HEAD
#undef SLIST_REMOVE_HEAD
#undef SLIST_REMOVE
#undef LIST_HEAD
#undef LIST_HEAD_INITIALIZER
#undef LIST_ENTRY
#undef LIST_FIRST
#undef LIST_END
#undef LIST_EMPTY
#undef LIST_NEXT
#undef LIST_FOREACH
#undef LIST_INIT
#undef LIST_INSERT_AFTER
#undef LIST_INSERT_BEFORE
#undef LIST_INSERT_HEAD
#undef LIST_REMOVE
#undef LIST_REPLACE
#undef SIMPLEQ_HEAD
#undef SIMPLEQ_HEAD_INITIALIZER
#undef SIMPLEQ_ENTRY
#undef SIMPLEQ_FIRST
#undef SIMPLEQ_END
#undef SIMPLEQ_EMPTY
#undef SIMPLEQ_NEXT
#undef SIMPLEQ_FOREACH
#undef SIMPLEQ_INIT
#undef SIMPLEQ_INSERT_HEAD
#undef SIMPLEQ_INSERT_TAIL
#undef SIMPLEQ_INSERT_AFTER
#undef SIMPLEQ_REMOVE_HEAD
#undef TAILQ_HEAD
#undef TAILQ_HEAD_INITIALIZER
#undef TAILQ_ENTRY
#undef TAILQ_FIRST
#undef TAILQ_END
#undef TAILQ_NEXT
#undef TAILQ_LAST
#undef TAILQ_PREV
#undef TAILQ_EMPTY
#undef TAILQ_FOREACH
#undef TAILQ_FOREACH_REVERSE
#undef TAILQ_INIT
#undef TAILQ_INSERT_HEAD
#undef TAILQ_INSERT_TAIL
#undef TAILQ_INSERT_AFTER
#undef TAILQ_INSERT_BEFORE
#undef TAILQ_REMOVE
#undef TAILQ_REPLACE
#undef CIRCLEQ_HEAD
#undef CIRCLEQ_HEAD_INITIALIZER
#undef CIRCLEQ_ENTRY
#undef CIRCLEQ_FIRST
#undef CIRCLEQ_LAST
#undef CIRCLEQ_END
#undef CIRCLEQ_NEXT
#undef CIRCLEQ_PREV
#undef CIRCLEQ_EMPTY
#undef CIRCLEQ_FOREACH
#undef CIRCLEQ_FOREACH_REVERSE
#undef CIRCLEQ_INIT
#undef CIRCLEQ_INSERT_AFTER
#undef CIRCLEQ_INSERT_BEFORE
#undef CIRCLEQ_INSERT_HEAD
#undef CIRCLEQ_INSERT_TAIL
#undef CIRCLEQ_REMOVE
#undef CIRCLEQ_REPLACE

/*
 * This file defines five types of data structures: singly-linked lists, 
 * lists, simple queues, tail queues, and 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 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 simple queue is headed by a pair of pointers, one the head of the
 * list and the other to the tail of the list. The elements are singly
 * linked to save space, so elements can only be removed from the
 * head of 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 simple queue 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.
 *
 * 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.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 */

/*
 * Singly-linked List definitions.
 */
#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 access methods.
 */
#define	SLIST_FIRST(head)	((head)->slh_first)
#define	SLIST_END(head)		NULL
#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)

#define	SLIST_FOREACH(var, head, field)					\
	for((var) = SLIST_FIRST(head);					\
	    (var) != SLIST_END(head);					\
	    (var) = SLIST_NEXT(var, field))

/*
 * Singly-linked List functions.
 */
#define	SLIST_INIT(head) {						\
	SLIST_FIRST(head) = SLIST_END(head);				\
}

#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
	(slistelm)->field.sle_next = (elm);				\
} while (0)

#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.sle_next = (head)->slh_first;			\
	(head)->slh_first = (elm);					\
} while (0)

#define	SLIST_REMOVE_HEAD(head, field) do {				\
	(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)

#define SLIST_REMOVE(head, elm, type, field) do {			\
	if ((head)->slh_first == (elm)) {				\
		SLIST_REMOVE_HEAD((head), field);			\
	}								\
	else {								\
		struct type *curelm = (head)->slh_first;		\
		while( curelm->field.sle_next != (elm) )		\
			curelm = curelm->field.sle_next;		\
		curelm->field.sle_next =				\
		    curelm->field.sle_next->field.sle_next;		\
	}								\
} while (0)

/*
 * List definitions.
 */
#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 access methods
 */
#define	LIST_FIRST(head)		((head)->lh_first)
#define	LIST_END(head)			NULL
#define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
#define	LIST_NEXT(elm, field)		((elm)->field.le_next)

#define LIST_FOREACH(var, head, field)					\
	for((var) = LIST_FIRST(head);					\
	    (var)!= LIST_END(head);					\
	    (var) = LIST_NEXT(var, field))

/*
 * List functions.
 */
#define	LIST_INIT(head) do {						\
	LIST_FIRST(head) = LIST_END(head);				\
} while (0)

#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
		(listelm)->field.le_next->field.le_prev =		\
		    &(elm)->field.le_next;				\
	(listelm)->field.le_next = (elm);				\
	(elm)->field.le_prev = &(listelm)->field.le_next;		\
} while (0)

#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.le_prev = (listelm)->field.le_prev;		\
	(elm)->field.le_next = (listelm);				\
	*(listelm)->field.le_prev = (elm);				\
	(listelm)->field.le_prev = &(elm)->field.le_next;		\
} while (0)

#define LIST_INSERT_HEAD(head, elm, field) do {				\
	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
	(head)->lh_first = (elm);					\
	(elm)->field.le_prev = &(head)->lh_first;			\
} while (0)

#define LIST_REMOVE(elm, field) do {					\
	if ((elm)->field.le_next != NULL)				\
		(elm)->field.le_next->field.le_prev =			\
		    (elm)->field.le_prev;				\
	*(elm)->field.le_prev = (elm)->field.le_next;			\
} while (0)

#define LIST_REPLACE(elm, elm2, field) do {				\
	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
		(elm2)->field.le_next->field.le_prev =			\
		    &(elm2)->field.le_next;				\
	(elm2)->field.le_prev = (elm)->field.le_prev;			\
	*(elm2)->field.le_prev = (elm2);				\
} while (0)

/*
 * Simple queue definitions.
 */
#define SIMPLEQ_HEAD(name, type)					\
struct name {								\
	struct type *sqh_first;	/* first element */			\
	struct type **sqh_last;	/* addr of last next element */		\
}

#define SIMPLEQ_HEAD_INITIALIZER(head)					\
	{ NULL, &(head).sqh_first }

#define SIMPLEQ_ENTRY(type)						\
struct {								\
	struct type *sqe_next;	/* next element */			\
}

/*
 * Simple queue access methods.
 */
#define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
#define	SIMPLEQ_END(head)	    NULL
#define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
#define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)

#define SIMPLEQ_FOREACH(var, head, field)				\
	for((var) = SIMPLEQ_FIRST(head);				\
	    (var) != SIMPLEQ_END(head);					\
	    (var) = SIMPLEQ_NEXT(var, field))

/*
 * Simple queue functions.
 */
#define	SIMPLEQ_INIT(head) do {						\
	(head)->sqh_first = NULL;					\
	(head)->sqh_last = &(head)->sqh_first;				\
} while (0)

#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
		(head)->sqh_last = &(elm)->field.sqe_next;		\
	(head)->sqh_first = (elm);					\
} while (0)

#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.sqe_next = NULL;					\
	*(head)->sqh_last = (elm);					\
	(head)->sqh_last = &(elm)->field.sqe_next;			\
} while (0)

#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
		(head)->sqh_last = &(elm)->field.sqe_next;		\
	(listelm)->field.sqe_next = (elm);				\
} while (0)

#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do {			\
	if (((head)->sqh_first = (elm)->field.sqe_next) == NULL)	\
		(head)->sqh_last = &(head)->sqh_first;			\
} while (0)

/*
 * Tail queue definitions.
 */
#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 access methods 
 */
#define	TAILQ_FIRST(head)		((head)->tqh_first)
#define	TAILQ_END(head)			NULL
#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname)					\
	(*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field)				\
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#define	TAILQ_EMPTY(head)						\
	(TAILQ_FIRST(head) == TAILQ_END(head))

#define TAILQ_FOREACH(var, head, field)					\
	for((var) = TAILQ_FIRST(head);					\
	    (var) != TAILQ_END(head);					\
	    (var) = TAILQ_NEXT(var, field))

#define TAILQ_FOREACH_REVERSE(var, head, field, headname)		\
	for((var) = TAILQ_LAST(head, headname);				\
	    (var) != TAILQ_END(head);					\
	    (var) = TAILQ_PREV(var, headname, field))

/*
 * Tail queue functions.
 */
#define	TAILQ_INIT(head) do {						\
	(head)->tqh_first = NULL;					\
	(head)->tqh_last = &(head)->tqh_first;				\
} while (0)

#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
		(head)->tqh_first->field.tqe_prev =			\
		    &(elm)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm)->field.tqe_next;		\
	(head)->tqh_first = (elm);					\
	(elm)->field.tqe_prev = &(head)->tqh_first;			\
} while (0)

#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.tqe_next = NULL;					\
	(elm)->field.tqe_prev = (head)->tqh_last;			\
	*(head)->tqh_last = (elm);					\
	(head)->tqh_last = &(elm)->field.tqe_next;			\
} while (0)

#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
		(elm)->field.tqe_next->field.tqe_prev =			\
		    &(elm)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm)->field.tqe_next;		\
	(listelm)->field.tqe_next = (elm);				\
	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
} while (0)

#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
	(elm)->field.tqe_next = (listelm);				\
	*(listelm)->field.tqe_prev = (elm);				\
	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
} while (0)

#define TAILQ_REMOVE(head, elm, field) do {				\
	if (((elm)->field.tqe_next) != NULL)				\
		(elm)->field.tqe_next->field.tqe_prev =			\
		    (elm)->field.tqe_prev;				\
	else								\
		(head)->tqh_last = (elm)->field.tqe_prev;		\
	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
} while (0)

#define TAILQ_REPLACE(head, elm, elm2, field) do {			\
	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
		(elm2)->field.tqe_next->field.tqe_prev =		\
		    &(elm2)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm2)->field.tqe_next;		\
	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
	*(elm2)->field.tqe_prev = (elm2);				\
} while (0)

/*
 * Circular queue definitions.
 */
#define CIRCLEQ_HEAD(name, type)					\
struct name {								\
	struct type *cqh_first;		/* first element */		\
	struct type *cqh_last;		/* last element */		\
}

#define CIRCLEQ_HEAD_INITIALIZER(head)					\
	{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }

#define CIRCLEQ_ENTRY(type)						\
struct {								\
	struct type *cqe_next;		/* next element */		\
	struct type *cqe_prev;		/* previous element */		\
}

/*
 * Circular queue access methods 
 */
#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
#define	CIRCLEQ_END(head)		((void *)(head))
#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
#define	CIRCLEQ_EMPTY(head)						\
	(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))

#define CIRCLEQ_FOREACH(var, head, field)				\
	for((var) = CIRCLEQ_FIRST(head);				\
	    (var) != CIRCLEQ_END(head);					\
	    (var) = CIRCLEQ_NEXT(var, field))

#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
	for((var) = CIRCLEQ_LAST(head);					\
	    (var) != CIRCLEQ_END(head);					\
	    (var) = CIRCLEQ_PREV(var, field))

/*
 * Circular queue functions.
 */
#define	CIRCLEQ_INIT(head) do {						\
	(head)->cqh_first = CIRCLEQ_END(head);				\
	(head)->cqh_last = CIRCLEQ_END(head);				\
} while (0)

#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
	(elm)->field.cqe_prev = (listelm);				\
	if ((listelm)->field.cqe_next == CIRCLEQ_END(head))		\
		(head)->cqh_last = (elm);				\
	else								\
		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
	(listelm)->field.cqe_next = (elm);				\
} while (0)

#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
	(elm)->field.cqe_next = (listelm);				\
	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
	if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))		\
		(head)->cqh_first = (elm);				\
	else								\
		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
	(listelm)->field.cqe_prev = (elm);				\
} while (0)

#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.cqe_next = (head)->cqh_first;			\
	(elm)->field.cqe_prev = CIRCLEQ_END(head);			\
	if ((head)->cqh_last == CIRCLEQ_END(head))			\
		(head)->cqh_last = (elm);				\
	else								\
		(head)->cqh_first->field.cqe_prev = (elm);		\
	(head)->cqh_first = (elm);					\
} while (0)

#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.cqe_next = CIRCLEQ_END(head);			\
	(elm)->field.cqe_prev = (head)->cqh_last;			\
	if ((head)->cqh_first == CIRCLEQ_END(head))			\
		(head)->cqh_first = (elm);				\
	else								\
		(head)->cqh_last->field.cqe_next = (elm);		\
	(head)->cqh_last = (elm);					\
} while (0)

#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
	if ((elm)->field.cqe_next == CIRCLEQ_END(head))			\
		(head)->cqh_last = (elm)->field.cqe_prev;		\
	else								\
		(elm)->field.cqe_next->field.cqe_prev =			\
		    (elm)->field.cqe_prev;				\
	if ((elm)->field.cqe_prev == CIRCLEQ_END(head))			\
		(head)->cqh_first = (elm)->field.cqe_next;		\
	else								\
		(elm)->field.cqe_prev->field.cqe_next =			\
		    (elm)->field.cqe_next;				\
} while (0)

#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {			\
	if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==		\
	    CIRCLEQ_END(head))						\
		(head).cqh_last = (elm2);				\
	else								\
		(elm2)->field.cqe_next->field.cqe_prev = (elm2);	\
	if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==		\
	    CIRCLEQ_END(head))						\
		(head).cqh_first = (elm2);				\
	else								\
		(elm2)->field.cqe_prev->field.cqe_next = (elm2);	\
} while (0)

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