分享
 
 
 

Apache中的环形链表

王朝system·作者佚名  2006-02-01
窄屏简体版  字體: |||超大  

5.1环型链表概述

Apache中很多地方都使用到了环形链表的数据结构,比如存储段组中就是使用环形链表保存所有的存储段数据。为了能够简化对该环形链表的操作,Apache中定义了一系列的宏来方便对链表的操作。因此在继续分析存储段之间的关系之前,我们首先来看一下Apache中环形结构的实现。

Apache中环形结构的实现采用了大量的宏,其实现参考了4.4FreeBSD中队列<sys/queue.h>和Dean Gaudet的”splim/ring.h”的实现。这两个具体的实现可以http://www.freebsd.org/cgi/cvsweb/cgi/src/sys/sys/queue.h和http://www.arctic.org/~dean/splim/找到,而Apache中所有的环形链表的实现宏都属于APR的一部分,在apr_ring.h中实现。

对于任何一个普通的数据结构比如下面的my_element_t数据结构

struct my_element_t

{

int foo;

char *bar;

}

如果我们需要构成一个双向链表,链表中的每一个元素都是my_element_t类型,那么我们要做的事情无非就是在结构内部加上next和prev指针就可以了:

struct my_element_t

{

my_element_t *next;

my_element_t *prev;

int foo;

char *bar;

}

结构定义好后,后继的工作就是为这种数据结构编写一套用于链表操作的子程序。由于用来维持链表的两个指针的类型是固定的(都是指向my_element_结构),因此这些子程序并不适合于其它数据结构的队列操作。换言之,需要维持多少种数据结构的链表,就的有多少套与之对应的操作函数。对于使用链表较少的应用程序而言,这不是一个问题,但是对于Apache这种需要使用大量不同数据结构链表的系统就不合适了。因此Apache中将具体的数据类型抽象出来,形成了一套通用的,一般的可以适用于各种数据结构的队列操作。

抽象的核心思想就是将各个具体的结构中的next和prev指针从具体的“宿主”数据结构中抽象出来,形成一种新的数据结构,然后将这种数据结构再寄生到具体的数据结构的内部,成为这种数据结构的链表中的各个结点的“连接件”,当然也可以独立存在形成链表头,Apache中称之为“哨兵结点”。

从上面my_element_t结构可以看出,next和prev指针是构成环形结构的核心,Apache中将其称之为”环域(ring entry field)”,Apache将这两个指针从具体的数据结构中抽象出来,并用宏APR_RING_ENTRY定义它:

#define APR_RING_ENTRY(elem)

struct {

struct elem *next;

struct elem *prev;

}

其中elem是环域所在的结构的类型。APR_RING_ENTRY宏形成了各个结点之间的连接件。对于任何一个普通的结构比如elem,我们只要在里面加入APR_RING_ENTRY(elem)就可以构成环形结构,因此对于上面my_element_t结构而言,我们可以改写为:

struct my_element_t

{

APR_RING_ENTRY(my_element_t) link;

//原来此处为APR_RING_ENTRY(my_element_t);错误,由allan修正

int foo;

char *bar;

}

从上面可以看出,APR_RING_ENTRY宏的参数必须与结构本身的名称相同,否则就无法形成连接。一个APR_RING_ENTRY宏对应一个环形链表。当然你也可以将一个结构放入到多个环形链表中,此时只需要在结构中增加多个APR_RING_ENTRY就可以,比如下面的A就通过两个环形域位于两个双向链表中:

另外,由于环形链表的的特殊性决定了没有绝对的起点和终点,但是为了操作的方便性,我们我们还是有必要定义一个链表头,这样只要找到链表头,就可以很方便的对环形链表进行操作了。Apache中链表头定义如下:

#define APR_RING_HEAD(head, elem)

struct head {

struct elem *next;

struct elem *prev;

}

与普通的元素结点相比,头结点显然只包含了前面所说的“环域”,而不包括实际的数据域。头结点通常位于环链表首结点的前面,同时位于尾结点的后面。

5.2初始化空环(宏APR_RING_INIT)

APR_RING_INIT(hp, elem, link)宏用来初始化一个空环,其定义如下:

#define APR_RING_INIT(hp, elem, link) do {

APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link);

APR_RING_LAST((hp)) = APR_RING_SENTINEL((hp), elem, link);

} while (0)

其中hp则是环形链表的头结构,elem则是元素结构的名称,link则是元素结构中APR_RING_ENTRY环域的名称。在存储段组中,Apache声明了一个list成员用以保存实际的存储段组链表,其声明为:

APR_RING_HEAD(apr_bucket_list, apr_bucket) list;

该宏声明了环形链表的头部结构,定义如下:

struct apr_bucket_list

{

apr_bucket *next;

apr_bucket *prev;

}

在函数apr_brigade_create中,存储段组将使用宏APR_RING_INIT对list环进行初始化,初始化代码为APR_RING_INIT(&b->list, apr_bucket, link);

在存储段环形结构中apr_bucket结构中的next和prev指向的类型都还是apr_bucket。这个在正常的存储段不算什么,但是对于两个特殊的存储段则有些为难:首存储段和尾存储段。由于apr_bucket_list作为头结构,直接位于首尾存储段之间,它们的示意图如下:

从上面的图示中我们可以看到头存储段的prev和尾存储段的next分别指向的此时是apr_bucket_list,而不是apr_bucket,因此为了能够正确的进行处理,我们可能需要类似下面的代码进行判断处理:

(1)、如果是头结点,prev指针指向的是apr_bucket_list结点结构,同时apr_bucket_list的next指向头结点

(2)、如果是尾结点,next指针指向的是apr_bucket_list结点结构,同时apr_bucket_list的prev指向该结点

(3)、如果既不是头结点,也不是尾结点在结点的next和prev都指向apr_bucket类型的结构。

这种分支判断打断了处理的连续性能,在进行结点增加和移除的时候无疑增加了复杂性。由于apr_bucket_list中的成员next和prev完全相同,因此如果能够将apr_bucket_list类型强制转换为apr_bucket,我们则就没有必要做额外的处理了。

Apache中使用APR_RING_SENTINEL宏完成这种强制转换,其定义为如下:

#define APR_RING_SENTINEL(hp, elem, link)

(struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))

将头结构通过强制转换apr_bucket结构后,我们将其称之为“哨兵(sentinel)”。当然这种转换后的结构与正常的apr_bucket还是不同的,它只有next和prev两个字段,而不具备其余的数据字段,因此对一般存储段的操作我们都不能使用到“哨兵”存储段中。

从上面的分析我们可以看出头部结构实际上担任了两个职责:头结构作为操作存储段链表的起始点;哨兵结构可以作为判断链表结束的终点。因此我们可以很容易的明白下面几个宏的原理:

(1)、#define APR_RING_EMPTY(hp, elem, link)

(APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))

如果头部结点的next指向的不是实际的存储段结点,而是哨兵结点,这表明链表中尚不存在实际的存储段结点,此时可以断定链表为空。

5.3添加链表结点

环型链表中所有的结点的添加都是基于宏APR_RING_SPLICE_AFTER进行的,该宏定义如下:

#define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do {

APR_RING_PREV((ep1), link) = (lep);

APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link);

APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN);

APR_RING_NEXT((lep), link) = (ep1);

} while (0)

该宏将结点ep1到epN链表插入到结点lep之后,当然,在插入之前ep1到epN已经应该是成型的双向链表,该宏不负责对ep1到epN之间的结点进行构建,插入步骤可以分为为四步:

①调整ep1的prev指针指向lep

②调整epN的next指针指向lep的next指针

③调整epN后结点的prev指针指向epN

④调整lep的next指针指向en1

指针调整中①②的次序没有任何限制;③④次序不能颠倒,同时对ep1和epN指针的调整必须在对lep的调整之前,否则会失去指针链表。

与之类似或者进行了扩展的宏还包括

APR_RING_INSERT_BEFORE(lep, nep, link),

该宏将结点nep插入到环形结构中的lep结点之前,从原来的…lep…变换为…nep…lep…。

APR_RING_INSERT_AFTER(lep, nep, link),

该宏将结点nep插入到环形结构中的lep结点之后,从原来的…lep…变换为…lep…nep…

APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link),

该宏将从ep1到epN的所有结点形成的双向环形链表链接到现有的环形链表hp之前,从原来的…hp…变换为…ep1…epN…hp。

APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link),

该宏将从ep1到epN的所有结点形成的双向环形链表链接到现有的环形链表hp之后,从原来的…hp…变换为…hp…ep1…epN…。

APR_RING_INSERT_HEAD(hp, nep, elem, link),

该宏将nep结点插入到环型链表hp的头部。

APR_RING_INSERT_TAIL(hp, nep, elem, link),

该宏将nep结点追加到环型链表hp的末尾。

APR_RING_CONCAT(h1, h2, elem, link),

该宏将两个环型链表h1,h2合并为一个新的环型链表,合并的时候h2追加到h2尾部。

APR_RING_PREPEND(h1, h2, elem, link)

该宏将两个链表h1,h2合并为一个新的环型链表,合并的时候h2插入到h1之前。

5.4删除结点

环型链表中结点的删除时基于宏APR_RING_UNSPLICE,其定义如下:

#define APR_RING_UNSPLICE(ep1, epN, link) do {

APR_RING_NEXT(APR_RING_PREV((ep1), link), link) =

APR_RING_NEXT((epN), link);

APR_RING_PREV(APR_RING_NEXT((epN), link), link) =

APR_RING_PREV((ep1), link);

} while (0)

该宏用于将ep1到epN的所有结点从双向链表中删除,删除包括两步:调整ep1的前一个结点的next指针指向epN的后一个指针;调整epN的后一个结点的prev指针指向ep1结点的前一个结点。

除此之外,删除结点还可以使用宏APR_RING_REMOVE实现:

#define APR_RING_REMOVE(ep, link)

APR_RING_UNSPLICE((ep), (ep), link)

5.5结点的遍历

结点的遍历从头结点开始,到尾结点结束。在链表中,如果某个结点的后继结点为“哨兵结点”的话,我们可以判断,该结点已经为最后一个结点,因此结点的遍历可以有两种途径:

ep = APR_RING_FIRST(hp);

while (ep != APR_RING_SENTINEL(hp, elem, link)) {

//循环体代码

ep = APR_RING_NEXT(ep, link);

}

或者

for ((ep) = APR_RING_FIRST((hp));

(ep) != APR_RING_SENTINEL((hp), elem, link);

(ep) = APR_RING_NEXT((ep), link))

{

//循环体代码

}

Apache中将第二种遍历实现定义为宏APR_RING_FOREACH:

#define APR_RING_FOREACH(ep, hp, elem, link)

for ((ep) = APR_RING_FIRST((hp));

(ep) != APR_RING_SENTINEL((hp), elem, link);

(ep) = APR_RING_NEXT((ep), link))

关于作者

张中庆,目前主要的研究方向是嵌入式浏览器,移动中间件以及大规模服务器设计。目前正在进行Apache的源代码分析,计划出版《Apache源代码全景分析》上下册。Apache系列文章为本书的草案部分,对Apache感兴趣的朋友可以通过flydish at sina.com.cn与之联系!

如果你觉得本文不错,请点击文后的“推荐本文”链接!!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有