wifidog自带HTTP 服务器 Lighttpd1.4.20源码分析之array.c(h) -----通用数组（2）

上文讲解到
array.h中还有一个定义：

 typedef struct {
  DATA_UNSET;
  array *value;
 } data_array;

这个定义了一个array类型的数据，也就是说，通用数组中存放的数据可以数通用数组，这样可以形成多维的通用数组。
在array.h中定义了如下的通用数组操作函数：
1、array *array_init(void);
初始化数组，分配空间。
2、array *array_init_array(array * a);
用数组a来初始化一个数组。也就是得到一个a的深拷贝。
3、void array_free(array * a);
释放数组。释放所有空间。
4、void array_reset(array * a);
重置data中的所有数据（调用UNSET类型数据中的reset函数），并将used设为0。相当于清空数组。
5、int array_insert_unique(array * a, data_unset * str);
将str插入到数组中。
6、data_unset *array_pop(array * a);
弹出data中的最后一个元素，返回奇指针，data中的最后一个位置设为NULL。
7、int array_print(array * a, int depth);
打印数组中的内容。depth参数用于在打印多维数组时，实现缩进。
8、a_unset *array_get_unused_element(array * a, data_type_t t);
返回第一个未使用的数据，也就是used位置的数据，这个数据不在数组中，返回这个数据指针后，将data[unsed]设为NULL。可能返回NULL。
9、data_unset *array_get_element(array * a, const char *key);
根据key值，返回数组中key值与之相同的数据
10、data_unset *array_replace(array * a, data_unset * du);
如果数组中有与du的key值相同的数据，则用du替换那个数据，并返回那个数据的指针。如果不存在，则把du插入到数组中。（调用data_insert_unique函数）
11、 int array_strcasecmp(const char *a, size_t a_len, const char *b, size_t b_len);
这个函数并没用实现，仅仅给出了上面的定义。也许这个是用来比较两个字符串，并且可能会忽略大小写。
12、void array_print_indent(int depth);
根据depth打印空白，实现缩进。
13、size_t array_get_max_key_length(array * a);
返回数组中最长的key的长度。

另外，在array.c中定义了一个辅助函数static intarray_get_index(array *a, const char *key, size_t keylen, int *rndx)。这个函数的作用是通过key值，查找数据，返回其在数组data中的下标位置，并通过参数rndx返回其下标在数组sorted中的位置。
函数的定义如下：

Code
static int array_get_index(array *a, const char *key, size_t keylen, int *rndx) 
{
    /*参数keylen是key的长度*/
    int ndx = -1;
    int i, pos = 0;
    if (key == NULL) return -1;
    /* try to find the string */
    /* 
* sorted数组是个下标数组，存放的是排好序的输入元素的下标，
* 相当于一个排好序的数组。
     * 利用sorted数组进行二分查找。
     * 若找到，返回元素在data数组中的位置，并通过rndx返回
* 其在sorted数组中的位置。
     * 若没有找到，通过rndx返回此元素在sorted中的位置，并返回-1
     */
/* pos中存放的是元素在数组data中的位置 */
/*  
当data的空间不够时，通用数组每次为data增加16个空间，第一次初始化时，
data的长度为16。因此，size始终是16的倍数。
used可以为任何数值，当然要大于等于0,小于size。
而next_power_of_2是大于used最小的2的倍数，如used=5,那么
next_power_of_2就等于8。
这样，used始终大于等于next_power_of_2的1/2。
*/
/*
 在这儿的二分搜索中，next_power_of_2是个很有创意的技巧。
next_power_of_2类似于一个标杆，利用这个标杆进行二分搜索可以减少很多
出错的几率，也使程序更加易懂。效率上当然没有什么损失。下面的程序读者可
自行看看，并不是很难。
 */
    for (i = pos = a->next_power_of_2 / 2; ; i >>= 1) 
{
 int cmp;
 if (pos < 0) {
 pos += i;
 } else if (pos >= (int)a->used) {
 pos -= i;
 } else {
 /* 比较两个元素的key值 */
 cmp = buffer_caseless_compare(key, keylen
, a->data[a->sorted[pos]]->key->ptr
, a->data[a->sorted[pos]]->key->used
);
 if (cmp == 0) {
 /* found */
 ndx = a->sorted[pos];
 break;
 } else if (cmp < 0) {/* 所找数据在前半部分 */
 pos -= i;
 } else { /*  所找数据在后半部分*/
 pos += i;
 }
 }
 if (i == 0) break;
    }
    if (rndx) *rndx = pos;
    return ndx;
}

在上面列出的函数中，还有一个函数要重点讲解一下，也是最复杂的一个函数：int array_insert_unique(array *a, data_unset *str)。这个函数将数据str插入到数组中，当并不是单纯的插入，如果数组中存在key于str相同的数据，则把str的内容拷贝到这个数据中。

Code
int array_insert_unique(array *a, data_unset *str) {
    int ndx = -1;
    int pos = 0;
    size_t j;
    /* generate unique index if neccesary */
    if (str->key->used == 0 || str->is_index_key) {
               buffer_copy_long(str->key, a->unique_ndx++);
                   str->is_index_key = 1;
    }
    /* 在数组中查找与str具有相同key的数据 */
    if (-1 != (ndx = array_get_index(a, str->key->ptr, str->key->used, &pos))) 
        {
            /* 找到，复制 */
             if (a->data[ndx]->type == str->type) 
              {
                       str->insert_dup(a->data[ndx], str);
              } 
              else 
              {
                       fprintf(stderr, "a\n");
              }
              return 0;
    }
    /* 当数组的长度大于最大值时，不进行插入，并返回-1 */
    if (a->used+1 > INT_MAX) {
                    /* we can't handle more then INT_MAX entries: see array_get_index() */
                   return -1;
    }

    if (a->size == 0) {
               /* 数组为空 */
               /* 初始data的长度为16 */
               a->size   = 16;
               a->data   = malloc(sizeof(*a->data)     * a->size);
               a->sorted = malloc(sizeof(*a->sorted)   * a->size);
               assert(a->data);
               assert(a->sorted);
               for (j = a->used; j < a->size; j++) 
                            a->data[j] = NULL;
    } 
        else if (a->size == a->used) 
        {
          /* data已经满了，对data进行扩容，增加16个空间。 */
          /* 这就是为什么size一定是16的倍数 */
               a->size  += 16;
               a->data   = realloc(a->data, sizeof(*a->data) * a->size);
               a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
               assert(a->data);
               assert(a->sorted);
               for (j = a->used; j < a->size; j++)
                             a->data[j] = NULL;
    }
    ndx = (int) a->used;
    a->data[a->used++] = str;
    /*
               在上面调用函数array_get_index的时候，
              已将str应该在数组sorted中位置存放在了pos中。 
        */
    if (pos != ndx /* 要插入的位置在中部 */&&((pos < 0) /* 在开始位置插入 */
                            ||buffer_caseless_compare(str->key->ptr
                                          , str->key->used
                                          , a->data[a->sorted[pos]]->key->ptr
                                          , a->data[a->sorted[pos]]->key->used
                            ) > 0)) 
        {
               /* 判断当前pos所对应的元素是否比str小，若是，这pos后移一位 */
               pos++;
    }
    /* 移动sorted数组中后面的数据，腾出位置。 */
    if (pos != ndx) {
               memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
    }
    /* insert */
    a->sorted[pos] = ndx;
    /* 如果used==next_power_of_2时，扩展next_power_of_2 */
    if (a->next_power_of_2 == (size_t)ndx) 
              a->next_power_of_2 <<= 1;
    return 0;
}

其他函数都很简单，读者可自己查看。另外，print函数虽然复杂，但对整个程序的意义不大，读者可自行查看。

总结：
　　Lighttpd中的通用数组的设置主要是使用的面向对象的思想，使数组具有很好的扩展性和适应性。通用数组中二分查找的实现也是一个特色。还有就是使用sorted数组只对data中的数据的下标排序，这也是一个很有用的技巧。
　　以上就是我的一点拙见，还望读者网友对疏漏之处进行批评指正。

本文章由 http://www.wifidog.pro/2015/04/13/wifidog-lighttpd%E5%88%86%E6%9E%90%E9%80%9A%E7%94%A8%E6%95%B0%E7%BB%84-2.html 整理编辑，转载请注明出处

标签: none