关于PHP源码中HashTable的解析
这篇文章主要介绍了关于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中文网其他相关文章！
本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
AI Hentai Generator
免费生成ai无尽的。
热门文章
R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
1 周前
By DDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
在哪里可以找到原子中的起重机控制钥匙卡
1 周前
By DDD
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
Java中使用Hashtable类的isEmpty()方法判断哈希表是否为空
Jul 24, 2023 pm 02:21 PM
Java中使用Hashtable类的isEmpty()方法判断哈希表是否为空哈希表是Java集合框架中常用的数据结构之一，它实现了键值对的存储和检索。在Hashtable类中，isEmpty()方法用于判断哈希表是否为空。本文将介绍如何使用Hashtable类的isEmpty()方法，并提供相应的代码示例。首先，我们需要了解一下Hashtable类。Hash
Java中使用Hashtable类的containsKey()方法判断键是否存在于哈希表中
Jul 25, 2023 pm 12:00 PM
Java中使用Hashtable类的containsKey()方法判断键是否存在于哈希表中在Java编程中，使用Hashtable类可以使用哈希表来存储和管理数据。哈希表是一种用于存储键值对的数据结构，通过将键映射到值来实现快速的数据访问。在实际的编程过程中，我们经常需要判断某个特定的键是否存在于哈希表中。为了实现这个功能，我们可以使用Hashtable类提
PHP源码运行问题：index报错解决方法
Mar 09, 2024 pm 09:24 PM
PHP源码运行问题：index报错解决方法，需要具体代码示例PHP是一种广泛使用的服务器端脚本语言，经常被用于开发动态网站和Web应用程序。然而，有时候在运行PHP源码时会遇到各种问题，其中“index报错”是比较常见的一种情况。本文将介绍一些常见的index报错原因以及解决方法，并提供具体的代码示例，帮助读者更好地处理这类问题。问题描述：在运行PHP程序时
使用Hashtable类的put()方法将键值对插入到Hashtable中
Jul 25, 2023 am 09:29 AM
Hashtable是Java中的一个数据结构类，用于存储键值对。它基于哈希表的实现方式，可以高效地进行元素的插入、查找和删除操作。在Hashtable类中，插入键值对的方法是put()方法。put()方法用于将指定的键值对插入到Hashtable中。它接受两个参数，第一个参数是键（key），用于唯一地标识一个值；第二个参数是值（value），是要存储的数据。
Java中使用Hashtable类的size()方法获取哈希表中的键值对数量
Jul 24, 2023 pm 09:05 PM
Java中使用Hashtable类的size()方法获取哈希表中的键值对数量哈希表（Hashtable）是一种键值对存储结构，通过哈希函数将键映射到存储位置来实现高效的数据查找。在Java中，Hashtable是一个线程安全的哈希表实现类，它提供了丰富的操作方法和属性。Hashtable类中的size()方法可以用来获取哈希表中的键值对数量。下面我们将通过代
Java中使用Hashtable类的containsValue()方法判断值是否存在于哈希表中
Jul 25, 2023 am 11:05 AM
Java中使用Hashtable类的containsValue()方法判断值是否存在于哈希表中哈希表是一种以键值对形式存储数据的数据结构，它提供了一种高效的数据访问方式。Java中的Hashtable类是实现了哈希表的一种数据结构，它提供了多种方法用于操作哈希表中的数据。在实际开发中，我们经常会遇到需要判断某个值是否存在于哈希表中的需求。Java中的Hash
如何使用枚举在Java中显示Hashtable的元素？
Sep 16, 2023 pm 12:41 PM
一个Hashtable是Java中一种强大的数据结构，允许程序员以键值对的形式存储和组织数据。许多应用程序需要从Hashtable中检索和显示条目。在Hashtable中，任何非空对象都可以作为键或值。然而，为了成功地存储和检索Hashtable中的项，用作键的对象必须实现equals()方法和hashCode()方法。这些实现确保了键的比较和哈希处理的正确性，从而实现了Hashtable中数据的高效管理和检索。Throughtheutilizationofthekeys()andelement
