Apache基础数据结构(tables)代码浅析 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> Apache基础数据结构(tables)代码浅析

Apache基础数据结构(tables)代码浅析

浏览:1881次出处信息

提到Apache社区脑子里立马会呈现出一系列的Java项目集合,尽管@gnawux师兄教导我不要纠结于语言,但对于Java的抵制还是很难一下子就消失的，所幸Apache社区最重量级的项目Apache开源HTTP服务器httpd的源代码是完全使用C语言开发的，尽管近年来涌现出种种轻量级高性能Web服务器，Apache仍以它的功能广泛和真正的高性能而处于无可取代的位置。

Apache也经常受人诟病，矛头直指它的低效，我没有太多这方面的经验，因此没有过多的发言权，看到一些大牛们对这个问题的评论是觉得Apache低效是因为对Apache缺少了解。我个人也觉得这样一款多年风行Web服务器领域的软件肯定有它存在的理由，我们认为它不好可能是我们对它的了解不够。

在网上看到过关于Apache源码是否值得阅读的讨论，很多人认为Apache源码组织结构不好，不太适合阅读，更多人推荐nginx等源码，其实我觉得像Apache这种项目正是”重剑无锋，大巧不工“，Linux源码也有人评价说组织的不好，可读它的代码也仍然非常有意义。我个人认为阅读Apache源码一方面能加深对Apache的了解，在使用的时候真正发挥出它的高性能，另一方面也能借鉴它作为大型服务器软件设计的方法。当然，如果要编写扩展模块来实现一些附加功能的话那阅读源码甚至是必须的工作。

以上都是我个人的理解，最近简单地翻阅了部分代码，长时间没有更新博客，这里就写一些Apache里面最基本的tables数据结构(和其它模块关联较小，相对比较独立，当然我也觉得读任何源码都应该先搞清楚它最基础的数据结构)。

C语言里面没有类似于STL的vector这样的数据结构，动态数组肯定是需要自己来实现的。看一下apache里面关于动态数组结构的定义：

struct apr_array_header_t {
    /** The pool the array is allocated out of */
    apr_pool_t *pool;
    /** The amount of memory allocated for each element of the array */
    int elt_size;
    /** The number of active elements in the array */
    int nelts;
    /** The number of elements allocated in the array */
    int nalloc;
    /** The elements in the array */
    char *elts;
};

pool是内存池，apache有自己的内存管理机制，它在内存池中分配内存，而不是直接使用malloc分配，内存池由apache统一进行管理，这是后话，现在只需要知道在apache中如果要申请一块内存空间就必须有一个对应的内存池。

elt_size是数组中每个元素的大小。

nelts是数组中活跃元素的个数。何为活跃元素？相对于nalloc来看，nalloc是数组中分配空间的元素个数，它在数组创建的时候会先分配nalloc个元素的空间，而这些内存空间仅仅分配而未进行初始化，也就是nelts为0，当往数组中插入元素时，nelts会递增，nelts也就是数组中实际存在的元素个数。当nelts个数大于nalloc时，则表明数组中已分配的内存空间不够，则需要再从内存池中申请额外的空间来扩充数组的容量。

elts便指向元素列表的起始地址。

创建一个数组：

APR_DECLARE(apr_array_header_t *) apr_array_make(apr_pool_t *p,
						int nelts, int elt_size)
{
    apr_array_header_t *res;
 
    res = (apr_array_header_t *) apr_palloc(p, sizeof(apr_array_header_t));
    make_array_core(res, p, nelts, elt_size, 1);
    return res;
}
 
static void make_array_core(apr_array_header_t *res, apr_pool_t *p,
			    int nelts, int elt_size, int clear)
{
    /*
     * Assure sanity if someone asks for
     * array of zero elts.
     */
    if (nelts < 1) {
        nelts = 1;
    }
 
    if (clear) {
        res->elts = apr_pcalloc(p, nelts * elt_size);
    }
    else {
        res->elts = apr_palloc(p, nelts * elt_size);
    }
 
    res->pool = p;
    res->elt_size = elt_size;
    res->nelts = 0;		/* No active elements yet... */
    res->nalloc = nelts;	/* ...but this many allocated */
}

上面的两个函数功能都很清晰，没有什么需要解释的，只是分配内存用的是apr_palloc()和apr_pcalloc()两个函数从内存池中分配内存，这两个函数的区别是后者在分配了内存之后会先清零，这也就是那个clear参数的作用了。

往数组中压入元素：

APR_DECLARE(void *) apr_array_push(apr_array_header_t *arr)
{
    if (arr->nelts == arr->nalloc) {
        int new_size = (arr->nalloc <= 0) ? 1 : arr->nalloc * 2;
        char *new_data;
 
        new_data = apr_palloc(arr->pool, arr->elt_size * new_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;
    }
 
    ++arr->nelts;
    return arr->elts + (arr->elt_size * (arr->nelts - 1));
}

上面提到如果数组中活跃元素已经占满了所有的已分配的内存空间之后，便需要向内存池申请额外的内存才能便新元素得已插入，apache的做法也很简单，申请双陪的内存，将旧内存中的内容copy到新内存中的前半部分，后半部分清零，或不做处理(apr_array_push_noclear()函数)。然后就是增加活跃元素数，返回最新元素的内存地址。

还有一系列关于数据操作的函数，apr_array_pop()从数组中弹出元素，apr_array_cat()连接两个数组，apr_array_copy()拷贝一个数组，原理都很简单，不再一一赘述，详情可见srclib/arp/tables/apr_tables.c

接下来看apache里面另一个很重要的数据结构，一个类似于数据字典的table，但它允许有多个相同健的元素存在。

struct apr_table_t {
    /* This has to be first to promote backwards compatibility with
     * older modules which cast a apr_table_t * to an apr_array_header_t *...
     * they should use the apr_table_elts() function for most of the
     * cases they do this for.
     */
    /** The underlying array for the table */
    apr_array_header_t a;
    /** Who created the array. */
    void *creator;
    /* An index to speed up table lookups.  The way this works is:
     *   - Hash the key into the index:
     *     - index_first[TABLE_HASH(key)] is the offset within
     *       the table of the first entry with that key
     *     - index_last[TABLE_HASH(key)] is the offset within
     *       the table of the last entry with that key
     *   - If (and only if) there is no entry in the table whose
     *     key 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];
};

数据表中的元素是存放在变量名为a的数组中的。creator是该数据表的创建者，通常是个字符串。最后的三个字段是比较有学问的字段。TABLE_HASH_SIZE宏的大小定义为32，index_initialized变量也是一个32位的常数，该变量用于对每个key的hash值进行一个映射，key的hash算法很简单：

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

相当于把key的前8个字节转换成整形再与32求余，最后结果是一个小于32的整数。于是，当表中存在某个key时，假设key对应的hash值i，则index_initialized的第i位是被置位的，这样可以快速地检测某个key是否在表中存在。

至于index_first和index_last这两上数组中存储的是某个hash值所对应的元素在a数组中的索引范围(肯定是需要一个范围的，32个元素的hash表非常容易出现碰撞)。如果key对应的hash值为4，而index_first[4]=22，index_last[4]=26，则要查找的元素在a数组中第22个元素到第26个元素之间。至于index_last和index_first最面的值是怎么确定的接下来讨论。

需要提一下的是a数组中每一个元素都是一个apr_entry_t结构：

struct apr_table_entry_t {
    /** The key for the current table entry */
    char *key;          /* maybe NULL in future;
                         * check when iterating thru table_elts
                         */
    /** The value for the current table entry */
    char *val;
 
    /** A checksum for the key, for use by the apr_table internals */
    apr_uint32_t key_checksum;
};

我们看下是如何获取某个健值的：

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;
}

程序遍历index_first[hash]和index_last[hash]区间内的链表，通过比对健值来获取要寻找的值。

接下来看设置某个健值的函数，稍微复杂一点：

APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
                                const char *val)
{
    apr_table_entry_t *next_elt;
    apr_table_entry_t *end_elt;
    apr_table_entry_t *table_end;
    apr_uint32_t checksum;
    int hash;
 
    COMPUTE_KEY_CHECKSUM(key, checksum);
    hash = TABLE_HASH(key);
    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
        t->index_first[hash] = t->a.nelts;
        TABLE_SET_INDEX_INITIALIZED(t, hash);
        goto add_new_elt;
    }
    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];
    table_end =((apr_table_entry_t *) t->a.elts) + t->a.nelts;
 
    for (; next_elt <= end_elt; next_elt++) {
	if ((checksum == next_elt->key_checksum) &&
            !strcasecmp(next_elt->key, key)) {
 
            /* Found an existing entry with the same key, so overwrite it */
 
            int must_reindex = 0;
            apr_table_entry_t *dst_elt = NULL;
 
            next_elt->val = apr_pstrdup(t->a.pool, val);
 
            /* Remove any other instances of this key */
            for (next_elt++; next_elt <= end_elt; next_elt++) {
                if ((checksum == next_elt->key_checksum) &&
                    !strcasecmp(next_elt->key, key)) {
                    t->a.nelts--;
                    if (!dst_elt) {
                        dst_elt = next_elt;
                    }
                }
                else if (dst_elt) {
                    *dst_elt++ = *next_elt;
                    must_reindex = 1;
                }
            }
 
            /* If we\'ve removed anything, shift over the remainder
             * of the table (note that the previous loop didn\'t
             * run to the end of the table, just to the last match
             * for the index)
             */
            if (dst_elt) {
                for (; next_elt < table_end; next_elt++) {
                    *dst_elt++ = *next_elt;
                }
                must_reindex = 1;
            }
            if (must_reindex) {
                table_reindex(t);
            }
            return;
        }
    }
 
add_new_elt:
    t->index_last[hash] = t->a.nelts;
    next_elt = (apr_table_entry_t *) table_push(t);
    next_elt->key = apr_pstrdup(t->a.pool, key);
    next_elt->val = apr_pstrdup(t->a.pool, val);
    next_elt->key_checksum = checksum;
}

TABLE_INDEX_IS_INITIALIZED(t,i)这个宏是检测index_initialized这个变量中的第i位是否被置位。如果没有被置位，则表示该key对应的节点已经在a数组中存在。如果存在则index_first[hash]和index_last[hash]都是存在的，为什么呢？先假设key对应的hash位未被置位，则新插入该key时，我们会把这个key对应的apr_entry_t结构放到a数组的最后，它的索引值便是a.nelts，这时候我们也把index_first[hash]和index_last[hash]的值都设置为a.nelts。当插入另一个key时，它的hash值可能与上一个key出现碰撞，此时该hash值对应的index_first[hash]的索引值不变，将index_last[hash]设置为新索引值，这样这两个key所对应的apr_entry_t结构便都存在于a[index_first[hash]]和a[index_last[a]]之间，我们只需要遍历找到该结构并将其val属性设置为我们要设置的值即可。同时由于该表允许多个相同健的存在，我们在设置健值之后也需要从表中移除其它的具有相同健的对象。与table有关的函数也有很多，大原理都比较简单，也不再赘述了。

本文纯属个人见解，如有谬误烦请指出。

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：给你的代码《约法四章》：基本功能、错误处理、智能纠错、日志收集

后一篇：浅析linux kernel network之socket创建 >>

文章信息

作者：levin 来源： basic coder
标签： tables 源码
发布时间：2012-03-18 23:42:36

建议继续学习

近3天十大热文