月度归档:2009年12月

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 打印出来。 相信这会给一些想学习源码的童鞋一些帮助。 源代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
<!-- 
#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'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] = '\0';
        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源代码分析:Zend HashTable详解【转】

PHP源代码分析:Zend HashTable详解
很久以前就看到这篇文章,最近兴趣转移到PHP源码,在网上找一圈,在think in code 上找到了这篇地址:http://www.blankyao.cn/index.php/php-zend-hashtable.html,转载如下:
另,原作者的地址为http://www.phpinternals.com,不过貌似无法访问了。。。杯具啊
【正文】
By Altair(eniac2008@hotmail.com), http://www.phpinternals.com

本文的PDF版本下载地址:http://www.phpinternals.com/download/zend_hash_v0.2.pdf

在PHP的Zend引擎中,有一个数据结构非常重要,它无处不在,是PHP数据存储的核心,各种常量、变量、函数、类、对象等都用它来组织,这个数据结构就是HashTable。

HashTable在通常的数据结构教材中也称作散列表,哈希表。其基本原理比较简单(如果你对其不熟悉,请查阅随便一本数据结构教材或在网上搜 索),但PHP的实现有其独特的地方。理解了HashTable的数据存储结构,对我们分析PHP的源代码,特别是Zend Engine中的虚拟机的实现时,有很重要的帮助。它可以帮助我们在大脑中模拟一个完整的虚拟机的形象。它也是PHP中其它一些数据结构如数组实现的基 础。

Zend HashTable的实现结合了双向链表和向量(数组)两种数据结构的优点,为PHP提供了非常高效的数据存储和查询机制。

Let’s begin!

一、 HashTable的数据结构

在Zend Engine中的HashTable的实现代码主要包括zend_hash.h, zend_hash.c这两个文件中。Zend HashTable包括两个主要的数据结构,其一是Bucket(桶)结构,另一个是HashTable结构。Bucket结构是用于保存数据的容器,而 HashTable结构则提供了对所有这些Bucket(或桶列)进行管理的机制。

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;

在Zend HashTable中,每个数据元素(Bucket)有一个键名(key),它在整个HashTable中是唯一的,不能重复。根据键名可以唯一确定 HashTable中的数据元素。键名有两种表示方式。第一种方式使用字符串arKey作为键名,该字符串的长度为nKeyLength。注意到在上面的 数据结构中arKey虽然只是一个长度为1的字符数组,但它并不意味着key只能是一个字符。实际上Bucket是一个可变长的结构体,由于arKey是 Bucket的最后一个成员变量,通过arKey与nKeyLength结合可确定一个长度为nKeyLength的key。这是C语言编程中的一个比较 常用的技巧。另一种键名的表示方式是索引方式,这时nKeyLength总是0,长整型字段h就表示该数据元素的键名。简单的来说,即如果 nKeyLength=0,则键名为h;否则键名为arKey, 键名的长度为nKeyLength。

当nKeyLength > 0时,并不表示这时的h值就没有意义。事实上,此时它保存的是arKey对应的hash值。不管hash函数怎么设计,冲突都是不可避免的,也就是说不同 的arKey可能有相同的hash值。具有相同hash值的Bucket保存在HashTable的arBuckets数组(参考下面的解释)的同一个索 引对应的桶列中。这个桶列是一个双向链表,其前向元素,后向元素分别用pLast, pNext来表示。新插入的Bucket放在该桶列的最前面。

在Bucket中,实际的数据是保存在pData指针指向的内存块中,通常这个内存块是系统另外分配的。但有一种情况例外,就是当Bucket保存 的数据是一个指针时,HashTable将不会另外请求系统分配空间来保存这个指针,而是直接将该指针保存到pDataPtr中,然后再将pData指向 本结构成员的地址。这样可以提高效率,减少内存碎片。由此我们可以看到PHP HashTable设计的精妙之处。如果Bucket中的数据不是一个指针,pDataPtr为NULL。

HashTable中所有的Bucket通过pListNext, pListLast构成了一个双向链表。最新插入的Bucket放在这个双向链表的最后。

注意在一般情况下,Bucket并不能提供它所存储的数据大小的信息。所以在PHP的实现中,Bucket中保存的数据必须具有管理自身大小的能力。

typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
 
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

在HashTable结构中,nTableSize指定了HashTable的大小,同时它限定了HashTable中能保存Bucket的最大数量,此 数越大,系统为HashTable分配的内存就越多。为了提高计算效率,系统自动会将nTableSize调整到最小一个不小于nTableSize的2 的整数次方。也就是说,如果在初始化HashTable时指定一个nTableSize不是2的整数次方,系统将会自动调整nTableSize的值。即

nTableSize = 2ceil(log(nTableSize, 2)) 或 nTableSize = pow(ceil(log(nTableSize,2)))

例如,如果在初始化HashTable的时候指定nTableSize = 11,HashTable初始化程序会自动将nTableSize增大到16。

arBuckets是HashTable的关键,HashTable初始化程序会自动申请一块内存,并将其地址赋值给arBuckets,该内存大 小正好能容纳nTableSize个指针。我们可以将arBuckets看作一个大小为nTableSize的数组,每个数组元素都是一个指针,用于指向 实际存放数据的Bucket。当然刚开始时每个指针均为NULL。

nTableMask的值永远是nTableSize – 1,引入这个字段的主要目的是为了提高计算效率,是为了快速计算Bucket键名在arBuckets数组中的索引。

nNumberOfElements记录了HashTable当前保存的数据元素的个数。当nNumberOfElement大于nTableSize时,HashTable将自动扩展为原来的两倍大小。

nNextFreeElement记录HashTable中下一个可用于插入数据元素的arBuckets的索引。

pListHead, pListTail则分别表示Bucket双向链表的第一个和最后一个元素,这些数据元素通常是根据插入的顺序排列的。也可以通过各种排序函数对其进行重 新排列。pInternalPointer则用于在遍历HashTable时记录当前遍历的位置,它是一个指针,指向当前遍历到的Bucket,初始值是 pListHead。

pDestructor是一个函数指针,在HashTable的增加、修改、删除Bucket时自动调用,用于处理相关数据的清理工作。

persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用PHP的内存分配函数。具体请参考PHP的内存管理。

nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制。

inconsistent成员用于调试目的,只在PHP编译成调试版本时有效。表示HashTable的状态,状态有四种:

状态值 含义
HT_IS_DESTROYING 正在删除所有的内容,包括arBuckets本身
HT_IS_DESTROYED 已删除,包括arBuckets本身
HT_CLEANING 正在清除所有的arBuckets指向的内容,但不包括arBuckets本身
HT_OK 正常状态,各种数据完全一致

typedef struct _zend_hash_key {
char *arKey;      /* hash元素key名称 */
uint nKeyLength;     /* hash 元素key长度 */
ulong h;       /* key计算出的hash值或直接指定的数值下标 */
} zend_hash_key;

现在来看zend_hash_key结构就比较容易理解了。它通过arKey, nKeyLength, h三个字段唯一确定了HashTable中的一个元素。

根据上面对HashTable相关数据结构的解释,我们可以画出HashTable的内存结构图:

hashtable结构

hashtable结构

二、 Zend HashTable的实现

本节具体介绍一下PHP中HashTable的实现。以下函数均取自于zend_hash.c。只要充分理解了上述数据结构,HashTable实现的代码并不难理解。

1 HashTable初始化

HashTable提供了一个zend_hash_init宏来完成HashTable的初始化操作。实际上它是通过下面的内部函数来实现的:

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
uint i = 3;
Bucket **tmp;
 
SET_INCONSISTENT(HT_OK);
 
if (nSize &gt;= 0×80000000) {
/* prevent overflow */
ht-&gt;nTableSize = 0×80000000;
} else {
while ((1U &lt;&lt; i) &lt; nSize) { /* 自动调整nTableSize至2的n次方 */ i++; } ht-&gt;nTableSize = 1 &lt;&lt; i;     /* i的最小值为3,因此HashTable大小最小为8 */ } 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;
 
/* 根据persistent使用不同方式分配arBuckets内存,并将其所有指针初始化为NULL*/
/* Uses ecalloc() so that Bucket* == NULL */
if (persistent) {
tmp = (Bucket **) calloc(ht-&gt;nTableSize, sizeof(Bucket *));
if (!tmp) {
return FAILURE;
}
ht-&gt;arBuckets = tmp;
} else {
tmp = (Bucket **) ecalloc_rel(ht-&gt;nTableSize, sizeof(Bucket *));
if (tmp) {
ht-&gt;arBuckets = tmp;
}
}
 
return SUCCESS;
}

在以前的版本中,可以使用pHashFunction来指定hash函数。但现PHP已强制使用DJBX33A算法,因此实际上pHashFunction这个参数并不会用到,保留在这里只是为了与以前的代码兼容。

2 增加、插入和修改元素

向HashTable中添加一个新的元素最关键的就是要确定将这个元素插入到arBuckets数组中的哪个位置。根据上面对Bucket结构键名 的解释,我们可以知道有两种方式向HashTable添加一个新的元素。第一种方法是使用字符串作为键名来插入Bucket;第二种方法是使用索引作为键 名来插入Bucket。第二种方法具体又可以分为两种情况:指定索引或不指定索引,指定索引指的是强制将Bucket插入到指定的索引位置中;不指定索引 则将Bucket插入到nNextFreeElement对应的索引位置中。这几种插入数据的方法实现比较类似,不同的只是定位Bucket的方法。

修改HashTable中的数据的方法与增加数据的方法也很类似。

我们先看第一种使用字符串作为键名增加或修改Bucket的方法:

ZEND_API int _zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
ulong h;
uint nIndex;
Bucket *p;
 
IS_CONSISTENT(ht);     // 调试信息输出
 
if (nKeyLength &lt;= 0) { #if ZEND_DEBUG ZEND_PUTS(”zend_hash_update: Can’t put in empty key\n”); #endif return FAILURE; } /* 使用hash函数计算arKey的hash值 */ h = zend_inline_hash_func(arKey, nKeyLength); /* 将hash值和nTableMask按位与后生成该元素在arBuckets中的索引。让它和 * nTableMask按位与是保证不会产生一个使得arBuckets越界的数组下标。 */ nIndex = h &amp; ht-&gt;nTableMask;
 
p = ht-&gt;arBuckets[nIndex];   /* 取得相应索引对应的Bucket的指针 */
 
/* 检查对应的桶列中是否包含有数据元素(key, hash) */
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; // 对应的数据元素已存在,不能进行插入操作
}
HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
if (p-&gt;pData == pData) {
ZEND_PUTS(”Fatal error in zend_hash_update: p-&gt;pData == pData\n”);
HANDLE_UNBLOCK_INTERRUPTIONS();
return FAILURE;
}
#endif
if (ht-&gt;pDestructor) {
/* 如果数据元素存在,对原来的数据进行析构操作 */
ht-&gt;pDestructor(p-&gt;pData);
}
/* 用新的数据来更新原来的数据 */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p-&gt;pData;
}
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
}
}
p = p-&gt;pNext;
}
 
/* HashTable中没有key对应的数据,新增一个Bucket */
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;
// 将Bucket加入到相应的桶列中
CONNECT_TO_BUCKET_DLLIST(p, ht-&gt;arBuckets[nIndex]);
if (pDest) {
*pDest = p-&gt;pData;
}
 
HANDLE_BLOCK_INTERRUPTIONS();
// 将Bucket 加入到HashTable的双向链表中
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht-&gt;arBuckets[nIndex] = p;
HANDLE_UNBLOCK_INTERRUPTIONS();
 
ht-&gt;nNumOfElements++;
// 如果HashTable已满,重新调整HashTable的大小。
ZEND_HASH_IF_FULL_DO_RESIZE(ht);   /* If the Hash table is full, resize it */
return SUCCESS;
}

因为这个函数是使用字符串作为键名来插入数据的,因此它首先检查nKeyLength的值是否大于0,如果不是的话就直接退出。然后计算arKey对应的 hash值h,将其与nTableMask按位与后得到一个无符号整数nIndex。这个nIndex就是将要插入的Bucket在arBuckets数 组中的索引位置。
现在已经有了arBuckets数组的一个索引,我们知道它包括的数据是一个指向Bucket的双向链表的指针。如果这个双向链表不为空的话我们首先检查 这个双向链表中是否已经包含了用字符串arKey指定的键名的Bucket,这样的Bucket如果存在,并且我们要做的操作是插入新Bucket(通过 flag标识),这时就应该报错 – 因为在HashTable中键名不可以重复。如果存在,并且是修改操作,则使用在HashTable中指定了析构函数pDestructor对原来的 pData指向的数据进行析构操作;然后将用新的数据替换原来的数据即可成功返回修改操作。
如果在HashTable中没有找到键名指定的数据,就将该数据封装到Bucket中,然后插入HashTable。这里要注意的是如下的两个宏:
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex])
CONNECT_TO_GLOBAL_DLLIST(p, ht)
前者是将该Bucket插入到指定索引的Bucket双向链表中,后者是插入到整个HashTable的Bucket双向链表中。两者的插入方式也不同,前者是将该Bucket插入到双向链表的最前面,后者是插入到双向链表的最末端。

下面是第二种插入或修改Bucket的方法,即使用索引的方法:

ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
uint nIndex;
Bucket *p;
 
IS_CONSISTENT(ht);
 
if (flag &amp; HASH_NEXT_INSERT) {
h = ht-&gt;nNextFreeElement;
}
nIndex = h &amp; ht-&gt;nTableMask;
 
p = ht-&gt;arBuckets[nIndex];
 
// 检查是否含有相应的数据
while (p != NULL) {
if ((p-&gt;nKeyLength == 0) &amp;&amp; (p-&gt;h == h)) {
if (flag &amp; HASH_NEXT_INSERT || flag &amp; HASH_ADD) {
return FAILURE;
}
//
// …… 修改Bucket数据,略
//
if ((long)h &gt;= (long)ht-&gt;nNextFreeElement) {
ht-&gt;nNextFreeElement = h + 1;
}
if (pDest) {
*pDest = p-&gt;pData;
}
return SUCCESS;
}
p = p-&gt;pNext;
}
p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht-&gt;persistent);
if (!p) {
return FAILURE;
}
p-&gt;nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
p-&gt;h = h;
INIT_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p-&gt;pData;
}
 
CONNECT_TO_BUCKET_DLLIST(p, ht-&gt;arBuckets[nIndex]);
 
HANDLE_BLOCK_INTERRUPTIONS();
ht-&gt;arBuckets[nIndex] = p;
CONNECT_TO_GLOBAL_DLLIST(p, ht);
HANDLE_UNBLOCK_INTERRUPTIONS();
 
if ((long)h &gt;= (long)ht-&gt;nNextFreeElement) {
ht-&gt;nNextFreeElement = h + 1;
}
ht-&gt;nNumOfElements++;
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
return SUCCESS;
}

flag标志指明当前操作是HASH_NEXT_INSERT(不指定索引插入或修改), HASH_ADD(指定索引插入)还是HASH_UPDATE(指定索引修改)。由于这些操作的实现代码基本相同,因此统一合并成了一个函数,再用flag加以区分。
本函数基本与前一个相同,不同的是如果确定插入到arBuckets数组中的索引的方法。如果操作是HASH_NEXT_INSERT,则直接使用nNextFreeElement作为插入的索引。注意nNextFreeElement的值是如何使用和更新的。
3 访问元素
同样,HashTable用两种方式来访问元素,一种是使用字符串arKey的zend_hash_find();另一种是使用索引的访问方式zend_hash_index_find()。由于其实现的代码很简单,分析工作就留给读者自已完成。
4 删除元素
HashTable删除数据均使用zend_hash_del_key_or_index()函数来完成,其代码也较为简单,这里也不再详细分析。需要的是注意如何根据arKey或h来计算出相应的下标,以及两个双向链表的指针的处理。
5 遍历元素

/* This is used to recurse elements and selectively delete certain entries
* from a hashtable. apply_func() receives the data and decides if the entry
* should be deleted or recursion should be stopped. The following three
* return codes are possible:
* ZEND_HASH_APPLY_KEEP   - continue
* ZEND_HASH_APPLY_STOP   - stop iteration
* ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
*/
 
ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
{
Bucket *p;
 
IS_CONSISTENT(ht);
 
HASH_PROTECT_RECURSION(ht);
p = ht-&gt;pListHead;
while (p != NULL) {
int result = apply_func(p-&gt;pData TSRMLS_CC);
 
if (result &amp; ZEND_HASH_APPLY_REMOVE) {
p = zend_hash_apply_deleter(ht, p);
} else {
p = p-&gt;pListNext;
}
if (result &amp; ZEND_HASH_APPLY_STOP) {
break;
}
}
HASH_UNPROTECT_RECURSION(ht);
}

因为HashTable中所有Bucket都可以通过pListHead指向的双向链表来访问,因此遍历HashTable的实现也比较简单。这里值得一 提的是对当前遍历到的Bucket的处理使用了一个apply_func_t类型的回调函数。根据实际需要,该回调函数返回下面值之一:

ZEND_HASH_APPLY_KEEP
ZEND_HASH_APPLY_STOP
ZEND_HASH_APPLY_REMOVE

它们分别表示继续遍历,停止遍历或删除相应元素后继续遍历。

还有一个要注意的问题就是遍历时的防止递归的问题,也就是防止对同一个HashTable同时进行多次遍历。这是用下面两个宏来实现的:
HASH_PROTECT_RECURSION(ht)
HASH_UNPROTECT_RECURSION(ht)
其主要原理是如果遍历保护标志bApplyProtection为真,则每次进入遍历函数时将nApplyCount值加1,退出遍历函数时将nApplyCount值减1。开始遍历之前如果发现nApplyCount > 3就直接报告错误信息并退出遍历。

上面的apply_func_t不带参数。HashTable还提供带一个参数或可变参数的回调方式,对应的遍历函数分别为:

typedef int (*apply_func_arg_t)(void *pDest,void *argument TSRMLS_DC);
void zend_hash_apply_with_argument(HashTable *ht,
apply_func_arg_t apply_func, void *data TSRMLS_DC);
 
typedef int (*apply_func_args_t)(void *pDest,
int num_args, va_list args, zend_hash_key *hash_key);
void zend_hash_apply_with_arguments(HashTable *ht,
apply_func_args_t apply_func, int numargs,);

除了上面提供的几种提供外,还有许多其它操作HashTable的API。如排序、HashTable的拷贝与合并等等。只要充分理解了上述HashTable的数据结构,理解这些代码并不困难。

mysql各版本之间的差别

在PHP面试中经常会遇到关于mysql各版本之间差别的问题,
翻看以前的书籍(《MySQL5 权威指南》)找到如下答案,另外参考了如下网址的部分内容
摘抄如下:
功能 版本(开始支持的版本)

镜像(动态复制)                                             3.23
在MyISAM数据表中进行全文搜索              3.23
BDB数据表开始支持事务                                3.23.34
InnoDB数据表开始支持事务处理                3.23.34
InnoDB数据表上的引用集成性检查功能   3.23.34
==================================
Delete和跨多个数据表的Delete                  4.0
跨多个数据表的UPDATE                               4.0
UNION(合并多个SELECT结果)                   4.0
查询缓冲区(加快重复执行的SQL命令的执行速度) 4.0
嵌入式MySQL库                                               4.0
加密通信(SSL)                                             4.0
InnoDB数据表开始支持热备份                    4.0
适用于客户软件共享函数库的GPL许可证   4.0
================================
子查询                                                                   4.1
支持Unicode(UTF8和UCS2=UTF16)        4.1
支持GIS(GEOMETRY数据类型,R树索引)        4.1
可变语句(带参数的SQL命令)                      4.1
GROUP BY 语句增加ROLLUP子句                 4.1
mysql.user数据表采用了更好的口令字加密算法      4.1
允许单个数据表单独存在一个InnoDB表空间文件里   4.1
======================================
VARCHAR类型的数据列可以容纳超过255个字符      5.0
引入了了BIT数据类型                                          5.0
存储过程                                                                  5.0
触发器                                                       5.0
视图                                                           5.0
游标                                                           5.0
更节约空间的InnoDB表空间格式                          5.0
新的数据库架构管理方案(数据字典,INFORMATION_SCHEMA数据库)5.0
====================================================
FULL OUTER JOIN                     5.1
事件调度                                                5.1
分区                                                        5.1
基于行的备份                                      5.1
插件API                                               5.1
服务器日志表                                     5.1
外键 6.x (3.23版本中已在innoDB中实现)

以上所示的版本是指开始支持的版本