哈尔滨网站建设公司哪家好wordpress标记已读

哈尔滨网站建设公司哪家好,wordpress标记已读,兖矿东华建设网站,什么是网站功能需求侵入式链表详解 目录 什么是侵入式链表与传统链表的对比侵入式链表的优势Linux内核中的实现核心数据结构核心操作函数container_of宏详解使用示例应用场景总结 什么是侵入式链表 **侵入式链表#xff08;Intrusive Linked List#xff09;**是一种特殊的链表实现方式…侵入式链表详解目录什么是侵入式链表与传统链表的对比侵入式链表的优势Linux内核中的实现核心数据结构核心操作函数container_of宏详解使用示例应用场景总结什么是侵入式链表**侵入式链表Intrusive Linked List**是一种特殊的链表实现方式它的特点是链表节点直接嵌入到数据结构内部而不是通过指针指向独立的数据节点。在侵入式链表中链表节点list_head是数据结构的一个成员而不是独立存在的。这种设计使得链表操作更加高效并且不需要额外的内存分配。核心思想数据结构包含list_head成员list_head嵌入在数据中通过container_of获取完整数据与传统链表的对比传统链表非侵入式传统链表通常采用以下结构// 传统链表节点结构structlist_node{void*data;// 指向实际数据structlist_node*next;// 指向下一个节点structlist_node*prev;// 指向前一个节点};特点链表节点和数据是分离的需要额外的指针来存储数据每次访问数据都需要解引用内存布局不连续说明list_node中的data字段是一个指针指向实际的数据对象数据对象和链表节点在内存中是分离的。自包含链表专用链表节点还有一种常见的链表实现方式数据直接嵌入在链表节点中// 自包含链表节点结构structlist_node{inta;// 数据直接嵌入在节点中structlist_node*next;// 指向下一个节点structlist_node*prev;// 指向前一个节点};特点数据直接存储在链表节点中不是指针链表节点就是数据结构本身不需要额外的指针来访问数据内存布局连续但只适用于单一数据类型简单直接适合特定场景说明数据字段如int a直接嵌入在链表节点结构体中链表节点本身就是数据容器。适用场景数据类型简单且固定不需要存储复杂数据结构适合教学示例和简单应用侵入式链表侵入式链表的结构// 侵入式链表节点结构structlist_head{structlist_head*next;// 指向下一个节点structlist_head*prev;// 指向前一个节点};// 数据结构中包含list_headstructmy_data{intvalue;charname[32];structlist_headlist;// 链表节点嵌入在数据结构中};特点链表节点直接嵌入在数据结构中不需要额外的指针存储数据通过container_of宏从节点指针获取完整数据结构内存布局更紧凑说明list_head直接嵌入在my_data结构体中数据对象和链表节点在内存中是连续的通过list成员连接。三种链表类型对比总结特性传统链表自包含链表侵入式链表数据存储外部对象通过指针节点内部数据结构内部灵活性高可存储任意类型低固定类型高任意类型内存开销中等需要指针低最低适用场景通用场景简单固定类型系统编程、高性能场景侵入式链表的优势1. 内存效率高无额外指针开销不需要额外的指针来存储数据内存布局紧凑数据连续存储缓存友好2. 性能优势减少内存分配不需要为链表节点单独分配内存减少指针解引用数据访问路径更短更好的缓存局部性数据连续存储提高缓存命中率3. 灵活性一个对象可以同时属于多个链表只需在结构中包含多个list_head成员类型无关链表操作不关心数据类型通用性强4. 适合系统编程零开销抽象编译后几乎没有额外开销适合内核开发Linux内核广泛使用Linux内核中的实现Linux内核在include/linux/list.h中实现了完整的侵入式双向链表。这是经过多年优化的工业级实现。文件位置linux-4.14.7/include/linux/list.h核心数据结构list_head结构体structlist_head{structlist_head*next;// 指向下一个节点structlist_head*prev;// 指向前一个节点};这是侵入式链表的核心数据结构只包含两个指针非常简洁。初始化宏// 初始化宏定义#defineLIST_HEAD_INIT(name){(name),(name)}// 声明并初始化链表头#defineLIST_HEAD(name)\structlist_headnameLIST_HEAD_INIT(name)// 初始化函数staticinlinevoidINIT_LIST_HEAD(structlist_head*list){WRITE_ONCE(list-next,list);list-prevlist;}初始化后的状态next和prev都指向自身形成一个空的双向循环链表核心操作函数1. 添加节点list_add - 在头部添加/** * list_add - 在链表头部添加新节点 * new: 要添加的新节点 * head: 链表头 * * 在head之后插入new节点适合实现栈LIFO */staticinlinevoidlist_add(structlist_head*new,structlist_head*head){__list_add(new,head,head-next);}list_add_tail - 在尾部添加/** * list_add_tail - 在链表尾部添加新节点 * new: 要添加的新节点 * head: 链表头 * * 在head之前插入new节点适合实现队列FIFO */staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head){__list_add(new,head-prev,head);}__list_add - 内部插入函数/** * __list_add - 在两个已知节点之间插入新节点 * new: 新节点 * prev: 前一个节点 * next: 后一个节点 */staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){if(!__list_add_valid(new,prev,next))return;next-prevnew;new-nextnext;new-prevprev;WRITE_ONCE(prev-next,new);}2. 删除节点list_del - 删除节点/** * list_del - 从链表中删除节点 * entry: 要删除的节点 * * 注意删除后节点处于未定义状态 */staticinlinevoidlist_del(structlist_head*entry){__list_del_entry(entry);entry-nextLIST_POISON1;// 设置为毒药指针便于调试entry-prevLIST_POISON2;}staticinlinevoid__list_del_entry(structlist_head*entry){if(!__list_del_entry_valid(entry))return;__list_del(entry-prev,entry-next);}staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next-prevprev;WRITE_ONCE(prev-next,next);}list_del_init - 删除并重新初始化/** * list_del_init - 删除节点并重新初始化 * entry: 要删除的节点 * * 删除后节点可以重新使用 */staticinlinevoidlist_del_init(structlist_head*entry){__list_del_entry(entry);INIT_LIST_HEAD(entry);}3. 遍历链表list_for_each - 遍历链表节点/** * list_for_each - 遍历链表 * pos: 用作循环游标的list_head指针 * head: 链表头 */#definelist_for_each(pos,head)\for(pos(head)-next;pos!(head);pospos-next)list_for_each_entry - 遍历链表中的数据/** * list_for_each_entry - 遍历链表中的数据项 * pos: 用作循环游标的数据结构指针 * head: 链表头 * member: list_head在数据结构中的成员名 */#definelist_for_each_entry(pos,head,member)\for(poslist_first_entry(head,typeof(*pos),member);\pos-member!(head);\poslist_next_entry(pos,member))list_for_each_entry_safe - 安全遍历允许删除/** * list_for_each_entry_safe - 安全遍历允许在遍历时删除节点 * pos: 用作循环游标的数据结构指针 * n: 另一个数据结构指针用作临时存储 * head: 链表头 * member: list_head在数据结构中的成员名 */#definelist_for_each_entry_safe(pos,n,head,member)\for(poslist_first_entry(head,typeof(*pos),member),\nlist_next_entry(pos,member);\pos-member!(head);\posn,nlist_next_entry(n,member))4. 其他常用操作list_empty - 判断链表是否为空/** * list_empty - 判断链表是否为空 * head: 链表头 */staticinlineintlist_empty(conststructlist_head*head){returnREAD_ONCE(head-next)head;}list_move - 移动节点/** * list_move - 将节点从一个链表移动到另一个链表头部 * list: 要移动的节点 * head: 目标链表头 */staticinlinevoidlist_move(structlist_head*list,structlist_head*head){__list_del_entry(list);list_add(list,head);}container_of宏详解container_of宏是侵入式链表的灵魂它能够从结构体成员的指针获取整个结构体的指针。宏定义/** * container_of - 从成员指针获取包含它的结构体指针 * ptr: 成员指针 * type: 结构体类型 * member: 成员在结构体中的名称 */#definecontainer_of(ptr,type,member)({\consttypeof(((type*)0)-member)*__mptr(ptr);\(type*)((char*)__mptr-offsetof(type,member));})工作原理1. offsetof宏#defineoffsetof(TYPE,MEMBER)((size_t)((TYPE*)0)-MEMBER)原理将0强制转换为TYPE*类型访问MEMBER成员得到成员相对于结构体起始地址的偏移量由于基址是0所以((TYPE *)0)-MEMBER就是偏移量示例structmy_data{intvalue;// 偏移量: 0charname[32];// 偏移量: 4structlist_headlist;// 偏移量: 36 (假设)};// offsetof(struct my_data, list) 362. container_of计算过程假设我们有structmy_data{intvalue;structlist_headlist;};structmy_data*data;structlist_head*list_ptrdata-list;现在要从list_ptr获取data// 步骤1: 获取list成员的类型并验证consttypeof(((structmy_data*)0)-list)*__mptrlist_ptr;// 步骤2: 将指针转换为char*以便进行字节级运算char*__mptr_char(char*)__mptr;// 步骤3: 减去偏移量得到结构体起始地址structmy_data*result(structmy_data*)(__mptr_char-offsetof(structmy_data,list));内存布局示意地址: 0x1000 0x1024 [my_data] [list] ^ ^ | | data list_ptr offsetof 0x1024 - 0x1000 0x24 从list_ptr获取data: data list_ptr - offsetof 0x1024 - 0x24 0x1000 ✓为什么需要typeoftypeof用于类型检查确保传入的ptr确实是member类型的指针提高代码安全性。使用示例示例1基本使用#includestdio.h#includestdlib.h#includelist.h// 假设包含了list.h// 定义数据结构structstudent{intid;charname[32];intage;structlist_headlist;// 链表节点};intmain(void){// 初始化链表头LIST_HEAD(student_list);// 创建学生数据structstudent*s1malloc(sizeof(structstudent));s1-id1;strcpy(s1-name,Alice);s1-age20;INIT_LIST_HEAD(s1-list);structstudent*s2malloc(sizeof(structstudent));s2-id2;strcpy(s2-name,Bob);s2-age21;INIT_LIST_HEAD(s2-list);// 添加到链表list_add(s1-list,student_list);list_add(s2-list,student_list);// 遍历链表structstudent*pos;list_for_each_entry(pos,student_list,list){printf(ID: %d, Name: %s, Age: %d\n,pos-id,pos-name,pos-age);}// 清理list_for_each_entry_safe(pos,n,student_list,list){list_del(pos-list);free(pos);}return0;}示例2多个链表// 一个对象可以同时属于多个链表structtask{intpid;charname[32];structlist_headrun_list;// 运行队列structlist_headwait_list;// 等待队列structlist_headall_tasks;// 所有任务列表};// 初始化structtask*tmalloc(sizeof(structtask));INIT_LIST_HEAD(t-run_list);INIT_LIST_HEAD(t-wait_list);INIT_LIST_HEAD(t-all_tasks);// 添加到不同链表list_add(t-run_list,run_queue);list_add(t-all_tasks,task_list);示例3实现队列// 使用list_add_tail实现FIFO队列LIST_HEAD(queue);voidenqueue(structlist_head*item){list_add_tail(item,queue);}structlist_head*dequeue(void){if(list_empty(queue))returnNULL;structlist_head*itemqueue.next;list_del(item);returnitem;}示例4实现栈// 使用list_add实现LIFO栈LIST_HEAD(stack);voidpush(structlist_head*item){list_add(item,stack);}structlist_head*pop(void){if(list_empty(stack))returnNULL;structlist_head*itemstack.next;list_del(item);returnitem;}应用场景1. Linux内核Linux内核中广泛使用侵入式链表进程管理进程链表、运行队列内存管理页框链表、伙伴系统文件系统inode链表、dentry缓存设备驱动设备链表网络协议栈sk_buff链表2. 高性能系统编程嵌入式系统资源受限环境实时系统低延迟要求游戏引擎性能敏感场景3. 需要多链表管理的场景当一个对象需要同时属于多个链表时侵入式链表特别有用structprocess{intpid;structlist_headrunq;// 运行队列structlist_headwaitq;// 等待队列structlist_headchildren;// 子进程列表structlist_headsiblings;// 兄弟进程列表};总结侵入式链表的优点内存效率高无额外指针开销性能优秀缓存友好访问速度快灵活性强一个对象可属于多个链表类型无关通用性强代码复用性好侵入式链表的缺点侵入性需要修改数据结构添加list_head成员学习曲线container_of宏的理解需要一定时间调试困难指针操作较多调试相对复杂适用场景✅ 系统编程内核、驱动✅ 性能敏感的应用✅ 需要多链表管理的场景✅ 内存受限的环境❌ 简单的用户态应用可能过度设计关键要点理解container_of宏这是侵入式链表的精髓正确使用遍历宏区分普通遍历和安全遍历注意内存管理删除节点后要释放内存理解循环链表链表头指向自身表示空链表