Apache源代码分析——Apache数组[table.c]
Apache源代码分析——Apache数组[table.c]tingya | 18 一月, 2005 22:39
该文件主要分析了Apache中的重要的数据结构数组和表格
/////////////////////////////////////////////////////////////
//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来执行的。
///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////
