Apache中的表格实现剖析(2)

3.2.3表格元素查找

    表格元素查找是表格的一个非常重要的功能。目前存在很多的线性表查找算法，最基本的无非三种：顺序查找，二分查找以及哈希查找。相对而言，顺序查找是最简单也是最轻易实现，但是其通常在插入数据时候较为快捷，而查找的时候则就相对较慢。二分查找是一个较快的查找方法，但是其前提必须数据进行排序，因此排序使得插入较慢，因此也不是所有场合均适合。而哈希查找则既实现简单，又插入和查找速度较快。因此在Apache中队表格的插入和查找则采取了哈希算法。

Apache中在表格中查找一个键值为key的元素的函数为apr_table_get，其定义如下：

APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)

{

    apr_table_entry_t *next_elt;

    apr_table_entry_t *end_elt;

    apr_uint32_t checksum;

    int hash;

 

    if (key == NULL) {

     return NULL;

    }

    hash = TABLE_HASH(key);

    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {

        return NULL;

    }

    COMPUTE_KEY_CHECKSUM(key, checksum);

    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;

    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];

 

    for (; next_elt <= end_elt; next_elt++) {

     if ((checksum == next_elt->key_checksum) &&

            !strcasecmp(next_elt->key, key)) {

         return next_elt->val;

     }

    }

    return NULL;

}

    正如前面的apr_table_entry_t中看到的，对于表格中的每一个元素我们都维护一个key成员，为字符指针变量，该key用来标识该元素，在Apache中由于答应重复key的存在，因此在表格中可能存在多个key相同的元素，不过apr_table_get函数只返回查找到的第一个符合要求的元素。

    对于任何一个键值，我们可以通过TABLE_HASH(key)找到对应元素在表格中存放的索引。 TABLE_HASH为一个宏，定义为(TABLE_INDEX_MASK & *(unsigned char *)(key))。一旦得到哈希索引hash，函数将判定该索引所定应的内存块是否已经被初始化。假如该索引块还没有初始化，则理所当然，里面什么都没有，也就没法取了，此时直接返回NULL。

    当然假如内存中确实有“货”可用，则函数将进一步调用宏COMPUTE_KEY_CHECKSUM(key, checksum)来计算键值key所对应的校验值，校验结果即为checksum，该checksum主要作为宏TABLE_HASH的参数。

现在我们再往返顾前面提到的apr_table_t中的剩余的两个辅助成员变量：

int index_first[TABLE_HASH_SIZE];

int index_last[TABLE_HASH_SIZE];

    前面我们提到这二个辅助成员主要用在加速对表格中成员的查找，那么我们现在看看这两个成员变量是如何实现查找加速的。

    我们首先来看宏TABLE_HASH(key)的实现：

    #define TABLE_HASH(key) (TABLE_INDEX_MASK & *(unsigned char *)(key))

    从上面的哈希值得计算中可以看出，不管对于任何一个键值key，只有该键值的第一个字母参与了运算，因此比如对于“hello”和“house”而言，其计算出来的结果都是8。我们将整个表格分为多个“类别”，这些类别通过TABLE_HASH(key)进行区分，实际上也就是按照key的第一个字母进行分类。因此“hello”和“house”属于同一个类，而和“cat”则属于不同的类别。Apache中对键值的查找是基于类别进行的。假如一个类别在表格中具有多个元素，那么毫无疑问，肯定就发生了哈希冲突。

    为了解决索引冲突的问题，apr_table_t中引入index_first和index_last数组，分别记录给定的类别在表格中的起始索引和终止索引。对于某个类别，比如“h”类别(所有的以h开始的键值都属于这个类)，它在index_first和index_last中的索引可以通过TABLE_HASH(key)计算得到，结果为8。因此整个表格中第一个h类元素在表格中的索引保存在index_first[8](即index_first[TABLE_HASH(key)]中，而最后一个h类的成员的索引则保存在index_last[8]中。同理假如对于“c”类别，它的TABLE_HASH(key)为3，因此整个表格的第一个c类元素的索引则保存在index_first[3]中，最后一个在保存在index_last[3]中。

    比如，目前在表格中仅存在三个键值以字母h开头，分别为“house”、“hello”、“horse”，它们在表格中的索引分别为7、9、12，同时还存在四个以c开始的键值，分别是“cat”、“copy”、“catch”、“cite”，它们在表格中的索引分别为5、6、8、10。对于h类而言，它们对应的index_first中的索引为8，值为7，意味着所有的以h开始的键值第一次出现是在表格的索引为7的位置，同样从上表可以看出，所有以c开始的键值第一次出现是在表格的索引为5的位置。同样对于h类而言，它们对应的index_last中的索引也是8，值为12，意味着表格中最后一个以h开始的键值在表格中的索引为12，同时，表格中的最后一个以c起始的键值的索引是10。

    假如现在需要查找”hello”，经过COMPUTE_KEY_CHECKSUM(key, checksum)计算后，它的checksum为8。因此函数此时将检查index_first[8]和index_last[8]中的数据，如图，分别为7和11。这意味着所有的以’h’开始的键值都在表格的第 7和第11之间，因此此时只需要搜索索引从7到11的元素就可以了。

    一旦明确index_first和index_last数组的用途，我们就可以使用这两个数组加快搜索速度。比如假如需要搜索“hello”，我们不再需要从第一个元素查找到最后一个元素，相反，我们仅仅需要搜索表格中索引位于index_first[TABLE_HASH(“hello”)]和index_last[TABLE_HASH(“hello”)]之间的元素，即表格中第7个和第12个之间的元素。通过这种策略，可以大大缩小查询的范围。对于缩小范围之内的查找，我们则使用普通的查找方法，逐一比较。

上述算法的实现代码如下：

next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;

end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];

for (; next_elt <= end_elt; next_elt++)

{

if ((checksum == next_elt->key_checksum) &&!strcasecmp(next_elt->key, key))

{

return next_elt->val;

}

}

    在进行比较的时候，上面的代码采取了一定的变通。正常情况下，将需要查询的键值与查询范围内的每一个字符串键值进行比较的时候可以调用strcmp实现，对于Apache而言则就是strcasecmp。为了能够加快查找的速度，Apache中对于每一个字符串，取其前面的4个字符计算该字符串的校验码：

#define COMPUTE_KEY_CHECKSUM(key, checksum)    \

{                                              \

    const char *k = (key);                     \

    apr_uint32_t c = (apr_uint32_t)*k;         \

    (checksum) = c;                            \

    (checksum) <<= 8;                          \

    if (c) {                                   \

        c = (apr_uint32_t)*++k;                \

        checksum = c;                         \

    }                                          \

    (checksum) <<= 8;                          \

    if (c) {                                   \

        c = (apr_uint32_t)*++k;                \

        checksum = c;                         \

    }                                          \

    (checksum) <<= 8;                          \

    if (c) {                                   \

        c = (apr_uint32_t)*++k;                \

        checksum = c;                         \

    }                                          \

    checksum &= CASE_MASK;                     \

}

    宏COMPUTE_KEY_CHECKSUM计算给定key的校验码checksum，因此对于任何的字符串比较都会分为两个步骤：

    checksum == next_elt->key_checksum) &&!strcasecmp(next_elt->key, key

    首先比较它们的校验码，即前四个字符，假如相等，才会进一步调用strcasecmp进行比较；假如校验整数值不相等，那么就没有必要调用strcasecmp进一步比较。由于整数之间的比较速度比较快，因此通过这种两阶段比较能够有效的提高比较速度。

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