内核链表---include/linux/list.h
链表数据结构定义
struct list_head
{
struct list_head *next,*prev;
}
内核链表具备双链表功能，实际上，通常它都组织成双向循环链表。
链表操作---
初始化链表头
INIT_LIST_HEAD(list_head *head)
内核代码
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
插入节点---
list_add(struct list_head *new,struct list_head *head)
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
WARN(next->prev != prev,
"list_add corruption. next->prev should be "
"prev (%p), but was %p. (next=%p).\n",
prev, next->prev, next);
WARN(prev->next != next,
"list_add corruption. prev->next should be "
"next (%p), but was %p. (prev=%p).\n",
next, prev->next, prev);
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
EXPORT_SYMBOL(__list_add);
list_add_tail(struct list_head *new,struct list_head *head)
删除节点---
list_del(struct list_head *entry)
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;
}
提取数据-----
list_entry(ptr,type,member)---已知数据结构中节点的指针ptr，type大的结构的类型，member小结构在大结构中对应的成员名。函数返回指向大结构的指针。
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
指针ptr指向结构体type中的成员member；通过指针ptr，返回结构体type的起始地址
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
1.ptr为物理地址,其类型和member类型一致,最终使用typeof( ((type *)0)->member )
由编译器自动返回member的类型
2.type为包含member成员的结构体
3.offsetof(type,member)为member成员在type结构体中的偏移值,大小范围0~sizeof(type)字节 (因为以0地址为type类型数据结构的起始地址)
4.ptr- offsetof()就等于包含该ptr的type结构体父变量的物理起始地址,强制转换为(type*).
应用举例：
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#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_entry((head)->next, typeof(*pos), member)返回(head)->next物理指针所处位置向前减去offsetof()个字节数据之后, 其父变量pos的物理地址,父变量的类型在编译时由typeof(*pos)自动返回(gliethttp).
所以list_for_each_entry遍历head下面挂接的类型为typeof(*pos)的childs结构体们,当然每个child结构体包含struct list_head node之类相似的双向链表list_head类型项,就这样通过循环pos将依次指向双向链表上的各个child.(member就是child类型中被定义的变量名)
//-------------------------------------------------------------
下面一段程序摘自: drivers/usb/driver.c
struct usb_dynids {
spinlock_t lock;
struct list_head list;
};
struct usb_dynid {
struct list_head node;
struct usb_device_id id;
};
static const struct usb_device_id *usb_match_dynamic_id(struct usb_interface *intf,
struct usb_driver *drv)
{
struct usb_dynid *dynid;
spin_lock(&drv->dynids.lock);
//1. drv->dynids.list为head,即:树根,父亲,正如上面的struct usb_dynids
//2. dynid为child,其中drv->dynids.list.next存放了第一个child结构体中的
// struct list_head类型名字为node的物理地址值.
//3. 看着很复杂,其实翻译出来就简单多了(gliethttp)
//模型为for(child;child != head;child = child->next)
// for(dynid = container_of(drv->dynids.list.next, struct usb_dynid,nod);
// dynid->node != &drv->dynids.list;
// dynid = container_of(dynid->node.next, struct usb_dynid,nod)
// )
list_for_each_entry(dynid, &drv->dynids.list, node) {
if (usb_match_one_id(intf, &dynid->id)) {
spin_unlock(&drv->dynids.lock);
return &dynid->id;
}
}
spin_unlock(&drv->dynids.lock);
return NULL;
}
遍历---
list_for_each(struct list_head *pos,struct list_head *head)
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
列子--
list_for_each(pos,head)
{
card=list_entry(entry,struct cs_card,list)
if(card->dev_midi==minor)
break;
}