linux内核的双向链表详解

linxu kernel 的双向链表详解:
目录
1.数据结构
2.定义头结点
3.初始化。
4.添加(add)结点
5.删除(del)结点
6.替换(replace)结点
7.移动(move)结点
8.双向链表的应用

    1.数据结构：
struct list_head{
    struct list_head *next, *prev;
}
    2.定义头结点
2.1
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
2.2
#define LIST_HEAD_INIT(name) { &(name), &(name) }
定义一个头结点，比如：
LIST_HEAD(head) struct list_head head = {&head, &head);
等价于就是：  head.next = &head;
          head.prev = &head;

    3.初始化
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}
其实就是让prev/next指向自身.
    4.添加结点
4.1添加到指定结点后(head->next指向new 作为链表头)
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
最后的结果就是 参数new,head:
    new 添加到 head 和 head->next 中间。

4.2添加到指定结点前(head->prev指向new 作为链表尾)
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}
最后的结果就是 参数new,head:
    new 添加到 head->prev 和 head 中间。

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;
}
最后的结果就是 参数new prev next:
       new 添加到prev  和 next 中间。

    5.删除结点
5.1
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}
5.2
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}
5.3
/********** include/linux/list.h **********/
/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1 ((void *) 0x00100100)
#define LIST_POISON2 ((void *) 0x00200200)
最后的结果就是:entry所指的结点从它所属的链表删除。
极端情况下该链表只有一个结点（假设头结点为head),那么链表情况:
   head->next = entry;
   head->prev = entry;
   entry->next = head;
   entry->prev = head;
调用删除结点（prev = head, next = head):
  next->prev = prev; => head->prev = prev; => head->prev = head;
  prev->next = next; => head->next = next; => head->next = head;
和之前刚初始化一个头结点的一样的状态。
5.4
static inline void list_del_init(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry);
}
删除之后，并重新初始化entry结点。

    6.替换结点
6.1
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;
}
最终的结果就是:new 结点替换了 old结点。
            需要注意的是,old的prev和next是没有改变的。
6.2
static inline void list_replace_init(struct list_head *old,
                    struct list_head *new)
{
    list_replace(old, new);
    INIT_LIST_HEAD(old);
}
和6.1差别的是，并重新初始化old，这样old->next = old / old->prev = old。

    7.移动结点
7.1
static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add(list, head);
}
7.2
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);
}
最后的结果就是:
对于7.1和7.2的区别就是在调用list_add和list_add_tail的区别，这个函数，
前面分析过了。那么就是把参数list从原来位置删除，然后在添加到由参数head
前面(list_add_tail 链表尾)或后面(list_add 链表头)。

    8.双向链表的应用
1-7大概就是双向链表的基本操作，初始化、添加、删除、移动、替换。
当然在/include/linux/list.h不仅仅包含这几个操作，还有判断是否为空、
是否只是一个结点、单链表切割为双链表、双链表合并为单链表等。
8.1
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
向链表在整个kernel中是使用的非常广泛的，经常是内嵌到某一个结构体里面。
container_of是非常常见的，那么这个宏的作用就是通过ptr(struct list *)，
来得到包含该list的结构体地址。
比如:
struct A
{
    ...
    struct list entry;
    ...
};
假设有一个结构体A的实例:tmp。那么知道entry的地址就可以知道tmp所在地址。
container_of(&entry, struct A, entry);
(&entry) - [&(((struct A) *0)->entry)]
           相当于entry在struct A的偏移量,那样减一下就可以得到tmp的地址。
void example(const struct list *entry) //参数entry为tmp的list域的地址
{

    struct *tmp = container_of(entry, struct A, list);
    ...
}
8.2
/**
 * list_first_entry - get the first element from a list
 * @ptr:    the list head to take the element from.
 * @type:    the type of the struct this is embedded in.
 * @member:    the name of the list_struct within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)
得到链表第一个结点内嵌到结构体的地址，由上面的参数英文解释也可知道。
ptr就是list head链表头，ptr->next就是第一个entry的address.
然后调用list_entry，相当于调用container_of...
8.3
/**
 * list_for_each    -    iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:    the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

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

遍历链表结点，然后又由上可知，可由结点得到内嵌到结构体的地址，所有经常
这样使用这个宏：
假设结构体struct A, 链表头A_list;
struct list_head *ptr;
...
list_for_each(ptr, &A_list) {
        struct A *tmp;
        tmp = list_entry(ptr, struct hostap_bss_info, list);
        tmp->xxx = ...;
        tmp->yyy = ...;
        ...