Apache中的哈希表剖析(1)
作者： 来源： 发表时间：2006-03-06
浏览次数：
字号：大 中 小
(apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
sizeof(*ht->array) * (orig->max + 1));
尽管称之为哈希表拷贝，但是apr_hash_copy实现的仅仅是一种影像拷贝。之所以称之为影像拷贝，是因为尽管拷贝后的哈希表能够实现与源哈希表相同的功能，但是内部数据组织已经发生了变化，最大的变化就是从源哈希表的不连续的链表结构转换为连续的块状结构。
既然是块状数据结构，我们首先就必须考虑块状结构的大小，然后才能分配。新的块状结构的大小应该与原有的链表结构大小相等。总的大小包括三方面：
1)、apr_hash_t结构的大小sizeof(apr_hash_t)
2)、apr_hash_t结构内array数组的大小，数组的总元素个数为max+1，每一个元素都是一个 apr_hash_entry_t类型的指针，因此整个数组的大小为(orig->max+1)*sizeof(*ht->array)，或者也可以写成(orig->max+1)*sizeof(apr_hash_entry_t*)。
3)、整个哈希表中apr_hash_entry_t类型结点的总数，其值由orig->count决定，每个结点的大小为sizeof(apr_hash_entry_t)，故总大小为sizeof(apr_hash_entry_t) * orig->count。
一旦确定了总的需要分配的内存大小，APR将从内存池中一次性分配足够的连续内存。这些内存将被分为三部分：apr_hash_t部分、max+1个apr_hash_entry_t指针部分以及count个哈希元素的大小。因此内存一旦分配完毕，除了使用原有哈希表结构成员初始化新的哈希表成员包括pool、count、max以及hash_func等之外，最重要的就是设置指针指向后面的两个内存部分，初始化后的布局如下所示：
1. j =0;
2. for (i = 0; i <= ht->max; i++) {
3. apr_hash_entry_t **new_entry = &(ht->array[i]); u
4. apr_hash_entry_t *orig_entry = orig->array[i];
5. while (orig_entry) {
6. *new_entry = &new_vals[j++];
7. (*new_entry)->hash = orig_entry->hash;
8. (*new_entry)->key = orig_entry->key;
9. (*new_entry)->klen = orig_entry->klen;
10. (*new_entry)->val = orig_entry->val;
11. new_entry = &((*new_entry)->next); v
12. orig_entry = orig_entry->next;w
13. }
14. *new_entry = NULL;
15. }
16. return ht;
在源哈希表中，ht->array数组中的每一个元素都是一个apr_hash_entry_t类型的指针，指向的是一个链表，而到了目标哈希表中，该指针指向的则是一个数组。因此，拷贝的一个重要任务就是调整array数组中的各个指针将其指向new_vals内存的适当的部分。调整后的布局如下图所示。
调整过程包括三个大步骤，图示中用jkl进行标识：
j array数组中的每一个元素都是一个指针，必须调整数组中的每一个指针指向new_vals部分的合适的位置。原则是：如果源哈希表中对应元素为NULL，则新指针也为NULL；如果对应的结点链表结点数目为n，则下一个索引指针与前一个偏移n*sizeof(apr_hash_entry_t)个。具体如灰色代码部分所示。
k 对每一个结点进行内容拷贝，如7.8.9.10行。
l 调整各个结点内部的next指针，指向它的直接后继结点，或者是紧靠它的下一个apr_hash_entry_t结点，或者是NULL。
new_entry = &((*new_entry)->next);
在上图中我们用虚线将链表结构和块状结构中对应得结点连接起来，以方便对比。
中国源码网: 中国人的开放源代码社区
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
