[转贴]分析list_head结构＆建立双向链表的一种常见方法

雪中独行

原文出自：http://www.linuxforum.net

========================================================
分析list_head结构        作者：opera
========================================================

1. 
   
2. ; include/linux/list.h
   
3. 
   
4. struct list_head {
   
5.         struct list_head *next, *prev;
   
6. };
   
7. 
   
8. list_head结构用于构造双向环形链表
   
9. 
   
10. LIST_HEAD(head) : 定义一个空表头
    
11.         struct list_head head = {&head,&head};
    
12. 
    
13. INIT_LIST_HEAD(head) : 初始化一个已定义的表头;
    
14.         head->;next = head;
    
15.         head->;prev = head;
    
16. 
    
17. list_add(entry,head);        将entry添加到head之后,用于构造堆栈
    
18.         head->;next->;prev = entry;
    
19.         entry->;next = head->;next;
    
20.         entry->;prev = head;             
    
21.         head->;next = entry;
    
22. 
    
23. list_add_tail(entry,head) : 将entry添加到head之前,用于构造队列
    
24.         head->;prev = entry;
    
25.         entry->;next = head;               
    
26.         entry->;prev = head->;prev;
    
27.         head->;prev->;next = entry;
    
28. 
    
29. list_del(entry) : 删除entry
    
30.         entry->;next->;prev = entry->;prev;
    
31.         entry->;prev->;next = entry->;next;       
    
32. 
    
33. list_del_init(entry) : 删除并复位entry
    
34.         entry->;next->;prev = entry->;prev;
    
35.         entry->;prev->;next = entry->;next;       
    
36.         entry->;next = entry;
    
37.         entry->;prev = entry;
    
38.        
    
39. list_empty(head) : 测试环形链表是否为空
    
40.         (head->;next == head)
    
41. 
    
42. list_splice(list,head) : 将两个环形链表合成一个大表
    
43.         list->;prev->;next = head->;next;
    
44.         list->;next->;prev = head;
    
45.         head->;next->;prev = list->;prev;
    
46.         head->;next = list->;next;
    
47. 
    
48. list_entry(ptr,type,member) :
    
49. 如果type结构中member的地址是ptr,则返回type结构的地址
    
50.         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->;member)))
    
51. 
    
52. list_for_each(entry,head) : 遍历链表
    
53.         for (entry = (head)->;next; entry != (head); entry = entry->;next)
    
54.        
    

复制代码

========================================================
建立双向链表的一种常见方法        作者：西安交通大学 王灏  
========================================================

在分析内核时常常碰到以“pprev”作为尾缀的二次指针和带有“next”尾缀的一次指针。而且在链表管理时使用这么一对指针。这里以网络bind哈希表建立为例解释（内核2.2.18）。

1. 
   
2. struct **skp = &udp_hash[sk->;num & (UDP_HTABLE_SIZE -1)]
   
3. 
   
4. 
   
5. 
   
6. SOCKHASH_LOCK();
   
7. 
   
8. if((sk->;next = *skp) != NULL)
   
9. 
   
10.         (*skp)->;pprev = &sk->;next;
    
11. 
    
12. 请注意这里pprev通常是指向前一个结点的next的地址
    
13. 
    
14. *skp = sk;
    
15. 
    
16. sk->;pprev =skp;
    
17. 
    
18. 
    
19. 
    
20. SOCKHASH_UNLOCK();
    

复制代码

第一句赋值语句将skp指向以sk->;num为参数的哈希链的起始地址，而哈希数组的每一项都是指向sock结构的指针。所以* skp就是指向哈希链中的第一个sock结构。整个if语句完成在第一个sock结点和当前插入结点间的链接关系（包括前向指针和后向指针），后面两条语句在哈希数组项和当前插入结点之间建立链接关系。



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

dajun

la ji