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