上节我们对Linux内核链表的设计原理进行分析，理解了内核链表的设计的优点，并解决内核链表访问问题。
linux内核链表之HashList内核链表之HashList哈希链表（HashList/hlist）的设计初衷是为了方便快捷的查找，为了降低Hash表中键的冲突，一般设计会将Hash桶的数量设计的比较大。Linux链表设计者认为常规的双指针头结点的双向循环链表设计对于大数量桶的Hash表过于浪费，从而设计一套适合于Hash表的只有单指针的表头。该表头只有指向首节点的指针，没有指向尾节点指针，从而在海量Hash表中能够将表头存储空间减少一半。Hash链表这种单头指针设计缺失了对尾结点的时间复杂度的O(1)访问。同样也带来了对不同类..https://blog.csdn.net/xuedaon/article/details/121653851本节我们主要将Linux内核中链表的实现库进行分析解释。
// 内核链表数据结构
struct list_head{
struct list_head *next, *prev;
};
// 初始化内核链表头节点： 头结点的next，prev指针都指向自己的地址
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name)
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
图 1 初始化链表头节点
// 将new节点插入到prev之后，next之前
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
next->prev = new; // 如图2：(1)
new->next = next; // 如图2：(2)
new->prev = prev; // 如图2：(3)
prev->next = new; // 如图2：(4)
}
// 将new节点插入到头结点之后
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 将new节点插入到头结点之前
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
图 2 新节点插入
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
图 3 链表节点删除
#define list_entry(ptr, type, member) container_of(ptr, type, member) // 从头到尾遍历整个链表 #define list_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next) // 尾从到头遍历整个链表 #define list_for_each_prev(pos, head) for (pos = (head)->prev; pos != (head); pos = pos->prev) // 安全的从头到尾遍历整个链表：在遍历的时候可以安全的删除节点 #define list_for_each_safe(pos, n, head) for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next) // 安全的从尾到头遍历整个链表：在遍历的时候可以安全的删除节点 #define list_for_each_prev_safe(pos, n, head) for (pos = (head)->prev, n = pos->prev; pos != (head); pos = n, n = pos->prev) // 从头到尾遍历整个链表，并用type *pos指针获取节点的首地址 #define list_for_each_entry(pos, head, member) for (pos = list_entry((head)->next, typeof(*pos), member); &pos->member != (head); pos = list_entry(pos->member.next, typeof(*pos), member)) // 从尾到头遍历整个链表，并用type *pos指针获取节点的首地址 #define list_for_each_entry_reverse(pos, head, member) for (pos = list_entry((head)->prev, typeof(*pos), member); &pos->member != (head); pos = list_entry(pos->member.prev, typeof(*pos), member))
