技术总结|tailq详解

用户1904552

发布于 2023-04-17 19:22:24

9850

发布于 2023-04-17 19:22:24

文章被收录于专栏：周末程序猿

tailq介绍

TAILQ是linux内核对双向队列操作的一种抽象，能实现操作队列需要的各种操作：插入元素，删除元素，遍历队列等，其封装是对应的宏定义，下面详细说明tailq的操作，从定义，初始化，插入，删除和遍历这几个API来介绍，并且提供c++版本的tailq。

tailq的宏定义API

（1）定义：TAILQ_ENTRY(type) 初始化一个type类型的entry

#define TAILQ_ENTRY(type)   \
    struct {                \
        struct type *tqe_next;  \
        struct type **tqe_prev; \
        TRACEBUF        \
    }

其中TRACEBUF是一个用来调试的宏：

struct node{    
    int a, b, c;
    TAILQ_ENTRY(node);
};

展开如下：

struct node{ 
    int a, b, c;    
    struct {        
        struct node *tqe_next;
        sturct node **tqe_prev;
    };
};

（2）定义：TAILQ_HEAD(name, type) 初始化name的结构体，类型为type，初始化头部

#define TAILQ_HEAD(name, type)  \
    struct name {               \
        struct type **tqh_last; \
        TRACEBUF                \
    }

展开如下：

struct head {
    struct node *tqh_first;
    struct node **tqh_last;
} q_head;

（3）初始化：TAILQ_INIT(head) 初始化头部，其中head是上面的TAILQ_HEAD

#define TAILQ_INIT(head) do {                       \
    TAILQ_FIRST((head)) = NULL;                     \
    (head)->tqh_last = &TAILQ_FIRST((head));        \
    QMD_TRACE_HEAD(head);                           \
} while (0)

其中QMD_TRACE_HEAD为了debug而设置的。

（4）插入：TAILQ_INSERT_TAIL(head, elm, field) head是TAILQ_HEAD的头部，elm是对应需要处理的节点，field就是对应上面的TAILQ_ENTRY

#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)

其中插入方式是通过尾插法，QMD_TAILQ_CHECK_TAIL，QMD_TRACE_HEAD，QMD_TRACE_ELEM对应调试信息。

（5）删除：TAILQ_REMOVE(head, elm, field) head是TAILQ_HEAD的头部，elm是对应需要处理的节点，field就是对应上面的TAILQ_ENTRY

#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)

其中删除的方式是删除头部位置的最近的节点。

（6）遍历：TAILQ_FOREACH(var, head, field) var是临时变量，head对应TAILQ_HEAD的定义，field对应TAILQ_ENTRY

#define TAILQ_FOREACH(var, head, field)                 \
        for ((var) = TAILQ_FIRST((head));               \
            (var);                                      \
            (var) = TAILQ_NEXT((var), field))

（7）其他操作宏

#define TAILQ_FIRST(head)  \
   ((head)->tqh_first) // 队列的第一个节点
#define TAILQ_NEXT(elm, field) \
   ((elm)->field.tqe_next) // 当前elm的下一个节点

tailq的c++实现

CPP_TAILQ_ENTRY {
public:
    T *tqe_next;  // next element
    T **tqe_prev; // address of previous next element
};

template<class T>
class CPP_TAILQ_HEAD
{public:
    T *tqh_first; // first element
    T **tqh_last; // addr of last next element
};

#define CPP_TAILQ_FIRST(head)       ((head)->tqh_first)#define CPP_TAILQ_NEXT(elm, field)  ((elm)->field.tqe_next)
#define CPP_TAILQ_EMPTY(head)       ((head)->tqh_first == NULL) // 判断队列是否为空
#define CPP_TAILQ_INIT(head) do {                   \
    CPP_TAILQ_FIRST((head)) = NULL;                 \
    (head)->tqh_last = &CPP_TAILQ_FIRST((head));    \
} while (0)

#define CPP_TAILQ_FOREACH(var, head, field)         \
    for ((var) = CPP_TAILQ_FIRST((head));           \
        (var);                                      \
        (var) = CPP_TAILQ_NEXT((var), field))

#define CPP_TAILQ_FOREACH_SAFE(var, head, field, tvar)              \ 
         for ((var) = CPP_TAILQ_FIRST((head));                      \ 
             (var) && ((tvar) = CPP_TAILQ_NEXT((var), field), 1);   \ 
             (var) = (tvar)) 

#define CPP_TAILQ_REMOVE(head, elm, field) do {             \
    if ((CPP_TAILQ_NEXT((elm), field)) != NULL)             \
        CPP_TAILQ_NEXT((elm), field)->field.tqe_prev =      \
            (elm)->field.tqe_prev;                          \    
        else {                                               \
        (head)->tqh_last = (elm)->field.tqe_prev;           \
    }                                                       \
    *(elm)->field.tqe_prev = CPP_TAILQ_NEXT((elm), field);  \
} while (0)

#define CPP_TAILQ_INSERT_TAIL(head, elm, field) do {        \
    CPP_TAILQ_NEXT((elm), field) = NULL;                    \
    (elm)->field.tqe_prev = (head)->tqh_last;               \
    *(head)->tqh_last = (elm);                              \
    (head)->tqh_last = &CPP_TAILQ_NEXT((elm), field);       \
} while (0)

#define CPP_TAILQ_CONCAT(head1, head2, field) do {          \
    if (!CPP_TAILQ_EMPTY(head2)) {                          \
        *(head1)->tqh_last = (head2)->tqh_first;            \
        (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;     \
        (head1)->tqh_last = (head2)->tqh_last;                      \
        CPP_TAILQ_INIT((head2));                                    \
    }                                                               \
} while (0)

使用gtest写的部分的测试用例如下：

class TestInt;
typedef CPP_TAILQ_HEAD<TestInt> TestIntList;
class TestInt {
public:
    TestInt(int _d) : d_(_d)
    { }

public:
    CPP_TAILQ_ENTRY<TestInt> entry_;
    int d_;
};

// 插入的测试用例TEST(TAILQTest, INSERT_TAIL) 
{
    int arr[10] = {1, 2, 3, 4, 5};
    TestIntList tset;
    CPP_TAILQ_INIT(&tset);
    TestInt* ti1 = NULL;
    int idx = 0;    
    for (; idx < sizeof(arr)/sizeof(arr[0]); idx++)
    {
        ti1 = new TestInt(arr[idx]);
        CPP_TAILQ_INSERT_TAIL(&tset, ti1, entry_);
    }

    idx = 0;
    TestInt* ti2 = NULL;
    CPP_TAILQ_FOREACH(ti2, &tset, entry_)
    {        
        // LOG_TRACE("ti2 value : %d", ti2->d_);
        EXPECT_EQ(arr[idx++], ti2->d_);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-03-20，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历