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

3/23/2008来源:软件工程人气:4818

3.2表格(TABLE)
3.2.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而已。下面我们来看看表格是如何进行操作的。
3.2.2创建表格
    为了创建一个表格,我们可以使用函数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与之联系!

假如你觉得本文不错,请点击文后的“推荐本文”链接!!