Apache中的哈希表剖析(3)

转载请注明来源:http://blog.csdn.net/tingya

3.4.5哈希表合并

在Apache中经常需要将两个哈希表合并为一个新的哈希表，为此APR中提供了专门的哈希合并函数apr_hash_merge，该函数定义如下：

APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,

const apr_hash_t *h1,

const apr_hash_t *h2,

void * (*merger)(apr_pool_t *p,

const void *key,

apr_ssize_t klen,

const void *h1_val,

const void *h2_val,

const void *data),

const void *data);

h1和h2是两个需要进行合并的哈希表。由于某个键可能同时出现在h1和h2中，而合并后的哈希表中只允许存在一次，因此在新的合并后的哈希表中如何处理h1和h2中相同的键是必须考虑的事情。参数中的merge函数用来处理这种情况。data是传递个合并函数merger的额外参数。

{

apr_hash_t *res;

apr_hash_entry_t *new_vals = NULL;

apr_hash_entry_t *iter;

apr_hash_entry_t *ent;

unsigned int i,j,k;

res = apr_palloc(p, sizeof(apr_hash_t));

res->pool = p;

res->free = NULL;

res->hash_func = base->hash_func;

res->count = base->count;

res->max = (overlay->max > base->max) ? overlay->max : base->max;

if (base->count + overlay->count > res->max) {

res->max = res->max * 2 + 1;

}

res->array = alloc_array(res, res->max);

if (base->count + overlay->count) {

new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *

(base->count + overlay->count));

}

从大的角度而言，哈希表的合并非常简单：首先创建一个新的哈希表，然后将需要合并的哈希表填入到新哈希表中。创建新的哈希表可以分为三个步骤：

1)、创建apr_hash_t结构。这个可以通过apr_palloc实现，非常简单。

2)、初始化apr_hash_t内部的array数组。数组的大小取决于两方面：

■ 暂时将新哈希表的容量max设定为两个需要合并的哈希表中容量max最大的。

■ 如果现有的两个哈希表中已经使用的元素个数总和超过max，那么max个元素不足以存放两个哈希表中所有的元素，因此最终的容量调整为max*2 + 1。

3)、合并的两个哈希表中apr_hash_entry_t结点数目为bash->count + overlay->count，因此它们所占用的总内存大小为sizeof(apr_hash_entry_t)*(base->count+overlay->count)。合并前，两个哈希表中所有结点都是用链表方式保存，而在合并后所有的结点都用连续内存块保存，这点与前面的哈希表拷贝非常相似。

4)、一旦分配了需要的内存块，我们就必须调整array数组中的指针指向实际的内存。

j = 0;

for (k = 0; k <= base->max; k++) {

for (iter = base->array[k]; iter; iter = iter->next) {

i = iter->hash & res->max;

new_vals[j].klen = iter->klen;

new_vals[j].key = iter->key;

new_vals[j].val = iter->val;

new_vals[j].hash = iter->hash;

new_vals[j].next = res->array[i];

res->array[i] = &new_vals[j];

j++;

}

}

函数首先将第一个哈希表中的所有结点拷贝到上述的内存块中，同时调整array数组中的指针指向这些内存块。拷贝后的内存布局如下所示。

从下图中可以看出，对于源哈希表索引index链表，结点在链表中出现的顺序与在内存块中出现的顺序正好相反：源哈希中array[index]是链表中第一个结点的地址，而在目标哈希表中，array[index]则是链表中的最后一个结点的地址；

在第一次的拷贝中，另外一个重要的方面就是索引不变性。任意一个结点，如果在源哈希表中的索引为index，则它在新哈希表中的索引肯定也是index，这个可以下面的几行代码中看出：

i = iter->hash & res->max;

res->array[i] = &new_vals[j];

5)、当第一个哈希表拷贝到新哈希表后，对于第二个哈希表的处理就开始展开：

for (k = 0; k <= overlay->max; k++) {

for (iter = overlay->array[k]; iter; iter = iter->next) {

i = iter->hash & res->max ; u

for (ent = res->array[i]; ent; ent = ent->next) {

if ((ent->klen == iter->klen) &&

(memcmp(ent->key, iter->key, iter->klen) == 0)) {

if (merger) {

ent->val = (*merger)(p, iter->key, iter->klen,

iter->val, ent->val, data);

}

else {

ent->val = iter->val;

}

break;

}

}

if (!ent) {

new_vals[j].klen = iter->klen;

new_vals[j].key = iter->key;

new_vals[j].val = iter->val;

new_vals[j].hash = iter->hash;

new_vals[j].next = res->array[i];

res->array[i] = &new_vals[j];

res->count++;

j++;

}

}

}

与第一个哈希表的简单拷贝相比，第二个哈希表的处理无非也是将其中的每一个结点拷贝到新的哈希表中，因此最外层的循环为：

for (k = 0; k <= overlay->max; k++) {

for (iter = overlay->array[k]; iter; iter = iter->next) {

……

}

对于每一个结点，函数首先计算它的哈希值i，如u，并根据该哈希值i作出进一步的处理：

1)、如果经过第一次的拷贝之后，新哈希表中索引为i的链表仍然为NULL，那么该结点将直接插入索引i链表中。

2)、如果新哈希表中索引i链表已经存在，那么此时的处理又出现了进一步的分化：

■ 如果在索引i链表中存在一个与当前结点完全相同的结点(键长度相等，且键值完全相同)，那么这种情况称之为键冲突，即哈希表1和哈希表2中存在完全相同的结点。对于这种情况通常的处理是由专门的合并函数merger完成，不过如果没有定义该合并函数，默认情况是否直接覆盖val。

■ 如果当前结点在索引i链表中不存在，那么此时意味着这是一个新结点，此时将其追加到索引i链表的尾部。比如哈希表2中的索引3链表，该链表中的结点最终插入到目标哈希表的10、11结点处。此时可以看到，10、11和第一个哈希表中的结点3不再连续，不过它们之间通过next关联在一起，如①所示。

最终合并后新哈希表的内存示意图如图所示。

3.4.6哈希表使用示例

下面的代码演示了哈希表的使用，包括下面几个方面：

1)、哈希表创建

2)、哈希表键/值增加

3)、哈希表键/值检索

4)、哈希表遍历

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <apr_general.h>

#include <apr_hash.h>

#include <apr_strings.h>

//在哈希表中增加、删除、修改元素

static void modify_hashtab(apr_hash_t *ht, apr_pool_t *mp)

{

apr_hash_set(ht, "foo", APR_HASH_KEY_STRING, "FOO");

apr_hash_set(ht, apr_pstrdup(mp, "bar"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "BAR"));

apr_hash_set(ht, apr_pstrdup(mp, "foobar"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "BAR"));

apr_hash_set(ht, apr_pstrdup(mp, "barfoo"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "FOO"));

/* To delete an entry, pass NULL as a value */

apr_hash_set(ht, apr_pstrdup(mp, "to-del"), APR_HASH_KEY_STRING, apr_pstrdup(mp, "TO-DEL"));

apr_hash_set(ht, "to-del", APR_HASH_KEY_STRING, NULL);

apr_hash_set(ht,apr_pstrdup(mp,"override"),APR_HASH_KEY_STRING,apr_pstrdup(mp,"old-val"));

apr_hash_set(ht,apr_pstrdup(mp,"override"),APR_HASH_KEY_STRING,apr_pstrdup(mp, "new-val"));

}

//迭代整个哈希表

static void iterate_hashtab(apr_hash_t *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);

}

}

int main(int argc, const char *argv[])

{

apr_pool_t *mp;

apr_hash_t *ht;

apr_initialize();

apr_pool_create(&mp, NULL);

ht = apr_hash_make(mp);

modify_hashtab(ht, mp);

{

const char *val = apr_hash_get(ht, "foo", APR_HASH_KEY_STRING);

printf("val for \"foo\" is %s\n", val);

}

iterate_hashtab(ht);

apr_pool_destroy(mp);

apr_terminate();

return 0;

}

程序运行结果如下：

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

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