分析结构建立双向链表的一牛

作者：opera

代码:

; include/linux/list.h

struct list_head {

struct list_head *next, *prev;

};

list_head结构用于构造双向环形链表

LIST_HEAD(head) : 定义一个空表头

struct list_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结点和当前插入结点间的链接关系（包括前向指针和后向指针），后面两条语句在哈希数组项和当前插入结点之间建立链接关系。

3年前 用这种方法这里的链表通常pprev指针只在链表管理时（插入与删除）使用，而在查找时仅使用next指针，也就是说这种链表的查找通常是单向的（pprev通常不指向结点的起始位置，若进行前向查找必须有一个类似于list_head双向链表的计算结点起始位置的宏）。这使得这种链表只是在链表建立和链表删除时有双向链表的效率，而查找时仅是单向链表的效率。但是这种链表通常用在哈希表中，这样虽然查找是单向链表的效率，但是由于具有同一个哈希值的链较短，所以执行效率也非常好，而且兼有双向链表的插入删除效率。

查看本文来源