如果想出发,就不要等到明天!
全部博文(317)
分类: C/C++
2013-06-13 19:36:09
原文地址:Linux内核list/hlist解读 作者:aquester
Linux内核list/hlist解读
目录
3.12. list_for_each_safe_rcu 14
Linux内核实现了一批优雅而功能强大的双向循环列表操作宏,它们位于/usr/include/linux/list.h(请注意直接#include会报编译错误),这些宏可以直接扣出来,在需要时使用。
请注意typeof并不是一个宏,而是GCC的一个内建操作符。
typeof(variable)
得到变量variable的类型,这个类型可以用来定义同类型的其它变量。
int m = 1;
typeof(m) n = m; // 等同于int n = m;
// type:结构体类型
// member:结构体成员
#define offsetof(type, member) \
((size_t) &((type *)0)->member)
计算出一个结构体type中,指定成员member在该结构体中的位置。
(type *)0是一个类型为type的指针,其指针地址为0x0。&((type *)0)->member)是得到成员member的地址,由于结构体本身的地址为0x0,所以成员member的地址亦为member在该type中的偏移位置。
假设有如下一个结构体:
#pragma pack(4)
struct X
{
int32_t a;
int32_t b;
int32_t c;
};
#pragma pack()
那么offsetof(Struct X, b)的值等于4。
// ptr:结构体成员member的地址
// type:结构体类型
// member:结构体成员member
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
通过结构体一个成员的地址,得到该结构体的地址。
定义结构体变量:
struct X x;
那么container_of(&x.b, struct X, b)的值将和&x相等。
// x:需要预读的变量
#define prefetch(x) __builtin_prefetch(x)
这里使用到的__builtin_prefetch是GCC内建函数,它的作用是告诉cpu括号中的x可能马上就要用到,以便cpu预取一下,这样可以提高效率。
struct list_head
{
struct list_head *next; // 指向下一个结点
struct list_head *prev; // 指向前一个结点
};
这个定义虽然简单,但却是核心。
用来实现通用的双向链表,只包括前后指针,并不包含数据成员。
struct list_head有点类似于C++基类:
class list_head
{
public:
list_head()
: next(NULL)
, prev(NULL)
{
}
public: // 实际使用时,应当改为private,采用成员函数操作方式
list_head* next;
list_head* prev;
};
在C++语言中,基类是子类实例的一个子对象。在设计模式中,有template模式与strategy两个可以相互转化的模式,template模式采用的是继承,而strategy模式采用的是子对象方式。
由于在C语言中,没有继承的概念,所以只能采用子对象的方式。因此需要这样使用:
struct MyData
{
// 它在结构体中出现的顺序没有要求,
// 因为可以通过下面将要介绍的container_of宏来取得它所归属结构体的地址
struct list_head list;
char* data;
};
如果是在C++中,则:
class MyData: pubic list_head
{
private:
char* _data;
};
在C++中,如果:
list_head* data = new MyData;
则可以这样:
MyData* mydata = dynamic_cast
即可由基类子对象的地址,来得到子类对象的地址。而在C语言中,则需要借助container_of宏:container_of(data, MyData, list);
双向循环列表头尾相连,有2个遍历方向:
1) 顺时针
2) 逆时针
// ptr:结构体成员member的地址
// type:结构体类型
// member:结构体成员member
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
从list_entry的定义可以看出,它等同于container_of,即通过结构体type一个成员member的地址ptr,得到该结构本的地址。
// pos:指向当前结点的指针
// head:指向双向链表的头的指针
#define list_for_each(pos, head) \
for (pos = (head)->next; \
prefetch(pos->next), pos != (head); \
pos = pos->next)
这里的prefetch(pos->next)不是必须的,只是为提升效率。
以顺时针方向遍历双向循环链表,由于是双向循环链表,所以循环终止条件是“pos != (head)”。在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。
struct list_head cur;
struct list_head list;
list_for_each(cur, &list)
{
// 使用cur
}
// pos:指向当前结点的指针
// head:指向双向链表的头的指针
#define __list_for_each(pos, head) \
for (pos = (head)->next; \
pos != (head); \
pos = pos->next)
功能和list_for_each相同,即以顺时针方向遍历双向循环链表,只不过省去了prefetch(pos->next)。在遍历过程中,不能删除pos(必须保证pos->next有效),否则会造成SIGSEGV错误。
// pos:指向当前结点的指针
// head:指向双向链表的头的指针
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; \
prefetch(pos->prev), pos != (head); \
pos = pos->prev)
以逆时针方向遍历双向循环链表。在遍历过程中,不能删除pos(必须保证pos->prev有效),否则会造成SIGSEGV错误。
// pos:指向当前结点的指针
// head:指向双向链表的头的指针
// n:临时用来保存指向pos的下一个结点的指针
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; \
pos != (head); \
pos = n, n = pos->next)
以顺时针方向遍历双向循环链表。在遍历过程中,允许删除pos,因为每次都保存了pos->next。
list_for_each_safe(pos, n, head) |
list_for_each(pos, head) |
遍历中,可删除pos |
遍历中,不可删除pos |
struct list_head cur;
struct list_head tmp; // 临时用来保存cur的next
struct list_head list;
list_for_each_safe(cur, tmp, &list)
{
// 使用pos
list_del(pos); // 将pos从链表中剔除
delete pos; // 删除pos
}
为方便讲解,假设有:
struct MyNode
{
struct list_head list;
};
实际中,应当将MyNode替代成需要的类型的,但不管叫什么,总是聚合了struct list_head。
// pos:指向当前结点(在这里,类型为MyNode)的指针
// head:指向双向链表list_head的头的指针
// member:list_head类型在MyNode中的成员(在这里为list)
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
以顺时针方向遍历双向循环链表。它和list_for_each一样是做链表遍历,但pos的类型不一样。在list_for_each中,pos类型是“struct list_head*”,而在list_for_each_entry是typeof(*pos)类型。
list_for_each_entry(pos, head, member) |
list_for_each(pos, head) |
遍历链表,pos和head是typeof(*pos)类型 |
遍历链表,pos和head是struct list_head类型 |
// 这个示例,是可以编译成功,并可运行查看效果
// 假设文件名为x.cpp,则编译方法为:g++ -g -o x x.cpp
#include
#include
struct list_head {
struct list_head *next, *prev;
};
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
static inline void __list_add(struct list_head *inserted,
struct list_head *prev,
struct list_head *next)
{
next->prev = inserted;
inserted->next = next;
inserted->prev = prev;
prev->next = inserted;
}
static inline void list_add_tail(struct list_head *inserted, struct list_head *head)
{
__list_add(inserted, head->prev, head);
}
#define prefetch(x) __builtin_prefetch(x)
#define offsetof(type, member) \
((size_t) &((type *)0)->member)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
// 以上除#include外的代码,是从/usr/include/linux/list.h直接抄过来的,
// 但请注意直接#include
// 定义一个结构体
struct MyData
{
public:
struct list_head list; // 功能上相当于从list_head继承
char* data;
};
int main()
{
MyData* head = new MyData; // 必须有个空闲头结点
MyData* data1 = new MyData; // 第一个结点
data1->data = reinterpret_cast
MyData* data2 = new MyData; // 第二个结点
data2->data = reinterpret_cast
INIT_LIST_HEAD(&head->list);
list_add_tail(&data1->list, &head->list);
list_add_tail(&data2->list, &head->list);
// 请注意cur1和cur2的数据类型
MyData* cur1 = NULL;
list_head* cur2 = NULL;
// 请注意下面两个循环的区别,它们是互通的
list_for_each_entry(cur1, &head->list, list)
{
printf("%p\n", cur1->data);
}
list_for_each(cur2, &head->list)
{
MyData* dd = container_of(cur2, MyData, list);
printf("%p\n", dd->data);
}
return 0;
}
上段代码运行后,将输出以下四行信息:
0x1
0x2
0x1
0x2
// pos:指向当前结点(在这里,类型为MyNode)的指针
// head:指向双向链表list_head的头的指针
// member:list_head类型在MyNode中的成员(在这里为list)
// n:用来临时存储pos的下一个结点(类型和pos相同)
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
list_for_each_entry的可删除结点版本。
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
prefetch(pos->member.prev), &pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
作用和list_for_each_entry相同,只不过它是逆时针方向遍历。
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
以顺时针方向,从pos点开始遍历链表。
list_for_each_entry_continue(pos, head, member) |
list_for_each_entry(pos, head, member) |
从pos点开始遍历链表 |
从头开始遍历链表 |
传入的pos不能为NULL,必须是已经指向链表某个结点的有效指针 |
对传入的pos无要求,可以为NULL |
这个牵涉到RCU(Read-Copy-Update),在这里不详细讲解了,如有兴趣,请参考《玩转多线程编程.ppt》一文。
hlist也是 一种双向链表,但不同于list_head,它的头部只有一个指针,常被用作哈希表的bucket数组,这样就可减少哈希bucket一半的内存消耗。
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};