tail queue in queue.h for free bsd

     /*
     * 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 definitions.
    */
   #define (, )                                          \
   struct  {                                                           \
           struct  *tqh_first; /* first element */                     \
           struct  **tqh_last; /* addr of last next element */         \
   }
   
   #define ()                                    \
           { , &().tqh_first }
   
   #define ()                                               \
   struct {                                                                \
           struct  *tqe_next;  /* next element */                      \
           struct  **tqe_prev; /* address of previous next element */  \
   }
   
   /* 
    * tail queue access methods 
    */
   #define ()               (()->tqh_first)
   #define ()                 
   #define (elm, )          ((elm)->.tqe_next)
   #define (, headname)                                      \
           (*(((struct headname *)(()->tqh_last))->tqh_last))
   /* XXX */
   #define (elm, headname, )                                \
           (*(((struct headname *)((elm)->.tqe_prev))->tqh_last))
   #define ()                                               \
           (() == ())
   
   #define (var, , )                                 \
           for((var) = ();                                  \
               (var) != ();                                   \
               (var) = (var, ))
   
   #define (var, , headname, )               \
           for((var) = (, headname);                         \
               (var) != ();                                   \
               (var) = (var, headname, ))
   
   /*
    * Tail queue functions.
    */
   #define () do {                                           \
           ()->tqh_first = ;                                       \
           ()->tqh_last = &()->tqh_first;                          \
   } while (0)
   
   #define (, elm, ) do {                        \
           if (((elm)->.tqe_next = ()->tqh_first) != )        \
                   ()->tqh_first->.tqe_prev =                     \
                       &(elm)->.tqe_next;                             \
           else                                                            \
                   ()->tqh_last = &(elm)->.tqe_next;              \
           ()->tqh_first = (elm);                                      \
           (elm)->.tqe_prev = &()->tqh_first;                     \
   } while (0)
   
   #define (, elm, ) do {                        \
           (elm)->.tqe_next = ;                                   \
           (elm)->.tqe_prev = ()->tqh_last;                       \
           *()->tqh_last = (elm);                                      \
           ()->tqh_last = &(elm)->.tqe_next;                      \
   } while (0)
   
   #define (, listelm, elm, ) do {              \
           if (((elm)->.tqe_next = (listelm)->.tqe_next) != )\
                   (elm)->.tqe_next->.tqe_prev =                 \
                       &(elm)->.tqe_next;                             \
           else                                                            \
                   ()->tqh_last = &(elm)->.tqe_next;              \
           (listelm)->.tqe_next = (elm);                              \
           (elm)->.tqe_prev = &(listelm)->.tqe_next;             \
   } while (0)
   
   #define (listelm, elm, ) do {                   \
           (elm)->.tqe_prev = (listelm)->.tqe_prev;              \
           (elm)->.tqe_next = (listelm);                              \
           *(listelm)->.tqe_prev = (elm);                             \
           (listelm)->.tqe_prev = &(elm)->.tqe_next;             \
   } while (0)
   
   #define (, elm, ) do {                             \
           if (((elm)->.tqe_next) != )                            \
                   (elm)->.tqe_next->.tqe_prev =                 \
                       (elm)->.tqe_prev;                              \
           else                                                            \
                   ()->tqh_last = (elm)->.tqe_prev;               \
           *(elm)->.tqe_prev = (elm)->.tqe_next;                 \
           ((elm)->.tqe_prev);                           \
           ((elm)->.tqe_next);                           \
   } while (0)
   
   #define (, elm, elm2, ) do {                      \
           if (((elm2)->.tqe_next = (elm)->.tqe_next) != )   \
                   (elm2)->.tqe_next->.tqe_prev =                \
                       &(elm2)->.tqe_next;                            \
           else                                                            \
                   ()->tqh_last = &(elm2)->.tqe_next;             \
           (elm2)->.tqe_prev = (elm)->.tqe_prev;                 \
           *(elm2)->.tqe_prev = (elm2);                               \
           ((elm)->.tqe_prev);                           \
           ((elm)->.tqe_next);                           \
   } while (0)


Tail queue 使用例子：
test1.c

#include 
#include "queue.h"


#define REPEAT 500
#define NOBJECTS 1000000

// 在程序中如果我们想使用queue.h中提供的东西来
// 简便地将自己的数据存储在队列中，就要定义如下的结构体:
// 结构体中前面几项是自己的数据，最后一项是 TAILQ_ENTRY(..)...
// 当然，如果最后一项根据自己选择的队列类型也可以是
// SLIST_ENTRY或LIST_ENTRY或SIMPLEQ_ENTRY或CIRCLEQ_ENTRY
struct object{
    char anything[7]; // 这里我们自己的数据很简单，是字符数组
    TAILQ_ENTRY(object) tailq_entry;
};



struct object objects[NOBJECTS]; 

TAILQ_HEAD(,object) the_tailq;   // 定义TAILQ队列头(definations)
TAILQ_INIT(&the_tailq);          // 初始化TAILQ队列头(functions)

static void test_tailq(){
    int t;
    puts("Testing TAILQ...");
    for (t = 0; t < REPEAT; t++) {
        int i;

        for (i = 0; i < NOBJECTS; i++) {
            TAILQ_INSERT_TAIL(&the_tailq, objects+i, tailq_entry);
        }
        for (i = 0; i < NOBJECTS; i++) {
            TAILQ_REMOVE_HEAD(&the_tailq, tailq_entry);
        }
    }
}


int main(){

    test_stailq();

    return 0;
}

test2.c

1. #include  
2. #include   
3. #include "queue.h"  
4.   
5. struct QUEUE_ITEM{  
6.     int value;  
7.     TAILQ_ENTRY(QUEUE_ITEM) entries;  
8. };  
9. TAILQ_HEAD(,QUEUE_ITEM) queue_head;  
10. int main(int argc,char **argv){  
11.     struct QUEUE_ITEM *item;  
12.     struct QUEUE_ITEM *tmp_item;  
13.   
14.     TAILQ_INIT(&queue_head);  
15.     int i=0;  
16.     for(i=5;i<10;i+=2){  
17.         item=malloc(sizeof(item));  
18.         item->value=i;  
19.         TAILQ_INSERT_TAIL(&queue_head, item, entries);  
20.     }  
21.       
22.     struct QUEUE_ITEM *ins_item;  
23.     ins_item=malloc(sizeof(ins_item));  
24.   
25.     ins_item->value=100;  
26.     TAILQ_INSERT_BEFORE(item,ins_item,entries);  
27.   
28.   
29.     tmp_item=TAILQ_FIRST(&queue_head);  
30.     printf("first element is %d\n",tmp_item->value);  
31.   
32.     tmp_item=TAILQ_NEXT(tmp_item,entries);  
33.     printf("next element is %d\n",tmp_item->value);  
34.   
35.     tmp_item=TAILQ_NEXT(tmp_item,entries);  
36.     printf("next element is %d\n",tmp_item->value);  
37.   
38.     tmp_item=TAILQ_NEXT(tmp_item,entries);  
39.     printf("next element is %d\n",tmp_item->value);  
40.   
41. }