深度剖析Linux内核链表

—

Linux内核链表详解

Linux内核链表是Linux内核最经典的数据结构之一，Linux内核链表最大的优点就是节省内存，对链表的各项操作较快，实现思路耳目一新，而且在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)

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

INIT_LIST_HEAD函数prev指针和next指针指向链表头结点。LIST_HEAD_INIT宏初始化链表头结点next指针和prev指针保存头结点地址，实际上和INI_LIST_HEAD函数初始化效果一样，LIST_HEAD宏就是链表结点的完整初始化。我们以实际代码为例。

struct list_head list;
LIST_HEAD(list); //list = {&list, &list}

内核链表插入结点

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
#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

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

我们作图解释会更容易理解内核链表插入操作。
直接看代码我们即可知道内核链表实际上采用的是尾插法，并且有一个头结点。内核链表插入结点前如图所示：

结合list_add_tail函数分析可知，假设链表list插入结点node，则next=list->next，prev=list;再调用__list_add则可将新结点插入到链表里面。

内核链表删除结点

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
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(struct list_head *entry);
#endif

直接分析代码可知，删除结点实际上就是将目标结点后面一个结点的前向指针指向目标结点的前向结点，目标结点的前向结点的后向指针指向目标结点的后向结点，这样就可以把目标结点分离出来了。

往期推荐

您现在的位置是：嵌入式系统与单片机 > 技术阅读 > 深度剖析Linux内核链表