可复用链表list.h

可复用链表list.h这种用法惊艳到我了传统的教科书式的链表有个非常大的缺点: 一句话讲就是复用性差每种类型的链表我们都需要编写不同的函数去实现增删改查等基本操作不仅效率低, 而且还容易出错而linux内核的list.h就是为了解决这一痛点而诞生的我们只需要添加基本的成员, 然后对list.h中的函数简单封装一下, 就能够实现想要的功能了须知我们使用的list是一种特殊双向环形链表,双向环形链表 大家可能比较好理解, 那么特殊之处在什么地方呢?我觉得有必要了解一下普通的环形链表为了方便讲解, 这儿我使用了3个节点的链表, 收尾相接组成了一个环形链表 (后同)如图所示, 除了基本成员, 还会有个结构体指针next结构体中的next指向了下个节点的首地址 ( 也就是结构体第一个成员的地址 )结构体C的next指向了结构体A的首地址普通双向环形链表如图所示, 除了基本成员, 还会有两个结构体指针next和prev结构体中的next指向了下个节点的首地址结构体中的prev指向了上个节点的首地址结构体C的next指向了结构体A的首地址结构体A的prev指向了结构体C的首地址特殊双向环形链表先看list类型的结构体structlist_head{structlist_head*next,*prev;};使用它时我们会像下面这样定义typedefstruct{inta;intb;charc;...structlist_headlist;...}Queue;list使用时的结构一般如下图所示图3如图所示, 除了基本成员, 还会有1个list_head类型的成员这个list_head类型的成员为一个结构体, 这个结构体有两个指针成员list-next和list-prev结构体中的list-next指向了下个结构体的list成员的首地址结构体中的list-prev指向了上个结构体的list成员的首地址结构体C的list-next指向了结构体A的list成员的地址结构体A的list-prev指向了结构体C的list成员的地址基本函数init_list_head()staticinlinevoidinit_list_head(structlist_head*list)初始化头结点, 初始化之后如下图所示list_add()staticinlinevoidlist_add(structlist_head*new,structlist_head*head)图3 执行list_add(X-list, A-list)之后如下图所示list_add_tail()staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head)将新节点添加到指定节点之前. 也就是让指定节点跑到后面去.图3 执行list_add_tail(X-list, A-list)之后如下图所示list_del()staticinlinevoidlist_del(structlist_head*entry)图3 执行list_del(A-list)之后如下图所示list_move()staticinlinevoidlist_move(structlist_head*list,structlist_head*head)将list节点 移动到head后面.图3 执行list_move(A-list, B-list)之后如下图所示list_move_tail()staticinlinevoidlist_move_tail(structlist_head*list,structlist_head*head)将list节点 移动到head前面.图3 执行list_move_tail(B-list, A-list)之后如下图所示list_replace()staticinlinevoidlist_replace(structlist_head*old,structlist_head*new)将list节点 移动到head前面.图3 执行list_replace(X-list, B-list)之后如下图所示除了上面列举的接口之外, 还有其它很多接口, 这儿就不一一列举了…有兴趣的话自己去看代码list_entry() 详解根据list成员得到结构体的指针这是一个比较重要的宏函数这是个宏定义, 有很多种不同的版本, 不过原理都差不多, 为了方便大家理解我以下面这种为例进行讲解#definelist_entry(ptr,type,member)\((type*)((char*)(ptr)-(unsignedlong)(((type*)0)-member)))由上图可知, 假如addr的值为0, 那么list地址就是 它 在结构体重的偏移量.因此(unsigned long)(((type *)0)-member))就是list在结构体中的偏移量.而(type *)((char *)(ptr)是 实际 使用过程中list的地址那么(type *)((char *)(ptr)-(unsigned long)(((type *)0)-member))就是结构体A的地址备注:按说来,0地址不能这样用的, 读出来的内容也没有意义, 但如果我们不对0地址进行写, 也不会对系统造成任何影响.list_entry() 使用如果我们有上图中结构体A的指针, 该怎么访问结构体B的其他成员呢 ?Queue*tmplist_entry(A-list.next,Queue,list);// 获取 B 的结构体指针printf(B-a %d\n,tmp-a);// 访问 a 成员printf(B-b %d\n,tmp-b);// 访问 b 成员printf(B-c %d\n,tmp-c);// 访问 c 成员常见函数list_for_each_entryQueue*pos;list_for_each_entry(pos,A.list,list){/* 第一次进来 pos 为 B *//* 第二次进来 pos 为 C */}实践我在网上找了一个足够小, 但是足以方便大家理解的使用list实现fifo的开源代码链接 : 点击进入