linux/list.h中,双向循环链表的结构体定义:
struct list_head {
struct list_head *next, *prev; };
|
可以看到,这个结构中不包括数据域。也就是说,这个结点本身并不保存什么数据信息。那它的作用是什么呢?
linux内核经常要维护数据结构的列表。实现的方法就是通过将 struct list_head 结构体嵌入到所需要维护的数据结构中去,通过维护这个链表结构体,来达到所要维护数据结构的列表。
LDD3的图11-1明确地显示了这种关系。
在把 list_head 嵌入到一个 custom structure 后,这些 custom structure 就有了链接的关系。
通过 list_entry macro 可以从一个链表节点得到包含该节点的 custom structure 的指针。
/**
* 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)
|
(解释补在后面)
对于链表的操作:添加、删除...等,头文件中都有。一个需要理解的操作是:遍历
也就是通过该链表,遍历整个 custom structure 链表。
这个是通过 list_for_each_entry宏实现的,其代码如下:
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/ #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))
|
其中的prefetch是预取当前结点的下一个结点,当链表节点很多时,它能加快运行速度。
关于结构体成员的初始化
一开始没有看懂下面这个代码:
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
|
第一个宏后面的 {&(name), &(name)} 在第二个宏中当作右值直接赋给 struct list_head name.
一个双向循环链表初始是将头结点的两个成员指针赋值为本结构体的地址!
该头文件还提到一个hlist,它主要是为HASH表而构造的数据类型。有数据结构的基础,仔细看代码就可以弄清楚它的结构。这里主不多提了。
http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/#N101F3
补:contaner_of的理解
------------------ #define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );}) ----
第一句:定义一指针指向ptr。
第二句:用ptr的地址 |减去| member成员变量在type中的偏移地址,
再强转换成type类型的地址。
作用:
-------
由member成员的地址(ptr为指向member的指针)得到包含member成员的type的地址。
-------
一个例子:
struct scull_dev *dev;
container_of(inode->i_cdev, struct scull_dev, cdev);
其中:i_cdev是指向cdev的指针。[LDD3-P62]
------------------ #ifdef __compiler_offsetof #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) #else #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #endif ----
作用:获取MEMBER在TYPE中的偏移地址 ------------------
|
PS:
注意到贯穿整个文件的: static
inline
还有内核API:双下划线'__'为前缀,不过这些API都会被封装到省略'__'的相同API函数中去。