LibEvent代码阅读--TAILQ_ENTRY联想hlist_node

在阅读代码的过程中经常出现采用宏定义数据结构的问题，这种宏定义的方式简化了临时类型的定时，能够快速的定义新的类型:

#define TAILQ_ENTRY(type)                        \
struct {                                \
    struct type *tqe_next;    /* next element */            \
    struct type **tqe_prev;    /* address of previous next element */    \
}

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

以上代码能够通过传递不同的类型快速的创建新的数据结构，并不需要进行相关的定义，快速简洁，这种编码的方式也是很多开源代码中经常使用的形式，不是说明这种形式的优势，而是记录一下为什么采用了指向该对象的指针(**tqe_prev)，而不是通常情况下采用的前一个对象的指针。由该结构体的形式，回忆起了linux内核源码list.h中的hlist_node结构体，如下所示:

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

在这个结构体中为什么不采用prev，而是定义一个pprev指针呢?原因主要是这个对象的使用场景使用这种方式能够较好的实现管理，hlist通常被用来实现hash链表，也就是在某个hash节点中保存一个hlist_head，然后映射到该节点下的对象采用链表的方式管理。通常情况下这种映射不会很多，也就是这个链表中的节点不会很多，如果很多说明对应的hash算法存在问题。这种方式减少了双向链表的内存需求，虽然不能执行快速的双向查找，但在较少节点成员的情况下，对性能影响并不大。
hlist_node中的next是指向下一个对象的指针，而pprev则是指向前一个对象指针的指针，前一个对象的指针的指针实际也就是next指针的指针（有点儿绕）。prev指向了前一个对象，也就是一个hlist_node, pprev则是指向了这个对象的指针，也就是pprev实际上指向了&list_node,实际上&list_node和第一个成员的取地址实际上是一样的，因此&list_node取地址，也可以认为是&next，也就是next指针的指针。

在hlist_head中只定义了一个first，这比list_head中少了一个成员，这就简化了数据成员的添加操作，在list_head中添加成员通常需要判断当前链表中是否存在节点，而hlist则不需要,如下所示:

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    struct hlist_node *first = h->first;
    n->next = first;//添加到头部，next执行当前head的first
    if (first) //如果当前list中有成员，则将frist的pprev指向需要添加的成员指针
        first->pprev = &n->next;
    h->first = n;//更新head的first成员
    n->pprev = &h->first; //新添加的成员执行first的指针
}

在链表中删除对象实际上也不需要list_head，这个在list的操作中需要无处不在的head。

static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;  //当前对象的前一个对象的next指针
    *pprev = next;  //*prev实际是前一个对象的next，因此*pprev就是前一个对象的next执行了当前对象的next
    if (next)
        next->pprev = pprev;  //下一个节点的prev执行当前节点的pprev
}

static inline void hlist_del(struct hlist_node *n)
{
    __hlist_del(n);
    n->next = LIST_POISON1;
    n->pprev = LIST_POISON2;
}

这种hlist的节点删除相比list的删除要更加的方便。

这边进行简单的分析，仅仅用于记录。
更贱详细的分析可以参见http://blog.csdn.net/hs794502825/article/details/24597773.

TAILQ_ENTRY的定义方式实际是将hlist_node更加的实例化，基本的思路还是一样。