开始研读
下Linux
内核代码刚开始就有令人惊叹发现不得不感叹内核代码设计得的美！单是最常用链表也设计得不得不令人佩服！1.1.链表list_head
/linux/list.h很经典
链表在内核中很常用例如管理进程进程各个状态队列都是使用这个双向链表实现
内核中链表定义成和数据无关形式而不是通常我们使用链表格式例如typedef struct _list{
Elemtype elem;
struct _list *next;
}list;
内核中
链表定义为struct list_head{
struct list_head *next, *prev;
};
可见
这个链表节点中不包含任何数据只有两个指针当需要使用链表来组织数据结构时这个结构中就包含个list_head成员例如struct _list_struct{
Elemtype elem;
struct list_head list;
...
};
显而易见
链表实现成和数据分离好处是不用为每种数据都定义链表操作可以使用统链表操作即可但是问题是:只知道数据成员list地址怎样去访问自身以及其他成员呢？#
list_entry(ptr,type,member) \container_of(ptr,type,member)
而container_of(ptr,type,member)宏定义在
/list/kernel.h中#
container_of(ptr,type,member) ({const typeof( ((type *)0)->member) *__ptr=ptr;
(type *)( (char *)__ptr - off
of(type,member));})上面
宏有几点需要解释:1)typeof(type) 宏
typeof(type) 宏返回变量type
类型例如:
a; typeof(a) b;等价于 b;2)off
of(type,member)宏它定义在
/linx/stddef.h中如下:#
offof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)这个宏返回member在type类型中
偏移量type是个结构例如:typeof(list_head,next);返回0
也就是返回相对于结构起始地址偏移量3)为什么要使用typeof(((type *)0)->member)来定义指针 __ptr
而不是这样:const typeof(member) *__ptr=ptr;？
其实
这个很简单
member是结构成员只能通过结构来访问！4)访问数据
在文件
/linux/list.h中有访问链表数据代码#
list_for_each_entry(pos, head, member)for(pos=list_entry((head)->next,typeof(*pos),member);...)
从上面
使用来看替换list_entry宏以及container_of宏后变成如下:pos=({const typeof(((typeof(*pos) *)0)->member) *__ptr=(head)->next;
(typeof(*pos) *)((char *)__ptr - off
of(typeof(typeof(*pos)),member));});1)这里
语法很奇怪小括号
中包含了个代码段{}这是平常都见不到1.2.链表hlist_head
hlist_head链表也是
个双向链表它定义如下struct hlist_head{
struct hlist_node *first;
};
struct hlist_node{
struct hlist_node *next, **prev;
};
显然
这个双向链表不是真正双向链表表头只有个first域为什么这样设计？代码中注释解释:为了节约内存特别适合作为Hash表冲突链但Hash表很大时那么表头节约下来内存就相当客观了虽然每个表头只节约个指针同时
表头不致性也会带来链表操作上困难显然就是在表头和首数据节点的间插入节点时需要特别处理这也就是为什么会设计 2级指针pprev原因看看代码
inline void hlist_add_before(struct hlist_node *n,struct hlist_node *next){
n->pprev=next->pprev;
n->next=next;
next->pprev=&n->next;
*(n->pprev)=n;
}
解释:指针n指向新节点
指针next指向将要在它的前插入新节点那个节点看上面
代码就可以看到 2级指针pprev威力了！有没有看到当next就是第个数据节点时这里插入也就是在表头和首数据节点的间插入个节点但是并不需要特别处理！而是统使用*(n->pprev)来访问前驱指针域(在普通节点中是next而在表头中是first)这太经典了！本文来自CSDN博客
转载请标明出处:http://blog.csdn.net/leisure512/archive/2010/01/14/5188986.aspx
最新评论