linux内核list.h头文件分析（五）——hlist分析

hlist概述

在前面分析了的list，hlist和list是不相同的，在list中每个节点都是一样的，不管头结点还是其他节点，使用同一个结构体表示，但是hlist不是这样表示的。在hlist中，头结点使用的是struct hlist_head来表示的，而对于其他节点使用的是struct hlist_node这个数据结构来表示的。另外，还有一点hlist和list是不相同的，hlist不是双向循环链表，至于为什么要这么设计hlist，原因就是为了去掉list头结点中的prev变量，这样就可以节省空间资源。

具体的有关hlist的空间表示，请参阅图1所示。

 

图1 hlist的空间表示

首先我们要彻底理解struct hlist_node **prev中的二级指针表示的含义。pprev首先也是一个指针，不过它是指向指针的指针（这点请仔细体会），在hlist中pprev指向的是当前hlist_node变量中的前一个变量的next的地址，如果是第一个元素的话，这个值指向的是first的地址，如果是最后一个节点的话，指向的是NULL。如果再深入理解一下，其实*pprev和next这两个变量分别表示指向自己的指针和指向其他节点的指针。

（一）hlist的定义与初始化

下面看一下hlist节点的定义

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

#define HLIST_HEAD_INIT { .first = NULL }

这个宏定义是用来给struct hlist_head变量来进行初始化的。

#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }

这个宏就不用多说了吧，就是定一个一个struct hlist_head节点，并且给其初始化为NULL。

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

这个宏是给struct hlist_head节点进行初始化的。

static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
    h->next = NULL;
    h->pprev = NULL;
}

这个宏函数是对struct hlist_node节点的一个变量进行初始化的操作。这个宏用在删除节点之后对节点的操作当中。

这么来设计链表结构可能还有另外一个好处：

给pCur的当前节点节点的前面增加一个节点pNode是比较方便的

pNode->next = pCur;

*(pCur->pprev) = pNode;

（二）判断链表是不是空链，节点是不是空节点。

h：struct hlist_node节点指针。

判断h->prev是不是为空，如果pprev的指向是空的话，表示这个节点没有添加到这个链表当中来，如果是空，返回true，否则返回false。这个宏在删除操作当中使用了，在其他许多地方也有调用这个判断。

static inline int hlist_unhashed(const struct hlist_node *h)
{
    return !h->pprev;
}

h：struct hlist_head节点指针（hlist链表的头节点）。

判断hlist链表是不是空链表，如果是，返回true，否则返回false。

static inline int hlist_empty(const struct hlist_head *h)
{
    return !h->first;
}

（三）hlist的删除节点的操作

注：如果对于删除操作理解不是很好时，建议先看下面的增加节点的操作，我是按照内核代码中的顺序进行分析的。

在删除操作这里提供了两个接口：

static inline void hlist_del(struct hlist_node *n)

static inline void hlist_del_init(struct hlist_node *n)

其中第一个接口是将n这个节点删除后不可用指向LIST_POSION，但是后者的话，将删除之后的节点调用了INIT_HLIST_NODE(n)操作，这样就使删除的这个节点中的元素指向了NULL。

真正的删除操作是在static inline void __hlist_del(struct hlist_node *n)中实现的。

n：要删除的节点。

对于删除操作的话，要注意n是不是末尾节点，如果是末尾节点的话，next就是NULL，所以就没有指向的pprev，就更不能进行相应的修改了，否则进行修改。

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

n：要删除的节点。

在这个函数中首先删除了n节点，之后将n节点的两个指针指向了LIST_POSION，表示不可使用的地方。

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

n：要删除的节点。

首先判断要删除的pprev是不是空，如果是，则不能删除，否则进行删除操作，删除完成之后，将n节点的next和pprev都指向NULL（初始化节点）。

至于这里为什么要判断，我也没有搞清楚。

static inline void hlist_del_init(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        __hlist_del(n);
        INIT_HLIST_NODE(n);
    }
}

（四）hlist增加节点的操作

在增加操作中提供了三个接口：

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)

static inline void hlist_add_before(struct hlist_node *n,

struct hlist_node *next)

static inline void hlist_add_after(struct hlist_node *n,

struct hlist_node *next)

下面我们一一来分析：

n：要添加的新的节点。

h：hlist链表的表头节点。

这个函数是给h的下一个和first节点中添加一个新的hlist_node节点，类似与头插。

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    struct hlist_node *first = h->first;
    n->next = first;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    n->pprev = &h->first;
}

n：要添加的新的节点。

next：在next节点之前添加n。

在next节点的前面添加一个新的节点n，在使用这个函数中要特别注意，next不能为NULL。

static inline void hlist_add_before(struct hlist_node *n,
                    struct hlist_node *next)
{
    n->pprev = next->pprev;
    n->next = next;
    next->pprev = &n->next;
    *(n->pprev) = n;
}

对于这段代码的前三句都比较好理解一些，对于*(n->pprev) = n这句，其实就是将添加之前时的next的前面那个节点的next指针指向n这个新增加的节点。

n：表示在n节点之后添加next。

next：要添加的新的节点。

在n节点的后面添加一个新的节点next，这里也要求n不能为NULL。

static inline void hlist_add_after(struct hlist_node *n,
                    struct hlist_node *next)
{
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;

    if(next->next)
        next->next->pprev = &next->next;
}

总的来说，对于hlist添加一个节点要把握4个指针的指向。