转自：
引子：
Linux和一般程序不同的是它内部含有了超量多的数据结构，并且绝大部分数据结构以层次的形式现出出来。为了有效的利用内存，一般情况下，数据结构在使用时通过kmalloc分配，使用结束后使用kfree释放，所以Linux的数据结构都会含有两点，使用引用计数来决定生存期，使用双向链接方式链接，如A通过链表链接B，B又通过指针指向A。
Linux中的链表很多是把同一种类型的数据结构链接在一起，然后挂在父辈数据结构的链表上形成双向链表，也有哈希表，哈希表用来快速的从内存中找到指定文件。也有把很多可用资源等链接成一个队列使用。
1.最常见链表数据结构
a)第一种形式
struct list_head{
structlist_head*next,*prev;
}
b)第二种形式
struct hlist_head{
structhlist_node*first;
};
struct hlist_node{
structhlist_node*next,**pprev;
};
2.概况
上面的两种结构体在单独使用时是毫无意义的，Linux把这些链表结构嵌入到其他的数据结构中用来连接多个数据结构，以内核对象结构举例，内核对象被连接在一起又连接在了kset的structlist_headlist链表上，如下：
structkobject{
const char *k_name;
char name[KOBJ_NAME_LEN];
struct kref kref;
struct list_head entry;
struct kobject *parent;
struct kset *kset;
struct kobj_type *ktype;
struct dentry *dentry;
wait_queue_head_t poll;
};
连接成下表形式：（注意中间的是kset）
kobject0 kobject1 kset kobject2 kobject3
║ ║ ║ ║ ║
┌──╫───────╫───────╫───────╫───────╫─────┐
│ entry entry list entry entry │
└─ prev ←──── prev ←──── prev ←──── prev ←──── prev ←───┘
┌→ next ────→ next ────→ next ────→ next ────→ next ────┐
└────────────────────────────────────────┘
*parent *parent *parent *parent *parent
&kset &kset &kset &kset &kset
类似的形式在Linux中式司空见惯的，一个kset与四个kobject链接在一起，并作为kobject的父辈链表。
双向链表的好处是，当给kset添加一个kset时，可以直接添加在kset链表的next上，而取出时从链表的prev取出，这是先进先出的形式，或者从链表的next添加，并且从next处取出，这是最近使用的形式。
为了能从链表中找到实体，Linux定义了如下宏
#define container_of(ptr,type,member)({\
const typeof ( ((type*) 0)->member ) *__mptr=(ptr);\
(type*)((char*)__mptr-offsetof(type,member));})
注：1.typeof(data)是找到date的类型，这里是找到ptr的类型
2.offsetof(type,member)是找到type类型中member的偏移地址用unsignedlong表示
举例得到kobject1的地址：
structlist_head*temp=kset.list.prev;
structkobjectkobject1=container_of(temp,structkobject,entry);
这个宏也是一般不直接使用的，而是套嵌在其他的宏或inline函数中，如上面常被定义成
#define toKobject(list)\
container_of(list,structkobject,entry)
到这一步，相信你已经对这个链表的使用大概有个底了，后面是缩短你处理链表时间的函数等。你可以在内核文档的/include/linux/list.h中见到这些
3.定义并初始化一个structlist_head链表
a）.使用前要先初始化，让它的prev,和next都指向自己。
#define LIST_HEAD_INIT(name) {&(name),&(name)}
b).声明一个name名称的链表并进行初始化
#define LIST_HEAD(name)\
struct list_head name=LIST_HEAD_INIT(name)
4.添加一个structlist_head节点，所有参数使用指针传递
a).基本函数,把new节点插入到prev和next节点之间，prev和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;
}
b).把new节点插入到head节点的next处。
static inline void list_add(struct list_head *new,struct list_head *head)
{
__list_add(new,head,head->next);
}
c).把new节点插入到head节点的prev处，也就是head的尾部
static inline void list_add_tail(struct list_head *new,struct list_head *head)
{
__list_add(new,head->prev,head);
}
4.删除一个structlist_head节点，所有参数使用指针传递
a).基本函数，连接prev和next，来忽略prev和next中间的节点
static inline void __list_del(struct list_head *prev,struct list_head *next)
{
next->prev=prev;
prev->next=next;
}
b).将entry节点从所在链表上删除，并赋予新值
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev,entry->next);
entry->next=LIST_POISON1;
entry->prev=LIST_POISON2;
}
c).将entry从所在链表上删除，并初始化
staticinlinevoidlist_del_init(structlist_head*entry)
{
__list_del(entry->prev,entry->next);
INIT_LIST_HEAD(entry);
}
5.替换一个structlist_head节点，
a).基本函数，把new节点插入到old节点所在的位置，并把old从链表上移出
staticinlinevoidlist_replace(structlist_head *old,struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
b).使用new节点代替old所在位置，并初始化移出的old
static inline void list_replace_init(struct list_head *old,struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}
5.转移一个struct list_head节点，
a).把list节点从所在链表上删除，然后插入到head的后面
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
b).把list从所在链表上删除，然后插入到head的前面，即head得尾部
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
6.检测函数
a).检测head是否被链接到了其他的链表上
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
b).检测链表是否为空，并且是否正确
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
b).检测list是否是head链表上的最后一个节点
static inline int list_is_last(const struct list_head *list,const struct list_head *head)
{
return list->next == head;
}
7.把一个链表上的所有结构转接到另外一个链表上
a).基本函数，把list所在的链表从list处整体删除然后插入到head的后面
static inline void __list_splice(struct list_head *list,struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
b).只有list有链表时才会进行转接
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
c).只有list有链表时才会进行转接，并且初始化list
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}
6.从list_head节点得到结构体
a).给出type类型中struct list_head member所在的位置来得到，这个type类型结构的地址
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
b)得到ptr的下一个的实体
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
7.遍历链表（比较有价值的宏）
a).使用pos遍历struct list_head *head上的所有节点
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head);pos = pos->next)
b).基本函数，使用pos遍历struct list_head *head上的所有节点
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
c).使用pos从尾部向前遍历head上的所有节点
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head);pos = pos->prev)
d).使用pos和n一起遍历head上的节点时。n是pos的next节点
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
e).遍历链表head的节点所在的数据结构体，使用数据结构体pos遍历
#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))
f).从链表head的尾部开始遍历节点所在的数据结构体，使用数据结构体pos遍历
#define list_for_each_entry_reverse(pos, head, member)\
for (pos = list_entry((head)->prev, typeof(*pos), member); \
prefetch(pos->member.prev), &pos->member != (head);\
pos = list_entry(pos->member.prev, typeof(*pos), member))
8.上面是struct list_head 的主要用法，熟练这些宏和函数的使用就可以避开链表的烦扰来专心研究数据结构。如果你现在还有耐心，下面是上述的Linux中的另外一组链表，struct hlist_head 和struct hlist_node.
9.与struct list_head 不同的是hlist_head和hlist_node组成以hlist_head为头的双向线链表，struct hlist_head link其实等价于struct hlist_node *link,只是使用结构体更加容易规划。另外，这两个链表结构常用在散列表中，组成如下的形式。
struct hlist_head {struct hlist_node *first;};
struct hlist_node {struct hlist_node *next, **pprev;};
struct hlist_head hlist_header[n]
hlist_header[0]---->hlist_node0--->hlist_node1---->hlist_node2--->hlist_node3
hlist_header[1]---->hlist_node0--->hlist_node1---->hlist_node2--->hlist_node3
hlist_header[2]---->hlist_node0--->hlist_node1---->hlist_node2--->hlist_node3
...............
hlist_header[n]---->hlist_node0--->hlist_node1---->hlist_node2--->hlist_node3
*first ─→ &hlist_node0
↑ *next──→ &hlist_node2
│ ↑ *next ───→ &hlist_node2
│ │ ↑ *next ─→ &hlist_node3
│ └──┐ └───┐ ↑ *next ──→(NULL)
│ │ │ └──┐
└────── **pprev └---- **prev └─── **prev └─ **prev
10.hlist的初始化
a).hlist_head的定义
#define HLIST_HEAD(name) struct hlist_head name = {.first = NULL }
b).hlist_head的初始化
#define HLIST_HEAD_INIT { .first = NULL }
c).hlist_node的初始化
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
h->next = NULL;
h->pprev = NULL;
}
11.在head上添加node
a).把node添加在h的后面
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
12.在node上添加node
a).把node n连接在next的前面
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
{
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
*(n->pprev) = n;
}
b).把node next连接在n的后面
static inline void hlist_add_after(struct hlist_node *n,
struct hlist_node *next)
{
next->next = n->next;
n->next = next;
next->pprev = &n->next;
if(next->next)
next->next->pprev= &next->next;
}
14.从hlist_node节点得到结构体
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
15.遍历hlist链表
a).使用struct hlist_node *pos遍历以struct hlist_head *head开始的链表
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; });pos = pos->next)
b).使用实体数据结构 *tpos和struct hlist_head *pos遍历以struct hlist_head *head开始的链表,并且pos是tpos结构中的member成员
#define hlist_for_each_entry(tpos, pos, head, member)\
for (pos = (head)->first;\
pos && ({ prefetch(pos->next); 1;}) &&\
({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
pos = pos->next)
16.这些都是基本函数，另外还有一些在链表上加上读写锁之类的链表在此不再介绍，其实这些都不是特别难，但是需要使用娴熟。来加快你读懂Linux源代码的速度
