linux中的list源码分析

网上关于list的源码分析很多，这里只是学习做比较。

list的数据结构定义

/* *双链表 */ 
struct list_head { 
　　struct list_head * next, ** prev; 
};

或许我们比较习惯如下的形式

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

前文已经说明，这与传统的经典定义有差异，只有链接指针，而无数据节点。这样做是为了带来数据定义的通用性。在C++中，使用模板技术来实现，而C中并没有相关的技术，那么如何访问到节点上的数据呢，成为面临的挑战之一。

1.声明

关于的list的声明

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

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

#define INIT_LIST_HEAD(ptr) do{\
(ptr) -> next = (ptr);(ptr) -> prev = (ptr);\
} while ( 0 )

LIST_HEAD_INIT(name)将 name 的地址直接分别赋值给 next 和 prev ，那么它们事实上都指向自己，也形成一个空链表（此处存疑）。

宏LIST_HEAD(name) ，它本质是一个定义并初始化变量。

INIT_LIST_HEAD(ptr)是用来在运行时进行初始化的，特别是list安全删除的时候。

注释，在最新版2.6的linux中，该宏已经修改为内联函数，这样做类型是安全的吧。代码如下

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

从运行时初始化来看，linux下的list_head是个循环双链表，这从判断是否为空可以验证。代码如下

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}

2.插入节点

/* 添加节点 */
static inline void list_add( struct list_head * new , struct list_head * head);
static inline void list_add_tail( struct list_head * new , struct list_head * head);

list_head是个循环双链表，所以list支持在节点前和节点后插入新的节点。实际上， list_add 和list_add_tail都是转调函数__list_add来实现的，只是传递的参数不一样。

前者调用参数为__list_add(new, head, head->next);
后者调用参数为__list_add(new, head->prev, head);

__list_add的实现代码如下

/* *
new--待插入的节点
prev--插入后new的前一个节点
next--插入后new的后一个节点
*/
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 ;
}

注意：Linux下第一个参数为待插入的节点，有C++思维的人比较习惯第二个参数为待插入节点。同时要要注意的是第二个参数不能为空。同时，参数new在C++中为关键字，无法编译通过的。

View Code

/**
 * 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.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}


/**
 * 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);
}

有热心的同学画了示意图，如下

2.删除元素

由于数据域与指针域分离，与传统意义上的删除——释放节点空间有区别，此处只是将节点从链表中摘取下来。

/* ***删除节点自身*** */ 
static inline void list_del( struct list_head * entry); 
static inline void list_del_init(struct list_head *entry)

list_del的实现为

/* *
* 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.
*/

static inline void list_del( struct list_head * entry)
{
　　__list_del(entry -> prev, entry -> next);
　　entry -> next = LIST_POISON1;
　　entry -> prev = LIST_POISON2;

}

list_del 只是简单的调用__list_del 函数。然后将 prev 、 next 指针分别被设为 LIST_POSITION2 和 LIST_POSITION1 两个特殊值，这样设置是为了保证不在链表中的节点项不可访问--对 LIST_POSITION1 和 LIST_POSITION2 的访问都将引起页故障（具体如何处理还有待看资料）。请注意这个函数的后两句话，它属于不安全的删除。

POSITION宏定义

/* 

* 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)

如果要安全删除，用到list_del_init，其实现为

/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry);
}

多了一个初始化链表节点的过程。

__list_del的实现也为简单，分别让 entry 节点的前后两个结点（ prev 和 next ）"越级"指向彼此即可。具体实现为

/*
 * 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;
}

3.替换元素

/**替换元素*/
static inline void list_replace( struct list_head *old,
                　　　　　　　　　　struct list_head *new)
static inline void list_replace_init( struct list_head *old,
                    　　　　　　　　　　  struct list_head *new)

list_replace_init 是安全的调用，比list_replace多了一个运行时初始化节点的功能。

list_replace的代码实现如下，请自行画图理解

/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
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;
}

5.移动元素

/**移动元素*/
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,struct list_head *head)

理解了删除和增加结点，那么将一个节点移动到链表中另一个位置，其实就很清晰了。list_move函数最终调用的是__list_add(list,head,head->next)，实现将list移动到头结点之后；而list_move_tail函数最终调用__list_add_tail(list,head->prev,head)，实现将list节点移动到链表末尾。

list_move

/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */
static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add(list, head);
}

list_move_tail

/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */
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);
}