집 > 기사 > 백엔드 개발 > PHP 소스 코드의 HashTable 분석에 대해

PHP 소스 코드의 HashTable 분석에 대해

不言원래의: 2018-06-28 16:12:511644검색

这篇文章主要介绍了关于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&lt;&lt;0)#define HASH_ADD (1&lt;&lt;1)#define HASH_NEXT_INSERT(1&lt;&lt;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)-&gt;pNext = (list_head); \
(element)-&gt;pLast = NULL; \
if ((element)-&gt;pNext) { \
    (element)-&gt;pNext-&gt;pLast = (element); \
} #define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
(element)-&gt;pListLast = (ht)-&gt;pListTail; \
(ht)-&gt;pListTail = (element); \
(element)-&gt;pListNext = NULL; \
if ((element)-&gt;pListLast != NULL) { \
    (element)-&gt;pListLast-&gt;pListNext = (element); \
} \
if (!(ht)-&gt;pListHead) { \
    (ht)-&gt;pListHead = (element); \
} \
if ((ht)-&gt;pInternalPointer == NULL) { \
    (ht)-&gt;pInternalPointer = (element); \
} #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)-&gt;nNumOfElements &gt; (ht)-&gt;nTableSize) {\
    zend_hash_do_resize(ht); \
} int zend_hash_rehash(HashTable *ht) {
    Bucket *p;
    uint nIndex; 
     memset(ht-&gt;arBuckets, 0, ht-&gt;nTableSize * sizeof(Bucket *));
    p = ht-&gt;pListHead;
    while (p != NULL) {
        nIndex = p-&gt;h &amp; ht-&gt;nTableMask;
        CONNECT_TO_BUCKET_DLLIST(p, ht-&gt;arBuckets[nIndex]);
        ht-&gt;arBuckets[nIndex] = p;
        p = p-&gt;pListNext;
    }
    return SUCCESS;} static int zend_hash_do_resize(HashTable *ht) {
    Bucket **t;     if ((ht-&gt;nTableSize &lt;&lt; 1) &gt; 0) {/* Let&#39;s double the table size */
        t = (Bucket **) perealloc_recoverable(ht-&gt;arBuckets, (ht-&gt;nTableSize &lt;&lt; 1) * sizeof(Bucket *), ht-&gt;persistent);
        if (t) {
            ht-&gt;arBuckets = t;
            ht-&gt;nTableSize = (ht-&gt;nTableSize &lt;&lt; 1);
            ht-&gt;nTableMask = ht-&gt;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)-&gt;pData != &amp;(p)-&gt;pDataPtr) { \
pefree_rel((p)-&gt;pData, (ht)-&gt;persistent); \
} \
memcpy(&amp;(p)-&gt;pDataPtr, pData, sizeof(void *)); \
(p)-&gt;pData = &amp;(p)-&gt;pDataPtr; \
} else { \
    if ((p)-&gt;pData == &amp;(p)-&gt;pDataPtr) { \
        (p)-&gt;pData = (void *) pemalloc_rel(nDataSize, (ht)-&gt;persistent); \
        (p)-&gt;pDataPtr=NULL; \
    } else { \
        (p)-&gt;pData = (void *) perealloc_rel((p)-&gt;pData, nDataSize, (ht)-&gt;persistent);\
/* (p)-&gt;pDataPtr is already NULL so no need to initialize it */ \
    } \
    memcpy((p)-&gt;pData, pData, nDataSize); \
} #define INIT_DATA(ht, p, pData, nDataSize); \
if (nDataSize == sizeof(void*)) { \
memcpy(&amp;(p)-&gt;pDataPtr, pData, sizeof(void *)); \
(p)-&gt;pData = &amp;(p)-&gt;pDataPtr; \
} else { \
    (p)-&gt;pData = (void *) pemalloc_rel(nDataSize, (ht)-&gt;persistent);\
    if (!(p)-&gt;pData) { \
        pefree_rel(p, (ht)-&gt;persistent); \
        return FAILURE; \
    } \
    memcpy((p)-&gt;pData, pData, nDataSize); \
    (p)-&gt;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 &gt;= 8; nKeyLength -= 8) {
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
        hash = ((hash &lt;&lt; 5) + hash) + *arKey++;
    }
    switch (nKeyLength) {
        case 7: hash = ((hash &lt;&lt; 5) + hash) + *arKey++; /* fallthrough... */
        case 6: hash = ((hash &lt;&lt; 5) + hash) + *arKey++; /* fallthrough... */
        case 5: hash = ((hash &lt;&lt; 5) + hash) + *arKey++; /* fallthrough... */
        case 4: hash = ((hash &lt;&lt; 5) + hash) + *arKey++; /* fallthrough... */
        case 3: hash = ((hash &lt;&lt; 5) + hash) + *arKey++; /* fallthrough... */
        case 2: hash = ((hash &lt;&lt; 5) + hash) + *arKey++; /* fallthrough... */
        case 1: hash = ((hash &lt;&lt; 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 &gt;= 0x80000000) {/* prevent overflow */
        ht-&gt;nTableSize = 0x80000000;
    } else {
        while ((1U &lt;&lt; i) &lt; nSize) {
            i++;
        }
        ht-&gt;nTableSize = 1 &lt;&lt; i;
    } 
    ht-&gt;nTableMask = ht-&gt;nTableSize - 1;
    ht-&gt;pDestructor = pDestructor;
    ht-&gt;arBuckets = NULL;
    ht-&gt;pListHead = NULL;
    ht-&gt;pListTail = NULL;
    ht-&gt;nNumOfElements = 0;
    ht-&gt;nNextFreeElement = 0;
    ht-&gt;pInternalPointer = NULL;
    ht-&gt;persistent = persistent;
    ht-&gt;nApplyCount = 0;
    ht-&gt;bApplyProtection = 1; 
 
    tmp = (Bucket **) calloc(ht-&gt;nTableSize, sizeof(Bucket *));
    if (!tmp) {
        return FAILURE;
    }
    ht-&gt;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 &lt;= 0) {
        return FAILURE;
    } 
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h &amp; ht-&gt;nTableMask; 
    p = ht-&gt;arBuckets[nIndex];     while (p != NULL) {
        if ((p-&gt;h == h) &amp;&amp; (p-&gt;nKeyLength == nKeyLength)) {
            if (!memcmp(p-&gt;arKey, arKey, nKeyLength)) {
                if (flag &amp; HASH_ADD) {
                    return FAILURE;
                }                 if (ht-&gt;pDestructor) {
                    ht-&gt;pDestructor(p-&gt;pData);
                }
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                *pDest = p-&gt;pData;
            }
            return SUCCESS;
        }
    }
    p = p-&gt;pNext;} 
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht-&gt;persistent);if (!p) {
    return FAILURE;}memcpy(p-&gt;arKey, arKey, nKeyLength);p-&gt;nKeyLength = nKeyLength;INIT_DATA(ht, p, pData, nDataSize);p-&gt;h = h;CONNECT_TO_BUCKET_DLLIST(p, ht-&gt;arBuckets[nIndex]);if (pDest) {*pDest = p-&gt;pData;} 
 
CONNECT_TO_GLOBAL_DLLIST(p, ht);ht-&gt;arBuckets[nIndex] = p; 
 
ht-&gt;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-&gt;pListHead;
    while (p != NULL) {
        q = p;
        p = p-&gt;pListNext;
        if (ht-&gt;pDestructor) {
            ht-&gt;pDestructor(q-&gt;pData);
        }
        if (q-&gt;pData != &amp;q-&gt;pDataPtr) {
            pefree(q-&gt;pData, ht-&gt;persistent);
        }
        pefree(q, ht-&gt;persistent);
    }
    pefree(ht-&gt;arBuckets, ht-&gt;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-&gt;nTableMask; 
    p = ht-&gt;arBuckets[nIndex];
    while (p != NULL) {
        if ((p-&gt;h == h) &amp;&amp; (p-&gt;nKeyLength == nKeyLength)) {
            if (!memcmp(p-&gt;arKey, arKey, nKeyLength)) {
            *pData = p-&gt;pData;
            return SUCCESS;
        }
    }
    p = p-&gt;pNext;}return FAILURE;} 
 void zend_hash_display(HashTable *ht) {
    Bucket *p;
    uint i;
    int flag  = 0 ;     for (i = 0; i &lt; ht-&gt;nTableSize; i++) {
        p = ht-&gt;arBuckets[i];
        flag = 0;
        while (p != NULL) {
            printf("(%d %s &lt;==&gt; 0x%lX %d)   ", i, p-&gt;arKey, p-&gt;h, p-&gt;pNext);
            p = p-&gt;pNext;
            flag = 1;
        }
        if (flag == 1) {
            printf("\n");
        }     } 
    p = ht-&gt;pListTail;
    while (p != NULL) {
        printf("%s &lt;==&gt; 0x%lX\n", p-&gt;arKey, p-&gt;h);
        p = p-&gt;pListLast;
    }}int main() {
    int i;
    char ch[20];
    HashTable ht;
    zend_hash_init(&amp;ht, 50, NULL, NULL);
    for (i = 30; i &lt; 68; i++) {
        sprintf(ch, "%d", i);
        ch[strlen(ch) + 1] = &#39;\0&#39;;
        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;}?&gt;

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

PHP 소스 코드의 HashTable 분석에 대해

관련 기사