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

一、链表结构和初始化

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链表，明天抽时间再去巩固。