C语言关于Linux内核纯链表实现的简单讲解_c语言 创建内核链表

C语言关于Linux内核纯链表实现的简单讲解

      在操作系统内广泛使用到各种类型的链表，链表是作为操作系统非常重要的数据结构之一，可以说是操作系统的基石。而在Linux内核中，存在着专门用于链表实现的文件，可供开发者直接调取使用，并且效率达到了最优化，极大的方便了系统开发人员。

      废话少说，首先我们来看一下这一段代码

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

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12

这里主要包含一个结构体定义，两个宏，一个函数。

      结构体就是我们的链表节点（采用双链表），或许有人会疑问，为什么只有指针而没有有效数据？这就是为什么我们把它叫做纯链表的原因了。整个文件都是为链表使用者服务的。
具体使用方法：

• 1，包含相应的头文件
• 2，按需要制作自己的结构体，并在结构体内声明一个struct list_head类型的变量（它将代替链表的两个指针变量）。结合所包含的文件函数，它将完成链表的所有基本操作。（NOTE：普通链表的使用是链表将数据包住，而在这里是数据将链表包住）

      代码中两个宏共同完成了一个节点的初始化，&(name)代表的是自己的地址，因此两个指针变量初始化指向自己。
而INIT_LIST_HEAD函数完成的同样也是节点的初始化，使用内联函数有效提高函数运行速度。

接下来我们看一下插入函数是如何实现的。

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
         		struct list_head *prev,
         		struct list_head *next);
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

      从注释我们可以很好的理解，该函数仅用于向两个已知函数内插入节点。因此它不能够实现末尾插（会产生段错误）。该函数采用了三个参数，要插入的节点new，插入位置前一个节点prev，和后一个节点next。使函数的实现变得更加简单，也不用再考虑节点各指针转移指向的顺序。
NOTE：#ifndef CONFIG_DEBUG_LIST很显然这是一个调试判断，第一阶段调试将执行，后期再次编译即只需要执行#else口的声明即可。

      该函数被后面函数多次调用，以实现不同场景的不同需求。如堆载的辅助实现，队列的辅助实现，都是链表要实现的点。

/**
 * 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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

      通过注释我们可以很容易知道它要干什么，将它们与上面的__list_add函数做对比，以及在真实需求上做分析，可以发现其实现之精妙，相辅相成，并且效率达到最高。

关于链表节点的删除函数也在其中实现出来了。

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

/**
 * 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.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
 entry->next = LIST_POISON1;
 entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

      简单通过两个函数实现，相信会有人疑问这么简单的实现为什么非要写出两个函数？
      首先是因为其中某个函数可被多函数调用使用，保留中间环节使程序更加清晰明了。
      关于 LIST_POISON1的值我们在这里不做讨论，你只需要把它假设是NULL即可，至于为什么这么做的理由可自行查阅资料。

程序接下来是一个替换函数。

/**
 * 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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

将链表中节点old替换成new，同时将old使用函数
      INIT_LIST_HEAD重新初始化以备它用。各节点指向步骤类似于双链表的操作过程。

      代码继续往下面看是一个删除节点并初始化这个删除的节点（可重复利用）。

/**
 * 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);
}
1
2
3
4
5
6
7
8

      节点能够在链表中灵活的移动也是列表操作的一个重点，下面的代码就是为解决这个实现的。

/**
 * 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 - 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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

      这两个函数主要还是通过对前面函数的调用实现的，进一步体现了其封装性的完好。
      它们都是用于实现将链表中一节点搬移到另一个节点周围（一个前一个后），实现过程是先从链表中删除list节点，然后将删除的list节点加入到链表中head节点前面或后面。

      对于该函数的其它内容都是用类似的方法去分析即可，通过对它们的分析我们的C语言能力能够有所提高，因为写Linux内核的人必然是很厉害的高手，学习他们的编程习惯自然可以使自己受益良多。

若读者还有兴趣阅读这部分代码，可在我的博客首页下载该文件，或者在下方留言我将发入你的邮箱。