企业官网建设流程全解析

可复用链表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使用时的结构一般如下图所示

• 如图所示, 除了基本成员, 还会有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*tmp=list_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_entry

Queue*pos;list_for_each_entry(pos,&A.list,list){/* 第一次进来 pos 为 B *//* 第二次进来 pos 为 C */}

实践

我在网上找了一个足够小, 但是足以方便大家理解的使用list实现fifo的开源代码

链接 : 点击进入