这篇文章主要介绍了关于PHP源码中HashTable的解析,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下
PHP源码中HashTable的简单示例 前些日子看了那篇对hasttable的介绍,于是也想自己运行一下,可是对于源码的调试不是太在行。 所以想了个办法:自己把PHP源码中的一些简单操作提取出来,自己运行一下,查看输出或调试。 于是花费了三天的空闲时间把一些相关的东西提取出来,主要是Zend目录下的zend_alloc.c,zend_alloc.h,zend_hash.c,zend_hash.h四个文件。 将与PHP相关的内存分配去掉,默认使用系统自带的内存分配方式。 另外:一些注释是http://www.phppan.com/2009/12/zend-hashtable/中所引用文章中的相关信息。 作者地址:http://www.phpinternals.com 下面的代码是一个可以运行的C程序,它初始化一个容量为50的hashtable(实际上分配了64个),然后将30到68,写入hash table,并将这个hash table 打印出来。 相信这会给一些想学习源码的童鞋一些帮助。 源代码如下:
<!-- #include <stdio.h-->#include #include typedef unsigned long ulong;typedef unsigned int uint;typedef unsigned char zend_bool;typedef unsigned int size_t;typedef void (*dtor_func_t)(void *pDest);typedef ulong (*hash_func_t)(char *arKey, uint nKeyLength);#define SUCCESS 0#define FAILURE -1 /* this MUST stay a negative number, or it may affect functions! */ #define HASH_UPDATE (1<<0)#define HASH_ADD (1<<1)#define HASH_NEXT_INSERT(1<<2) #define HASH_DEL_KEY 0 #define perealloc_recoverable(ptr, size, persistent) (__zend_realloc((ptr), (size)))#define pefree_rel(ptr, persistent)(free(ptr))//此处省略了使用PHP的内存分配函数#define pemalloc_rel(size, persistent) (__zend_malloc(size))#define perealloc_rel(ptr, size, persistent) (__zend_realloc((ptr), (size)))#define pemalloc(size, persistent) (__zend_malloc(size))#define pefree(ptr, persistent) (free(ptr)) inline static void * __zend_malloc(size_t len) { void *tmp = malloc(len); if (tmp) { return tmp; } fprintf(stderr, "Out of memory\n"); exit(1);} inline static void * __zend_realloc(void *p, size_t len) { p = realloc(p, len); if (p) { return p; } fprintf(stderr, "Out of memory\n"); exit(1);} typedef struct bucket { ulong h; /* Used for numeric indexing */ uint nKeyLength; /* key 长度 */ void *pData; /* 指向Bucket中保存的数据的指针 */ void *pDataPtr; /* 指针数据 */ struct bucket *pListNext; /* 指向HashTable桶列中下一个元素 */ struct bucket *pListLast; /* 指向HashTable桶列中前一个元素 */ struct bucket *pNext; /* 指向具有同一个hash值的桶列的后一个元素 */ struct bucket *pLast; /* 指向具有同一个hash值的桶列的前一个元素 */ char arKey[1]; /* 必须是最后一个成员,key名称*/} Bucket; typedef struct _hashtable { uint nTableSize;/*指定了HashTable的大小,同时它限定了HashTable中能保存Bucket的最大数量 此 数越大,系统为HashTable分配的内存就越多。为了提高计算效率, 系统自动会将nTableSize调整到最小一个不小于nTableSize的2 的整数次方*/ uint nTableMask;/*nTableMask的值永远是nTableSize – 1,引入这个字段的主要目的是为了提高计算效率*/ uint nNumOfElements;/*记录HashTable当前保存的数据元素的个数*/ ulong nNextFreeElement;/*记录HashTable中下一个可用于插入数据元素的arBuckets的索引*/ Bucket *pInternalPointer;/* Used for element traversal */ Bucket *pListHead;/*Bucket双向链表的第一个元素*/ Bucket *pListTail;/*Bucket双向链表的最后一元素*/ Bucket **arBuckets;/*存储Bucket双向链表*/ dtor_func_t pDestructor;/*函数指针,在HashTable的增加、修改、删除Bucket时自动调用,用于处理相关数据的清理工作*/ zend_bool persistent;/*指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用PHP的内存分配函数。*/ unsigned char nApplyCount;/*nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制*/ zend_bool bApplyProtection;} HashTable; typedef struct _zend_hash_key { char *arKey; uint nKeyLength; ulong h;} zend_hash_key; typedef zend_bool (*merge_checker_func_t)(HashTable *target_ht, void *source_data, zend_hash_key *hash_key, void *pParam); #define CONNECT_TO_BUCKET_DLLIST(element, list_head) \ (element)->pNext = (list_head); \ (element)->pLast = NULL; \ if ((element)->pNext) { \ (element)->pNext->pLast = (element); \ } #define CONNECT_TO_GLOBAL_DLLIST(element, ht) \ (element)->pListLast = (ht)->pListTail; \ (ht)->pListTail = (element); \ (element)->pListNext = NULL; \ if ((element)->pListLast != NULL) { \ (element)->pListLast->pListNext = (element); \ } \ if (!(ht)->pListHead) { \ (ht)->pListHead = (element); \ } \ if ((ht)->pInternalPointer == NULL) { \ (ht)->pInternalPointer = (element); \ } #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ if ((ht)->nNumOfElements > (ht)->nTableSize) {\ zend_hash_do_resize(ht); \ } int zend_hash_rehash(HashTable *ht) { Bucket *p; uint nIndex; memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *)); p = ht->pListHead; while (p != NULL) { nIndex = p->h & ht->nTableMask; CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); ht->arBuckets[nIndex] = p; p = p->pListNext; } return SUCCESS;} static int zend_hash_do_resize(HashTable *ht) { Bucket **t; 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) { ht->arBuckets = t; ht->nTableSize = (ht->nTableSize << 1); ht->nTableMask = ht->nTableSize - 1; zend_hash_rehash(ht); return SUCCESS; } return FAILURE; } return SUCCESS;} #define UPDATE_DATA(ht, p, pData, nDataSize) \ if (nDataSize == sizeof(void*)) { \ if ((p)->pData != &(p)->pDataPtr) { \ pefree_rel((p)->pData, (ht)->persistent); \ } \ memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \ (p)->pData = &(p)->pDataPtr; \ } else { \ if ((p)->pData == &(p)->pDataPtr) { \ (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \ (p)->pDataPtr=NULL; \ } else { \ (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);\ /* (p)->pDataPtr is already NULL so no need to initialize it */ \ } \ memcpy((p)->pData, pData, nDataSize); \ } #define INIT_DATA(ht, p, pData, nDataSize); \ if (nDataSize == sizeof(void*)) { \ memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \ (p)->pData = &(p)->pDataPtr; \ } else { \ (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\ if (!(p)->pData) { \ pefree_rel(p, (ht)->persistent); \ return FAILURE; \ } \ memcpy((p)->pData, pData, nDataSize); \ (p)->pDataPtr=NULL; \ } static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength) { register ulong hash = 5381; /* variant with the hash unrolled eight times */ for (; nKeyLength >= 8; nKeyLength -= 8) { hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; hash = ((hash << 5) + hash) + *arKey++; } switch (nKeyLength) { case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */ case 1: hash = ((hash << 5) + hash) + *arKey++; break; case 0: break; } return hash;}ulong zend_hash_func(char *arKey, uint nKeyLength) { return zend_inline_hash_func(arKey, nKeyLength);} //省略了int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor) { uint i = 3; Bucket **tmp; zend_bool persistent = 1; if (nSize >= 0x80000000) {/* prevent overflow */ 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; tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *)); if (!tmp) { return FAILURE; } ht->arBuckets = tmp; return SUCCESS;} int zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag) { ulong h; uint nIndex; Bucket *p; if (nKeyLength <= 0) { 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; } if (ht->pDestructor) { ht->pDestructor(p->pData); } UPDATE_DATA(ht, p, pData, nDataSize); if (pDest) { *pDest = p->pData; } 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;} CONNECT_TO_GLOBAL_DLLIST(p, ht);ht->arBuckets[nIndex] = p; ht->nNumOfElements++;ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */return SUCCESS;} void zend_hash_destroy(HashTable *ht) { Bucket *p, *q; p = ht->pListHead; while (p != NULL) { q = p; p = p->pListNext; if (ht->pDestructor) { ht->pDestructor(q->pData); } if (q->pData != &q->pDataPtr) { pefree(q->pData, ht->persistent); } pefree(q, ht->persistent); } pefree(ht->arBuckets, ht->persistent); } int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength, void **pData) { ulong h; uint nIndex; Bucket *p; 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)) { *pData = p->pData; return SUCCESS; } } p = p->pNext;}return FAILURE;} void zend_hash_display(HashTable *ht) { Bucket *p; uint i; int flag = 0 ; for (i = 0; i < ht->nTableSize; i++) { p = ht->arBuckets[i]; flag = 0; while (p != NULL) { printf("(%d %s <==> 0x%lX %d) ", i, p->arKey, p->h, p->pNext); p = p->pNext; flag = 1; } if (flag == 1) { printf("\n"); } } p = ht->pListTail; while (p != NULL) { printf("%s <==> 0x%lX\n", p->arKey, p->h); p = p->pListLast; }}int main() { int i; char ch[20]; HashTable ht; zend_hash_init(&ht, 50, NULL, NULL); for (i = 30; i < 68; i++) { sprintf(ch, "%d", i); ch[strlen(ch) + 1] = '\0'; zend_hash_add_or_update(&ht, ch, strlen(ch) + 1, NULL, 0, NULL, 0); } zend_hash_display(&ht); zend_hash_destroy(&ht); return 0;}?>
以上就是本文的全部内容,希望对大家的学习有所帮助,更多相关内容请关注PHP中文网!
相关推荐:
以上是关于PHP源码中HashTable的解析的详细内容。更多信息请关注PHP中文网其他相关文章!