linux通用链表

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

一、链表结构和初始化

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链表，过段时间再去巩固。

本文出自 “cizyzhang” 博客，请务必保留此出处http://cizyzhang.blog.51cto.com/1529108/1380381

linux通用链表,古老的榕树,5-wow.com