Code example sharing about kernel linked list in Linux

This article mainly introduces relevant information about the detailed explanation of kernel linked list examples in Linux. Linked lists generally require initialization, insertion, deletion, display, release of linked lists, and node search operations. Friends in need can refer to the following

Detailed explanation of kernel linked list examples in Linux

In a linked list, initialization, insertion, deletion, display, release of the linked list, and finding nodes are generally required. Operations, I will give a brief introduction to these operations below. Because of my lack of ability, I may not understand some things deeply enough, resulting in certain errors. Please point it out to fellow bloggers.

A. Several main functions in the Linux kernel linked list (the following is the source code in the kernel for everyone to analyze)

1) Initialization:

#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)  // ptr为struct list_head，其中包括两个指针next和prev，这里已经可以看出内核链表是双向循环链表

2) Tail insertion:

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
} //尾部插入,传入的参数是新节点中的两个指针和头结点中的两个指针

3) Head insertion function

static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
} //头插入函数,传入的参数是新节点中的两个指针和头结点中的两个指针

4) Delete node function

static inline void list_del(struct list_head *entry)  //传入要删除节点中的指针域
{
__list_del(entry->prev, entry->next);//两个参数分别为所删除节点前一个节点和后一个节点
entry->next = (void *) 0;//删除节点后置为空
entry->prev = (void *) 0;
}

5) Display function (if you want to print out the information in the linked list, you must write a printing function yourself, such as printf, because of this In fact, it is a traversal function with no display function)

#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))

/* 这个函数用于遍历链表
pos为节点指针，
head是头结点中的两个指针的地址
member为各节点中的指针域
*/

6) Delete the linked list

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

//这里面的pos和n都是list_head指针，n指针是用于在删除时不让链表断链

7) Find nodes (this is also the traversal function in the kernel)

#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))

B. Here is a piece of code to show you the specific application method

#include"kernel.h"
#include<errno.h>
#include<stdio.h>
#include<stdlib.h>

typedef struct list_node
{
int data;
struct list_head list;//节点的指针域是被封装在struct list_head这个结构体内
//这个结构体中包括struct list_head *next,*prev
}*node,node1;


node init_head(node head)//初始化空链表
{
head = (node)malloc(sizeof(node1));//为节点分配空间
if(head == NULL)
{
perror("head");
return NULL;
}
INIT_LIST_HEAD(&(head->list));//#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)//调用内核中的初始化函数，传入的参数是
//节点的中两个指针，即struct list_head结构体中的两个指针
return head;
}

node insert_tail(node head,int data)//尾部插入函数
{
node new = (node)malloc(sizeof(node1));//为新节点分配空间
if(new == NULL)//判断一下分配空间是否成功
{
perror("new:");
return NULL;
}
new->data = data;
list_add_tail(&(new->list),&(head->list));//调用内核中的从尾部插入的函数，传入的参数为新节点中的两个指针
//和头结点中的两个指针
return 0;
}

 

head_insert_node(node head,int data)//头插入函数
{
node new;//创建一个新节点
new = (node)malloc(sizeof(node1));//为新节点分配空间
if(new == NULL)//判断一下分配空间是否成功
{
perror("new:");
return 0;
}
new->data = data;
list_add(&(new->list),&(head->list));//调用内核中从头插入的函数，传入的参数为新节点的两个指针和头结点的两个指针
return 0;
}

node search_node(node head,int data)//寻找节点函数
{
node p = NULL;
list_for_each_entry(p,&(head->list),list) //内核中的遍历函数
{
if(p->data == data) //p即为需要找的节点
{
printf("found the data:%d\n",p->data);
goto OK;
}
}

puts("not found the data!");
return NULL;

OK:
return p;
}

int show_node(node tmp)
{
if(tmp == NULL)
{
puts("tmp is NULL!");
return -1;
}
printf("the data is %d\n",tmp->data);
return 0;
}

int delete_node(node head,int data)
{
node p = NULL;
list_for_each_entry(p,&(head->list),list)
{
if(p->data == data)
{
printf("found the data which you want to delete!\n");
goto f;
}
}

f:
list_del(&(p->list));
free(p);
return 0;
}
int show_list(node head)
{
node p = NULL;
list_for_each_entry(p,&(head->list),list)
{
printf("data:%d\n",p->data);
}
return 0;
}
int delete_list(node head)//删除链表函数
{
node p,q;
list_for_each_entry_safe(p,q,&(head->list),list)//这是内核中的安全删除函数
{
list_del(&(p->list));
free(p);
}
list_del(&(head->list));
free(head);
return 0;
}
int main(int argc,char **argv)
{
node head;
node tmp;
head = init_head(head);//初始化空链表函数
insert_tail(head,45);//从末尾插入函数
insert_tail(head,55);
insert_tail(head,65);
head_insert_node(head,75);//从头插入函数
show_list(head); //显示链表函数 

tmp = search_node(head,55);//寻找结点函数
show_node(head);
delete_node(head,55);
//show_list(head);
delete_list(head);//删除链表函数
return 0;
}

The above is the detailed content of Code example sharing about kernel linked list in Linux. For more information, please follow other related articles on the PHP Chinese website!