linux内核链表

注意：
1.以下代码除了说明的，一般都取自include/linux/list.h
2.内核版本为：2.6.32-71.29.1.el6.i686

一.链表数据结构的实现：

注意一点：在定义链表时，必须定义不带数据的头结点，然后让头指针指向它。在后面的遍历都是基于这点考虑的。
内核采用的双向循环链表，将指针域封装成一个结构体：

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

使用时直接将这个结构体与所要用到的数据放在一块组成一个结构体。

二.相关函数
1.声明和初始化
linux源代码中初始化结构体时，一般都会先把右值用宏定义出来，然后再赋值。我认为主要是想让代码可读性增强

#define LIST_HEAD_INIT(name) { &(name), &(name) }

  #define LIST_HEAD(name) \
  struct list_head name = LIST_HEAD_INIT(name)

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

2.插入/删除
    2.1插入
链表的插入根据插入的位置分为头插法和尾插法。先定义了一个可以在链表任意节点插入的函数，
然后再调用这个函数实现头插和尾插。

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 void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

尾插：

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

    2.2删除

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

注意要将删除节点的指针域指向特定值LIST_POISON1和LIST_POISON2,防止对entry的访问。

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}

 
3.遍历
3.1根据list_head获得结点的地址：
链表中仅仅给出的一个结点的list_head的地址，如何通过list_head的地址获得结点的地址，
从而获得数据域中的值呢？

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

//取自include/linux/kernel.h文件中

#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

3.2遍历宏

#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

有了list_for_each(),为什么还用定义list_for_each_safe()呢？
原因是当删除节点时，节点的next会被改变为一个固定值，下次遍历将产生错误。所以还需要一个指针来保存下一个节点指针。

#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

三.不足
  1. 链表的操作中还有像合并，移动的操作，这些就等到真正要用时再看一下吧。
  2.哈希表没有列出来
四.参考资料