linux内核链表阅读笔记
时间：2010-10-25 来源：烟雾弹下的真实
Linux内核链表
1. 循环链表list
（1） 基本表结构
结构定义：
struct list_head {
struct list_head *next, *prev;
};
初始化节点：
static inline void INIT_LIST_HEAD(struct list_head *list)
（2） 一般定义循环链表步骤
定义头节点：
struct list_head *head=kmalloc（…）；
定义链表节点：
struct list_node
{
struct list_head node；
data_type data；
}
初始化头结点：
INIT_LIST_HEAD（head）；
构造和初始化结点：
struct list_node *data_node=kmalloc（…）
INIT_LIST_HEAD（&data_node->node）；
（3） 常用循环链表操作
插入：
在链表头后面插入，类似于栈的插入
static inline void list_add(struct list_head *new, struct list_head *head)
如：list_add（&data_node->node,head）
在链表尾部插入，类似于队列的插入
static inline void list_add_tail(struct list_head *new, struct list_head *head)
如：list_add_tail（&data_node->node，head）
删除：
static inline void list_del(struct list_head *entry)
如：list_del（&data_node->node）
遍历：
获取单个节点
list_entry(ptr, type, member)
ptr指向欲获得的节点（head->next），type为这个结点的类型（struct list_node），member为这个类型中的list_head成员名（node）
如：
struct list_node *pos；
pos=list_entry（head->next，typeof（*pos），node）
遍历整个链表
list_for_each_entry(pos, head, member)
pos为struct list_node型指针，head为链表头（head），member为成员（node）
如：
struct list_node *pos；
list_for_each_entry（pos，head，node）{ }
安全遍历整个链表
当在遍历的时候需要删除当前节点的时候需要用到这个宏
list_for_each_entry_safe(pos, n, head, member)
其中n为struct list_node*型的指针。
如：
struct list_node *pos,*n；
list_for_each_entry_safe（pos，n，head，node）
{
list_del（&pos->node）；
}
2. 循环链表hlist
（1） 基本表结构
结构定义：
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
初始化节点：
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
static inline void INIT_HLIST_NODE(struct hlist_node *h)
（2） 一般定义循环链表步骤
定义头节点：
struct hlist_head *head=kmalloc（…）；
定义链表节点：
struct list_node
{
struct hlist_node node；
data_type data；
}
初始化头结点：
INIT_HLIST_HEAD（head）；
构造和初始化结点：
struct hlist_node *data_node=kmalloc（…）
INIT_HLIST_NODE（&data_node->node）；
（3） 常用循环链表操作
插入：
在链表头后面插入，当head->first=NULL时可以使用
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
如：
if（head->first=NULL）
hlist_add_head（&data_node->node,head）
在链表的某节点前插入
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
如：
if（head->first!=NULL）
hlist_add_before（&data_node->node，head->first）
删除：
static inline void hlist_del(struct hlist_node *n)
如：hlist_del（&data_node->node）
遍历：
获取单个节点
hlist_entry(ptr, type, member)
ptr指向欲获得的节点（head->first），type为这个结点的类型（struct hlist_node），member为这个类型中的hlist_node成员名（node）
如：
struct hlist_node *pos；
struct list_node *tpos;
tpos=hlist_entry（head->first，typeof（*pos），node）
遍历整个链表
hlist_for_each_entry(tpos, pos, head, member)
tpos为struct list_node指针，pos为struct hlist_node型指针，head为链表头（head），member为成员（node）
如：
struct hlist_node *pos；
struct list_node *tpos；
hlist_for_each_entry（tpos，pos，head，node）{ }
安全遍历整个链表
当在遍历的时候需要删除当前节点的时候需要用到这个宏
hlist_for_each_entry_safe(tpos, pos, n, head, member)
其中n为struct hlist_node*型的指针。
如：
struct hlist_node *pos,*n；
struct list_node *tpos；
hlist_for_each_entry_safe（tpos，pos，n，head，node）
{
hlist_del（&tpos->node）；
}
相关阅读 更多 +
