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的声明
#defineLIST_HEAD_INIT(name) { &(name), &(name) }



#defineLIST_HEAD(name)

structlist_head name=LIST_HEAD_INIT(name)



#defineINIT_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.插入节点
/添加节点/

staticinlinevoidlist_add(structlist_headnew,structlist_headhead);

staticinlinevoidlist_add_tail(structlist_headnew,structlist_headhead);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的后一个节点

/

staticinlinevoid__list_add(structlist_headnew,

structlist_headprev,

structlist_headnext)

{

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.

/



staticinlinevoidlist_del(structlist_headentry)

{

__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);}

原文链接: https://www.cnblogs.com/westfly/archive/2011/04/08/1977308.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍