Linux Hash list相关的知识学习
在看桥接、路由代码时，经常会有hash表相关定的结构，为了能够更好的理解桥接、路由的代码，所以需要好好的理解hash链表
一、相关数据结构
数据结构：
struct hlist_head {
structhlist_node *first;
};
struct hlist_node {
structhlist_node *next, **pprev;
};
二、相关疑问
1、与一般的链表相比，hash list的表头与表节点的数据结构是不同的，其表头只有一个first指针，而没有prev指针，这是为什么呢？
首先我们需要知道hash的概念，对于hash表，其目的是为了方便快速的查找，如果hash表的长度较小的话（即hash数组的大小较小），则冲突的可能性则比较大，这样也就失去了散列表的意义。因此尽可能的维护一直大的hash表，但又要尽可能小的使用内存空间，这就需要改造hash表的数据结构了。普通链表元素都包含2个指针next、prev，而每一个指针则占用4个字节，如果我们能够将链表相关的数据结构所包含的指针减少到一个的话，则hash表的大小就会增加1倍。比如我们使用普通的链表结构list_head定义一个hash表
struct list_head hash[255];该hash表的大小为255，占用内存为255*8bytes。如果使用hlist_head，则相同内存大小，我们可以定义的hash表的大小为500。由此可见，相同内存下，与普通list_head相比，表头仅包含一个指针可以使hash表增倍
2、hlist_node中，为什么pprev是指针的指针，而不是一级指针呢？
这样做就解决了数据结构不一致的问题，hlist_node巧妙的将pprev指向上一个节点的next指针的地址，由于hlist_head和hlist_node指向的下一个节点的指针类型相同，就解决了通用性
三、相关函数介绍：
创建并初始化一个hash表头
#define HLIST_HEAD(name) struct hlist_head name ={ .first = NULL }
/*初始化hash表头，将其first指针置为NULL*/
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
初始化一个hash表节点
/*初始化hash表节点，将其next、pprev指针置为NULL*/
static inline void INIT_HLIST_NODE(struct hlist_node*h)
{
h->next =NULL;
h->pprev =NULL;
}
判断一个hash节点是否在hash表中
/*判断hash表节点是否在hash表中，对于一个hash节点，若其pprev值为NULL，
则说明该hash节点所指向的前一个hash节点的next值为NULL，则说明该节点在hash表中；
若其pprev指针不为NULL，则说明该节点在hash表中*/
static inline int hlist_unhashed(const structhlist_node *h)
{
return!h->pprev;
}
/*判断一个hash表是否为空，若其first指针为空，则是空hash表*/
static inline int hlist_empty(const struct hlist_head*h)
{
return!h->first;
}
Hash节点删除相关的函数
/*从hash表中删除一个hash节点
1、获取要删除节点的next指针
2、获取要删除节点的pprev指针， 这样*pprev即为当前节点的前一个节点所指向的next节点的地址。
3、通过*pprev指针，将n的前一个节点与n->next节点关联
4、如果n->next不等于NULL,则设置n->next->pprev的值。
*/
static inline void __hlist_del(struct hlist_node *n)
{
structhlist_node *next = n->next;
structhlist_node **pprev = n->pprev;
*pprev =next;
if (next)
next->pprev= pprev;
}
/*
1、调用__hlist_del，从hash表中删除一个hash节点
2、将删除节点的next、pprev值分别设置为LIST_POISON1、IST_POISON2
当调用__hlist_del从hash表中删除一个节点后，该节点的next与pprev值并不为空，为防止
代码通过节点n访问到hash表，需要将该节点的next与pprev设置为LIST_POISON1、IST_POISON2
*/
static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);
n->next =LIST_POISON1;
n->pprev =LIST_POISON2;
}
/*
1、调用__hlist_del，从hash表中删除一个hash节点
2、调用INIT_HLIST_NODE初始化节点n的next、pprev指针
*/
static inline void hlist_del_init(struct hlist_node*n)
{
if(!hlist_unhashed(n)) {
__hlist_del(n);
INIT_HLIST_NODE(n);
}
}
增加hash节点相关的函数
/*
在hash表头添加一个节点n
1、获取hash表头h的first指针，即所指向的下一个节点
2、将n->next与h->first关联
3、如果first不为NULL，则h->first->pprev 等于 &n->next
4、h->first 等于n，n->pprev=&h->first
*/
static inline void hlist_add_head(struct hlist_node*n, struct hlist_head *h)
{
structhlist_node *first = h->first;
n->next =first;
if (first)
first->pprev= &n->next;
h->first =n;
n->pprev =&h->first;
}
/*
1、首先将next->pprev的值赋给n->pprev
2、然后n->next = next
3、重新设置next->pprev的值，将其指向n->next
4、重新设置*(n->pprev)的值为n，即将n的前一个节点指向的next指针设置为n
*/
/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node*n,
structhlist_node *next)
{
n->pprev =next->pprev;
n->next =next;
next->pprev= &n->next;
*(n->pprev)= n;
}
/*
将节点next插在节点n之后
*/
static inline void hlist_add_after(struct hlist_node*n,
structhlist_node *next)
{
next->next= n->next;
n->next =next;
next->pprev= &n->next;
if(next->next)
next->next->pprev = &next->next;
}
Hash表头转移函数
/*
将一个hash表中的节点都移植到一个新的hash表头中
1、将旧hash表的first值赋给新hash表的hash值
2、若hash表的first指针不为空，则分别更新这两个hash表的first指针
*/
/*
* Move a listfrom one list head to another. Fixup the pprev
* reference ofthe first entry if it exists.
*/
static inline void hlist_move_list(struct hlist_head*old,
struct hlist_head *new)
{
new->first= old->first;
if(new->first)
new->first->pprev= &new->first;
old->first= NULL;
}
/*通过成员指针获得整个结构体的指针*/
#define hlist_entry(ptr, type, member)container_of(ptr,type,member)
遍历hash表相关的函数
/*遍历hash表的每一个节点，不能进行删除节点操作*/
#define hlist_for_each(pos, head) \
for (pos =(head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)
/*遍历hash表的每一个节点，可以进行删除节点操作*/
#define hlist_for_each_safe(pos, n, head) \
for (pos =(head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)
用链表外的结构体地址来进行遍历，而不用哈希链表的地址进行遍历
通过hash表的first节点进行遍历：
#define hlist_for_each_entry(tpos, pos, head, member) \
for (pos =(head)->first; \
pos && ({ prefetch(pos->next);1;}) && \
({ tpos =hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
#define hlist_for_each_entry_safe(tpos, pos, n, head,member) \
for (pos =(head)->first; \
pos && ({ n = pos->next; 1; })&& \
({ tpos =hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = n)
从当前hash节点开始遍历
#define hlist_for_each_entry_from(tpos, pos, member) \
for (; pos&& ({ prefetch(pos->next); 1;}) && \
({ tpos =hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
从当前hash节点的下一个节点开始遍历
#define hlist_for_each_entry_continue(tpos, pos,member) \
for (pos =(pos)->next; \
pos && ({ prefetch(pos->next);1;}) && \
({ tpos =hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
山不厌高，水不厌深。
