3.4. linux 通用双向循环链表

在linux内核中，有一种通用的的双向循环链表，构成了各种队列的基础。链表的结构定义和相关函数均在 include/linux/list.h 中。

include/linux/types.h 中对 list_head 做出了定义

struct list_head {
    struct list_head *next, *prev;
};

这是链表的元素结构，因为时循环链表，表头和表中节点都是同样的结构。有prev和next两个指针，分别指向前一节点和后一节点。

#define LIST_HEAD_INIT(name)    {&(name), &(name)}

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->prev = list;
    list->next = list;
}

初始化时，链表头的prev和next都是指向自身的。

static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
    new->next = next;
    next->prev = new;
    prev->next = new;
    new->prev = prev;

}

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head-prev, head);
}

双向循环链表的实现，很少有例外的情况，基本都可以用公共的方式来处理。

链表API实现时大致都是分为两层：一层是外部的,如 list_add list_add_tail ,用来消除一些例外情况，调用内部实现； 一层是内部的，函数名前会加双下划线，如 __list_add ,往往都是几个操作公共的部分，或者排除例外后的实现。

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    prev->next = next;
    next->prev = prev;
}

static inline void list_del(struct list_head *head)
{
    __list_del(head->prev, head->next);
}

static inline void list_del_init(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    LIST_INIT_HEAD(entry);
}

list_del是将链表中的节点删除，list_del_init则是将链表中的节点删除后再次把节点指针初始化。

static inline void list_replace(struct list_head *old, struct list_head *new)
{
    new->next = old->next;
    new->next->prev = new;
    new->prev = old->prev;
    new->prev->next = new;
}


static inline void list_replace_init(struct list_head *old, struct list_head *new)
{
    list_replace(old, new);
    INIT_LIST_HEAD(old);
}

list_replace 将链表中的一个节点old，替换为另一个节点new。

static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add(list, 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);
}

list_move 的作用是将list节点从原链表中删除，并加入新的链表head中。

static inline int list_is_last(struct list_head *list, struct list_head *head)
{
    return (list->next == head);
}

list_is_last 判断list是否处于head链表的尾部。

static inline int list_empty(struct list_head *head)
{
    rerurn (head->next == head);
}

static inline int list_empty_careful(const struct list_head *head)
{
    struct list_head *next = head->next;
    return (next == head) && (next == head->prev);
}

list_empty 判断head链表是否为空

static inline int list_is_singular(const list_head *head)
{
    return !list_empty(head) && (head->next == head->prev);
}

list_is_singular 判断head是否只有一个节点，即除链表头head外是否只有一个节点。

static inline void __list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry)
{
    entry->next->prev = head->prev;
    head->prev->next = entry->next;
    list->next = head;
    head->prev = list;
    entry->next = list;
    list->prev = entry;
}

static line void lis_cut_position(struct list_head *list, struct list_head *head, struct list_head entry)
{
    if(list_entry(head))
        return;
    if(list_is_singular(head) && (list->next != entry && head != entry))
        return;
    if(entry == head)
        INIT_LIST_HEAD(list);
    else
        __list_cut_position(list, head, entry);
}

list_cut_position 用于把head链表分为两部分，从head->next 一直到entry被从head链表中删除，加入新的链表list。 新的链表应该是空的，或者原来的节点可以被忽略掉。

static inline void __list_splice(struct list_head *list, struct list_head *prev, struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;

    prev->next = first;
    first->prev = prev;

    last->next = next;
    next->prev = last;
}

static inline void list_splice(struct list_head *list, struct list_head *head)
{
    if(!list_empty(list))
        __list_splice(list, head, head->next);
}

static inline void list_splice_tail(struct list_head *list, struct list_head *head)
{
    if(!list_emptu=y(list))
        __list_splice(list, head->prev, head)；
}

list_splict 的功能和list_cut_posiotion相反，它合并两个链表。list_splice把list链表中的节点加入到head链表中。

list_splict是把原来list链表中的节点全部插入到head链表的头部，list_splice_tail则是把原来list链表中的节点全部加到head链表的尾部。

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

list_entry 主要用于从list节点查找其内嵌在的结构。比如定义了一个结构struct A{struct list_head list;},如果知道结构中链表的地址ptrlist， 就可以从ptrlist进而获取整个结构的指针，struct A *Ptr = list_entry(ptrlist, struct A, list);

这种地址翻译的技巧是linux的拿手好戏，container_of随处可见，只是链表节点多被封装在更复杂的结构中，使用专门的list_entry定义也是对了使用方便

#define __list_for_each(pos,head) \
    for(pos = (head)->next; pos != head; pos = pos->next)

list_for_each 遍历链表中的每一个节点。

#define list_for_each_prev(pos,head) \
    for(pos = (head)->prev; pos != head; pos = pos->prev)

list_for_each_prev 遍历链表中的每一个节点，不同的是它是逆序的.

#define list_for_each_safe(pos, n, head) \
    for(pos = (head)->next, n = pos->next;pos != head; pos = n,n = pos->next)

list_for_each_safe 也是链表顺序遍历，只是它更加安全，即使在遍历过程中喔咕，当前节点从链表中删除，也不会影响链表的遍历。参数中需要加一个暂存的链表节点指针n

#define list_for_each_entry(pos, head, member) \
    for(pos = list_entry(head->next, typeof(*pos), member);
        &pos->member != head; \
        pos = list_entry(pos->memer.prev, typeof(*pos), member)
        )

list_for_each_entry 不是遍历链表节点，而是遍历链表节点所嵌套进的结list_for_each_entry 不是遍历链表节点，而是遍历链表节点所嵌套进的结构.