文章目录
  1. 1. 前沿
  2. 2. 普通链表
  3. 3. 哈希链表
  4. 4. 设计原理
  5. 5. 常用操作
    1. 5.1. (1) 初始化
    2. 5.2. (2) 插入
    3. 5.3. (3) 删除
    4. 5.4. (4) 遍历

前沿

先来直观的比较下普通链表和哈希链表:

普通链表

普通链表的表头和节点相同

1
2
3
struct list_head {  
struct list_head *next, *prev;
};

详情请参考内核数据结构之链表

哈希链表

哈希链表头

1
2
3
struct hlist_head {  
struct hlist_node *first;
};

哈希链表节点

1
2
3
struct hlist_node {  
struct hlist_node *next, **pprev;
};

设计原理

Linux链表设计者认为双指针表头双循环链表对于HASH表来说过于浪费,因而另行设计了一套用于HASH表的hlist数据结构,即单指针表头双循环链表。hlist表头仅有一个指向首节点的指针,而没有指向尾节点的指针,这样在海量的HASH表中存储的表头就能减少一半的空间消耗。

这里还需要注意:struct hlist_node **pprev,也就是说pprev是指向前一个节点(也可以是表头)中next指针的指针。

Q: 为什么不使用struct hlist_node *prev,即让prev指向前一个节点呢?
A: 因为这时候表头(hlist_head)和节点(hlist_node)的数据结构不同。如果使用struct hlist_node *prev,只适用于前一个为节点的情况,而不适用于前一个为表头的情况。如果每次操作都要考虑指针类型转换,会是一件麻烦的事情。所以,我们需要一种统一的操作,而不用考虑前一个元素是节点还是表头。
struct hlist_node **pprev,pprev指向前一个元素的next指针,不用管前一个元素是节点还是表头。当我们需要操作前一个元素(节点或表头),可以统一使用*(node->pprev)来访问和修改前一元素的next(或first)指针。

原理图如下:

常用操作

(1) 初始化

1
2
3
4
5
6
7
8
/*
* Double linked lists with a single pointer list head.
* Mostly useful for hash tables where the two pointer list head is too wasteful.
* You lose the ability to access the tail in O(1).
*/
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD (name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

(2) 插入

1
2
3
4
5
6
7
8
/* next must be != 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;
}

(3) 删除

1
2
3
4
5
6
7
8
static inline void __hlist_del(struct hlist_node *n)  
{
struct hlist_node *next = n->next;
struct hlist_node **prev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}

(4) 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *) 0)->MEMBER)  

/*
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*/
#define container_of(ptr, type, member) ({ \
const typeof(((type *) 0)->member) * __mptr = (ptr); \
(type *) ((char *) __mptr - offsetof(type, member)); })

#define hlist_entry(ptr, type, member) container_of(ptr, type, member)

#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos; pos = pos->next)

/**
* hlist_for_each_entry - iterate over list of given type
* @tpos: the type * to use as a loop cursor.
* @pos: the &struct hlist_node to use a loop cursor.
* @head: the head for your list.
* @member: the name of the hlist_node within the struct.
*/
#define hlist_for_each_entry(tpos, pos, head, member) \
for (pos = (head)->first; \
pos && ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)

参考资料:

  1. 哈希链表及其变种

  2. Linux内核链表

文章目录
  1. 1. 前沿
  2. 2. 普通链表
  3. 3. 哈希链表
  4. 4. 设计原理
  5. 5. 常用操作
    1. 5.1. (1) 初始化
    2. 5.2. (2) 插入
    3. 5.3. (3) 删除
    4. 5.4. (4) 遍历