申明一個鏈表頭指針結構：
#define SLIST_ENTRY(type) / struct { / struct type *sle_next; /* next element */ / }#define SLIST_HEAD(name, type) /struct name { / struct type *slh_first; /* first element */ /}//取頭指針#define SLIST_FIRST(head) ((head)->slh_first)//取成員的next指針#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)//1.將新成員elm的next指針，指向頭指針指向的成員//2.頭指針指向新成員#define SLIST_INSERT_HEAD(head, elm, field) do { / SLIST_NEXT((elm), field) = SLIST_FIRST((head)); / SLIST_FIRST((head)) = (elm); /} while (0)//鏈表成員結構typedef struct _bfd{ SLIST_ENTRY(_bfd) next; //單鏈表next指針}BFD;//申明鏈表頭指針SLIST_HEAD(_bfd_str, _bfd) head;“頭插法”插入一個成員：
BFD *bfd = NULL;bfd = new BFD;SLIST_INSERT_HEAD(&head, bfd, next);刪除上述成員，參考下文queue源碼：
SLIST_REMOVE(&head, bfd,_bfd, next);queue.h源碼
/** @addtogroup M_COMMON_QUEUE 隊列庫@par 1. 功能概述隊列公共庫函數提供了幾類不同類型的隊列的操作函數。可提供隊列初始化，插入，刪除，查找，遍歷等通用操作。@par 2. 使用說明本庫的使用一般分為下面幾類:- SLIST前綴類函數: -# Singly-linked，提供鏈表頭指向首個節點的單向鏈表算法函數。適用于很少或者沒有隨機刪除操作或者是用于實現LIFO隊列的情況。- STAILQ前綴類函數: -# Singly-linked Tail queue，提供鏈表頭指向頭節點和尾節點的單向鏈表算法函數。同Singly-linked相比，提供了尾節點的操作。- LIST前綴類函數: -# List，提供鏈表頭指向頭節點的雙向鏈表操算法函數。適用于大量隨機刪除操作情況,但是只提供了頭節點開始的前向遍歷操作。- TAILQ類函數: -# Tail queue，提供鏈表頭指向頭節點和尾節點的雙向鏈表算法函數。同List相比，提供了尾節點的操作,頭節點的前向和尾節點的反向遍歷操作。- STAILQ類函數: -# Circular queue，提供循環雙向鏈表算法函數。適用于大量隨機刪除操作情況,同List，但提供的操作更豐富。@par 3. 相關函數分類信息- 本庫操作包含如下宏定義 - @ref SLIST_HEAD(name, type) ; - @ref SLIST_HEAD_INITIALIZER(head); - @ref SLIST_ENTRY(type); - @ref SLIST_EMPTY(head); - @ref SLIST_ENTRY_INIT(elm, field); - @ref SLIST_FIRST(head); - @ref SLIST_FOREACH(var, head, field); - @ref SLIST_FOREACH_SAFE(var, head, field, tvar); - @ref SLIST_INIT(head); - @ref SLIST_INSERT_AFTER(slistelm, elm, field); - @ref SLIST_INSERT_HEAD(head, elm, field); - @ref SLIST_NEXT(elm, field); - @ref SLIST_REMOVE(head, elm, type, field); - @ref SLIST_REMOVE_HEAD(head, field); - @ref STAILQ_HEAD(name, type); - @ref STAILQ_HEAD_INITIALIZER(head); - @ref STAILQ_ENTRY(type); - @ref STAILQ_CONCAT(head1, head2); - @ref STAILQ_EMPTY(head); - @ref STAILQ_ENTRY_INIT(elm, field); - @ref STAILQ_FIRST(head); - @ref STAILQ_FOREACH(var, head, field); - @ref STAILQ_FOREACH_SAFE(var, head, field, tvar); - @ref STAILQ_INIT(head); - @ref STAILQ_INSERT_AFTER(head, tqelm, elm, field); - @ref STAILQ_INSERT_HEAD(head, elm, field); - @ref STAILQ_INSERT_TAIL(head, elm, field); - @ref STAILQ_LAST(head, type, field); - @ref STAILQ_NEXT(elm, field); - @ref STAILQ_REMOVE(head, elm, type, field); - @ref STAILQ_REMOVE_HEAD(head, field); - @ref STAILQ_REMOVE_HEAD_UNTIL(head, elm, field); - @ref LIST_HEAD(name, type); - @ref LIST_HEAD_INITIALIZER(head); - @ref LIST_ENTRY(type); - @ref LIST_EMPTY(head); - @ref LIST_ENTRY_INIT(elm, field); - @ref LIST_FIRST(head); - @ref LIST_FOREACH(var, head, field); - @ref LIST_FOREACH_SAFE(var, head, field, tvar); - @ref LIST_INIT(head); - @ref LIST_INSERT_AFTER(listelm, elm, field); - @ref LIST_INSERT_BEFORE(listelm, elm, field); - @ref LIST_INSERT_HEAD(head, elm, field); - @ref LIST_NEXT(elm, field); - @ref LIST_REMOVE(elm, field); - @ref TAILQ_HEAD(name, type); - @ref TAILQ_HEAD_INITIALIZER(head); - @ref TAILQ_ENTRY(type); - @ref TAILQ_CONCAT(head1, head2, field); - @ref TAILQ_EMPTY(head) ; - @ref TAILQ_ENTRY_INIT(elm, field); - @ref TAILQ_IS_ENTRY_INIT(elm, field); - @ref TAILQ_FIRST(head); - @ref TAILQ_FOREACH(var, head, field); - @ref TAILQ_FOREACH_SAFE(var, head, field, tvar); - @ref TAILQ_FOREACH_REVERSE(var, head, headname, field); - @ref TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar); - @ref TAILQ_INIT(head); - @ref TAILQ_INSERT_AFTER(head, listelm, elm, field); - @ref TAILQ_INSERT_BEFORE(listelm, elm, field); - @ref TAILQ_INSERT_HEAD(head, elm, field); - @ref TAILQ_INSERT_TAIL(head, elm, field); - @ref TAILQ_LAST(head, headname); - @ref TAILQ_NEXT(elm, field); - @ref TAILQ_PREV(elm, headname, field); - @ref TAILQ_REMOVE(head, elm, field); - @ref CIRCLEQ_HEAD(name, type); - @ref CIRCLEQ_HEAD_INITIALIZER(head); - @ref CIRCLEQ_ENTRY(type); - @ref CIRCLEQ_EMPTY(head); - @ref CIRCLEQ_ENTRY_INIT(elm, field); - @ref CIRCLEQ_FIRST(head); - @ref CIRCLEQ_FOREACH(var, head, field) ; - @ref CIRCLEQ_FOREACH_SAFE(var, head, field, tvar); - @ref CIRCLEQ_FOREACH_REVERSE(var, head, field); - @ref CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, field, tvar); - @ref CIRCLEQ_INIT(head); - @ref CIRCLEQ_INSERT_AFTER(head, listelm, elm, field); - @ref CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field); - @ref CIRCLEQ_INSERT_HEAD(head, elm, field); - @ref CIRCLEQ_INSERT_TAIL(head, elm, field); - @ref CIRCLEQ_LAST(head); - @ref CIRCLEQ_NEXT(elm,field); - @ref CIRCLEQ_PREV(elm,field); - @ref CIRCLEQ_REMOVE(head, elm, field); * @{ *//* 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 $ */#ifndef _SYS_QUEUE_H_#define _SYS_QUEUE_H_//#include "queue_nsr.h"#ifdef __cplusplusextern "C" {#endif /* * 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 + + + + + * */ /* 增加了SAFE宏和ENTRY_INIT宏,by jin */#define __offsetof(type, field) ((size_t)(&((type *)0)->field)) /* * 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_ENTRY_INIT(elm, field) do { / (elm)->field.sle_next = NULL; /} while (0) #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_FOREACH_SAFE(var, head, field, tvar) / for ((var) = SLIST_FIRST((head)); / (var) && ((tvar) = SLIST_NEXT((var), field), 1); / (var) = (tvar)) #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_CONCAT(head1, head2) do { / if (!STAILQ_EMPTY((head2))) { / *(head1)->stqh_last = (head2)->stqh_first; / (head1)->stqh_last = (head2)->stqh_last; / STAILQ_INIT((head2)); / } /} while (0) #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)#define STAILQ_ENTRY_INIT(elm, field) do { / (elm)->field.stqe_next = NULL; /} while (0) #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_FOREACH_SAFE(var, head, field, tvar) / for ((var) = STAILQ_FIRST((head)); / (var) && ((tvar) = STAILQ_NEXT((var), field), 1); / (var) = (tvar)) #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 : / ((struct type *) / ((char *)((head)->stqh_last) - __offsetof(struct type, 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_ENTRY_INIT(elm, field) do { / (elm)->field.le_next = NULL; / (elm)->field.le_prev = NULL; /} while (0)/* by wangll */#define LIST_ENTRY_IS_EMPTY(elm, field) ((elm)->field.le_next == NULL && (elm)->field.le_prev == 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_FOREACH_SAFE(var, head, field, tvar) / for ((var) = LIST_FIRST((head)); / (var) && ((tvar) = LIST_NEXT((var), field), 1); / (var) = (tvar)) #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_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) #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)#define TAILQ_ENTRY_INIT(elm, field) do { / (elm)->field.tqe_next = NULL; / (elm)->field.tqe_prev = NULL; /} while (0)/* by wangll */#define TAILQ_ENTRY_IS_EMPTY(elm, field) ((elm)->field.tqe_next == NULL && (elm)->field.tqe_prev == NULL)/* 2008-12-12 add by sunxq */#define TAILQ_IS_ENTRY_INIT(elm, field) / ((NULL == (elm)->field.tqe_next)&&(NULL == (elm)->field.tqe_prev))/* end of add by sunxq */ #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_SAFE(var, head, field, tvar) / for ((var) = TAILQ_FIRST((head)); / (var) && ((tvar) = TAILQ_NEXT((var), field), 1); / (var) = (tvar)) #define TAILQ_FOREACH_REVERSE(var, head, headname, field) / for ((var) = TAILQ_LAST((head), headname); / (var); / (var) = TAILQ_PREV((var), headname, field))#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) / for ((var) = TAILQ_LAST((head), headname); / (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); / (var) = (tvar)) #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) /* * Circular queue declarations. */ #define CIRCLEQ_HEAD(name, type) / struct name { / struct type *cqh_first; /* first element */ / struct type *cqh_last; /* last element */ / } #define CIRCLEQ_HEAD_INITIALIZER(head) / { (void *)&(head), (void *)&(head) } #define CIRCLEQ_ENTRY(type) / struct { / struct type *cqe_next; /* next element */ / struct type *cqe_prev; /* previous element */ / } /* * Circular queue functions. */ #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))#define CIRCLEQ_ENTRY_INIT(elm, field) do { / (elm)->field.cqe_next = NULL; / (elm)->field.cqe_prev = NULL; /} while (0) #define CIRCLEQ_FIRST(head) ((head)->cqh_first) #define CIRCLEQ_FOREACH(var, head, field) / for ((var) = CIRCLEQ_FIRST((head)); / (var) != (void *)(head) || ((var) = NULL); / (var) = CIRCLEQ_NEXT((var), field))/* var = NULL,why? */#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) / for ((var) = CIRCLEQ_FIRST((head)); / ((var) != (void *)(head) || ((var) = NULL)) && ((tvar) = CIRCLEQ_NEXT((var), field), 1); / (var) = (tvar)) #define CIRCLEQ_FOREACH_REVERSE(var, head, field) / for ((var) = CIRCLEQ_LAST((head)); / (var) != (void *)(head) || ((var) = NULL); / (var) = CIRCLEQ_PREV((var), field)) #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, field, tvar) / for ((var) = CIRCLEQ_LAST((head)); / ((var) != (void *)(head) || ((var) = NULL)) && ((tvar) = CIRCLEQ_PREV((var), field), 1); / (var) = (tvar)) #define CIRCLEQ_INIT(head) do { / CIRCLEQ_FIRST((head)) = (void *)(head); / CIRCLEQ_LAST((head)) = (void *)(head); / } while (0) #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { / CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); / CIRCLEQ_PREV((elm), field) = (listelm); / if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) / CIRCLEQ_LAST((head)) = (elm); / else / CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);/ CIRCLEQ_NEXT((listelm), field) = (elm); / } while (0) #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { / CIRCLEQ_NEXT((elm), field) = (listelm); / CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); / if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) / CIRCLEQ_FIRST((head)) = (elm); / else / CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);/ CIRCLEQ_PREV((listelm), field) = (elm); / } while (0) #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { / CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); / CIRCLEQ_PREV((elm), field) = (void *)(head); / if (CIRCLEQ_LAST((head)) == (void *)(head)) / CIRCLEQ_LAST((head)) = (elm); / else / CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); / CIRCLEQ_FIRST((head)) = (elm); / } while (0) #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { / CIRCLEQ_NEXT((elm), field) = (void *)(head); / CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); / if (CIRCLEQ_FIRST((head)) == (void *)(head)) / CIRCLEQ_FIRST((head)) = (elm); / else / CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); / CIRCLEQ_LAST((head)) = (elm); / } while (0) #define CIRCLEQ_LAST(head) ((head)->cqh_last) #define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) #define CIRCLEQ_REMOVE(head, elm, field) do { / if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) / CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); / else / CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = / CIRCLEQ_PREV((elm), field); / if (CIRCLEQ_PREV((elm), field) == (void *)(head)) / CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); / else / CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = / CIRCLEQ_NEXT((elm), field); / } while (0)#define SLIST_HEAD_ENCODE(tHead,tHeadMsg) SLIST_NSR_HEAD_ENCODE(&(tHead),&(tHeadMsg))#define SLIST_HEAD_DECODE(tHead,tHeadMsg) SLIST_NSR_HEAD_DECODE(&(tHead),&(tHeadMsg))#define SLIST_HEAD_INVERT(tHeadMsg) SLIST_NSR_HEAD_INVERT(&(tHeadMsg))#define SLIST_ENTRY_ENCODE(tNode,tNodeMsg) SLIST_NSR_ENTRY_ENCODE(&(tNode),&(tNodeMsg))#define SLIST_ENTRY_DECODE(tNode,tNodeMsg) SLIST_NSR_ENTRY_DECODE(&(tNode),&(tNodeMsg))#define SLIST_ENTRY_INVERT(tHeadMsg) SLIST_NSR_ENTRY_INVERT(&(tHeadMsg))#define STAILQ_HEAD_ENCODE(tHead,tHeadMsg) STAILQ_NSR_HEAD_ENCODE(&(tHead),&(tHeadMsg))#define STAILQ_HEAD_DECODE(tHead,tHeadMsg) STAILQ_NSR_HEAD_DECODE(&(tHead),&(tHeadMsg))#define STAILQ_HEAD_INVERT(tHeadMsg) STAILQ_NSR_HEAD_INVERT(&(tHeadMsg))#define STAILQ_ENTRY_ENCODE(tNode,tNodeMsg) STAILQ_NSR_ENTRY_ENCODE(&(tNode),&(tNodeMsg))#define STAILQ_ENTRY_DECODE(tNode,tNodeMsg) STAILQ_NSR_ENTRY_DECODE(&(tNode),&(tNodeMsg))#define STAILQ_ENTRY_INVERT(tHeadMsg) STAILQ_NSR_ENTRY_INVERT(&(tHeadMsg))#define LIST_HEAD_ENCODE(tHead,tHeadMsg) LIST_NSR_HEAD_ENCODE(&(tHead),&(tHeadMsg))#define LIST_HEAD_DECODE(tHead,tHeadMsg) LIST_NSR_HEAD_DECODE(&(tHead),&(tHeadMsg))#define LIST_HEAD_INVERT(tHeadMsg) LIST_NSR_HEAD_INVERT(&(tHeadMsg))#define LIST_ENTRY_ENCODE(tNode,tNodeMsg) LIST_NSR_ENTRY_ENCODE(&(tNode),&(tNodeMsg))#define LIST_ENTRY_DECODE(tNode,tNodeMsg) LIST_NSR_ENTRY_DECODE(&(tNode),&(tNodeMsg))#define LIST_ENTRY_INVERT(tHeadMsg) LIST_NSR_ENTRY_INVERT(&(tHeadMsg))#define TAILQ_HEAD_ENCODE(tHead,tHeadMsg) TAILQ_NSR_HEAD_ENCODE(&(tHead),&(tHeadMsg))#define TAILQ_HEAD_DECODE(tHead,tHeadMsg) TAILQ_NSR_HEAD_DECODE(&(tHead),&(tHeadMsg))#define TAILQ_HEAD_INVERT(tHeadMsg) TAILQ_NSR_HEAD_INVERT(&(tHeadMsg))#define TAILQ_ENTRY_ENCODE(tNode,tNodeMsg) TAILQ_NSR_ENTRY_ENCODE(&(tNode),&(tNodeMsg))#define TAILQ_ENTRY_DECODE(tNode,tNodeMsg) TAILQ_NSR_ENTRY_DECODE(&(tNode),&(tNodeMsg))#define TAILQ_ENTRY_INVERT(tHeadMsg) TAILQ_NSR_ENTRY_INVERT(&(tHeadMsg))#define CIRCLEQ_HEAD_ENCODE(tHead,tHeadMsg) CIRCLEQ_NSR_HEAD_ENCODE(&(tHead),&(tHeadMsg))#define CIRCLEQ_HEAD_DECODE(tHead,tHeadMsg) CIRCLEQ_NSR_HEAD_DECODE(&(tHead),&(tHeadMsg))#define CIRCLEQ_HEAD_INVERT(tHeadMsg) CIRCLEQ_NSR_HEAD_INVERT(&(tHeadMsg))#define CIRCLEQ_ENTRY_ENCODE(tNode,tNodeMsg) CIRCLEQ_NSR_ENTRY_ENCODE(&(tNode),&(tNodeMsg))#define CIRCLEQ_ENTRY_DECODE(tNode,tNodeMsg) CIRCLEQ_NSR_ENTRY_DECODE(&(tNode),&(tNodeMsg))#define CIRCLEQ_ENTRY_INVERT(tHeadMsg) CIRCLEQ_NSR_ENTRY_INVERT(&(tHeadMsg))#define SLIST_INIT_NOTIFY(pHead) / SLIST_NSR_INIT(pHead)#define SLIST_INSERT_AFTER_NOTIFY(pRefElement, pElement, litNodeName) / SLIST_NSR_INSERT_AFTER(pRefElement, pElement, litNodeName)#define SLIST_INSERT_HEAD_NOTIFY(pHead, pElement, litNodeName) / SLIST_NSR_INSERT_HEAD(pHead, pElement, litNodeName)#define SLIST_REMOVE_NOTIFY(pHead, pElement, litElement_S, litNodeName) / SLIST_NSR_REMOVE(pHead, pElement, litElement_S, litNodeName)#define SLIST_REMOVE_HEAD_NOTIFY(pHead, litNodeName) / SLIST_NSR_REMOVE_HEAD(pHead, litNodeName)#define STAILQ_CONCAT_NOTIFY(pHeadDest, pHeadSrc) / STAILQ_NSR_CONCAT(pHeadDest, pHeadSrc)#define STAILQ_ENTRY_INIT_NOTIFY(pElement, litNodeName) / STAILQ_NSR_ENTRY_INIT(pElement, litNodeName)#define STAILQ_INIT_NOTIFY(pHead) / STAILQ_NSR_INIT(pHead)#define STAILQ_INSERT_AFTER_NOTIFY(pHead, pRefElement, pElement, litNodeName) / STAILQ_NSR_INSERT_AFTER(pHead, pRefElement, pElement, litNodeName)#define STAILQ_INSERT_HEAD_NOTIFY(pHead, pElement, litNodeName) / STAILQ_NSR_INSERT_HEAD(pHead, pElement, litNodeName)#define STAILQ_INSERT_TAIL_NOTIFY(pHead, pElement, litNodeName) / STAILQ_NSR_INSERT_TAIL(pHead, pElement, litNodeName)#define STAILQ_REMOVE_NOTIFY(pHead, pElement, litElement_t, litNodeName) / STAILQ_NSR_REMOVE(pHead, pElement, litElement_t, litNodeName)#define STAILQ_REMOVE_HEAD_NOTIFY(pHead, litNodeName) / STAILQ_NSR_REMOVE_HEAD(pHead, litNodeName)#define STAILQ_REMOVE_HEAD_UNTIL_NOTIFY(pHead, pElement, litNodeName) / STAILQ_NSR_REMOVE_HEAD_UNTIL(pHead, pElement, litNodeName)#define LIST_ENTRY_INIT_NOTIFY(pElement, litNodeName) / LIST_NSR_ENTRY_INIT(pElement, litNodeName)#define LIST_INIT_NOTIFY(pHead) / LIST_NSR_INIT(pHead)#define LIST_INSERT_AFTER_NOTIFY(pRefElement, pElement, litNodeName) / LIST_NSR_INSERT_AFTER(pRefElement, pElement, litNodeName)#define LIST_INSERT_BEFORE_NOTIFY(pRefElement, pElement, litNodeName) / LIST_NSR_INSERT_BEFORE(pRefElement, pElement, litNodeName)#define LIST_INSERT_HEAD_NOTIFY(pHead, pElement, litNodeName) / LIST_NSR_INSERT_HEAD(pHead, pElement, litNodeName)#define LIST_REMOVE_NOTIFY(pElement, litNodeName) / LIST_NSR_REMOVE(pElement, litNodeName)#define TAILQ_INIT_NOTIFY(pHead) / TAILQ_NSR_INIT(pHead)#define TAILQ_ENTRY_INIT_NOTIFY(pElement, litNodeName) / TAILQ_NSR_ENTRY_INIT(pElement, litNodeName)#define TAILQ_CONCAT_NOTIFY(pHeadDest, pHeadSrc, litNodeName) / TAILQ_NSR_CONCAT(pHeadDest, pHeadSrc, litNodeName)#define TAILQ_INSERT_AFTER_NOTIFY(pHead, pRefElement, pElement, litNodeName) / TAILQ_NSR_INSERT_AFTER(pHead, pRefElement, pElement, litNodeName)#define TAILQ_INSERT_BEFORE_NOTIFY(pRefElement, pElement, litNodeName) / TAILQ_NSR_INSERT_BEFORE(pRefElement, pElement, litNodeName)#define TAILQ_INSERT_HEAD_NOTIFY(pHead, pElement, litNodeName) / TAILQ_NSR_INSERT_HEAD(pHead, pElement, litNodeName)#define TAILQ_INSERT_TAIL_NOTIFY(pHead, pElement, litNodeName) / TAILQ_NSR_INSERT_TAIL(pHead, pElement, litNodeName)#define TAILQ_REMOVE_NOTIFY(pHead, pElement, litNodeName) / TAILQ_NSR_REMOVE(pHead, pElement, litNodeName)#define CIRCLEQ_INIT_NOTIFY(pHead) / CIRCLEQ_NSR_INIT(pHead)#define CIRCLEQ_INSERT_AFTER_NOTIFY(pHead, pRefElement, pElement, litNodeName) / CIRCLEQ_NSR_INSERT_AFTER(pHead, pRefElement, pElement, litNodeName)#define CIRCLEQ_INSERT_BEFORE_NOTIFY(pHead, pRefElement, pElement, litNodeName) / CIRCLEQ_NSR_INSERT_BEFORE(pHead, pRefElement, pElement, litNodeName)#define CIRCLEQ_INSERT_HEAD_NOTIFY(pHead, pElement, litNodeName) / CIRCLEQ_NSR_INSERT_HEAD(pHead, pElement, litNodeName)#define CIRCLEQ_INSERT_TAIL_NOTIFY(pHead, pElement, litNodeName) / CIRCLEQ_NSR_INSERT_TAIL(pHead, pElement, litNodeName)#define CIRCLEQ_REMOVE_NOTIFY(pHead, pElement, litNodeName) / CIRCLEQ_NSR_REMOVE(pHead, pElement, litNodeName) #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 = (struct quehead *)a, *head = (struct quehead *)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 = (struct quehead *)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 */#ifdef __cplusplus}#endif#endif /* !_SYS_QUEUE_H_ *//** @}*/新聞熱點
疑難解答
