- 论坛徽章:
- 0
|
apache2.0源代码基础lib中的tables中代码分析，关于tables已经分析，见 http://blog.chinaunix.net/u/3629/article_5125.html
这个hash还是很简单的，提供的功能也很少，简单的介绍一下
主要有如下数据结构：
struct apr_hash_t {
apr_pool_t *pool;
apr_hash_entry_t **array;
apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
unsigned int count, max;
apr_hash_entry_t *free; /* List of recycled entries */
};
struct apr_hash_index_t {
apr_hash_t *ht;
apr_hash_entry_t *this, *next;
unsigned int index;
};
还有一个index的数据结构，用来遍历hash表
struct apr_hash_entry_t {
apr_hash_entry_t *next;
unsigned int hash;
const void *key;
apr_ssize_t klen;
const void *val;
};
hash的组织结构如下图：
解释一下每一个函数：
--------------------------------------------------------------------------------------------------------------------
static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max)
分配hansh的桶。注意只分配头指针，没有具体的空间
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool)
初始化hash表，调用alloc_array分配hash桶。
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi)
用来遍历hash表，这个遍历是按照桶号进行，0到max-1，具体的过程：
假设hi指定的元素是桶0的最后一个元素，那么他的next就是桶1的第一个元素，如果桶一没有元素，那就是
第二个桶，依次往后
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_pool_t *p, apr_hash_t *ht)
hash表的第一个元素，从桶0开始，如果桶0种没有元素，就到桶一中找，找到非空的第一个元素
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(void) apr_hash_this(apr_hash_index_t *hi,const void **key,apr_ssize_t *klen,void **val)
获取hi指向的元素的key，value；这个简单，就不说了
--------------------------------------------------------------------------------------------------------------------
static void expand_array(apr_hash_t *ht)
扩展桶，扩展桶数量，不是扩展实际的元素。如果原来是max个桶，会扩展到2*max个
在扩展的时候要注意将原有的元素重新分配到桶中，这时候就需要遍历老的桶，使用apr_hash_first和apr_hash_next
进行循环，将元素根据hash_key重新计算它所在的桶
--------------------------------------------------------------------------------------------------------------------
static apr_hash_entry_t **find_entry(apr_hash_t *ht,
const void *key,
apr_ssize_t klen,
const void *val)
查找key是否在hash中，存在就返回该节点，不存在，就会申请一个节点（是否申请新的节点取决于val是否为NULL。
因为这个函数有两个地方调用，一个是apr_hash_get，这时候是获取key对应的val，没有就没有，
还有就是apr_hash_set时存放新数据，没有，需要返回新的节点用来存储数据）在free list中有空闲，就使用free list
中的，不存在，申请内存。对应的代码片段
/* add a new entry for non-NULL values */
if ((he = ht->free) != NULL)
ht->free = he->next;
else
he = apr_palloc(ht->pool, sizeof(*he));
这个函数中，有一个关于计算hash的代码，比较简单，至于为什么使用33作为基数，也有说明，这儿就不解释了
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool,
const apr_hash_t *orig)
这个copy就是拷贝orig的数据返回。步骤也很简单，先调用apr_hash_make生成一个新的hash，遍历附值。
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(void *) apr_hash_get(apr_hash_t *ht,
const void *key,
apr_ssize_t klen)
获取key对应的val，比较简单。直接调用find_entry就可以了，找到了返回数据，没有此key，返回NULL
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(void) apr_hash_set(apr_hash_t *ht,
const void *key,
apr_ssize_t klen,
const void *val)
这个set有两个作用，第一个作用就是向hash中放入数据，第二个作用就是删除，第三个就是修改
在此函数中会调用find_entry(ht, key, klen, val)先查找key是否存在，如果存在就返回该节点，
不存在会分配一个节点，返回
会判断val是否为null，如果是null，就是删除此key，将这个节点放入free的list中，否则将新val放入此节点中。
注意这儿会进行一个操作：如果count的值大于max，就会扩展桶。这样做的目的就是防止桶后面的拉链太长，
就是冲突太多。
对应的代码片段为：
if (ht->count > ht->max) {
expand_array(ht);
}
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(unsigned int) apr_hash_count(apr_hash_t *ht)
获取表中的数据个数，直接返回count就可以了
--------------------------------------------------------------------------------------------------------------------
APR_DECLARE(apr_hash_t*) apr_hash_overlay(apr_pool_t *p,
const apr_hash_t *overlay,
const apr_hash_t *base)
和
APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p,
const apr_hash_t *overlay,
const apr_hash_t *base,
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)
将两个hash进行merge操作
-------------------------------------------------------------------------------------------------------------------- |
|
免费注册
发表于 2007-11-10 21:20
