linux通用链表

xian123

　　在大学学习《数据结构》时，链表是必须要精通的。那个时候什么线性结构的数据都用链表来玩过，还有十字链表等。但看了内核的通用链表才感觉什么叫实用。

　　一、链表结构和初始化
struct list_head {
struct list_head *next, *prev;  // 仅仅两个指针成员，其他数据自行定义
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name) //name->next = name->prev = name
/* 初始化节点 */
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)　　二、节点添加
/* new指向需要插入的节点
* 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和next连接
new->prev = prev;
prev->next = new;   // 完成new和prev连接
}
/* 头插法：插入链表head的第一个节点，即head->next位置 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/* 尾插法：插入链表head的尾部，即head->prev位置 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}　　该通用链表还有一种添加节点方法，就是在上述每个接口名后加_rcu，如

static inline void __list_add_rcu(struct list_head * new,
struct list_head * prev, struct list_head * next)
{
new->next = next;
new->prev = prev;
smp_wmb();
next->prev = new;
prev->next = new;
}　　与前面比较，只是多余smp_wmb()语句，该语句定义为空，为了防止编译器或者cpu优化代码的执行顺序，以确保在它之前的两行代码执行完成后再执行后面两行。
/* empty define to make this work in userspace -HW */
#define smp_wmb()　　三、节点删除（仅仅从链表中删除，内存等资源不释放）
/* prev:删除节点位置的前一个节点
* next:删除节点位置的后一个节点
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
// 其实被删除的节点的prev和next还是指向链表中的前后节点
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1; // LIST_POISON1=((void *) 0x00100100)
entry->prev = LIST_POISON2; // LIST_POISON2=((void *) 0x00200200)
// 这两个指针并没什么特殊，他们指向一般不可用的内存，再被引用时就会段错误。可以帮助确认该节点没有被初始化。
}
/* 删除节点并初始化节点 */
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}　　四、移动节点

/* 将节点list移动到链表首部 */
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next); // 删除节点
list_add(list, head);  // 添加节点
}
/* 将节点list移动到链表尾部 */
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);
}　　五、判断链表是否空
/* 判断链表头结点的next是否指向自己，即没有其他节点 */
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
/* 在多核情况下使用，head->prev = head->next 能够确保链表为空 */
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}　　六、连接两个链表

/* 将list链表插入到head节点后 */
static inline void __list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next; // 指向list第一个节点
struct list_head *last = list->prev;  // 指向list最后一个节点
struct list_head *at = head->next;   // 指向head后一个节点
first->prev = head;
head->next = first;  // 插入list链表
last->next = at;
at->prev = last;   // head后原链表连接到list后
}
/**
* list：需要插入的链表
* head: 链表被插入位置
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
/* 将list链表插入head后，并初始化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);
}
}　　七、获取用户定义的数据结构
　　这里使用C语言的一个技巧。将0地址强制转换成TYPE类型（即包含了链表元素的结构体），然后从0地址开始计算，就能很容易得到链表元素在结构体中偏移。

　　注意：这里只是读取从0地址开始的数据，并没有进行赋值等写操作，所以不会使程序崩溃。
/* 计算TYPE结构体中MEMBER的偏移 */
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
/**
* ptr:    指向结构体中链表节点的指针
* type:   用户定义的结构体
* member: 链表节点在结构体中的名字
* 第一行获取ptr指针的地址，第二行减去偏移就得到结构体的地址
*/
#define container_of(ptr, type, member) ({          \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)　　    举个例子
struct test{
int a;
int b;
struct list_head node;
}
/* 已知node地址，获取struct test的地址 */
struct test tmp;
struct test *p = list_entry(&tmp.node, typeof(tmp), node)　　八、遍历链表
/* 只是简单的遍历head链表，不要做增加删除操作，很容易出错 */
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)
/* 反向遍历head链表，与上面类似，只是顺序相反 */
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev ; pos != (head); \
pos = pos->prev)
/* 安全模式下遍历链表，可以做增加、删除操作（对pos操作，n不要动） */
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/**
* 与前面不同，这里需要用到用户自定义的结构体。遍历时可以访问其他struct成员，但不要做添加删除操作
* pos:    指向自定义的struct
* head:   链表头结点
* member: 自定义的struct中链表元素名称
*/
#define list_for_each_entry(pos, head, member)          \
for (pos = list_entry((head)->next, typeof(*pos), member);   \
&pos->member != (head);                 \
pos = list_entry(pos->member.next, typeof(*pos), member))
/* 与前一个遍历顺序相反，其他类似 */
#define list_for_each_entry_reverse(pos, head, member)          \
for (pos = list_entry((head)->prev, typeof(*pos), member);           \
&pos->member != (head);                     \
pos = list_entry(pos->member.prev, typeof(*pos), member))
/* 为list_for_each_entry_continue所用，如果pos有值则不变，否则从链表头虚拟一个pos指针 */
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
/* 从pos->member下一节点开始遍历链表 */
#define list_for_each_entry_continue(pos, head, member)         \
for (pos = list_entry(pos->member.next, typeof(*pos), member);           \
&pos->member != (head);                 \
pos = list_entry(pos->member.next, typeof(*pos), member))
/* 与list_for_each_entry类似，区别是可以做添加删除操作（对pos操作，n不动） */
#define list_for_each_entry_safe(pos, n, head, member)          \
for (pos = list_entry((head)->next, typeof(*pos), member),   \
n = list_entry(pos->member.next, typeof(*pos), member);  \
&pos->member != (head);                     \
pos = n, n = list_entry(n->member.next, typeof(*n), member))　　算是对链表的一次复习，linux也有通用hash链表，明天抽时间再去巩固。