注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

FY

Johnson 's Blog

 
 
 

日志

 
 

Lighttpd1.4.20源码分析之array.c(h) -----通用数组  

2014-06-23 18:07:32|  分类: LINUX |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://www.cnblogs.com/kernel_hcy/archive/2009/10/23/1588873.html

Lighttpd提供了一个通用数组,这个数组与程序的其他部分练习较少,因此可以单独进行分析。
首先要说一下Lighttpd中的定义的一些数据结构。
在array.h中有下面的定义:
复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
 1 typedef enum { 
 2         TYPE_UNSET,         /* 数据的类型未设置,
 3                                这几种数据类型使用了面向对象的设计思想,
 4                                这个类型相当于父类型,继承关系见后面 
 5                              */
 6         TYPE_STRING,         /* 字符串类型 */
 7         TYPE_COUNT,         /* COUNT类型 */
 8         TYPE_ARRAY,         /* 数组类型 */
 9         TYPE_INTEGER,     /* 整数类型 */
10         TYPE_FASTCGI,     /* FASTCGI类型 */
11         TYPE_CONFIG         /* CONFIG类型 */
12 } data_type_t;
13 
复制代码
这是一个枚举类型,定义了各个数据类型的标志。从中可以看出程序中所定义使用的数据类型的种类和个数。
Lighttpd在定义数据类型的时候使用了面向对象的思想,因此,程序具有很好的扩展性和适应性。这些类型中,最重要的是UNSET类型,这个类型在所有的数据类型中,起到了父类型的作用。在array.h中,UNSET类型的定义如下:
复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
#define DATA_UNSET \
    data_type_t type; \
    buffer 
*key; \
    
int is_index_key; /* 1 if key is a array index */ \
    
struct data_unset *(*copy)(const struct data_unset *src); \
    
void (* free)(struct data_unset *p); \
    
void (* reset)(struct data_unset *p); \
        
int (*insert_dup)(struct data_unset *dst, struct data_unset *src); \
    
void (*print)(const struct data_unset *p, int depth)

typedef 
struct data_unset {
    DATA_UNSET;
} data_unset;
复制代码
其中,UNSET类型数据的定义中,数据的实际定义部分使用宏DATA_UNSET,这样可以方便其他类型在定义中直接引用DATA_UNSET宏来模拟继承。在宏DATA_UNSET中,定义了下面五个函数指针:
复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
1 struct data_unset *(*copy)(const struct data_unset *src); 
2 void (* free)(struct data_unset *p); 
3 void (* reset)(struct data_unset *p); 
4 int (*insert_dup)(struct data_unset *dst, struct data_unset *src); 
5 void (*print)(const struct data_unset *p, int depth)
6 
复制代码
这五个函数指针相当于UNSET的成员函数,其他类型可以通过对这五个指针赋值来实现成员函数的重写(Overwrite)。每种类型都配有自己特有的初始化函数,形式为:data_XXXXX *data_XXXXX_init(void)。在这些初始化函数中,对上面这五个函数指针进行赋值,当然,赋值的函数都应先定义好。
这几种类型的继承关系图如下:(类图)

 

下面分析一下STRING类型的初始化函数data_string * data_string_init(void):

复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
 1 data_string *data_string_init(void)
 2 {
 3     data_string *ds;
 4     /*
 5 分配内存空间。
 6 这里用的是calloc函数,分配的空间会自动清零。
 7 */
 8     ds = calloc(1sizeof(*ds));
 9     assert(ds);
10     /*
11 初始化各个数据成员,
12 这里调用buffer_init函数,主要就是分配内存空间
13 */
14     ds->key = buffer_init();
15     ds->value = buffer_init();
16     /*确定成员函数的具体调用函数,对函数指针赋值*/
17     ds->copy = data_string_copy;
18     ds->free = data_string_free;
19     ds->reset = data_string_reset;
20     ds->insert_dup = data_string_insert_dup;
21     ds->print = data_string_print;
22     ds->type = TYPE_STRING;
23     return ds;
24 }
25 
复制代码
其他类型的init函数,以及其他函数都不难,读者可自行查看代码。
至于各个类型的用处以及各个类型中个成员变量的含义,暂且不用关心,只要知道这七个类型之间的关系即可,除了UNSET类型,其他类型的操作函数的实现都在文件data_XXXXX.c中。这些函数的实现都很简单,不在一一介绍,读者可自己看看。这七个类型构成了通用数组所要处理的类型,其中,在数组的定义和实现中只使用UNSET类型,利用上面的定义,通用数组可以不用关心数组中存储的到底是哪种具体的类型,只需将其按照UNSET类型来处理就可以了。这就实现了通用数组。
下面这个定义是通用数组的核心定义,也就是定义了数组。。。
复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
typedef struct 
{
    
/* UNSET类型的指针型数组,存放数组中的元素 */
    data_unset 
**data;
    
/* 存放着排好序的各个元素的下标的数组 */
    size_t 
*sorted;
    size_t used;    
/* data中使用了的长度,也就是数组中元素个数 */

        
/* data的大小。data的大小会根据数据的多少变化,会为以后的数据预先分
           配空间 
*/
    size_t size;    
    
        size_t unique_ndx;        
/*  */
        
/* 比used大的最小的2的倍数。也就是离used最近的且比used大的2的倍
              数 ,用于在数组中利用二分法查找元素
*/
    size_t next_power_of_2;
        
/* data is weakref, don't bother the data */
        
/* data就是一个指针,不用关系其所指向的内容 */
    
int is_weakref;                
} array;
复制代码
各个变量的含义见上。
array.h中还有一个定义:
1 typedef struct {
2  DATA_UNSET;
3  array *value;
4 } data_array;
5 
这个定义了一个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中的位置。
函数的定义如下:
复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
 1 static int array_get_index(array *a, const char *key, size_t keylen, int *rndx) 
 2 {
 3     /*参数keylen是key的长度*/
 4     int ndx = -1;
 5     int i, pos = 0;
 6     if (key == NULL) return -1;
 7     /* try to find the string */
 8     /* 
 9 * sorted数组是个下标数组,存放的是排好序的输入元素的下标,
10 * 相当于一个排好序的数组。
11      * 利用sorted数组进行二分查找。
12      * 若找到,返回元素在data数组中的位置,并通过rndx返回
13 * 其在sorted数组中的位置。
14      * 若没有找到,通过rndx返回此元素在sorted中的位置,并返回-1
15      */
16 /* pos中存放的是元素在数组data中的位置 */
17 /*  
18 当data的空间不够时,通用数组每次为data增加16个空间,第一次初始化时,
19 data的长度为16。因此,size始终是16的倍数。
20 used可以为任何数值,当然要大于等于0,小于size。
21 而next_power_of_2是大于used最小的2的倍数,如used=5,那么
22 next_power_of_2就等于8。
23 这样,used始终大于等于next_power_of_2的1/2。
24 */
25 /*
26  在这儿的二分搜索中,next_power_of_2是个很有创意的技巧。
27 next_power_of_2类似于一个标杆,利用这个标杆进行二分搜索可以减少很多
28 出错的几率,也使程序更加易懂。效率上当然没有什么损失。下面的程序读者可
29 自行看看,并不是很难。
30  */
31     for (i = pos = a->next_power_of_2 / 2; ; i >>= 1
32 {
33  int cmp;
34  if (pos < 0) {
35  pos += i;
36  } else if (pos >= (int)a->used) {
37  pos -= i;
38  } else {
39  /* 比较两个元素的key值 */
40  cmp = buffer_caseless_compare(key, keylen
41 , a->data[a->sorted[pos]]->key->ptr
42 , a->data[a->sorted[pos]]->key->used
43 );
44  if (cmp == 0) {
45  /* found */
46  ndx = a->sorted[pos];
47  break;
48  } else if (cmp < 0) {/* 所找数据在前半部分 */
49  pos -= i;
50  } else { /*  所找数据在后半部分*/
51  pos += i;
52  }
53  }
54  if (i == 0break;
55     }
56     if (rndx) *rndx = pos;
57     return ndx;
58 }
59 
60 
复制代码

在上面列出的函数中,还有一个函数要重点讲解一下,也是最复杂的一个函数:int array_insert_unique(array *a, data_unset *str)。这个函数将数据str插入到数组中,当并不是单纯的插入,如果数组中存在key于str相同的数据,则把str的内容拷贝到这个数据中。
复制代码
Lighttpd1.4.20源码分析之array.c(h) -----通用数组 - FY - FY
 1 int array_insert_unique(array *a, data_unset *str) {
 2     int ndx = -1;
 3     int pos = 0;
 4     size_t j;
 5     /* generate unique index if neccesary */
 6     if (str->key->used == 0 || str->is_index_key) {
 7                buffer_copy_long(str->key, a->unique_ndx++);
 8                    str->is_index_key = 1;
 9     }
10     /* 在数组中查找与str具有相同key的数据 */
11     if (-1 != (ndx = array_get_index(a, str->key->ptr, str->key->used, &pos))) 
12         {
13             /* 找到,复制 */
14              if (a->data[ndx]->type == str->type) 
15               {
16                        str->insert_dup(a->data[ndx], str);
17               } 
18               else 
19               {
20                        fprintf(stderr, "a\n");
21               }
22               return 0;
23     }
24     /* 当数组的长度大于最大值时,不进行插入,并返回-1 */
25     if (a->used+1 > INT_MAX) {
26                     /* we can't handle more then INT_MAX entries: see array_get_index() */
27                    return -1;
28     }
29 
30     if (a->size == 0) {
31                /* 数组为空 */
32                /* 初始data的长度为16 */
33                a->size   = 16;
34                a->data   = malloc(sizeof(*a->data)     * a->size);
35                a->sorted = malloc(sizeof(*a->sorted)   * a->size);
36                assert(a->data);
37                assert(a->sorted);
38                for (j = a->used; j < a->size; j++
39                             a->data[j] = NULL;
40     } 
41         else if (a->size == a->used) 
42         {
43           /* data已经满了,对data进行扩容,增加16个空间。 */
44           /* 这就是为什么size一定是16的倍数 */
45                a->size  += 16;
46                a->data   = realloc(a->data, sizeof(*a->data) * a->size);
47                a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
48                assert(a->data);
49                assert(a->sorted);
50                for (j = a->used; j < a->size; j++)
51                              a->data[j] = NULL;
52     }
53     ndx = (int) a->used;
54     a->data[a->used++= str;
55     /*
56                在上面调用函数array_get_index的时候,
57               已将str应该在数组sorted中位置存放在了pos中。 
58         */
59     if (pos != ndx /* 要插入的位置在中部 */&&((pos < 0/* 在开始位置插入 */
60                             ||buffer_caseless_compare(str->key->ptr
61                                           , str->key->used
62                                           , a->data[a->sorted[pos]]->key->ptr
63                                           , a->data[a->sorted[pos]]->key->used
64                             ) > 0)) 
65         {
66                /* 判断当前pos所对应的元素是否比str小,若是,这pos后移一位 */
67                pos++;
68     }
69     /* 移动sorted数组中后面的数据,腾出位置。 */
70     if (pos != ndx) {
71                memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
72     }
73     /* insert */
74     a->sorted[pos] = ndx;
75     /* 如果used==next_power_of_2时,扩展next_power_of_2 */
76     if (a->next_power_of_2 == (size_t)ndx) 
77               a->next_power_of_2 <<= 1;
78     return 0;
79 }
80 
81 
复制代码
其他函数都很简单,读者可自己查看。另外,print函数虽然复杂,但对整个程序的意义不大,读者可自行查看。

总结:
  Lighttpd中的通用数组的设置主要是使用的面向对象的思想,使数组具有很好的扩展性和适应性。通用数组中二分查找的实现也是一个特色。还有就是使用sorted数组只对data中的数据的下标排序,这也是一个很有用的技巧。

  以上就是我的一点拙见,还望读者网友对疏漏之处进行批评指正。 

  评论这张
 
阅读(118)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018