精通
英语
和
开源
，
擅长
开发
与
培训
，
胸怀四海
第一信赖
精通
英语
和
开源
，
擅长
开发
与
培训
，
胸怀四海
第一信赖
//Apache源代码分析——Apache数组table.c
//张中庆于西安交通大学软件所
//tingya$stu,xjtu,edu,cn,将$换成@,换成.防止地址被收集
//转载请保留出处
//最初出自西安交通大学兵马俑Linux版
//////////////////////////////////////////////////////////////该文件中定义了表格和数组的相关数据结构以及函数操作。表格用来保存应用程序中的各种数据结构，而数组则主要用来保存字符串链表。
关于表格的最重要的数据结构有两个。
struct apr_array_header_t {
apr_pool_t *pool;
int elt_size;
int nelts;
int nalloc;
char *elts;
};
Apr_array_header_t是数组组件的核心数据结构。Pool是分配数组内存的内存池。Elt_size是数组中每个元素的大小，而nelts则是当前数组中活动的数组的个数。Nalloc则是数组中分配空间的元素。当然数组中的非活动的数组个数则就是nalloc-nelts了。elts则指向实际的数组元素保存空间。
Apr_table_entry_t通常是作为apr_table_t表格的元素而存在的。Apr_table_t是apr_table_entry_t的“盛装”容易，其定义相对简单，结构如下：
///////////////////////////////////////////////////////////////////////////////////////
Apache的数组操作函数中最核心的函数就是make_array_core函数，其定义如下：
static void make_array_core(apr_array_header_t *res, apr_pool_t *p, int nelts, int elt_size, int clear)
函数用来生成一个数组，申请数组的内存从内存池p中申请，数组元素个数位nelts，每个元素的大小为elt_size。clar用来通知系统在创建内存之后是否进行初始化为0。
流程描述：
函数在确保nelts大于0之后，将从内存池p中为数组分配空间，如果clear为0，则调用apr_palloc，如果为1，则调用apr_pcalloc。两者的区别正好在于apr_palloc只管分配，不管初始化；而apr_pcalloc还需要多做一步初始化。分配的空间地址赋值给res参数。一旦获得分配的空间，函数将继续对里面的成员进行初始化，包括pool，elt_size，nelts以及nalloc。Nalloc用来记录已经分配的元素大小。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(void *) apr_array_pop(apr_array_header_t *arr)
{
//检查给定的数组是否为空
if (apr_is_empty_array(arr)) {
return NULL;
}
return arr->elts + (arr->elt_size * (--arr->nelts));
}
Apr_array_pop从数组重取出一个元素，该元素通过apr_array_header_t返回。Arr数组中的元素首地址始终是elts，每当在数组中增加新的元素的时候，elts所指向的内存空间大小将增加elt_size大小。因此当数组中的元素为nelts个的时候，elts的只想的总空间为elt_size*nelts大小。因此，最后一个元素的地址实际上就是(nelts-1)*elt_size。将该地址返回则将取得最后一个元素。
APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
该函数与apr_array_pop对应，用来往数组中压入新的数据。
流程描述：
函数在压入数组之前首先检查数组中是否有非活动的空闲元素空间，如果没有，即意味着nelts=nalloc，则必须创建新空间用来保存压入的数据，创建不是每次都创建一个元素空间，而是按照下面的原则创建：
(1) 如果当前压入的数据是第一个数据，即压入之前nalloc为0，则只创建大小为elt_size的空间，即一个元素的空间。
(2) 如果当前压入元素之前，系统已经分配了nalloc个单元，那么函数将直接批量一次性创建nalloc*2个元素空间，这样申请的空间实际上将达到3*nalloc*elt_size大小。
当然这些空间都得从内存池arr->pool中申请。一旦分配完这些空间，第一个可用的空闲空间则是第nalloc+1或者elt_size+1个元素。此时只需要将需要压入的元素拷贝到该地址空间即可，拷贝完之后，将elt_size加一，并返回新元素的地址。这真是下面的代码所完成的事情：
memcpy(new_data, arr->elts, arr->nalloc * arr->elt_size); memset(new_data + arr->nalloc * arr->elt_size, 0, arr->elt_size * (new_size - arr->nalloc)); arr->elts = new_data; arr->nalloc = new_size; /////////////////////////////////////////////////////////////////////////////////////// static void *apr_array_push_noclear(apr_array_header_t *arr
该函数与apr_array_push函数功能基本类似，其唯一区别正如函数名称，在于“noclear”。Arp_array_push在产生新的空闲块，压入新元素之前调用memset对新内存块进行清零操作，而”noclear”函数则省去了这一步。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(apr_array_header_t *) apr_array_copy(apr_pool_t *p,const apr_array_header_t *arr)
函数用来进行数组之间的拷贝，将数组arr拷贝到数组p中。
拷贝函数内部非常简单。首先定义一个arp_array_header_t的变量res，从内存池p中为其分配足够的空间，然后调用make_array_core生成一个与arr数组大小相同的数组，逐一进行内存拷贝。然后返回该空间。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(void) apr_array_cat(apr_array_header_t *dst,const apr_array_header_t *src)
该函数将数组dst和数组src进行合并，合并后src追加到dst的末尾。
流程描述：
函数需要做的第一件事情就是判断为了合并，函数是不是需要开辟新的空间。为此函数只需要检dst中的空闲元素是否足够存放src中非空闲的元素，即dst->nalloc-dst->nelts>=src->nelts，而不是dst->nalloc-dst->nelts>=src->nalloc。事实上，src中的空闲元素在拷贝的时候完全可以忽略，因为其本身不包含有效信息。如果dst足够大以至于完全可以容纳，那么函数需要做的只是将src中的非空闲元素逐一拷贝，否则增加空闲块的算法与apr_array_push类似，但是不完全相同，算法如下：
(1) 如果dst中元素个数为零，此时，将产生一个新的空间。
(2) 如果dst中元素个数nalloc不为零，则产生nalloc*2个空闲空间。
(3) 尽管如此，如果src的非空闲元素实在太多，而dst本身空闲空间很小，那么即使一次产生nalloc个空闲块也不一定能够盛放src中的元素。唯一的办法就是不停的产生新的空闲块，直到空闲块总数能够容纳src中的非空闲元素为止。这真是下面的代码所做的事情：
if (dst->nelts + src->nelts > dst->nalloc) {
int new_size = (dst->nalloc <= 0) ? 1 : dst->nalloc * 2;
while (dst->nelts + src->nelts > new_size) {
new_size *= 2;
}
}
一旦确定确定需要产生的空闲块的总数，函数将一次性从内存池dst->pool中申请。然后将src中的数据拷贝空间空间即可。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(int) apr_is_empty_array(const apr_array_header_t *a)
该函数通过给定的数组a是否为空。判断的方法很简单，就是检查a是否为NULL ，或者a->nelts是否为NULL。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p, int nelts, int elt_size)
该函数用来生成数组结构，生成的数组元素个数为nelts，每个元素空间为elt_size，函数返回生成的数组。
函数的内部执行实际上是通过调用make_array_core来执行的。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p, int nelts, int elt_size);函数描述：
该函数用来从内存池p中申请一块内存，创建一个数组，数组元素位nelts个，每个元素的大小位elt_size。
流程描述：
表格函数
关于表格的最重要的数据结构就是apr_table_t。表格内部是基于数组类型apr_array_header_t结构实现的。表格的第一个成员就是apr_array_header_t，而且必须是apr_array_header_t。之所以这样，是为了与原有的模块保持向后兼容。这样原有的模块即使将apr_table_t结构强制转换为apr_array_header_t类型的时候也不会发生任何异常。
struct apr_table_t {
/* they should use the apr_table_elts() function for most of the
* cases they do this for.
*/
apr_array_header_t a;
#ifdef MAKE_TABLE_PROFILE
void *creator;
#endif
/* An index to speed up table lookups. The way this works is:
* - Take the requested key and compute its checksum
* - Hash the checksum into the index:
* - index_first[TABLE_HASH(checksum)] is the offset within
* the table of the first entry with that key checksum
* - index_last[TABLE_HASH(checksum)] is the offset within
* the table of the first entry with that key checksum
* - If (and only if) there is no entry in the table whose
* checksum hashes to index element i, then the i'th bit
* of index_initialized will be zero. (Check this before
* trying to use index_first[i] or index_last[i]!)
*/
apr_uint32_t index_initialized;
int index_first[TABLE_HASH_SIZE];
int index_last[TABLE_HASH_SIZE];
};
creator用来跟踪表格的创建者。为了能够加快对表格的访问，结构中增加了三个辅助的成员变量，即index_initialized，index_first，index_last。Index_intialized是一个32位的整数，共有32X8个bit，系统用32x8位的每一位 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_table内部。
由于表格的核心数据结构还是apr_array_header_t结构，因此对表格的大部分操作实际上还是对数组类型的操作。只不过此时数组的每个元素结构变成了apr_table_entry_t。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(apr_table_t *) apr_table_make(apr_pool_t *p, int nelts)
该函数的功能非常明确，就是从内存池p中申请内存创建元素个数为nelts的表格，创建的表格由函数返回。
流程描述：
函数首先从内存池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)。
至此函数将创建了一个空空如也的表格，下面要做的就是往里面不断的放入apr_table_entry_t结构的数据了。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
该函数也是表格函数族中比较核心的函数之一，函数用来在表格apr_table_t中查找键值为key的元素。
流程描述：
通常情况下，对表格的查找无非包括三种：顺序查找，二分查找以及哈希查找。相对而言，顺序查找是最简单也是最容易实现，但是其通常在插入数据时候较为快捷，而查找的时候则就相对较慢。二分查找是一个较快的查找方法，但是其前提必须数据进行排序。因此也不是所有场合均适合。而哈希查找则既存在实现简单，又插入和查找速度较快。因此在Apache中队表格的插入和查找则采取了哈希算法。
对于表格中的每一个元素我们都维护一个key成员，为字符指针变量。函数通过TABLE_HASH(key)找到对应元素应该存放的索引。 TABLE_HASH为一个宏，定义为(TABLE_INDEX_MASK & *(unsigned char *)(key))。一旦得到哈希索引hash，函数将判断该索引所定应的内存块是否已经被初始化，这项工作通过宏TABLE_INDEX_IS_INITIALIZED(t, hash)来实现。如果该索引块还没有初始化，则里面什么都没有，也就没法取了。
当然如果内存中确实有“货”可用，则函数将调用宏COMPUTE_KEY_CHECKSUM(key, checksum);来计算键值key所对应的校验值，校验结果即为checksum。
现在我们再来回顾前面提到的apr_table_t中的三个辅助成员变量：
apr_uint32_t index_initialized; int index_first[TABLE_HASH_SIZE]; int index_last[TABLE_HASH_SIZE];
前面我们提到这三个辅助成员主要用在加速对表格中成员的查找，那么我们现在看看这三个成员变量是如何加速的。
Index_first和index_last都是整数型数组，其主要用来存放索引，即TABLE_HASH(checksum)的值。而从TABLE_HASH(checksum)的实现(TABLE_INDEX_MASK & *(unsigned char *)(key))我们可以看出一个很现实的问题，就是即使不同的键值key其得出的TABLE_HASH值也可能是相同的。比如“hello”和“house”计算出来的索引都是8，这是由于*(unsigned char *)(key))只取字符串的第一个字母决定的。为此TABLE_HASH即存在哈希冲突问题。为了解决这个问题apr_table_t中引入index_first和index_last。index_last[TABLE_HASH(checksum)]中的值则是表格中第一个键值的检验值为checksum的元素在相对于表格起始位置的偏移量。而index_last[TABLE_HASH(checksum)]则是表格中最后一个键值的校验值为checksum的元素的偏移量。当然在index_first[TABLE_HASH(checksum)]和index_last[TABLE_HASH(checksum)]之间可能还存在更多的类似的元素。不过我们已经缩小的搜索的范围。因此我们需要作的只是对index_first[TABLE_HASH(checksum)]和index_last[TABLE_HASH(checksum)]中的每一个元素逐一查找，看看它们的key_checksum和key是否同时与参数中的值相等，如果相等，表示找到，否则表示没有找到。下面的代码所作的工作正是上面所阐述的。
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;
}
}
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,const char *val)
该函数在表格中增加新的元素，元素的键值为key，值为val。
函数流程：
函数首先需要做的无非就是计算元素的校验值和在表格中的插入索引。校验值和哈希值分别用checksum和hash来保存。一旦得到哈希值，函数还得调用TABLE_INDEX_IS_INITIALIZED宏检查，看看索引hash的内存是否已经被初始化。如果没有初始化，则需要额外多做一些事情，首先调用TABLE_SET_INDEX_INITIALIZED将该索引内存初始化，同时增加新的内存单元。
如果该内存已经初始化，那么函数将键值为key的单元插入表格中。在插入之前，函数还需要判断该单元是否已经在表格中存在，为此，其必须进行查找，一旦查找到，则覆盖原有的单元。
///////////////////////////////////////////////////////////////////////////////////////
static void apr_table_cat(apr_table_t *t, const apr_table_t *s)函数描述：
该函数用来将两个表格进行合并，合并后的表格为t。
流程描述：
合并中首当其冲的是必须对两个表格中内置的数组进行合并，为此函数中调用apr_array_cat(&t->a,&s->a)，一旦数组进行合并之后，函数将根据合并的数组对表格中的各个成员进行调整以适应新的内置数组，这些调整包括对index_first和index_last以及index_initialized等的调整。
如果原有的表格t中没有任何的有效单元，即t->a.nelts为0，那么合并后的表格t中的index_first和index_last数组以及index_initiailized则直接从s中原封不动的拷贝。
如果表格t中原来就有数据，那么对于s中已经初始化过的单元，则意味着该单元已经被使用，因此index_first也就存在相应的记录，其不会受s的影响。因此我们需要修改的只有index_last数组。由于s中的元素都是追加到t的末尾，因此s中数组index_last中所表示的偏移量到了t中实际上得多偏移t->a.nelts个大小。而对于那些没有初始化的单元，则由于是将被第一次使用，因此我们只需要修改index_first数组的值。这真是下面的代码所作的事情：
for (idx = 0; idx < TABLE_HASH_SIZE; ++idx) {
if (TABLE_INDEX_IS_INITIALIZED(s, idx)) {
t->index_last[idx] = s->index_last[idx] + n;
if (!TABLE_INDEX_IS_INITIALIZED(t, idx))
{
t->index_first[idx] = s->index_first[idx] + n;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,const char *val);
APR_DECLARE(void) apr_table_addn(apr_table_t *t, const char *key,const char *val)
函数描述：
该函数在表格中增加单元，键值为key，值为val。函数在增加单元的时候完全不考虑该元素是否已经在表格中存在。
函数首先获取到键值对应的哈希值，并将t中的index_last对应的索引单元的值即该单元的偏移量设置为a.nelts，意味着该单元处于表格的最末尾处，代码即下：
t->index_last[hash] = t->a.nelts;
如果索引hash没有初始化，则还必须同时调用TABLE_SET_INDEX_INITIALIZED进行初始化，此外由于由于该单元是第一次使用，因此还必须修改index_first对应索引单元中的值：t->index_first[hash] = t->a.nelts。
至此设置完毕，我们可以明白，键值哈希为hash的单元其在表格中的第一个位置与最后一个位置都是位于表格的末尾。如果下次增加新的同hash值得单元时候，index_first将不变化，只有index_last数组变化。同样在查找的时候，也只需要查找index_first[hash]和index_last[hash]中的单元就可以了。
函数接着需要做的就是实实在在的将单元压入表格数组中，同时对其中的成员进行初始化，两者的区别在于下面的代码。apr_table_add中实现如下：
elts->key = apr_pstrdup(t->a.pool, key); elts->val = apr_pstrdup(t->a.pool, val); 而apr_table_addn中实现如下： elts->key = (char *)key; elts->val = (char *)val;
从中可以看出在设置之前，apr_table_add对其中的key和val进行了拷贝，并用拷贝值进行赋值。函数这样做的目的无非就是防止key和val被修改。而apr_table_addn中则直接赋值，为此，我们必须小心处理，确保单元加入表格之后key和val的值没有被修改。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,const char *val); APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,const char *val)
该函数用来将val合并到键值为key的单元的数据上面，如果表格中没有找到key的单元，函数的行为将与apr_table_add相同。
函数流程：
函数首先执行与查找类似的操作，在表格中找到第一个和最后一个键值为key的单元，一旦找到，再比较checksum是否相同。如果找到该单元，则调用apr_pstrcat(t->a.pool, next_elt->val, ", ",val, NULL);进行合并，所谓合并就是将val追加到原有的val的末尾。如果没有找到，函数将新增一个单元。
///////////////////////////////////////////////////////////////////////////////////////
APR_DECLARE(apr_table_t *) apr_table_overlay(apr_pool_t *p,const apr_table_t *overlay,const apr_table_t *base)
函数将表overlay和base合并为一个新的表格newtable，并将该表返回
流程描述：
函数的实现非常的简单，首先从内存池p中分配一块apr_table_t的空间，然后调用copy_array_hdr_core用overlay生成最初的新表，继而调用apr_array_cat将base追加到新表的末尾。此时追加完之后的表格就是合并之后的表格。
/////////////////////////////////////////////////////////////////////////////////////// APR_DECLARE_NONSTD(int) apr_table_do(apr_table_do_callback_fn_t *comp,void *rec, const apr_table_t *t, ...) /* * Iterate over a table running the provided function once for every * element in the table. If there is data passed in as a vararg, then the * function is only run on those elements whose key matches something in * the vararg. If the vararg is NULL, then every element is run through the * function. Iteration continues while the function returns non-zero. * @param comp The function to run * @param rec The data to pass as the first argument to the function * @param t The table to iterate over * @param ... The vararg. If this is NULL, then all elements in the table are *run through the function, otherwise only those whose key matches *are run. * @return FALSE if one of the comp() iterations returned zero; TRUE if all iterations returned non-zero * @see apr_table_do_callback_fn_t */ /////////////////////////////////////////////////////////////////////////////////////// APR_DECLARE(void) apr_table_compress(apr_table_t *t, unsigned flags)
该函数用来对给定的表格t进行压缩，压缩操作包括覆盖或者合并重复的单元。如果flags为APR_OVERLAP_TABLES_MERGE，则进行合并操作；如果flags为APR_OVERLAP_TABLES_SET，则进行覆盖操作。
函数描述：
函数将表t中的元素逐一拷贝到数组sort_next中，然后调用table_mergesort对数组进行排序，排序后的数组用sort_array表示。一旦排序完毕，函数将处理重复的键值。处理的算法如下：
(1) 对于排序后的数组中的每一个元素，用sort_next和last记录当前元素以及它的下一个元素，从key_checksum和key两个方面来进行比较，如果完成相等，则表明这两个这两个元素完全相同，此时修改dup_found=1表明遇到了重复的元素，同时用dup_last指向后一个元素。
(2) 一旦遇到重复的单元，由于整个数组是经过排序的，因此重复的单元都是连接在一起的。一旦我们发现到了两个重复的单元，那么我们则有必要继续往后查找，直到找到最后一个与之相同的元素。为此dup_last指针就是为这而存在。其继续往后查找，直到找到最后一个重复值。
(3) 一旦发现某个元素不属于重复元素，那么此时有必要将dup_last退后一个，指向真正的最后一个元素。重复的元素介于sort_next和dup_last之间。到此，对于压缩重复的元素，不管是覆盖还是合并都将变得简单。
(4) 对于重复的单元如果进行的是合并的策略，那么合并后的各个单元的val都追加到sort_next后面。比如如果从sort_next往后的各个单元的val分别为“I”，“am”，“a”，“boy”，则合并后的val的值为“I， am， a， boy， ”。为此在合并之前有必要知道合并后val的大小，这样才能从内存池中去申请。为了知道合并后的val长度，函数对从sort_next到dup_last的单元逐一累加。下面的代码就是为了这个目的。
do {
len += strlen((*next)->val);
len += 2; /* for ", " or trailing null */
} while (++next <= dup_last);
(5) 经过循环，最终的val分配长度保存在len中，函数紧接着调用apr_palloc(t->a.pool, len)分配空间new_value，然后再遍历一次重复的元素，将其中的每个元素都追加上去。
val_dst = new_val;
next = last;
for (;;) {
strcpy(val_dst, (*next)->val);
val_dst += strlen((*next)->val);
next++;
if (next > dup_last) {
*val_dst = 0;
break;
}
else {
*val_dst++ = ',';
*val_dst++ = ' ';
}
}
(6) 如果对于重复单元进行的是覆盖策略，则直接将dup_last的val值赋给last。最后函数将重复单元中的多余的单元的key设置为NULL。
(7) 对于所有的重复的元素都如此反复，当处理完毕的时候，表t中的所有的元素的个数仍然保持不变化，唯一变化的就是多了很多键值为NULL的空心单元，这些单元曾经是重复的单元。为此，想真正的对表进行压缩，还得将这些空心单元剔除出去。函数中设置了一个“纯洁”没有任何重复污染的表dst，在遍历表src的时候，只有遇到key不为NULL的时候才添加到dst中。一旦处理完毕，函数将调用table_reindex进行重新索引。
///////////////////////////////////////////////////////////////////////////////////////
static apr_table_entry_t **table_mergesort(apr_pool_t *pool, apr_table_entry_t **values, int n)
该函数属于内部函数，其用自顶向上的合并算法(bottom-up mergesort)对表values中的数据进行排序。为此，我们首先简单了解一下bottom-up mergesort排序算法。
事实上，任意给定的数组a都是由不多于n段自然有序的子数组拼接起来的，如就是由自然排好序的子数组，，和拼接起来的。而且可以在O(n)的时间里把这些子数组的界限找出来。因此我们不妨按照这种自然的有序段，通过调用Merge (c，d， l， m， r)反复地合并其相邻的两段，最后也可达到将 a 排序的目的。例如由⇒，，和⇒和 ⇒。