linux内核哈希链表解析

系统管理员 2022-08-20 12:05 185阅读 0赞

哈希表的介绍  hlist  
linux内核里边除了著名的list双向循环链表以外，还有一个重要的数据结构，就是哈希链表。哈希链表也在很多重要的地方有所使用，比如linux内核的dentry，进程查询，文件系统等，可以说，弄明白hlist对于理解linux内核具有重要的意义。  
数据结构的介绍

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

linux内核的哈希链表有两个数据结构组成，一个是hlist\_head是哈希表的表头，一个是hlist\_node，是哈希表的后续节点。在使用的时候，一般定义一个struct hlist\_head xxx\[100\]数组（100只是一个代表的数字，视具体情况而定），采取哈希函数来将键值与数组的对应的地址联系起来，如果出现冲突的话，就在hlist\_head的后边继续添加。  
hlist\_head的成员first指针指向后续的第一个节点，如果哈希链表是空的话，就为NULL。  
为什么hlist\_head不弄成双向链表呢，因为为了节约空间，如果一个指针的话，一个哈希数组的空间消耗就会减半。  
hlist\_node的成员next指向后续的节点的地址，如果为空就是NULL，另一个成员pprev是二级指针，指向前一个节点的next成员的地址，如果前一个成员是hlist\_head的话，pprev的值就是前一个的first指针的地址。  
Linux的链表和散列表的操作函数的定义在include/linux/list.h文件中，接下来就打开这个文件看一下hlist数据结构的操作函数和宏。

#define HLIST_HEAD_INIT { .first = NULL }
    #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
    #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

初始化哈希链表，这三个初始化宏都是建立一个hlist\_head结构体，并把first成员设置为NULL。

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

这个函数是初始化一个hlist\_node数据结构，仅仅是简单的把两个成员变量赋值为NULL而已。

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

这个函数是判断哈希链表的节点是不是在哈希链表上，还是已经被删除了。判断方法是判断pprev成员是不是为空，如果是NULL的话，就说明这个node节点是已经从哈希链表上边删除了，否则的话就说明这个节点仍然在哈希链表上。

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

这个函数是判断哈希链表是不是空，传入参数是哈希链表头，判断方法是判断hlist\_head的first成员是不是为NULL。

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;
    }

此函数是哈希链表删除的主要逻辑函数，传入参数就是要删除的链表节点，首先获得hlist\_node的next和pprev成员，next指向下一个hlist\_node结构体的地址，pprev是上一个成员的next指针的地址，\*pprev就是上一个节点的next指针（也可能是first指针），吧上一个指针的next指针的值变成next指针的值，就代表上一个节点的next指针指向了要删除节点的下一个节点，如果next不为空，下一个指针的pprev成员指向要删除的节点的上一个节点的next成员的地址。  
这个函数就显示了hlist\_node把pprev成员设置为二级指针的优点，就是不必因为上一个节点是hlist\_head还是hlist\_node节点而做不同的操作。如果pprev不是二级指针，而是一个hlist\_node \* prev的话，首先编译的时候就会报错，此外，删除操作的时候还要因为上一个节点是hlist\_head还是hlist\_node做出不同的逻辑。

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

这个函数其实就是上一个函数的收尾的函数，就是在删除以后把已经删除的节点的指针的值更改一下，至于这个LIST\_POISON1和LIST\_POISON2是何方神圣，我们看看这个宏的定义

/********** include/linux/list.h **********/
    /*
     * These are non-NULL pointers that will result in page faults
     * under normal circumstances, used to verify that nobody uses
     * non-initialized list entries.
     */
    #define LIST_POISON1  ((void *) 0x00100100)
    #define LIST_POISON2  ((void *) 0x00200200)

这个宏的上边还有英文的注释，我们看英文就可以明白，这两个值是为了防止有人使用到未初始化的哈希链表，学计算机英语不好也不行啊。。

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

这个函数就是把哈希链表的节点先删除再初始化。

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;
    }

这个函数的作用是把一个哈希链表的节点插入到哈希链表的头节点的后边，传入了hlist\_head和hlist\_node结构体，首先得到hlist\_head的first成员，就是后边的节点的指针，这个节点可能是NULL，然后新插入的节点的next指向first后边的节点，如果first不为空，也就是后边有节点存在，head的后边的节点的pprev成员就指向新插入的节点的next成员的地址，head的first就指向新插入的节点，新插入节点的pprev成员指向head的first成员的地址。

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;
    }

这个函数的作用是把一个节点插入到一个哈希链表的节点的前边，首先把将要插入的节点的pprev成员变量指向next的前边的节点，要插入的节点的next指向下一个节点，然后next节点的pprev就要指向已经插入的节点的next节点的地址，已经插入的节点的pprev指向的前一个节点的值就要变成已经插入节点的地址。

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;
    }

这个函数是把一个节点插入到一个节点的后边，和上一个函数差别不大，唯一需要注意的就是后边可能是NULL。

#define hlist_for_each(pos, head) \
    	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
    	     pos = pos->next)

这个宏是对哈希链表进行遍历的宏，pos代表一个hlist\_node结构体指针，head代表hlist\_head结构体，就是哈洗链表的头。