linux内核学习之——链表篇

unix_fensi

                                -------------双向循环链表---------------------------
来源于：list.h
设计思想：尽可能的代码重用，化大堆的链表设计为单个链表。
链
表的构造：如果需要构造某类对象的特定列表，则在其结构中定义一个类型为list_head指针的成员，通过这个成员将这类对象连接起来，形成所需列表，
并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数，即可构造和操作不同对象的列表，而无需为每类对象的每种列表编写专用函数，实现了代码的
重用。
如果想对某种类型创建链表，就把一个list_head类型的变量嵌入到该类型中，用list_head中的成员和相对应的处理函数来对链表进行遍历。如果想得到相应的结构的指针，使用list_entry可以算出来。
-------------防止重复包含同一个头文件---------------
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H
...
#endif
用于防止重复包含同一个list.h头文件
-----------struct list_head{}及初始化宏---------
struct list_head
{
struct list_head *next, *prev;
};
list_head从字面上理解，好像是头结点的意思。但从这里的代码来看却是普通结点的结构体。在后面的代码中将list_head当成普通的结点来处理。
--LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
分析：name当为结构体struct list_head{}的一个结构体变量，&(name)为该结构体变量的地址。用name结构体变量的始地址将该结构体变量进行初始化。
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
1.ptr为一个结构体的指针，而name为一个结构体变量；
2.ptr使用时候，当用括号，(ptr);
------------__list_add()---list_add()-------------
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;
}
1.普通的在两个非空结点中插入一个结点，注意new,prev,next都不能是空值。
2.即：适用于中间结点插入。首结点和尾结点则由于指针为空，不能用此函数。
3.在prev指针和next指针所指向的结点之间插入new指针所指向的结点。
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
在head和head->next两指针所指向的结点之间插入new所指向的结点。
即：在head指针后面插入new所指向的结点。此函数用于在头结点后面插入结点。
注意：对只有一个单个结点的链表，则head->next为空，list_add（）不能用。
-------------list_add_tail()-------------------
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
在头结点指针head所指向结点的前面插入new所指向的结点。也相当于在尾结点后面增加一个new所指向的结点。（条件是：head->prev当指向尾结点）
注意：
1.head->prev不能为空，即若head为头结点，其head->prev当指向一个数值，一般为指向尾结点，构成循环链表。
2.对只有单个结点的头结点调用此函数则会出错。
-----------__list_del()---list_del()--------------
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
在prev和next指针所指向的结点之间，两者互相所指。在后面会看到：prev为待删除的结点的前面一个结点，next为待删除的结点的后面一个结点。
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
删除entry所指的结点，同时将entry所指向的结点指针域封死。
对LIST_POISON1,LIST_POISON2的解释说明： Linux
内核中解释：These are non-NULL pointers that will result in page faults under
normal circumstances, used to verify that nobody uses non-initialized
list entries. #define LIST_POISON1 ((void *) 0x00100100) #define LIST_POISON2 ((void *) 0x00200200) 常规思想是：entry->next = NULL; entry->prev = NULL;
注意：Linux内核中的‘=’都与前后隔了一个空格，这样比紧靠前后要清晰。
---------------list_del_init()--------------------
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
删除entry所指向的结点，同时将entry所指向的结点的next，prev指针域指向自身。
-----------list_move()--list_move_tail()----------
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
将list结点前后两个结点互相指向彼此，删除list指针所指向的结点，再将此结点插入head，和head->next两个指针所指向的结点之间。
即：将list所指向的结点移动到head所指向的结点的后面。
static inline void list_move_tail(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
删除了list所指向的结点，将其插入到head所指向的结点的前面，如果head->prev指向链表的尾结点的话，就是将list所指向的结点插入到链表的结尾。
---------------------list_empty(）-------------
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
注意：
1.如果是只有一个结点，head，head->next，head->prev都指向同一个结点，则这里会返回1，但链表却不为空，仍有一个头结点
2.return 后面不带括号，且为一个表达式。
3.测试链表是否为空,但这个空不是没有任何结点，而是只有一个头结点。
--------------------list_empty_careful(）---------
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
分析：
1.
只有一个头结点head，这时head指向这个头结点，head->next,head->prev指向head，
即：head==head->next==head->prev，这时候list_empty_careful（）函数返回1。
2.
有两个结点，head指向头结点，head->next,head->prev均指向后面那个结点，
即：head->next==head->prev,而head!=head->next,head!=head->prev.
所以函数将返回0
3.有三个及三个以上的结点，这是一般的情况，自己容易分析了。
注意：这里empty list是指只有一个空的头结点，而不是毫无任何结点。并且该头结点必须其head->next==head->prev==head
---------------__list_splice()------------------
static inline void __list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
--------------------list_splice()----------------
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
分析：
情况1：
普遍的情况，每个链表都至少有3个以上的结点：
====>此处作者画了图，可显示不出来，郁闷！！！
========》待作者上传一个word文档，图在里面。
-------------------------------------------------------------------------------------------
这种情况会丢弃list所指向的结点，这是特意设计的，因为两个链表有两个头结点，要去掉一个头结点。只要一个头结点。
---------------------------------------------------------------------------------------------------------------
特殊情况1：
初始情况：
------------------------------------------------------------------------
特殊情况2：
初始情况：
--------------------list_splice_init()-----------------------------------
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list))
{
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}
--------------------\asm-i386\posix_types.h-------
typedef unsigned int __kernel_size_t;
------\linux\types.h---------size_t---------------
#ifndef _SIZE_T
#define _SIZE_T
typedef __kernel_size_t size_t;
#endif
-------------\linux\compiler-gcc4.h--------------
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
分析准备：__compiler_offsetof(),为gcc编译器中的编译方面的参数，查阅gcc方面的文档:
--->gcc.pdf.Download from
www.gnu.org
。其中解释如下：
#define offsetof(type, member) __builtin_offsetof (type, member)
自
己分析：即：__builtin_offsetof(a,b)就是#define offsetof(TYPE, MEMBER) ((size_t)
&((TYPE
*)0)->MEMBER)。__builtin_offsetof(a,b)和offsetof(TYPE,MEMBER)本质一样的，只是
offsetof()宏是由程序员自己来设计(详见后面讲解)。而__builtin_offsetof()宏就是在编译器中已经设计好了的函数，直接调
用即可。明白了这个区别后，下面的代码很好理解。
-------\linux\stddef.h-----offsetof()-----------
#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)
-------------------------------
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
1.对__compiler_offsetof()宏的分析：
__compiler_offsetof
来确认编译器中是否内建了功能同offsetof()宏一样的宏。若已经内建了这样的宏，则offsetof()就是使用这个内建宏
__compiler_offsetof()即：__builtin_offsetof()宏。如果没有定义__compiler_offsetof()
宏，则offsetof()宏就由程序员来设计之。
2.对offsetof()宏的分析：（以下引用论坛）---曾经的腾讯QQ的笔试题。
宿舍舍友参加qq笔试，回来讨论一道选择题，求结构中成员偏移。
想起Linux内核链表，数据节点携带链表节点，通过链表访问数据的方法，用到offsetof宏，今天把它翻了出来:
#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER ) 一共4步 1. ( (TYPE *)0 ) 将零转型为TYPE类型指针; 2. ((TYPE *)0)->MEMBER 访问结构中的数据成员; 3. &( ( (TYPE *)0 )->MEMBER )取出数据成员的地址; 4.(size_t)(&(((TYPE*)0)->MEMBER))结果转换类型.巧妙之处在于将0转换成(TYPE*)，结构以内存空间首地址0作为起始地址，则成员地址自然为偏移地址；
举例说明：
#include
typedef struct _test
{
char i;
int j;
char k;
}Test;
int main()
{
Test *p = 0;
printf("%p\n", &(p->k));
}
自
己分析：这里使用的是一个利用编译器技术的小技巧，即先求得结构成员变量在结构体中的相对于结构体的首地址的偏移地址，然后根据结构体的首地址为0，从而
得出该偏移地址就是该结构体变量在该结构体中的偏移，即：该结构体成员变量距离结构体首的距离。在offsetof()中，这个member成员的地址实
际上就是type数据结构中member成员相对于结构变量的偏移量。对于给定一个结构，offsetof(type,member)是一个常
量，list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。
---------------------typeof()--------------------
--->我开始不懂，源代码中也查不到，网上发贴请教。由liubo1977在www.linuxforum.net上的Linux内核技术论坛上解答，QQ:84915771
答复：
unsigned int i;
typeof(i) x;
x=100;
printf("x:%d\n",x);
typeof() 是 gcc 的扩展，和 sizeof() 类似。
------------------------
container_of()
和offsetof()并不仅用于链表操作，这里最有趣的地方是 ((type *)0)->member，它将0地址强制 "转换" 为
type 结构的指针，再访问到 type 结构中的 member 成员。在 container_of 宏中，它用来给 typeof()
提供参数，以获得 member 成员的数据类型；
---------------container_of()--------------------
container_of() 来自\linux\kernel.h
内核中的注释：container_of - cast a member of a tructure 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 truct.
#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) 自己分析： 1.(type
*)0->member为设计一个type类型的结构体，起始地址为0，编译器将结构体的起始的地址加上此结构体成员变量的偏移得到此结构体成员变
量的偏移地址，由于结构体起始地址为0，所以此结构体成员变量的偏移地址就等于其成员变量在结构体内的距离结构体开始部分的偏移量。即：&
(type *)0->member就是取出其成员变量的偏移地址。而其等于其在结构体内的偏移量:即为：(size_t)(&
((type
*)0)->member)经过size_t的强制类型转换后，其数值为结构体内的偏移量。该偏移量这里由offsetof()求出。 2.typeof( ( (type *)0)->member )为取出member成员的变量类型。用其定义__mptr指针.ptr为指向该成员变量的指针。__mptr为member数据类型的常量指针，其指向ptr所指向的变量处。 3.(char
*)__mptr转换为字节型指针。(char *)__mptr - offsetof(type,member)
)用来求出结构体起始地址（为char *型指针），然后(type *)( (char *)__mptr -
offsetof(type,member) )在(type *)作用下进行将字节型的结构体起始指针转换为type *型的结构体起始指针。 这就是从结构体某成员变量指针来求出该结构体的首指针。指针类型从结构体某成员变量类型转换为该结构体类型。
               
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/79063/showart_1186531.html