About the analysis of HashTable in PHP source code
这篇文章主要介绍了关于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中文网！
相关推荐：
The above is the detailed content of About the analysis of HashTable in PHP source code. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1359
52
Using the isEmpty() method of the Hashtable class in Java to determine whether the hash table is empty
Jul 24, 2023 pm 02:21 PM
In Java, the isEmpty() method of the Hashtable class is used to determine whether the hash table is empty. The hash table is one of the commonly used data structures in the Java collection framework. It implements the storage and retrieval of key-value pairs. In the Hashtable class, the isEmpty() method is used to determine whether the hash table is empty. This article will introduce how to use the isEmpty() method of the Hashtable class and provide corresponding code examples. First, we need to understand the Hashtable class. Hash
What is php source code
Oct 11, 2019 am 09:35 AM
PHP source code refers to PHP source code. Source code is the basis of programs and websites, and PHP, the "hypertext preprocessor", is a general open source scripting language.
Use the containsKey() method of the Hashtable class in Java to determine whether the key exists in the hash table
Jul 25, 2023 pm 12:00 PM
In Java, the containsKey() method of the Hashtable class is used to determine whether the key exists in the hash table. In Java programming, the Hashtable class can be used to store and manage data using a hash table. A hash table is a data structure used to store key-value pairs, enabling fast data access by mapping keys to values. In the actual programming process, we often need to determine whether a specific key exists in the hash table. In order to achieve this function, we can use the Hashtable class to provide
PHP source code running problem: index error solution
Mar 09, 2024 pm 09:24 PM
PHP source code running problem: Index error resolution requires specific code examples. PHP is a widely used server-side scripting language that is often used to develop dynamic websites and web applications. However, sometimes you will encounter various problems when running PHP source code, among which "index error" is a common situation. This article will introduce some common causes and solutions of index errors, and provide specific code examples to help readers better deal with such problems. Problem Description: When running a PHP program
Use the put() method of the Hashtable class to insert key-value pairs into the Hashtable
Jul 25, 2023 am 09:29 AM
Hashtable is a data structure class in Java used to store key-value pairs. It is based on the implementation of hash table and can efficiently perform insertion, search and deletion operations of elements. In the Hashtable class, the method for inserting key-value pairs is the put() method. The put() method is used to insert the specified key-value pair into the Hashtable. It accepts two parameters. The first parameter is the key, which is used to uniquely identify a value; the second parameter is the value, which is the data to be stored.
Using the size() method of the Hashtable class in Java to obtain the number of key-value pairs in the hash table
Jul 24, 2023 pm 09:05 PM
In Java, use the size() method of the Hashtable class to obtain the number of key-value pairs in the hash table. A hash table (Hashtable) is a key-value pair storage structure that uses a hash function to map keys to storage locations to achieve efficient data Find. In Java, Hashtable is a thread-safe hash table implementation class that provides rich operation methods and properties. The size() method in the Hashtable class can be used to obtain the number of key-value pairs in the hash table. Below we will pass the code
Use the containsValue() method of the Hashtable class in Java to determine whether a value exists in the hash table
Jul 25, 2023 am 11:05 AM
In Java, the containsValue() method of the Hashtable class is used to determine whether a value exists in a hash table. A hash table is a data structure that stores data in the form of key-value pairs. It provides an efficient way to access data. The Hashtable class in Java is a data structure that implements a hash table. It provides a variety of methods for operating data in the hash table. In actual development, we often encounter the need to determine whether a certain value exists in the hash table. Hash in Java
How to display elements of a Hashtable in Java using enumeration?
Sep 16, 2023 pm 12:41 PM
A Hashtable is a powerful data structure in Java that allows programmers to store and organize data in the form of key-value pairs. Many applications require retrieving and displaying entries from a Hashtable. In a Hashtable, any non-null object can be used as a key or value. However, in order to successfully store and retrieve items in a Hashtable, the object used as the key must implement the equals() method and the hashCode() method. These implementations ensure the correctness of key comparisons and hashing, enabling efficient management and retrieval of data in Hashtables. Throughtheutilizationofthekeys()andelement
