04數據結構_數組和字符串 · PHP底層內核源碼與擴展開發

## 數組/哈希表 ### 數組結構 ```c /* Zend/zend_type.h */ typedef struct _zend_array HashTable; //這個結構體64位平臺占56個字節. struct _zend_array { zend_refcounted_h gc; //引用計數信息,與字符串相同 union { struct { ZEND_ENDIAN_LOHI_4( zend_uchar flags,//zend_hash.h:line 38 zend_uchar nApplyCount,//數組循環遞歸保護 zend_uchar nIteratorsCount,//數組迭代深度 zend_uchar consistency)//一致性狀態 zend_hash.c line 38 } v; uint32_t flags; //標志位 } u; uint32_t nTableMask; //計算bucket索引時的掩碼,等于nTableSize的負值(nTableMask = -nTableSize) Bucket *arData; //指向 Bucket 類型數據的指針,插入時只會在 arData 數組的結尾插入,而不會填充已經被刪除的節點. uint32_t nNumUsed; //arData數組已經使用bucket數,每當添加一個新的數據時,此成員會加1. uint32_t nNumOfElements; //有效bucket數,nNumOfElements <= nNumUsed,因為刪除的并不是直接從arData中移除 uint32_t nTableSize; //hash表的大小,為2^n uint32_t nInternalPointer; //數值索引,用于HashTable遍歷 zend_long nNextFreeElement; //下一個空閑可用位置的數字索引 dtor_func_t pDestructor; //析構函數,銷毀時調用的函數指針 }; typedef struct _Bucket { zval val; zend_ulong h; /* hash value (or numeric index) */ zend_string *key; /* string key or NULL for numerics */ } Bucket; //引用結構 typedef struct _zend_refcounted_h { uint32_t refcount; /* reference counter 32-bit */ union { struct { ZEND_ENDIAN_LOHI_3( zend_uchar type, //zend_value的類型,與zval.u1.type一致 zend_uchar flags, /* line:438 used for strings & objects */ uint16_t gc_info) /* GC信息,垃圾回收的過程會用到 keeps GC root number (or 0) and color */ } v; uint32_t type_info; } u; } zend_refcounted_h; ``` zval.value.arr將指向上面的這樣的一個結構體, 由它實際保存一個數組, 引用計數部分保存在zend_refcounted_h結構中: 所有的復雜類型的定義, 開始的時候都是zend_refcounted_h結構, 這個結構里除了引用計數以外, 還有GC相關的結構. 從而在做GC回收的時候, GC不需要關心具體類型是什么, 所有的它都可以當做zend_refcounted*結構來處理. 插入元素時按順序依次插入數組,比如第一個元素在arData[0]、第二個在arData[1]...arData[nNumUsed]. ### 數據結構圖片當我們分配完整的arData內存時,會通過公式`tablesize * sizeof(bucket) + tablesize * sizeof(uint32)`計算它的大小 ![](https://box.kancloud.cn/8058e1c04cb3f4969706721ba2e18814_1129x981.png) ### 監視EG,CG,PG全局變量 ### hash映射函數,碰撞處理 hash表背后的概念非常簡單:字符串鍵通過散列函數運行,該函數返回一個整數.然后,該整數用作“正常”數組的索引.問題是兩個不同的字符串可能導致相同的哈希,因為可能的字符串的數量實際上是無限的,而散列受整數大小的限制.這樣的hash表需要實現某種碰撞解決機制->鏈表法. 生成hash值:DJBX33A算法 Zend/zend_string.h : line 325 ### hashtable的操作 ```c /* ht: 數組地址HashTable*,如果內部使用可以直接通過emalloc分配 nSize: 初始化大小,只是參考值,這個值會被對齊到2^n,最小為8 pHashFunction: 無用,設置為NULL即可 pDestructor: 刪除或更新數組元素時會調用這個函數對操作的元素進行處理,比如將一個字符串插入數組,字符串的refcount增加,刪除時不是簡單的將元素的Bucket刪除就可以了,還需要對其refcount進行處理,這個函數就是進行清理工作的 persistent: 是否持久化 */ //hash初始化 ALLOC_HASHTABLE(ht); zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent); //添加元素 //key為zend_string zend_hash_update(ht, key, pData) //插入或更新元素,會增加key的refcount zend_hash_update_ind(ht, key, pData)//插入或更新元素,當Bucket類型為indirect時,將pData更新至indirect的值,而不是更新Bucket zend_hash_add(ht, key, pData) //添加元素,與zend_hash_update()類似,不同的地方在于如果元素已經存在則不會更新 zend_hash_add_new(ht, key, pData) //直接插入元素,不管key存在與否,如果存在也不覆蓋原來元素,而是當做哈希沖突處理,所有會出現一個數組中key相同的情況,慎用!!! //key為普通字符串:char* //與上面幾個對應,這里的key為普通字符串,會自動生成zend_string的key zend_hash_str_update(ht, key, len, pData) zend_hash_str_update_ind(ht, key, len, pData) zend_hash_str_add(ht, key, len, pData) zend_hash_str_add_new(ht, key, len, pData) //key為數值索引 zend_hash_index_add(ht, h, pData) //插入元素,h為數值 zend_hash_index_add_new(ht, h, pData) //zend_hash_index_add_new zend_hash_index_update(ht, h, pData) //與zend_hash_add_new()類似 //使用自動索引值 zend_hash_next_index_insert(ht, pData) zend_hash_next_index_insert_new(ht, pData) //查找元素 zend_hash_find(const HashTable *ht, zend_string *key); //根據zend_string key查找數組元素 zend_hash_str_find(const HashTable *ht, const char *key, size_t len); //根據普通字符串key查找元素 zend_hash_index_find(const HashTable *ht, zend_ulong h); //獲取數值索引元素 //判斷元素是否存在 zend_hash_exists(const HashTable *ht, zend_string *key); zend_hash_str_exists(const HashTable *ht, const char *str, size_t len); zend_hash_index_exists(const HashTable *ht, zend_ulong h); zend_hash_num_elements(ht) //獲取數組元素數 zend_array_count(HashTable *ht);//與zend_hash_num_elements()類似,會有一些特殊處理 //刪除元素 zend_hash_del(HashTable *ht, zend_string *key); //刪除key zend_hash_del_ind(HashTable *ht, zend_string *key); ////與zend_hash_del()類似,不同地方是如果元素類型為indirect則同時銷毀indirect的值 zend_hash_str_del(HashTable *ht, const char *key, size_t len); zend_hash_str_del_ind(HashTable *ht, const char *key, size_t len); zend_hash_index_del(HashTable *ht, zend_ulong h); zend_hash_del_bucket(HashTable *ht, Bucket *p); //銷毀 zend_hash_destroy(ht);//調用所有Bucket的析構函數并釋放它們 FREE_HASHTABLE(ht); //遍歷 //遍歷獲取所有val zval *val; ZEND_HASH_FOREACH_VAL(ht, val) { ... } ZEND_HASH_FOREACH_END(); //遍歷獲取所有的數值索引 #define ZEND_HASH_FOREACH_NUM_KEY(ht, _h) \ ZEND_HASH_FOREACH(ht, 0); \ _h = _p->h; //遍歷獲取所有的key #define ZEND_HASH_FOREACH_STR_KEY(ht, _key) \ ZEND_HASH_FOREACH(ht, 0); \ _key = _p->key; //上面兩個的聚合 #define ZEND_HASH_FOREACH_KEY(ht, _h, _key) \ ZEND_HASH_FOREACH(ht, 0); \ _h = _p->h; \ _key = _p->key; //遍歷獲取數值索引key及value #define ZEND_HASH_FOREACH_NUM_KEY_VAL(ht, _h, _val) \ ZEND_HASH_FOREACH(ht, 0); \ _h = _p->h; \ _val = _z; //遍歷獲取key及value #define ZEND_HASH_FOREACH_STR_KEY_VAL(ht, _key, _val) \ ZEND_HASH_FOREACH(ht, 0); \ _key = _p->key; \ _val = _z; #define ZEND_HASH_FOREACH_KEY_VAL(ht, _h, _key, _val) \ ZEND_HASH_FOREACH(ht, 0); \ _h = _p->h; \ _key = _p->key; \ _val = _z; ``` ### 數組操作將zend_hash API與zvals一起使用通常需要自己處理zval分配和初始化。所以PHP提供了專門針對這種用例的第二組API。也就是array api。 | PHP語法 | C語法(arr是zval*） | 作用 | | -------- | ----- | ----- | | $arr = array(); | array_init(arr); | 初始化一個新數組 | | $arr[] = NULL; | add_next_index_null(arr); | 向數字索引的數組增加指定類型的值 | | $arr[] = 42; | add_next_index_long(arr, 42); | | | $arr[] = true; | add_next_index_bool(arr, 1); | | | $arr[] = 3.14; | add_next_index_double(arr, 3.14); | | | $arr[] = 'foo'; | add_next_index_string(arr, "foo", 1); | | | $arr[] = $myvar; | add_next_index_zval(arr, myvar); | | | $arr[0] = NULL; | add_index_null(arr, 0); | 向數組中指定的數字索引增加指定類型的值 | | $arr[1] = 42; | add_index_long(arr, 1, 42); | | | $arr[2] = true; | add_index_bool(arr, 2, 1); | | | $arr[3] = 3.14; | add_index_double(arr, 3, 3.14); | | | $arr[4] = 'foo'; | add_index_string(arr, 4, "foo", 1); | | | $arr[5] = $myvar; | add_index_zval(arr, 5, myvar); | | | $arr['abc'] = NULL; | add_assoc_null(arr, "abc"); | | | $arr['def'] = 711; | add_assoc_long(arr, "def", 711); | 向關聯索引的數組增加指定類型的值 | | $arr['ghi'] = true; | add_assoc_bool(arr, "ghi", 1); | | | $arr['jkl'] = 1.44; | add_assoc_double(arr, "jkl", 1.44); | | | $arr['mno'] = 'baz'; | add_assoc_string(arr, "mno", "baz", 1); | | | $arr['pqr'] = $myvar; | add_assoc_zval(arr, "pqr", myvar); | . | ## 字符串 ```c /* gc: 變量引用信息,比如當前value的引用數,所有用到引用計數的變量類型都會有這個結構,3.1節會詳細分析 h: 哈希值,數組中計算索引時會用到 len: 字符串長度,通過這個值保證二進制安全 val: 字符串內容,變長struct,分配時按len長度申請內存事實上字符串又可具體分為幾類:IS_STR_PERSISTENT(通過malloc分配的)、IS_STR_INTERNED(php代碼里寫的一些字面量,比如函數名、變量值)、IS_STR_PERMANENT(永久值,生命周期大于request)、IS_STR_CONSTANT(常量)、IS_STR_CONSTANT_UNQUALIFIED,這個信息通過flag保存:zval.value->gc.u.flags,后面用到的時候再具體分析. */ struct _zend_string { zend_refcounted_h gc; zend_ulong h; /* hash value */ size_t len; char val[1]; }; ``` ### 示例 ```c zend_string *foo, *foo2; foo = zend_string_init("foo", strlen("foo"), 0); foo2 = zend_string_copy(foo); /* “foo”字符串引用數加1 */ /* 內部字符串，“foo”字符串引用變回為1,盡管有有三個地方在使用此字符串 */ foo = zend_new_interned_string(foo); /* foo指向內部字符串，這里釋放操作沒有任何作用。*/ zend_string_release(foo); /* foo2 指向內部字符串，這里同樣沒有作用 */ zend_string_release(foo2); /* 進程結束時，PHP將清理整個內部字符串空間，我們前面聲明的"foo"將在此時釋放 */ ``` ### 字符串的操作 ```c //創建zend_string zend_string *zend_string_init(const char *str, size_t len, int persistent); //字符串復制,只增加引用 zend_string *zend_string_copy(zend_string *s); //字符串拷貝,硬拷貝 zend_string *zend_string_dup(zend_string *s, int persistent); //將字符串按len大小重新分配,會減少s的refcount,返回新的字符串 zend_string *zend_string_realloc(zend_string *s, size_t len, int persistent); //延長字符串,與zend_string_realloc()類似,不同的是len不能小于s的長度 zend_string *zend_string_extend(zend_string *s, size_t len, int persistent); //截斷字符串,與zend_string_realloc()類似,不同的是len不能大于s的長度 zend_string *zend_string_truncate(zend_string *s, size_t len, int persistent); //獲取字符串refcount uint32_t zend_string_refcount(const zend_string *s); //增加字符串refcount uint32_t zend_string_addref(zend_string *s); //減少字符串refcount uint32_t zend_string_delref(zend_string *s); //釋放字符串,減少refcount,為0時銷毀 void zend_string_release(zend_string *s); //銷毀字符串,不管引用計數是否為0 void zend_string_free(zend_string *s); //比較兩個字符串是否相等,區分大小寫,memcmp() zend_bool zend_string_equals(zend_string *s1, zend_string *s2); //比較兩個字符串是否相等,不區分大小寫 #define zend_string_equals_ci(s1, s2) \ (ZSTR_LEN(s1) == ZSTR_LEN(s2) && !zend_binary_strcasecmp(ZSTR_VAL(s1), ZSTR_LEN(s1), ZSTR_VAL(s2), ZSTR_LEN(s2))) //其它宏,zstr類型為zend_string* #define ZSTR_VAL(zstr) (zstr)->val //獲取字符串 #define ZSTR_LEN(zstr) (zstr)->len //獲取字符串長度 #define ZSTR_H(zstr) (zstr)->h //獲取字符串哈希值 #define ZSTR_HASH(zstr) zend_string_hash_val(zstr) //計算字符串哈希值 ZVAL_STR(zval, zstr); //將字符串存儲到zval Z_STRVAL(zval) //獲取ZVAL中的字符串 Z_STRLEN(zval) //獲取ZVAL中的字符串長度 Z_STRHASH(zval) //獲取ZVAL中的字符串哈希值 ``` php_printf():打印格式化字符串到輸出流。該函數內部使用spprintf()，會執行動態分配空間并它在將其發送到SAPI輸出之后釋放自身。 spprintf()： ```c #include <time.h> char *result; int r; time_t timestamp = time(NULL); r = spprintf(&result, 0, "Here is the date: %s", asctime(localtime(&timestamp)));/* result 為 "Here is the date: Thu Jun 15 19:12:51 2017\n" */ efree(result); ``` strpprintf(): ```c zend_string *result; result = strpprintf(0, "You are using PHP %s", PHP_VERSION); /* Do something with result */ zend_string_release(result); ``` ## 參考資料: http://blog.jpauli.tech/2016/04/08/hashtables.html https://github.com/pangudashu http://ju.outofmemory.cn/entry/197064 http://www.phpinternalsbook.com