1 數組 本節我們講一下php的數組，在php中，數組使用HashTable實現的。本節中我們先詳細的介紹一下HashTable，然後再講講如何使用HastTable 1.1 變長結構體 所謂的變長結構體，其實是我們C語言結構體的一種特殊用法，並沒有什麼新奇之處。我們先來看一下變長結構體的一種通用定義方法。 typedef struct bucket { int n; char key[30]; char value[1]; } Bucket; 我們定義了一個結構體Bucket，我們希望用這個結構體存放學生的個人簡介。其中key用來存在學生的姓名，value用來存放學生的簡介。大家可能很好奇，我們的value聲明了長度為1. 1個char能存多少信息呀？ 其實，對於變長結構體，我們在使用的使用不能直接定義變量，例如：Bucket bucket; 您要是這樣使用，value肯定存儲不了多少信息。對於變長結構體，我們在使用的時候需要先聲明一個變長結構體的指針，然後通過malloc函數分配函數空間，我們需要用到的空間長度是多少，我們就可以malloc多少。通用的使用方法如下： Bucket* pBucket; pBucket = malloc(sizeof(Bucket) + n * sizeof(char)); 其中n就是你要使用value的長度。如果這樣使用的話，value指向的字符串不久變長了嗎！ 1.2 Hashtable簡介 我們先看一下HashTable的定義 struct _hashtable; typedef struct bucket { ulong h;//當元素是數字索引時使用 uint nKeyLength;//當使用字符串索引時，這個變量表示索引的長度，索引（字符串）保存在最後一個元素aKey void *pData;//用來指向保存的數據，如果保存的數據是指針的話，pDataPtr就指向這個數據，pData指向pDataPtr void *pDataPtr; struct bucket *pListNext; //上一個元素 struct bucket *pListLast; //下一個元素 struct bucket *pNext; //指向下一個bucket的指針 struct bucket *pLast; //指向上一個bucket的指針 char arKey[1]; //必須放在最後，主要是為了實現變長結構體 } Bucket; typedef struct _hashtable { uint nTableSize; //哈希表的大小 uint nTableMask; //數值上等於nTableSize- 1 uint nNumOfElements; //記錄了當前HashTable中保存的記錄數 ulong nNextFreeElement; //指向下一個空閒的Bucket Bucket *pInternalPointer; //這個變量用於數組反轉 Bucket *pListHead; //指向Bucket的頭 Bucket *pListTail; //指向Bucket的尾 Bucket **arBuckets; dtor_func_t pDestructor; //函數指針，數組增刪改查時自動調用，用於某些清理操作 zend_bool persistent; //是否持久 unsigned char nApplyCount; zend_bool bApplyProtection; //和nApplyCount一起起作用，防止數組遍歷時無限遞歸 #if ZEND_DEBUG int inconsistent; #endif } HashTable; 希望大家能好好看看上面的定義，有些東西我將出來反而會說不明白，不如大家看看代碼淺顯明了。PHP的數組，其實是一個帶有頭結點的雙向鏈表，其中HashTable是頭，Bucket存儲具體的結點信息。 1.3 HashTable內部函數分析 1.3.1 宏HASH_PROTECT_RECURSION #defineHASH_PROTECT_RECURSION(ht) \ if ((ht)->bApplyProtection) { \ if ((ht)->nApplyCount++ >= 3){ \ zend_error(E_ERROR, "Nestinglevel too deep - recursive dependency?"); \ } \ } 這個宏主要用來防止循環引用。 1.3.2 宏ZEND_HASH_IF_FULL_DO_RESIZE #defineZEND_HASH_IF_FULL_DO_RESIZE(ht) \ if ((ht)->nNumOfElements >(ht)->nTableSize) { \ zend_hash_do_resize(ht); \ } 這個宏的作用是檢查目前HashTable中的元素個數是否大於了總的HashTable的大小，如果個數大於了HashTable的大小，那麼我們就重新分配空間。我們看一下zend_hash_do_resize static int zend_hash_do_resize(HashTable *ht) { Bucket **t; IS_CONSISTENT(ht); if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */ t = (Bucket**) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent); if (t) { HANDLE_BLOCK_INTERRUPTIONS(); ht->arBuckets = t; ht->nTableSize = (ht->nTableSize << 1); ht->nTableMask = ht->nTableSize - 1; zend_hash_rehash(ht); HANDLE_UNBLOCK_INTERRUPTIONS(); return SUCCESS; } return FAILURE; } return SUCCESS; } 從上面的代碼中我們可以看出，HashTable在分配空間的時候，新分配的空間等於原有空間的2倍。 1.3.3 函數 _zend_hash_init 這個函數是用來初始化HashTable的，我們先看一下代碼： ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { uint i = 3; //HashTable的大小默認無2的3次方 Bucket **tmp; SET_INCONSISTENT(HT_OK); if (nSize >= 0x80000000) { ht->nTableSize = 0x80000000; } else { while ((1U << i) < nSize) { i++; } ht->nTableSize = 1 << i; } ht->nTableMask = ht->nTableSize- 1; ht->pDestructor = pDestructor; ht->arBuckets = NULL; ht->pListHead = NULL; ht->pListTail = NULL; ht->nNumOfElements = 0; ht->nNextFreeElement = 0; ht->pInternalPointer = NULL; ht->persistent = persistent; ht->nApplyCount = 0; ht->bApplyProtection = 1; /* Uses ecalloc() so that Bucket* == NULL */ if (persistent) { tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket*)); if (!tmp) { return FAILURE; } ht->arBuckets = tmp; } else { tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket*)); if (tmp) { ht->arBuckets = tmp; } } return SUCCESS; } 可以看出，HashTable的大小被初始化為2的n次方，另外我們看到有兩種內存方式，一種是calloc，一種是ecalloc_rel，這兩中內存分配方式我們細講了，有興趣的話大家可以自己查一查。 1.3.4 函數_zend_hash_add_or_update 這個函數向HashTable中添加或者修改元素信息 ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC) { ulong h; uint nIndex; Bucket *p; IS_CONSISTENT(ht); if (nKeyLength <= 0) { #if ZEND_DEBUG ZEND_PUTS("zend_hash_update: Can't put inempty key\n"); #endif return FAILURE; } h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; while (p != NULL) { if ((p->h == h) && (p->nKeyLength == nKeyLength)) { if (!memcmp(p->arKey, arKey, nKeyLength)) { if (flag & HASH_ADD) { return FAILURE; } HANDLE_BLOCK_INTERRUPTIONS(); #if ZEND_DEBUG if (p->pData == pData) { ZEND_PUTS("Fatal error in zend_hash_update:p->pData == pData\n"); HANDLE_UNBLOCK_INTERRUPTIONS(); return FAILURE; } #endif if (ht->pDestructor) { ht->pDestructor(p->pData); } UPDATE_DATA(ht, p, pData, nDataSize); if (pDest) { *pDest = p->pData; } HANDLE_UNBLOCK_INTERRUPTIONS(); return SUCCESS; } } p = p->pNext; } p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent); if (!p) { return FAILURE; } memcpy(p->arKey, arKey, nKeyLength); p->nKeyLength = nKeyLength; INIT_DATA(ht, p, pData, nDataSize); p->h = h; CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); if (pDest) { *pDest = p->pData; } HANDLE_BLOCK_INTERRUPTIONS(); CONNECT_TO_GLOBAL_DLLIST(p, ht); ht->arBuckets[nIndex] = p; HANDLE_UNBLOCK_INTERRUPTIONS(); ht->nNumOfElements++; ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ return SUCCESS; } 1.3.5 宏CONNECT_TO_BUCKET_DLLIST #define CONNECT_TO_BUCKET_DLLIST(element, list_head) \ (element)->pNext= (list_head); \ (element)->pLast= NULL; \ if((element)->pNext) { \ (element)->pNext->pLast =(element); \ } 這個宏是將bucket加入到bucket鏈表中 1.3.6 其他函數或者宏定義 我們只是簡單的介紹一下HashTable，如果你想細致的了解HashTable的話，建議您看看php的源代碼，關於HashTable的代碼在Zend/zend_hash.h 和Zend/zend_hash.c中。 zend_hash_add_empty_element 給函數增加一個空元素 zend_hash_del_key_or_index 根據索引刪除元素 zend_hash_reverse_apply 反向遍歷HashTable zend_hash_copy 拷貝 _zend_hash_merge 合並 zend_hash_find 字符串索引方式查找 zend_hash_index_find 數值索引方法查找 zend_hash_quick_find 上面兩個函數的封裝 zend_hash_exists 是否存在索引 zend_hash_index_exists 是否存在索引 zend_hash_quick_exists 上面兩個方法的封裝 1.4 C擴展常用HashTable函數 雖然HashTable看起來有點復雜，但是使用卻是很方便的，我們可以用下面的函數對HashTable進行初始化和賦值。 2005 年地方院校招生人數 PHP語法 C語法 意義 $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(3.14); $arr[] = ‘foo’; add_next_index_string(arr, “foo”, 1); 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); 1.5 任務和實驗 說了這麼多，我們實驗一下。 任務：返回一個數組，數組中的數據如下： Array ( [0] => for test [42] => 123 [for test. for test.] => 1 [array] => Array ( [0] => 3.34 ) ) 代碼實現： PHP_FUNCTION(test) { zval* t; array_init(return_value); add_next_index_string(return_value, "for test", 1); add_index_long(return_value, 42, 123); add_assoc_double(return_value, "for test. for test.", 1.0); ALLOC_INIT_ZVAL(t); array_init(t); add_next_index_double(t, 3.34); add_assoc_zval(return_value, "array", t); } 很簡單吧，還記得return_value嗎？
