diff options
Diffstat (limited to 'Zend/zend_hash.c')
| -rw-r--r-- | Zend/zend_hash.c | 1701 |
1 files changed, 890 insertions, 811 deletions
diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c index 829cd33641..901f6de43a 100644 --- a/Zend/zend_hash.c +++ b/Zend/zend_hash.c @@ -22,39 +22,21 @@ #include "zend.h" #include "zend_globals.h" -#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \ - (element)->pNext = (list_head); \ - (element)->pLast = NULL; \ - if ((element)->pNext) { \ - (element)->pNext->pLast = (element); \ - } - -#define CONNECT_TO_GLOBAL_DLLIST(element, ht) \ - (element)->pListLast = (ht)->pListTail; \ - (ht)->pListTail = (element); \ - (element)->pListNext = NULL; \ - if ((element)->pListLast != NULL) { \ - (element)->pListLast->pListNext = (element); \ - } \ - if (!(ht)->pListHead) { \ - (ht)->pListHead = (element); \ - } \ - if ((ht)->pInternalPointer == NULL) { \ - (ht)->pInternalPointer = (element); \ - } - #if ZEND_DEBUG -#define HT_OK 0 -#define HT_IS_DESTROYING 1 -#define HT_DESTROYED 2 -#define HT_CLEANING 3 +/* +#define HASH_MASK_CONSISTENCY 0x60 +*/ +#define HT_OK 0x00 +#define HT_IS_DESTROYING 0x20 +#define HT_DESTROYED 0x40 +#define HT_CLEANING 0x60 static void _zend_is_inconsistent(const HashTable *ht, const char *file, int line) { - if (ht->inconsistent==HT_OK) { + if ((ht->flags & HASH_MASK_CONSISTENCY) == HT_OK) { return; } - switch (ht->inconsistent) { + switch ((ht->flags & HASH_MASK_CONSISTENCY)) { case HT_IS_DESTROYING: zend_output_debug_string(1, "%s(%d) : ht=%p is being destroyed", file, line, ht); break; @@ -71,75 +53,47 @@ static void _zend_is_inconsistent(const HashTable *ht, const char *file, int lin zend_bailout(); } #define IS_CONSISTENT(a) _zend_is_inconsistent(a, __FILE__, __LINE__); -#define SET_INCONSISTENT(n) ht->inconsistent = n; +#define SET_INCONSISTENT(n) do { \ + (ht)->flags |= n; \ + } while (0) #else #define IS_CONSISTENT(a) #define SET_INCONSISTENT(n) #endif #define HASH_PROTECT_RECURSION(ht) \ - if ((ht)->bApplyProtection) { \ + if ((ht)->flags & HASH_FLAG_APPLY_PROTECTION) { \ if ((ht)->nApplyCount++ >= 3) { \ zend_error(E_ERROR, "Nesting level too deep - recursive dependency?"); \ } \ } - #define HASH_UNPROTECT_RECURSION(ht) \ - if ((ht)->bApplyProtection) { \ + if ((ht)->flags & HASH_FLAG_APPLY_PROTECTION) { \ (ht)->nApplyCount--; \ } - #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ - if ((ht)->nNumOfElements > (ht)->nTableSize) { \ + if ((ht)->nNumUsed >= (ht)->nTableSize) { \ zend_hash_do_resize(ht); \ } static void zend_hash_do_resize(HashTable *ht); -ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength) -{ - return zend_inline_hash_func(arKey, nKeyLength); -} - - -#define UPDATE_DATA(ht, p, pData, nDataSize) \ - if (nDataSize == sizeof(void*)) { \ - if ((p)->pData != &(p)->pDataPtr) { \ - pefree_rel((p)->pData, (ht)->persistent); \ - } \ - memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \ - (p)->pData = &(p)->pDataPtr; \ - } else { \ - if ((p)->pData == &(p)->pDataPtr) { \ - (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \ - (p)->pDataPtr=NULL; \ - } else { \ - (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \ - /* (p)->pDataPtr is already NULL so no need to initialize it */ \ - } \ - memcpy((p)->pData, pData, nDataSize); \ - } - -#define INIT_DATA(ht, p, pData, nDataSize); \ - if (nDataSize == sizeof(void*)) { \ - memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \ - (p)->pData = &(p)->pDataPtr; \ - } else { \ - (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\ - memcpy((p)->pData, pData, nDataSize); \ - (p)->pDataPtr=NULL; \ - } - -#define CHECK_INIT(ht) do { \ - if (UNEXPECTED((ht)->nTableMask == 0)) { \ - (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent); \ +#define CHECK_INIT(ht, packed) do { \ + if (UNEXPECTED((ht)->nTableMask == 0)) { \ + (ht)->arData = (Bucket *) pecalloc((ht)->nTableSize, sizeof(Bucket), (ht)->flags & HASH_FLAG_PERSISTENT); \ + if (packed) { \ + (ht)->flags |= HASH_FLAG_PACKED; \ + } else { \ + (ht)->arHash = (zend_uint*) pecalloc((ht)->nTableSize, sizeof(zend_uint), (ht)->flags & HASH_FLAG_PERSISTENT); \ + memset((ht)->arHash, INVALID_IDX, (ht)->nTableSize * sizeof(zend_uint)); \ + } \ (ht)->nTableMask = (ht)->nTableSize - 1; \ } \ } while (0) -static const Bucket *uninitialized_bucket = NULL; +static const zend_uint uninitialized_bucket = {INVALID_IDX}; ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { @@ -159,104 +113,136 @@ ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, dtor_func_t pDestructor, ht->nTableMask = 0; /* 0 means that ht->arBuckets is uninitialized */ ht->pDestructor = pDestructor; - ht->arBuckets = (Bucket**)&uninitialized_bucket; - ht->pListHead = NULL; - ht->pListTail = NULL; + ht->arData = NULL; + ht->arHash = (zend_uint*)&uninitialized_bucket; + ht->nNumUsed = 0; ht->nNumOfElements = 0; ht->nNextFreeElement = 0; - ht->pInternalPointer = NULL; - ht->persistent = persistent; + ht->nInternalPointer = INVALID_IDX; + ht->flags = HASH_FLAG_APPLY_PROTECTION; + if (persistent) { + ht->flags |= HASH_FLAG_PERSISTENT; + } ht->nApplyCount = 0; - ht->bApplyProtection = 1; return SUCCESS; } +static void zend_hash_packed_grow(HashTable *ht) +{ + HANDLE_BLOCK_INTERRUPTIONS(); + ht->arData = (Bucket *) perealloc(ht->arData, (ht->nTableSize << 1) * sizeof(Bucket), ht->flags & HASH_FLAG_PERSISTENT); + memset(ht->arData + ht->nTableSize, 0, sizeof(Bucket) * ht->nTableSize); + ht->nTableSize = (ht->nTableSize << 1); + ht->nTableMask = ht->nTableSize - 1; + HANDLE_UNBLOCK_INTERRUPTIONS(); +} + +ZEND_API void zend_hash_packed_to_hash(HashTable *ht) +{ + HANDLE_BLOCK_INTERRUPTIONS(); + ht->flags &= ~HASH_FLAG_PACKED; + ht->arHash = (zend_uint*) pecalloc(ht->nTableSize, sizeof(zend_uint), ht->flags & HASH_FLAG_PERSISTENT); + zend_hash_rehash(ht); + HANDLE_UNBLOCK_INTERRUPTIONS(); +} + +ZEND_API void zend_hash_to_packed(HashTable *ht) +{ + HANDLE_BLOCK_INTERRUPTIONS(); + ht->flags |= HASH_FLAG_PACKED; + pefree(ht->arHash, ht->flags & HASH_FLAG_PERSISTENT); + ht->arHash = (zend_uint*)&uninitialized_bucket; + HANDLE_UNBLOCK_INTERRUPTIONS(); +} ZEND_API int _zend_hash_init_ex(HashTable *ht, uint nSize, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection ZEND_FILE_LINE_DC) { int retval = _zend_hash_init(ht, nSize, pDestructor, persistent ZEND_FILE_LINE_CC); - ht->bApplyProtection = bApplyProtection; + if (!bApplyProtection) { + ht->flags &= ~HASH_FLAG_APPLY_PROTECTION; + } return retval; } ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection) { - ht->bApplyProtection = bApplyProtection; + if (bApplyProtection) { + ht->flags |= HASH_FLAG_APPLY_PROTECTION; + } else { + ht->flags &= ~HASH_FLAG_APPLY_PROTECTION; + } } - - -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) +static zend_always_inline Bucket *zend_hash_find_bucket(const HashTable *ht, zend_string *key) { ulong h; uint nIndex; + uint idx; Bucket *p; -#ifdef ZEND_SIGNALS - TSRMLS_FETCH(); -#endif - IS_CONSISTENT(ht); - - ZEND_ASSERT(nKeyLength != 0); + h = STR_HASH_VAL(key); + nIndex = h & ht->nTableMask; + idx = ht->arHash[nIndex]; + while (idx != INVALID_IDX) { + p = ht->arData + idx; + if ((p->key == key) || /* check for the the same interned string */ + (p->h == h && + p->key && + p->key->len == key->len && + memcmp(p->key->val, key->val, key->len) == 0)) { + return p; + } + idx = p->val.u.next; + } + return NULL; +} - CHECK_INIT(ht); +static zend_always_inline Bucket *zend_hash_str_find_bucket(const HashTable *ht, const char *str, int len, ulong h) +{ + uint nIndex; + uint idx; + Bucket *p; - h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if (p->arKey == arKey || - ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { - if (flag & HASH_ADD) { - return FAILURE; - } - ZEND_ASSERT(p->pData != pData); - HANDLE_BLOCK_INTERRUPTIONS(); - if (ht->pDestructor) { - ht->pDestructor(p->pData); - } - UPDATE_DATA(ht, p, pData, nDataSize); - if (pDest) { - *pDest = p->pData; - } - HANDLE_UNBLOCK_INTERRUPTIONS(); - return SUCCESS; + idx = ht->arHash[nIndex]; + while (idx != INVALID_IDX) { + p = ht->arData + idx; + if ((p->h == h) + && p->key + && (p->key->len == len) + && !memcmp(p->key->val, str, len)) { + return p; } - p = p->pNext; - } - - if (IS_INTERNED(arKey)) { - p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent); - p->arKey = arKey; - } else { - p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent); - p->arKey = (const char*)(p + 1); - memcpy((char*)p->arKey, arKey, nKeyLength); - } - p->nKeyLength = nKeyLength; - INIT_DATA(ht, p, pData, nDataSize); - p->h = h; - CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); - if (pDest) { - *pDest = p->pData; + idx = p->val.u.next; } + return NULL; +} - HANDLE_BLOCK_INTERRUPTIONS(); - CONNECT_TO_GLOBAL_DLLIST(p, ht); - ht->arBuckets[nIndex] = p; - HANDLE_UNBLOCK_INTERRUPTIONS(); +static zend_always_inline Bucket *zend_hash_index_find_bucket(const HashTable *ht, ulong h) +{ + uint nIndex; + uint idx; + Bucket *p; - ht->nNumOfElements++; - ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ - return SUCCESS; + nIndex = h & ht->nTableMask; + idx = ht->arHash[nIndex]; + while (idx != INVALID_IDX) { + p = ht->arData + idx; + if (p->h == h && !p->key) { + return p; + } + idx = p->val.u.next; + } + return NULL; } -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) +ZEND_API zval *_zend_hash_add_or_update(HashTable *ht, zend_string *key, zval *pData, int flag ZEND_FILE_LINE_DC) { + ulong h; uint nIndex; + uint idx; Bucket *p; #ifdef ZEND_SIGNALS TSRMLS_FETCH(); @@ -264,148 +250,199 @@ ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, const char *arKey, ui IS_CONSISTENT(ht); - ZEND_ASSERT(nKeyLength != 0); - - CHECK_INIT(ht); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if (p->arKey == arKey || - ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { - if (flag & HASH_ADD) { - return FAILURE; - } - ZEND_ASSERT(p->pData != pData); - HANDLE_BLOCK_INTERRUPTIONS(); - if (ht->pDestructor) { - ht->pDestructor(p->pData); - } - UPDATE_DATA(ht, p, pData, nDataSize); - if (pDest) { - *pDest = p->pData; - } - HANDLE_UNBLOCK_INTERRUPTIONS(); - return SUCCESS; - } - p = p->pNext; - } - - if (IS_INTERNED(arKey)) { - p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent); - p->arKey = arKey; - } else { - p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent); - p->arKey = (const char*)(p + 1); - memcpy((char*)p->arKey, arKey, nKeyLength); + CHECK_INIT(ht, 0); + if (ht->flags & HASH_FLAG_PACKED) { + zend_hash_packed_to_hash(ht); } - p->nKeyLength = nKeyLength; - INIT_DATA(ht, p, pData, nDataSize); - p->h = h; - - CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); + h = STR_HASH_VAL(key); + p = zend_hash_find_bucket(ht, key); - if (pDest) { - *pDest = p->pData; + if (p) { + if (flag & HASH_ADD) { + return NULL; + } + ZEND_ASSERT(&p->val != pData); + HANDLE_BLOCK_INTERRUPTIONS(); + if (ht->pDestructor) { + ht->pDestructor(&p->val); + } + p->val = *pData; + HANDLE_UNBLOCK_INTERRUPTIONS(); + return &p->val; } + + ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ HANDLE_BLOCK_INTERRUPTIONS(); - ht->arBuckets[nIndex] = p; - CONNECT_TO_GLOBAL_DLLIST(p, ht); + idx = ht->nNumUsed++; + ht->nNumOfElements++; + if (ht->nInternalPointer == INVALID_IDX) { + ht->nInternalPointer = idx; + } + p = ht->arData + idx; + p->h = h; + p->key = key; + STR_ADDREF(key); + p->val = *pData; + nIndex = h & ht->nTableMask; + p->val.u.next = ht->arHash[nIndex]; + ht->arHash[nIndex] = idx; HANDLE_UNBLOCK_INTERRUPTIONS(); - ht->nNumOfElements++; - ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ - return SUCCESS; + return &p->val; } +ZEND_API zval *_zend_hash_str_add_or_update(HashTable *ht, const char *str, int len, zval *pData, int flag ZEND_FILE_LINE_DC) +{ + zend_string *key = STR_INIT(str, len, ht->flags & HASH_FLAG_PERSISTENT); + zval *ret = _zend_hash_add_or_update(ht, key, pData, flag ZEND_FILE_LINE_CC); + STR_RELEASE(key); + return ret; +} -ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength) +ZEND_API zval *zend_hash_add_empty_element(HashTable *ht, zend_string *key) { - void *dummy = (void *) 1; + + zval dummy; - return zend_hash_add(ht, arKey, nKeyLength, &dummy, sizeof(void *), NULL); + ZVAL_NULL(&dummy); + return zend_hash_add(ht, key, &dummy); } +ZEND_API zval *zend_hash_str_add_empty_element(HashTable *ht, const char *str, int len) +{ + + zval dummy; + + ZVAL_NULL(&dummy); + return zend_hash_str_add(ht, str, len, &dummy); +} -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) +ZEND_API zval *_zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, zval *pData, int flag ZEND_FILE_LINE_DC) { uint nIndex; + uint idx; Bucket *p; #ifdef ZEND_SIGNALS TSRMLS_FETCH(); #endif IS_CONSISTENT(ht); - CHECK_INIT(ht); if (flag & HASH_NEXT_INSERT) { h = ht->nNextFreeElement; } - nIndex = h & ht->nTableMask; + CHECK_INIT(ht, h >= 0 && h < ht->nTableSize); - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if ((p->nKeyLength == 0) && (p->h == h)) { - if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) { - return FAILURE; + if (ht->flags & HASH_FLAG_PACKED) { + if (h >= 0 && h < ht->nTableSize) { + p = ht->arData + h; + if (Z_TYPE(p->val) != IS_UNDEF) { + if (ht->pDestructor) { + ht->pDestructor(&p->val); + } + p->val = *pData; + HANDLE_UNBLOCK_INTERRUPTIONS(); + if ((long)h >= (long)ht->nNextFreeElement) { + ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX; + } + return &p->val; + } + if (h >= ht->nNumUsed) { /* we have to keep the order :( */ + goto new_packed; + } else { + goto convert_to_hash; } - ZEND_ASSERT(p->pData != pData); + } else if (h >= ht->nNumUsed && /* we have to keep the order :( */ + h < ht->nTableSize * 2 && + ht->nTableSize - ht->nNumOfElements < ht->nTableSize / 2) { + zend_hash_packed_grow(ht); +new_packed: HANDLE_BLOCK_INTERRUPTIONS(); - if (ht->pDestructor) { - ht->pDestructor(p->pData); + if (h >= ht->nNumUsed) { + ht->nNumUsed = h + 1; + } + ht->nNumOfElements++; + if (ht->nInternalPointer == INVALID_IDX) { + ht->nInternalPointer = h; } - UPDATE_DATA(ht, p, pData, nDataSize); - HANDLE_UNBLOCK_INTERRUPTIONS(); if ((long)h >= (long)ht->nNextFreeElement) { ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX; } - if (pDest) { - *pDest = p->pData; - } - return SUCCESS; + p = ht->arData + h; + p->h = h; + p->key = NULL; + p->val = *pData; + p->val.u.next = INVALID_IDX; + + HANDLE_UNBLOCK_INTERRUPTIONS(); + + return &p->val; + } else { +convert_to_hash: + zend_hash_packed_to_hash(ht); } - p = p->pNext; } - p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent); - p->arKey = NULL; - p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */ - p->h = h; - INIT_DATA(ht, p, pData, nDataSize); - if (pDest) { - *pDest = p->pData; + + p = zend_hash_index_find_bucket(ht, h); + if (p) { + if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) { + return NULL; + } + ZEND_ASSERT(&p->val != pData); + HANDLE_BLOCK_INTERRUPTIONS(); + if (ht->pDestructor) { + ht->pDestructor(&p->val); + } + p->val = *pData; + HANDLE_UNBLOCK_INTERRUPTIONS(); + if ((long)h >= (long)ht->nNextFreeElement) { + ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX; + } + return &p->val; } - CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); + ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ HANDLE_BLOCK_INTERRUPTIONS(); - ht->arBuckets[nIndex] = p; - CONNECT_TO_GLOBAL_DLLIST(p, ht); - HANDLE_UNBLOCK_INTERRUPTIONS(); - + idx = ht->nNumUsed++; + ht->nNumOfElements++; + if (ht->nInternalPointer == INVALID_IDX) { + ht->nInternalPointer = idx; + } if ((long)h >= (long)ht->nNextFreeElement) { ht->nNextFreeElement = h < LONG_MAX ? h + 1 : LONG_MAX; } - ht->nNumOfElements++; - ZEND_HASH_IF_FULL_DO_RESIZE(ht); - return SUCCESS; + p = ht->arData + idx; + p->h = h; + p->key = NULL; + nIndex = h & ht->nTableMask; + p->val = *pData; + p->val.u.next = ht->arHash[nIndex]; + ht->arHash[nIndex] = idx; + HANDLE_UNBLOCK_INTERRUPTIONS(); + + return &p->val; } static void zend_hash_do_resize(HashTable *ht) { - Bucket **t; #ifdef ZEND_SIGNALS TSRMLS_FETCH(); #endif IS_CONSISTENT(ht); - if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */ - t = (Bucket **) perealloc(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent); + if (ht->nNumUsed < ht->nNumOfElements) { HANDLE_BLOCK_INTERRUPTIONS(); - ht->arBuckets = t; + zend_hash_rehash(ht); + HANDLE_UNBLOCK_INTERRUPTIONS(); + } else if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */ + HANDLE_BLOCK_INTERRUPTIONS(); + ht->arData = (Bucket *) perealloc(ht->arData, (ht->nTableSize << 1) * sizeof(Bucket), ht->flags & HASH_FLAG_PERSISTENT); + ht->arHash = (zend_uint *) perealloc(ht->arHash, (ht->nTableSize << 1) * sizeof(zend_uint), ht->flags & HASH_FLAG_PERSISTENT); ht->nTableSize = (ht->nTableSize << 1); ht->nTableMask = ht->nTableSize - 1; zend_hash_rehash(ht); @@ -416,107 +453,230 @@ static void zend_hash_do_resize(HashTable *ht) ZEND_API int zend_hash_rehash(HashTable *ht) { Bucket *p; - uint nIndex; + uint nIndex, i, j; IS_CONSISTENT(ht); + memset(ht->arHash, INVALID_IDX, ht->nTableSize * sizeof(zend_uint)); + if (UNEXPECTED(ht->nNumOfElements == 0)) { return SUCCESS; } - memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *)); - p = ht->pListHead; - while (p != NULL) { - nIndex = p->h & ht->nTableMask; - CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); - ht->arBuckets[nIndex] = p; - p = p->pListNext; + for (i = 0, j = 0; i < ht->nNumUsed; i++) { + p = ht->arData + i; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (i != j) { + ht->arData[j] = ht->arData[i]; + if (ht->nInternalPointer == i) { + ht->nInternalPointer = j; + } + } + nIndex = ht->arData[j].h & ht->nTableMask; + ht->arData[j].val.u.next = ht->arHash[nIndex]; + ht->arHash[nIndex] = j; + j++; } + ht->nNumUsed = j; return SUCCESS; } -ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag) +static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint idx, Bucket *p, Bucket *prev) +{ + if (!(ht->flags & HASH_FLAG_PACKED)) { + if (prev) { + prev->val.u.next = p->val.u.next; + } else { + ht->arHash[p->h & ht->nTableMask] = p->val.u.next; + } + } + if (ht->nNumUsed - 1 == idx) { + do { + ht->nNumUsed--; + } while (ht->nNumUsed > 0 && (Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)); + } + ht->nNumOfElements--; + if (ht->nInternalPointer == idx) { + while (1) { + idx++; + if (idx >= ht->nNumUsed) { + ht->nInternalPointer = INVALID_IDX; + break; + } else if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { + ht->nInternalPointer = idx; + break; + } + } + } + if (ht->pDestructor) { + ht->pDestructor(&p->val); + } +//??? if (ht->flags & HASH_FLAG_BIG_DATA) { +//??? pefree(p->xData, ht->flags & HASH_FLAG_PERSISTENT); +//??? } + if (p->key) { + STR_RELEASE(p->key); + } + Z_TYPE(p->val) = IS_UNDEF; +} + +static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint idx, Bucket *p) { uint nIndex; + Bucket *prev = NULL; + + if (!(ht->flags & HASH_FLAG_PACKED)) { + nIndex = p->h & ht->nTableMask; + idx = ht->arHash[nIndex]; + if (p != ht->arData + idx) { + prev = ht->arData + idx; + while (ht->arData + prev->val.u.next != p) { + idx = prev->val.u.next; + prev = ht->arData + idx; + } + idx = prev->val.u.next; + } + } + + _zend_hash_del_el_ex(ht, idx, p, prev); +} + +ZEND_API int zend_hash_del(HashTable *ht, zend_string *key) +{ + ulong h; + uint nIndex; + uint idx; Bucket *p; + Bucket *prev = NULL; #ifdef ZEND_SIGNALS TSRMLS_FETCH(); #endif IS_CONSISTENT(ht); - if (flag == HASH_DEL_KEY) { - h = zend_inline_hash_func(arKey, nKeyLength); + h = STR_HASH_VAL(key); + nIndex = h & ht->nTableMask; + + idx = ht->arHash[nIndex]; + while (idx != INVALID_IDX) { + p = ht->arData + idx; + if ((p->key == key) || + (p->h == h && + p->key && + p->key->len == key->len && + memcmp(p->key->val, key->val, key->len) == 0)) { + HANDLE_BLOCK_INTERRUPTIONS(); + _zend_hash_del_el_ex(ht, idx, p, prev); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return SUCCESS; + } + prev = p; + idx = p->val.u.next; } + return FAILURE; +} + +ZEND_API int zend_hash_str_del(HashTable *ht, const char *str, int len) +{ + ulong h; + uint nIndex; + uint idx; + Bucket *p; + Bucket *prev = NULL; +#ifdef ZEND_SIGNALS + TSRMLS_FETCH(); +#endif + + IS_CONSISTENT(ht); + + h = zend_inline_hash_func(str, len + 1); nIndex = h & ht->nTableMask; - p = ht->arBuckets[nIndex]; - while (p != NULL) { + idx = ht->arHash[nIndex]; + while (idx != INVALID_IDX) { + p = ht->arData + idx; if ((p->h == h) - && (p->nKeyLength == nKeyLength) - && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */ - || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */ + && p->key + && (p->key->len == len) + && !memcmp(p->key->val, str, len)) { HANDLE_BLOCK_INTERRUPTIONS(); - if (p == ht->arBuckets[nIndex]) { - ht->arBuckets[nIndex] = p->pNext; - } else { - p->pLast->pNext = p->pNext; - } - if (p->pNext) { - p->pNext->pLast = p->pLast; - } - if (p->pListLast != NULL) { - p->pListLast->pListNext = p->pListNext; - } else { - /* Deleting the head of the list */ - ht->pListHead = p->pListNext; - } - if (p->pListNext != NULL) { - p->pListNext->pListLast = p->pListLast; - } else { - ht->pListTail = p->pListLast; - } - if (ht->pInternalPointer == p) { - ht->pInternalPointer = p->pListNext; - } - ht->nNumOfElements--; - if (ht->pDestructor) { - ht->pDestructor(p->pData); - } - if (p->pData != &p->pDataPtr) { - pefree(p->pData, ht->persistent); - } - pefree(p, ht->persistent); + _zend_hash_del_el_ex(ht, idx, p, prev); HANDLE_UNBLOCK_INTERRUPTIONS(); return SUCCESS; } - p = p->pNext; + prev = p; + idx = p->val.u.next; } return FAILURE; } +ZEND_API int zend_hash_index_del(HashTable *ht, ulong h) +{ + uint nIndex; + uint idx; + Bucket *p; + Bucket *prev = NULL; +#ifdef ZEND_SIGNALS + TSRMLS_FETCH(); +#endif + + IS_CONSISTENT(ht); + + if (ht->flags & HASH_FLAG_PACKED) { + if (h >=0 && h < ht->nTableSize) { + p = ht->arData + h; + if (Z_TYPE(p->val) != IS_UNDEF) { + HANDLE_BLOCK_INTERRUPTIONS(); + _zend_hash_del_el_ex(ht, h, p, NULL); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return SUCCESS; + } + } + return FAILURE; + } + nIndex = h & ht->nTableMask; + + idx = ht->arHash[nIndex]; + while (idx != INVALID_IDX) { + p = ht->arData + idx; + if ((p->h == h) && (p->key == NULL)) { + HANDLE_BLOCK_INTERRUPTIONS(); + _zend_hash_del_el_ex(ht, idx, p, prev); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return SUCCESS; + } + prev = p; + idx = p->val.u.next; + } + return FAILURE; +} ZEND_API void zend_hash_destroy(HashTable *ht) { - Bucket *p, *q; + uint idx; + Bucket *p; IS_CONSISTENT(ht); SET_INCONSISTENT(HT_IS_DESTROYING); - p = ht->pListHead; - while (p != NULL) { - q = p; - p = p->pListNext; + for (idx = 0 ; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; if (ht->pDestructor) { - ht->pDestructor(q->pData); + ht->pDestructor(&p->val); } - if (q->pData != &q->pDataPtr) { - pefree(q->pData, ht->persistent); +//??? if (ht->flags & HASH_FLAG_BIG_DATA) { +//??? pefree(p->xData, ht->flags & HASH_FLAG_PERSISTENT); +//??? } + if (p->key) { + STR_RELEASE(p->key); } - pefree(q, ht->persistent); } if (ht->nTableMask) { - pefree(ht->arBuckets, ht->persistent); + pefree(ht->arData, ht->flags & HASH_FLAG_PERSISTENT); + if (!(ht->flags & HASH_FLAG_PACKED)) { + pefree(ht->arHash, ht->flags & HASH_FLAG_PERSISTENT); + } } SET_INCONSISTENT(HT_DESTROYED); @@ -525,31 +685,33 @@ ZEND_API void zend_hash_destroy(HashTable *ht) ZEND_API void zend_hash_clean(HashTable *ht) { - Bucket *p, *q; + uint idx; + Bucket *p; IS_CONSISTENT(ht); - p = ht->pListHead; - - if (ht->nTableMask) { - memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *)); + for (idx = 0; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (ht->pDestructor) { + ht->pDestructor(&p->val); + } +//??? if (ht->flags & HASH_FLAG_BIG_DATA) { +//??? pefree(p->xData, ht->flags & HASH_FLAG_PERSISTENT); +//??? } + if (p->key) { + STR_RELEASE(p->key); + } } - ht->pListHead = NULL; - ht->pListTail = NULL; + ht->nNumUsed = 0; ht->nNumOfElements = 0; ht->nNextFreeElement = 0; - ht->pInternalPointer = NULL; - - while (p != NULL) { - q = p; - p = p->pListNext; - if (ht->pDestructor) { - ht->pDestructor(q->pData); - } - if (q->pData != &q->pDataPtr) { - pefree(q->pData, ht->persistent); + ht->nInternalPointer = INVALID_IDX; + if (ht->nTableMask) { + memset(ht->arData, 0, ht->nTableSize*sizeof(Bucket)); + if (!(ht->flags & HASH_FLAG_PACKED)) { + memset(ht->arHash, INVALID_IDX, ht->nTableSize * sizeof(zend_uint)); } - pefree(q, ht->persistent); } } @@ -558,70 +720,35 @@ ZEND_API void zend_hash_clean(HashTable *ht) * next bucket. The hash *may* be altered during that time, the * returned value will still be valid. */ -static Bucket *zend_hash_apply_deleter(HashTable *ht, Bucket *p) +static void zend_hash_apply_deleter(HashTable *ht, uint idx, Bucket *p) { - Bucket *retval; #ifdef ZEND_SIGNALS TSRMLS_FETCH(); #endif HANDLE_BLOCK_INTERRUPTIONS(); - if (p->pLast) { - p->pLast->pNext = p->pNext; - } else { - uint nIndex; - - nIndex = p->h & ht->nTableMask; - ht->arBuckets[nIndex] = p->pNext; - } - if (p->pNext) { - p->pNext->pLast = p->pLast; - } else { - /* Nothing to do as this list doesn't have a tail */ - } - - if (p->pListLast != NULL) { - p->pListLast->pListNext = p->pListNext; - } else { - /* Deleting the head of the list */ - ht->pListHead = p->pListNext; - } - if (p->pListNext != NULL) { - p->pListNext->pListLast = p->pListLast; - } else { - ht->pListTail = p->pListLast; - } - if (ht->pInternalPointer == p) { - ht->pInternalPointer = p->pListNext; - } - ht->nNumOfElements--; + _zend_hash_del_el(ht, idx, p); HANDLE_UNBLOCK_INTERRUPTIONS(); - - if (ht->pDestructor) { - ht->pDestructor(p->pData); - } - if (p->pData != &p->pDataPtr) { - pefree(p->pData, ht->persistent); - } - retval = p->pListNext; - pefree(p, ht->persistent); - - return retval; } ZEND_API void zend_hash_graceful_destroy(HashTable *ht) { + uint idx; Bucket *p; IS_CONSISTENT(ht); - p = ht->pListHead; - while (p != NULL) { - p = zend_hash_apply_deleter(ht, p); + for (idx = 0; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + zend_hash_apply_deleter(ht, idx, p); } if (ht->nTableMask) { - pefree(ht->arBuckets, ht->persistent); + pefree(ht->arData, ht->flags & HASH_FLAG_PERSISTENT); + if (!(ht->flags & HASH_FLAG_PACKED)) { + pefree(ht->arHash, ht->flags & HASH_FLAG_PERSISTENT); + } } SET_INCONSISTENT(HT_DESTROYED); @@ -629,18 +756,24 @@ ZEND_API void zend_hash_graceful_destroy(HashTable *ht) ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht) { + uint idx; Bucket *p; IS_CONSISTENT(ht); - p = ht->pListTail; - while (p != NULL) { - zend_hash_apply_deleter(ht, p); - p = ht->pListTail; + idx = ht->nNumUsed; + while (idx > 0) { + idx--; + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + zend_hash_apply_deleter(ht, idx, p); } if (ht->nTableMask) { - pefree(ht->arBuckets, ht->persistent); + pefree(ht->arData, ht->flags & HASH_FLAG_PERSISTENT); + if (!(ht->flags & HASH_FLAG_PACKED)) { + pefree(ht->arHash, ht->flags & HASH_FLAG_PERSISTENT); + } } SET_INCONSISTENT(HT_DESTROYED); @@ -657,19 +790,21 @@ ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht) ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC) { + uint idx; Bucket *p; + int result; IS_CONSISTENT(ht); HASH_PROTECT_RECURSION(ht); - p = ht->pListHead; - while (p != NULL) { - int result = apply_func(p->pData TSRMLS_CC); + for (idx = 0; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + + result = apply_func(&p->val TSRMLS_CC); if (result & ZEND_HASH_APPLY_REMOVE) { - p = zend_hash_apply_deleter(ht, p); - } else { - p = p->pListNext; + zend_hash_apply_deleter(ht, idx, p); } if (result & ZEND_HASH_APPLY_STOP) { break; @@ -681,19 +816,21 @@ ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC) ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC) { + uint idx; Bucket *p; + int result; IS_CONSISTENT(ht); HASH_PROTECT_RECURSION(ht); - p = ht->pListHead; - while (p != NULL) { - int result = apply_func(p->pData, argument TSRMLS_CC); + for (idx = 0; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + + result = apply_func(&p->val, argument TSRMLS_CC); if (result & ZEND_HASH_APPLY_REMOVE) { - p = zend_hash_apply_deleter(ht, p); - } else { - p = p->pListNext; + zend_hash_apply_deleter(ht, idx, p); } if (result & ZEND_HASH_APPLY_STOP) { break; @@ -705,27 +842,27 @@ ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t appl ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, ...) { + uint idx; Bucket *p; va_list args; zend_hash_key hash_key; + int result; IS_CONSISTENT(ht); HASH_PROTECT_RECURSION(ht); - p = ht->pListHead; - while (p != NULL) { - int result; + for (idx = 0; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; va_start(args, num_args); - hash_key.arKey = p->arKey; - hash_key.nKeyLength = p->nKeyLength; hash_key.h = p->h; - result = apply_func(p->pData TSRMLS_CC, num_args, args, &hash_key); + hash_key.key = p->key; + + result = apply_func(&p->val TSRMLS_CC, num_args, args, &hash_key); if (result & ZEND_HASH_APPLY_REMOVE) { - p = zend_hash_apply_deleter(ht, p); - } else { - p = p->pListNext; + zend_hash_apply_deleter(ht, idx, p); } if (result & ZEND_HASH_APPLY_STOP) { va_end(args); @@ -740,19 +877,23 @@ ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC) { - Bucket *p, *q; + uint idx; + Bucket *p; + int result; IS_CONSISTENT(ht); HASH_PROTECT_RECURSION(ht); - p = ht->pListTail; - while (p != NULL) { - int result = apply_func(p->pData TSRMLS_CC); + idx = ht->nNumUsed; + while (idx > 0) { + idx--; + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + + result = apply_func(&p->val TSRMLS_CC); - q = p; - p = p->pListLast; if (result & ZEND_HASH_APPLY_REMOVE) { - zend_hash_apply_deleter(ht, q); + zend_hash_apply_deleter(ht, idx, p); } if (result & ZEND_HASH_APPLY_STOP) { break; @@ -762,92 +903,116 @@ ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSR } -ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size) +ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor) { + uint idx; Bucket *p; - void *new_entry; + zval *new_entry; zend_bool setTargetPointer; IS_CONSISTENT(source); IS_CONSISTENT(target); - setTargetPointer = !target->pInternalPointer; - p = source->pListHead; - while (p) { - if (setTargetPointer && source->pInternalPointer == p) { - target->pInternalPointer = NULL; + setTargetPointer = (target->nInternalPointer == INVALID_IDX); + for (idx = 0; idx < source->nNumUsed; idx++) { + p = source->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + + if (setTargetPointer && source->nInternalPointer == idx) { + target->nInternalPointer = INVALID_IDX; } - if (p->nKeyLength) { - zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry); + if (p->key) { + new_entry = zend_hash_update(target, p->key, &p->val); } else { - zend_hash_index_update(target, p->h, p->pData, size, &new_entry); + new_entry = zend_hash_index_update(target, p->h, &p->val); } if (pCopyConstructor) { pCopyConstructor(new_entry); } - p = p->pListNext; } - if (!target->pInternalPointer) { - target->pInternalPointer = target->pListHead; + if (target->nInternalPointer == INVALID_IDX && target->nNumOfElements > 0) { + idx = 0; + while (Z_TYPE(target->arData[idx].val) == IS_UNDEF) { + idx++; + } + target->nInternalPointer = idx; } } -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) +ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, int overwrite ZEND_FILE_LINE_DC) { + uint idx; Bucket *p; - void *t; + zval *t; int mode = (overwrite?HASH_UPDATE:HASH_ADD); IS_CONSISTENT(source); IS_CONSISTENT(target); - p = source->pListHead; - while (p) { - if (p->nKeyLength>0) { - 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) { + for (idx = 0; idx < source->nNumUsed; idx++) { + p = source->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (p->key) { + t = _zend_hash_add_or_update(target, p->key, &p->val, mode ZEND_FILE_LINE_RELAY_CC); + if (t && pCopyConstructor) { pCopyConstructor(t); } } else { - if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h)) && zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) { - pCopyConstructor(t); + if ((mode==HASH_UPDATE || !zend_hash_index_exists(target, p->h))) { + t = zend_hash_index_update(target, p->h, &p->val); + if (t && pCopyConstructor) { + pCopyConstructor(t); + } } } - p = p->pListNext; } - target->pInternalPointer = target->pListHead; + if (target->nNumOfElements > 0) { + idx = 0; + while (Z_TYPE(target->arData[idx].val) == IS_UNDEF) { + idx++; + } + target->nInternalPointer = idx; + } } -static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func) +static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, zval *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func) { zend_hash_key hash_key; - hash_key.arKey = p->arKey; - hash_key.nKeyLength = p->nKeyLength; hash_key.h = p->h; + hash_key.key = p->key; return merge_checker_func(target, source_data, &hash_key, pParam); } -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) +ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam) { + uint idx; Bucket *p; - void *t; + zval *t; IS_CONSISTENT(source); IS_CONSISTENT(target); - p = source->pListHead; - while (p) { - if (zend_hash_replace_checker_wrapper(target, p->pData, p, pParam, pMergeSource)) { - if (zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) { + for (idx = 0; idx < source->nNumUsed; idx++) { + p = source->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (zend_hash_replace_checker_wrapper(target, &p->val, p, pParam, pMergeSource)) { + t = zend_hash_update(target, p->key, &p->val); + if (t && pCopyConstructor) { pCopyConstructor(t); } } - p = p->pListNext; } - target->pInternalPointer = target->pListHead; + if (target->nNumOfElements > 0) { + idx = 0; + while (Z_TYPE(target->arData[idx].val) == IS_UNDEF) { + idx++; + } + target->nInternalPointer = idx; + } } @@ -855,139 +1020,104 @@ ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor * data is returned in pData. The reason is that there's no reason * someone using the hash table might not want to have NULL data */ -ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData) +ZEND_API zval *zend_hash_find(const HashTable *ht, zend_string *key) { - ulong h; - uint nIndex; Bucket *p; IS_CONSISTENT(ht); - h = zend_inline_hash_func(arKey, nKeyLength); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if (p->arKey == arKey || - ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { - *pData = p->pData; - return SUCCESS; - } - p = p->pNext; + if (ht->flags & HASH_FLAG_PACKED) { + return NULL; } - return FAILURE; -} + p = zend_hash_find_bucket(ht, key); + return p ? &p->val : NULL; +} -ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData) +ZEND_API zval *zend_hash_str_find(const HashTable *ht, const char *str, int len) { - uint nIndex; + ulong h; Bucket *p; - ZEND_ASSERT(nKeyLength != 0); - IS_CONSISTENT(ht); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if (p->arKey == arKey || - ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { - *pData = p->pData; - return SUCCESS; - } - p = p->pNext; + if (ht->flags & HASH_FLAG_PACKED) { + return NULL; } - return FAILURE; -} + h = zend_inline_hash_func(str, len + 1); + p = zend_hash_str_find_bucket(ht, str, len, h); + return p ? &p->val : NULL; +} -ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength) +ZEND_API int zend_hash_exists(const HashTable *ht, zend_string *key) { - ulong h; - uint nIndex; Bucket *p; IS_CONSISTENT(ht); - h = zend_inline_hash_func(arKey, nKeyLength); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if (p->arKey == arKey || - ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { - return 1; - } - p = p->pNext; + if (ht->flags & HASH_FLAG_PACKED) { + return 0; } - return 0; -} + p = zend_hash_find_bucket(ht, key); + return p ? 1 : 0; +} -ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h) +ZEND_API int zend_hash_str_exists(const HashTable *ht, const char *str, int len) { - uint nIndex; + ulong h; Bucket *p; - ZEND_ASSERT(nKeyLength != 0); - IS_CONSISTENT(ht); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if (p->arKey == arKey || - ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { - return 1; - } - p = p->pNext; + if (ht->flags & HASH_FLAG_PACKED) { + return 0; } - return 0; + h = zend_inline_hash_func(str, len + 1); + p = zend_hash_str_find_bucket(ht, str, len, h); + return p ? 1 : 0; } - -ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData) +ZEND_API zval *zend_hash_index_find(const HashTable *ht, ulong h) { - uint nIndex; Bucket *p; IS_CONSISTENT(ht); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if ((p->h == h) && (p->nKeyLength == 0)) { - *pData = p->pData; - return SUCCESS; + if (ht->flags & HASH_FLAG_PACKED) { + if (h >= 0 && h < ht->nTableSize) { + p = ht->arData + h; + if (Z_TYPE(p->val) != IS_UNDEF) { + return &p->val; + } } - p = p->pNext; + return NULL; } - return FAILURE; + + p = zend_hash_index_find_bucket(ht, h); + return p ? &p->val : NULL; } ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h) { - uint nIndex; Bucket *p; IS_CONSISTENT(ht); - nIndex = h & ht->nTableMask; - - p = ht->arBuckets[nIndex]; - while (p != NULL) { - if ((p->h == h) && (p->nKeyLength == 0)) { - return 1; + if (ht->flags & HASH_FLAG_PACKED) { + if (h >= 0 && h < ht->nTableSize) { + if (Z_TYPE(ht->arData[h].val) != IS_UNDEF) { + return 1; + } } - p = p->pNext; + return 0; } - return 0; + + p = zend_hash_index_find_bucket(ht, h); + return p ? 1 : 0; } @@ -1001,9 +1131,10 @@ ZEND_API int zend_hash_num_elements(const HashTable *ht) ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr) { - ptr->pos = ht->pInternalPointer; - if (ht->pInternalPointer) { - ptr->h = ht->pInternalPointer->h; + ptr->pos = ht->nInternalPointer; + ptr->ht = (HashTable*)ht; + if (ht->nInternalPointer != INVALID_IDX) { + ptr->h = ht->arData[ht->nInternalPointer].h; return 1; } else { ptr->h = 0; @@ -1013,19 +1144,36 @@ ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr) ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr) { - if (ptr->pos == NULL) { - ht->pInternalPointer = NULL; - } else if (ht->pInternalPointer != ptr->pos) { - Bucket *p; + uint idx; + if (ptr->pos == INVALID_IDX) { + ht->nInternalPointer = INVALID_IDX; + } else if (ptr->ht != ht) { IS_CONSISTENT(ht); - p = ht->arBuckets[ptr->h & ht->nTableMask]; - while (p != NULL) { - if (p == ptr->pos) { - ht->pInternalPointer = p; + for (idx = 0; idx < ht->nNumUsed; idx++) { + if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { + ht->nInternalPointer = idx; + return 0; + } + } + idx = INVALID_IDX; + return 0; + } else if (ht->nInternalPointer != ptr->pos) { + IS_CONSISTENT(ht); + if (ht->flags & HASH_FLAG_PACKED) { + if (Z_TYPE(ht->arData[ptr->h].val) != IS_UNDEF) { + ht->nInternalPointer = ptr->h; return 1; } - p = p->pNext; + } else { + idx = ht->arHash[ptr->h & ht->nTableMask]; + while (idx != INVALID_IDX) { + if (idx == ptr->pos) { + ht->nInternalPointer = idx; + return 1; + } + idx = ht->arData[idx].val.u.next; + } } return 0; } @@ -1034,12 +1182,25 @@ ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr) ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos) { + uint idx; + IS_CONSISTENT(ht); - if (pos) - *pos = ht->pListHead; - else - ht->pInternalPointer = ht->pListHead; + for (idx = 0; idx < ht->nNumUsed; idx++) { + if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { + if (pos) { + *pos = idx; + } else { + ht->nInternalPointer = idx; + } + return; + } + } + if (pos) { + *pos = INVALID_IDX; + } else { + ht->nInternalPointer = INVALID_IDX; + } } @@ -1048,60 +1209,94 @@ ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *p */ ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos) { + uint idx; + IS_CONSISTENT(ht); - if (pos) - *pos = ht->pListTail; - else - ht->pInternalPointer = ht->pListTail; + idx = ht->nNumUsed; + while (idx > 0) { + idx--; + if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { + if (pos) { + *pos = idx; + } else { + ht->nInternalPointer = idx; + } + return; + } + } + if (pos) { + *pos = INVALID_IDX; + } else { + ht->nInternalPointer = INVALID_IDX; + } } ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos) { - HashPosition *current = pos ? pos : &ht->pInternalPointer; + HashPosition *current = pos ? pos : &ht->nInternalPointer; + uint idx = *current; IS_CONSISTENT(ht); - if (*current) { - *current = (*current)->pListNext; - return SUCCESS; - } else - return FAILURE; + if (idx != INVALID_IDX) { + while (1) { + idx++; + if (idx >= ht->nNumUsed) { + *current = INVALID_IDX; + return SUCCESS; + } + if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { + *current = idx; + return SUCCESS; + } + } + } else { + return FAILURE; + } } ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos) { - HashPosition *current = pos ? pos : &ht->pInternalPointer; + HashPosition *current = pos ? pos : &ht->nInternalPointer; + uint idx = *current; IS_CONSISTENT(ht); - if (*current) { - *current = (*current)->pListLast; - return SUCCESS; - } else - return FAILURE; + if (idx != INVALID_IDX) { + while (idx > 0) { + idx--; + if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { + *current = idx; + return SUCCESS; + } + } + *current = INVALID_IDX; + return SUCCESS; + } else { + return FAILURE; + } } /* This function should be made binary safe */ -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) +ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, zend_string **str_index, ulong *num_index, zend_bool duplicate, HashPosition *pos) { + uint idx; Bucket *p; - p = pos ? (*pos) : ht->pInternalPointer; + idx = pos ? (*pos) : ht->nInternalPointer; IS_CONSISTENT(ht); - if (p) { - if (p->nKeyLength) { + if (idx != INVALID_IDX) { + p = ht->arData + idx; + if (p->key) { if (duplicate) { - *str_index = estrndup(p->arKey, p->nKeyLength - 1); + *str_index = STR_DUP(p->key, 0); } else { - *str_index = (char*)p->arKey; - } - if (str_length) { - *str_length = p->nKeyLength; + *str_index = p->key; } return HASH_KEY_IS_STRING; } else { @@ -1112,35 +1307,40 @@ ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, char **str_index, return HASH_KEY_NON_EXISTENT; } -ZEND_API void zend_hash_get_current_key_zval_ex(const HashTable *ht, zval *key, HashPosition *pos) { +ZEND_API void zend_hash_get_current_key_zval_ex(const HashTable *ht, zval *key, HashPosition *pos) +{ + uint idx; Bucket *p; IS_CONSISTENT(ht); - p = pos ? (*pos) : ht->pInternalPointer; + idx = pos ? (*pos) : ht->nInternalPointer; - if (!p) { + if (idx == INVALID_IDX) { Z_TYPE_P(key) = IS_NULL; - } else if (p->nKeyLength) { - Z_TYPE_P(key) = IS_STRING; - Z_STRVAL_P(key) = IS_INTERNED(p->arKey) ? (char*)p->arKey : estrndup(p->arKey, p->nKeyLength - 1); - Z_STRLEN_P(key) = p->nKeyLength - 1; } else { - Z_TYPE_P(key) = IS_LONG; - Z_LVAL_P(key) = p->h; + p = ht->arData + idx; + if (p->key) { + ZVAL_STR(key, p->key); + STR_ADDREF(p->key); + } else { + ZVAL_LONG(key, p->h); + } } } ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos) { + uint idx; Bucket *p; - p = pos ? (*pos) : ht->pInternalPointer; + idx = pos ? (*pos) : ht->nInternalPointer; IS_CONSISTENT(ht); - if (p) { - if (p->nKeyLength) { + if (idx != INVALID_IDX) { + p = ht->arData + idx; + if (p->key) { return HASH_KEY_IS_STRING; } else { return HASH_KEY_IS_LONG; @@ -1150,74 +1350,73 @@ ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos) } -ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos) +ZEND_API zval *zend_hash_get_current_data_ex(HashTable *ht, HashPosition *pos) { + uint idx; Bucket *p; - p = pos ? (*pos) : ht->pInternalPointer; + idx = pos ? (*pos) : ht->nInternalPointer; IS_CONSISTENT(ht); - if (p) { - *pData = p->pData; - return SUCCESS; + if (idx != INVALID_IDX) { + p = ht->arData + idx; + return &p->val; } else { - return FAILURE; + return NULL; } } /* This function changes key of current element without changing elements' * order. If element with target key already exists, it will be deleted first. */ -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) +ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, zend_string *str_index, ulong num_index, int mode, HashPosition *pos) { + uint idx1, idx2; Bucket *p, *q; ulong h; #ifdef ZEND_SIGNALS TSRMLS_FETCH(); #endif - p = pos ? (*pos) : ht->pInternalPointer; + idx1 = pos ? (*pos) : ht->nInternalPointer; IS_CONSISTENT(ht); - if (p) { + if (idx1 != INVALID_IDX) { + p = ht->arData + idx1; if (key_type == HASH_KEY_IS_LONG) { - str_length = 0; - if (!p->nKeyLength && p->h == num_index) { + if (p->h == num_index && p->key == NULL) { return SUCCESS; } - q = ht->arBuckets[num_index & ht->nTableMask]; - while (q != NULL) { - if (!q->nKeyLength && q->h == num_index) { + idx2 = ht->arHash[num_index & ht->nTableMask]; + while (idx2 != INVALID_IDX) { + q = ht->arData + idx2; + if (q->h == num_index && q->key == NULL) { break; } - q = q->pNext; + idx2 = q->val.u.next; } } else if (key_type == HASH_KEY_IS_STRING) { - if (IS_INTERNED(str_index)) { - h = INTERNED_HASH(str_index); - } else { - h = zend_inline_hash_func(str_index, str_length); - } - - if (p->arKey == str_index || - (p->nKeyLength == str_length && - p->h == h && - memcmp(p->arKey, str_index, str_length) == 0)) { + h = STR_HASH_VAL(str_index); + if (p->key == str_index || + (p->h == h && + p->key && + p->key->len == str_index->len && + memcmp(p->key->val, str_index->val, str_index->len) == 0)) { return SUCCESS; } - q = ht->arBuckets[h & ht->nTableMask]; - - while (q != NULL) { - if (q->arKey == str_index || - (q->h == h && q->nKeyLength == str_length && - memcmp(q->arKey, str_index, str_length) == 0)) { + idx2 = ht->arHash[h & ht->nTableMask]; + while (idx2 != INVALID_IDX) { + q = ht->arData + idx2; + if (q->key == str_index || + (q->h == h && q->key && q->key->len == str_index->len && + memcmp(q->key->val, str_index->val, str_index->len) == 0)) { break; } - q = q->pNext; + idx2 = q->val.u.next; } } else { return FAILURE; @@ -1225,150 +1424,49 @@ ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const HANDLE_BLOCK_INTERRUPTIONS(); - if (q) { + if (idx2 != INVALID_IDX) { + /* we have another bucket with the key equal to new one */ if (mode != HASH_UPDATE_KEY_ANYWAY) { - Bucket *r = p->pListLast; - int found = HASH_UPDATE_KEY_IF_BEFORE; - - while (r) { - if (r == q) { - found = HASH_UPDATE_KEY_IF_AFTER; - break; - } - r = r->pListLast; - } + int found = (idx1 < idx2) ? HASH_UPDATE_KEY_IF_BEFORE : HASH_UPDATE_KEY_IF_AFTER; + if (mode & found) { /* delete current bucket */ - if (p == ht->arBuckets[p->h & ht->nTableMask]) { - ht->arBuckets[p->h & ht->nTableMask] = p->pNext; - } else { - p->pLast->pNext = p->pNext; - } - if (p->pNext) { - p->pNext->pLast = p->pLast; - } - if (p->pListLast != NULL) { - p->pListLast->pListNext = p->pListNext; - } else { - /* Deleting the head of the list */ - ht->pListHead = p->pListNext; - } - if (p->pListNext != NULL) { - p->pListNext->pListLast = p->pListLast; - } else { - ht->pListTail = p->pListLast; - } - if (ht->pInternalPointer == p) { - ht->pInternalPointer = p->pListNext; - } - ht->nNumOfElements--; - if (ht->pDestructor) { - ht->pDestructor(p->pData); - } - if (p->pData != &p->pDataPtr) { - pefree(p->pData, ht->persistent); - } - pefree(p, ht->persistent); + _zend_hash_del_el(ht, idx1, p); HANDLE_UNBLOCK_INTERRUPTIONS(); return FAILURE; } } /* delete another bucket with the same key */ - if (q == ht->arBuckets[q->h & ht->nTableMask]) { - ht->arBuckets[q->h & ht->nTableMask] = q->pNext; - } else { - q->pLast->pNext = q->pNext; - } - if (q->pNext) { - q->pNext->pLast = q->pLast; - } - if (q->pListLast != NULL) { - q->pListLast->pListNext = q->pListNext; - } else { - /* Deleting the head of the list */ - ht->pListHead = q->pListNext; - } - if (q->pListNext != NULL) { - q->pListNext->pListLast = q->pListLast; - } else { - ht->pListTail = q->pListLast; - } - if (ht->pInternalPointer == q) { - ht->pInternalPointer = q->pListNext; - } - ht->nNumOfElements--; - if (ht->pDestructor) { - ht->pDestructor(q->pData); - } - if (q->pData != &q->pDataPtr) { - pefree(q->pData, ht->persistent); - } - pefree(q, ht->persistent); - } - - if (p->pNext) { - p->pNext->pLast = p->pLast; - } - if (p->pLast) { - p->pLast->pNext = p->pNext; - } else { - ht->arBuckets[p->h & ht->nTableMask] = p->pNext; - } - - if ((IS_INTERNED(p->arKey) != IS_INTERNED(str_index)) || - (!IS_INTERNED(p->arKey) && p->nKeyLength != str_length)) { - Bucket *q; - - if (IS_INTERNED(str_index)) { - q = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent); - } else { - q = (Bucket *) pemalloc(sizeof(Bucket) + str_length, ht->persistent); - } - - q->nKeyLength = str_length; - if (p->pData == &p->pDataPtr) { - q->pData = &q->pDataPtr; - } else { - q->pData = p->pData; - } - q->pDataPtr = p->pDataPtr; - q->pListNext = p->pListNext; - q->pListLast = p->pListLast; - if (q->pListNext) { - p->pListNext->pListLast = q; - } else { - ht->pListTail = q; - } - if (q->pListLast) { - p->pListLast->pListNext = q; - } else { - ht->pListHead = q; - } - if (ht->pInternalPointer == p) { - ht->pInternalPointer = q; - } - if (pos) { - *pos = q; - } - pefree(p, ht->persistent); - p = q; + _zend_hash_del_el(ht, idx2, q); } + /* remove old key from hash */ + if (ht->arHash[p->h & ht->nTableMask] == idx1) { + ht->arHash[p->h & ht->nTableMask] = p->val.u.next; + } else { + uint idx3 = ht->arHash[p->h & ht->nTableMask]; + while (ht->arData[idx3].val.u.next != idx1) { + idx3 = ht->arData[idx3].val.u.next; + } + ht->arData[idx3].val.u.next = p->val.u.next; + } + + /* update key */ + if (p->key) { + STR_RELEASE(p->key); + } if (key_type == HASH_KEY_IS_LONG) { p->h = num_index; + p->key = NULL; } else { p->h = h; - p->nKeyLength = str_length; - if (IS_INTERNED(str_index)) { - p->arKey = str_index; - } else { - p->arKey = (const char*)(p+1); - memcpy((char*)p->arKey, str_index, str_length); - } + p->key = str_index; + STR_ADDREF(str_index); } - CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]); - ht->arBuckets[p->h & ht->nTableMask] = p; + /* insert new key into hash */ + p->val.u.next = ht->arHash[p->h & ht->nTableMask]; + ht->arHash[p->h & ht->nTableMask] = idx1; HANDLE_UNBLOCK_INTERRUPTIONS(); return SUCCESS; @@ -1380,7 +1478,6 @@ ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compar, int renumber TSRMLS_DC) { - Bucket **arTmp; Bucket *p; int i, j; @@ -1389,59 +1486,65 @@ ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */ return SUCCESS; } - arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent); - p = ht->pListHead; - i = 0; - while (p) { - arTmp[i] = p; - p = p->pListNext; - i++; - } - - (*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC); - HANDLE_BLOCK_INTERRUPTIONS(); - ht->pListHead = arTmp[0]; - ht->pListTail = NULL; - ht->pInternalPointer = ht->pListHead; - - arTmp[0]->pListLast = NULL; - if (i > 1) { - arTmp[0]->pListNext = arTmp[1]; - for (j = 1; j < i-1; j++) { - arTmp[j]->pListLast = arTmp[j-1]; - arTmp[j]->pListNext = arTmp[j+1]; - } - arTmp[j]->pListLast = arTmp[j-1]; - arTmp[j]->pListNext = NULL; + if (ht->nNumUsed == ht->nNumOfElements) { + i = ht->nNumUsed; } else { - arTmp[0]->pListNext = NULL; + for (j = 0, i = 0; j < ht->nNumUsed; j++) { + p = ht->arData + j; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (i != j) { + ht->arData[i] = *p; + } + i++; + } } - ht->pListTail = arTmp[i-1]; - pefree(arTmp, ht->persistent); - HANDLE_UNBLOCK_INTERRUPTIONS(); + (*sort_func)((void *) ht->arData, i, sizeof(Bucket), compar TSRMLS_CC); + + HANDLE_BLOCK_INTERRUPTIONS(); + ht->nNumUsed = i; + ht->nInternalPointer = 0; if (renumber) { - p = ht->pListHead; - i=0; - while (p != NULL) { - p->nKeyLength = 0; - p->h = i++; - p = p->pListNext; + for (j = 0; j < i; j++) { + p = ht->arData + j; + p->h = j; + if (p->key) { + STR_RELEASE(p->key); + p->key = NULL; + } } + } + if (renumber) { ht->nNextFreeElement = i; - zend_hash_rehash(ht); } + if (ht->flags & HASH_FLAG_PACKED) { + if (!renumber) { + zend_hash_packed_to_hash(ht); + } + } else { + if (renumber) { + ht->flags |= HASH_FLAG_PACKED; + pefree(ht->arHash, ht->flags & HASH_FLAG_PERSISTENT); + ht->arHash = (zend_uint*)&uninitialized_bucket; + } else { + zend_hash_rehash(ht); + } + } + + HANDLE_UNBLOCK_INTERRUPTIONS(); + return SUCCESS; } ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC) { + uint idx1, idx2; Bucket *p1, *p2 = NULL; int result; - void *pData2; + zval *pData2; IS_CONSISTENT(ht1); IS_CONSISTENT(ht2); @@ -1456,64 +1559,68 @@ ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t co return result; } - p1 = ht1->pListHead; - if (ordered) { - p2 = ht2->pListHead; - } + for (idx1 = 0, idx2 = 0; idx1 < ht1->nNumUsed; idx1++) { + p1 = ht1->arData + idx1; + if (Z_TYPE(p1->val) == IS_UNDEF) continue; - while (p1) { - if (ordered && !p2) { - HASH_UNPROTECT_RECURSION(ht1); - HASH_UNPROTECT_RECURSION(ht2); - return 1; /* That's not supposed to happen */ - } if (ordered) { - if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */ + while (1) { + p2 = ht2->arData + idx2; + if (idx2 == ht2->nNumUsed) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return 1; /* That's not supposed to happen */ + } + if (p2) break; + idx2++; + } + if (p1->key == NULL && p2->key == NULL) { /* numeric indices */ result = p1->h - p2->h; - if (result!=0) { + if (result != 0) { HASH_UNPROTECT_RECURSION(ht1); HASH_UNPROTECT_RECURSION(ht2); return result; } } else { /* string indices */ - result = p1->nKeyLength - p2->nKeyLength; - if (result!=0) { + result = (p1->key ? p1->key->len : 0) - (p2->key ? p2->key->len : 0); + if (result != 0) { HASH_UNPROTECT_RECURSION(ht1); HASH_UNPROTECT_RECURSION(ht2); return result; } - result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength); - if (result!=0) { + result = memcmp(p1->key->val, p2->key->val, p1->key->len); + if (result != 0) { HASH_UNPROTECT_RECURSION(ht1); HASH_UNPROTECT_RECURSION(ht2); return result; } } - pData2 = p2->pData; + pData2 = &p2->val; } else { - if (p1->nKeyLength==0) { /* numeric index */ - if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) { + if (p1->key == NULL) { /* numeric index */ + pData2 = zend_hash_index_find(ht2, p1->h); + if (pData2 == NULL) { HASH_UNPROTECT_RECURSION(ht1); HASH_UNPROTECT_RECURSION(ht2); return 1; } } else { /* string index */ - if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) { + pData2 = zend_hash_find(ht2, p1->key); + if (pData2 == NULL) { HASH_UNPROTECT_RECURSION(ht1); HASH_UNPROTECT_RECURSION(ht2); return 1; } } } - result = compar(p1->pData, pData2 TSRMLS_CC); - if (result!=0) { + result = compar(&p1->val, pData2 TSRMLS_CC); + if (result != 0) { HASH_UNPROTECT_RECURSION(ht1); HASH_UNPROTECT_RECURSION(ht2); return result; } - p1 = p1->pListNext; if (ordered) { - p2 = p2->pListNext; + idx2++; } } @@ -1523,31 +1630,41 @@ ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t co } -ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC) +ZEND_API zval *zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag TSRMLS_DC) { + uint idx; Bucket *p, *res; IS_CONSISTENT(ht); if (ht->nNumOfElements == 0 ) { - *pData=NULL; - return FAILURE; + return NULL; } - res = p = ht->pListHead; - while ((p = p->pListNext)) { + idx = 0; + while (1) { + if (idx == ht->nNumUsed) { + return NULL; + } + if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) break; + idx++; + } + res = ht->arData + idx; + for (; idx < ht->nNumUsed; idx++) { + p = ht->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (flag) { - if (compar(&res, &p TSRMLS_CC) < 0) { /* max */ + if (compar(res, p TSRMLS_CC) < 0) { /* max */ res = p; } } else { - if (compar(&res, &p TSRMLS_CC) > 0) { /* min */ + if (compar(res, p TSRMLS_CC) > 0) { /* min */ res = p; } } } - *pData = res->pData; - return SUCCESS; + return &res->val; } ZEND_API ulong zend_hash_next_free_element(const HashTable *ht) @@ -1558,44 +1675,6 @@ ZEND_API ulong zend_hash_next_free_element(const HashTable *ht) } - -#if ZEND_DEBUG -void zend_hash_display_pListTail(const HashTable *ht) -{ - Bucket *p; - - p = ht->pListTail; - while (p != NULL) { - zend_output_debug_string(0, "pListTail has key %s\n", p->arKey); - p = p->pListLast; - } -} - -void zend_hash_display(const HashTable *ht) -{ - Bucket *p; - uint i; - - if (UNEXPECTED(ht->nNumOfElements == 0)) { - zend_output_debug_string(0, "The hash is empty"); - return; - } - for (i = 0; i < ht->nTableSize; i++) { - p = ht->arBuckets[i]; - while (p != NULL) { - zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h); - p = p->pNext; - } - } - - p = ht->pListTail; - while (p != NULL) { - zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h); - p = p->pListLast; - } -} -#endif - /* * Local variables: * tab-width: 4 |