如何使用内核提供的双向循环列表

realtang

我从include/linux/list.h中提取出了关于双向循环链表的核心部分，并以此为基础加上一个例子展示一下这个非常有用的功能。
list功能的头文件：

2. /*********************************************************************************************************/
3. //Author:                  Tang Xu
4. //File:                  list_fun.h
5. //
6. /*********************************************************************************************************/
7. #ifndef LIST_FUN_H
8. #define LIST_FUN_H
10. #define LIST_HEAD_INIT(name) { &(name), &(name) }
12. #define LIST_HEAD(name) \
13.         struct list_head name = LIST_HEAD_INIT(name)
15. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
16. /**
17. * container_of - cast a member of a structure out to the containing structure
18. * @ptr:        the pointer to the member.
19. * @type:        the type of the container struct this is embedded in.
20. * @member:        the name of the member within the struct.
21. *
22. */
23. #define container_of(ptr, type, member) ({                        \
24.         const typeof( ((type *)0)->member ) *__mptr = (ptr);        \
25.         (type *)( (char *)__mptr - offsetof(type,member) );})
26. /**
27. * list_entry - get the struct for this entry
28. * @ptr:        the &struct list_head pointer.
29. * @type:        the type of the struct this is embedded in.
30. * @member:        the name of the list_struct within the struct.
31. */
32. #define list_entry(ptr, type, member) \
33.         container_of(ptr, type, member)
34. /**
35. * list_for_each        -        iterate over a list
36. * @pos:        the &struct list_head to use as a loop counter.
37. * @head:        the head for your list.
38. */       
39. #define list_for_each(pos, head) \
40.         for (pos = (head)->next; pos != (head); pos = pos->next)
42. #define list_for_each_prev(pos, head) \
43.         for (pos = (head)->prev; pos != (head); pos = pos->prev)
44.        
45. /**
46. * list_for_each_entry        -        iterate over list of given type
47. * @pos:        the type * to use as a loop counter.
48. * @head:        the head for your list.
49. * @member:        the name of the list_struct within the struct.
50. */
51. #define list_for_each_entry(pos, head, member)                                \
52.         for (pos = list_entry((head)->next, typeof(*pos), member);        \
53.              &pos->member != (head);         \
54.              pos = list_entry(pos->member.next, typeof(*pos), member))
56. #define list_for_each_entry_reverse(pos, head, member)                        \
57.         for (pos = list_entry((head)->prev, typeof(*pos), member);        \
58.              &pos->member != (head);         \
59.              pos = list_entry(pos->member.prev, typeof(*pos), member))       
60.                  
61. struct list_head {
62.         struct list_head *next, *prev;
63. };
64. #ifdef __cplusplus
65. extern "C" {
66. #endif
68. /**
69. *
70. */
71. extern void INIT_LIST_HEAD(struct list_head *list);
73. /**
74. *
75. */
76. extern void list_add(struct list_head *new, struct list_head *head);
78. /**
79. *
80. */
81. extern void list_add_tail(struct list_head *new, struct list_head *head);
83. /**
84. *
85. */
86. extern void list_del(struct list_head *entry);
88. /**
89. *
90. */
91. extern int list_empty(const struct list_head *head);
93. /**
94. *
95. */
96. extern void list_del_init(struct list_head *entry);
99. #ifdef __cplusplus
100. }
101. #endif
103. #endif

复制代码

下面是实现该功能的文件。

2. #include "list_fun.h"
3. #define LIST_POISON1  ((void *) 0x00100100)
4. #define LIST_POISON2  ((void *) 0x00200200)
6.        
7. void INIT_LIST_HEAD(struct list_head *list)
8. {
9.         list->next = list;
10.         list->prev = list;
11. }
13. void __list_add(struct list_head *new,
14.                               struct list_head *prev,
15.                               struct list_head *next)
16. {
17.         next->prev = new;
18.         new->next = next;
19.         new->prev = prev;
20.         prev->next = new;
21. }
23. void list_add(struct list_head *new, struct list_head *head)
24. {
25.         __list_add(new, head, head->next);
26. }
28. void list_add_tail(struct list_head *new, struct list_head *head)
29. {
30.         __list_add(new, head->prev, head);
31. }
33. void __list_del(struct list_head * prev, struct list_head * next)
34. {
35.         next->prev = prev;
36.         prev->next = next;
37. }
39. void list_del(struct list_head *entry)
40. {
41.         __list_del(entry->prev, entry->next);
42.         entry->next = LIST_POISON1;
43.         entry->prev = LIST_POISON2;
44. }
46. int list_empty(const struct list_head *head)
47. {
48.         return head->next == head;
49. }
51. void list_del_init(struct list_head *entry)
52. {
53.         __list_del(entry->prev, entry->next);
54.         INIT_LIST_HEAD(entry);
55. }

复制代码

再下面是如何使用的参考代码。

2. #include <stdio.h>
3. #include "list_fun.h"
5. typedef struct _test {
6.         struct list_head list;
7.         void * data;
8.         int           len;
9. } TESTLIST;
12. int main()
13. {
14.         int i;
15.         TESTLIST head;
16.         memset( &head, 0, sizeof( TESTLIST));
17.         INIT_LIST_HEAD( &head.list);
18.         //创建链表
19.         TESTLIST * p_testlist = NULL;
20.         for( i=0; i<100; i++) {
21.                 p_testlist = malloc( sizeof( TESTLIST));
22.                 if( NULL == p_testlist) {
23.                         perror("Memory shortage");
24.                         exit( -1);
25.                 }
26.                 p_testlist->data = NULL;
27.                 p_testlist->len = i;
28.                 list_add( &p_testlist->list, &head.list);
29.         }
30.         //遍历链表并打印
31.         p_testlist = NULL;
32.         list_for_each_entry( p_testlist, &head.list, list)
33.                 printf("%d\n", p_testlist->len);
34.         //删除链表
35.         p_testlist = NULL;
36.         list_for_each_entry( p_testlist, &head.list, list) {
37.                 list_del( &p_testlist->list);
38.              if( p_testlist->data) {
39.                    free( p_testlist->data);
40.               }
41.               free( p_testlist);
42.        }
43.         return 0;
45. }

复制代码

x11

运行结果是Segmentation fault

realtang

删除链表那里有些问题，不好意思。改成
       

2. //删除链表
3.         p_testlist = NULL;
4.         struct list_head * j;
5.         list_for_each( j, &head.list) {
6.                 struct list_head tmp;
7.                 tmp.next = j->next;
8.                 tmp.prev = j->prev;               
9.                 if( list_entry( j, TESTLIST, list)->data )
10.                         free( list_entry( j, TESTLIST, list)->data);
11.                 list_del( j);
12.                 free( list_entry( j, TESTLIST, list));
13.                 j = &tmp;
14.         }

复制代码

ipconfigme

为什么要加上这么一段？

3.                 struct list_head tmp;
4.                 tmp.next = j->next;
5.                 tmp.prev = j->prev;               
7.                 j = &tmp;

复制代码

asert

好东西,问一下内核里的哈希表数据结构在哪个文件有实现的呀?能提供一些使用的例子代码吗?