首页 > 代码库 > Linux list_head

Linux list_head

在linux kernel里面链表应用非常广泛。

我们在应用程序中,定义一个链表结构通常要包含数据域,如下:

typedef struct _listNode{

     int data;

     struct _listNode *prev, *next;

}ListNode;

但在内核代码中,定义的链表都没有数据域, 如下:

struct list_head {

  struct list_head *next, *prev;

};
如果需要定义双链表结构,则在数据结构中包含一个list_head的成员变量,

struct book{

      int data;

      struct list_head list;

}

假设我们有另外一个结构体person,里面也有一个链表,这个链表是book的双链表。(代表一个人有多本书)

struct person{

     char *name;

     int booknum;

     struct list_head booklist;

}

我们在初始化时,创建book的结构,并且将book加入到person的book list中。

struct person *myperson;

book= kmalloc(sizeof(struct book), GFP_KERNEL);

list_add_tail(&book->list, &myperson->booklist);
person->booknum++

那么后续我们知道booklist结构的地址(address A),如何知道booklist中的book结构(address B)呢?

技术分享

 

struct book mybook;

list_for_each_entry(mybook, &myperson->booklist, list) //遍历myperson->booklist,每个元素放在mybook.

#define list_for_each_entry(pos, head, member) \
  for (pos = list_first_entry(head, typeof(*pos), member); \
  &pos->member != (head); \
  pos = list_next_entry(pos, member))

#define list_first_entry(ptr, type, member) \
  list_entry((ptr)->next, type, member)

最终展开的myperson->booklist的第一个元素的book结构为list_entry((&myperson->booklist)->next, struct book, list)

可以看出通过list_entry来获取myperson->booklist中的book结构。

#define list_entry(ptr, type, member) \
  container_of(ptr, type, member)

#define container_of(ptr, type, member) ({ \//ptr为(&myperson->booklist)的元素的地址(address A),type为实际的结构struct book,list是book中的list成员名字
  const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  (type *)( (char *)__mptr - offsetof(type,member) );})

将list_entry展开

((struct book*)((char *)((&myperson->booklist)->next)-(size_t)(&((struct book *)0)->list)))

 

(unsigned long)(&((struct book *)0)->list))即list相对于book 首地址的偏移(上图的offset)。

1. ( (type*)0 ) 将零转型为type类型指针; 
2. ((tpye*)0)->member访问结构中的数据成员; 
3. &( ( (type*)0 )->member)取出数据成员的地址; 
4.(size_t)(&(((type*)0)->member))转换成size_t类型,即member相对type结构首地址的偏移。

myperson的booklist 的地址(address A) 减去 偏移(offset)即为book结构首地址(Address B)。

Linux list_head