1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2013 Zend Technologies Ltd. (http://www.zend.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 2.00 of the Zend license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.zend.com/license/2_00.txt. |
11 | If you did not receive a copy of the Zend license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@zend.com so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Andi Gutmans <andi@zend.com> |
16 | Zeev Suraski <zeev@zend.com> |
17 +----------------------------------------------------------------------+
18 */
19
20 /* $Id$ */
21
22 #include "zend.h"
23
24 #define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
25 (element)->pNext = (list_head); \
26 (element)->pLast = NULL; \
27 if ((element)->pNext) { \
28 (element)->pNext->pLast = (element); \
29 }
30
31 #define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
32 (element)->pListLast = (ht)->pListTail; \
33 (ht)->pListTail = (element); \
34 (element)->pListNext = NULL; \
35 if ((element)->pListLast != NULL) { \
36 (element)->pListLast->pListNext = (element); \
37 } \
38 if (!(ht)->pListHead) { \
39 (ht)->pListHead = (element); \
40 } \
41 if ((ht)->pInternalPointer == NULL) { \
42 (ht)->pInternalPointer = (element); \
43 }
44
45 #if ZEND_DEBUG
46 #define HT_OK 0
47 #define HT_IS_DESTROYING 1
48 #define HT_DESTROYED 2
49 #define HT_CLEANING 3
50
_zend_is_inconsistent(const HashTable * ht,const char * file,int line)51 static void _zend_is_inconsistent(const HashTable *ht, const char *file, int line)
52 {
53 if (ht->inconsistent==HT_OK) {
54 return;
55 }
56 switch (ht->inconsistent) {
57 case HT_IS_DESTROYING:
58 zend_output_debug_string(1, "%s(%d) : ht=%p is being destroyed", file, line, ht);
59 break;
60 case HT_DESTROYED:
61 zend_output_debug_string(1, "%s(%d) : ht=%p is already destroyed", file, line, ht);
62 break;
63 case HT_CLEANING:
64 zend_output_debug_string(1, "%s(%d) : ht=%p is being cleaned", file, line, ht);
65 break;
66 default:
67 zend_output_debug_string(1, "%s(%d) : ht=%p is inconsistent", file, line, ht);
68 break;
69 }
70 zend_bailout();
71 }
72 #define IS_CONSISTENT(a) _zend_is_inconsistent(a, __FILE__, __LINE__);
73 #define SET_INCONSISTENT(n) ht->inconsistent = n;
74 #else
75 #define IS_CONSISTENT(a)
76 #define SET_INCONSISTENT(n)
77 #endif
78
79 #define HASH_PROTECT_RECURSION(ht) \
80 if ((ht)->bApplyProtection) { \
81 if ((ht)->nApplyCount++ >= 3) { \
82 zend_error(E_ERROR, "Nesting level too deep - recursive dependency?"); \
83 } \
84 }
85
86
87 #define HASH_UNPROTECT_RECURSION(ht) \
88 if ((ht)->bApplyProtection) { \
89 (ht)->nApplyCount--; \
90 }
91
92
93 #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
94 if ((ht)->nNumOfElements > (ht)->nTableSize) { \
95 zend_hash_do_resize(ht); \
96 }
97
98 static int zend_hash_do_resize(HashTable *ht);
99
zend_hash_func(const char * arKey,uint nKeyLength)100 ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength)
101 {
102 return zend_inline_hash_func(arKey, nKeyLength);
103 }
104
105
106 #define UPDATE_DATA(ht, p, pData, nDataSize) \
107 if (nDataSize == sizeof(void*)) { \
108 if ((p)->pData != &(p)->pDataPtr) { \
109 pefree_rel((p)->pData, (ht)->persistent); \
110 } \
111 memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \
112 (p)->pData = &(p)->pDataPtr; \
113 } else { \
114 if ((p)->pData == &(p)->pDataPtr) { \
115 (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \
116 (p)->pDataPtr=NULL; \
117 } else { \
118 (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \
119 /* (p)->pDataPtr is already NULL so no need to initialize it */ \
120 } \
121 memcpy((p)->pData, pData, nDataSize); \
122 }
123
124 #define INIT_DATA(ht, p, pData, nDataSize); \
125 if (nDataSize == sizeof(void*)) { \
126 memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \
127 (p)->pData = &(p)->pDataPtr; \
128 } else { \
129 (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
130 if (!(p)->pData) { \
131 pefree_rel(p, (ht)->persistent); \
132 return FAILURE; \
133 } \
134 memcpy((p)->pData, pData, nDataSize); \
135 (p)->pDataPtr=NULL; \
136 }
137
138
139
_zend_hash_init(HashTable * ht,uint nSize,hash_func_t pHashFunction,dtor_func_t pDestructor,zend_bool persistent ZEND_FILE_LINE_DC)140 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)
141 {
142 uint i = 3;
143 Bucket **tmp;
144
145 SET_INCONSISTENT(HT_OK);
146
147 if (nSize >= 0x80000000) {
148 /* prevent overflow */
149 ht->nTableSize = 0x80000000;
150 } else {
151 while ((1U << i) < nSize) {
152 i++;
153 }
154 ht->nTableSize = 1 << i;
155 }
156
157 ht->nTableMask = ht->nTableSize - 1;
158 ht->pDestructor = pDestructor;
159 ht->arBuckets = NULL;
160 ht->pListHead = NULL;
161 ht->pListTail = NULL;
162 ht->nNumOfElements = 0;
163 ht->nNextFreeElement = 0;
164 ht->pInternalPointer = NULL;
165 ht->persistent = persistent;
166 ht->nApplyCount = 0;
167 ht->bApplyProtection = 1;
168
169 /* Uses ecalloc() so that Bucket* == NULL */
170 if (persistent) {
171 tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
172 if (!tmp) {
173 return FAILURE;
174 }
175 ht->arBuckets = tmp;
176 } else {
177 tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
178 if (tmp) {
179 ht->arBuckets = tmp;
180 }
181 }
182
183 return SUCCESS;
184 }
185
186
_zend_hash_init_ex(HashTable * ht,uint nSize,hash_func_t pHashFunction,dtor_func_t pDestructor,zend_bool persistent,zend_bool bApplyProtection ZEND_FILE_LINE_DC)187 ZEND_API int _zend_hash_init_ex(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection ZEND_FILE_LINE_DC)
188 {
189 int retval = _zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent ZEND_FILE_LINE_CC);
190
191 ht->bApplyProtection = bApplyProtection;
192 return retval;
193 }
194
195
zend_hash_set_apply_protection(HashTable * ht,zend_bool bApplyProtection)196 ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
197 {
198 ht->bApplyProtection = bApplyProtection;
199 }
200
201
202
_zend_hash_add_or_update(HashTable * ht,const char * arKey,uint nKeyLength,void * pData,uint nDataSize,void ** pDest,int flag ZEND_FILE_LINE_DC)203 ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
204 {
205 ulong h;
206 uint nIndex;
207 Bucket *p;
208
209 IS_CONSISTENT(ht);
210
211 if (nKeyLength <= 0) {
212 #if ZEND_DEBUG
213 ZEND_PUTS("zend_hash_update: Can't put in empty key\n");
214 #endif
215 return FAILURE;
216 }
217
218 h = zend_inline_hash_func(arKey, nKeyLength);
219 nIndex = h & ht->nTableMask;
220
221 p = ht->arBuckets[nIndex];
222 while (p != NULL) {
223 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
224 if (!memcmp(p->arKey, arKey, nKeyLength)) {
225 if (flag & HASH_ADD) {
226 return FAILURE;
227 }
228 HANDLE_BLOCK_INTERRUPTIONS();
229 #if ZEND_DEBUG
230 if (p->pData == pData) {
231 ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
232 HANDLE_UNBLOCK_INTERRUPTIONS();
233 return FAILURE;
234 }
235 #endif
236 if (ht->pDestructor) {
237 ht->pDestructor(p->pData);
238 }
239 UPDATE_DATA(ht, p, pData, nDataSize);
240 if (pDest) {
241 *pDest = p->pData;
242 }
243 HANDLE_UNBLOCK_INTERRUPTIONS();
244 return SUCCESS;
245 }
246 }
247 p = p->pNext;
248 }
249
250 p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
251 if (!p) {
252 return FAILURE;
253 }
254 memcpy(p->arKey, arKey, nKeyLength);
255 p->nKeyLength = nKeyLength;
256 INIT_DATA(ht, p, pData, nDataSize);
257 p->h = h;
258 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
259 if (pDest) {
260 *pDest = p->pData;
261 }
262
263 HANDLE_BLOCK_INTERRUPTIONS();
264 CONNECT_TO_GLOBAL_DLLIST(p, ht);
265 ht->arBuckets[nIndex] = p;
266 HANDLE_UNBLOCK_INTERRUPTIONS();
267
268 ht->nNumOfElements++;
269 ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
270 return SUCCESS;
271 }
272
_zend_hash_quick_add_or_update(HashTable * ht,const char * arKey,uint nKeyLength,ulong h,void * pData,uint nDataSize,void ** pDest,int flag ZEND_FILE_LINE_DC)273 ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
274 {
275 uint nIndex;
276 Bucket *p;
277
278 IS_CONSISTENT(ht);
279
280 if (nKeyLength == 0) {
281 return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
282 }
283
284 nIndex = h & ht->nTableMask;
285
286 p = ht->arBuckets[nIndex];
287 while (p != NULL) {
288 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
289 if (!memcmp(p->arKey, arKey, nKeyLength)) {
290 if (flag & HASH_ADD) {
291 return FAILURE;
292 }
293 HANDLE_BLOCK_INTERRUPTIONS();
294 #if ZEND_DEBUG
295 if (p->pData == pData) {
296 ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
297 HANDLE_UNBLOCK_INTERRUPTIONS();
298 return FAILURE;
299 }
300 #endif
301 if (ht->pDestructor) {
302 ht->pDestructor(p->pData);
303 }
304 UPDATE_DATA(ht, p, pData, nDataSize);
305 if (pDest) {
306 *pDest = p->pData;
307 }
308 HANDLE_UNBLOCK_INTERRUPTIONS();
309 return SUCCESS;
310 }
311 }
312 p = p->pNext;
313 }
314
315 p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
316 if (!p) {
317 return FAILURE;
318 }
319
320 memcpy(p->arKey, arKey, nKeyLength);
321 p->nKeyLength = nKeyLength;
322 INIT_DATA(ht, p, pData, nDataSize);
323 p->h = h;
324
325 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
326
327 if (pDest) {
328 *pDest = p->pData;
329 }
330
331 HANDLE_BLOCK_INTERRUPTIONS();
332 ht->arBuckets[nIndex] = p;
333 CONNECT_TO_GLOBAL_DLLIST(p, ht);
334 HANDLE_UNBLOCK_INTERRUPTIONS();
335
336 ht->nNumOfElements++;
337 ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
338 return SUCCESS;
339 }
340
341
zend_hash_add_empty_element(HashTable * ht,const char * arKey,uint nKeyLength)342 ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength)
343 {
344 void *dummy = (void *) 1;
345
346 return zend_hash_add(ht, arKey, nKeyLength, &dummy, sizeof(void *), NULL);
347 }
348
349
_zend_hash_index_update_or_next_insert(HashTable * ht,ulong h,void * pData,uint nDataSize,void ** pDest,int flag ZEND_FILE_LINE_DC)350 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)
351 {
352 uint nIndex;
353 Bucket *p;
354
355 IS_CONSISTENT(ht);
356
357 if (flag & HASH_NEXT_INSERT) {
358 h = ht->nNextFreeElement;
359 }
360 nIndex = h & ht->nTableMask;
361
362 p = ht->arBuckets[nIndex];
363 while (p != NULL) {
364 if ((p->nKeyLength == 0) && (p->h == h)) {
365 if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
366 return FAILURE;
367 }
368 HANDLE_BLOCK_INTERRUPTIONS();
369 #if ZEND_DEBUG
370 if (p->pData == pData) {
371 ZEND_PUTS("Fatal error in zend_hash_index_update: p->pData == pData\n");
372 HANDLE_UNBLOCK_INTERRUPTIONS();
373 return FAILURE;
374 }
375 #endif
376 if (ht->pDestructor) {
377 ht->pDestructor(p->pData);
378 }
379 UPDATE_DATA(ht, p, pData, nDataSize);
380 HANDLE_UNBLOCK_INTERRUPTIONS();
381 if ((long)h >= (long)ht->nNextFreeElement) {
382 ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
383 }
384 if (pDest) {
385 *pDest = p->pData;
386 }
387 return SUCCESS;
388 }
389 p = p->pNext;
390 }
391 p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
392 if (!p) {
393 return FAILURE;
394 }
395 p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */
396 p->h = h;
397 INIT_DATA(ht, p, pData, nDataSize);
398 if (pDest) {
399 *pDest = p->pData;
400 }
401
402 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
403
404 HANDLE_BLOCK_INTERRUPTIONS();
405 ht->arBuckets[nIndex] = p;
406 CONNECT_TO_GLOBAL_DLLIST(p, ht);
407 HANDLE_UNBLOCK_INTERRUPTIONS();
408
409 if ((long)h >= (long)ht->nNextFreeElement) {
410 ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX;
411 }
412 ht->nNumOfElements++;
413 ZEND_HASH_IF_FULL_DO_RESIZE(ht);
414 return SUCCESS;
415 }
416
417
zend_hash_do_resize(HashTable * ht)418 static int zend_hash_do_resize(HashTable *ht)
419 {
420 Bucket **t;
421
422 IS_CONSISTENT(ht);
423
424 if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */
425 t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
426 if (t) {
427 HANDLE_BLOCK_INTERRUPTIONS();
428 ht->arBuckets = t;
429 ht->nTableSize = (ht->nTableSize << 1);
430 ht->nTableMask = ht->nTableSize - 1;
431 zend_hash_rehash(ht);
432 HANDLE_UNBLOCK_INTERRUPTIONS();
433 return SUCCESS;
434 }
435 return FAILURE;
436 }
437 return SUCCESS;
438 }
439
zend_hash_rehash(HashTable * ht)440 ZEND_API int zend_hash_rehash(HashTable *ht)
441 {
442 Bucket *p;
443 uint nIndex;
444
445 IS_CONSISTENT(ht);
446
447 memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
448 p = ht->pListHead;
449 while (p != NULL) {
450 nIndex = p->h & ht->nTableMask;
451 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
452 ht->arBuckets[nIndex] = p;
453 p = p->pListNext;
454 }
455 return SUCCESS;
456 }
457
zend_hash_del_key_or_index(HashTable * ht,const char * arKey,uint nKeyLength,ulong h,int flag)458 ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
459 {
460 uint nIndex;
461 Bucket *p;
462
463 IS_CONSISTENT(ht);
464
465 if (flag == HASH_DEL_KEY) {
466 h = zend_inline_hash_func(arKey, nKeyLength);
467 }
468 nIndex = h & ht->nTableMask;
469
470 p = ht->arBuckets[nIndex];
471 while (p != NULL) {
472 if ((p->h == h)
473 && (p->nKeyLength == nKeyLength)
474 && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
475 || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
476 HANDLE_BLOCK_INTERRUPTIONS();
477 if (p == ht->arBuckets[nIndex]) {
478 ht->arBuckets[nIndex] = p->pNext;
479 } else {
480 p->pLast->pNext = p->pNext;
481 }
482 if (p->pNext) {
483 p->pNext->pLast = p->pLast;
484 }
485 if (p->pListLast != NULL) {
486 p->pListLast->pListNext = p->pListNext;
487 } else {
488 /* Deleting the head of the list */
489 ht->pListHead = p->pListNext;
490 }
491 if (p->pListNext != NULL) {
492 p->pListNext->pListLast = p->pListLast;
493 } else {
494 ht->pListTail = p->pListLast;
495 }
496 if (ht->pInternalPointer == p) {
497 ht->pInternalPointer = p->pListNext;
498 }
499 if (ht->pDestructor) {
500 ht->pDestructor(p->pData);
501 }
502 if (p->pData != &p->pDataPtr) {
503 pefree(p->pData, ht->persistent);
504 }
505 pefree(p, ht->persistent);
506 HANDLE_UNBLOCK_INTERRUPTIONS();
507 ht->nNumOfElements--;
508 return SUCCESS;
509 }
510 p = p->pNext;
511 }
512 return FAILURE;
513 }
514
515
zend_hash_destroy(HashTable * ht)516 ZEND_API void zend_hash_destroy(HashTable *ht)
517 {
518 Bucket *p, *q;
519
520 IS_CONSISTENT(ht);
521
522 SET_INCONSISTENT(HT_IS_DESTROYING);
523
524 p = ht->pListHead;
525 while (p != NULL) {
526 q = p;
527 p = p->pListNext;
528 if (ht->pDestructor) {
529 ht->pDestructor(q->pData);
530 }
531 if (q->pData != &q->pDataPtr) {
532 pefree(q->pData, ht->persistent);
533 }
534 pefree(q, ht->persistent);
535 }
536 pefree(ht->arBuckets, ht->persistent);
537
538 SET_INCONSISTENT(HT_DESTROYED);
539 }
540
541
zend_hash_clean(HashTable * ht)542 ZEND_API void zend_hash_clean(HashTable *ht)
543 {
544 Bucket *p, *q;
545
546 IS_CONSISTENT(ht);
547
548 p = ht->pListHead;
549
550 memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
551 ht->pListHead = NULL;
552 ht->pListTail = NULL;
553 ht->nNumOfElements = 0;
554 ht->nNextFreeElement = 0;
555 ht->pInternalPointer = NULL;
556
557 while (p != NULL) {
558 q = p;
559 p = p->pListNext;
560 if (ht->pDestructor) {
561 ht->pDestructor(q->pData);
562 }
563 if (q->pData != &q->pDataPtr) {
564 pefree(q->pData, ht->persistent);
565 }
566 pefree(q, ht->persistent);
567 }
568 }
569
570 /* This function is used by the various apply() functions.
571 * It deletes the passed bucket, and returns the address of the
572 * next bucket. The hash *may* be altered during that time, the
573 * returned value will still be valid.
574 */
zend_hash_apply_deleter(HashTable * ht,Bucket * p)575 static Bucket *zend_hash_apply_deleter(HashTable *ht, Bucket *p)
576 {
577 Bucket *retval;
578
579 HANDLE_BLOCK_INTERRUPTIONS();
580 if (p->pLast) {
581 p->pLast->pNext = p->pNext;
582 } else {
583 uint nIndex;
584
585 nIndex = p->h & ht->nTableMask;
586 ht->arBuckets[nIndex] = p->pNext;
587 }
588 if (p->pNext) {
589 p->pNext->pLast = p->pLast;
590 } else {
591 /* Nothing to do as this list doesn't have a tail */
592 }
593
594 if (p->pListLast != NULL) {
595 p->pListLast->pListNext = p->pListNext;
596 } else {
597 /* Deleting the head of the list */
598 ht->pListHead = p->pListNext;
599 }
600 if (p->pListNext != NULL) {
601 p->pListNext->pListLast = p->pListLast;
602 } else {
603 ht->pListTail = p->pListLast;
604 }
605 if (ht->pInternalPointer == p) {
606 ht->pInternalPointer = p->pListNext;
607 }
608 ht->nNumOfElements--;
609 HANDLE_UNBLOCK_INTERRUPTIONS();
610
611 if (ht->pDestructor) {
612 ht->pDestructor(p->pData);
613 }
614 if (p->pData != &p->pDataPtr) {
615 pefree(p->pData, ht->persistent);
616 }
617 retval = p->pListNext;
618 pefree(p, ht->persistent);
619
620 return retval;
621 }
622
623
zend_hash_graceful_destroy(HashTable * ht)624 ZEND_API void zend_hash_graceful_destroy(HashTable *ht)
625 {
626 Bucket *p;
627
628 IS_CONSISTENT(ht);
629
630 p = ht->pListHead;
631 while (p != NULL) {
632 p = zend_hash_apply_deleter(ht, p);
633 }
634 pefree(ht->arBuckets, ht->persistent);
635
636 SET_INCONSISTENT(HT_DESTROYED);
637 }
638
zend_hash_graceful_reverse_destroy(HashTable * ht)639 ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht)
640 {
641 Bucket *p;
642
643 IS_CONSISTENT(ht);
644
645 p = ht->pListTail;
646 while (p != NULL) {
647 zend_hash_apply_deleter(ht, p);
648 p = ht->pListTail;
649 }
650
651 pefree(ht->arBuckets, ht->persistent);
652
653 SET_INCONSISTENT(HT_DESTROYED);
654 }
655
656 /* This is used to recurse elements and selectively delete certain entries
657 * from a hashtable. apply_func() receives the data and decides if the entry
658 * should be deleted or recursion should be stopped. The following three
659 * return codes are possible:
660 * ZEND_HASH_APPLY_KEEP - continue
661 * ZEND_HASH_APPLY_STOP - stop iteration
662 * ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
663 */
664
zend_hash_apply(HashTable * ht,apply_func_t apply_func TSRMLS_DC)665 ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
666 {
667 Bucket *p;
668
669 IS_CONSISTENT(ht);
670
671 HASH_PROTECT_RECURSION(ht);
672 p = ht->pListHead;
673 while (p != NULL) {
674 int result = apply_func(p->pData TSRMLS_CC);
675
676 if (result & ZEND_HASH_APPLY_REMOVE) {
677 p = zend_hash_apply_deleter(ht, p);
678 } else {
679 p = p->pListNext;
680 }
681 if (result & ZEND_HASH_APPLY_STOP) {
682 break;
683 }
684 }
685 HASH_UNPROTECT_RECURSION(ht);
686 }
687
688
zend_hash_apply_with_argument(HashTable * ht,apply_func_arg_t apply_func,void * argument TSRMLS_DC)689 ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)
690 {
691 Bucket *p;
692
693 IS_CONSISTENT(ht);
694
695 HASH_PROTECT_RECURSION(ht);
696 p = ht->pListHead;
697 while (p != NULL) {
698 int result = apply_func(p->pData, argument TSRMLS_CC);
699
700 if (result & ZEND_HASH_APPLY_REMOVE) {
701 p = zend_hash_apply_deleter(ht, p);
702 } else {
703 p = p->pListNext;
704 }
705 if (result & ZEND_HASH_APPLY_STOP) {
706 break;
707 }
708 }
709 HASH_UNPROTECT_RECURSION(ht);
710 }
711
712
zend_hash_apply_with_arguments(HashTable * ht TSRMLS_DC,apply_func_args_t apply_func,int num_args,...)713 ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, ...)
714 {
715 Bucket *p;
716 va_list args;
717 zend_hash_key hash_key;
718
719 IS_CONSISTENT(ht);
720
721 HASH_PROTECT_RECURSION(ht);
722
723 p = ht->pListHead;
724 while (p != NULL) {
725 int result;
726 va_start(args, num_args);
727 hash_key.arKey = p->arKey;
728 hash_key.nKeyLength = p->nKeyLength;
729 hash_key.h = p->h;
730 result = apply_func(p->pData TSRMLS_CC, num_args, args, &hash_key);
731
732 if (result & ZEND_HASH_APPLY_REMOVE) {
733 p = zend_hash_apply_deleter(ht, p);
734 } else {
735 p = p->pListNext;
736 }
737 if (result & ZEND_HASH_APPLY_STOP) {
738 va_end(args);
739 break;
740 }
741 va_end(args);
742 }
743
744 HASH_UNPROTECT_RECURSION(ht);
745 }
746
747
zend_hash_reverse_apply(HashTable * ht,apply_func_t apply_func TSRMLS_DC)748 ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)
749 {
750 Bucket *p, *q;
751
752 IS_CONSISTENT(ht);
753
754 HASH_PROTECT_RECURSION(ht);
755 p = ht->pListTail;
756 while (p != NULL) {
757 int result = apply_func(p->pData TSRMLS_CC);
758
759 q = p;
760 p = p->pListLast;
761 if (result & ZEND_HASH_APPLY_REMOVE) {
762 zend_hash_apply_deleter(ht, q);
763 }
764 if (result & ZEND_HASH_APPLY_STOP) {
765 break;
766 }
767 }
768 HASH_UNPROTECT_RECURSION(ht);
769 }
770
771
zend_hash_copy(HashTable * target,HashTable * source,copy_ctor_func_t pCopyConstructor,void * tmp,uint size)772 ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)
773 {
774 Bucket *p;
775 void *new_entry;
776 zend_bool setTargetPointer;
777
778 IS_CONSISTENT(source);
779 IS_CONSISTENT(target);
780
781 setTargetPointer = !target->pInternalPointer;
782 p = source->pListHead;
783 while (p) {
784 if (setTargetPointer && source->pInternalPointer == p) {
785 target->pInternalPointer = NULL;
786 }
787 if (p->nKeyLength) {
788 zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry);
789 } else {
790 zend_hash_index_update(target, p->h, p->pData, size, &new_entry);
791 }
792 if (pCopyConstructor) {
793 pCopyConstructor(new_entry);
794 }
795 p = p->pListNext;
796 }
797 if (!target->pInternalPointer) {
798 target->pInternalPointer = target->pListHead;
799 }
800 }
801
802
_zend_hash_merge(HashTable * target,HashTable * source,copy_ctor_func_t pCopyConstructor,void * tmp,uint size,int overwrite ZEND_FILE_LINE_DC)803 ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite ZEND_FILE_LINE_DC)
804 {
805 Bucket *p;
806 void *t;
807 int mode = (overwrite?HASH_UPDATE:HASH_ADD);
808
809 IS_CONSISTENT(source);
810 IS_CONSISTENT(target);
811
812 p = source->pListHead;
813 while (p) {
814 if (p->nKeyLength>0) {
815 if (_zend_hash_quick_add_or_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t, mode ZEND_FILE_LINE_RELAY_CC)==SUCCESS && pCopyConstructor) {
816 pCopyConstructor(t);
817 }
818 } else {
819 if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h)) && zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
820 pCopyConstructor(t);
821 }
822 }
823 p = p->pListNext;
824 }
825 target->pInternalPointer = target->pListHead;
826 }
827
828
zend_hash_replace_checker_wrapper(HashTable * target,void * source_data,Bucket * p,void * pParam,merge_checker_func_t merge_checker_func)829 static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)
830 {
831 zend_hash_key hash_key;
832
833 hash_key.arKey = p->arKey;
834 hash_key.nKeyLength = p->nKeyLength;
835 hash_key.h = p->h;
836 return merge_checker_func(target, source_data, &hash_key, pParam);
837 }
838
839
zend_hash_merge_ex(HashTable * target,HashTable * source,copy_ctor_func_t pCopyConstructor,uint size,merge_checker_func_t pMergeSource,void * pParam)840 ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, merge_checker_func_t pMergeSource, void *pParam)
841 {
842 Bucket *p;
843 void *t;
844
845 IS_CONSISTENT(source);
846 IS_CONSISTENT(target);
847
848 p = source->pListHead;
849 while (p) {
850 if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) {
851 if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) {
852 pCopyConstructor(t);
853 }
854 }
855 p = p->pListNext;
856 }
857 target->pInternalPointer = target->pListHead;
858 }
859
860
zend_get_hash_value(const char * arKey,uint nKeyLength)861 ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength)
862 {
863 return zend_inline_hash_func(arKey, nKeyLength);
864 }
865
866
867 /* Returns SUCCESS if found and FAILURE if not. The pointer to the
868 * data is returned in pData. The reason is that there's no reason
869 * someone using the hash table might not want to have NULL data
870 */
zend_hash_find(const HashTable * ht,const char * arKey,uint nKeyLength,void ** pData)871 ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
872 {
873 ulong h;
874 uint nIndex;
875 Bucket *p;
876
877 IS_CONSISTENT(ht);
878
879 h = zend_inline_hash_func(arKey, nKeyLength);
880 nIndex = h & ht->nTableMask;
881
882 p = ht->arBuckets[nIndex];
883 while (p != NULL) {
884 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
885 if (!memcmp(p->arKey, arKey, nKeyLength)) {
886 *pData = p->pData;
887 return SUCCESS;
888 }
889 }
890 p = p->pNext;
891 }
892 return FAILURE;
893 }
894
895
zend_hash_quick_find(const HashTable * ht,const char * arKey,uint nKeyLength,ulong h,void ** pData)896 ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData)
897 {
898 uint nIndex;
899 Bucket *p;
900
901 if (nKeyLength==0) {
902 return zend_hash_index_find(ht, h, pData);
903 }
904
905 IS_CONSISTENT(ht);
906
907 nIndex = h & ht->nTableMask;
908
909 p = ht->arBuckets[nIndex];
910 while (p != NULL) {
911 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
912 if (!memcmp(p->arKey, arKey, nKeyLength)) {
913 *pData = p->pData;
914 return SUCCESS;
915 }
916 }
917 p = p->pNext;
918 }
919 return FAILURE;
920 }
921
922
zend_hash_exists(const HashTable * ht,const char * arKey,uint nKeyLength)923 ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)
924 {
925 ulong h;
926 uint nIndex;
927 Bucket *p;
928
929 IS_CONSISTENT(ht);
930
931 h = zend_inline_hash_func(arKey, nKeyLength);
932 nIndex = h & ht->nTableMask;
933
934 p = ht->arBuckets[nIndex];
935 while (p != NULL) {
936 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
937 if (!memcmp(p->arKey, arKey, nKeyLength)) {
938 return 1;
939 }
940 }
941 p = p->pNext;
942 }
943 return 0;
944 }
945
946
zend_hash_quick_exists(const HashTable * ht,const char * arKey,uint nKeyLength,ulong h)947 ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h)
948 {
949 uint nIndex;
950 Bucket *p;
951
952 if (nKeyLength==0) {
953 return zend_hash_index_exists(ht, h);
954 }
955
956 IS_CONSISTENT(ht);
957
958 nIndex = h & ht->nTableMask;
959
960 p = ht->arBuckets[nIndex];
961 while (p != NULL) {
962 if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
963 if (!memcmp(p->arKey, arKey, nKeyLength)) {
964 return 1;
965 }
966 }
967 p = p->pNext;
968 }
969 return 0;
970
971 }
972
973
zend_hash_index_find(const HashTable * ht,ulong h,void ** pData)974 ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
975 {
976 uint nIndex;
977 Bucket *p;
978
979 IS_CONSISTENT(ht);
980
981 nIndex = h & ht->nTableMask;
982
983 p = ht->arBuckets[nIndex];
984 while (p != NULL) {
985 if ((p->h == h) && (p->nKeyLength == 0)) {
986 *pData = p->pData;
987 return SUCCESS;
988 }
989 p = p->pNext;
990 }
991 return FAILURE;
992 }
993
994
zend_hash_index_exists(const HashTable * ht,ulong h)995 ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h)
996 {
997 uint nIndex;
998 Bucket *p;
999
1000 IS_CONSISTENT(ht);
1001
1002 nIndex = h & ht->nTableMask;
1003
1004 p = ht->arBuckets[nIndex];
1005 while (p != NULL) {
1006 if ((p->h == h) && (p->nKeyLength == 0)) {
1007 return 1;
1008 }
1009 p = p->pNext;
1010 }
1011 return 0;
1012 }
1013
1014
zend_hash_num_elements(const HashTable * ht)1015 ZEND_API int zend_hash_num_elements(const HashTable *ht)
1016 {
1017 IS_CONSISTENT(ht);
1018
1019 return ht->nNumOfElements;
1020 }
1021
1022
zend_hash_get_pointer(const HashTable * ht,HashPointer * ptr)1023 ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr)
1024 {
1025 ptr->pos = ht->pInternalPointer;
1026 if (ht->pInternalPointer) {
1027 ptr->h = ht->pInternalPointer->h;
1028 return 1;
1029 } else {
1030 ptr->h = 0;
1031 return 0;
1032 }
1033 }
1034
zend_hash_set_pointer(HashTable * ht,const HashPointer * ptr)1035 ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)
1036 {
1037 if (ptr->pos == NULL) {
1038 ht->pInternalPointer = NULL;
1039 } else if (ht->pInternalPointer != ptr->pos) {
1040 Bucket *p;
1041
1042 IS_CONSISTENT(ht);
1043 p = ht->arBuckets[ptr->h & ht->nTableMask];
1044 while (p != NULL) {
1045 if (p == ptr->pos) {
1046 ht->pInternalPointer = p;
1047 return 1;
1048 }
1049 p = p->pNext;
1050 }
1051 return 0;
1052 }
1053 return 1;
1054 }
1055
zend_hash_internal_pointer_reset_ex(HashTable * ht,HashPosition * pos)1056 ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)
1057 {
1058 IS_CONSISTENT(ht);
1059
1060 if (pos)
1061 *pos = ht->pListHead;
1062 else
1063 ht->pInternalPointer = ht->pListHead;
1064 }
1065
1066
1067 /* This function will be extremely optimized by remembering
1068 * the end of the list
1069 */
zend_hash_internal_pointer_end_ex(HashTable * ht,HashPosition * pos)1070 ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)
1071 {
1072 IS_CONSISTENT(ht);
1073
1074 if (pos)
1075 *pos = ht->pListTail;
1076 else
1077 ht->pInternalPointer = ht->pListTail;
1078 }
1079
1080
zend_hash_move_forward_ex(HashTable * ht,HashPosition * pos)1081 ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
1082 {
1083 HashPosition *current = pos ? pos : &ht->pInternalPointer;
1084
1085 IS_CONSISTENT(ht);
1086
1087 if (*current) {
1088 *current = (*current)->pListNext;
1089 return SUCCESS;
1090 } else
1091 return FAILURE;
1092 }
1093
zend_hash_move_backwards_ex(HashTable * ht,HashPosition * pos)1094 ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
1095 {
1096 HashPosition *current = pos ? pos : &ht->pInternalPointer;
1097
1098 IS_CONSISTENT(ht);
1099
1100 if (*current) {
1101 *current = (*current)->pListLast;
1102 return SUCCESS;
1103 } else
1104 return FAILURE;
1105 }
1106
1107
1108 /* This function should be made binary safe */
zend_hash_get_current_key_ex(const HashTable * ht,char ** str_index,uint * str_length,ulong * num_index,zend_bool duplicate,HashPosition * pos)1109 ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos)
1110 {
1111 Bucket *p;
1112
1113 p = pos ? (*pos) : ht->pInternalPointer;
1114
1115 IS_CONSISTENT(ht);
1116
1117 if (p) {
1118 if (p->nKeyLength) {
1119 if (duplicate) {
1120 *str_index = estrndup(p->arKey, p->nKeyLength - 1);
1121 } else {
1122 *str_index = p->arKey;
1123 }
1124 if (str_length) {
1125 *str_length = p->nKeyLength;
1126 }
1127 return HASH_KEY_IS_STRING;
1128 } else {
1129 *num_index = p->h;
1130 return HASH_KEY_IS_LONG;
1131 }
1132 }
1133 return HASH_KEY_NON_EXISTANT;
1134 }
1135
1136
zend_hash_get_current_key_type_ex(HashTable * ht,HashPosition * pos)1137 ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)
1138 {
1139 Bucket *p;
1140
1141 p = pos ? (*pos) : ht->pInternalPointer;
1142
1143 IS_CONSISTENT(ht);
1144
1145 if (p) {
1146 if (p->nKeyLength) {
1147 return HASH_KEY_IS_STRING;
1148 } else {
1149 return HASH_KEY_IS_LONG;
1150 }
1151 }
1152 return HASH_KEY_NON_EXISTANT;
1153 }
1154
1155
zend_hash_get_current_data_ex(HashTable * ht,void ** pData,HashPosition * pos)1156 ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos)
1157 {
1158 Bucket *p;
1159
1160 p = pos ? (*pos) : ht->pInternalPointer;
1161
1162 IS_CONSISTENT(ht);
1163
1164 if (p) {
1165 *pData = p->pData;
1166 return SUCCESS;
1167 } else {
1168 return FAILURE;
1169 }
1170 }
1171
1172 /* This function changes key of current element without changing elements'
1173 * order. If element with target key already exists, it will be deleted first.
1174 */
zend_hash_update_current_key_ex(HashTable * ht,int key_type,const char * str_index,uint str_length,ulong num_index,int mode,HashPosition * pos)1175 ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const char *str_index, uint str_length, ulong num_index, int mode, HashPosition *pos)
1176 {
1177 Bucket *p, *q;
1178
1179 p = pos ? (*pos) : ht->pInternalPointer;
1180
1181 IS_CONSISTENT(ht);
1182
1183 if (p) {
1184 if (key_type == HASH_KEY_IS_LONG) {
1185 str_length = 0;
1186 if (!p->nKeyLength && p->h == num_index) {
1187 return SUCCESS;
1188 }
1189
1190 q = ht->arBuckets[num_index & ht->nTableMask];
1191 while (q != NULL) {
1192 if (!q->nKeyLength && q->h == num_index) {
1193 break;
1194 }
1195 q = q->pNext;
1196 }
1197 } else if (key_type == HASH_KEY_IS_STRING) {
1198 ulong h;
1199
1200 if (p->nKeyLength == str_length &&
1201 memcmp(p->arKey, str_index, str_length) == 0) {
1202 return SUCCESS;
1203 }
1204
1205 h = zend_inline_hash_func(str_index, str_length);
1206 q = ht->arBuckets[h & ht->nTableMask];
1207
1208 while (q != NULL) {
1209 if (q->h == h && q->nKeyLength == str_length &&
1210 memcmp(q->arKey, str_index, str_length) == 0) {
1211 break;
1212 }
1213 q = q->pNext;
1214 }
1215 } else {
1216 return FAILURE;
1217 }
1218
1219 HANDLE_BLOCK_INTERRUPTIONS();
1220
1221 if (q) {
1222 if (mode != HASH_UPDATE_KEY_ANYWAY) {
1223 Bucket *r = p->pListLast;
1224 int found = HASH_UPDATE_KEY_IF_BEFORE;
1225
1226 while (r) {
1227 if (r == q) {
1228 found = HASH_UPDATE_KEY_IF_AFTER;
1229 break;
1230 }
1231 r = r->pListLast;
1232 }
1233 if (mode & found) {
1234 /* delete current bucket */
1235 if (p == ht->arBuckets[p->h & ht->nTableMask]) {
1236 ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
1237 } else {
1238 p->pLast->pNext = p->pNext;
1239 }
1240 if (p->pNext) {
1241 p->pNext->pLast = p->pLast;
1242 }
1243 if (p->pListLast != NULL) {
1244 p->pListLast->pListNext = p->pListNext;
1245 } else {
1246 /* Deleting the head of the list */
1247 ht->pListHead = p->pListNext;
1248 }
1249 if (p->pListNext != NULL) {
1250 p->pListNext->pListLast = p->pListLast;
1251 } else {
1252 ht->pListTail = p->pListLast;
1253 }
1254 if (ht->pInternalPointer == p) {
1255 ht->pInternalPointer = p->pListNext;
1256 }
1257 if (ht->pDestructor) {
1258 ht->pDestructor(p->pData);
1259 }
1260 if (p->pData != &p->pDataPtr) {
1261 pefree(p->pData, ht->persistent);
1262 }
1263 pefree(p, ht->persistent);
1264 ht->nNumOfElements--;
1265 HANDLE_UNBLOCK_INTERRUPTIONS();
1266 return FAILURE;
1267 }
1268 }
1269 /* delete another bucket with the same key */
1270 if (q == ht->arBuckets[q->h & ht->nTableMask]) {
1271 ht->arBuckets[q->h & ht->nTableMask] = q->pNext;
1272 } else {
1273 q->pLast->pNext = q->pNext;
1274 }
1275 if (q->pNext) {
1276 q->pNext->pLast = q->pLast;
1277 }
1278 if (q->pListLast != NULL) {
1279 q->pListLast->pListNext = q->pListNext;
1280 } else {
1281 /* Deleting the head of the list */
1282 ht->pListHead = q->pListNext;
1283 }
1284 if (q->pListNext != NULL) {
1285 q->pListNext->pListLast = q->pListLast;
1286 } else {
1287 ht->pListTail = q->pListLast;
1288 }
1289 if (ht->pInternalPointer == q) {
1290 ht->pInternalPointer = q->pListNext;
1291 }
1292 if (ht->pDestructor) {
1293 ht->pDestructor(q->pData);
1294 }
1295 if (q->pData != &q->pDataPtr) {
1296 pefree(q->pData, ht->persistent);
1297 }
1298 pefree(q, ht->persistent);
1299 ht->nNumOfElements--;
1300 }
1301
1302 if (p->pNext) {
1303 p->pNext->pLast = p->pLast;
1304 }
1305 if (p->pLast) {
1306 p->pLast->pNext = p->pNext;
1307 } else {
1308 ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
1309 }
1310
1311 if (p->nKeyLength != str_length) {
1312 Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) - 1 + str_length, ht->persistent);
1313
1314 q->nKeyLength = str_length;
1315 if (p->pData == &p->pDataPtr) {
1316 q->pData = &q->pDataPtr;
1317 } else {
1318 q->pData = p->pData;
1319 }
1320 q->pDataPtr = p->pDataPtr;
1321 q->pListNext = p->pListNext;
1322 q->pListLast = p->pListLast;
1323 if (q->pListNext) {
1324 p->pListNext->pListLast = q;
1325 } else {
1326 ht->pListTail = q;
1327 }
1328 if (q->pListLast) {
1329 p->pListLast->pListNext = q;
1330 } else {
1331 ht->pListHead = q;
1332 }
1333 if (ht->pInternalPointer == p) {
1334 ht->pInternalPointer = q;
1335 }
1336 if (pos) {
1337 *pos = q;
1338 }
1339 pefree(p, ht->persistent);
1340 p = q;
1341 }
1342
1343 if (key_type == HASH_KEY_IS_LONG) {
1344 p->h = num_index;
1345 } else {
1346 memcpy(p->arKey, str_index, str_length);
1347 p->h = zend_inline_hash_func(str_index, str_length);
1348 }
1349
1350 CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
1351 ht->arBuckets[p->h & ht->nTableMask] = p;
1352 HANDLE_UNBLOCK_INTERRUPTIONS();
1353
1354 return SUCCESS;
1355 } else {
1356 return FAILURE;
1357 }
1358 }
1359
zend_hash_sort(HashTable * ht,sort_func_t sort_func,compare_func_t compar,int renumber TSRMLS_DC)1360 ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
1361 compare_func_t compar, int renumber TSRMLS_DC)
1362 {
1363 Bucket **arTmp;
1364 Bucket *p;
1365 int i, j;
1366
1367 IS_CONSISTENT(ht);
1368
1369 if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
1370 return SUCCESS;
1371 }
1372 arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);
1373 if (!arTmp) {
1374 return FAILURE;
1375 }
1376 p = ht->pListHead;
1377 i = 0;
1378 while (p) {
1379 arTmp[i] = p;
1380 p = p->pListNext;
1381 i++;
1382 }
1383
1384 (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
1385
1386 HANDLE_BLOCK_INTERRUPTIONS();
1387 ht->pListHead = arTmp[0];
1388 ht->pListTail = NULL;
1389 ht->pInternalPointer = ht->pListHead;
1390
1391 arTmp[0]->pListLast = NULL;
1392 if (i > 1) {
1393 arTmp[0]->pListNext = arTmp[1];
1394 for (j = 1; j < i-1; j++) {
1395 arTmp[j]->pListLast = arTmp[j-1];
1396 arTmp[j]->pListNext = arTmp[j+1];
1397 }
1398 arTmp[j]->pListLast = arTmp[j-1];
1399 arTmp[j]->pListNext = NULL;
1400 } else {
1401 arTmp[0]->pListNext = NULL;
1402 }
1403 ht->pListTail = arTmp[i-1];
1404
1405 pefree(arTmp, ht->persistent);
1406 HANDLE_UNBLOCK_INTERRUPTIONS();
1407
1408 if (renumber) {
1409 p = ht->pListHead;
1410 i=0;
1411 while (p != NULL) {
1412 p->nKeyLength = 0;
1413 p->h = i++;
1414 p = p->pListNext;
1415 }
1416 ht->nNextFreeElement = i;
1417 zend_hash_rehash(ht);
1418 }
1419 return SUCCESS;
1420 }
1421
1422
zend_hash_compare(HashTable * ht1,HashTable * ht2,compare_func_t compar,zend_bool ordered TSRMLS_DC)1423 ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)
1424 {
1425 Bucket *p1, *p2 = NULL;
1426 int result;
1427 void *pData2;
1428
1429 IS_CONSISTENT(ht1);
1430 IS_CONSISTENT(ht2);
1431
1432 HASH_PROTECT_RECURSION(ht1);
1433 HASH_PROTECT_RECURSION(ht2);
1434
1435 result = ht1->nNumOfElements - ht2->nNumOfElements;
1436 if (result!=0) {
1437 HASH_UNPROTECT_RECURSION(ht1);
1438 HASH_UNPROTECT_RECURSION(ht2);
1439 return result;
1440 }
1441
1442 p1 = ht1->pListHead;
1443 if (ordered) {
1444 p2 = ht2->pListHead;
1445 }
1446
1447 while (p1) {
1448 if (ordered && !p2) {
1449 HASH_UNPROTECT_RECURSION(ht1);
1450 HASH_UNPROTECT_RECURSION(ht2);
1451 return 1; /* That's not supposed to happen */
1452 }
1453 if (ordered) {
1454 if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
1455 result = p1->h - p2->h;
1456 if (result!=0) {
1457 HASH_UNPROTECT_RECURSION(ht1);
1458 HASH_UNPROTECT_RECURSION(ht2);
1459 return result;
1460 }
1461 } else { /* string indices */
1462 result = p1->nKeyLength - p2->nKeyLength;
1463 if (result!=0) {
1464 HASH_UNPROTECT_RECURSION(ht1);
1465 HASH_UNPROTECT_RECURSION(ht2);
1466 return result;
1467 }
1468 result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
1469 if (result!=0) {
1470 HASH_UNPROTECT_RECURSION(ht1);
1471 HASH_UNPROTECT_RECURSION(ht2);
1472 return result;
1473 }
1474 }
1475 pData2 = p2->pData;
1476 } else {
1477 if (p1->nKeyLength==0) { /* numeric index */
1478 if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
1479 HASH_UNPROTECT_RECURSION(ht1);
1480 HASH_UNPROTECT_RECURSION(ht2);
1481 return 1;
1482 }
1483 } else { /* string index */
1484 if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) {
1485 HASH_UNPROTECT_RECURSION(ht1);
1486 HASH_UNPROTECT_RECURSION(ht2);
1487 return 1;
1488 }
1489 }
1490 }
1491 result = compar(p1->pData, pData2 TSRMLS_CC);
1492 if (result!=0) {
1493 HASH_UNPROTECT_RECURSION(ht1);
1494 HASH_UNPROTECT_RECURSION(ht2);
1495 return result;
1496 }
1497 p1 = p1->pListNext;
1498 if (ordered) {
1499 p2 = p2->pListNext;
1500 }
1501 }
1502
1503 HASH_UNPROTECT_RECURSION(ht1);
1504 HASH_UNPROTECT_RECURSION(ht2);
1505 return 0;
1506 }
1507
1508
zend_hash_minmax(const HashTable * ht,compare_func_t compar,int flag,void ** pData TSRMLS_DC)1509 ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
1510 {
1511 Bucket *p, *res;
1512
1513 IS_CONSISTENT(ht);
1514
1515 if (ht->nNumOfElements == 0 ) {
1516 *pData=NULL;
1517 return FAILURE;
1518 }
1519
1520 res = p = ht->pListHead;
1521 while ((p = p->pListNext)) {
1522 if (flag) {
1523 if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
1524 res = p;
1525 }
1526 } else {
1527 if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
1528 res = p;
1529 }
1530 }
1531 }
1532 *pData = res->pData;
1533 return SUCCESS;
1534 }
1535
zend_hash_next_free_element(const HashTable * ht)1536 ZEND_API ulong zend_hash_next_free_element(const HashTable *ht)
1537 {
1538 IS_CONSISTENT(ht);
1539
1540 return ht->nNextFreeElement;
1541
1542 }
1543
1544
1545 #if ZEND_DEBUG
zend_hash_display_pListTail(const HashTable * ht)1546 void zend_hash_display_pListTail(const HashTable *ht)
1547 {
1548 Bucket *p;
1549
1550 p = ht->pListTail;
1551 while (p != NULL) {
1552 zend_output_debug_string(0, "pListTail has key %s\n", p->arKey);
1553 p = p->pListLast;
1554 }
1555 }
1556
zend_hash_display(const HashTable * ht)1557 void zend_hash_display(const HashTable *ht)
1558 {
1559 Bucket *p;
1560 uint i;
1561
1562 for (i = 0; i < ht->nTableSize; i++) {
1563 p = ht->arBuckets[i];
1564 while (p != NULL) {
1565 zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1566 p = p->pNext;
1567 }
1568 }
1569
1570 p = ht->pListTail;
1571 while (p != NULL) {
1572 zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
1573 p = p->pListLast;
1574 }
1575 }
1576 #endif
1577
1578 /*
1579 * Local variables:
1580 * tab-width: 4
1581 * c-basic-offset: 4
1582 * indent-tabs-mode: t
1583 * End:
1584 */
1585
