??????? 上節(jié)博客中，我們講到了 Linux 中的宏定義 offsetof 與 container_of 宏。那么本節(jié)我們的課程目標(biāo)就是一直 Linux 內(nèi)核鏈表，使其適用于非 GNU 編譯器，分析 Linux 內(nèi)核中鏈表的基本實現(xiàn)。

????????我們首先來看看 Linux 內(nèi)核鏈表的位置及其依賴：

????????1、位置：{linux-2.6.39}\\include\linux\list.h

????????2、依賴：

????????????#include <linux/types.h>

????????????#include <linux/stddef.h>

????????????#include <linux/poison.h>

????????????#include <linux/prefetch.h>

????????在移植時需要注意的事項：

????????1、清楚文件間的依賴：剝離依賴文件中與鏈表實現(xiàn)相關(guān)的代碼

????????2、清楚平臺相關(guān)代碼（GNU C）：（{}），typeof，__builtin_prefetch，static inline

????????我們下來看看 list.h 的源碼是怎樣寫的

#ifndef?_LINUX_LIST_H #define?_LINUX_LIST_H//?#include?<linux/types.h> //?#include?<linux/stddef.h> //?#include?<linux/poison.h> //?#include?<linux/prefetch.h>#ifndef?offsetof #define?offsetof(TYPE,?MEMBER)?((size_t)?&((TYPE?*)0)->MEMBER) #endif#ifndef?container_of #define?container_of(ptr,?type,?member)?((type?*)((char?*)ptr?-?offsetof(type,member))) #endif#define?prefetch(x)?((void)x)#define?LIST_POISON1??(NULL) #define?LIST_POISON2??(NULL)struct?list_head?{struct?list_head?*next,?*prev; };struct?hlist_head?{struct?hlist_node?*first; };struct?hlist_node?{struct?hlist_node?*next,?**pprev; };/**?Simple?doubly?linked?list?implementation.**?Some?of?the?internal?functions?("__xxx")?are?useful?when*?manipulating?whole?lists?rather?than?single?entries,?as*?sometimes?we?already?know?the?next/prev?entries?and?we?can*?generate?better?code?by?using?them?directly?rather?than*?using?the?generic?single-entry?routines.*/#define?LIST_HEAD_INIT(name)?{?&(name),?&(name)?}#define?LIST_HEAD(name)?\struct?list_head?name?=?LIST_HEAD_INIT(name)static?void?INIT_LIST_HEAD(struct?list_head?*list) {list->next?=?list;list->prev?=?list; }/**?Insert?a?new?entry?between?two?known?consecutive?entries.**?This?is?only?for?internal?list?manipulation?where?we?know*?the?prev/next?entries?already!*/ #ifndef?CONFIG_DEBUG_LIST static?void?__list_add(struct?list_head?*node,struct?list_head?*prev,struct?list_head?*next) {next->prev?=?node;node->next?=?next;node->prev?=?prev;prev->next?=?node; } #else extern?void?__list_add(struct?list_head?*node,struct?list_head?*prev,struct?list_head?*next); #endif/***?list_add?-?add?a?new?entry*?@new:?new?entry?to?be?added*?@head:?list?head?to?add?it?after**?Insert?a?new?entry?after?the?specified?head.*?This?is?good?for?implementing?stacks.*/ static?void?list_add(struct?list_head?*node,?struct?list_head?*head) {__list_add(node,?head,?head->next); }/***?list_add_tail?-?add?a?new?entry*?@new:?new?entry?to?be?added*?@head:?list?head?to?add?it?before**?Insert?a?new?entry?before?the?specified?head.*?This?is?useful?for?implementing?queues.*/ static?void?list_add_tail(struct?list_head?*node,?struct?list_head?*head) {__list_add(node,?head->prev,?head); }/**?Delete?a?list?entry?by?making?the?prev/next?entries*?point?to?each?other.**?This?is?only?for?internal?list?manipulation?where?we?know*?the?prev/next?entries?already!*/ static?void?__list_del(struct?list_head?*?prev,?struct?list_head?*?next) {next->prev?=?prev;prev->next?=?next; }/***?list_del?-?deletes?entry?from?list.*?@entry:?the?element?to?delete?from?the?list.*?Note:?list_empty()?on?entry?does?not?return?true?after?this,?the?entry?is*?in?an?undefined?state.*/ #ifndef?CONFIG_DEBUG_LIST static?void?__list_del_entry(struct?list_head?*entry) {__list_del(entry->prev,?entry->next); }static?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_entry(struct?list_head?*entry); extern?void?list_del(struct?list_head?*entry); #endif/***?list_del_init?-?deletes?entry?from?list?and?reinitialize?it.*?@entry:?the?element?to?delete?from?the?list.*/ static?void?list_del_init(struct?list_head?*entry) {__list_del_entry(entry);INIT_LIST_HEAD(entry); }/***?list_move?-?delete?from?one?list?and?add?as?another's?head*?@list:?the?entry?to?move*?@head:?the?head?that?will?precede?our?entry*/ static?void?list_move(struct?list_head?*list,?struct?list_head?*head) {__list_del_entry(list);list_add(list,?head); }/***?list_move_tail?-?delete?from?one?list?and?add?as?another's?tail*?@list:?the?entry?to?move*?@head:?the?head?that?will?follow?our?entry*/ static?void?list_move_tail(struct?list_head?*list,struct?list_head?*head) {__list_del_entry(list);list_add_tail(list,?head); }/***?list_is_last?-?tests?whether?@list?is?the?last?entry?in?list?@head*?@list:?the?entry?to?test*?@head:?the?head?of?the?list*/ static?int?list_is_last(const?struct?list_head?*list,const?struct?list_head?*head) {return?list->next?==?head; }/***?list_empty?-?tests?whether?a?list?is?empty*?@head:?the?list?to?test.*/ static?int?list_empty(const?struct?list_head?*head) {return?head->next?==?head; }/***?list_empty_careful?-?tests?whether?a?list?is?empty?and?not?being?modified*?@head:?the?list?to?test**?Description:*?tests?whether?a?list?is?empty?_and_?checks?that?no?other?CPU?might?be*?in?the?process?of?modifying?either?member?(next?or?prev)**?NOTE:?using?list_empty_careful()?without?synchronization*?can?only?be?safe?if?the?only?activity?that?can?happen*?to?the?list?entry?is?list_del_init().?Eg.?it?cannot?be?used*?if?another?CPU?could?re-list_add()?it.*/ static?int?list_empty_careful(const?struct?list_head?*head) {struct?list_head?*next?=?head->next;return?(next?==?head)?&&?(next?==?head->prev); }/***?list_rotate_left?-?rotate?the?list?to?the?left*?@head:?the?head?of?the?list*/ static?void?list_rotate_left(struct?list_head?*head) {struct?list_head?*first;if?(!list_empty(head))?{first?=?head->next;list_move_tail(first,?head);} }/***?list_is_singular?-?tests?whether?a?list?has?just?one?entry.*?@head:?the?list?to?test.*/ static?int?list_is_singular(const?struct?list_head?*head) {return?!list_empty(head)?&&?(head->next?==?head->prev); }static?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; }/***?list_cut_position?-?cut?a?list?into?two*?@list:?a?new?list?to?add?all?removed?entries*?@head:?a?list?with?entries*?@entry:?an?entry?within?head,?could?be?the?head?itself*????and?if?so?we?won't?cut?the?list**?This?helper?moves?the?initial?part?of?@head,?up?to?and*?including?@entry,?from?@head?to?@list.?You?should*?pass?on?@entry?an?element?you?know?is?on?@head.?@list*?should?be?an?empty?list?or?a?list?you?do?not?care?about*?losing?its?data.**/ static?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); }static?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; }/***?list_splice?-?join?two?lists,?this?is?designed?for?stacks*?@list:?the?new?list?to?add.*?@head:?the?place?to?add?it?in?the?first?list.*/ static?void?list_splice(const?struct?list_head?*list,struct?list_head?*head) {if?(!list_empty(list))__list_splice(list,?head,?head->next); }/***?list_splice_tail?-?join?two?lists,?each?list?being?a?queue*?@list:?the?new?list?to?add.*?@head:?the?place?to?add?it?in?the?first?list.*/ static?void?list_splice_tail(struct?list_head?*list,struct?list_head?*head) {if?(!list_empty(list))__list_splice(list,?head->prev,?head); }/***?list_splice_init?-?join?two?lists?and?reinitialise?the?emptied?list.*?@list:?the?new?list?to?add.*?@head:?the?place?to?add?it?in?the?first?list.**?The?list?at?@list?is?reinitialised*/ static?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);} }/***?list_splice_tail_init?-?join?two?lists?and?reinitialise?the?emptied?list*?@list:?the?new?list?to?add.*?@head:?the?place?to?add?it?in?the?first?list.**?Each?of?the?lists?is?a?queue.*?The?list?at?@list?is?reinitialised*/ static?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);} }/***?list_entry?-?get?the?struct?for?this?entry*?@ptr:????the?&struct?list_head?pointer.*?@type:????the?type?of?the?struct?this?is?embedded?in.*?@member:????the?name?of?the?list_struct?within?the?struct.*/ #define?list_entry(ptr,?type,?member)?\container_of(ptr,?type,?member)/***?list_first_entry?-?get?the?first?element?from?a?list*?@ptr:????the?list?head?to?take?the?element?from.*?@type:????the?type?of?the?struct?this?is?embedded?in.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Note,?that?list?is?expected?to?be?not?empty.*/ #define?list_first_entry(ptr,?type,?member)?\list_entry((ptr)->next,?type,?member)/***?list_for_each????-????iterate?over?a?list*?@pos:????the?&struct?list_head?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*/ #define?list_for_each(pos,?head)?\for?(pos?=?(head)->next;?prefetch(pos->next),?pos?!=?(head);?\pos?=?pos->next)/***?__list_for_each????-????iterate?over?a?list*?@pos:????the?&struct?list_head?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.**?This?variant?differs?from?list_for_each()?in?that?it's?the*?simplest?possible?list?iteration?code,?no?prefetching?is?done.*?Use?this?for?code?that?knows?the?list?to?be?very?short?(empty*?or?1?entry)?most?of?the?time.*/ #define?__list_for_each(pos,?head)?\for?(pos?=?(head)->next;?pos?!=?(head);?pos?=?pos->next)/***?list_for_each_prev????-????iterate?over?a?list?backwards*?@pos:????the?&struct?list_head?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*/ #define?list_for_each_prev(pos,?head)?\for?(pos?=?(head)->prev;?prefetch(pos->prev),?pos?!=?(head);?\pos?=?pos->prev)/***?list_for_each_safe?-?iterate?over?a?list?safe?against?removal?of?list?entry*?@pos:????the?&struct?list_head?to?use?as?a?loop?cursor.*?@n:????????another?&struct?list_head?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*/ #define?list_for_each_safe(pos,?n,?head)?\for?(pos?=?(head)->next,?n?=?pos->next;?pos?!=?(head);?\pos?=?n,?n?=?pos->next)/***?list_for_each_prev_safe?-?iterate?over?a?list?backwards?safe?against?removal?of?list?entry*?@pos:????the?&struct?list_head?to?use?as?a?loop?cursor.*?@n:????????another?&struct?list_head?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*/ #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)/***?list_for_each_entry????-????iterate?over?list?of?given?type*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.*/ #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))/***?list_for_each_entry_reverse?-?iterate?backwards?over?list?of?given?type.*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.*/ #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))/***?list_prepare_entry?-?prepare?a?pos?entry?for?use?in?list_for_each_entry_continue()*?@pos:????the?type?*?to?use?as?a?start?point*?@head:????the?head?of?the?list*?@member:????the?name?of?the?list_struct?within?the?struct.**?Prepares?a?pos?entry?for?use?as?a?start?point?in?list_for_each_entry_continue().*/ #define?list_prepare_entry(pos,?head,?member)?\((pos)???:?list_entry(head,?typeof(*pos),?member))/***?list_for_each_entry_continue?-?continue?iteration?over?list?of?given?type*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Continue?to?iterate?over?list?of?given?type,?continuing?after*?the?current?position.*/ #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))/***?list_for_each_entry_continue_reverse?-?iterate?backwards?from?the?given?point*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Start?to?iterate?over?list?of?given?type?backwards,?continuing?after*?the?current?position.*/ #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))/***?list_for_each_entry_from?-?iterate?over?list?of?given?type?from?the?current?point*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Iterate?over?list?of?given?type,?continuing?from?current?position.*/ #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))/***?list_for_each_entry_safe?-?iterate?over?list?of?given?type?safe?against?removal?of?list?entry*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@n:????????another?type?*?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.*/ #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))/***?list_for_each_entry_safe_continue?-?continue?list?iteration?safe?against?removal*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@n:????????another?type?*?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Iterate?over?list?of?given?type,?continuing?after?current?point,*?safe?against?removal?of?list?entry.*/ #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))/***?list_for_each_entry_safe_from?-?iterate?over?list?from?current?point?safe?against?removal*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@n:????????another?type?*?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Iterate?over?list?of?given?type?from?current?point,?safe?against*?removal?of?list?entry.*/ #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))/***?list_for_each_entry_safe_reverse?-?iterate?backwards?over?list?safe?against?removal*?@pos:????the?type?*?to?use?as?a?loop?cursor.*?@n:????????another?type?*?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?list_struct?within?the?struct.**?Iterate?backwards?over?list?of?given?type,?safe?against?removal*?of?list?entry.*/ #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))/***?list_safe_reset_next?-?reset?a?stale?list_for_each_entry_safe?loop*?@pos:????the?loop?cursor?used?in?the?list_for_each_entry_safe?loop*?@n:????????temporary?storage?used?in?list_for_each_entry_safe*?@member:????the?name?of?the?list_struct?within?the?struct.**?list_safe_reset_next?is?not?safe?to?use?in?general?if?the?list?may?be*?modified?concurrently?(eg.?the?lock?is?dropped?in?the?loop?body).?An*?exception?to?this?is?if?the?cursor?element?(pos)?is?pinned?in?the?list,*?and?list_safe_reset_next?is?called?after?re-taking?the?lock?and?before*?completing?the?current?iteration?of?the?loop?body.*/ #define?list_safe_reset_next(pos,?n,?member)????????????????\n?=?list_entry(pos->member.next,?typeof(*pos),?member)/**?Double?linked?lists?with?a?single?pointer?list?head.*?Mostly?useful?for?hash?tables?where?the?two?pointer?list?head?is*?too?wasteful.*?You?lose?the?ability?to?access?the?tail?in?O(1).*/#define?HLIST_HEAD_INIT?{?.first?=?NULL?} #define?HLIST_HEAD(name)?struct?hlist_head?name?=?{??.first?=?NULL?} #define?INIT_HLIST_HEAD(ptr)?((ptr)->first?=?NULL) static?void?INIT_HLIST_NODE(struct?hlist_node?*h) {h->next?=?NULL;h->pprev?=?NULL; }static?int?hlist_unhashed(const?struct?hlist_node?*h) {return?!h->pprev; }static?int?hlist_empty(const?struct?hlist_head?*h) {return?!h->first; }static?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; }static?void?hlist_del(struct?hlist_node?*n) {__hlist_del(n);n->next?=?LIST_POISON1;n->pprev?=?LIST_POISON2; }static?void?hlist_del_init(struct?hlist_node?*n) {if?(!hlist_unhashed(n))?{__hlist_del(n);INIT_HLIST_NODE(n);} }static?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; }/*?next?must?be?!=?NULL?*/ static?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; }static?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; }/*?after?that?we'll?appear?to?be?on?some?hlist?and?hlist_del?will?work?*/ static?void?hlist_add_fake(struct?hlist_node?*n) {n->pprev?=?&n->next; }/**?Move?a?list?from?one?list?head?to?another.?Fixup?the?pprev*?reference?of?the?first?entry?if?it?exists.*/ static?void?hlist_move_list(struct?hlist_head?*old,struct?hlist_head?*node) {node->first?=?old->first;if?(node->first)node->first->pprev?=?&node->first;old->first?=?NULL; }#define?hlist_entry(ptr,?type,?member)?container_of(ptr,type,member)#define?hlist_for_each(pos,?head)?\for?(pos?=?(head)->first;?pos?&&?({?prefetch(pos->next);?1;?});?\pos?=?pos->next)#define?hlist_for_each_safe(pos,?n,?head)?\for?(pos?=?(head)->first;?pos?&&?({?n?=?pos->next;?1;?});?\pos?=?n)/***?hlist_for_each_entry????-?iterate?over?list?of?given?type*?@tpos:????the?type?*?to?use?as?a?loop?cursor.*?@pos:????the?&struct?hlist_node?to?use?as?a?loop?cursor.*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?hlist_node?within?the?struct.*/ #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)/***?hlist_for_each_entry_continue?-?iterate?over?a?hlist?continuing?after?current?point*?@tpos:????the?type?*?to?use?as?a?loop?cursor.*?@pos:????the?&struct?hlist_node?to?use?as?a?loop?cursor.*?@member:????the?name?of?the?hlist_node?within?the?struct.*/ #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)/***?hlist_for_each_entry_from?-?iterate?over?a?hlist?continuing?from?current?point*?@tpos:????the?type?*?to?use?as?a?loop?cursor.*?@pos:????the?&struct?hlist_node?to?use?as?a?loop?cursor.*?@member:????the?name?of?the?hlist_node?within?the?struct.*/ #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)/***?hlist_for_each_entry_safe?-?iterate?over?list?of?given?type?safe?against?removal?of?list?entry*?@tpos:????the?type?*?to?use?as?a?loop?cursor.*?@pos:????the?&struct?hlist_node?to?use?as?a?loop?cursor.*?@n:????????another?&struct?hlist_node?to?use?as?temporary?storage*?@head:????the?head?for?your?list.*?@member:????the?name?of?the?hlist_node?within?the?struct.*/ #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)#endif

????????我們來看看 Linux 內(nèi)核鏈表的實現(xiàn)：

????????1、帶頭結(jié)點的雙向循環(huán)鏈表，且頭結(jié)點為表中成員；

????????2、頭結(jié)點的 next 指針指向首結(jié)點；

????????3、頭結(jié)點的 prev 指針指向尾結(jié)點。

????????關(guān)系如下圖所示

????????下來我們來看看 Linux 內(nèi)核鏈表的結(jié)點定義，如下

????????那么問題來了，數(shù)據(jù)放在那里呢？所以說，下來我們要使用 struct list_head 自定義鏈表結(jié)點。如下

????????下來我們來加下自定義的鏈表結(jié)點

/***?list_replace?-?replace?old?entry?by?new?one*?@old?:?the?element?to?be?replaced*?@new?:?the?new?element?to?insert**?If?@old?was?empty,?it?will?be?overwritten.*/ static?void?list_replace(struct?list_head?*old,struct?list_head?*node) {node->next?=?old->next;node->next->prev?=?node;node->prev?=?old->prev;node->prev->next?=?node; }static?void?list_replace_init(struct?list_head?*old,struct?list_head?*node) {list_replace(old,?node);INIT_LIST_HEAD(old); }

????????下來我們來看看 Linux 內(nèi)核鏈表的插入、刪除、遍歷等操作。

????????A、插入操作：a> 在鏈表頭部插入：list_add(new,head)、b>? 在鏈表尾部插入：list_add_tail(new,head)；如下

????????B、刪除操作：如下

????????C、遍歷操作：a> 正向遍歷：list_for_each(pos,head)、b> 逆向遍歷：list_for_each_prev(pos,head)；如下

????????下來我們來測試下代碼，測試代碼如下

#include?<stdio.h> #include?<malloc.h> #include?"LinuxList.h"void?list_demo_1() {struct?Node{struct?list_head?head;int?value;};struct?Node?l?=?{0};struct?list_head*?list?=?(struct?list_head*)&l;struct?list_head*?slider?=?NULL;int?i?=?0;INIT_LIST_HEAD(list);printf("Insert?begin?...\n");for(i=0;?i<5;?i++){struct?Node*?n?=?(struct?Node*)malloc(sizeof(struct?Node));n->value?=?i;list_add_tail((struct?list_head*)n,?list);}list_for_each(slider,?list){printf("%d\n",?((struct?Node*)slider)->value);}printf("Insert?end?...\n");printf("Delete?begin?...\n");list_for_each(slider,?list){if(?((struct?Node*)slider)->value?==?3?){list_del(slider);free(slider);break;}}list_for_each(slider,?list){printf("%d\n",?((struct?Node*)slider)->value);}printf("Delete?end?...\n"); }void?list_demo_2() {struct?Node{int?value;struct?list_head?head;};struct?Node?l?=?{0};struct?list_head*?list?=?&l.head;struct?list_head*?slider?=?NULL;int?i?=?0;INIT_LIST_HEAD(list);printf("Insert?begin?...\n");for(i=0;?i<5;?i++){struct?Node*?n?=?(struct?Node*)malloc(sizeof(struct?Node));n->value?=?i;list_add(&n->head,?list);}list_for_each(slider,?list){printf("%d\n",?list_entry(slider,?struct?Node,?head)->value);}printf("Insert?end?...\n");printf("Delete?begin?...\n");list_for_each(slider,?list){struct?Node*?n?=?list_entry(slider,?struct?Node,?head);if(?n->value?==?3?){list_del(slider);free(n);break;}}list_for_each(slider,?list){printf("%d\n",?list_entry(slider,?struct?Node,?head)->value);}printf("Delete?end?...\n"); }int?main() {list_demo_1();list_demo_2();return?0; }

????????我們編譯看看結(jié)果

????????輸出結(jié)果如我們所想的那樣，現(xiàn)在移植已經(jīng)完成。經(jīng)過今天對 Linux 內(nèi)核中鏈表的移植，總結(jié)如下：1、Linux 內(nèi)核鏈表移植時需要剔除依賴以及平臺相關(guān)代碼；2、Linux 內(nèi)核鏈表是帶頭節(jié)點的雙向循環(huán)鏈表；3、使用 Linux 內(nèi)核鏈表時需要自定義鏈表節(jié)點：a> 將 struct list_head 作為結(jié)點結(jié)構(gòu)體的第一個成員或最后一個成員；b> struct list_head 作為最后一個成員時，需要使用 list_entry 宏；c> list_entry 的定義中使用了 container_of 宏。

轉(zhuǎn)載于:https://blog.51cto.com/12810168/2175686

總結(jié)

以上是生活随笔為你收集整理的Linux 内核链表剖析（二十）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。