c语言内核链表入门教程

Myth丶恋晨 2022-11-27 10:15 69阅读 0赞

##### 最近感觉内核链表真的很实用，而且内核链表的设计真的很好还经得起系统的运行，但是！毕竟没有十全十美地东西，内核链表也存在着缺陷，在一些特殊地方可能没有设计地很到位,这个就要使用者看自己地代码是否适用内核链表了，有时候可能要自己拿里面链表的代码出来修改一下用 #####

*  内核链表其实也是双向链表(有且仅有一个前驱指针和后继指针)，只不过是一种特殊地双向链表  
      
    
 *  它地指针域和数据域分开，指针域用单独地一个结构体存储  
      
    
 *  然后一个大的结构体存放的是要存放的数据和存放指针域的机构体  
      
    
 *  使用内核链表的话，存放数据域和指针域结构体的大结构体需要自己定义  
      
    
 *  内核链表中的所有操作都是针对存放指针域的结构体的操作

**这是我在Linux官网下载的内核中内核链表所在的位置：**

> linux-5.6.6/include/linux/list.h

[这是下载内核链表的地址https://mirrors.edge.kernel.org/pub/linux/kernel/][https_mirrors.edge.kernel.org_pub_linux_kernel]

（注意！下载要下载**后缀**的**gz**或者**xz**的）

#### 以下是链表中对指针域的结构体的定义 ####

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rha2FzaGk3Nw_size_16_color_FFFFFF_t_70_pic_center]

*  其中 struct list\_head \*next;是用于存放下一个节点的指针域结构体的地址  
      
    
 *  struct list\_head \*prev;是用于存放上一个节点的指针域结构体的地址

#### 我们定义一个存放数据域和指针域的结构体 ####

struct list_head 
    	{ 
    		int data;
    		struct list_head *ker_list_node;
    	};

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rha2FzaGk3Nw_size_16_color_FFFFFF_t_70_pic_center 1]

*  其中head为头节点，假设 它存放整个数据域和指针域的地址为0x1000，其中存放指针域的地址为0x1004；
 *  node1 的存放整个数据域和指针域的地址 假设 为0x2000，其中存放指针域的地址为0x2004；
 *  node2 存放整个数据域和指针域的地址 假设 为0x3000，其中存放指针域的地址为0x3004；

> 1.  图中的head节点中一共存放了一个data数据和一个指针域结构体(绿色部分代表)struct list\_head,指针域里面包括了一个\*prev 和 \*next指针
> 2.  如果head节点需要与下一个节点链接时，就要head里面的struct list\_head结构体的*next就需要存放node1的指针域的地址0x2004,然后node1的*prev也需要存放head的里面struct list\_head的地址，最后head的指针域struct list\_head的\*prev就需要存放node1里面struct list\_head地址(可能这里会有点绕，需要慢慢去理解）

## 下面是一些内核链表中常用的一些函数 ##

注：其中函数里面的static inline是指静态的内联函数(在编译时展开函数)

##### 1. INIT\_LIST\_HEAD(ptr) #####

函数作用：初始化一个指针域结构体里面的指针  
形参所代表意义：

*  ptr：要初始化的节点指针域结构体（小结构体）的地址

###### 内核链表中的函数原型： ######

#define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0)

> 在内核链表中其实是一个宏定义，在编译的时候将会替换成宏定义里面的代码，其实就是它的前驱指针和后继指针都存放自己的地址（也可以理解为自己指向自己）

##### 2.void \_\_list\_add(struct list\_head \*new,struct list\_head \*prev,struct list\_head \*next) #####

函数作用：把一个新节点插入到链表  
形参所代表的意义：

*  struct list\_head \*new:要插入的新节点
 *  struct list\_head \*prev：要插入新节点位置的前一个节点
 *  struct list\_head \*next：要插入节点位置的后一个节点

###### 内核链表中的函数原型： ######

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

> 传进来的参数有：插入节点位置的前一个节点和后一个节点，一个新节点；  
> 1.先把后一个节点的前驱指针*prev指向（存放）新节点的地址  
> 2.把新节点的后继指针*next指向（存放）插入位置后一个节点next的地址  
> 3.新节点的前一个指向（存放）插入位置前一个节点的地址  
> 4.要插入位置前一个节点prev的后继指针\*next指向（存放）新节点的地址

##### 3.void list\_add(struct list\_head \*new, struct list\_head \*head) #####

函数作用：把新节点插入到head为头节点的链表的前面

形参所代表的意义：

*  struct list\_head \*new：所需要插入的新节点
 *  struct list\_head \*head：需要插入新节点的链表的头节点

###### 内核链表中的函数原型： ######

static inline void list_add(struct list_head *new, struct list_head *head)
    { 
    	__list_add(new, head, head->next);
    }
    //其中调用的是下面这个函数
    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;  
    }

![内核链表的插入][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rha2FzaGk3Nw_size_16_color_FFFFFF_t_70_pic_center 2]

> 这个函数在内核链表中其实就是调用了void \_\_list\_add(struct list\_head \*new,struct list\_head \*prev,struct list\_head \*next)这个函数，通过把新节点、头节点、头节点的下一个传进来，执行的步骤可以 画图理解一下，其实就是把原来的两根线断掉，然后把新节点妥善放进来

##### 4.void list\_add\_tail(struct list\_head \*new, struct list\_head \*head) #####

函数作用：把节点插入到链表的末尾

###### 内核链表中的函数原型： ######

static inline void list_add_tail(struct list_head *new, struct list_head *head)
    { 
    	__list_add(new, head->prev, head);
    }
    
    //通过调用void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next)实现尾插
    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;  
    }

> 通过传递新节点，链表最后一个节点(头节点的前一个)，和头节点；然后把头节点最后一个节点(头节点的前一个)当成要插入位置的前一个，把头节点当成要插入节点位置的下一个节点

##### 5.void \_\_list\_del(struct list\_head \*prev, struct list\_head \*next) #####

函数作用：把链表中的两个节点相连起来，用于链表删除某一结点，跳过要删除的节点，然后两节点相连  
形参代表的意义：

*  struct list\_head \*prev：要连接的前一个节点
 *  struct list\_head \*next：要连接的后一个节点

###### 链表中的函数原型： ######

static inline void __list_del(struct list_head *prev, struct list_head *next)
    { 
    	next->prev = prev;
    	prev->next = next;
    }

> 就是把next节点的前一个指向prev（next的prev指针用于存放prev的指针域结构体的地址）；prev节点的next指针指向next节点(把prev节点的next指针存放了next节点中指针域结构体的地址)

##### 6.void list\_del(struct list\_head \*entry) #####

函数作用：把链表中的某一结点剔除出去，但是！！没有释放掉  
形参代表的意义：

*  struct list\_head \*entry：链表中要剔除出去的节点

###### 内核链表中的函数原型： ######

static inline void list_del(struct list_head *entry) 
    { 
    	__list_del(entry->prev, entry->next);
    	entry->next = (void *) 0;//NULL
    	entry->prev = (void *) 0;//NULL
    }

> 这里首先调用了\_\_list\_del()这个函数，把entry这个节点先删除掉，然后把这个节点里面的两个指针置为0（NULL）

##### 7.void list\_move(struct list\_head \*list,struct list\_head \*head) #####

函数作用：把链表的某一结点移动到以head为头节点的链表头中  
形参代表的意义：

*  struct list\_head \*list：要移动到链表头的节点
 *  struct list\_head \*head：以head为头节点的链表

###### 内核链表中的函数原型： ######

static inline void list_move(struct list_head *list,
    							struct list_head *head)
    { 
    	__list_del(list->prev, list->next);
    	list_add(list, head);
    }

> 通过调用\_\_list\_del(list->prev, list->next);这个函数先把这个节从链表中删除出去，然后调用了头插的函数list\_add(list, head);最终把节点移动到以head为头节点的链表中去

##### 8.int list\_empty(struct list\_head \*head) #####

函数作用：判断以head为头节点的链表是否只有一个头结点  
形参代表的意义：

*  struct list\_head \*head：需要判断的以head为头节点的链表

###### 内核链表中函数原型： ######

static inline int list_empty(struct list_head *head)
    { 
    	return head->next == head;
    }

> head->next == head;当相等时会返回1，不相等时返回0

##### 9. list\_entry(ptr, type, member) #####

（这是一个宏定义，非函数）  
该宏定义作用：把指针域的结构体（小结构体）地址转为存放数据和指针结构体（大结构体）的整个的地址  
形参代表的意义：

*  ptr：指针域结构体（小结构体）的指针，
 *  type：存放数据的大结构体的数据类型，
 *  member：指针域结构体(小结构体)的变量名

###### 内核链表中的原型： ######

#define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

> 通过先把小结构体的地址减去数据类型的大小，获得整个结构体的地址

##### 10.list\_for\_each(pos, head) #####

(这实质是一个宏定义，定义了一个for循环，并非函数)  
作用：用于遍历以head为头节点的链表从头开始遍历所有节点  
形参代表的意义：

*  pos：自己定义的一个struct list\_head指针结构体类型的变量
 *  head：头节点中struct list\_head 指针结构体的地址

###### 内核中的原型为： ######

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

> 把pos赋值为头节点的下一个节点，只要pos不是头节点，就一直往后遍历

##### 11.list\_for\_each\_prev(pos, head) #####

(这实质是一个宏定义，定义了一个for循环，并非函数)  
作用：用于遍历以head为头节点的链表从末尾开始遍历所有节点  
形参代表的意义：

*  pos：自己定义的一个struct list\_head指针结构体类型的变量
 *  head：头节点中struct list\_head 指针结构体的地址

###### 内核中的原型为： ######

#define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); \ pos = pos->prev)

> 把头节点的前一个赋值给pos，只要pos不为头节点就一直往前遍历

##### 12.list\_for\_each\_safe(pos, n, head) #####

(这实质是一个宏定义，定义了一个for循环，并非函数)  
作用：用于遍历以head为头节点的链表从头开始遍历所有节点，并且在遍历过程中可以删除节点  
形参代表的意义：

*  pos：自己定义的一个struct list\_head指针结构体类型的变量
 *  n：自己定义的一个struct list\_head指针结构体类型的变量（作用是为了在释放掉p所指向的节点后，还能继续往后遍历并不受影响）
 *  head：头节点中struct list\_head 指针结构体的地址

###### 内核中的原型为： ######

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

> 把头节点的下一个赋值给pos，n为pos的下一个，只要pos不为头节点，n就赋值给pos，n的下一个就赋值给n

##### 13.list\_for\_each\_tail\_safe(pos, n, head) #####

(这实质是一个宏定义，定义了一个for循环，并非函数)  
作用：用于遍历以head为头节点的链表从末尾开始遍历所有节点  
形参代表的意义：

*  pos：自己定义的一个struct list\_head指针结构体类型的变量
 *  n： 自己定义的一个struct list\_head指针结构体类型的变量（作用是为了在释放掉p所指向的节点后，还能继续往后遍历并不受影响）
 *  head：头节点中struct list\_head 指针结构体的地址

###### 内核中的原型为： ######

#define list_for_each_tail_safe(pos, n, head) \ for (pos = (head)->prev, n = pos->prev; pos != (head); \ pos = n, n = pos->prev)

> 把头节点的前一个赋值给pos，n为pos的下一个，只要pos不为头节点就一直往前遍历；把n赋值给pos，再把n的下一个赋值给n

##### 本博文仅仅是讲解了内核链表中的一些函数，但是有一些细节可能讲的不是特别清楚，有什么不懂的可以留言私信都可以，看到会第一时间回复================================================ #####

##### 这些都是关于我个人的一些了解，包括图也都是自己画的；如果有什么地方写错或者画错了麻烦告知一下，真的非常感谢 #####

[https_mirrors.edge.kernel.org_pub_linux_kernel]: https://mirrors.edge.kernel.org/pub/linux/kernel/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rha2FzaGk3Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/08ff941a52934cdbb4d4b90cf74dbb2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rha2FzaGk3Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/fb16cb968a5d490485a3675cf9086a45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rha2FzaGk3Nw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/897b0222c72847d6a6b7b340ae591e55.png