?

內核鏈表list.h文件剖析

一、內核鏈表的結構【雙向循環鏈表】

??? 內核鏈表的好主要體現為兩點，1是可擴展性，2是封裝。可以將內核鏈表復用到用戶態編程中，以后在用戶態下編程就不需要寫一些關于鏈表的代碼了，直接將內核中list.h中的代碼拷貝過來用。

struct list_head {struct list_head *next, *prev; }; // 包含了兩個指向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

1、offsetof【在已知某一個成員變量的名字和結構體類型的情況下，計算該成員相對于結構體的起始地址的偏移量】

#ifdef __compiler_offsetof #define offsetof(TYPE,MEMBER)__compiler_offsetof(TYPE,MEMBER) #else #ifndef offsetof #define offsetof(type, member) ((size_t) &((type*)0)->member) #endif

?

2、container_of【已知某一個成員變量的名字、指針和結構體類型的情況下，計算結構體的指針，也就是計算結構體的起始地址】

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

?

3、LIST_HEAD_INIT【初始化一個結點名字為name的雙向循環鏈表的頭結點】

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

?

4、LIST_HEAD【初始化一個結點名字為name的雙向循環鏈表的頭結點】

#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)

?

5、INIT_LIST_HEAD【初始化鏈表節點，將next和prev指針都指向其自身，我們就構造了一個空的雙循環鏈表。】

static __INLINE__ void INIT_LIST_HEAD(struct list_head *list) {list->next= list;list->prev= list; }

?

6、list_add【在頭結點后加一個新結點】

#ifndef CONFIG_DEBUG_LIST static __INLINE__ void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next) {next->prev= new;new->next =next;new->prev =prev;prev->next= new; } #else extern void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next); #endifstatic __INLINE__ void list_add(struct list_head *new,struct list_head *head) {__list_add(new, head, head->next); }

?

7、list_add_tail【添加結點new到鏈表尾】

static __INLINE__ void list_add_tail(struct list_head *new, struct list_head *head) {__list_add(new, head->prev, head); } // 在head->prev和head之間加入new，即在鏈表尾加入new結點

?

8、list_del【list_del將會將該節點與外界的“聯系”切斷，然后就可以使用free釋放了（如果是內核態就用kfree或vfree）】

#define LIST_POISON1 0 #define LIST_POISON2 0static __INLINE__ void __list_del(struct list_head *prev, struct list_head * next) {next->prev= prev;prev->next= next; }#ifndef CONFIG_DEBUG_LIST static __INLINE__ void list_del(struct list_head *entry) {__list_del(entry->prev, entry->next);entry->next= LIST_POISON1;entry->prev= LIST_POISON2; } #else extern void list_del(struct list_head *entry); #endif

?

9、list_replace【用結點new替換結點old】

static __INLINE__ void list_replace(struct list_head *old,struct list_head *new) {new->next =old->next;new->next->prev = new;new->prev =old->prev;new->prev->next = new; }

?

10、 list_replace_init【用結點new替換結點old，并初始化old】

static __INLINE__ void list_replace_init(struct list_head *old,struct list_head *new) {list_replace(old, new);INIT_LIST_HEAD(old); }

?

11、list_del_init【刪除結點entry，并初始化entry】

static __INLINE__ void list_del_init(struct list_head*entry) {__list_del(entry->prev, entry->next);INIT_LIST_HEAD(entry); }

?

12、list_move【先將list節點從原鏈表中刪除，然后將其添加到head鏈表的表頭】

static __INLINE__ void list_move(struct list_head *list, struct list_head *head) {__list_del(list->prev, list->next);list_add(list,head); }

?

13、list_move_tail【先將list節點從原鏈表中刪除，然后將其添加到head鏈表的表尾】

static __INLINE__ void list_move_tail(struct list_head *list,struct list_head *head) {__list_del(list->prev, list->next);list_add_tail(list, head); }

?

14、list_is_last【測試list節點是否為head鏈表的表尾節點。是返回1，否則返回0】

static __INLINE__ int list_is_last(const struct list_head *list,const struct list_head *head) {return list->next == head; }

?

15、list_empty【判斷head鏈表是否為空鏈表，是返回1，否則返回為0】

static __INLINE__ int list_empty(const struct list_head *head) {return head->next == head; }

16、list_empty_careful【判斷節點head的前驅和后驅是否都指向head。是返回1，否則返回0】

static __INLINE__ int list_empty_careful(const structlist_head *head) {struct list_head *next = head->next;return (next== head) && (next == head->prev); }

17、list_rotate_left【函數每次將頭結點后的一個結點放到head鏈表的末尾，直到head結點后沒有其他結點】

static __INLINE__ void list_rotate_left(struct list_head *head) {struct list_head *first;if(!list_empty(head)){first =head->next;list_move_tail(first, head);} }

?

18、list_is_singular【判斷head鏈表是否為單節點鏈表。是返回1，否為0】

static __INLINE__ int list_is_singular(const struct list_head *head) {return !list_empty(head) && (head->next == head->prev); }

?

19、__list_cut_position【這個函數是將head鏈表的頭結點至entry節點之間的節點連在list節點后面，即組成以list節點為頭結點的新鏈表】

static __INLINE__ void __list_cut_position(struct list_head *list,struct list_head *head, struct list_head *entry) {struct list_head *new_first = entry->next;list->next= head->next;list->next->prev = list;list->prev= entry;entry->next= list;head->next= new_first;new_first->prev = head; }<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">?</span>

20、list_cut_position【與__list_cut_position功能相似，不過要先判斷鏈表head是否為空鏈表，再判斷是否為了單鏈表而且節點不是entry的情況，如果head==entry，直接初始化list】

static __INLINE__ void list_cut_position(struct list_head *list,struct list_head *head, struct list_head *entry) {if(list_empty(head)){return;}if(list_is_singular(head) &&(head->next != entry && head != entry)){return;}if (entry ==head){INIT_LIST_HEAD(list);}else{__list_cut_position(list, head, entry);} }

?

21、__list_splice【將list鏈表的全部節點（頭節點list除外）插入在prev和next節點之間】

static __INLINE__ void __list_splice(const struct list_head *list,struct list_head *prev,struct list_head *next) {struct list_head *first = list->next;struct list_head *last = list->prev;first->prev= prev;prev->next= first;last->next= next;next->prev= last; }

?

22、list_splice_tail【在list是非空鏈表的情況下，將其插在head鏈表的尾部，即head節點的前面】

static __INLINE__ void list_splice_tail(struct list_head *list,struct list_head *head) {if(!list_empty(list)){__list_splice(list, head->prev, head);} }

?

23、list_splice_init【在list是非空鏈表的情況下，將其插在head鏈表的尾部，即head節點的前面。然后對list節點進行初始化，排除不安全因素】

static __INLINE__ void list_splice_init(struct list_head *list,struct list_head *head) {if(!list_empty(list)){__list_splice(list, head, head->next);INIT_LIST_HEAD(list);} }

?

24、list_splice_tail_init【在list是非空鏈表的情況下，將其插在head鏈表的尾部，即head節點的前面。然后對list節點進行初始化，排除不安全因素】

static __INLINE__ void list_splice_tail_init(struct list_head *list, struct list_head *head) {if(!list_empty(list)){__list_splice(list, head->prev, head);INIT_LIST_HEAD(list);} }

?

25、list_entry【獲取type類型結構體的起始指針】

#define list_entry(ptr, type, member) \container_of(ptr, type, member)

?

26、list_first_entry【已知type類型的結構體中member成員的指針后，求得它所在的鏈表的下一個指針所指的member所在的type類型的結構體的起始地址】

#define list_first_entry(ptr, type, member) \list_entry((ptr)->next, type, member)

?

27、list_for_each【從head節點開始（不包括head節點）遍歷它的每一個節點】

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

?

28、list_for_each_prev【它也是從head節點開始（不包括head節點）向前遍歷每一個節點！即從鏈表的尾部開始遍歷】

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

?

29、list_for_each_safe【從head節點開始（不包括head節點！）遍歷它的每一個節點！它用n先將下一個要遍歷的節點保存起來，防止刪除本節點后，無法找到下一個節點，而出現錯誤】

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

?

30、list_for_each_prev_safe【它也是從head節點開始（不包括head節點）向前遍歷每一個節點！即從鏈表的尾部開始遍歷】

#define list_for_each_prev_safe(pos, n, head) \for (pos =(head)->prev, n = pos->prev; \prefetch(pos->prev), pos != (head); \pos = n,n = pos->prev)

?

31、list_for_each_entry【已知指向某個結構體的指針pos，以及指向它中member成員的指針head，從下一個結構體開始向后遍歷這個結構體鏈】

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

?

32、list_for_each_entry_reverse【已知指向某個結構體的指針pos，以及指向它中member成員的指針head，從下一個結構體開始向前遍歷這個結構體鏈】

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

?

33、list_prepare_entry【判斷pos這個指針是否為空，為空的話給它賦值list_entry(head, typeof(*pos), member)這條語句求出來的結構體的地址】

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

?

34、list_for_each_entry_continue【已知指向某個結構體的指針pos，以及指向它中的member成員的head指針，從它的下一個結構體開始向后遍歷這個鏈表】

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

?

35、list_for_each_entry_continue_reverse【已知指向某個結構體的指針pos，以及指向它中的member成員的head指針，從它的前一個結構體開始向前遍歷這個鏈表】

#define list_for_each_entry_continue_reverse(pos,head, member) \for (pos =list_entry(pos->member.prev, typeof(*pos), member); \prefetch(pos->member.prev), &pos->member != (head); \pos =list_entry(pos->member.prev, typeof(*pos), member))

?

36、list_for_each_entry_from【從pos節點開始，向后遍歷鏈表】

#define list_for_each_entry_from(pos, head,member) \for (;prefetch(pos->member.next), &pos->member != (head); \pos =list_entry(pos->member.next, typeof(*pos), member))

?

37、list_for_each_entry_safe【先保存下一個要遍歷的節點！從head下一個節點向后遍歷鏈表】

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

?

38、list_for_each_entry_safe_continue【先保存下一個要遍歷的節點！從pos下一個節點向后遍歷鏈表】

#define list_for_each_entry_safe_continue(pos, n, head,member) \for (pos =list_entry(pos->member.next, typeof(*pos), member), \n =list_entry(pos->member.next, typeof(*pos), member); \&pos->member != (head); \pos = n,n = list_entry(n->member.next, typeof(*n), member))

?

39、list_for_each_entry_safe_from【先保存下一個要遍歷的節點！從pos節點向后遍歷鏈表】

#define list_for_each_entry_safe_from(pos, n, head,member) \for (n =list_entry(pos->member.next, typeof(*pos), member); \&pos->member != (head); \pos = n, n = list_entry(n->member.next,typeof(*n), member))

?

40、list_for_each_entry_safe_reverse【先保存下一個要遍歷的節點！從鏈表尾部向前遍歷鏈表】

#define list_for_each_entry_safe_reverse(pos, n, head,member) \for (pos =list_entry((head)->prev, typeof(*pos), member), \n =list_entry(pos->member.prev, typeof(*pos), member); \&pos->member != (head); \pos = n,n = list_entry(n->member.prev, typeof(*n), member))

?

41、list_safe_reset_next【獲取n結構體指針】

#define list_safe_reset_next(pos, n, member) \n =list_entry(pos->member.next, typeof(*pos), member)

?

// hash鏈表頭 struct hlist_head {structh list_node *first; };struct hlist_node {struct hlist_node *next, **pprev; };

1、INIT_HLIST_HEAD【初始化頭節點指針ptr】

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

?

2、INIT_HLIST_NODE【初始化hlist節點】

static __INLINE__ void INIT_HLIST_NODE(struct hlist_node *h) {h->next =NULL;h->pprev =NULL; }

?

3、hlist_unhashed【判斷h->pprev是否為空，是返回1，否返回0】

static __INLINE__ int hlist_unhashed(const struct hlist_node *h) {return !h->pprev; }

?

4、hlist_empty【判斷hlist是否為空，是返回1，否返回0】

static __INLINE__ int hlist_empty(const struct hlist_head *h) {return !h->first; }

?

5、__hlist_del【刪除結點n】

static __INLINE__ void __hlist_del(struct hlist_node*n) {struct hlist_node *next = n->next;struct hlist_node **pprev = n->pprev;*pprev = next;if (next){next->pprev = pprev;} }

?

6、hlist_del【刪除結點n，將結點next、pprev分別指向LIST_POISON1、LIST_POISON2。這樣設置是為了保證不在鏈表中的結點項不能被訪問】

static __INLINE__ void hlist_del(struct hlist_node *n) {__hlist_del(n);n->next =LIST_POISON1;n->pprev =LIST_POISON2; }

?

7、hlist_del_init【先判斷結點是否為空，不為空刪除，再初始化節點】

static __INLINE__ void hlist_del_init(struct hlist_node *n) {if(!hlist_unhashed(n)){__hlist_del(n);INIT_HLIST_NODE(n);} }

?

8、hlist_add_head【增加結點n到h表頭】

static __INLINE__ void hlist_add_head(struct hlist_node *n, struct hlist_head *h) {struct hlist_node *first = h->first;n->next =first;if (first){first->pprev = &n->next;}h->first =n;n->pprev =&h->first; }<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">?</span>

9、hlist_add_before【增加結點n到結點next之前】

/* next must be != NULL */ static __INLINE__ void hlist_add_before(struct hlist_node *n,struct hlist_node *next) {n->pprev =next->pprev;n->next = next;next->pprev= &n->next;*(n->pprev)= n; }

?

10、hlist_add_after【增加結點n到結點next之后】

static __INLINE__ void hlist_add_after(struct hlist_node *n,struct hlist_node *next) {next->next= n->next;n->next =next;next->pprev= &n->next;if(next->next){next->next->pprev =&next->next;} }

?

11、hlist_move_list【頭結點new接管頭結點old的所有節點，并初始化old】

static __INLINE__ void hlist_move_list(struct hlist_head *old,struct hlist_head *new) {new->first= old->first;if(new->first){new->first->pprev = &new->first;}old->first= NULL; }

?

12、hlist_entry【已知某一個成員變量的名字、指針和結構體類型的情況下，計算結構體的指針，也就是計算結構體的起始地址】

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

13、hlist_for_each【遍歷hlist鏈表】

#define hlist_for_each(pos, head) \for (pos =(head)->first; pos ; \pos =pos->next)

?

14、 hlist_for_each_safe【遍歷hlist鏈表，一般在刪除結點使用】

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

?

15、hlist_for_each_entry【遍歷找typeof(*tpos)的結構體類型入口地址】

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

?

16、hlist_for_each_entry_continue【從結點pos下一個遍歷找typeof(*tpos)的結構體類型入口地址】

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

?

17、hlist_for_each_entry_from【從節點pos開始遍歷找typeof(*tpos)的結構體類型入口地址】

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

?

18、hlist_for_each_entry_safe【從頭節點head開始遍歷找typeof(*tpos)的結構體類型入口地址】

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

總結

以上是生活随笔為你收集整理的内核链表list.h文件剖析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。