从零开始的敲代码生活--数据结构篇（内核链表）

一、内核链表基础概念普通链表数据域里面包含指针。 内核链表不把数据放在链表结点内部链表结点只存两个指针prev/next嵌入到自定义结构体中称为“侵入式链表”。 本质是双向循环链表有一个哨兵头结点不存有效数据哨兵的prev指向链表尾next指向链表第一个有效结点。优点通用一套链表代码可以管理任意自定义数据结构体双向循环头尾操作O(1)内核广泛使用不需要管理计数clen通过container_of宏由链表指针反推得到外部结构体首地址。缺点理解门槛高必须掌握container_of没有自带结点计数如需数量需要自己遍历统计。文件说明klisth.h内核链表头文件模拟linux内核list_headklist.c简单封装对外接口main_klist.c测试main函数注意Linux内核源码的list_head是纯头文件宏/内联函数没有.c文件这里为贴合文章格式做简单封装。二、头文件 klisth.h#ifndef _KLIST_H #define _KLIST_H #include stdio.h #include stdlib.h //内核链表结点只有两个指针无数据 typedef struct list_head { struct list_head *prev; struct list_head *next; }list_head; //container_of宏根据成员地址反推整个结构体首地址 #define container_of(ptr, type, member) \ ((type *)((char *)(ptr) - (unsigned long)(((type *)0)-member))) //初始化哨兵头结点 #define LIST_HEAD_INIT(name) { (name), (name) } #define LIST_HEAD(name) list_head name LIST_HEAD_INIT(name) //自定义数据结构体把list_head嵌入自己的结构体 typedef struct { int id; char name[20]; list_head node; //内核链表结点嵌入在这里 }Student_t; //函数声明 extern void list_init(list_head *head); extern void list_add_head(list_head *head, list_head *new); extern void list_add_tail(list_head *head, list_head *new); extern void list_del(list_head *pos); extern int list_is_empty(list_head *head); //遍历宏 #define list_for_each(pos, head) \ for(pos (head)-next; pos ! (head); pos pos-next) //遍历并拿到外部结构体指针 #define list_for_each_entry(stu, pos, head, member) \ for(pos (head)-next, stu container_of(pos, Student_t, member);\ pos ! (head);\ pos pos-next, stu container_of(pos, Student_t, member)) #endif三、功能实现 klist.c模拟内核链表基础操作内核中原为static inline这里封装成函数方便阅读。1. list_init 初始化哨兵头结点功能哨兵结点自环prev、next指向自己。#include klisth.h void list_init(list_head *head) { head-next head; head-prev head; }2. list_add_head 头插哨兵之后插入void list_add_head(list_head *head, list_head *new) { new-next head-next; new-prev head; head-next-prev new; head-next new; }3. list_add_tail 尾插哨兵的prev前面插入void list_add_tail(list_head *head, list_head *new) { new-next head; new-prev head-prev; head-prev-next new; head-prev new; }4. list_del 删除指定结点只摘链不free内存重要list_del只是把结点从链表摘出去不会释放结点对应的内存free由用户自己完成。void list_del(list_head *pos) { pos-prev-next pos-next; pos-next-prev pos-prev; pos-next NULL; pos-prev NULL; }5. list_is_empty 判断链表是否为空int list_is_empty(list_head *head) { return head-next head; }四、测试main函数 main_klist.c#include klisth.h int main(void) { //1.定义哨兵头结点 LIST_HEAD(stu_head); //申请3个学生结构体 Student_t *s1 malloc(sizeof(Student_t)); Student_t *s2 malloc(sizeof(Student_t)); Student_t *s3 malloc(sizeof(Student_t)); if(s1NULL||s2NULL||s3NULL) { printf(malloc error\n); return -1; } s1-id 1001; snprintf(s1-name,sizeof(s1-name),zhangsan); s2-id 1002; snprintf(s2-name,sizeof(s2-name),lisi); s3-id 1003; snprintf(s3-name,sizeof(s3-name),wangwu); //尾插把结构体内部的node挂入链表 list_add_tail(stu_head, s1-node); list_add_tail(stu_head, s2-node); list_add_tail(stu_head, s3-node); printf(遍历学生链表:\n); list_head *pos; Student_t *pstu; list_for_each_entry(pstu, pos, stu_head, node) { printf(id:%d name:%s\n, pstu-id, pstu-name); } //删除s2结点 list_del(s2-node); free(s2); s2 NULL; printf(删除lisi之后:\n); list_for_each_entry(pstu, pos, stu_head, node) { printf(id:%d name:%s\n, pstu-id, pstu-name); } //全部释放 while(!list_is_empty(stu_head)) { pos stu_head.next; list_del(pos); pstu container_of(pos, Student_t, node); free(pstu); } return 0; }五、编译运行内存检测编译gcc main_klist.c klist.c -o klist_demo运行程序./klist_demovalgrind检测内存泄漏valgrind --leak-checkfull ./klist_demo注意list_del()只做摘链不会free内存必须手动free外层结构体container_of是内核链表灵魂由链表成员指针找回整个结构体哨兵结点LIST_HEAD本身不存业务数据内核链表没有维护clen计数求长度需要遍历计数。