381a2a9a387f449fab7d0c7e97c4184c26963abfdr/* $NetBSD: queue.h,v 1.42 2005/07/13 15:08:24 wiz Exp $ */
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Copyright (c) 1991, 1993
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * The Regents of the University of California. All rights reserved.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Redistribution and use in source and binary forms, with or without
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * modification, are permitted provided that the following conditions
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * are met:
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * 1. Redistributions of source code must retain the above copyright
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * notice, this list of conditions and the following disclaimer.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * 2. Redistributions in binary form must reproduce the above copyright
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * notice, this list of conditions and the following disclaimer in the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * documentation and/or other materials provided with the distribution.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * 3. Neither the name of the University nor the names of its contributors
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * may be used to endorse or promote products derived from this software
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * without specific prior written permission.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * SUCH DAMAGE.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * @(#)queue.h 8.5 (Berkeley) 8/20/94
c1374a13e412c4ec42cba867e57347a0e049a822Surya Prakki * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Use is subject to license terms.
381a2a9a387f449fab7d0c7e97c4184c26963abfdrextern "C" {
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * This file defines five types of data structures: singly-linked lists,
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * lists, simple queues, tail queues, and circular queues.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * A singly-linked list is headed by a single forward pointer. The
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * elements are singly linked for minimum space and pointer manipulation
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * overhead at the expense of O(n) removal for arbitrary elements. New
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * elements can be added to the list after an existing element or at the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * head of the list. Elements being removed from the head of the list
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * should use the explicit macro for this purpose for optimum
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * efficiency. A singly-linked list may only be traversed in the forward
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * direction. Singly-linked lists are ideal for applications with large
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * datasets and few or no removals or for implementing a LIFO queue.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * A list is headed by a single forward pointer (or an array of forward
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * pointers for a hash table header). The elements are doubly linked
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * so that an arbitrary element can be removed without a need to
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * traverse the list. New elements can be added to the list before
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * or after an existing element or at the head of the list. A list
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * may only be traversed in the forward direction.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * A simple queue is headed by a pair of pointers, one the head of the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * list and the other to the tail of the list. The elements are singly
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * linked to save space, so elements can only be removed from the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * head of the list. New elements can be added to the list after
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * an existing element, at the head of the list, or at the end of the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * list. A simple queue may only be traversed in the forward direction.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * A tail queue is headed by a pair of pointers, one to the head of the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * list and the other to the tail of the list. The elements are doubly
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * linked so that an arbitrary element can be removed without a need to
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * traverse the list. New elements can be added to the list before or
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * after an existing element, at the head of the list, or at the end of
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * the list. A tail queue may be traversed in either direction.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * A circle queue is headed by a pair of pointers, one to the head of the
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * list and the other to the tail of the list. The elements are doubly
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * linked so that an arbitrary element can be removed without a need to
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * traverse the list. New elements can be added to the list before or after
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * an existing element, at the head of the list, or at the end of the list.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * A circle queue may be traversed in either direction, but has a more
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * complex end of list detection.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * For details on the use of these macros, see the queue(3) manual page.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * List definitions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr struct type **le_prev; /* address of previous next element */ \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * List functions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
381a2a9a387f449fab7d0c7e97c4184c26963abfdr panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
381a2a9a387f449fab7d0c7e97c4184c26963abfdr panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * List access methods.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Singly-linked List definitions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Singly-linked List functions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr for ((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Singly-linked List access methods.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Singly-linked Tail queue declarations.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr struct type **stqh_last; /* addr of last next element */ \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Singly-linked Tail queue functions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.stqe_next = (listelm)->field.stqe_next) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr } else { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Singly-linked Tail queue access methods.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Simple queue definitions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr struct type **sqh_last; /* addr of last next element */ \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Simple queue functions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr } else { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Simple queue access methods.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Tail queue definitions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Tail queue functions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
c1374a13e412c4ec42cba867e57347a0e049a822Surya Prakki panic("TAILQ_INSERT_HEAD %p %s:%d", (void *)(head), \
c1374a13e412c4ec42cba867e57347a0e049a822Surya Prakki panic("TAILQ_INSERT_TAIL %p %s:%d", (void *)(head), \
c1374a13e412c4ec42cba867e57347a0e049a822Surya Prakki panic("TAILQ_* forw %p %s:%d", (void *)(elm), \
c1374a13e412c4ec42cba867e57347a0e049a822Surya Prakki panic("TAILQ_* back %p %s:%d", (void *)(elm), \
c1374a13e412c4ec42cba867e57347a0e049a822Surya Prakki (void *)(head), (void *)(elm), __FILE__, __LINE__);
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
381a2a9a387f449fab7d0c7e97c4184c26963abfdr (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Tail queue access methods.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Circular queue definitions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Circular queue functions.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr} while (0)
381a2a9a387f449fab7d0c7e97c4184c26963abfdr * Circular queue access methods.
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
381a2a9a387f449fab7d0c7e97c4184c26963abfdr#endif /* !_SYS_QUEUE_H */