免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 22900 | 回复: 22

在用户空间编程使用linux内核链表list,hlist宏定义和操作 [复制链接]

论坛徽章:
0
发表于 2007-05-27 12:59 |显示全部楼层
在用户空间编程使用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. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "list.h"

  4. struct ST {
  5.     unsigned char ch;
  6.     int         this_data;
  7.    
  8.     struct list_head  i_list;
  9.    
  10.     int         more_data;
  11.    
  12.     struct hlist_node i_hash;
  13.    
  14.     char        str_data[32];
  15.     //.......
  16.     int        end_data;
  17. } *st;

  18. struct list_head list1;  
  19. struct hlist_head hlist[1024];

  20. #define LISTSIZE 1024

  21. unsigned int gethash(int c)
  22. {
  23.     return (c & 0xff);
  24. }

  25. main()
  26. {
  27. int i;
  28. unsigned int hash;
  29. struct list_head *list;
  30. struct list_head *n, *p;
  31. struct ST *pst;
  32. struct hlist_node *hp;

  33.     INIT_LIST_HEAD(&list1);
  34.     for(hash = 0; hash < LISTSIZE; hash++)
  35.         INIT_HLIST_HEAD(&hlist[hash]);

  36.     for(i = 0; i < LISTSIZE; i++) {
  37.         struct ST *p = malloc(sizeof(*p));
  38.         if(!p) {
  39.             printf("malloc.\n");
  40.             break;
  41.         }
  42.        
  43.         p->ch = 'a' + i;

  44.                 //串入长串
  45.                 list_add(&p->i_list, &list1);
  46.        
  47.        
  48.                 //串入HASH短串
  49.         hash = gethash(p->ch);
  50.         printf("ALLOC %x %d %p %u\n", p->ch, i, p, hash);
  51.         hlist_add_head(&p->i_hash, &hlist[hash]);

  52.     }
  53.    
  54.             
  55.     //通过长铁丝遍历
  56.     i = 0;
  57.     list_for_each(list, &list1) {
  58.         struct ST *p = list_entry(list, struct ST, i_list);
  59.         printf("%p  value %d = %c\n", p, i, p->ch);
  60.         i++;
  61.     }
  62.     printf("total %d \n", i);

  63.     //----------------------
  64.     //通过hash串查找内容'C'的箱子
  65.     hash = gethash('c');
  66.     hlist_for_each(hp, &hlist[hash]) {
  67.         struct ST *p = hlist_entry(hp, struct ST, i_hash);
  68.         printf("hlist: %c\n", p->ch);

  69.     }

  70. }
复制代码


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



  1. #ifndef _LINUX_LIST_H
  2. #define _LINUX_LIST_H

  3. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

  4. #define container_of(ptr, type, member) ( { \
  5.         const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  6.         (type *)( (char *)__mptr - offsetof(type,member) ); } )

  7. static inline void prefetch(const void *x) {;}
  8. static inline void prefetchw(const void *x) {;}

  9. #define LIST_POISON1  ((void *) 0x00100100)
  10. #define LIST_POISON2  ((void *) 0x00200200)

  11. struct list_head {
  12.         struct list_head *next, *prev;
  13. };

  14. #define LIST_HEAD_INIT(name) { &(name), &(name) }

  15. #define LIST_HEAD(name) \
  16.         struct list_head name = LIST_HEAD_INIT(name)

  17. #define INIT_LIST_HEAD(ptr) do { \
  18.         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  19. } while (0)

  20. /*
  21. * Insert a new entry between two known consecutive entries.
  22. *
  23. * This is only for internal list manipulation where we know
  24. * the prev/next entries already!
  25. */
  26. static inline void __list_add(struct list_head *new,
  27.                               struct list_head *prev,
  28.                               struct list_head *next)
  29. {
  30.         next->prev = new;
  31.         new->next = next;
  32.         new->prev = prev;
  33.         prev->next = new;
  34. }

  35. /**
  36. * list_add - add a new entry
  37. * @new: new entry to be added
  38. * @head: list head to add it after
  39. *
  40. * Insert a new entry after the specified head.
  41. * This is good for implementing stacks.
  42. */
  43. static inline void list_add(struct list_head *new, struct list_head *head)
  44. {
  45.         __list_add(new, head, head->next);
  46. }

  47. /**
  48. * list_add_tail - add a new entry
  49. * @new: new entry to be added
  50. * @head: list head to add it before
  51. *
  52. * Insert a new entry before the specified head.
  53. * This is useful for implementing queues.
  54. */
  55. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  56. {
  57.         __list_add(new, head->prev, head);
  58. }

  59. static inline void __list_del(struct list_head * prev, struct list_head * next)
  60. {
  61.         next->prev = prev;
  62.         prev->next = next;
  63. }

  64. static inline void list_del(struct list_head *entry)
  65. {
  66.         __list_del(entry->prev, entry->next);
  67.         entry->next = LIST_POISON1;
  68.         entry->prev = LIST_POISON2;
  69. }

  70. static inline void list_del_init(struct list_head *entry)
  71. {
  72.         __list_del(entry->prev, entry->next);
  73.         INIT_LIST_HEAD(entry);
  74. }

  75. static inline void list_move(struct list_head *list, struct list_head *head)
  76. {
  77.         __list_del(list->prev, list->next);
  78.         list_add(list, head);
  79. }

  80. static inline void list_move_tail(struct list_head *list,
  81.                                   struct list_head *head)
  82. {
  83.         __list_del(list->prev, list->next);
  84.         list_add_tail(list, head);
  85. }

  86. static inline int list_empty(const struct list_head *head)
  87. {
  88.         return head->next == head;
  89. }

  90. static inline int list_empty_careful(const struct list_head *head)
  91. {
  92.         struct list_head *next = head->next;
  93.         return (next == head) && (next == head->prev);
  94. }

  95. static inline void __list_splice(struct list_head *list,
  96.                                  struct list_head *head)
  97. {
  98.         struct list_head *first = list->next;
  99.         struct list_head *last = list->prev;
  100.         struct list_head *at = head->next;

  101.         first->prev = head;
  102.         head->next = first;

  103.         last->next = at;
  104.         at->prev = last;
  105. }

  106. /**
  107. * list_splice - join two lists
  108. * @list: the new list to add.
  109. * @head: the place to add it in the first list.
  110. */
  111. static inline void list_splice(struct list_head *list, struct list_head *head)
  112. {
  113.         if (!list_empty(list))
  114.                 __list_splice(list, head);
  115. }

  116. /**
  117. * list_splice_init - join two lists and reinitialise the emptied list.
  118. * @list: the new list to add.
  119. * @head: the place to add it in the first list.
  120. *
  121. * The list at @list is reinitialised
  122. */
  123. static inline void list_splice_init(struct list_head *list,
  124.                                     struct list_head *head)
  125. {
  126.         if (!list_empty(list)) {
  127.                 __list_splice(list, head);
  128.                 INIT_LIST_HEAD(list);
  129.         }
  130. }

  131. #define list_entry(ptr, type, member) container_of(ptr, type, member)


  132. #define list_for_each(pos, head) \
  133.         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
  134.                 pos = pos->next)

  135. #define __list_for_each(pos, head) \
  136.         for (pos = (head)->next; pos != (head); pos = pos->next)

  137. #define list_for_each_prev(pos, head) \
  138.         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
  139.                 pos = pos->prev)

  140. #define list_for_each_safe(pos, n, head) \
  141.         for (pos = (head)->next, n = pos->next; pos != (head); \
  142.                 pos = n, n = pos->next)

  143. #define list_for_each_entry(pos, head, member)                                \
  144.         for (pos = list_entry((head)->next, typeof(*pos), member);        \
  145.              prefetch(pos->member.next), &pos->member != (head);         \
  146.              pos = list_entry(pos->member.next, typeof(*pos), member))

  147. #define list_for_each_entry_reverse(pos, head, member)                        \
  148.         for (pos = list_entry((head)->prev, typeof(*pos), member);        \
  149.              prefetch(pos->member.prev), &pos->member != (head);         \
  150.              pos = list_entry(pos->member.prev, typeof(*pos), member))

  151. #define list_prepare_entry(pos, head, member) \
  152.         ((pos) ? : list_entry(head, typeof(*pos), member))

  153. #define list_for_each_entry_continue(pos, head, member)                 \
  154.         for (pos = list_entry(pos->member.next, typeof(*pos), member);        \
  155.              prefetch(pos->member.next), &pos->member != (head);        \
  156.              pos = list_entry(pos->member.next, typeof(*pos), member))

  157. #define list_for_each_entry_safe(pos, n, head, member)                        \
  158.         for (pos = list_entry((head)->next, typeof(*pos), member),        \
  159.                 n = list_entry(pos->member.next, typeof(*pos), member);        \
  160.              &pos->member != (head);                                         \
  161.              pos = n, n = list_entry(n->member.next, typeof(*n), member))

  162. //HASH LIST
  163. struct hlist_head {
  164.         struct hlist_node *first;
  165. };

  166. struct hlist_node {
  167.         struct hlist_node *next, **pprev;
  168. };

  169. #define HLIST_HEAD_INIT { .first = NULL }
  170. #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
  171. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
  172. #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

  173. static inline int hlist_unhashed(const struct hlist_node *h)
  174. {
  175.         return !h->pprev;
  176. }

  177. static inline int hlist_empty(const struct hlist_head *h)
  178. {
  179.         return !h->first;
  180. }

  181. static inline void __hlist_del(struct hlist_node *n)
  182. {
  183.         struct hlist_node *next = n->next;
  184.         struct hlist_node **pprev = n->pprev;
  185.         *pprev = next;
  186.         if (next)
  187.                 next->pprev = pprev;
  188. }

  189. static inline void hlist_del(struct hlist_node *n)
  190. {
  191.         __hlist_del(n);
  192.         n->next = LIST_POISON1;
  193.         n->pprev = LIST_POISON2;
  194. }

  195. static inline void hlist_del_init(struct hlist_node *n)
  196. {
  197.         if (n->pprev)  {
  198.                 __hlist_del(n);
  199.                 INIT_HLIST_NODE(n);
  200.         }
  201. }

  202. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  203. {
  204.         struct hlist_node *first = h->first;
  205.         n->next = first;
  206.         if (first)
  207.                 first->pprev = &n->next;
  208.         h->first = n;
  209.         n->pprev = &h->first;
  210. }


  211. /* next must be != NULL */
  212. static inline void hlist_add_before(struct hlist_node *n,
  213.                                         struct hlist_node *next)
  214. {
  215.         n->pprev = next->pprev;
  216.         n->next = next;
  217.         next->pprev = &n->next;
  218.         *(n->pprev) = n;
  219. }

  220. static inline void hlist_add_after(struct hlist_node *n,
  221.                                         struct hlist_node *next)
  222. {
  223.         next->next = n->next;
  224.         n->next = next;
  225.         next->pprev = &n->next;

  226.         if(next->next)
  227.                 next->next->pprev  = &next->next;
  228. }

  229. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)

  230. #define hlist_for_each(pos, head) \
  231.         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
  232.              pos = pos->next)

  233. #define hlist_for_each_safe(pos, n, head) \
  234.         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
  235.              pos = n)

  236. #define hlist_for_each_entry(tpos, pos, head, member)                         \
  237.         for (pos = (head)->first;                                         \
  238.              pos && ({ prefetch(pos->next); 1;}) &&                         \
  239.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  240.              pos = pos->next)

  241. #define hlist_for_each_entry_continue(tpos, pos, member)                 \
  242.         for (pos = (pos)->next;                                                 \
  243.              pos && ({ prefetch(pos->next); 1;}) &&                         \
  244.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  245.              pos = pos->next)

  246. #define hlist_for_each_entry_from(tpos, pos, member)                         \
  247.         for (; pos && ({ prefetch(pos->next); 1;}) &&                         \
  248.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  249.              pos = pos->next)

  250. #define hlist_for_each_entry_safe(tpos, pos, n, head, member)                  \
  251.         for (pos = (head)->first;                                         \
  252.              pos && ({ n = pos->next; 1; }) &&                                  \
  253.                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  254.              pos = n)

  255. #endif

复制代码

论坛徽章:
0
发表于 2007-05-27 16:28 |显示全部楼层
加精...

论坛徽章:
0
发表于 2007-05-27 19:04 |显示全部楼层
版主自己加个精华好了
一直觉得这个东东和内核还是用户空间基本没有区别。

论坛徽章:
0
发表于 2007-05-27 20:17 |显示全部楼层
記得以前有一個全macro的list.h和rbtree.h,可惜現在找不到了。

论坛徽章:
0
发表于 2007-05-28 12:52 |显示全部楼层
如果用c++还是stl方便

论坛徽章:
0
发表于 2007-05-28 13:08 |显示全部楼层
STL的效率你实验过?

论坛徽章:
0
发表于 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 编辑 ]

论坛徽章:
0
发表于 2007-05-28 15:11 |显示全部楼层
原帖由 xhl 于 2007-5-28 14:49 发表


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


記起來了。

论坛徽章:
0
发表于 2007-05-28 15:32 |显示全部楼层
以前也尝试过这么写过,不过最后发现初始化和繁杂的参数实在令人烦恼,干脆就改用C++风格了
STL还是不错

论坛徽章:
0
发表于 2007-05-28 18:48 |显示全部楼层
原帖由 duanjigang 于 2007-5-28 15:32 发表
以前也尝试过这么写过,不过最后发现初始化和繁杂的参数实在令人烦恼,干脆就改用C++风格了
STL还是不错

c能用stl吗?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP