当前位置: 首页 >> 应用软件 >> 网络相关 >> Apache中的哈希表剖析(2)

Apache中的哈希表剖析(2)

作者：来源：http://blog.csdn.net/tingya 发表时间：2006-03-06 浏览次数：字号：大 中 小

向量中真正的第一个和最后一个，那不是用户需要考虑的事情。

不过迭代子是范型技术的产物，是和C++紧密联系的，而Apache则是纯C编写的，因此当然不可能直接使用STL，不过它显然是受了STL的影响——它的目的就是使用C语言仿造一个哈希表上的迭代子，使得算法与细节分开。下面是APR中使用仿迭代子对哈希表ht进行遍历的代码：

apr_hash_index_t *hi;

for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) {

const char *k;

const char *v;

apr_hash_this(hi, (const void**)&k, NULL, (void**)&v);

printf("ht iteration: key=%s, val=%s\n", k, v);

}

在上面的代码中你根本就看不出哈希表的内部细节。这实际上也达到了我们前面提出的要求。

为了实现仿造的效果，哈希表中引入了一个辅助数据结构apr_hash_index_t，用于记录当前访问的结点的相关索引信息：

struct apr_hash_index_t {

apr_hash_t *ht;

apr_hash_entry_t *this, *next;

unsigned int index;

};

ht是当前访问的哈希表，index是当前访问的结点所在的哈希索引，值从0到max之间。this和next是这个结构的最重要的成员。this用以指向当前正在访问的结点，而next则指向按照深度遍历时this之后下一个将要被访问的结点。在整个遍历过程中，最重要的就是不断地调整this和next的指针，下面是可能出现的情况：

在分析上面的图示的时候，我们给出两个定义：直接后继结点和间接后继结点。

对于某个结点，它的直接后继结点就是可以通过next指针直接获取的结点。比如上图的(1)-(4)，this结点的直接后继结点都是NULL，而(5)中，this的直接后继存在，且为next。

对于某个结点，它的间接后继结点就是按照前述的哈希表深度遍历访问顺序中的下一个结点。对于图(5)，this的间接后继结点就是它的直接后继结点。下表给出了上图中的各个直接后继和间接后继结点的情况：

图	直接后继结点		间接后继结点
(1)	NULL		NULL
(2)	NULL		Not NULL
(3)	NULL		NULL
(4)	NULL		Not NULL
(5)	Not NULL	Not NULL

从上表可以看出(1)-(4)图可以归结为一个大类，那就是this的直接后继都是为NULL，这导致this结点和next结点位于不同的索引链表中，而(5)则是另外一个大类，它的直接后继不为NULL，这导致this和next位于同一链表中。对于给定的this结点，如何获取它的下一个结点？？Apache中使用apr_hash_next函数来获取this结点的下一个结点：

APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)

{

hi->this = hi->next;

while (!hi->this) {

if (hi->index > hi->ht->max)

return NULL;

hi->this = hi->ht->array[hi->index++];

}

hi->next = hi->this->next;

return hi;

}

this结点由传入参数hi指定，函数内部计算this的next结点，并继续通过hi返回出去。函数中正是利用了上面所说的分类规律：

■ while循环用于处理上图的(1)(2)(3)(4)四种情况，如果直接后继为NULL，则直接跳至下一个索引链表工作，直到索引为max为止。

■ hi->next=hi->this->next用以处理直接后继不为NULL的情况，那么此时只需要调整next就可以了。

除了apr_hash_next之外，Apache中还提供了另外两个辅助函数apr_hash_first和ap_hash_this。apr_hash_first主要为遍历整个哈希表作必要的准备，并返回整个哈希表的第一个元素的索引结构apr_hash_index_t。该函数需要两个参数：内部索引分配所需要的内存池以及需要遍历的哈希表：

APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_pool_t *p, apr_hash_t *ht)

{

apr_hash_index_t *hi;

if (p)

hi = apr_palloc(p, sizeof(*hi));

else

hi = &ht->iterator;

hi->ht = ht;

hi->index = 0;

hi->this = NULL;

hi->next = NULL;

return apr_hash_next(hi);