Linux内核链表之list_head_linux list_head

Linux内核链表之双链表

（include/linux/list.h）

 

1、定义以及初始化 

include/linux/type.h定义的结构体

struct list_head {

struct list_head *next, *prev;

};

 

2、初始化

初始化①

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

 

#define LIST_HEAD(name) \

struct list_head name = LIST_HEAD_INIT(name)

 

解析：struct list_head name = { &(name), &(name) } 其实就是结构体的赋值

初始化②

static inline void INIT_LIST_HEAD(struct list_head *list)

{

list->next = list;

list->prev = list;

}

 

初始化的结果都是让结构体的前后指针指向自身的地址

 

3、链表的插入

3.1插入函数实现

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;

}

 

解析：

①static和inline的作用：

static修饰函数，表明这个函数属于静态函数，用来限制函数的作用域的，表名该函数只能在本文件内使用。

inline修饰函数：为了解决一些频繁调用的小函数大量消耗栈空间或是叫栈内存的问题，特别的引入了inline修饰符，表示为内联函数。

②参数：new 插入的节点，prev、next插入点前后相邻的链表

插入前：

 

插入后:

 

现在再看就很好理解了

next->prev = new;

new->next = next;

new->prev = prev;

prev->next = new;

 

3.2函数的封装

头插：

 @new: new entry to be added

 @head: list head to add it after

static inline void list_add(struct list_head *new, struct list_head *head)

{

__list_add(new, head, head->next);

}

尾插：

 @new: new entry to be added

 @head: list head to add it before

static inline void list_add_tail(struct list_head *new, struct list_head *head)

{

__list_add(new, head->prev, head);

}

4、链表的删除

有点复杂

#ifdef CONFIG_ILLEGAL_POINTER_VALUE

# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)

#else

# define POISON_POINTER_DELTA 0

#endif

 

#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)

#define LIST_POISON2  ((void *) 0x200 + POISON_POINTER_DELTA)

 

static inline void __list_del(struct list_head * prev, struct list_head * next)

{

next->prev = prev;

WRITE_ONCE(prev->next, next);

}

 

static inline void list_del(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

entry->next = LIST_POISON1;

entry->prev = LIST_POISON2;

}

主要关键点在于：

entry->next = LIST_POISON1;

entry->prev = LIST_POISON2;

为什么不直接赋值为NULL呢？带研究。。。

 

5、链表的遍历

/**

 * list_for_each - iterate over a list

 * @pos: the &struct list_head to use as a loop cursor. //遍历到的节点

 * @head: the head for your list.   //head节点

 */

#define list_for_each(pos, head) \

for (pos = (head)->next; pos != (head); pos = pos->next)

 

 

/**

 * list_for_each_safe - iterate over a list safe against removal of list entry

 * @pos: the &struct list_head to use as a loop cursor.//遍历到的节点

 * @n: another &struct list_head to use as temporary storage //n作为存储节点

 * @head: the head for your list.   //head

 */

#define list_for_each_safe(pos, n, head) \

for (pos = (head)->next, n = pos->next; pos != (head); \

pos = n, n = pos->next)

 

由上面两个对比来看，list_for_each_safe()函数比list_for_each()多了一个中间变量n，带safe的函数主要是用于节点删除的时候导致的可能发生的错误。

list_for_each()：list_del(pos)将pos的前后指针指向undefined state，导致kernel panic，list_del_init(pos)将pos前后指针指向自身，导致死循环。

list_for_each_safe()：首先将pos的后指针缓存到n，处理一个流程后再赋回pos，避免了这种情况发生。

6、其他常用函数

/**

 * list_entry - get the struct for this entry

 * @ptr: the &struct list_head pointer.   //成员变量的地址

 * @type: the type of the struct this is embedded in. //结构体类型

 * @member: the name of the list_head within the struct.//成员变量名

 */

#define list_entry(ptr, type, member) \

container_of(ptr, type, member)

 

 

/**

 * container_of - cast a member of a structure out to the containing structure

 * @ptr:        the pointer to the member.    //成员变量的地址

 * @type:       the type of the container struct this is embedded in. //结构体类型

 * @member:     the name of the member within the struct.//成员变量名

 */

#define container_of(ptr, type, member) ({                      \

const typeof( ((type *)0)->member ) *__mptr = (ptr);    \

(type *)( (char *)__mptr - offsetof(type,member) );})

 

解析:看着头大自己理解吧，看下使用吧

设有如下结构体定义：
typedef struct test
{
     type1 member;
}type;


定义变量：

type a;
type * b;
type1 * ptr;
执行：
   ptr=&(a.member);
   b=list_entry(ptr,type,member);
则可使b指向a，得到了a的地址。