【原创】Twemperf 中对 BSD queue.h 的兼容实现-阿里云开发者社区

研究 twemperf 源码过程中，发现其中包含了针对 BSD queue.h 文件的兼容实现。并且还额外增加了 SLIST 和 STAILQ 两种结构的实现和相应操作。

下面给出的是 twemperf 中 mcp_queue.h 的源码。

        /*
       
        *  twemperf - a tool for measuring memcached server performance. 
       
        *  Copyright (C) 2011 Twitter, Inc. 
       
        * 
       
        *  This program is free software: you can redistribute it and/or modify 
       
        *  it under the terms of the GNU General Public License as published by 
       
        *  the Free Software Foundation, either version 3 of the License, or 
       
        *  (at your option) any later version. 
       
        * 
       
        *  This program is distributed in the hope that it will be useful, 
       
        *  but WITHOUT ANY WARRANTY; without even the implied warranty of 
       
        *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
       
        *  GNU General Public License for more details. 
       
        * 
       
        *  You should have received a copy of the GNU General Public License 
       
        *  along with this program.  If not, see <http://www.gnu.org/licenses/>. 
       
        */ 
       
        /*-
       
        * 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. 
       
        * 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.73 2010/02/20 01:05:30 emaste Exp $ 
       
        */ 
       
        #ifndef _MCP_QUEUE_H_
       
        #define _MCP_QUEUE_H_
       
        #include <mcp_log.h>
       
        #define __offsetof(type, field) ((size_t)(&((type *)NULL)->field))
       
        /*
       
        * This file defines five types of data structures: singly-linked lists, 
       
        * singly-linked tail queues, lists, tail queues, and circular queues. 
       
        * 该文件定义 5 中类型的数据结构： 
       
        * 
       
        * 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. 
       
        * singly-linked list 通过单个正向指针进行访问。元素构成单链表，移除元素的时间复 
       
        * 杂度为 O(n) 。新元素可被添加到指定元素的后面或者 list 的头部。仅支持正向遍历。  
       
        * 适用范围：少量或者没有移除操作的大数据集应用程序；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. 
       
        * singly-linked tail queue 可通过一对指针进行访问，分别指向头部和尾部。元素构成 
       
        * 单链表，移除元素的时间复杂度为 O(n) 。新元素可被添加到指定元素的后面、list 的头部或尾部。 
       
        * 仅支持正向遍历。适用范围：少量或者没有移除操作的大数据集应用程序；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. 
       
        * list 通过单个正向指针进行访问（或者用于哈希表头的一组正向指针）。元素构成双链表，故 
       
        * 无需遍历就可以删除任意元素。新元素可被添加到指定元素的前面或后面，以及 list 的头部。 
       
        * 仅支持正向遍历。 
       
        * 
       
        * 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 queue 可通过一对指针进行访问，分别指向头部和尾部。元素构成双链表，故 
       
        * 无需遍历就可以删除任意元素。新元素可被添加到指定元素的前面或后面，以及 tail queue  
       
        * 的头部或尾部。<span></span>支持正向和反向遍历。 
       
        *  
       
        * 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 queue 可通过一对指针进行访问，分别指向头部和尾部。元素构成双链表，故 
       
        * 无需遍历就可以删除任意元素。新元素可被添加到指定元素的前面或后面，以及 circle queue  
       
        * 的头部或尾部。支持正向和反向遍历，但需要更加复杂的 list 末端检测。 
       
        * 
       
        * 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              +       +       +       +       + 
       
        * 
       
        */ 
       
        #define QUEUE_MACRO_SCRUB 1
       
        #ifdef MCP_ASSERT_PANIC
       
        # define QUEUE_MACRO_TRACE  1
       
        # define QUEUE_MACRO_ASSERT 1
       
        #endif
       
        #ifdef QUEUE_MACRO_SCRUB
       
        #define QMD_SAVELINK(name, link)    void **name = (void *)&(link)
       
        // 即"trash it" ，将 x 的值设置为NULL
       
        #define TRASHIT(x) do {                                                 \
       
        (x) = (
        void 
        *) NULL;                                                \ 
       
        } 
        while 
        (0) 
       
        #else
       
        #define QMD_SAVELINK(name, link)
       
        #define TRASHIT(x)
       
        #endif /* QUEUE_MACRO_SCRUB */
       
        #ifdef QUEUE_MACRO_TRACE
       
        /* Store the last 2 places the queue element or head was altered */
       
        struct 
        qm_trace { 
       
        char 
        *lastfile; 
       
        int  
        lastline; 
       
        char 
        *prevfile; 
       
        int  
        prevline; 
       
        };
       
        #define TRACEBUF    struct qm_trace trace;
       
        #define QMD_TRACE_HEAD(head) do {                                       \
       
        (head)->trace.prevline = (head)->trace.lastline;                    \ 
       
        (head)->trace.prevfile = (head)->trace.lastfile;                    \ 
       
        (head)->trace.lastline = __LINE__;                                  \ 
       
        (head)->trace.lastfile = __FILE__;                                  \ 
       
        } 
        while 
        (0) 
       
        #define QMD_TRACE_ELEM(elem) do {                                       \
       
        (elem)->trace.prevline = (elem)->trace.lastline;                    \ 
       
        (elem)->trace.prevfile = (elem)->trace.lastfile;                    \ 
       
        (elem)->trace.lastline = __LINE__;                                  \ 
       
        (elem)->trace.lastfile = __FILE__;                                  \ 
       
        } 
        while 
        (0) 
       
        #else
       
        #define QMD_TRACE_ELEM(elem)
       
        #define QMD_TRACE_HEAD(head)
       
        #define TRACEBUF
       
        #endif /* QUEUE_MACRO_TRACE */
       
        /*
       
        * 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_FOREACH_SAFE(var, head, field, tvar)                      \
       
        for 
        ((var) = SLIST_FIRST((head));                                   \ 
       
        (var) && ((tvar) = SLIST_NEXT((var), field), 1);                \ 
       
        (var) = (tvar)) 
       
        #define SLIST_FOREACH_PREVPTR(var, varp, head, field)                   \
       
        for 
        ((varp) = &SLIST_FIRST((head));                                 \ 
       
        ((var) = *(varp)) != NULL;                                      \ 
       
        (varp) = &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_REMOVE_AFTER(curelm, field);                              \ 
       
        }                                                                   \ 
       
        } 
        while 
        (0) 
       
        #define SLIST_REMOVE_AFTER(elm, field) do {                             \
       
        QMD_SAVELINK(oldnext, SLIST_NEXT(SLIST_NEXT(elm, field), field));   \ 
       
        SLIST_NEXT(elm, field) = SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 
       
        TRASHIT(*oldnext);                                                  \ 
       
        } 
        while 
        (0) 
       
        #define SLIST_REMOVE_HEAD(head, field) do {                             \
       
        QMD_SAVELINK(oldnext, SLIST_NEXT(SLIST_FIRST((head)), field));      \ 
       
        SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);       \ 
       
        TRASHIT(*oldnext);                                                  \ 
       
        } 
        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_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 *)(
        void 
        *)                                    \ 
       
        ((
        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);                        \ 
       
        STAILQ_REMOVE_AFTER(head, curelm, field);                       \ 
       
        }                                                                   \ 
       
        } 
        while 
        (0) 
       
        #define STAILQ_REMOVE_HEAD(head, field) do {                            \
       
        QMD_SAVELINK(oldnext, STAILQ_NEXT(STAILQ_FIRST((head)), field));    \ 
       
        if 
        ((STAILQ_FIRST((head)) =                                         \ 
       
        STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) {           \ 
       
        (head)->stqh_last = &STAILQ_FIRST((head));                      \ 
       
        }                                                                   \ 
       
        TRASHIT(*oldnext);                                                  \ 
       
        } 
        while 
        (0) 
       
        #define STAILQ_REMOVE_AFTER(head, elm, field) do {                      \
       
        QMD_SAVELINK(oldnext, STAILQ_NEXT(STAILQ_NEXT(elm, field), field)); \ 
       
        if 
        ((STAILQ_NEXT(elm, field) =                                      \ 
       
        STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) {        \ 
       
        (head)->stqh_last = &STAILQ_NEXT((elm), field);                 \ 
       
        }                                                                   \ 
       
        TRASHIT(*oldnext);                                                  \ 
       
        } 
        while 
        (0) 
       
        #define STAILQ_SWAP(head1, head2, type) do {                            \
       
        struct 
        type *swap_first = STAILQ_FIRST(head1);                      \ 
       
        struct 
        type **swap_last = (head1)->stqh_last;                       \ 
       
        STAILQ_FIRST(head1) = STAILQ_FIRST(head2);                          \ 
       
        (head1)->stqh_last = (head2)->stqh_last;                            \ 
       
        STAILQ_FIRST(head2) = swap_first;                                   \ 
       
        (head2)->stqh_last = swap_last;                                     \ 
       
        if 
        (STAILQ_EMPTY(head1))                                            \ 
       
        (head1)->stqh_last = &STAILQ_FIRST(head1);                      \ 
       
        if 
        (STAILQ_EMPTY(head2))                                            \ 
       
        (head2)->stqh_last = &STAILQ_FIRST(head2);                      \ 
       
        } 
        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 */ 
        // 指向上一链表元素的le_next 指针的地址\ 
       
        }
       
        /*
       
        * List functions. 
       
        */ 
       
        #ifdef QUEUE_MACRO_ASSERT
       
        // 校验由 head 指定的链表的头元素是否合法
       
        #define QMD_LIST_CHECK_HEAD(head, field) do {                               \
       
        if 
        (LIST_FIRST((head)) != NULL &&                                       \ 
       
        LIST_FIRST((head))->field.le_prev != &LIST_FIRST((head))) {         \ 
       
        log_panic(
        "Bad list head %p first->prev != head"
        , (
        void 
        *)(head));  \ 
       
        }                                                                       \ 
       
        } 
        while 
        (0) 
       
        // 校验元素 elm 的 le_next 指针所指对象是否合法
       
        #define QMD_LIST_CHECK_NEXT(elm, field) do {                                \
       
        if 
        (LIST_NEXT((elm), field) != NULL &&                                  \ 
       
        LIST_NEXT((elm), field)->field.le_prev != &((elm)->field.le_next)) {\ 
       
        log_panic(
        "Bad link elm %p next->prev != elm"
        ,(
        void 
        *)(elm));       \ 
       
        }                                                                       \ 
       
        } 
        while 
        (0) 
       
        // 校验元素 elm 的 le_prev 指针所指对象是否合法
       
        #define QMD_LIST_CHECK_PREV(elm, field) do {                            \
       
        if 
        (*(elm)->field.le_prev != (elm)) {                               \ 
       
        log_panic(
        "Bad link elm %p prev->next != elm"
        ,(
        void 
        *)(elm));   \ 
       
        }                                                                   \ 
       
        } 
        while 
        (0) 
       
        #else
       
        #define QMD_LIST_CHECK_HEAD(head, field)
       
        #define QMD_LIST_CHECK_NEXT(elm, field)
       
        #define QMD_LIST_CHECK_PREV(elm, field)
       
        #endif /* QUEUE_MACRO_ASSERT */
       
        #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_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 {                     \
       
        QMD_LIST_CHECK_NEXT(listelm, field);                                \ 
       
        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 {                    \
       
        QMD_LIST_CHECK_PREV(listelm, field);                                \ 
       
        (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 {                         \
       
        QMD_LIST_CHECK_HEAD((head), field);                                 \ 
       
        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) 
       
        // 获取元素 elm 中 le_next 指向的下一个 elm 元素
       
        #define LIST_NEXT(elm, field)    ((elm)->field.le_next)
       
        // 将元素 elm 从链表中移除
       
        #define LIST_REMOVE(elm, field) do {                                    \
       
        QMD_SAVELINK(oldnext, (elm)->field.le_next);                        \ 
       
        QMD_SAVELINK(oldprev, (elm)->field.le_prev);                        \ 
       
        QMD_LIST_CHECK_NEXT(elm, field);                                    \ 
       
        QMD_LIST_CHECK_PREV(elm, field);                                    \ 
       
        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);                    \ 
       
        TRASHIT(*oldnext);                                                  \ 
       
        TRASHIT(*oldprev);                                                  \ 
       
        } 
        while 
        (0) 
       
        #define LIST_SWAP(head1, head2, type, field) do {                       \
       
        struct 
        type *swap_tmp = LIST_FIRST((head1));                        \ 
       
        LIST_FIRST((head1)) = LIST_FIRST((head2));                          \ 
       
        LIST_FIRST((head2)) = swap_tmp;                                     \ 
       
        if 
        ((swap_tmp = LIST_FIRST((head1))) != NULL)                       \ 
       
        swap_tmp->field.le_prev = &LIST_FIRST((head1));                 \ 
       
        if 
        ((swap_tmp = LIST_FIRST((head2))) != NULL)                       \ 
       
        swap_tmp->field.le_prev = &LIST_FIRST((head2));                 \ 
       
        } 
        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 */             
        \ 
       
        TRACEBUF                                                            \ 
       
        }
       
        #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 */      
        \ 
       
        TRACEBUF                                                            \ 
       
        }
       
        /*
       
        * Tail queue functions. 
       
        */ 
       
        #ifdef QUEUE_MACRO_ASSERT
       
        #define QMD_TAILQ_CHECK_HEAD(head, field) do {                              \
       
        if 
        (!TAILQ_EMPTY(head) &&                                               \ 
       
        TAILQ_FIRST((head))->field.tqe_prev != &TAILQ_FIRST((head))) {      \ 
       
        log_panic(
        "Bad tailq head %p first->prev != head"
        , (
        void 
        *)(head)); \ 
       
        }                                                                       \ 
       
        } 
        while 
        (0) 
       
        #define QMD_TAILQ_CHECK_TAIL(head, field) do {                              \
       
        if 
        (*(head)->tqh_last != NULL) {                                        \ 
       
        log_panic(
        "Bad tailq NEXT(%p->tqh_last) != NULL"
        ,(
        void 
        *)(head));   \ 
       
        }                                                                       \ 
       
        } 
        while 
        (0) 
       
        #define QMD_TAILQ_CHECK_NEXT(elm, field) do {                               \
       
        if 
        (TAILQ_NEXT((elm), field) != NULL &&                                 \ 
       
        TAILQ_NEXT((elm), field)->field.tqe_prev != &((elm)->field.tqe_next)) {\ 
       
        log_panic(
        "Bad link elm %p next->prev != elm"
        ,(
        void 
        *)(elm));       \ 
       
        }                                                                       \ 
       
        } 
        while 
        (0) 
       
        #define QMD_TAILQ_CHECK_PREV(elm, field) do {                           \
       
        if 
        (*(elm)->field.tqe_prev != (elm)) {                              \ 
       
        log_panic(
        "Bad link elm %p prev->next != elm"
        ,(
        void 
        *)(elm));   \ 
       
        }                                                                   \ 
       
        } 
        while 
        (0) 
       
        #else
       
        #define QMD_TAILQ_CHECK_HEAD(head, field)
       
        #define QMD_TAILQ_CHECK_TAIL(head, headname)
       
        #define QMD_TAILQ_CHECK_NEXT(elm, field)
       
        #define QMD_TAILQ_CHECK_PREV(elm, field)
       
        #endif /* QUEUE_MACRO_ASSERT */
       
        #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));                                            \ 
       
        QMD_TRACE_HEAD(head1);                                          \ 
       
        QMD_TRACE_HEAD(head2);                                          \ 
       
        }                                                                   \ 
       
        } 
        while 
        (0) 
       
        #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_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));                            \ 
       
        QMD_TRACE_HEAD(head);                                               \ 
       
        } 
        while 
        (0) 
       
        #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
       
        QMD_TAILQ_CHECK_NEXT(listelm, field);                               \ 
       
        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);                   \ 
       
        QMD_TRACE_HEAD(head);                                           \ 
       
        }                                                                   \ 
       
        TAILQ_NEXT((listelm), field) = (elm);                               \ 
       
        (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);              \ 
       
        QMD_TRACE_ELEM(&(elm)->field);                                      \ 
       
        QMD_TRACE_ELEM(&listelm->field);                                    \ 
       
        } 
        while 
        (0) 
       
        #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
       
        QMD_TAILQ_CHECK_PREV(listelm, field);                               \ 
       
        (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);              \ 
       
        QMD_TRACE_ELEM(&(elm)->field);                                      \ 
       
        QMD_TRACE_ELEM(&listelm->field);                                    \ 
       
        } 
        while 
        (0) 
       
        #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
       
        QMD_TAILQ_CHECK_HEAD(head, field);                                  \ 
       
        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));                       \ 
       
        QMD_TRACE_HEAD(head);                                               \ 
       
        QMD_TRACE_ELEM(&(elm)->field);                                      \ 
       
        } 
        while 
        (0) 
       
        #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
       
        QMD_TAILQ_CHECK_TAIL(head, field);                                  \ 
       
        TAILQ_NEXT((elm), field) = NULL;                                    \ 
       
        (elm)->field.tqe_prev = (head)->tqh_last;                           \ 
       
        *(head)->tqh_last = (elm);                                          \ 
       
        (head)->tqh_last = &TAILQ_NEXT((elm), field);                       \ 
       
        QMD_TRACE_HEAD(head);                                               \ 
       
        QMD_TRACE_ELEM(&(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 {                             \
       
        QMD_SAVELINK(oldnext, (elm)->field.tqe_next);                       \ 
       
        QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);                       \ 
       
        QMD_TAILQ_CHECK_NEXT(elm, field);                                   \ 
       
        QMD_TAILQ_CHECK_PREV(elm, field);                                   \ 
       
        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;                       \ 
       
        QMD_TRACE_HEAD(head);                                           \ 
       
        }                                                                   \ 
       
        *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);                  \ 
       
        TRASHIT(*oldnext);                                                  \ 
       
        TRASHIT(*oldprev);                                                  \ 
       
        QMD_TRACE_ELEM(&(elm)->field);                                      \ 
       
        } 
        while 
        (0) 
       
        #define TAILQ_SWAP(head1, head2, type, field) do {                      \
       
        struct 
        type *swap_first = (head1)->tqh_first;                       \ 
       
        struct 
        type **swap_last = (head1)->tqh_last;                        \ 
       
        (head1)->tqh_first = (head2)->tqh_first;                            \ 
       
        (head1)->tqh_last = (head2)->tqh_last;                              \ 
       
        (head2)->tqh_first = swap_first;                                    \ 
       
        (head2)->tqh_last = swap_last;                                      \ 
       
        if 
        ((swap_first = (head1)->tqh_first) != NULL)                      \ 
       
        swap_first->field.tqe_prev = &(head1)->tqh_first;               \ 
       
        else                                                                
        \ 
       
        (head1)->tqh_last = &(head1)->tqh_first;                        \ 
       
        if 
        ((swap_first = (head2)->tqh_first) != NULL)                      \ 
       
        swap_first->field.tqe_prev = &(head2)->tqh_first;               \ 
       
        else                                                                
        \ 
       
        (head2)->tqh_last = &(head2)->tqh_first;                        \ 
       
        } 
        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_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)) 
       
        #define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
       
        for 
        ((var) = CIRCLEQ_LAST((head));                                  \ 
       
        (var) != (
        void 
        *)(head) || ((var) = NULL);                      \ 
       
        (var) = CIRCLEQ_PREV((var), field)) 
       
        #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) 
       
        #endif

代码中主要实现了五种类型数据结构和其相应的操作。通过 linux 下的 man 命令，可以查看 BSD 库中的定义说明。

        # man 3 queue
       
        QUEUE(3)                 BSD Library Functions Manual                 QUEUE(3)
       
        NAME
       
        LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE - implementations of lists, 
        tail 
        queues, and circular queues 
       
        实现 list 、
        tail 
        queue 和 circular queue 的功能。 
       
        SYNOPSIS
       
        #include <sys/queue.h> 
       
        LIST_ENTRY(TYPE); 
       
        LIST_HEAD(HEADNAME, TYPE); 
       
        LIST_INIT(LIST_HEAD *
        head
        ); 
       
        LIST_INSERT_AFTER(LIST_ENTRY *listelm, TYPE *elm, LIST_ENTRY NAME); 
       
        LIST_INSERT_HEAD(LIST_HEAD *
        head
        , TYPE *elm, LIST_ENTRY NAME); 
       
        LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME); 
       
        TAILQ_ENTRY(TYPE); 
       
        TAILQ_HEAD(HEADNAME, TYPE); 
       
        TAILQ_INIT(TAILQ_HEAD *
        head
        ); 
       
        TAILQ_INSERT_AFTER(TAILQ_HEAD *
        head
        , TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME); 
       
        TAILQ_INSERT_HEAD(TAILQ_HEAD *
        head
        , TYPE *elm, TAILQ_ENTRY NAME); 
       
        TAILQ_INSERT_TAIL(TAILQ_HEAD *
        head
        , TYPE *elm, TAILQ_ENTRY NAME); 
       
        TAILQ_REMOVE(TAILQ_HEAD *
        head
        , TYPE *elm, TAILQ_ENTRY NAME); 
       
        CIRCLEQ_ENTRY(TYPE); 
       
        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_REMOVE(CIRCLEQ_HEAD *
        head
        , TYPE *elm, CIRCLEQ_ENTRY NAME); 
       
        DESCRIPTION
       
        These macros define and operate on three types of data structures: lists, 
        tail 
        queues, and circular queues.  All three structures support the following functionality: 
       
        上述宏用于定义和操作 3 种类型的数据结构：list 、
        tail 
        queue 和 circular queue 。这 3 中数据结构均支持下述功能： 
       
        1.   Insertion of a new entry at the 
        head 
        of the list. 
       
        2.   Insertion of a new entry after any element 
        in 
        the list. 
       
        3.   Removal of any entry 
        in 
        the list. 
       
        4.   Forward traversal through the list. 
       
        1. 可以在 list 头处插入新的 entry 。 
       
        2. 可以在 list 中任意元素后插入新的 entry 。 
       
        3. 可以从 list 中移除任意 entry 。 
       
        4. 可以对 list 进行前向遍历。 
       
        Lists are the simplest of the three data structures and support only the above functionality. 
       
        list 是上述 3 种数据结构中最简单的，且仅支持上述功能。 
       
        Tail queues add the following functionality: 
       
        tail 
        queue 增加了下述功能： 
       
        1.   Entries can be added at the end of a list. 
       
        1. 可以在 list 的最后增加 entry 。 
       
        However: 
       
        但是： 
       
        1.   All list insertions and removals must specify the 
        head 
        of the list. 
       
        2.   Each 
        head 
        entry requires two pointers rather than one. 
       
        3.   Code size is about 15% greater and operations run about 20% slower than lists. 
       
        1. 所有的 list 插入和移除操作均必须提供 list 的头指针。 
       
        2. 每一个 
        head 
        entry 都要求含有两个指针，而不是一个指针。 
       
        3. 与 list 相比，代码量增加大约 15% ，运算速度减慢大约 20% 。 
       
        Circular queues add the following functionality: 
       
        circular queue 增加了下述功能： 
       
        1.   Entries can be added at the end of a list. 
       
        2.   Entries can be added before another entry. 
       
        3.   They may be traversed backwards, from 
        tail 
        to 
        head
        . 
       
        1. 可以在 list 的最后增加 entry 。 
       
        2. 可以在任意其他的 entry 之前增加 entry 。 
       
        3. 可以进行后向遍历，即从 queue 尾到 queue 头。 
       
        However: 
       
        但是： 
       
        1.   All list insertions and removals must specify the 
        head 
        of the list. 
       
        2.   Each 
        head 
        entry requires two pointers rather than one. 
       
        3.   The termination condition 
        for 
        traversal is 
        more 
        complex. 
       
        4.   Code size is about 40% greater and operations run about 45% slower than lists. 
       
        1. 所有的 list 插入和移除操作均必须提供 list 的头指针。 
       
        2. 每一个 
        head 
        entry 都要求含有两个指针，而不是一个指针。 
       
        3. 遍历的终止条件更加复杂。 
       
        4. 与 list 相比，代码量增加大约 40% ，运算速度减慢大约 45% 。 
       
        In the macro definitions, TYPE is the name of a user defined structure, that must contain a field of 
        type 
        LIST_ENTRY, TAILQ_ENTRY, or CIRCLEQ_ENTRY, named NAME.  The argument HEADNAME is the name of a user defined structure that must be declared using the macros LIST_HEAD, TAILQ_HEAD, or CIRCLEQ_HEAD.  See the examples below 
        for 
        further explanation of how these macros are used. 
       
        在上述宏定义中，TYPE 是用户定义结构的名字，且该结构中含有类型为 LIST_ENTRY 、TAILQ_ENTRY ，或 CIRCLEQ_ENTRY 的域，且命名为 NAME 。参数 HEADNAME 是用户定义结构的名字，其必须事先通过宏 LIST_HEAD 、TAILQ_HEAD ，或 CIRCLEQ_HEAD 定义好。详细信息可以参考下面的例子。 
       
        LISTS
       
        A list is headed by a structure defined by the LIST_HEAD macro.  This structure contains a single pointer to the first element on the list.  The elements are doubly linked so that an arbitrary element can be removed without traversing the list.  New elements can be added to the list after an existing element or at the 
        head 
        of the list. 
       
        list 可通过由宏 LIST_HEAD 定义的结构进行访问操作。该结构包含单独一个指针指向 list 的头部。list 中的元素以双链表的方式进行组织，故无需遍历 list 就可将任意元素删除。新元素可以添加到 list 中指定元素的后边，或者 list 的尾部。 
       
        A LIST_HEAD structure is declared as follows: 
       
        声明一个 LIST_HEAD 结构如下： 
       
        LIST_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 list.  A pointer to the 
        head 
        of the list can later be declared as: 
       
        其中 HEADNAME 是要定义的结构的名字，而 TYPE 用于表示将在 list 表中进行链接的元素的类型。指向 list 头的指针可以按如下方式进行声明： 
       
        struct HEADNAME *headp; 
       
        (The names 
        head 
        and headp are user selectable.) 
       
        The macro LIST_ENTRY declares a structure that connects the elements 
        in 
        the list. 
       
        宏 LIST_ENTRY 声明用于在 list 中将元素链接起来的结构。 
       
        The macro LIST_INIT initializes the list referenced by 
        head
        . 
       
        宏 LIST_INIT 用于初始化由 
        head 
        指向的 list 。 
       
        The macro LIST_INSERT_HEAD inserts the new element elm at the 
        head 
        of the list. 
       
        宏 LIST_INSERT_HEAD 用于在 list 头部插入新元素。 
       
        The macro LIST_INSERT_AFTER inserts the new element elm after the element listelm. 
       
        宏 LIST_INSERT_AFTER 用于在指定元素后插入新元素。 
       
        The macro LIST_REMOVE removes the element elm from the list. 
       
        宏 LIST_REMOVE 用于从 list 中移除元素。 
       
        LIST EXAMPLE
       
        list 操作范例
       
        LIST_HEAD(listhead, entry) 
        head
        ; 
       
        struct listhead *headp;         /* List 
        head
        . */ 
       
        struct entry { 
       
        ... 
       
        LIST_ENTRY(entry) entries;      /* List. */ 
       
        ... 
       
        } *n1, *n2, *np; 
       
        LIST_INIT(&
        head
        );                       /* Initialize the list. */ 
       
        n1 = malloc(sizeof(struct entry));      /* Insert at the 
        head
        . */ 
       
        LIST_INSERT_HEAD(&
        head
        , n1, entries); 
       
        n2 = malloc(sizeof(struct entry));      /* Insert after. */ 
       
        LIST_INSERT_AFTER(n1, n2, entries); 
       
        /* Forward traversal. */ 
       
        for 
        (np = 
        head
        .lh_first; np != NULL; np = np->entries.le_next) 
       
        np-> ... 
       
        while 
        (
        head
        .lh_first != NULL)           /* Delete. */ 
       
        LIST_REMOVE(
        head
        .lh_first, entries); 
       
        TAIL QUEUES
       
        A 
        tail 
        queue is headed by a structure defined by the TAILQ_HEAD macro.  This structure contains a pair of pointers, one to the first element 
        in 
        the 
        tail 
        queue and the other to the last element 
        in 
        the 
        tail 
        queue.  The elements are doubly linked so that an arbitrary element can be removed without traversing the 
        tail 
        queue.  New elements can be added to the 
        tail 
        queue after an existing element, at the 
        head 
        of the 
        tail 
        queue, or at the end of the 
        tail 
        queue.  A TAILQ_HEAD structure is declared as follows: 
       
        tail 
        queue 可通过由宏 TAILQ_HEAD 定义的结构进行访问操作。该结构包含一对指针，一个指向 
        tail 
        queue 的头部，一个指向 
        tail 
        queue 的尾部。
        tail 
        queue 中的元素以双链表的方式进行组织，故无需遍历 
        tail 
        queue 就可将任意元素删除。新元素可以添加到指定元素的后边、
        tail 
        queue 的头部、或者 
        tail 
        queue 的尾部。TAILQ_HEAD 结构的声明如下： 
       
        TAILQ_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 
        tail 
        queue.  A pointer to the 
        head 
        of the 
        tail 
        queue can later be declared as: 
       
        其中 HEADNAME 是要定义的结构的名字，TYPE 是链接进该 
        tail 
        queue 的元素的类型。指向 
        tail 
        queue 头部的指针可按如下方式声明： 
       
        struct HEADNAME *headp; 
       
        (The names 
        head 
        and headp are user selectable.) 
       
        The macro TAILQ_ENTRY declares a structure that connects the elements 
        in 
        the 
        tail 
        queue. 
       
        宏 TAILQ_ENTRY 声明用于在 
        tail 
        queue 中将元素链接起来的结构。 
       
        The macro TAILQ_INIT initializes the 
        tail 
        queue referenced by 
        head
        . 
       
        宏 TAILQ_INIT 用于初始化由 
        head 
        指向的 
        tail 
        queue 。 
       
        The macro TAILQ_INSERT_HEAD inserts the new element elm at the 
        head 
        of the 
        tail 
        queue. 
       
        宏 TAILQ_INSERT_HEAD 用于在 
        tail 
        queue 头部插入新元素。 
       
        The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the 
        tail 
        queue. 
       
        宏 TAILQ_INSERT_TAIL 用于在 
        tail 
        queue 尾部插入新元素。 
       
        The macro TAILQ_INSERT_AFTER inserts the new element elm after the element listelm. 
       
        宏 TAILQ_INSERT_AFTER 用于在指定元素后插入新元素。 
       
        The macro TAILQ_REMOVE removes the element elm from the 
        tail 
        queue. 
       
        宏 TAILQ_REMOVE 用于从 
        tail 
        queue 中移除元素。 
       
        TAIL QUEUE EXAMPLE
       
        TAIL QUEUE 操作范例
       
        TAILQ_HEAD(tailhead, entry) 
        head
        ; 
       
        struct tailhead *headp;         /* Tail queue 
        head
        . */ 
       
        struct entry { 
       
        ... 
       
        TAILQ_ENTRY(entry) entries;     /* Tail queue. */ 
       
        ... 
       
        } *n1, *n2, *np; 
       
        TAILQ_INIT(&
        head
        );                      /* Initialize the queue. */ 
       
        n1 = malloc(sizeof(struct entry));      /* Insert at the 
        head
        . */ 
       
        TAILQ_INSERT_HEAD(&
        head
        , n1, entries); 
       
        n1 = malloc(sizeof(struct entry));      /* Insert at the 
        tail
        . */ 
       
        TAILQ_INSERT_TAIL(&
        head
        , n1, entries); 
       
        n2 = malloc(sizeof(struct entry));      /* Insert after. */ 
       
        TAILQ_INSERT_AFTER(&
        head
        , n1, n2, entries); 
       
        /* Forward traversal. */ 
       
        for 
        (np = 
        head
        .tqh_first; np != NULL; np = np->entries.tqe_next) 
       
        np-> ... 
       
        /* Delete. */ 
       
        while 
        (
        head
        .tqh_first != NULL) 
       
        TAILQ_REMOVE(&
        head
        , 
        head
        .tqh_first, entries); 
       
        CIRCULAR QUEUES
       
        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 element 
        in 
        the circular queue and the other to the last element 
        in 
        the circular 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 structure is declared as follows: 
       
        circular queue 可通过由宏 CIRCLEQ_HEAD 定义的结构进行访问操作。该结构包含一对指针，一个指向 circular queue 的头部，一个指向 circular queue 的尾部。circular queue 中的元素以双链表的方式进行组织，故无需遍历 circular queue 就可将任意元素删除。新元素可以添加到指定元素的后边、前面、circular queue 的头部、或者 
        tail 
        queue 的尾部。CIRCLEQ_HEAD 结构的声明如下： 
       
        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: 
       
        其中 HEADNAME 是要定义的结构的名字，TYPE 是链接进该 circular queue 的元素的类型。指向 
        tail 
        queue 头部的指针可按如下方式声明： 
       
        struct HEADNAME *headp; 
       
        (The names 
        head 
        and headp are user selectable.) 
       
        The macro CIRCLEQ_ENTRY declares a structure that connects the elements 
        in 
        the circular queue. 
       
        宏 CIRCLEQ_ENTRY 声明用于在 circular queue 中将元素链接起来的结构。 
       
        The macro CIRCLEQ_INIT initializes the circular queue referenced by 
        head
        . 
       
        宏 CIRCLEQ_INIT 用于初始化由 
        head 
        指向的 circular queue 。 
       
        The macro CIRCLEQ_INSERT_HEAD inserts the new element elm at the 
        head 
        of the circular queue. 
       
        宏 CIRCLEQ_INSERT_HEAD 用于在 circular queue 头部插入新元素。 
       
        The macro CIRCLEQ_INSERT_TAIL inserts the new element elm at the end of the circular queue. 
       
        宏 CIRCLEQ_INSERT_TAIL 用于在 circular queue 尾部插入新元素。 
       
        The macro CIRCLEQ_INSERT_AFTER inserts the new element elm after the element listelm. 
       
        宏 CIRCLEQ_INSERT_AFTER 用于在指定元素后插入新元素。 
       
        The macro CIRCLEQ_INSERT_BEFORE inserts the new element elm before the element listelm. 
       
        宏 CIRCLEQ_INSERT_BEFORE 用于在指定元素后插入新元素。 
       
        The macro CIRCLEQ_REMOVE removes the element elm from the circular queue. 
       
        宏 CIRCLEQ_REMOVE 用于从 circular queue 中移除元素。 
       
        CIRCULAR QUEUE EXAMPLE
       
        CIRCULAR QUEUE 操作范例
       
        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); 
       
        /* Forward traversal. */ 
       
        for 
        (np = 
        head
        .cqh_first; np != (void *)&
        head
        ; np = np->entries.cqe_next) 
       
        np-> ... 
       
        /* Reverse traversal. */ 
       
        for 
        (np = 
        head
        .cqh_last; np != (void *)&
        head
        ; np = np->entries.cqe_prev) 
       
        np-> ... 
       
        /* Delete. */ 
       
        while 
        (
        head
        .cqh_first != (void *)&
        head
        ) 
       
        CIRCLEQ_REMOVE(&
        head
        , 
        head
        .cqh_first, entries); 
       
        CONFORMING TO
       
        Not 
        in 
        POSIX.1-2001.  Present on the BSDs.  The queue functions first appeared 
        in 
        4.4BSD. 
       
        4BSD                           January 24, 1994                           4BSD
       
        (END)

经查证，BSD 的 queue 实现在诸多开源库中均有出现，比如 libevent、twemproxy、twemperf 和 twemcache 。其中的封装大同小异。具体的使用方法可以参考上面 man 命令给出的示例程序，也可以参考上述开源实现中的用法。唯一要说明的是， BSD queue 的实现中不涉及任何锁相关操作 ，故在实际使用中需按情况进行相应改动。

======== 2013-11-29 更新 =========
libevent 的源码中也包含对 queue.h 的兼容实现头文件。一般存在于 libevent-x.x.xx-stable\compat\sys 目录下。

【原创】Twemperf 中对 BSD queue.h 的兼容实现

热门文章

最新文章

相关电子书