Annotation of embedaddon/php/Zend/zend_hash.c, revision 1.1.1.4

1.1       misho       1: /*
                      2:    +----------------------------------------------------------------------+
                      3:    | Zend Engine                                                          |
                      4:    +----------------------------------------------------------------------+
1.1.1.4 ! misho       5:    | Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) |
1.1       misho       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: 
1.1.1.2   misho      20: /* $Id$ */
1.1       misho      21: 
                     22: #include "zend.h"
1.1.1.2   misho      23: #include "zend_globals.h"
1.1       misho      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: 
                     52: static 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: 
                     99: static int zend_hash_do_resize(HashTable *ht);
                    100: 
                    101: ZEND_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: 
1.1.1.2   misho     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:  
                    146: static const Bucket *uninitialized_bucket = NULL;
1.1       misho     147: 
                    148: ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
                    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: 
1.1.1.2   misho     164:        ht->nTableMask = 0;     /* 0 means that ht->arBuckets is uninitialized */
1.1       misho     165:        ht->pDestructor = pDestructor;
1.1.1.2   misho     166:        ht->arBuckets = (Bucket**)&uninitialized_bucket;
1.1       misho     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: 
                    179: ZEND_API int _zend_hash_init_ex(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection ZEND_FILE_LINE_DC)
                    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: 
                    188: ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)
                    189: {
                    190:        ht->bApplyProtection = bApplyProtection;
                    191: }
                    192: 
                    193: 
                    194: 
                    195: ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
                    196: {
                    197:        ulong h;
                    198:        uint nIndex;
                    199:        Bucket *p;
1.1.1.2   misho     200: #ifdef ZEND_SIGNALS
                    201:        TSRMLS_FETCH();
                    202: #endif
1.1       misho     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: 
1.1.1.2   misho     213:        CHECK_INIT(ht);
                    214: 
1.1       misho     215:        h = zend_inline_hash_func(arKey, nKeyLength);
                    216:        nIndex = h & ht->nTableMask;
                    217: 
                    218:        p = ht->arBuckets[nIndex];
                    219:        while (p != NULL) {
1.1.1.2   misho     220:                if (p->arKey == arKey ||
                    221:                        ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
1.1       misho     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:        
1.1.1.2   misho     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);
1.1       misho     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: 
                    278: ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
                    279: {
                    280:        uint nIndex;
                    281:        Bucket *p;
1.1.1.2   misho     282: #ifdef ZEND_SIGNALS
                    283:        TSRMLS_FETCH();
                    284: #endif
1.1       misho     285: 
                    286:        IS_CONSISTENT(ht);
                    287: 
                    288:        if (nKeyLength == 0) {
                    289:                return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
                    290:        }
                    291: 
1.1.1.2   misho     292:        CHECK_INIT(ht);
1.1       misho     293:        nIndex = h & ht->nTableMask;
                    294:        
                    295:        p = ht->arBuckets[nIndex];
                    296:        while (p != NULL) {
1.1.1.2   misho     297:                if (p->arKey == arKey ||
                    298:                        ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
1.1       misho     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:        
1.1.1.2   misho     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);
1.1       misho     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: 
                    359: ZEND_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: 
                    367: ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
                    368: {
                    369:        uint nIndex;
                    370:        Bucket *p;
1.1.1.2   misho     371: #ifdef ZEND_SIGNALS
                    372:        TSRMLS_FETCH();
                    373: #endif
1.1       misho     374: 
                    375:        IS_CONSISTENT(ht);
1.1.1.2   misho     376:        CHECK_INIT(ht);
1.1       misho     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:        }
1.1.1.2   misho     412:        p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent);
1.1       misho     413:        if (!p) {
                    414:                return FAILURE;
                    415:        }
1.1.1.2   misho     416:        p->arKey = NULL;
1.1       misho     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: 
                    440: static int zend_hash_do_resize(HashTable *ht)
                    441: {
                    442:        Bucket **t;
1.1.1.2   misho     443: #ifdef ZEND_SIGNALS
                    444:        TSRMLS_FETCH();
                    445: #endif
1.1       misho     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: 
                    465: ZEND_API int zend_hash_rehash(HashTable *ht)
                    466: {
                    467:        Bucket *p;
                    468:        uint nIndex;
                    469: 
                    470:        IS_CONSISTENT(ht);
1.1.1.2   misho     471:        if (UNEXPECTED(ht->nNumOfElements == 0)) {
                    472:                return SUCCESS;
                    473:        }
1.1       misho     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: 
                    486: ZEND_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;
1.1.1.2   misho     490: #ifdef ZEND_SIGNALS
                    491:        TSRMLS_FETCH();
                    492: #endif
1.1       misho     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: 
                    547: ZEND_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:        }
1.1.1.2   misho     567:        if (ht->nTableMask) {
                    568:                pefree(ht->arBuckets, ht->persistent);
                    569:        }
1.1       misho     570: 
                    571:        SET_INCONSISTENT(HT_DESTROYED);
                    572: }
                    573: 
                    574: 
                    575: ZEND_API void zend_hash_clean(HashTable *ht)
                    576: {
                    577:        Bucket *p, *q;
                    578: 
                    579:        IS_CONSISTENT(ht);
                    580: 
                    581:        p = ht->pListHead;
                    582: 
1.1.1.2   misho     583:        if (ht->nTableMask) {
                    584:                memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
                    585:        }
1.1       misho     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:  */
                    610: static Bucket *zend_hash_apply_deleter(HashTable *ht, Bucket *p)
                    611: {
                    612:        Bucket *retval;
1.1.1.2   misho     613: #ifdef ZEND_SIGNALS
                    614:        TSRMLS_FETCH();
                    615: #endif
1.1       misho     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: 
                    662: ZEND_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:        }
1.1.1.2   misho     672:        if (ht->nTableMask) {
                    673:                pefree(ht->arBuckets, ht->persistent);
                    674:        }
1.1       misho     675: 
                    676:        SET_INCONSISTENT(HT_DESTROYED);
                    677: }
                    678: 
                    679: ZEND_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: 
1.1.1.2   misho     691:        if (ht->nTableMask) {
                    692:                pefree(ht->arBuckets, ht->persistent);
                    693:        }
1.1       misho     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: 
                    707: ZEND_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: 
                    731: ZEND_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: 
                    755: ZEND_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: 
                    790: ZEND_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: 
                    814: ZEND_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: 
                    845: ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite ZEND_FILE_LINE_DC)
                    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: 
                    871: static 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: 
                    882: ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, merge_checker_func_t pMergeSource, void *pParam)
                    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: 
                    903: ZEND_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:  */
                    913: ZEND_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) {
1.1.1.2   misho     926:                if (p->arKey == arKey ||
                    927:                        ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
1.1       misho     928:                                *pData = p->pData;
                    929:                                return SUCCESS;
                    930:                }
                    931:                p = p->pNext;
                    932:        }
                    933:        return FAILURE;
                    934: }
                    935: 
                    936: 
                    937: ZEND_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) {
1.1.1.2   misho     952:                if (p->arKey == arKey ||
                    953:                        ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
1.1       misho     954:                                *pData = p->pData;
                    955:                                return SUCCESS;
                    956:                }
                    957:                p = p->pNext;
                    958:        }
                    959:        return FAILURE;
                    960: }
                    961: 
                    962: 
                    963: ZEND_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) {
1.1.1.2   misho     976:                if (p->arKey == arKey ||
                    977:                        ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
1.1       misho     978:                                return 1;
                    979:                }
                    980:                p = p->pNext;
                    981:        }
                    982:        return 0;
                    983: }
                    984: 
                    985: 
                    986: ZEND_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) {
1.1.1.2   misho    1001:                if (p->arKey == arKey ||
                   1002:                        ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
1.1       misho    1003:                                return 1;
                   1004:                }
                   1005:                p = p->pNext;
                   1006:        }
                   1007:        return 0;
                   1008: 
                   1009: }
                   1010: 
                   1011: 
                   1012: ZEND_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: 
                   1033: ZEND_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: 
                   1053: ZEND_API int zend_hash_num_elements(const HashTable *ht)
                   1054: {
                   1055:        IS_CONSISTENT(ht);
                   1056: 
                   1057:        return ht->nNumOfElements;
                   1058: }
                   1059: 
                   1060: 
                   1061: ZEND_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: 
                   1073: ZEND_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: 
                   1094: ZEND_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:  */
                   1108: ZEND_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: 
                   1119: ZEND_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: 
                   1132: ZEND_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  */
                   1147: ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos)
                   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 {
1.1.1.2   misho    1160:                                *str_index = (char*)p->arKey;
1.1       misho    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: 
                   1175: ZEND_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: 
                   1194: ZEND_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:  */
                   1213: ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const char *str_index, uint str_length, ulong num_index, int mode, HashPosition *pos)
                   1214: {
                   1215:        Bucket *p, *q;
1.1.1.2   misho    1216:        ulong h;
                   1217: #ifdef ZEND_SIGNALS
                   1218:        TSRMLS_FETCH();
                   1219: #endif
1.1       misho    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) {
1.1.1.2   misho    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:                        }
1.1       misho    1245: 
1.1.1.2   misho    1246:                        if (p->arKey == str_index ||
                   1247:                            (p->nKeyLength == str_length &&
                   1248:                             p->h == h &&
                   1249:                             memcmp(p->arKey, str_index, str_length) == 0)) {
1.1       misho    1250:                                return SUCCESS;
                   1251:                        }
                   1252: 
                   1253:                        q = ht->arBuckets[h & ht->nTableMask];
                   1254: 
                   1255:                        while (q != NULL) {
1.1.1.2   misho    1256:                                if (q->arKey == str_index ||
                   1257:                                    (q->h == h && q->nKeyLength == str_length &&
                   1258:                                     memcmp(q->arKey, str_index, str_length) == 0)) {
1.1       misho    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;
1.1.1.2   misho    1273: 
1.1       misho    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;
1.1.1.2   misho    1293:                                        } else {
1.1       misho    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;
1.1.1.2   misho    1328:                        } else {
1.1       misho    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: 
1.1.1.2   misho    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:                        }
1.1       misho    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 {
1.1.1.2   misho    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:                        }
1.1       misho    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: 
                   1421: ZEND_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: 
                   1484: ZEND_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: 
                   1570: ZEND_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: 
                   1597: ZEND_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
                   1607: void 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: 
                   1618: void zend_hash_display(const HashTable *ht)
                   1619: {
                   1620:        Bucket *p;
                   1621:        uint i;
                   1622: 
1.1.1.2   misho    1623:        if (UNEXPECTED(ht->nNumOfElements == 0)) {
                   1624:                zend_output_debug_string(0, "The hash is empty");
                   1625:                return;
                   1626:        }
1.1       misho    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:  */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>