@
- linux内核链表个人理解
- 内核链表解决得问题（为啥要用内核链表）
- 前期说明
- 链表定义
- 初始化
- 创建链表节点
- 插入
- 查找
- 删除
- 清空
- 显示
前言
本文以一个例题的实现来讲解【C语言】linux内核循环链表练习之创、插，查、删、清、显 示例。
linux内核链表简介
linux内核链表个人理解
所谓linux内核链表（后面简称linux指针域），即使用linux内核中已经写好得独立出来得链表（双向循环链表），它是一个linux内核中统一得标准得链表。之后我们操作时只需要在linux指针域得上面封装数据域即可。
内核链表的标准节点及其所有操作，都被封装在内核源码中，具体来讲都被封装在一个名为 list.h 的文件中，该文件在内核中的位置是：
kernel/linux/include/list.h
内核中的源码文件 list.h 实际上包含了两部分内容，一是内核链表，二是哈希链表。经过整理的、仅包含内核链表的文件：kernel_list.h
内核链表解决得问题（为啥要用内核链表）
内核链表主要是为了解决普通链表得通用性问题。 如下图所示，普通链表数据域和指针域混在一起，导致通用性不好，所以内核指针将指针域独立出来，那么就可以任意套数据域方便通用操作。
大概分两步：内核中list已经做了
- 针对标准节点，设计由标准节点构成的标准链表的所有操作
题目
完成如下功能，用内核链表来实现，从键盘输入一个整数
- （1）如果这个整数大于0，插入到链表，要求：有相同的元素就不添加
- （2）如果是负整数，就将这个负整数的绝对值从链表删除，如果不存在，打印提示
- （3）如果输入的是0，就遍历显示链表的所有元素，程序退出
代码实现
前期说明
该示例就是调用linux内核中得指针域标准代码，封装后得使用。整理过后得部分代码展示如下：
//指针域部分，小结构体，用它来构建“纯粹链表”
structlist_head {
structlist_head *next, *prev;
};
//节点结构体指针初始化
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
//将new节点插入到prev和next节点之间
staticinlinevoid __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;
}
/**
* 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.
*/
//将new节点插入到head的前面
staticinlinevoidlist_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
链表定义
typedefint Datatype;
typedefstructKernel_list{
structlist_headlist;
Datatype data;
}k_list;
关键点：
- struct list_head在linux指针域已经实现了，只需要调用即可；
- 这里定义得指针域用得是变量而不是指针，是为了后面使用时可以直接使用，而不用先申请空间（指针要使用都得先申请地址！！！）
- 这里将指针域放到数据域上面是为了方便理解，指针域指向得地址就是整个链表节点得地址，只需要做一下数据类型转换即可，内核中也有处理得方法，甚至于调用得时候只需要注意是大得链表还是指针域链表即可。
初始化
k_list* init_Kernel_list(void){
k_list *head = (k_list*)malloc(sizeof(k_list));
if (head!=NULL){
INIT_LIST_HEAD(&(head->list));
}
return head;
}
关键点：
- INIT_LIST_HEAD是linux指针域得中封装好得函数，只需要看怎么调用即可。
创建链表节点
k_list *create_Kernel_list_node(Datatype data){
k_list *node = (k_list*)malloc(sizeof(k_list));
if (node!=NULL){
node->data = data;
INIT_LIST_HEAD(&(node->list));
}
return node;
}
关键点：
- INIT_LIST_HEAD是linux指针域得中封装好得函数，只需要看怎么调用即可；
插入
voidinsert_Kernel_list_node(k_list *head, k_list *node){
list_add(&(node->list), &(head->list));
}
voidinsert_Kernel_list_node_tail(k_list *head, k_list *node){
list_add_tail(&(node->list), &(head->list));
}
关键点：
- list_add是linux指针域得中封装好得函数（头插），只需要看怎么调用即可；
- list_add_tail是linux指针域得中封装好得函数（尾插），只需要看怎么调用即可；
查找
k_list *find_Kernel_list_node(k_list *head, Datatype data){
k_list *pos,*n;
list_for_each_entry_safe(pos, n, &(head->list), list){
if(pos->data == data){
return pos;
}
}
returnNULL;
}
关键点：
- list_for_each_entry_safe是linux指针域得中封装好得函数（循环），只需要看怎么调用即可；
- 带“_safe”标记得是有安全保证得函数，比如在删除得时候，不会出现删除一个后就段错误；
删除
booldelete_Kernel_list_node(k_list *head, Datatype data){
k_list *pos,*n;
bool flag = false;
list_for_each_entry_safe(pos, n, &(head->list), list){
k_list *dele = find_Kernel_list_node(head, data);
if(dele!=NULL){
list_del(&(dele->list));
free(dele);
flag = true;
}
}
if(flag==false){
printf("delete error\n");
}
else{
printf("delete success\n");
}
return flag;
}
关键点：
- list_for_each_entry_safe是linux指针域得中封装好得函数（循环），只需要看怎么调用即可；
- 带“_safe”标记得是有安全保证得函数，比如在删除得时候，不会出现删除一个后就段错误；
- list_del是linux指针域得中封装好得函数（删除），只需要看怎么调用即可；
清空
voidclear_Kernel_list(k_list *head){
k_list *pos,*n;
list_for_each_entry_safe(pos, n, &(head->list), list){
list_del(&(pos->list));
free(pos);
}
}
关键点：
- 清空只需要在删除得基础上增加释放空间即可free(pos);
显示
voidshow_Kernel_list(k_list *head){
printf("list data:\n");
k_list *pos;
k_list *n;
list_for_each_entry_safe(pos, n, &(head->list), list){
// if(pos->list.next != &(head->list)){
printf("%d ", pos->data);
// }
}
printf("\n");
}
关键点：
- list_for_each_entry_safe是linux指针域得中封装好得函数（循环），只需要看怎么调用即可；
主函数
intmain(int argc, char *argv[]){
k_list *head = init_Kernel_list();
if(head==NULL){
printf("init error\n");
return-1;
}
for (int i=0; i<10; i++){
k_list *node = create_Kernel_list_node(i);
if(node!=NULL){
insert_Kernel_list_node_tail(head, node);
}
}
show_Kernel_list(head);
printf("输入一个数，+加,-删,0退出:\n");
while(1){
int num;
scanf("%d", &num);
if(num==0){
show_Kernel_list(head);
break;
}
elseif(num>0){
k_list *node = create_Kernel_list_node(num);
if(node!=NULL){
insert_Kernel_list_node_tail(head, node);
}
}
elseif(num<0){
delete_Kernel_list_node(head, -num);
}
}
clear_Kernel_list(head);
return0;
}
代码测试结果
yin@ubuntu:/mnt/hgfs/share/c_code/KeTang/02_数据结构$ ./04
list data:
0 1 2 3 4 5 6 7 8 9
输入一个数，+加,-删,0退出:
15
36
19
65
25
-5
delete success
-4
delete success
0
list data:
0 1 2 3 6 7 8 9 15 36 19 65 25
显示结果与预期相同。
资料获取
关注微信公众号，回复：list
欢迎FPGA同行者关注微信公众号FPGA加速者，获取更多精彩
