Kernel base Series(1)-----list_head

声明：本文为原创

#####请转贴时保留以下内容######

作者：GTT

本文档归属http://oldtown.cublog.cn/.转载请注明出处!

请提出宝贵意见Mail:[e-mail]

Linux Version：2.6.33

提示：本文是介绍一些linux kernel 基础数据结构系列！

 

以前在看Kernel source code 时，写了一些资料，希望对大家有些帮助。

这篇文章关于linux 的链表，很基础的。如果你很了解，可以直接pass掉。如果你刚刚看linux kernel，看看也许对你有些帮助。

 

你要问我kernel里什么数据结构用的最多，我会告诉你是链表。linux kerne 里很多地方都使用了双向循环链表，
hash表。链表是linux的基础，如果掌握了，各种数据结构之间的关系也很容易掌握。

 

linux 双向链表的实现是list_head
定义如下

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

刚看到这个结构时，是不是感觉缺点什么。就是个链，没有数据。怎么存储数据啊。
如果只看到这，想象的数据链只能是下面的

如何能存储数据呢？
存储了数据的链表至少应该如下

这样就有数据了，但也许还有疑惑，那个中类型的数据结构怎么又能和这个list_head联系在一起呢？
通常链表都是在自己的数据结构里定义两个结构名相同的指针。
如下

struct a {
   struct a *prev;
   struct a *next;
   …
}

这样相同类型a的实例，都可以链接起来了。达到上图的效果。
如果在a加入一个list_head，那么是不是跟上面的定义一致了

struct a {
   struct list_head list;
   …
}

剩下唯一的问题就是，如何根据list找到 a了。
上面的定义很好解决这个问题，强制转换list为struct a类型就可以了。
但如果是下面的定义呢？

struct a {
   …
   struct list_head list;
   …
}

 

强制转换是行不通了。所以得找个通用的方法来解决这个问题。
即给定结构定义和其中一个字段的内存地址，找到这个结构的内存地址。
用数学的角度考虑就是,知道两点相对距离，知道其中一个地点的坐标，求另一个地点的坐标。如下，D2距离0点长度是条件，D2到D1的长度也是条件，那么D1的坐标很容易算出的
就是D2距离0点长度减去D2到D1的长度

 

所以，只要求出字段和结构体顶的相对距离就可以知道结构体的实际内存地址了。
用下面的宏可以算出这个相对距离

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

 

也就是把内存0地址强制转换为TYPE类型，然后MEMBER的内存地址就是
这个相对距离了。很简单吧。
这样根据这个字段MEMBER的内存地址就可以找到TYPE的内存地址了。
这个过程的定义在下面

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr: the pointer to the member.
 * @type: the type of the container struct this is embedded in.
 * @member: the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type,member) );})

 

这个宏利用gcc的扩展typeof()获得member 成员的数据类型。
然后算出type 的内存地址。
member 的地址要高于type的，所以要减掉相对值。

可以参照下图理解这个宏

双向链表的声明与初始化

#define LIST_HEAD(name) \
struct list_head name = { &name, &name }
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

 

例如声明设备链表就可以这样声明
LIST_HEAD(devList)
判断这个devList是否为空，只要判断它的next是否等于devList就可以了。
判断list_head是否为空的方法

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}

很简单就是判断next是不是list_head自身。
通过下面的宏就可以取得所属结构体的地址了。

/**
 * list_entry - get the struct for this entry
 * @ptr: the &struct list_head pointer.
 * @type: the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

ptr 是list_head的指针，type 是所属结构体，member 是list_head在所属结构体的名称。

下面介绍list_head在双向链表里的增/删/合/移
对双向链表的插入操作有两种：表头/表尾插入。
所以有两个方法与之对应：

static inline void list_add(struct list_head *new, struct list_head *head)
static inline void list_add_tail(struct list_head *new, struct list_head *head)

插入前后可以说是换汤不换药，一个东西
都调用

static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)

这个方法。
插入表头是调用__list_add(new, head, head->next);新插入的new 就紧跟着head
插入表尾是调用__list_add(new, head->prev, head);新插入的new 则在链表最后面
插入表头/表尾也只是相对list_head的next,prev, 其实都紧挨着表头。一前一后的问题。

list_add在新增加new元素的先后变化图，如下

list_add_tail在新增加new元素的先后变化图，如下

删除一个双向链表的元素的方法如下

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

当元素被从双向链表上删除后，他的next/prev 被分别设置为常量LIST_POISON1/LIST_POISON2
以防止再次被误使用。

删除的前后变化图如下。
图中是删除Element3这个元素。

两个双向链表的合并

/**
 * list_splice - join two lists, this is designed for stacks
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
static inline void list_splice(const struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head, head->next);
}

 

list_splice把list链表的内容将挂接在head链表上，位于
head和head.next（原head链表的第一个节点元素）之间。
list_splice执行后新head链表将以原链list表的第一个节点
为首节点，而尾节点不变。
合并前后的变化如图

 

移动是指，从一个链表移动到另外一个链表上。
也就是两个动作，从一个链表上删除，在另一个链表上增加。
因为增加有表头/表尾插入，所以，移动也有两个方法

static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list, struct list_head *head)

可以参照增/删两种动作。

 

对双向链表的遍历

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

 

这只是取得了list_head,还要调用上面提到的list_entry(ptr, type, member) 来得到所属结构体的指针地址。
其他方法如下就不一一列出了。

 

Kernel base Series(2)将介绍hash table。