内核中的链表

2.6 内核中的链表

鉴于链表在内核中的特殊地位，有必要在此对其做一番陈述。内核中链表的实现位于include/linux/list.h文件，链表数据结构的定义也很简单。

21 struct list_head {
22      struct list_head *next, *prev;
23 };

list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核中的链表实际上都是双链表（通常都是双循环链表）。

通常，我们在数据结构课堂上所了解的链表定义方式是这样的（以单链表为例）：

struct list_node {
    struct list_node *next;
    ElemType    data;
};

通过这种方式使用链表，对每一种数据类型，都要定义它们各自的链表结构。而内核中的链表却与此不同，它并没有数据域，不是在链表结构中包含数据，而是在描述数据类型的结构中包含链表。

比如在hub驱动中使用struct usb_hub来描述hub设备，hub需要处理一系列的事件，比如当探测到一个设备连进来时，就会执行一些代码去初始化该设备，所以hub就创建了一个链表来处理各种事件，这个链表的结构如图3.6所示。

 

图3.6  hub链表结构

（1）声明与初始化。

链表的声明可以使用两种方式，一种为使用LIST_HEAD宏在编译时静态初始化，一种为使用INIT_LIST_HEAD()在运行时进行初始化。

25 #define LIST_HEAD_INIT(name) { &(name), &(name) }
26
27 #define LIST_HEAD(name) \
28      struct list_head name = LIST_HEAD_INIT(name)
29
上面去掉宏LIST_HEAD_INIT(name)后变为：
#define LIST_HEAD(name) \
struct list_head name = { &(name), &(name) }
例：
       LIST_HEAD(name);
       <==> struct list_head name = LIST_HEAD_INIT(name)
       <==> struct list_head name = { &(name), &(name)}

注解：
对于你的结构, 若想初始化, 可以
struct stu
    {
      int num;
   char name[10];
   struct stu *next;
 }; struct stu a={1, "xiaowang"}, b={2, "xiaoli"};

30 static inline void INIT_LIST_HEAD(struct list_head *list)
31 {
32      list->next = list;
33      list->prev = list;
34 }

无论采用哪种方式，新生成的链表头的两个指针next、prev都初始化为指向自己。

（2）判断链表是否为空。

298 static inline int list_empty(const struct list_head *head)
299 {
300     return head->next == head;
301 }

（3）插入。

有了链表，自然就要对其进行操作，就要向里面加东西。list_add()和list_add_tail()这两个函数可以完成这个工作。

67 static inline void list_add(struct list_head *new, struct list_head *head)
68 {
69      __list_add(new, head, head->next);
70 }
84 static inline void list_add_tail(structlist_head *new, struct list_head *head)
85 {
86      __list_add(new, head->prev, head);
87 }

其中，list_add()将数据插入在head之后，list_add_tail()将数据插入在head->prev之后。其实对于循环 链表来说，表头的next、prev分别指向链表中的第一个和最后一个节点，所以，list_add()和list_add_tail()的区别并不大。

（4）删除。

链表里的元素不能只加不减，没用了的元素就应该删除掉。

224 static inline void list_replace_init(struct list_head *old,
225                     struct list_head *new)
226 {
227     list_replace(old, new);
228     INIT_LIST_HEAD(old);
229}

list_replace_init()从链表里删除一个元素，并且将其初始化。

（5）遍历。

内核中的链表仅仅保存了list_head结构的地址，我们如何通过它获取一个链表节点真正的数据项？这就要提到链表的所有操作里面最为重要的list_entry宏了，我们可以通过它很容易地获得一个链表节点的数据。

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

还是hub驱动的那个例子，当我们要处理hub的事件的时候，我们当然需要知道具体是哪个hub触发了这起事件。而list_entry的作用就 是，从struct list_head event_list得到它所对应的struct usb_hub结构体变量。比如以下4行代码：

struct list_head *tmp;
struct usb_hub *hub;
tmp = hub_event_list.next;
hub = list_entry(tmp, struct usb_hub, event_list);

从全局链表hub_event_list中取出一个来，叫做tmp，然后通过tmp，获得它所对应的struct usb_hub。