作者:opera
代码:
; include/Linux/list.h
strUCt list_head {
struct list_head *next, *prev;
};
list_head结构用于构造双向环形链表
LIST_HEAD(head) : 定义一个空表头
struct list_head head = {&head,&head};
INIT_LIST_HEAD(head) : 初始化一个已定义的表头;
head-next = head;
head-prev = head;
list_add(entry,head); 将entry添加到head之后,用于构造堆栈
head-next-prev = entry;
entry-next = head-next;
entry-prev = head;
head-next = entry;
list_add_tail(entry,head) : 将entry添加到head之前,用于构造队列
head-prev = entry;
entry-next = head;
entry-prev = head-prev;
head-prev-next = entry;
list_del(entry) : 删除entry
entry-next-prev = entry-prev;
entry-prev-next = entry-next;
list_del_init(entry) : 删除并复位entry
entry-next-prev = entry-prev;
entry-prev-next = entry-next;
entry-next = entry;
entry-prev = entry;
list_empty(head) : 测试环形链表是否为空
(head-next == head)
list_splice(list,head) : 将两个环形链表合成一个大表
list-prev-next = head-next;
list-next-prev = head;
head-next-prev = list-prev;
head-next = list-next;
list_entry(ptr,type,member) :
假如type结构中member的地址是ptr,则返回type结构的地址
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)-member)))
list_for_each(entry,head) : 遍历链表
for (entry = (head)-next; entry != (head); entry = entry-next)
========================================================
建立双向链表的一种常见方法 作者:西安交通大学 王灏
========================================================
在分析内核时经常碰到以“pprev”作为尾缀的二次指针和带有“next”尾缀的一次指针。而且在链表治理时使用这么一对指针。这里以网络bind哈希表建立为例解释(内核2.2.18)。
代码:
struct **skp = &udp_hash[sk-num & (UDP_HTABLE_SIZE -1)]
SOCKHASH_LOCK();
if((sk-next = *skp) != NULL)
(*skp)-pprev = &sk-next;
请注重这里pprev通常是指向前一个结点的next的地址
*skp = sk;
sk-pprev =skp;
SOCKHASH_UNLOCK();
第一句赋值语句将skp指向以sk-num为参数的哈希链的起始地址,而哈希数组的每一项都是指向sock结构的指针。所以* skp就是指向哈希链中的第一个sock结构。整个if语句完成在第一个sock结点和当前插入结点间的链接关系(包括前向指针和后向指针),后面两条语句在哈希数组项和当前插入结点之间建立链接关系。
用这种方法这里的链表通常pprev指针只在链表治理时(插入与删除)使用,而在查找时仅使用next指针,也就是说这种链表的查找通常是单向的(pprev通常不指向结点的起始位置,若进行前向查找必须有一个类似于list_head双向链表的计算结点起始位置的宏)。这使得这种链表只是在链表建立和链表删除时有双向链表的效率,而查找时仅是单向链表的效率。但是这种链表通常用在哈希表中,这样虽然查找是单向链表的效率,但是由于具有同一个哈希值的链较短,所以执行效率也非常好,而且兼有双向链表的插入删除效率。