linux内核链表分析

链表是内核中使用最多的数据结构之一，最新的内核（2.6.39中）该数据结构定义在中定义

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)  //定义一个链表且用初始化指向自己,静态初始化一个链表

static inline void INIT_LIST_HEAD(struct list_head *list)   //动态的初始化一个链表，和上面的效果相同
{
    list->next = list;
    list->prev = list;
}

#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,

链表是内核中使用最多的数据结构之一，最新的内核（2.6.39中）该数据结构定义在中定义

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)  //定义一个链表且用初始化指向自己,静态初始化一个链表

static inline void INIT_LIST_HEAD(struct list_head *list)   //动态的初始化一个链表，和上面的效果相同
{
    list->next = list;
    list->prev = list;
}

#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next);
#endif

void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    WARN(next->prev != prev,
        "list_add corruption. next->prev should be "
        "prev (%p), but was %p. (next=%p)./n",
        prev, next->prev, next);
    WARN(prev->next != next,
        "list_add corruption. prev->next should be "
        "next (%p), but was %p. (prev=%p)./n",
        next, prev->next, prev);
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
EXPORT_SYMBOL(__list_add);

                  struct list_head *prev,
                  struct list_head *next);
#endif

//下面是定义了 CONFIG_DEBUG_LIST时的函数定义，其作用都是把new链接到prev 和next之间

void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    WARN(next->prev != prev,
        "list_add corruption. next->prev should be "
        "prev (%p), but was %p. (next=%p)./n",
        prev, next->prev, next);
    WARN(prev->next != next,
        "list_add corruption. prev->next should be "
        "next (%p), but was %p. (prev=%p)./n",
        next, prev->next, prev);
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
EXPORT_SYMBOL(__list_add);

//下面这函数对上

链表是内核中使用最多的数据结构之一，最新的内核（2.6.39中）该数据结构定义在中定义

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)  //定义一个链表且用初始化指向自己,静态初始化一个链表

static inline void INIT_LIST_HEAD(struct list_head *list)   //动态的初始化一个链表，和上面的效果相同
{
    list->next = list;
    list->prev = list;
}

#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,

链表是内核中使用最多的数据结构之一，最新的内核（2.6.39中）该数据结构定义在中定义

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)  //定义一个链表且用初始化指向自己,静态初始化一个链表

static inline void INIT_LIST_HEAD(struct list_head *list)   //动态的初始化一个链表，和上面的效果相同
{
    list->next = list;
    list->prev = list;
}

#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next);
#endif

void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    WARN(next->prev != prev,
        "list_add corruption. next->prev should be "
        "prev (%p), but was %p. (next=%p)./n",
        prev, next->prev, next);
    WARN(prev->next != next,
        "list_add corruption. prev->next should be "
        "next (%p), but was %p. (prev=%p)./n",
        next, prev->next, prev);
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
EXPORT_SYMBOL(__list_add);

                  struct list_head *prev,
                  struct list_head *next);
#endif

//下面是定义了 CONFIG_DEBUG_LIST时的函数定义，其作用都是把new链接到prev 和next之间

void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    WARN(next->prev != prev,
        "list_add corruption. next->prev should be "
        "prev (%p), but was %p. (next=%p)./n",
        prev, next->prev, next);
    WARN(prev->next != next,
        "list_add corruption. prev->next should be "
        "next (%p), but was %p. (prev=%p)./n",
        next, prev->next, prev);
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
EXPORT_SYMBOL(__list_add);

//下面函数的封装，用与将new插入head和head->next之间

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

//下面函数的封装，用与将new插入head->prev和head之间

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

//下面的函数的式把prev和next指向的两个链表前后相连

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

//下面函数表达的是把一个链表前指向和后指向向联，这样其本身就在链表之外，因此就被断开链表
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif

//new替换old所在链表中old的位置，但old本身还前后指向还指向以前的位置

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的位置，并使old之心其自身

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

//把entry指向链表节点从所在的链表中断开，且使其前后向指向其自身

static inline void list_del_init(struct list_head *entry)
{
    __list_del_entry(entry);
    INIT_LIST_HEAD(entry);
}

//把list中其自身链表中断开并联入到head所在链表

static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del_entry(list);
    list_add(list, head);
}

//和上面函数相同，只是加入前后位置相反

static inline void list_move_tail(struct list_head *list,
                  struct list_head *head)
{
    __list_del_entry(list);
    list_add_tail(list, head);
}

//判断list是否是以head为起始的链表未节点

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

//判断一个链表是否为空

static inline int list_empty(const struct list_head *head)
{
    return 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);
}

//在链表不为空的情况下，把head的next指向移到head->prev和head之间

static inline void list_rotate_left(struct list_head *head)
{
    struct list_head *first;

    if (!list_empty(head)) {
        first = head->next;
        list_move_tail(first, head);
    }
}

//判断链表是否只有一个节点

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