关于PHP源码中HashTable的解析

2020-03-22 17:37:29

字体：大中小

来源：转载

供稿：网友

这篇文章主要介绍了关于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 html' target='_blank'>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 amp; 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;} 
 if ((p)- pData == amp;(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( amp;(p)- pDataPtr, pData, sizeof(void *)); /(p)- pData = amp;(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 amp; ht- nTableMask;  p = ht- arBuckets[nIndex]; while (p != NULL) { if ((p- h == h) amp; amp; (p- nKeyLength == nKeyLength)) { if (!memcmp(p- arKey, arKey, nKeyLength)) { if (flag amp; 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 != amp;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 amp; ht- nTableMask;  p = ht- arBuckets[nIndex]; while (p != NULL) { if ((p- h == h) amp; amp; (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( amp;ht, 50, NULL, NULL); for (i = 30; i 68; i++) { sprintf(ch, %d , i); ch[strlen(ch) + 1] = /0  zend_hash_add_or_update( amp;ht, ch, strlen(ch) + 1, NULL, 0, NULL, 0); zend_hash_display( amp;ht); zend_hash_destroy( amp;ht); return 0;}?

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP ！