Chinaunix

标题: 在用户空间编程使用linux内核链表list，hlist宏定义和操作 [打印本页]

---

作者: 思一克    时间: 2007-05-27 12:59
标题: 在用户空间编程使用linux内核链表list，hlist宏定义和操作
在用户空间编程使用linux内核链表list，hlist宏定义和操作.

linux内核中的list_head和hlist_head/hlist_node是将数据结构串起来成为链表的两个重要链表构造工具。利用他们和其对应的宏定义，可以非常容易地将数据构成链表，进行链表的各种操作，和数据查询。

在内核中，他们使用的十分广泛。这些链表操作宏定义具有通用性，和具体数据结构无关。

利用他们，编程者就不必要自己具体操作链表的指针，而集中精力关心数据本身。使用这些工具的程序效率是很高的。

因为他们是内核定义的数据结构，在内核编程使用起来十分简单。

struct list_head { struct list_head *prev, *next; } 尺寸为2个指针大小。32位系统上为8个字节。
struct hlist_node 也是包含2个指针占8个字节。
struct hlist_head 占4个字节.

用他们将多个相同的数据结构串起来，必须在数据结构中加上他们的定义。一个数据结构也可以用多个相同链表或不同链表同时串起，串到多个不同的串中。

如果不在内核而在用户空间编程，也可以利用这些链表。（事实上，内核其它的数据结构多数都可以在用户空间使用）。

要“移植到用户空间”， 必须查找定义链表数据和宏的包含文件，将该文件拷贝出来，做适当改动，去掉内核特定的定义开关。如果该文件中引用的其它内核包含文件的关键数据定义，最好去掉引用，而将定义拷贝过来。

下面我给出的例子，就是一个用不同list_head和hash list将用户数据struct ST同时串起来的例子。
i_list是普通list的串。
i_hash是hash list的串（实际是多个串，被HASH分散在数组中,HASH关键字即是数组下标）

你可以想象数据结构是一个个货场的相同型号的分散放置的集装箱，为了将他们串起来，必须在箱子上安装上有孔的铁环，然后用铁丝通过这些安装上铁环就可以将他们串起来。
数据结构中的定义struct list_head就相当于铁环，可以焊接到箱子的任何位置。头部中间尾部都可以。

本例子中，一个箱子上安装了2个环，一个是i_list, 将箱子用一个长铁丝全部穿起来的。

还安了一个环i_hash, 这个环的用途是将箱子分组串到不同的串中（每个串使用一个独立的铁丝，当然每根铁丝长度就短了）。不同串的各个铁丝的头部排列放到一个hlist_head的数组中。


为了查找一个箱子，可以顺着长铁丝找（遍历），一个一个比较，知道找到箱子。但这样慢。
还可以直接顺着某个短铁丝找，如果事先可以确定要找的箱子必定在该端铁丝串中－－这是可以做到的,hash的作用。

struct hlist_head仅仅用了一个指针，占4个字节，因为hash数组往往相当大，而每个串长度很短（hash的目的）。这样可以节省4个字节乘以数据大小的空间。

文件list.h是 include/linux/list.h文件的用户空间改编版本。
具体的定义的含义，我这里不再叙述，你可以自己查找。有许多内核数据结构分析的地方有解释。


建议用户用C编程时候，如涉及到链表使用，那么使用list_head! 可以极大节省你的工作量和调式时间。
linux内核中还有许多定义好通用的东西，都是非常精彩和高效的。许多都可移植到用户程序中使用。

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include "list.h"
   
5. 
   
6. struct ST {
   
7.     unsigned char ch;
   
8.     int         this_data;
   
9.    
   
10.     struct list_head  i_list;
    
11.    
    
12.     int         more_data;
    
13.    
    
14.     struct hlist_node i_hash;
    
15.    
    
16.     char        str_data[32];
    
17.     //.......
    
18.     int        end_data;
    
19. } *st;
    
20. 
    
21. struct list_head list1;  
    
22. struct hlist_head hlist[1024];
    
23. 
    
24. #define LISTSIZE 1024
    
25. 
    
26. unsigned int gethash(int c)
    
27. {
    
28.     return (c & 0xff);
    
29. }
    
30. 
    
31. main()
    
32. {
    
33. int i;
    
34. unsigned int hash;
    
35. struct list_head *list;
    
36. struct list_head *n, *p;
    
37. struct ST *pst;
    
38. struct hlist_node *hp;
    
39. 
    
40.     INIT_LIST_HEAD(&list1);
    
41.     for(hash = 0; hash < LISTSIZE; hash++)
    
42.         INIT_HLIST_HEAD(&hlist[hash]);
    
43. 
    
44.     for(i = 0; i < LISTSIZE; i++) {
    
45.         struct ST *p = malloc(sizeof(*p));
    
46.         if(!p) {
    
47.             printf("malloc.\n");
    
48.             break;
    
49.         }
    
50.        
    
51.         p->ch = 'a' + i;
    
52. 
    
53.                 //串入长串
    
54.                 list_add(&p->i_list, &list1);
    
55.        
    
56.        
    
57.                 //串入HASH短串
    
58.         hash = gethash(p->ch);
    
59.         printf("ALLOC %x %d %p %u\n", p->ch, i, p, hash);
    
60.         hlist_add_head(&p->i_hash, &hlist[hash]);
    
61. 
    
62.     }
    
63.    
    
64.             
    
65.     //通过长铁丝遍历
    
66.     i = 0;
    
67.     list_for_each(list, &list1) {
    
68.         struct ST *p = list_entry(list, struct ST, i_list);
    
69.         printf("%p  value %d = %c\n", p, i, p->ch);
    
70.         i++;
    
71.     }
    
72.     printf("total %d \n", i);
    
73. 
    
74.     //----------------------
    
75.     //通过hash串查找内容'C'的箱子
    
76.     hash = gethash('c');
    
77.     hlist_for_each(hp, &hlist[hash]) {
    
78.         struct ST *p = hlist_entry(hp, struct ST, i_hash);
    
79.         printf("hlist: %c\n", p->ch);
    
80. 
    
81.     }
    
82. 
    
83. }
    

复制代码

改编后的放在用户空间的头文件list.h

1. 
   
2. 
   
3. #ifndef _LINUX_LIST_H
   
4. #define _LINUX_LIST_H
   
5. 
   
6. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
   
7. 
   
8. #define container_of(ptr, type, member) ( { \
   
9.         const typeof( ((type *)0)->member ) *__mptr = (ptr); \
   
10.         (type *)( (char *)__mptr - offsetof(type,member) ); } )
    
11. 
    
12. static inline void prefetch(const void *x) {;}
    
13. static inline void prefetchw(const void *x) {;}
    
14. 
    
15. #define LIST_POISON1  ((void *) 0x00100100)
    
16. #define LIST_POISON2  ((void *) 0x00200200)
    
17. 
    
18. struct list_head {
    
19.         struct list_head *next, *prev;
    
20. };
    
21. 
    
22. #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
23. 
    
24. #define LIST_HEAD(name) \
    
25.         struct list_head name = LIST_HEAD_INIT(name)
    
26. 
    
27. #define INIT_LIST_HEAD(ptr) do { \
    
28.         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
    
29. } while (0)
    
30. 
    
31. /*
    
32. * Insert a new entry between two known consecutive entries.
    
33. *
    
34. * This is only for internal list manipulation where we know
    
35. * the prev/next entries already!
    
36. */
    
37. static inline void __list_add(struct list_head *new,
    
38.                               struct list_head *prev,
    
39.                               struct list_head *next)
    
40. {
    
41.         next->prev = new;
    
42.         new->next = next;
    
43.         new->prev = prev;
    
44.         prev->next = new;
    
45. }
    
46. 
    
47. /**
    
48. * list_add - add a new entry
    
49. * @new: new entry to be added
    
50. * @head: list head to add it after
    
51. *
    
52. * Insert a new entry after the specified head.
    
53. * This is good for implementing stacks.
    
54. */
    
55. static inline void list_add(struct list_head *new, struct list_head *head)
    
56. {
    
57.         __list_add(new, head, head->next);
    
58. }
    
59. 
    
60. /**
    
61. * list_add_tail - add a new entry
    
62. * @new: new entry to be added
    
63. * @head: list head to add it before
    
64. *
    
65. * Insert a new entry before the specified head.
    
66. * This is useful for implementing queues.
    
67. */
    
68. static inline void list_add_tail(struct list_head *new, struct list_head *head)
    
69. {
    
70.         __list_add(new, head->prev, head);
    
71. }
    
72. 
    
73. static inline void __list_del(struct list_head * prev, struct list_head * next)
    
74. {
    
75.         next->prev = prev;
    
76.         prev->next = next;
    
77. }
    
78. 
    
79. static inline void list_del(struct list_head *entry)
    
80. {
    
81.         __list_del(entry->prev, entry->next);
    
82.         entry->next = LIST_POISON1;
    
83.         entry->prev = LIST_POISON2;
    
84. }
    
85. 
    
86. static inline void list_del_init(struct list_head *entry)
    
87. {
    
88.         __list_del(entry->prev, entry->next);
    
89.         INIT_LIST_HEAD(entry);
    
90. }
    
91. 
    
92. static inline void list_move(struct list_head *list, struct list_head *head)
    
93. {
    
94.         __list_del(list->prev, list->next);
    
95.         list_add(list, head);
    
96. }
    
97. 
    
98. static inline void list_move_tail(struct list_head *list,
    
99.                                   struct list_head *head)
    
100. {
     
101.         __list_del(list->prev, list->next);
     
102.         list_add_tail(list, head);
     
103. }
     
104. 
     
105. static inline int list_empty(const struct list_head *head)
     
106. {
     
107.         return head->next == head;
     
108. }
     
109. 
     
110. static inline int list_empty_careful(const struct list_head *head)
     
111. {
     
112.         struct list_head *next = head->next;
     
113.         return (next == head) && (next == head->prev);
     
114. }
     
115. 
     
116. static inline void __list_splice(struct list_head *list,
     
117.                                  struct list_head *head)
     
118. {
     
119.         struct list_head *first = list->next;
     
120.         struct list_head *last = list->prev;
     
121.         struct list_head *at = head->next;
     
122. 
     
123.         first->prev = head;
     
124.         head->next = first;
     
125. 
     
126.         last->next = at;
     
127.         at->prev = last;
     
128. }
     
129. 
     
130. /**
     
131. * list_splice - join two lists
     
132. * @list: the new list to add.
     
133. * @head: the place to add it in the first list.
     
134. */
     
135. static inline void list_splice(struct list_head *list, struct list_head *head)
     
136. {
     
137.         if (!list_empty(list))
     
138.                 __list_splice(list, head);
     
139. }
     
140. 
     
141. /**
     
142. * list_splice_init - join two lists and reinitialise the emptied list.
     
143. * @list: the new list to add.
     
144. * @head: the place to add it in the first list.
     
145. *
     
146. * The list at @list is reinitialised
     
147. */
     
148. static inline void list_splice_init(struct list_head *list,
     
149.                                     struct list_head *head)
     
150. {
     
151.         if (!list_empty(list)) {
     
152.                 __list_splice(list, head);
     
153.                 INIT_LIST_HEAD(list);
     
154.         }
     
155. }
     
156. 
     
157. #define list_entry(ptr, type, member) container_of(ptr, type, member)
     
158. 
     
159. 
     
160. #define list_for_each(pos, head) \
     
161.         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
     
162.                 pos = pos->next)
     
163. 
     
164. #define __list_for_each(pos, head) \
     
165.         for (pos = (head)->next; pos != (head); pos = pos->next)
     
166. 
     
167. #define list_for_each_prev(pos, head) \
     
168.         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
     
169.                 pos = pos->prev)
     
170. 
     
171. #define list_for_each_safe(pos, n, head) \
     
172.         for (pos = (head)->next, n = pos->next; pos != (head); \
     
173.                 pos = n, n = pos->next)
     
174. 
     
175. #define list_for_each_entry(pos, head, member)                                \
     
176.         for (pos = list_entry((head)->next, typeof(*pos), member);        \
     
177.              prefetch(pos->member.next), &pos->member != (head);         \
     
178.              pos = list_entry(pos->member.next, typeof(*pos), member))
     
179. 
     
180. #define list_for_each_entry_reverse(pos, head, member)                        \
     
181.         for (pos = list_entry((head)->prev, typeof(*pos), member);        \
     
182.              prefetch(pos->member.prev), &pos->member != (head);         \
     
183.              pos = list_entry(pos->member.prev, typeof(*pos), member))
     
184. 
     
185. #define list_prepare_entry(pos, head, member) \
     
186.         ((pos) ? : list_entry(head, typeof(*pos), member))
     
187. 
     
188. #define list_for_each_entry_continue(pos, head, member)                 \
     
189.         for (pos = list_entry(pos->member.next, typeof(*pos), member);        \
     
190.              prefetch(pos->member.next), &pos->member != (head);        \
     
191.              pos = list_entry(pos->member.next, typeof(*pos), member))
     
192. 
     
193. #define list_for_each_entry_safe(pos, n, head, member)                        \
     
194.         for (pos = list_entry((head)->next, typeof(*pos), member),        \
     
195.                 n = list_entry(pos->member.next, typeof(*pos), member);        \
     
196.              &pos->member != (head);                                         \
     
197.              pos = n, n = list_entry(n->member.next, typeof(*n), member))
     
198. 
     
199. //HASH LIST
     
200. struct hlist_head {
     
201.         struct hlist_node *first;
     
202. };
     
203. 
     
204. struct hlist_node {
     
205.         struct hlist_node *next, **pprev;
     
206. };
     
207. 
     
208. #define HLIST_HEAD_INIT { .first = NULL }
     
209. #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
     
210. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
     
211. #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
     
212. 
     
213. static inline int hlist_unhashed(const struct hlist_node *h)
     
214. {
     
215.         return !h->pprev;
     
216. }
     
217. 
     
218. static inline int hlist_empty(const struct hlist_head *h)
     
219. {
     
220.         return !h->first;
     
221. }
     
222. 
     
223. static inline void __hlist_del(struct hlist_node *n)
     
224. {
     
225.         struct hlist_node *next = n->next;
     
226.         struct hlist_node **pprev = n->pprev;
     
227.         *pprev = next;
     
228.         if (next)
     
229.                 next->pprev = pprev;
     
230. }
     
231. 
     
232. static inline void hlist_del(struct hlist_node *n)
     
233. {
     
234.         __hlist_del(n);
     
235.         n->next = LIST_POISON1;
     
236.         n->pprev = LIST_POISON2;
     
237. }
     
238. 
     
239. static inline void hlist_del_init(struct hlist_node *n)
     
240. {
     
241.         if (n->pprev)  {
     
242.                 __hlist_del(n);
     
243.                 INIT_HLIST_NODE(n);
     
244.         }
     
245. }
     
246. 
     
247. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
     
248. {
     
249.         struct hlist_node *first = h->first;
     
250.         n->next = first;
     
251.         if (first)
     
252.                 first->pprev = &n->next;
     
253.         h->first = n;
     
254.         n->pprev = &h->first;
     
255. }
     
256. 
     
257. 
     
258. /* next must be != NULL */
     
259. static inline void hlist_add_before(struct hlist_node *n,
     
260.                                         struct hlist_node *next)
     
261. {
     
262.         n->pprev = next->pprev;
     
263.         n->next = next;
     
264.         next->pprev = &n->next;
     
265.         *(n->pprev) = n;
     
266. }
     
267. 
     
268. static inline void hlist_add_after(struct hlist_node *n,
     
269.                                         struct hlist_node *next)
     
270. {
     
271.         next->next = n->next;
     
272.         n->next = next;
     
273.         next->pprev = &n->next;
     
274. 
     
275.         if(next->next)
     
276.                 next->next->pprev  = &next->next;
     
277. }
     
278. 
     
279. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
     
280. 
     
281. #define hlist_for_each(pos, head) \
     
282.         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
     
283.              pos = pos->next)
     
284. 
     
285. #define hlist_for_each_safe(pos, n, head) \
     
286.         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
     
287.              pos = n)
     
288. 
     
289. #define hlist_for_each_entry(tpos, pos, head, member)                         \
     
290.         for (pos = (head)->first;                                         \
     
291.              pos && ({ prefetch(pos->next); 1;}) &&                         \
     
292.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
293.              pos = pos->next)
     
294. 
     
295. #define hlist_for_each_entry_continue(tpos, pos, member)                 \
     
296.         for (pos = (pos)->next;                                                 \
     
297.              pos && ({ prefetch(pos->next); 1;}) &&                         \
     
298.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
299.              pos = pos->next)
     
300. 
     
301. #define hlist_for_each_entry_from(tpos, pos, member)                         \
     
302.         for (; pos && ({ prefetch(pos->next); 1;}) &&                         \
     
303.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
304.              pos = pos->next)
     
305. 
     
306. #define hlist_for_each_entry_safe(tpos, pos, n, head, member)                  \
     
307.         for (pos = (head)->first;                                         \
     
308.              pos && ({ n = pos->next; 1; }) &&                                  \
     
309.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
310.              pos = n)
     
311. 
     
312. #endif
     
313. 
     

复制代码

---

作者: W.Z.T    时间: 2007-05-27 16:28
加精...

---

作者: flw2    时间: 2007-05-27 19:04
版主自己加个精华好了
一直觉得这个东东和内核还是用户空间基本没有区别。

---

作者: 福瑞哈哥    时间: 2007-05-27 20:17
記得以前有一個全macro的list.h和rbtree.h，可惜現在找不到了。

---

作者: acguy    时间: 2007-05-28 12:52
如果用c++还是stl方便

---

作者: 思一克    时间: 2007-05-28 13:08
STL的效率你实验过？

---

作者: xhl    时间: 2007-05-28 14:49

原帖由 福瑞哈哥 于 2007-5-27 20:17 发表
記得以前有一個全macro的list.h和rbtree.h，可惜現在找不到了。

我喜欢用BSD 的 queue.h  tree.h 等，
虽然全是macro写的，调试不太方便，但总比自己写省心。

[ 本帖最后由 xhl 于 2007-5-28 14:50 编辑 ]

---

作者: 福瑞哈哥    时间: 2007-05-28 15:11

原帖由 xhl 于 2007-5-28 14:49 发表


我喜欢用BSD 的 queue.h  tree.h 等，
虽然全是macro写的，调试不太方便，但总比自己写省心。

記起來了。

---

作者: duanjigang    时间: 2007-05-28 15:32
以前也尝试过这么写过，不过最后发现初始化和繁杂的参数实在令人烦恼，干脆就改用C++风格了
STL还是不错

---

作者: flw2    时间: 2007-05-28 18:48

原帖由 duanjigang 于 2007-5-28 15:32 发表
以前也尝试过这么写过，不过最后发现初始化和繁杂的参数实在令人烦恼，干脆就改用C++风格了
STL还是不错

c能用stl吗?

---

作者: DesignInside    时间: 2007-05-28 20:43
wow...good job

---

作者: duanjigang    时间: 2007-05-29 09:16

原帖由 flw2 于 2007-5-28 18:48 发表

c能用stl吗?

我当然是用C++咯。。。。

---

作者: 思一克    时间: 2007-05-29 09:34
KERNEL中主要是效率（速度），麻烦些不怕。一些系统软件也是如此。
C++/STL不容易作到。

---

作者: converse    时间: 2008-04-11 14:34
才看到思兄这份代码,我最近也要研究一下linux里面的这些宏,不过用g++编译的时候会报一些错误,虽然用C++的人使用这种宏的可能性不大,不过还是尽量做的完美一些好了,我做了一些修改:

1. 
   
2. #ifndef _LINUX_LIST_H
   
3. #define _LINUX_LIST_H
   
4. 
   
5. #ifdef __cplusplus
   
6. extern "C" {
   
7. #endif /* __cplusplus */
   
8. 
   
9. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
   
10. 
    
11. #define container_of(ptr, type, member) ( { \
    
12.         const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    
13.         (type *)( (char *)__mptr - offsetof(type,member) ); } )
    
14. 
    
15. static inline void prefetch(const void *x) {;}
    
16. static inline void prefetchw(const void *x) {;}
    
17. 
    
18. #define LIST_POISON1  ((void *) 0x00100100)
    
19. #define LIST_POISON2  ((void *) 0x00200200)
    
20. 
    
21. struct list_head {
    
22.     struct list_head *next, *prev;
    
23. };
    
24. 
    
25. #define LIST_HEAD_INIT(name) { &(name), &(name) }
    
26. 
    
27. #define LIST_HEAD(name) \
    
28.     struct list_head name = LIST_HEAD_INIT(name)
    
29. 
    
30. #define INIT_LIST_HEAD(ptr) do { \
    
31.     (ptr)->next = (ptr); (ptr)->prev = (ptr); \
    
32. } while (0)
    
33. 
    
34. /*
    
35. * * Insert a newobj entry between two known consecutive entries.
    
36. * *
    
37. * * This is only for internal list manipulation where we know
    
38. * * the prev/next entries already!
    
39. * */
    
40. static inline void __list_add(struct list_head *newobj,
    
41.         struct list_head *prev,
    
42.         struct list_head *next)
    
43. {
    
44.     next->prev = newobj;
    
45.     newobj->next = next;
    
46.     newobj->prev = prev;
    
47.     prev->next = newobj;
    
48. }
    
49. 
    
50. /**
    
51. * * list_add - add a newobj entry
    
52. * * @newobj: newobj entry to be added
    
53. * * @head: list head to add it after
    
54. * *
    
55. * * Insert a newobj entry after the specified head.
    
56. * * This is good for implementing stacks.
    
57. * */
    
58. static inline void list_add(struct list_head *newobj, struct list_head *head)
    
59. {
    
60.     __list_add(newobj, head, head->next);
    
61. }
    
62. 
    
63. /**
    
64. * * list_add_tail - add a newobj entry
    
65. * * @newobj: newobj entry to be added
    
66. * * @head: list head to add it before
    
67. * *
    
68. * * Insert a newobj entry before the specified head.
    
69. * * This is useful for implementing queues.
    
70. * */
    
71. static inline void list_add_tail(struct list_head *newobj, struct list_head *head)
    
72. {
    
73.     __list_add(newobj, head->prev, head);
    
74. }
    
75. 
    
76. static inline void __list_del(struct list_head * prev, struct list_head * next)
    
77. {
    
78.     next->prev = prev;
    
79.     prev->next = next;
    
80. }
    
81. 
    
82. static inline void list_del(struct list_head *entry)
    
83. {
    
84.     __list_del(entry->prev, entry->next);
    
85.     entry->next = (struct list_head*)LIST_POISON1;
    
86.     entry->prev = (struct list_head*)LIST_POISON2;
    
87. }
    
88. 
    
89. static inline void list_del_init(struct list_head *entry)
    
90. {
    
91.     __list_del(entry->prev, entry->next);
    
92.     INIT_LIST_HEAD(entry);
    
93. }
    
94. 
    
95. static inline void list_move(struct list_head *list, struct list_head *head)
    
96. {
    
97.     __list_del(list->prev, list->next);
    
98.     list_add(list, head);
    
99. }
    
100. 
     
101. static inline void list_move_tail(struct list_head *list,
     
102.         struct list_head *head)
     
103. {
     
104.     __list_del(list->prev, list->next);
     
105.     list_add_tail(list, head);
     
106. }
     
107. 
     
108. static inline int list_empty(const struct list_head *head)
     
109. {
     
110.     return head->next == head;
     
111. }
     
112. 
     
113. static inline int list_empty_careful(const struct list_head *head)
     
114. {
     
115.     struct list_head *next = head->next;
     
116.     return (next == head) && (next == head->prev);
     
117. }
     
118. 
     
119. static inline void __list_splice(struct list_head *list,
     
120.         struct list_head *head)
     
121. {
     
122.     struct list_head *first = list->next;
     
123.     struct list_head *last = list->prev;
     
124.     struct list_head *at = head->next;
     
125. 
     
126.     first->prev = head;
     
127.     head->next = first;
     
128. 
     
129.     last->next = at;
     
130.     at->prev = last;
     
131. }
     
132. 
     
133. /**
     
134. * * list_splice - join two lists
     
135. * * @list: the newobj list to add.
     
136. * * @head: the place to add it in the first list.
     
137. * */
     
138. static inline void list_splice(struct list_head *list, struct list_head *head)
     
139. {
     
140.     if (!list_empty(list))
     
141.         __list_splice(list, head);
     
142. }
     
143. 
     
144. /**
     
145. * * list_splice_init - join two lists and reinitialise the emptied list.
     
146. * * @list: the newobj list to add.
     
147. * * @head: the place to add it in the first list.
     
148. * *
     
149. * * The list at @list is reinitialised
     
150. * */
     
151. static inline void list_splice_init(struct list_head *list,
     
152.         struct list_head *head)
     
153. {
     
154.     if (!list_empty(list)) {
     
155.         __list_splice(list, head);
     
156.         INIT_LIST_HEAD(list);
     
157.     }
     
158. }
     
159. 
     
160. #define list_entry(ptr, type, member) container_of(ptr, type, member)
     
161. 
     
162. 
     
163. #define list_for_each(pos, head) \
     
164.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
     
165.             pos = pos->next)
     
166. 
     
167. #define __list_for_each(pos, head) \
     
168.     for (pos = (head)->next; pos != (head); pos = pos->next)
     
169. 
     
170. #define list_for_each_prev(pos, head) \
     
171.     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
     
172.             pos = pos->prev)
     
173. 
     
174. #define list_for_each_safe(pos, n, head) \
     
175.     for (pos = (head)->next, n = pos->next; pos != (head); \
     
176.             pos = n, n = pos->next)
     
177. 
     
178. #define list_for_each_entry(pos, head, member)                                \
     
179.     for (pos = list_entry((head)->next, typeof(*pos), member);        \
     
180.             prefetch(pos->member.next), &pos->member != (head);         \
     
181.             pos = list_entry(pos->member.next, typeof(*pos), member))
     
182. 
     
183. #define list_for_each_entry_reverse(pos, head, member)                        \
     
184.     for (pos = list_entry((head)->prev, typeof(*pos), member);        \
     
185.             prefetch(pos->member.prev), &pos->member != (head);         \
     
186.             pos = list_entry(pos->member.prev, typeof(*pos), member))
     
187. 
     
188. #define list_prepare_entry(pos, head, member) \
     
189.     ((pos) ? : list_entry(head, typeof(*pos), member))
     
190. 
     
191. #define list_for_each_entry_continue(pos, head, member)                 \
     
192.     for (pos = list_entry(pos->member.next, typeof(*pos), member);        \
     
193.             prefetch(pos->member.next), &pos->member != (head);        \
     
194.             pos = list_entry(pos->member.next, typeof(*pos), member))
     
195. 
     
196. #define list_for_each_entry_safe(pos, n, head, member)                        \
     
197.     for (pos = list_entry((head)->next, typeof(*pos), member),        \
     
198.             n = list_entry(pos->member.next, typeof(*pos), member);        \
     
199.             &pos->member != (head);                                         \
     
200.             pos = n, n = list_entry(n->member.next, typeof(*n), member))
     
201. 
     
202. //HASH LIST
     
203. struct hlist_head {
     
204.     struct hlist_node *first;
     
205. };
     
206. 
     
207. struct hlist_node {
     
208.     struct hlist_node *next, **pprev;
     
209. };
     
210. 
     
211. #define HLIST_HEAD_INIT { .first = NULL }
     
212. #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
     
213. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
     
214. #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
     
215. 
     
216. static inline int hlist_unhashed(const struct hlist_node *h)
     
217. {
     
218.     return !h->pprev;
     
219. }
     
220. 
     
221. static inline int hlist_empty(const struct hlist_head *h)
     
222. {
     
223.     return !h->first;
     
224. }
     
225. 
     
226. static inline void __hlist_del(struct hlist_node *n)
     
227. {
     
228.     struct hlist_node *next = n->next;
     
229.     struct hlist_node **pprev = n->pprev;
     
230.     *pprev = next;
     
231.     if (next)
     
232.         next->pprev = pprev;
     
233. }
     
234. 
     
235. static inline void hlist_del(struct hlist_node *n)
     
236. {
     
237.     __hlist_del(n);
     
238.     n->next = (struct hlist_node*)LIST_POISON1;
     
239.     n->pprev = (struct hlist_node**)LIST_POISON2;
     
240. }
     
241. 
     
242. static inline void hlist_del_init(struct hlist_node *n)
     
243. {
     
244.     if (n->pprev)  {
     
245.         __hlist_del(n);
     
246.         INIT_HLIST_NODE(n);
     
247.     }
     
248. }
     
249. 
     
250. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
     
251. {
     
252.     struct hlist_node *first = h->first;
     
253.     n->next = first;
     
254.     if (first)
     
255.         first->pprev = &n->next;
     
256.     h->first = n;
     
257.     n->pprev = &h->first;
     
258. }
     
259. 
     
260. 
     
261. /* next must be != NULL */
     
262. static inline void hlist_add_before(struct hlist_node *n,
     
263.         struct hlist_node *next)
     
264. {
     
265.     n->pprev = next->pprev;
     
266.     n->next = next;
     
267.     next->pprev = &n->next;
     
268.     *(n->pprev) = n;
     
269. }
     
270. 
     
271. static inline void hlist_add_after(struct hlist_node *n,
     
272.         struct hlist_node *next)
     
273. {
     
274.     next->next = n->next;
     
275.     n->next = next;
     
276.     next->pprev = &n->next;
     
277. 
     
278.     if(next->next)
     
279.         next->next->pprev  = &next->next;
     
280. }
     
281. 
     
282. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
     
283. 
     
284. #define hlist_for_each(pos, head) \
     
285.     for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
     
286.             pos = pos->next)
     
287. 
     
288. #define hlist_for_each_safe(pos, n, head) \
     
289.     for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
     
290.             pos = n)
     
291. 
     
292. #define hlist_for_each_entry(tpos, pos, head, member)                         \
     
293.     for (pos = (head)->first;                                         \
     
294.             pos && ({ prefetch(pos->next); 1;}) &&                         \
     
295.             ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
296.             pos = pos->next)
     
297. 
     
298. #define hlist_for_each_entry_continue(tpos, pos, member)                 \
     
299.     for (pos = (pos)->next;                                                 \
     
300.             pos && ({ prefetch(pos->next); 1;}) &&                         \
     
301.             ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
302.             pos = pos->next)
     
303. 
     
304. #define hlist_for_each_entry_from(tpos, pos, member)                         \
     
305.     for (; pos && ({ prefetch(pos->next); 1;}) &&                         \
     
306.             ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
307.             pos = pos->next)
     
308. 
     
309. #define hlist_for_each_entry_safe(tpos, pos, n, head, member)                  \
     
310.     for (pos = (head)->first;                                         \
     
311.             pos && ({ n = pos->next; 1; }) &&                                  \
     
312.             ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
     
313.             pos = n)
     
314. 
     
315. #ifdef __cplusplus
     
316. }
     
317. #endif /* __cplusplus */
     
318. 
     
319. #endif
     
320. 
     

复制代码

---

作者: 芙蓉    时间: 2008-04-11 14:47

---

作者: converse    时间: 2008-04-11 15:49
看了一下 这些宏的设计很巧妙 但是用了一些gcc的扩展 比如typeof  这样要移植到别的编译器可能有一些问题  折中的办法是使用者自己传入类型替代这个宏.

---

作者: converse    时间: 2008-04-11 15:53
比如container_of宏的改造:
从
#define container_of(ptr, type, member) ( { \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) ); } )
变为:
#define container_of2(ptr, ptrtype, type, member) ( { \
        const ptrtype *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,member) ); } )

---

作者: 思一克    时间: 2008-04-11 16:21
LINUX代码非常巧妙, 还有许多比如树操作, 也是类似的宏+代码, 也可以在应用程序中使用.

原帖由 converse 于 2008-4-11 15:53 发表
比如container_of宏的改造:
从
#define container_of(ptr, type, member) ( { \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,memb ...

---

作者: 芙蓉    时间: 2008-04-11 17:16

原帖由 converse 于 2008-4-11 15:53 发表
比如container_of宏的改造:
从
#define container_of(ptr, type, member) ( { \
        const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type *)( (char *)__mptr - offsetof(type,memb ...

为什么不变为：

1. 
   
2. #define container_of2(ptr, type, member) ( { \
   
3.         (type *)( (char *)(ptr) - offsetof(type,member) ); } )
   

复制代码

上面的代码，该用typeof定义变量的时候不用，比如list_for_each_entry里的head
不该用typeof的时候却用了，比如这个container_of

---

作者: cobranail    时间: 2008-05-10 18:38
这个list.h在非linux系统中使用不会有问题吧？

#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)

这两个定义的作用是什么呢？

---

作者: pilgrim_kevin    时间: 2008-09-17 09:56
学习。

---

作者: hxqhit    时间: 2012-06-17 23:01
  挺好滴，我现在应用层链表就是用了list

不过最近在学习glib里面的数据结构实现也挺好的～～

---

作者: hxqhit    时间: 2012-06-17 23:05
Memory chunks
  Doubly-linked lists
  Singly-linked lists
  Hash tables
  Strings (which can grow dynamically)
  String chunks (groups of strings)
  Arrays (which can grow in size as elements are added)
  Balanced binary trees
  N-ary trees
  Quarks (a two-way association of a string and a unique integer identifier)
  Keyed data lists (lists of data elements accessible by a string or integer id)
  Relations and tuples (tables of data which can be indexed on any number of fields)
  Caches
这些常规的数据结构都有相关的API，在应用层开发还是挺方便的

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2