当前位置：首页 > news >正文

C-数据结构-双向链表（linux内核）

news 来源：原创 2024/7/5 10:28:05

/*
借用list.h内核源码实现双向链表
list.h解析可参考

https://blog.csdn.net/u012351051/article/details/99193521

lish.h

#ifndef LINUX_LIST_H__
#define LINUX_LIST_H__#define LIST_HEAD_INIT(name)	{&(name),&(name)}
#deinfe LIST_HEAD(name)	struct list_head name = LIST_HEAD_INIT(name)struct list_head
{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;
}
static inline void list_add(struct list_head *new, struct list_head *head)
{__list_add(new, head, head->next);
}
#define list_for_each(pos, head) \for (pos = (head)->next;  pos != (head); pos = pos->next)/* ptr->curtype->struct score_stmember->node
*/#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#define container_of(ptr, type, member) ({			\const typeof(((type *)0)->member) * __mptr = (ptr);	\(type *)((char *)__mptr - offsetof(type, member)); })#define list_entry(ptr, type, member) \container_of(ptr, type, member)#endif

main.c

#include<stdio.h>
#include<stdlib.h>
#include "list.h"
#define NAMESIZE	32
struct score_st
{int id;char name[NAMESIZE];struct list_head node;//谁用这个链表 就把当前的结构包含进来int math;int chinese;
}
static void print_s(struct score_st *d)
{printf("%d %s %d %d\n",d->id,d->name,d->math,d->chinese);
}int main()
{int i;struct score_st *datap;struct list_head *cur;LIST_HEAD(head);for(i = 0;i<7 ;i++){datap = malloc(sizeof(*datap));if(datap == NULL)exit(1);datap->id = i;snprintf(datap->name,NAMESIZE,"stu%d",i);data->math = rand()%100;data->chinese = rand()%100;list_add(&datap->node,&head);}	list_for_each(cur,&head){datap = list_entry(cur,struct score_st,node);print_s(datap);}list_for_each(cur,&head){datap = list_entry(cur,struct score_st,node);if(datap->id= 5)break;}if(cur = &head)printf("can not find!\n");elseprint_s(datap);exit(0);
}

补充说明

LIST_HEAD(head) 是一个宏，它用于定义并初始化一个双向链表的头节点。在你的代码中，它的作用是创建并初始化一个名为 head 的链表头节点。让我们详细解释一下这个宏和它的作用。

解释 `LIST_HEAD(head)`

在 list.h 头文件中，LIST_HEAD 宏定义如下：

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

这个宏展开为以下代码：

struct list_head head = {&(head), &(head)};

这里 LIST_HEAD_INIT(name) 是一个初始化宏，它将链表头节点的 prev 和 next 指针都指向节点自身。这就意味着，head 既是链表的起点也是链表的终点，表示一个空的链表。

详细解析

定义链表头节点：
```
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
```
这个宏定义了一个 struct list_head 类型的变量，并使用 LIST_HEAD_INIT 宏初始化它。
初始化链表头节点：
```
#define LIST_HEAD_INIT(name) {&(name), &(name)}
```
这个宏初始化链表头节点，使其 prev 和 next 都指向自己，表示一个空的双向链表。

使用示例

在你的 main.c 文件中，有以下代码：

LIST_HEAD(head);

这行代码等同于：

struct list_head head = {&head, &head};

这就创建了一个链表头节点 head，并且初始化了它的 prev 和 next 指针，使它们都指向 head 本身，表示链表为空。

如何工作

让我们看看这个链表头节点如何在代码中使用：

初始化链表：
```
LIST_HEAD(head);
```

向链表添加节点：

for (i = 0; i < 7; i++) {datap = malloc(sizeof(*datap));if (datap == NULL)exit(1);datap->id = i;snprintf(datap->name, NAMESIZE, "stu%d", i);datap->math = rand() % 100;datap->chinese = rand() % 100;list_add(&datap->node, &head);
}

这里我们通过 list_add 函数将新节点添加到链表中。
list_add 调用了 __list_add，它更新新节点和链表中其他节点的指针，使新节点正确插入链表。

遍历链表：
```
list_for_each(cur, &head) {datap = list_entry(cur, struct score_st, node);print_s(datap);
}
```
- 这里我们使用 list_for_each 宏遍历链表，从头节点开始，依次访问每个节点。