Linux辅导：Linux内核学习之链表

会计考友

在Linux内核中大量处所使用了链表这个数据结构。相信科班身世的学生或者自己进修过数据结构的同窗都不目生，不错，他就是最简单的线性结构——链表。不外，在内核傍边，一般采用的都是轮回双联表的数据结构。因为源码有三百多行我就不贴在这里，有乐趣的去下载一下：http://download.csdn.net/detail/huiguixian/3889011. 　　1. 链表的界说
/ T' G$ P6 ]1 `& Q- A: s" E) _　　这个跟我们在课本上进修的一样，相当简单。搜罗了一个前项指针，和后项指针。是不是有点不合错误劲？不错，竟然没稀有据域！不急，我们慢慢看。
" f, R$ B: ^& o% a　　view plainprint？
　　struct list_head { struct list_head *next， *prev；}；没稀有据是内核链表的一大特色，因为他采用的体例斗劲非凡，他不是用链表来包含数据的，而是让数据项反回来包含链表的。刚起头多多少少有点难以理解，下面会诠释的。
　　2. 链表的的界说和初始化
+ h. k. a3 p* Z6 i5 r" L0 \: C0 x　　（1）采用LIST_HEAD宏在编译时静态初始化
2 K' K. {3 p* o# E　　view plainprint？
: a' S  _  D. |1 f, l　　#defineLIST_HEAD_INIT（name） { &（name）， &（name） } #defineLIST_HEAD（name） \ struct list_head name =LIST_HEAD_INIT（name）
　　LIST_HEAD_INIT是宏界说，也就是耸ё仝界说的时辰把他扩展一下就很轻易理解了。好比初始化语句为
2 j' U8 s) Y- _& C% B2 m3 j9 B　　LIST_HEAD（event_list），可以理解为
　　view plainprint？
( D% q2 `9 {( n( z* [8 J; v　　struct list_headevent_list = { &event_list， &event_list }结构体巨匠应该还没有健忘吧，琅缦沔有一条可以按照成员挨次在界说时对其进行初始化，所以这句就很较着了。目的是把next prev指针初始化指向它自己。
　　（2）采用INIT_LIST_HEAD函数在运行时动态初始化，这个目的一眼就看出来了，同膳缦沔一样。
　　view plainprint？
　　static inline voidINIT_LIST_HEAD（struct list_head *list）
8 Q0 ^' O" E$ z' y　　{ list->next = list；list->prev = list；} 3. 判定链表是否为空的操作，即是判定是否指向自己自己而已
* ^& X7 `; ~7 G& S8 _1 `
1 G" l2 l8 U7 K6 a: i　　view plainprint？

会计考友

</p>　　static inline intlist_empty（const struct list_head *head）
. K& c, A+ @' \4 ?4 L　　{ return head->next == head；} 4.插入操作，学过链表操作的都看得懂，看不懂的自己去学链表去。
　　view plainprint？
　　static inline void__list_add（struct list_head *new，struct list_head *prev，struct list_head *next）
9 ]2 O) H- e$ ~" t# Q　　{ next->prev = new；new->next = next；new->prev = prev；prev->next = new；} static inline voidlist_add（struct list_head *new， struct list_head *head）
　　{ __list_add（new， head，head->next）；} static inline voidlist_add_tail（struct list_head *new， struct list_head *head）
2 i6 \2 ]" W% |7 A0 C& X6 {　　{ __list_add（new， head->prev，head）；} 5. 移动、删除等等近似，首要讲遍历！遍历的出色部门在于链表是被数据包含着的，若何经由过程被包含的链表掏出包含他的数据（有点拗口）
　　好比书上举的阿谁例子：
　　view plainprint？
& q# w, {. ?, h- x5 T　　struct list_head*tmp；struct usb_hub *hub；tmp =hub_event_list.next；hub = list_entry（tmp，struct usb_hub， event_list）；数据结构是usb_hub，琅缦沔包含着一个list_head数据项，然后此刻有一个list_head的链表hub_event_list，要掏出琅缦沔包含hub_event_list.next的数据usb_hub.这就是上述代码的功能。最主要的函数为list_entry，代码如下：
  }+ M! t! p' F! _$ N　　view plainprint？
' F5 d9 \1 V. f( n8 W1 j: `) U　　#definelist_entry（ptr， type， member） \ container_of（ptr， type， member）
　　这个不用诠释，他挪用的是container_of（ptr， type， member），直接看这赋Ｊ界说
# J& J& J: K7 U- [) w9 z$ W2 p　　view plainprint？
　　#definecontainer_of（ptr， type， member） （{         \ const typeof（ （（type *）0）->member ）*__mptr = （ptr）；    \（type*）（ （char *）__mptr - offsetof（type，member） ）；}）
5 P( R  k7 a* b* V/ [6 `: L; D　　#defineoffsetof（TYPE， MEMBER） （（size_t） &（（TYPE *）0）->MEMBER）
5 l) {5 A2 J3 E5 _- X2 v! @　　这个看起来斗劲吃力。需要一步步理解。首先，宏界说不是函数，宏界说的参数不受函数的限制，所以在list_entry和container_of的第二个参数都是以数据类型做参数的。此外GCC有一个对ISO C的扩展，就是他撑持typeof操作，具体可以看这里：http://blog.csdn.net/huiguixian/article/details/7045311 .首要看最后讲解typeof.简单来看他就是可以返回一个类型，根基可以用在你想用的任何时辰。
; s3 R6 }1 u1 V9 R. b　　接着膳缦沔的例子来诠释：
% j% Z3 y9 C) B& h# j　　type为usb_hub，type *就是usb_hub*，0可以理解为NULL，也就是usb_hub->event_list就是（（type *）0）->member.一整句就是界说了一个list_head类型的常量指针，指向了参数的event_list.然后下一步是经由过程计较偏移量，让这个指针减去这个偏移量，即减去后的指针指向的可以看作是一个usb_hub的数据结构，至此就把usb_hub掏出来了。