Linux内核学习之链表

文章参照任桥位Linux内核修炼之道3.6节编写。

在Linux内核中大量地方使用了链表这个数据结构。相信科班出身的学生或者自己学习过数据结构的同学都不陌生，不错，他就是最简单的线性结构——链表。不过，在内核当中，一般采用的都是循环双联表的数据结构。因为源码有三百多行我就不贴在这里，有兴趣的去下载一下：http://download.csdn.net/detail/huiguixian/3889011。

1. 链表的定义

这个跟我们在课本上学习的一样，相当简单。包括了一个前项指针，和后项指针。是不是有点不对劲？不错，竟然没有数据域！不急，我们慢慢看。

struct list_head {
        struct list_head *next, *prev;
};

没有数据是内核链表的一大特色，因为他采用的方式比较特殊，他不是用链表来包含数据的，而是让数据项反回来包含链表的。刚开始多多少少有点难以理解，下面会解释的。

2. 链表的的定义和初始化

(1)采用LIST_HEAD宏在编译时静态初始化

#defineLIST_HEAD_INIT(name) { &(name), &(name) }
#defineLIST_HEAD(name) \
        struct list_head name =LIST_HEAD_INIT(name)

LIST_HEAD_INIT是宏定义，也就是说在定义的时候把他扩展一下就很容易理解了。比如初始化语句为

LIST_HEAD(event_list)，可以理解为

struct list_headevent_list = { &event_list, &event_list }

结构体大家应该还没有忘记吧，里面有一条可以按照成员顺序在定义时对其进行初始化，所以这句就很明显了。目的是把next prev指针初始化指向它本身。

(2)采用INIT_LIST_HEAD函数在运行时动态初始化，这个目的一眼就看出来了，同上面一样。

static inline voidINIT_LIST_HEAD(struct list_head *list)
{
        list->next = list;
        list->prev = list;
}

3. 判断链表是否为空的操作，即是判断是否指向自己本身而已

static inline intlist_empty(const struct list_head *head)
{
        return head->next == head;
}

4.插入操作，学过链表操作的都看得懂，看不懂的自己去学链表去。

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. 移动、删除等等类似，主要讲遍历！遍历的精彩部分在于链表是被数据包含着的，如何通过被包含的链表取出包含他的数据（有点拗口）

比如书上举的那个例子：

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

#definelist_entry(ptr, type, member) \
        container_of(ptr, type, member)

这个不用解释，他调用的是container_of(ptr, type, member)，直接看这个宏定义

#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操作，具体可以看这里：http://blog.csdn.net/huiguixian/article/details/7045311。主要看最后讲解typeof。简单来看他就是可以返回一个类型，基本可以用在你想用的任何时候。

接着上面的例子来解释：

type为usb_hub，type *就是usb_hub*，0可以理解为NULL，也就是usb_hub->event_list就是((type *)0)->member。一整句就是定义了一个list_head类型的常量指针，指向了参数的event_list。然后下一步是通过计算偏移量，让这个指针减去这个偏移量，即减去后的指针指向的可以看作是一个usb_hub的数据结构，至此就把usb_hub取出来了。