QQ在线咨询
售前咨询热线
15821572819
售后咨询热线
15821572819

内核链表list.h文件剖析


内核链表list.h文件剖析

一、内核链表的结构【双向循环链表】

    内核链表的好主要体现为两点,1是可扩展性,2是封装。可以将内核链表复用到用户态编程中,以后在用户态下编程就不需要写一些关于链表的代码了,直接将内核中list.h中的代码拷贝过来用。


[cpp] view plain copy

  1. struct list_head  

  2. {  

  3.   struct list_head *next, *prev;  

  4. }; // 包含了两个指向list_head结构体的指针next,prev[后驱和前驱]  


 

二、内核链表常用接口

1、INIT_LIST_HEAD:创建链表

2、list_add:在prev和next之间插入结点

3、list_add_tail:在链表尾插入结点

4、list_del:删除结点

5、list_entry:取出结点

6、list_for_each:遍历链表

【推荐看使用sourceInsight查看代码】

 

三、深入分析list.h

1offsetof【在已知某一个成员变量的名字和结构体类型的情况下,计算该成员相对于结构体的起始地址的偏移量】


[cpp] view plain copy

  1. #ifdef __compiler_offsetof  

  2. #define offsetof(TYPE,MEMBER)__compiler_offsetof(TYPE,MEMBER)  

  3. #else  

  4. #ifndef offsetof  

  5. #define offsetof(type, member) ((size_t) &((type*)0)->member)  

  6. #endif  


 

2container_of【已知某一个成员变量的名字、指针和结构体类型的情况下,计算结构体的指针,也就是计算结构体的起始地址】


[cpp] view plain copy

  1. #define container_of(ptr, type, member) ({ \  

  2.   const typeof(((type *)0)->member ) *__mptr = (ptr); \  

  3.   (type *)((char *)__mptr - offsetof(type,member) );})  


 

3LIST_HEAD_INIT【初始化一个结点名字为name的双向循环链表的头结点】


[cpp] view plain copy

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


 

4LIST_HEAD【初始化一个结点名字为name的双向循环链表的头结点】


[cpp] view plain copy

  1. #define LIST_HEAD(name) \  

  2.   struct list_head name = LIST_HEAD_INIT(name)  


 

5INIT_LIST_HEAD【初始化链表节点,将next和prev指针都指向其自身,我们就构造了一个空的双循环链表。】


[cpp] view plain copy

  1. static __INLINE__ void INIT_LIST_HEAD(struct list_head *list)  

  2. {  

  3.   list->next= list;  

  4.   list->prev= list;  

  5. }  


 

6list_add【在头结点后加一个新结点】


[cpp] view plain copy

  1. #ifndef CONFIG_DEBUG_LIST  

  2. static __INLINE__ void __list_add(struct list_head *new,  

  3.                                   struct list_head *prev,  

  4.                                   struct list_head *next)  

  5. {  

  6.   next->prev= new;  

  7.   new->next =next;  

  8.   new->prev =prev;  

  9.   prev->next= new;  

  10. }  

  11. #else  

  12. extern void __list_add(struct list_head *new,  

  13.                        struct list_head *prev,  

  14.                        struct list_head *next);  

  15. #endif  

  16.    

  17. static __INLINE__ void list_add(struct list_head *new,struct list_head *head)  

  18. {  

  19.  __list_add(new, head, head->next);  

  20. }  


 

7list_add_tail【添加结点new到链表尾】


[cpp] view plain copy

  1. static __INLINE__ void list_add_tail(struct list_head *newstruct list_head *head)  

  2. {  

  3.  __list_add(new, head->prev, head);  

  4. // 在head->prev和head之间加入new,即在链表尾加入new结点  


 

8list_del【list_del将会将该节点与外界的“联系”切断,然后就可以使用free释放了(如果是内核态就用kfree或vfree)】


[cpp] view plain copy

  1. #define LIST_POISON1 0  

  2. #define LIST_POISON2 0  

  3.    

  4. static __INLINE__ void __list_del(struct list_head *prev, struct list_head * next)  

  5. {  

  6.   next->prev= prev;  

  7.   prev->next= next;  

  8. }  

  9.    

  10. #ifndef CONFIG_DEBUG_LIST  

  11. static __INLINE__ void list_del(struct list_head *entry)  

  12. {  

  13.  __list_del(entry->prev, entry->next);  

  14.   entry->next= LIST_POISON1;  

  15.   entry->prev= LIST_POISON2;  

  16. }  

  17. #else  

  18. extern void list_del(struct list_head *entry);  

  19. #endif  


 

9list_replace【用结点new替换结点old


[cpp] view plain copy

  1. static __INLINE__ void list_replace(struct list_head *old,  

  2.                                     struct list_head *new)  

  3. {  

  4.   new->next =old->next;  

  5.  new->next->prev = new;  

  6.   new->prev =old->prev;  

  7.  new->prev->next = new;  

  8. }  


 

10 list_replace_init【用结点new替换结点old,并初始化old


[cpp] view plain copy

  1. static __INLINE__ void list_replace_init(struct list_head *old,  

  2.     struct list_head *new)  

  3. {  

  4.  list_replace(old, new);  

  5.  INIT_LIST_HEAD(old);  

  6. }  


 

11list_del_init【删除结点entry,并初始化entry


[cpp] view plain copy

  1. static __INLINE__ void list_del_init(struct list_head*entry)  

  2. {  

  3.  __list_del(entry->prev, entry->next);  

  4.  INIT_LIST_HEAD(entry);  

  5. }  


 

12list_move【先将list节点从原链表中删除,然后将其添加到head链表的表头】


[cpp] view plain copy

  1. static __INLINE__ void list_move(struct list_head *list, struct list_head *head)  

  2. {  

  3.  __list_del(list->prev, list->next);  

  4.   list_add(list,head);  

  5. }  


 

13list_move_tail【先将list节点从原链表中删除,然后将其添加到head链表的表尾】


[cpp] view plain copy

  1. static __INLINE__ void list_move_tail(struct list_head *list,  

  2.                                       struct list_head *head)  

  3. {  

  4.  __list_del(list->prev, list->next);  

  5.  list_add_tail(list, head);  

  6. }  


 

14list_is_last【测试list节点是否为head链表的表尾节点。是返回1,否则返回0


[cpp] view plain copy

  1. static __INLINE__ int list_is_last(const struct list_head *list,  

  2.                                    const struct list_head *head)  

  3. {  

  4.   return list->next ==