Linux의 커널 연결 리스트에 대한 코드 예제 공유

이 글은 주로 Linux의 커널 연결리스트 예제에 대한 자세한 설명을 소개합니다. 연결리스트는 일반적으로 연결리스트의 초기화, 삽입, 삭제, 표시, 해제가 필요하며, 필요한 친구들이 참고할 수 있습니다

Linux의 커널 연결리스트 예제에 대한 자세한 설명

연결리스트에는 일반적으로 초기화, 삽입, 삭제, 표시, 연결리스트 해제, 노드 찾기 등 여러 가지 작업이 있는데 아래에서 간략히 소개하겠습니다. , 제가 ​​능력이 부족하고, 깊이 있게 이해하지 못한 부분이 있어서 오류가 있을 수 있으니 지적 부탁드립니다.

A. Linux 커널 연결 목록의 여러 주요 기능(커널의 소스 코드는 누구나 분석할 수 있도록 아래에 표시되어 있습니다.)

1) 초기화:

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

2) 꼬리 삽입:

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

3) 헤더 삽입 기능

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

4) 노드 삭제 기능

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

5) 표시 기능 (링크드 리스트의 정보를 출력하고 싶다면 출력 기능을 직접 작성해야 하며, printf와 같은 것 때문에 실제로는 순회 기능이고 표시 기능이 없습니다)

#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) 연결된 목록 삭제

#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) 노드 찾기(이것도 printf의 순회 기능입니다. 커널)

#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. 다음은 사용 방법을 보여주는 코드입니다

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

위 내용은 Linux의 커널 연결 리스트에 대한 코드 예제 공유의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!