五、内核链表

1、使用方法

链表结构体

1
2
3
4
5
6
7
8
typedef int DataType;

//双向循环链表节点结构体声明
typedef struct Node
{
	DataType data;
	struct list_head list;
}linknode;

1、初始化链表

1
2
3
4
5
6
7
8
9
10
// 初始化链表
linknode *init_list(void)
{
	linknode *head = malloc(sizeof(linknode));
	if(head == NULL)
		return NULL;
	
	INIT_LIST_HEAD(&head->list);
	return head;
}

2、创建节点

1
2
3
4
5
6
7
8
9
10
11
12
// 创建节点
linknode *create_node(DataType data)
{
	linknode *new = malloc(sizeof(linknode));
	if(new == NULL)
		return NULL;
	
	INIT_LIST_HEAD(&new->list);
	new->data = data;
	
	return new;	
}

3、遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 遍历
void display_list(linknode *head)
{
	struct list_head *pos = NULL;
	linknode *tmp = NULL;
	
	list_for_each(pos, &head->list)
	{
		tmp = list_entry(pos, linknode, list);
		printf("%d->", tmp->data);
	}
	
	printf("\n");
}

4、添加节点

4.1头插

1
2
3
4
5
// 将新节点new插入到以head为首的链表的开头
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

4.2尾插

1
2
3
4
5
// 将新节点new插入到以head为首的链表的末尾
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

5、删除节点

5.1 list_for_each_safe版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 删除节点
void remove_node(int data, linknode *head)
{
	struct list_head *pos = NULL;
	struct list_head *n = NULL;
	linknode *tmp = NULL;
	
	list_for_each_safe(pos, n, &head->list)
	{
		tmp = list_entry(pos, linknode, list);
		if(tmp->data == data)
		{
			list_del(pos);
			free(tmp);
		}
	}
	return ;
}

5.2 list_for_each_entry_safe版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 删除节点
void remove_node(int data, linknode *head)
{
	linknode *pos = NULL;
	linknode *n = NULL;
	
	list_for_each_entry_safe(pos, n, &head->list, list)
	{
		if(pos->data == data)
		{
			list_del(&pos->list);
			free(pos);
		}
	}
	
	return ;
}

6、更新节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 更新节点
void updata_node(DataType old_data, DataType new_data, linknode *head)
{
	if(list_empty(&head->list))
		return;

	linknode *pos = NULL;
	linknode *n = NULL;
	
	list_for_each_entry_safe(pos, n, &head->list, list)
	{
		if(pos->data == old_data)
		{
			pos->data = new_data;
		}
	}
}

7、查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 查找节点(根据数据查找)
linknode *find_node(DataType data, linknode *head)
{
	if(list_empty(&head->list))
		return NULL;

	linknode *pos = NULL;
	linknode *n = NULL;
	
	list_for_each_entry_safe(pos, n, &head->list, list)
	{
		if(pos->data == data)
		{
			return pos;
		}
	}
	
	return NULL;
}

2、kernel_list.h

内核小结构体

1
2
3
4
// 内核标准链表：小结构体
struct list_head {
	struct list_head *next, *prev;
};

1、初始化小结构体

1
2
3
4
// 初始化小结构体，让其自己形成一个双向循环
#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

2、头插

1
2
3
4
5
// 将新节点new插入到以head为首的链表的开头
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

3、尾插

1
2
3
4
5
// 将新节点new插入到以head为首的链表的末尾
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

4、删除节点

1
2
3
4
5
6
7
// 将entry指向的节点，从链表中剔除出去
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = (void *) 0;
	entry->prev = (void *) 0;
}

5、判断是否为空

1
2
3
4
5
//判断链表是否为空
static inline int list_empty(struct list_head *head)
{
	return head->next == head;
}

6、小结构体指针转大结构体

1
2
3
4
5
6
// 小结构体指针ptr转换成大结构体指针p: p = list_entry(ptr, type, member)
//ptr:小结构体指针
//type:大结构体类型
//member:小结构体在大结构体的名字
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

7、向后遍历（遍历过程中，不可以将节点删除）

1
2
3
4
5
6
7
8
9
10
/**
* list_for_each    -    iterate over a list
* @pos:    the &struct list_head to use as a loop counter.
* @head:    the head for your list.
*/

// 从头开始往后遍历链表（遍历过程中，不可以将节点删除）
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)

8、向前遍历

1
2
3
4
5
6
7
8
9
10
/**
* list_for_each_prev    -    iterate over a list backwards
* @pos:    the &struct list_head to use as a loop counter.
* @head:    the head for your list.
*/

// 从尾开始往前遍历链表
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); \
pos = pos->prev)

9、从头开始往后遍历链表（遍历过程中，可以将节点删除）

9.1删除节点安全版本（手动转换）

1
2
3
4
5
6
7
8
9
10
11
/**
* list_for_each_safe    -    iterate over a list safe against removal of list entry
* @pos:    the &struct list_head to use as a loop counter.
* @n:        another &struct list_head to use as temporary storage
* @head:    the head for your list.
*/

// 从头开始往后遍历链表（遍历过程中，可以将节点删除）
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)

9.2删除节点安全版本（自动转换）

1
2
3
4
5
6
7
8
9
10
11
12
/**
* list_for_each_entry_safe – iterate over list of given type safe against removal of list entry
* @pos:    the type * to use as a loop counter.
* @n:        another type * to use as temporary storage
* @head:    the head for your list.
* @member:    the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member)            \
for (pos = list_entry((head)->next, typeof(*pos), member),    \
n = list_entry(pos->member.next, typeof(*pos), member);    \
&pos->member != (head);                     \
pos = n, n = list_entry(n->member.next, typeof(*n), member))