首先回顧以下，在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中的數據的下標排序，也是一個很有用的技巧。