Chinaunix首页 | 论坛 | 博客
  • 博客访问: 13448
  • 博文数量: 3
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 27
  • 用 户 组: 普通用户
  • 注册时间: 2014-05-06 14:22
个人简介

Hello World.

文章分类
文章存档

2015年(2)

2014年(1)

我的朋友

分类: LINUX

2014-08-28 20:03:43


点击(此处)折叠或打开

  1. linxu kernel 的双向链表详解:
  2. 目录
  3. 1.数据结构
  4. 2.定义头结点
  5. 3.初始化。
  6. 4.添加(add)结点
  7. 5.删除(del)结点
  8. 6.替换(replace)结点
  9. 7.移动(move)结点
  10. 8.双向链表的应用

  11.     1.数据结构:
  12. struct list_head{
  13.     struct list_head *next, *prev;
  14. }
  15.     2.定义头结点
  16. 2.1
  17. #define LIST_HEAD(name) \
  18.     struct list_head name = LIST_HEAD_INIT(name)
  19. 2.2
  20. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  21. 定义一个头结点,比如:
  22. LIST_HEAD(head) struct list_head head = {&head, &head);
  23. 等价于就是: head.next = &head;
  24.      head.prev = &head;

  25.     3.初始化
  26. static inline void INIT_LIST_HEAD(struct list_head *list)
  27. {
  28.     list->next = list;
  29.     list->prev = list;
  30. }
  31. 其实就是让prev/next指向自身.
  32.     4.添加结点
  33. 4.1添加到指定结点后(head->next指向new 作为链表头)
  34. static inline void list_add(struct list_head *new, struct list_head *head)
  35. {
  36.     __list_add(new, head, head->next);
  37. }
  38. 最后的结果就是 参数new,head:
  39.     new 添加到 head 和 head->next 中间。

  40. 4.2添加到指定结点前(head->prev指向new 作为链表尾)
  41. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  42. {
  43.     __list_add(new, head->prev, head);
  44. }
  45. 最后的结果就是 参数new,head:
  46.     new 添加到 head->prev 和 head 中间。

  47. static inline void __list_add(struct list_head *new,
  48.              struct list_head *prev,
  49.              struct list_head *next)
  50. {
  51.     next->prev = new;
  52.     new->next = next;
  53.     new->prev = prev;
  54.     prev->next = new;
  55. }
  56. 最后的结果就是 参数new prev next:
  57.        new 添加到prev 和 next 中间。
  58.     
  59.     5.删除结点
  60. 5.1
  61. static inline void list_del(struct list_head *entry)
  62. {
  63.     __list_del(entry->prev, entry->next);
  64.     entry->next = LIST_POISON1;
  65.     entry->prev = LIST_POISON2;
  66. }
  67. 5.2
  68. static inline void __list_del(struct list_head * prev, struct list_head * next)
  69. {
  70.     next->prev = prev;
  71.     prev->next = next;
  72. }
  73. 5.3
  74. /********** include/linux/list.h **********/
  75. /*
  76.  * These are non-NULL pointers that will result in page faults
  77.  * under normal circumstances, used to verify that nobody uses
  78.  * non-initialized list entries.
  79.  */
  80. #define LIST_POISON1 ((void *) 0x00100100)
  81. #define LIST_POISON2 ((void *) 0x00200200)
  82. 最后的结果就是:entry所指的结点从它所属的链表删除。
  83. 极端情况下该链表只有一个结点(假设头结点为head),那么链表情况:
  84.    head->next = entry;
  85.    head->prev = entry;
  86.    entry->next = head;
  87.    entry->prev = head;
  88. 调用删除结点(prev = head, next = head):
  89.   next->prev = prev; => head->prev = prev; => head->prev = head;
  90.   prev->next = next; => head->next = next; => head->next = head;
  91. 和之前刚初始化一个头结点的一样的状态。
  92. 5.4
  93. static inline void list_del_init(struct list_head *entry)
  94. {
  95.     __list_del(entry->prev, entry->next);
  96.     INIT_LIST_HEAD(entry);
  97. }
  98. 删除之后,并重新初始化entry结点。

  99.     6.替换结点
  100. 6.1
  101. static inline void list_replace(struct list_head *old,
  102.                 struct list_head *new)
  103. {
  104.     new->next = old->next;
  105.     new->next->prev = new;
  106.     new->prev = old->prev;
  107.     new->prev->next = new;
  108. }
  109. 最终的结果就是:new 结点替换了 old结点。
  110.             需要注意的是,old的prev和next是没有改变的。
  111. 6.2
  112. static inline void list_replace_init(struct list_head *old,
  113.                     struct list_head *new)
  114. {
  115.     list_replace(old, new);
  116.     INIT_LIST_HEAD(old);
  117. }
  118. 和6.1差别的是,并重新初始化old,这样old->next = old / old->prev = old。
  119.     
  120.     7.移动结点
  121. 7.1
  122. static inline void list_move(struct list_head *list, struct list_head *head)
  123. {
  124.     __list_del(list->prev, list->next);
  125.     list_add(list, head);
  126. }
  127. 7.2
  128. static inline void list_move_tail(struct list_head *list,
  129.                  struct list_head *head)
  130. {
  131.     __list_del(list->prev, list->next);
  132.     list_add_tail(list, head);
  133. }
  134. 最后的结果就是:
  135. 对于7.1和7.2的区别就是在调用list_add和list_add_tail的区别,这个函数,
  136. 前面分析过了。那么就是把参数list从原来位置删除,然后在添加到由参数head
  137. 前面(list_add_tail 链表尾)或后面(list_add 链表头)
  138.     
  139.     8.双向链表的应用
  140. 1-7大概就是双向链表的基本操作,初始化、添加、删除、移动、替换。
  141. 当然在/include/linux/list.h不仅仅包含这几个操作,还有判断是否为空、
  142. 是否只是一个结点、单链表切割为双链表、双链表合并为单链表等。
  143. 8.1
  144. #define list_entry(ptr, type, member) \
  145.     container_of(ptr, type, member)
  146. 向链表在整个kernel中是使用的非常广泛的,经常是内嵌到某一个结构体里面。
  147. container_of是非常常见的,那么这个宏的作用就是通过ptr(struct list *)
  148. 来得到包含该list的结构体地址。
  149. 比如:
  150. struct A
  151. {
  152.     ...
  153.     struct list entry;
  154.     ...
  155. };
  156. 假设有一个结构体A的实例:tmp。那么知道entry的地址就可以知道tmp所在地址。
  157. container_of(&entry, struct A, entry);
  158. (&entry) - [&(((struct A) *0)->entry)]
  159.            相当于entry在struct A的偏移量,那样减一下就可以得到tmp的地址。
  160. void example(const struct list *entry) //参数entry为tmp的list域的地址
  161. {
  162.     
  163.     struct *tmp = container_of(entry, struct A, list);
  164.     ...
  165. }
  166. 8.2
  167. /**
  168.  * list_first_entry - get the first element from a list
  169.  * @ptr:    the list head to take the element from.
  170.  * @type:    the type of the struct this is embedded in.
  171.  * @member:    the name of the list_struct within the struct.
  172.  *
  173.  * Note, that list is expected to be not empty.
  174.  */
  175. #define list_first_entry(ptr, type, member) \
  176.     list_entry((ptr)->next, type, member)
  177. 得到链表第一个结点内嵌到结构体的地址,由上面的参数英文解释也可知道。
  178. ptr就是list head链表头,ptr->next就是第一个entry的address.
  179. 然后调用list_entry,相当于调用container_of...
  180. 8.3
  181. /**
  182.  * list_for_each    -    iterate over a list
  183.  * @pos:    the &struct list_head to use as a loop cursor.
  184.  * @head:    the head for your list.
  185.  */
  186. #define list_for_each(pos, head) \
  187.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
  188.             pos = pos->next)

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

  191. 遍历链表结点,然后又由上可知,可由结点得到内嵌到结构体的地址,所有经常
  192. 这样使用这个宏:
  193. 假设结构体struct A, 链表头A_list;
  194. struct list_head *ptr;
  195. ...
  196. list_for_each(ptr, &A_list) {
  197.         struct A *tmp;
  198.         tmp = list_entry(ptr, struct hostap_bss_info, list);
  199.         tmp->xxx = ...;
  200.         tmp->yyy = ...;
  201.         ...
阅读(1219) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:Linux高端内存的详解。

给主人留下些什么吧!~~