关于PHP源码中HashTable的解析

内容导读

收集整理的这篇技术教程文章主要介绍了关于PHP源码中HashTable的解析，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10667字，纯文字阅读大概需要16分钟。

内容图文

这篇文章主要介绍了关于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 memoryn");    exit(1);}  inline static void * __zend_realloc(void *p, size_t len) {    p = realloc(p, len);    if (p) {        return p;    }      fprintf(stderr, "Out of memoryn");    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'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%lXn", 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] = '';        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源代码中Zend HashTable的解析

以上就是关于PHP源码中HashTable的解析的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的关于PHP源码中HashTable的解析全部内容，希望文章能够帮你解决关于PHP源码中HashTable的解析所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。