Exemple de code partageant la liste chaînée du noyau sous Linux

Cet article présente principalement des informations pertinentes sur l'explication détaillée des exemples de listes chaînées du noyau sous Linux. Les listes chaînées nécessitent généralement des opérations d'initialisation, d'insertion, de suppression, d'affichage, de publication et de recherche de nœuds. suivant

Explication détaillée des exemples de listes chaînées du noyau sous Linux

Dans les listes chaînées, initialisation, insertion, suppression, affichage, publication de listes chaînées et recherche Les nœuds sont généralement nécessaires. Opérations, je vais donner une brève introduction à ces opérations ci-dessous. En raison de mon manque de capacité, je ne comprends peut-être pas certaines choses assez profondément, ce qui entraîne certaines erreurs. Veuillez le signaler aux autres blogueurs.

A. Plusieurs fonctions principales de la liste liée du noyau Linux (le code source du noyau est affiché ci-dessous pour que tout le monde puisse l'analyser)

1) Initialisation :

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

2) Insertion de la queue :

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

3) Fonction d'insertion de la tête

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

4) Fonction de suppression de nœud

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

5) Fonction d'affichage (si vous souhaitez imprimer les informations dans la liste chaînée, vous devez l'écrire vous-même en tant que fonction d'impression, telle que printf, car il s'agit en fait d'une fonction de parcours et n'a pas de fonction d'affichage)

#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) Supprimer la liste chaînée

#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) Rechercher des nœuds (c'est aussi la fonction de traversée dans le noyau)

#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. Suivant Un morceau de code pour vous montrer comment l'utiliser

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!