【原创】实战PHP7内核之哈希表HashTable的官方实现
问题背景:
研究的目的主要就是为了深入学习和理解PHP7内核中哈希表实现原理,因为HashTable是PHP内核最重要的一个数据结构,万能的PHP数组以及函数、类等等的内部实现全都离不开HashTable数据结构;此外对于想熟练编写PHP扩展的码友,学习并理解哈希表也是非常重要的。
获取源码:
https://github.com/blogdaren/PHP7HashTable
头部源码:
/* * ===================================================================================== * * Filename: PHP7HashTable.h * * Description: 哈希表头文件 * * ------------------------------ * / HashTable Data Layout Start / * ------------------------------ * * +=============================+ * | HT_IDX(ht, hN) | * | ... | * | HT_IDX(ht, h2) | * | HT_IDX(ht, h1) | * +-----------------------------+ * ht->arData ---> | Bucket[0] | * | Bucket[1] | * | ... | * | Bucket[ht->tableSize - 1] | * +=============================+ * * ----------------------------- * / HashTable Data Layout End / * ----------------------------- * * Version: 1.0 * Created: 2021年03月4日 16时50分55秒 * Revision: none * Compiler: gcc * Author: blogdaren * Organization: http://www.phpcreeper.com * * ===================================================================================== */ #include <stdio.h> #include <stdlib.h> #include <string.h> typedef int int32_t; typedef unsigned int uint32_t; typedef unsigned char boolean; typedef unsigned long ulong; typedef unsigned short ushort; typedef char * String; typedef struct HashTable HashTable; typedef struct Bucket Bucket; typedef struct BucketValue BucketValue; #define IS_UNDEF (1<<0) #define IS_STRING (1<<1) #define IS_LONG (1<<2) #define IS_DOUBLE (1<<3) #define IS_ARRAY (1<<4) #define USER_API #define SUCCESS 1 #define FAILURE 0 #define HT_MIN_SIZE 8 #define HT_INVALID_IDX ((uint32_t)-1) #define HT_HASH_SIZE(mask) \ (((size_t)(uint32_t)-(int32_t)(mask)) * sizeof(uint32_t)) #define HT_DATA_SIZE(size) \ ((size_t)(size) * sizeof(Bucket)) #define HT_SIZE_TOTAL(mask, size) \ (HT_HASH_SIZE((mask)) + HT_DATA_SIZE((size))) #define HT_SIZE(ht) \ HT_SIZE_TOTAL((ht)->tableMask, (ht)->tableSize) #define HT_GET_HASH_START_ADDRESS(ht) \ ((uint32_t*)((char *)ht->arData - HT_HASH_SIZE(ht->tableMask))) #define HT_OFFSET(ht, h) \ (h | ht->tableMask) #define HT_IDX(ht, h) \ (*((uint32_t*)ht->arData + HT_OFFSET(ht, h))) #define CHECK_WHETHER_NEED_TO_DO_RESIZE(ht) do{ \ if((ht)->positionNumberUsed >= (ht)->tableSize){ \ resizeHashTable(ht); \ } \ }while(0) \ struct HashTable { size_t tableSize; size_t tableMask; size_t positionNumberUsed; size_t validElementNumber; Bucket *arData; }; struct Bucket { ulong h; String key; BucketValue *val; size_t next; }; struct BucketValue { ushort type; ushort flag; union { long lval; double dval; char *str; HashTable *arr; } v; }; //核心实现代码详见:https://github.com/blogdaren/PHP7HashTable
版权声明:除非注明,本文由( blogdaren )原创,转载请保留文章出处。
发表评论: