Linux链表操作

95 阅读 0 评论 63 点赞

我是靠谱客的博主怕孤单小懒猪，最近开发中收集的这篇文章主要介绍Linux链表操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Linux里面链表使用非常频繁，下面来看看Linux是怎么玩链表的。下面代码均取自/include/linux/list.h

一 Linux链表定义

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

Linux对链表抽象了一个最小的单位list_head,它只有两个成员：next指向后一个节点，pre指向前一个节点。

二链表操作

1. 链表初始化

把pre和next都指向自身！判断链表是否为空即判断xxx->next = xxx 是否为true。

#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;
}

Linux里面链表的初始化提供了两种方式，1-4行使用宏的方式实现，将3-4行展开实际上就等于：

struct list_head name = {&(name), &(name)}   // 即name->pre = name, name->next = name

6-10行采用内联函数直接赋值的方式。

2. 添加元素

Linux链表是双向链表，我们可以从其头部插入（相当于栈），也可以从尾部插入（相当于队列），也可以从任意位置插入。它实现的时候并不是一下子实现这些参数，而是抽象出一个最基本的操作，然后根据不同的需求传入不同的参数。

基本添加操作：

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

从尾部添加：

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

3. 删除元素

删除就简单了，只需要改变一下指针指向就好。

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	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; //
}

注意10-11行，要处理被删除节点的pre和next。

4. 替换元素

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

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

5. 遍历链表

Linux链表是嵌入数据结构中的，我们要遍历链表，或者访问链表节点中的其他数据，首先要得到节点所在的结构的首地址，在Linux中用了一个比较牛X的宏实现：

/**
 * 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_struct within the struct.
 */
#define list_entry(ptr, type, member) 
	container_of(ptr, type, member)

// container_of
#define container_of(ptr, type, member) ({			
	const typeof(((type *)0)->member) * __mptr = (ptr);	
	(type *)((char *)__mptr - offsetof(type, member)); })
	
//offsetof
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

list_entry宏传入的三个参数：
ptr：表示链表类型指针，也就是member类型的指针，所有对象类型都挂在ptr所在的链表上
type：对象类型
member：member是type中的成员，也就是嵌入该对象结构中的链表

如果已知一个结构的首地址，那么我们很容易根据结构中成员的偏移量访问各个成员。现在的情况是，我们知道了成员的地址和成员以及结构体类型，要反推出结构体首地址，怎么做？很简单，只需要将该成员地址减去成员相对于结构首地址的偏移量即等于结构体首地址，即：

结构首地址 = &成员 - （成员偏移量）

现在再来看上面的宏:

//(type *)0  将0强制转换为该节点类型
//&(((type *)0)->MEMBER) 取结构体成员的地址即为该成员的偏移地址
// 由一个结构成员的偏移地址 = 成员地址 - 结构体首地址  可知：
// 如果该结构首地址本身为0，那么取得的成员地址就是偏移地址
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

// 用链表指针 - 偏移量即可得结构首地址
#define container_of(ptr, type, member) ({			
	const typeof(((type *)0)->member) * __mptr = (ptr);	
	(type *)((char *)__mptr - offsetof(type, member)); })

结构体像下面这样挂在链表上：

访问第一个节点：

#define list_first_entry(ptr, type, member) 
	list_entry((ptr)->next, type, member)

访问指定位置节点：

#define list_for_each(pos, head) 
	for (pos = (head)->next; pos != (head); pos = pos->next)

遍历链表：

// 用n作为中间变量，避免出现segment fault
#define list_for_each_safe(pos, n, head) 
	for (pos = (head)->next, n = pos->next; pos != (head); 
		pos = n, n = pos->next)