Linux内核学习之链表

发布时间：2012-06-09 10:14:32作者：知识屋

在Linux内核中大量处所使用了链表这个数据结构。相信科班身世的学生或者自己进修过数据结构的同窗都不目生，不错，他就是最简单的线性结构——链表。不外，在内核傍边，一般采用的都是轮回双联表的数据结构。因为源码有三百多行我就不贴在这里
1. 链表的界说

    这个跟我们在课本上进修的一样，相当简单。搜罗了一个前项指针，和后项指针。是不是有点不合错误劲？不错，竟然没稀有据域！不急，我们慢慢看。

    view plainprint？

    struct list_head { struct list_head *next， *prev；}；没稀有据是内核链表的一大特色，因为他采用的体例斗劲非凡，他不是用链表来包含数据的，而是让数据项反回来包含链表的。刚起头多多少少有点难以理解，下面会诠释的。

    2. 链表的的界说和初始化

    （1）采用LIST_HEAD宏在编译时静态初始化

    view plainprint？

    #defineLIST_HEAD_INIT（name） { &（name）， &（name） } #defineLIST_HEAD（name） struct list_head name =LIST_HEAD_INIT（name）

    LIST_HEAD_INIT是宏界说，也就是耸ё仝界说的时辰把他扩展一下就很轻易理解了。好比初始化语句为

    LIST_HEAD（event_list），可以理解为

    view plainprint？

    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）

    { list->next = list；list->prev = list；} 3. 判定链表是否为空的操作，即是判定是否指向自己自己而已

    view plainprint？

    static inline intlist_empty（const struct list_head *head）

    { return head->next == head；} 4.插入操作，学过链表操作的都看得懂，看不懂的自己去学链表去。

    view plainprint？

    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；} 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）

    { __list_add（new， head->prev，head）；}
5. 移动、删除等等近似，首要讲遍历！遍历的出色部门在于链表是被数据包含着的，若何经由过程被包含的链表掏出包含他的数据（有点拗口）

    好比书上举的阿谁例子：

    view plainprint？

    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，代码如下：

    view plainprint？

    #definelist_entry（ptr， type， member） container_of（ptr， type， member）

    这个不用诠释，他挪用的是container_of（ptr， type， member），直接看这赋Ｊ界说

    view plainprint？

    #definecontainer_of（ptr， type， member）（{         const typeof（（（type *）0）->member ）*__mptr = （ptr）；    （type*）（（char *）__mptr - offsetof（type，member））；}）

    #defineoffsetof（TYPE， MEMBER）（（size_t） &（（TYPE *）0）->MEMBER）

    这个看起来斗劲吃力。需要一步步理解。首先，宏界说不是函数，宏界说的参数不受函数的限制，所以在list_entry和container_of的第二个参数都是以数据类型做参数的。此外GCC有一个对ISO C的扩展，就是他撑持typeof操作，.首要看最后讲解typeof.简单来看他就是可以返回一个类型，根基可以用在你想用的任何时辰。

    接着膳缦沔的例子来诠释：

    type为usb_hub，type *就是usb_hub*，0可以理解为NULL，也就是usb_hub->event_list就是（（type *）0）->member.一整句就是界说了一个list_head类型的常量指针，指向了参数的event_list.然后下一步是经由过程计较偏移量，让这个指针减去这个偏移量，即减去后的指针指向的可以看作是一个usb_hub的数据结构，至此就把usb_hub掏出来了。

（免责声明：文章内容如涉及作品内容、版权和其它问题，请及时与我们联系，我们将在第一时间删除内容，文章内容仅供参考）