Linux编程细节3-内核-数据结构

来源：易妖游戏网

内核代码版本：https://www.kernel.org/pub/linux/kernel/v2.6/ 2.6.11

1 链表

http://blog.chinaunix.net/uid-297520-id-3601869.html

1.1 概述

就像许多其他程序一样，操作系统内核经常需要维护数据结构的列表。有时，linux内核中同时存在多个链表的实现代码。为了减少重复代码的数量，内核开发者已经建立了一套标准的双向循环链表。如果你需要操作链表，那么建议你使用这一内核设施。内核链表的好主要体现为两点，一是可扩展性，内核一直都是在发展中的，所以代码都不能写成死代码，要方便修改和追加；二是封装，将链表常见的操作都进行封装，使用者只关注接口，不需关注实现。当使用这些链表接口时，应该始终牢记这些链表函数不进行任何锁定。如果你的程序有可能试图对同一个链表执行并发操作的话，则有责任实现一个锁方案。

1.2 头文件定义

源码版本：2.6.34.14版本内核源码

链表定义： include/linux/list.h

1.3 数据结构

linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。

1.3.1 传统的list

传统的链表有个最大的缺点就是不好共通化，因为每个node中的data1，data2等等都是不确定的(无论是个数还是类型)。
linux中的链表巧妙的解决了这个问题，linux的链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中。

1.3.2 内核的list

即将传统的” 链表持有节点“改成现在的” 节点持有链表“。 这也即C++中的继承的含义。

1.3.3 list_head结构

内核链表结构定义如下：

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

为了在代码中使用内核链表设施，只需在构成链表的结构里面嵌入一个list_head。如：

struct todo_struct {
        ... other members ...
        struct list_head list;
}

注意list_head的成员prev，next指向的是list_head而不是包含list_head的结构体，我们的链表是通过list_head链起来的。

/*
 * ptr:是指向type中链表节点的指针。
 * type:一般是个结构体，也就是包含用户数据和链表节点的结构体。 
 * member:则是type中定义链表节点是用的名字。
*/
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)
#define container_of(ptr, type, member) ({			\
        const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
        (type *)( (char *)__mptr - offsetof(type,member) );})
  
注：container_of定义于include/linux/kernel.h中

#ifdef __compiler_offsetof
	#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
	#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
注：offsetof定义于include/linux/stddef.h中

1.3.4 list_entry宏

下面分析一下container_of宏:

// 步骤1：将数字0强制转型为type*，然后取得其中的member元素
((type *)0)->member  // 相当于((struct student *)0)->list

// 步骤2：定义一个临时变量__mptr，并将其也指向ptr所指向的链表节点
const typeof(((type *)0)->member)*__mptr = (ptr);

// 步骤3：计算member字段距离type中第一个字段的距离，也就是type地址和member地址之间的差
// offset(type, member)也是一个宏，定义如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

// 步骤4：将__mptr的地址 - type地址和member地址之间的差
// 其实也就是获取type的地址

1.3.5 list_for_each遍历宏

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

1.3.6 list_head使用示例图

在使用链表时我们通常会定义一个链表头，链表头通常是一个的list_head结构，在使用链表前需初始化链表头。从上图可以看出，我们的链表几乎可以说是于包含它的结构的，任何保含list_head成员的结构都可以添加到链表中来（当然我们只会将相同的结构组合成一个链表），针对整个链表的插入，删除、和并等操作完全是在list_head上进行的，而链表的遍历也是在list_head上移动。由此，内核有一套通用的专门用于处理链表的函数和宏，我们不必针对每一个链表都写一套操作函数。

1.4 函数操作

下面将列出对链表进行操作的函数和宏（head指向为链表头）：

1.4.1 初始化

LIST_HEAD_INIT(name) 在编译阶段初始化链表头

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

LIST_HEAD(name) 在编译阶段定义并初始化链表头

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

INIT_LIST_HEAD(struct list_head *head) 在运行阶段初始化链表头

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

1.4.2 增加、删除、替换、移动元素

list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)
    将new插入到链表开始／末尾
list_del(struct list_head *entry)
list_del_init(struct list_head *entry)
    从链表中删除entry
list_replace(struct list_head *old, struct list_head *new)
list_replace_init(struct list_head *old, struct list_head *new)
    在链表中用new替换old
list_move(struct list_head *list, struct list_head *head)
list_move_tail(struct list_head *list, struct list_head *head)
    将list从其所在链表删除，再插入到head链表的开始／末尾
list_rotate_left(struct list_head *head)
    将链表第一元素移动到最后

1.4.3 链表判定

list_is_last(const struct list_head *list, const struct list_head *head)
    判定list为是否链表最后一个元素
list_empty(const struct list_head *head)
list_empty_careful(const struct list_head *head)
    判定链表是否为空
list_is_singular(const struct list_head *head)
    判定链表是否只包含一个元素

1.4.4 合并、分割链表

list_cut_position(struct list_head *head1, struct list_head *head2, struct list_head *entry)
    将head链表一分为二

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道