Apache中的环形链表

boss44

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就通过两个环形域位于两个双向链表中：
http://asp.6to23.com/vcprogram/image/ring0.png
另外，由于环形链表的的特殊性决定了没有绝对的起点和终点，但是为了操作的方便性，我们我们还是有必要定义一个链表头，这样只要找到链表头，就可以很方便的对环形链表进行操作了。Apache中链表头定义如下：
#define APR_RING_HEAD(head, elem)  \
struct head {   \
struct elem *next; \
struct elem *prev; \
}
与普通的元素结点相比，头结点显然只包含了前面所说的“环域”，而不包括实际的数据域。头结点通常位于环链表首结点的前面，同时位于尾结点的后面。
http://asp.6to23.com/vcprogram/image/ring1.png
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作为头结构，直接位于首尾存储段之间，它们的示意图如下：
http://asp.6to23.com/vcprogram/image/ring2.png
从上面的图示中我们可以看到头存储段的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感兴趣的朋友可以通过flydish1234 at sina.com.cn与之联系!
如果你觉得本文不错，请点击文后的“推荐本文”链接！！