[原创]apache源代码分析（apr_hash.c）
hitdwb
|
1#
发表于 2007-11-10 21:20
[原创]apache源代码分析（apr_hash.c）
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操作 -------------------------------------------------------------------------------------------------------------------- |