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

    尽管apr_array_header_t数组已经可以完成大部分的任务，但是对于Apache而言，apr_array_header_t更倾向于内部数据结构，它通常作为其余的线性数据结构的实现基础，比如表格、队列以及哈希表。表格是Apache中用的最频繁的数据结构，比如HTTP请求中的域以及配置文件中的命令都是通过表格进行保存的。不过与通常的表格的含义不太相似，Apache表格更加与perl中的哈希表相似，唯一的区别就是在Apache表格中同样的键值你可以存在两次，而且表格是大小写字母敏感的。

    Apache中表格的数据结构是apr_table_t结构，该结构在apache的apr_table.h中定义如下：

strUCt apr_table_t {

apr_array_header_t a;

#ifdef MAKE_TABLE_PROFILE

void *creator;

#endif

apr_uint32_t index_initialized;

int index_first[TABLE_HASH_SIZE];

int index_last[TABLE_HASH_SIZE];

};

    从表格的结构可以看出，表格的内部还是数组结构，表格的各种操作实质上无非就是对数组元素操作的一种封装而已。为了保持向下兼容，apr_array_header_t必须位于表格结构的首部。由于表格结构是Apache中新的数据结构，因此假如需要某些旧的只支持数组的版本假如需要使用表格，只要使用将apr_table_t强制转换为apr_array_header_t结构就可以了。

    creator用来跟踪表格的创建者。另外为了能够加快对表格的访问，结构中增加了三个辅助的成员变量，即index_initialized，index_first，index_last。index_intialized是一个32位的无符号整数，共对应了32 Í 8个bit，系统中用256位中的第n位来记录当前分配空间的第n个元素是否已经被初始化，假如初始化，该位为1，否则0。因此我们可以看到表格中的元素最多也只能为256个。

    表格中的一个元素要被使用之前必须对其所在的区域进行初始化，初始化非常的简单，只是将index_initialized中对应的bit位置为1即可。可以通过宏TABLE_SET_INDEX_INITIALIZED实现初始化。

    #define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized = (1 << (i)))

    而判定一个对应的元素是否被初始化，则用宏TABLE_INDEX_IS_INITIALIZED实现：

    #define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))

    index_last和index_first数组的用法我们在后面的部分会具体描述。

    表格中存放的每一个元素用结构apr_table_entry_t描述：

    struct apr_table_entry_t {

char *key;

char *val;

apr_uint32_t key_checksum;

    };

    结构中，key是键值，目前用来标记表格中的每个元素，通常只有在对表格中的元素进行迭代的时候才能对该值进行检查。在以后的版本中，该值可能被设置为NULL。val则是当前元素的值。Key_checksum则是对键值key的校验值，一般在表格内部使用。

    由于表格的核心数据结构还是apr_array_header_t结构，因此对表格的大部分操作实际上还是对数组类型的操作。只不过此时数组的每个元素结构变成了apr_table_entry_t而已。下面我们来看看表格是如何进行操作的。

    为了创建一个表格，我们可以使用函数ap_make_table和apr_make_table，前者适用于Apache1.3，后者适用于2.0版本。函数定义生命如下：

APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)

{

    apr_table_t *t = apr_palloc(p, sizeof(apr_table_t));

    make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0);

#ifdef MAKE_TABLE_PROFILE

    t->creator = __builtin_return_address(0);

#endif

    t->index_initialized = 0;

    return t;

}

    函数首先从内存池p中分配处apr_table_t结构大小的内存块，然后调用make_array_core(&t->a, p, nelts, sizeof(apr_table_entry_t), 0)为创建apr_table_t的内部数组a，数组个数为nelts个，每个元素的大小为sizeof(apr_table_entry_t)。假如nelts为零，函数将推迟内存分配直到表格第一次使用为止。正如在数组部分看到的，表格会自动的分配其需要的内存空间，而不需要手工干涉。另外数组创建之后index_initialized被初始化为0，此时没有任何数据被使用。

    下面的代码演示了表格的创建操作：

    apr_table_t *my_table;

    my_table = apr_table_make(r->pool,10);

    至此函数将创建了一个空空如也的表格，下面要做的就是往里面不断的放入apr_table_entry_t结构的数据了。

    除了可以从头开始创建一个新的表格，Apache中还答应从一个原有的表格创建一个相同的表格，我们称之为表格复制。表格复制实现如下：

APR_DECLARE(apr_table_t *) apr_table_copy(apr_pool_t *p, const apr_table_t *t)

{

    apr_table_t *new = apr_palloc(p, sizeof(apr_table_t));

 

    make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);

    memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));

    new->a.nelts = t->a.nelts;

    memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);

    memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);

    new->index_initialized = t->index_initialized;

    return new;

}

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