list和hlist

题记

之前学习Linux内核的时候对于这两个结构的已经接触过，但是和我最初学习数据结构的构造方式不太一样，很长时间也没能理解，甚至觉得自己直接手写结构也问题不大。直到最近移植了两个功能，深深感觉到linux自带数据结构的库有多么好用，自己造轮子实在很麻烦，也很不利于二次读代码，所以现在把关于hlist和list的内容整理一下，以后再也不会自己造轮子了，用现成的库既好维护也好阅读。

list篇

节点定义

linux库对双链表节点的设计理念是将链表节点塞在其他数据结构中使用，降低数据和结构的耦合性，将对链表的操作全部抽象出来封装成库。

struct list_head {
	struct list_head *next, *prev;
};

初始化

可以很明显看出来有头节点。

这里的双链表是有头节点的结构，即使链表被判断为空，实际上链表中有一个头节点。
双链表是一定要初始化的，根据初始化函数的内容很容易看出，双链表初始化的节点next和prev域指针都是指向自己本节点而不是NULL，所以在之后的调试过程中出现空指针，一般两种情况，一种是代码中写错了，强行访问空指针，另外一种就是没有初始化头节点。

静态初始化

静态初始化只用于定义声明的地方，因为这里都是宏定义的语句，这种结构体声明的写法是只能在声明定义的时候使用，不可以用在之后的赋值中。如果只是需要一个双链表就直接用这个“LIST_HEAD”去声明就好了。

#define LIST_HEAD_INIT(name) { &(name), &(name) }//这种结构体声明的写法是只能在声明的时候使用。

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
示例：
LIST_HEAD (&my_list_head);

动态初始化

动态初始化是在在声明之后的赋值中使用，一般这种情况是，双链表被挂在其他结构中使用，比如首先大结构是个二叉树，每个二叉树节点都挂一个双链表，这时你的双链表就只能使用这种动态初始化去赋值。

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}
示例：
struct list_head my_list;
INIT_LIST_HEAD(&my_list);

宏函数操作

函数操作

hlist篇

节点定义

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;//这里的pprev存储前继节点地址的地址。
};

初始化

初始化方法有四个，分别针对hlist_head和hlist_node

[法一]
#define HLIST_HEAD_INIT { .first = NULL }   //不推荐使用

[法二]
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }  //hlist_head静态初始化方法初始化方法，只能在声明的时候使用。
示例：
HLIST_HEAD(my_hlist_head);//声明

[法三]
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)  //hlist_head动态初始化方法初始化方法，必须先声明。
示例：
hlist_head my_hlist_head;//声明
INIT_HLIST_HEAD(&my_hlist_head);//初始化

[法四]
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}//hlist_node动态初始化方法初始化方法，必须先声明。
示例：
hlist_node my_hlist_node;//声明
INIT_HLIST_NODE(&my_hlist_node);//初始化

宏函数操作

函数操作