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
51static 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
98static int zend_hash_do_resize(HashTable *ht);
99
100ZEND_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
140ZEND_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
187ZEND_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
196ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
197{
198    ht->bApplyProtection = bApplyProtection;
199}
200
201
202
203ZEND_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
273ZEND_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
342ZEND_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
350ZEND_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
418static 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
440ZEND_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
458ZEND_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
516ZEND_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
542ZEND_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 */
575static 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
624ZEND_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
639ZEND_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
665ZEND_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
689ZEND_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
713ZEND_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
748ZEND_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
772ZEND_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
803ZEND_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
829static 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
840ZEND_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
861ZEND_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 */
871ZEND_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
896ZEND_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
923ZEND_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
947ZEND_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
974ZEND_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
995ZEND_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
1015ZEND_API int zend_hash_num_elements(const HashTable *ht)
1016{
1017    IS_CONSISTENT(ht);
1018
1019    return ht->nNumOfElements;
1020}
1021
1022
1023ZEND_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
1035ZEND_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
1056ZEND_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 */
1070ZEND_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
1081ZEND_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
1094ZEND_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  */
1109ZEND_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
1137ZEND_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
1156ZEND_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 */
1175ZEND_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
1360ZEND_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
1423ZEND_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
1509ZEND_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
1536ZEND_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
1546void 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
1557void 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