queue

rain00 | 2008-02-03 11:10:19 阅读：1217

/* queue.h - linked-list and queue definitions */

/*
* 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
* $FreeBSD: src/sys/sys/queue.h,v 1.32.2.7 2002/04/17 14:21:02 des Exp $
*/

/*
modification history
--------------------
01l,07feb05,vvv _KERNEL cleanup
01k,03oct04,dlk Fix some diab compiler warnings by using do {} while (FALSE)
                 instead of do {} while (0) (wierd, but it works).
01j,23aug04,rp   merged from COMP_WN_IPV6_BASE6_ITER5_TO_UNIFIED_PRE_MERGE
01i,12jul04,vvv converted insque/remque to macros to fix compiler warnings
01h,20nov03,niq Remove copyright_wrs.h file inclusion
01g,05nov03,cdw Removal of unnecessary _KERNEL guards.
01f,04nov03,rlm Ran batch header path update for header re-org.
01e,03nov03,rlm Removed wrn/coreip/ prefix from #includes for header re-org.
01d,10jun03,vvv include netVersion.h
01c,01feb03,pas merge from FreeBSD 4.7 - use access macros internally
01b,06sep02,hsh add c++ protection
01a,15jul02,rvr inline function insque and remque function defies for
                 diab (teamf1)
*/

#ifndef _SYS_QUEUE_H_
#define _SYS_QUEUE_H_

#ifdef __cplusplus
extern "C" {
#endif

#include <netVersion.h>

/*
* This file defines five types of data structures: singly-linked lists,
* singly-linked tail queues, lists, 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 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.
*
* 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.
*
*
*   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  + + + + +
*
*/

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。