通用数组array.c(h)
最后更新于：2022-04-01 15:57:03
首先回顾以下，在array.h中，UNSET类型是一个宏：
~~~
#define DATA_UNSET \
data_type_t type; \
buffer *key; \
int is_index_key; /* 1 if key is a array index (autogenerated keys) */ \
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;
~~~
使用宏DATA_UNSET，这样可以方便其他类型在定义中直接引用DATA_UNSET宏来模拟继承。在宏DATA_UNSET中，定义了下面五个函数指针：
~~~
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)
~~~
这些函数指针相当于UNSET的成员函数，其他类型可以通过对这五个指针赋值来实现成员函数的重写（Overwrite）。每种类型都配有自己特有的初始化函数，在这些初始化函数中，对上面这五个函数指针进行赋值。
作者很巧妙地用面向对象的思想来组织C代码。
我们可以实例性地看下STRING类型的初始化函数（data_string.c）：
~~~
data_string *data_string_init(void) {
data_string *ds;
ds = calloc(1, sizeof(*ds)); //分配的空间会自动清零
assert(ds);
/* 初始化数据成员，buffer_init用来分配内存空间 */
ds->key = buffer_init();
ds->value = buffer_init();
/* 成员函数，对函数指针赋值 */
ds->copy = data_string_copy;
ds->free = data_string_free;
ds->reset = data_string_reset;
ds->insert_dup = data_string_insert_dup;
ds->print = data_string_print;
ds->type = TYPE_STRING;
return ds;
}
~~~
array.h中，各个数据类型的标志的定义：
~~~
typedef enum {
TYPE_UNSET, /* 数据的类型未设置，
这几种数据类型使用了面向对象的设计思想，
这个类型相当于父类型
*/
TYPE_STRING, /* 字符串类型 */
TYPE_COUNT, /* COUNT类型 */
TYPE_ARRAY, /* 数组类型 */
TYPE_INTEGER, /* 整数类型 */
TYPE_FASTCGI, /* FASTCGI类型 */
TYPE_CONFIG /* CONFIG类型 */
} data_type_t;
~~~
除了UNSET类型，其他类型的操作函数的实现都在文件data_XXX.c中。这七个类型构成了通用数组所要处理的类型。
为何叫做通用数组呢？
因为在数组的定义和实现中只使用UNSET类型，基于上面的定义，通用数组可以不用关心数组中存储的到底是哪种具体的类型，只需将其按照UNSET类型来处理就可以了，所以说是通用的。
下面这个定义是通用数组的核心定义：
~~~
typedef struct
{
/* UNSET类型的指针型数组，存放数组中的元素 */
data_unset **data;
/* 按 data 数据的排序顺序保存 data 的索引 */
size_t *sorted;
size_t used; /* data中已经使用了的长度，也就是数组中元素个数 */
/* data的大小。data的大小会根据数据的多少变化，会为以后的数据预先分配空间 */
size_t size;
/* 用于保存唯一索引,初始为 0,之后递增 */
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;
~~~
sorted（图中仅展示data_unset中的key）：
还有一个定义：
~~~
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插入到数组中，如果数组中存在key与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_get_index函数：
~~~
/*
* sorted数组是个下标数组，存放的是排好序的输入元素的下标（见前面的图），
* 相当于一个排好序的数组。
* 利用sorted数组进行二分查找。
* 若找到，返回元素在data数组中的位置，并通过rndx返回
* 其在sorted数组中的位置。
* 若没有找到，通过rndx返回此元素在sorted中的位置，并返回-1
*/
static int array_get_index(array *a, const char *key, size_t keylen, int *rndx) {
int ndx = -1;
int i, pos = 0; /* pos中存放的是元素在数组data中的位置 */
if (key == NULL) return -1;
/*
* 当data的空间不够时，通用数组每次为data增加16个空间，第一次初始化时，
* data的长度为16。因此，size始终是16的倍数。
* 而next_power_of_2是大于used最小的2的倍数，如used=5,那么
* next_power_of_2就等于8。
* 这样，used始终大于等于next_power_of_2的1/2。
*
* next_power_of_2类似于一个标杆，利用这个标杆进行二分搜索
* 可以减少很多出错的几率，也使程序更加易懂。
*/
/* try to find the string */
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;
}
~~~
本数据结构的实现中，二分查找是一个特色，然后用sorted数组只对data中的数据的下标排序，也是一个很有用的技巧。