下面就是kernel中的list_head结构定义:
1 2 3 4 5 | struct list_head { struct list_head *next, *prev; }; |
比如所有的进程是靠它串联在一起的,所有的inode也靠它串联在一起等等。
需要注意的一点是,头结点head是不使用的,这点需要注意。
使用list_head组织的链表的结构如下图所示:

list_head
特别注意的是,list_head中的指针存放的是另一个list_head的地址,而不是含有list_head结构的整个数据结构的地址;举例如下:
1 2 3 4 5 6 7 | struct file_node{ char c; struct list_head node; }; |
1 2 3 4 5 6 7 8 9 10 11 | #define list_entry(ptr,type,member)\ container_of(ptr,type,member) #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) );} ) |
1 | #define offsetof(TYPE,MEMBER) ( (size_t)& ((TYPE *)0)-> MEMBER ) |
(TYPE *)0 它表示将 0地址强制转换为TYPE类型,((TYPE *)0)-> MEMBER 也就是从0址址找到TYPE 的成员MEMBER 。
我们结合上面的结构file_node来看
将实参代入 offset( struct file_node, node );最终将变成这样:
( (size_t) & ((struct file_node*)0)-> node );这样看的还是不很清楚,我们再变变:
struct file_node *p = NULL;
& p->node;
这样应该比较清楚了,即求 p 的成员 node的地址,只不过p 为0地址,从0地址开始算成员node的地址,也就是 成员 node 在结构体 struct file_node中的偏移量。offset宏就是算MEMBER在TYPE中的偏移量的。
我们再看第二个宏
1 2 3 4 5 | #define container_of(ptr,type,member) ( {\ const typeof( ((type*)0)->member ) *__mptr=(ptr);\ (type*)( (char*)__mptr - offsetof(type,member) );} ) |
(char*)__mptr 之所以要强制类型转化为char是因为地址是以字节为单位的,而char的长度就是一个字节。
container_of的值是两个地址相减,
刚说了__mptr是结构体中list_head节点的地址,offset宏求的是list_head节点MEMBER在结构体TYPE中的偏移量,那么__mptr减去它所在结构体中的偏移量,就是结构体的地址。
所以list_entry(ptr,type,member)宏的功能就是,由结构体成员地址求结构体地址。其中ptr 是所求结构体中list_head成员指针,type是所求结构体类型,member是结构体list_head成员名。通过下图来总结一下:

list
列举一些双链表的常用操作:双向链表的遍历——list_for_each
1 2 3 4 5 6 7 | //注:这里prefetch 是gcc的一个优化选项,也可以不要 #define list_for_each(pos, head) \ for (pos = (head)->next; prefetch(pos->next), pos != (head); \ pos = pos->next) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | //LIST_HEAD() -- 生成一个名为name的双向链表头节点 #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | //将new所代表的结构体插入head所管理的双向链表的头节点head之后: (即插入表头) static inline void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | static inline void list_del(struct list_head *entry) { __list_del(entry->prev, entry->next); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; } |
1 2 3 4 5 6 7 | static inline int list_empty(const struct list_head *head) { return head->next == head; } |