diff options
Diffstat (limited to 'Zend/zend_hash.c')
| -rw-r--r-- | Zend/zend_hash.c | 1649 |
1 files changed, 1649 insertions, 0 deletions
diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c new file mode 100644 index 0000000..0609d70 --- /dev/null +++ b/Zend/zend_hash.c @@ -0,0 +1,1649 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2013 Zend Technologies Ltd. (http://www.zend.com) | + +----------------------------------------------------------------------+ + | This source file is subject to version 2.00 of the Zend license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.zend.com/license/2_00.txt. | + | If you did not receive a copy of the Zend license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@zend.com so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Andi Gutmans <andi@zend.com> | + | Zeev Suraski <zeev@zend.com> | + +----------------------------------------------------------------------+ +*/ + +/* $Id$ */ + +#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 + +static void _zend_is_inconsistent(const HashTable *ht, const char *file, int line) +{ + if (ht->inconsistent==HT_OK) { + return; + } + switch (ht->inconsistent) { + case HT_IS_DESTROYING: + zend_output_debug_string(1, "%s(%d) : ht=%p is being destroyed", file, line, ht); + break; + case HT_DESTROYED: + zend_output_debug_string(1, "%s(%d) : ht=%p is already destroyed", file, line, ht); + break; + case HT_CLEANING: + zend_output_debug_string(1, "%s(%d) : ht=%p is being cleaned", file, line, ht); + break; + default: + zend_output_debug_string(1, "%s(%d) : ht=%p is inconsistent", file, line, ht); + break; + } + zend_bailout(); +} +#define IS_CONSISTENT(a) _zend_is_inconsistent(a, __FILE__, __LINE__); +#define SET_INCONSISTENT(n) ht->inconsistent = n; +#else +#define IS_CONSISTENT(a) +#define SET_INCONSISTENT(n) +#endif + +#define HASH_PROTECT_RECURSION(ht) \ + if ((ht)->bApplyProtection) { \ + if ((ht)->nApplyCount++ >= 3) { \ + zend_error(E_ERROR, "Nesting level too deep - recursive dependency?"); \ + } \ + } + + +#define HASH_UNPROTECT_RECURSION(ht) \ + if ((ht)->bApplyProtection) { \ + (ht)->nApplyCount--; \ + } + + +#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ + if ((ht)->nNumOfElements > (ht)->nTableSize) { \ + zend_hash_do_resize(ht); \ + } + +static int 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);\ + if (!(p)->pData) { \ + pefree_rel(p, (ht)->persistent); \ + return FAILURE; \ + } \ + 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); \ + (ht)->nTableMask = (ht)->nTableSize - 1; \ + } \ +} while (0) + +static const Bucket *uninitialized_bucket = NULL; + +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) +{ + uint i = 3; + + SET_INCONSISTENT(HT_OK); + + if (nSize >= 0x80000000) { + /* prevent overflow */ + ht->nTableSize = 0x80000000; + } else { + while ((1U << i) < nSize) { + i++; + } + ht->nTableSize = 1 << i; + } + + 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->nNumOfElements = 0; + ht->nNextFreeElement = 0; + ht->pInternalPointer = NULL; + ht->persistent = persistent; + ht->nApplyCount = 0; + ht->bApplyProtection = 1; + return SUCCESS; +} + + +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) +{ + int retval = _zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent ZEND_FILE_LINE_CC); + + ht->bApplyProtection = bApplyProtection; + return retval; +} + + +ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection) +{ + ht->bApplyProtection = bApplyProtection; +} + + + +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) +{ + ulong h; + uint nIndex; + Bucket *p; +#ifdef ZEND_SIGNALS + TSRMLS_FETCH(); +#endif + + IS_CONSISTENT(ht); + + if (nKeyLength <= 0) { +#if ZEND_DEBUG + ZEND_PUTS("zend_hash_update: Can't put in empty key\n"); +#endif + return FAILURE; + } + + CHECK_INIT(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))) { + if (flag & HASH_ADD) { + return FAILURE; + } + HANDLE_BLOCK_INTERRUPTIONS(); +#if ZEND_DEBUG + if (p->pData == pData) { + ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n"); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return FAILURE; + } +#endif + 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); + if (!p) { + return FAILURE; + } + p->arKey = arKey; + } else { + p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent); + if (!p) { + return FAILURE; + } + 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; + } + + HANDLE_BLOCK_INTERRUPTIONS(); + CONNECT_TO_GLOBAL_DLLIST(p, ht); + ht->arBuckets[nIndex] = p; + HANDLE_UNBLOCK_INTERRUPTIONS(); + + ht->nNumOfElements++; + ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ + return SUCCESS; +} + +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) +{ + uint nIndex; + Bucket *p; +#ifdef ZEND_SIGNALS + TSRMLS_FETCH(); +#endif + + IS_CONSISTENT(ht); + + if (nKeyLength == 0) { + return zend_hash_index_update(ht, h, pData, nDataSize, pDest); + } + + 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; + } + HANDLE_BLOCK_INTERRUPTIONS(); +#if ZEND_DEBUG + if (p->pData == pData) { + ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n"); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return FAILURE; + } +#endif + 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); + if (!p) { + return FAILURE; + } + p->arKey = arKey; + } else { + p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent); + if (!p) { + return FAILURE; + } + 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; + } + + HANDLE_BLOCK_INTERRUPTIONS(); + ht->arBuckets[nIndex] = p; + CONNECT_TO_GLOBAL_DLLIST(p, ht); + HANDLE_UNBLOCK_INTERRUPTIONS(); + + ht->nNumOfElements++; + ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */ + return SUCCESS; +} + + +ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength) +{ + void *dummy = (void *) 1; + + return zend_hash_add(ht, arKey, nKeyLength, &dummy, sizeof(void *), NULL); +} + + +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) +{ + uint nIndex; + 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; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->nKeyLength == 0) && (p->h == h)) { + if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) { + return FAILURE; + } + HANDLE_BLOCK_INTERRUPTIONS(); +#if ZEND_DEBUG + if (p->pData == pData) { + ZEND_PUTS("Fatal error in zend_hash_index_update: p->pData == pData\n"); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return FAILURE; + } +#endif + if (ht->pDestructor) { + ht->pDestructor(p->pData); + } + 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 = p->pNext; + } + p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent); + if (!p) { + return FAILURE; + } + 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; + } + + CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); + + HANDLE_BLOCK_INTERRUPTIONS(); + ht->arBuckets[nIndex] = p; + CONNECT_TO_GLOBAL_DLLIST(p, ht); + HANDLE_UNBLOCK_INTERRUPTIONS(); + + 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; +} + + +static int 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_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent); + if (t) { + HANDLE_BLOCK_INTERRUPTIONS(); + ht->arBuckets = t; + ht->nTableSize = (ht->nTableSize << 1); + ht->nTableMask = ht->nTableSize - 1; + zend_hash_rehash(ht); + HANDLE_UNBLOCK_INTERRUPTIONS(); + return SUCCESS; + } + return FAILURE; + } + return SUCCESS; +} + +ZEND_API int zend_hash_rehash(HashTable *ht) +{ + Bucket *p; + uint nIndex; + + IS_CONSISTENT(ht); + 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; + } + return SUCCESS; +} + +ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag) +{ + uint nIndex; + Bucket *p; +#ifdef ZEND_SIGNALS + TSRMLS_FETCH(); +#endif + + IS_CONSISTENT(ht); + + if (flag == HASH_DEL_KEY) { + h = zend_inline_hash_func(arKey, nKeyLength); + } + nIndex = h & ht->nTableMask; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) + && (p->nKeyLength == nKeyLength) + && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */ + || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */ + 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; + } + if (ht->pDestructor) { + ht->pDestructor(p->pData); + } + if (p->pData != &p->pDataPtr) { + pefree(p->pData, ht->persistent); + } + pefree(p, ht->persistent); + HANDLE_UNBLOCK_INTERRUPTIONS(); + ht->nNumOfElements--; + return SUCCESS; + } + p = p->pNext; + } + return FAILURE; +} + + +ZEND_API void zend_hash_destroy(HashTable *ht) +{ + Bucket *p, *q; + + IS_CONSISTENT(ht); + + SET_INCONSISTENT(HT_IS_DESTROYING); + + p = ht->pListHead; + 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); + } + pefree(q, ht->persistent); + } + if (ht->nTableMask) { + pefree(ht->arBuckets, ht->persistent); + } + + SET_INCONSISTENT(HT_DESTROYED); +} + + +ZEND_API void zend_hash_clean(HashTable *ht) +{ + Bucket *p, *q; + + IS_CONSISTENT(ht); + + p = ht->pListHead; + + if (ht->nTableMask) { + memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *)); + } + ht->pListHead = NULL; + ht->pListTail = NULL; + 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); + } + pefree(q, ht->persistent); + } +} + +/* This function is used by the various apply() functions. + * It deletes the passed bucket, and returns the address of the + * 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) +{ + 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--; + 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) +{ + Bucket *p; + + IS_CONSISTENT(ht); + + p = ht->pListHead; + while (p != NULL) { + p = zend_hash_apply_deleter(ht, p); + } + if (ht->nTableMask) { + pefree(ht->arBuckets, ht->persistent); + } + + SET_INCONSISTENT(HT_DESTROYED); +} + +ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht) +{ + Bucket *p; + + IS_CONSISTENT(ht); + + p = ht->pListTail; + while (p != NULL) { + zend_hash_apply_deleter(ht, p); + p = ht->pListTail; + } + + if (ht->nTableMask) { + pefree(ht->arBuckets, ht->persistent); + } + + SET_INCONSISTENT(HT_DESTROYED); +} + +/* This is used to recurse elements and selectively delete certain entries + * from a hashtable. apply_func() receives the data and decides if the entry + * should be deleted or recursion should be stopped. The following three + * return codes are possible: + * ZEND_HASH_APPLY_KEEP - continue + * ZEND_HASH_APPLY_STOP - stop iteration + * ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former + */ + +ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC) +{ + Bucket *p; + + IS_CONSISTENT(ht); + + HASH_PROTECT_RECURSION(ht); + p = ht->pListHead; + while (p != NULL) { + int result = apply_func(p->pData TSRMLS_CC); + + if (result & ZEND_HASH_APPLY_REMOVE) { + p = zend_hash_apply_deleter(ht, p); + } else { + p = p->pListNext; + } + if (result & ZEND_HASH_APPLY_STOP) { + break; + } + } + HASH_UNPROTECT_RECURSION(ht); +} + + +ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC) +{ + Bucket *p; + + IS_CONSISTENT(ht); + + HASH_PROTECT_RECURSION(ht); + p = ht->pListHead; + while (p != NULL) { + int result = apply_func(p->pData, argument TSRMLS_CC); + + if (result & ZEND_HASH_APPLY_REMOVE) { + p = zend_hash_apply_deleter(ht, p); + } else { + p = p->pListNext; + } + if (result & ZEND_HASH_APPLY_STOP) { + break; + } + } + HASH_UNPROTECT_RECURSION(ht); +} + + +ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, ...) +{ + Bucket *p; + va_list args; + zend_hash_key hash_key; + + IS_CONSISTENT(ht); + + HASH_PROTECT_RECURSION(ht); + + p = ht->pListHead; + while (p != NULL) { + int result; + 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); + + if (result & ZEND_HASH_APPLY_REMOVE) { + p = zend_hash_apply_deleter(ht, p); + } else { + p = p->pListNext; + } + if (result & ZEND_HASH_APPLY_STOP) { + va_end(args); + break; + } + va_end(args); + } + + HASH_UNPROTECT_RECURSION(ht); +} + + +ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC) +{ + Bucket *p, *q; + + IS_CONSISTENT(ht); + + HASH_PROTECT_RECURSION(ht); + p = ht->pListTail; + while (p != NULL) { + int result = apply_func(p->pData TSRMLS_CC); + + q = p; + p = p->pListLast; + if (result & ZEND_HASH_APPLY_REMOVE) { + zend_hash_apply_deleter(ht, q); + } + if (result & ZEND_HASH_APPLY_STOP) { + break; + } + } + HASH_UNPROTECT_RECURSION(ht); +} + + +ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size) +{ + Bucket *p; + void *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; + } + if (p->nKeyLength) { + zend_hash_quick_update(target, p->arKey, p->nKeyLength, p->h, p->pData, size, &new_entry); + } else { + zend_hash_index_update(target, p->h, p->pData, size, &new_entry); + } + if (pCopyConstructor) { + pCopyConstructor(new_entry); + } + p = p->pListNext; + } + if (!target->pInternalPointer) { + target->pInternalPointer = target->pListHead; + } +} + + +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) +{ + Bucket *p; + void *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) { + 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); + } + } + p = p->pListNext; + } + target->pInternalPointer = target->pListHead; +} + + +static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *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; + 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) +{ + Bucket *p; + void *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) { + pCopyConstructor(t); + } + } + p = p->pListNext; + } + target->pInternalPointer = target->pListHead; +} + + +ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength) +{ + return zend_inline_hash_func(arKey, nKeyLength); +} + + +/* Returns SUCCESS if found and FAILURE if not. The pointer to the + * 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) +{ + 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; + } + return FAILURE; +} + + +ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData) +{ + uint nIndex; + Bucket *p; + + if (nKeyLength==0) { + return zend_hash_index_find(ht, h, pData); + } + + 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; + } + return FAILURE; +} + + +ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength) +{ + 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; + } + return 0; +} + + +ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h) +{ + uint nIndex; + Bucket *p; + + if (nKeyLength==0) { + return zend_hash_index_exists(ht, h); + } + + 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; + } + return 0; + +} + + +ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData) +{ + 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; + } + p = p->pNext; + } + return FAILURE; +} + + +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; + } + p = p->pNext; + } + return 0; +} + + +ZEND_API int zend_hash_num_elements(const HashTable *ht) +{ + IS_CONSISTENT(ht); + + return ht->nNumOfElements; +} + + +ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr) +{ + ptr->pos = ht->pInternalPointer; + if (ht->pInternalPointer) { + ptr->h = ht->pInternalPointer->h; + return 1; + } else { + ptr->h = 0; + return 0; + } +} + +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; + + IS_CONSISTENT(ht); + p = ht->arBuckets[ptr->h & ht->nTableMask]; + while (p != NULL) { + if (p == ptr->pos) { + ht->pInternalPointer = p; + return 1; + } + p = p->pNext; + } + return 0; + } + return 1; +} + +ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos) +{ + IS_CONSISTENT(ht); + + if (pos) + *pos = ht->pListHead; + else + ht->pInternalPointer = ht->pListHead; +} + + +/* This function will be extremely optimized by remembering + * the end of the list + */ +ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos) +{ + IS_CONSISTENT(ht); + + if (pos) + *pos = ht->pListTail; + else + ht->pInternalPointer = ht->pListTail; +} + + +ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos) +{ + HashPosition *current = pos ? pos : &ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (*current) { + *current = (*current)->pListNext; + return SUCCESS; + } else + return FAILURE; +} + +ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos) +{ + HashPosition *current = pos ? pos : &ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (*current) { + *current = (*current)->pListLast; + 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) +{ + Bucket *p; + + p = pos ? (*pos) : ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (p) { + if (p->nKeyLength) { + if (duplicate) { + *str_index = estrndup(p->arKey, p->nKeyLength - 1); + } else { + *str_index = (char*)p->arKey; + } + if (str_length) { + *str_length = p->nKeyLength; + } + return HASH_KEY_IS_STRING; + } else { + *num_index = p->h; + return HASH_KEY_IS_LONG; + } + } + return HASH_KEY_NON_EXISTANT; +} + + +ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos) +{ + Bucket *p; + + p = pos ? (*pos) : ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (p) { + if (p->nKeyLength) { + return HASH_KEY_IS_STRING; + } else { + return HASH_KEY_IS_LONG; + } + } + return HASH_KEY_NON_EXISTANT; +} + + +ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos) +{ + Bucket *p; + + p = pos ? (*pos) : ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (p) { + *pData = p->pData; + return SUCCESS; + } else { + return FAILURE; + } +} + +/* 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) +{ + Bucket *p, *q; + ulong h; +#ifdef ZEND_SIGNALS + TSRMLS_FETCH(); +#endif + + p = pos ? (*pos) : ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (p) { + if (key_type == HASH_KEY_IS_LONG) { + str_length = 0; + if (!p->nKeyLength && p->h == num_index) { + return SUCCESS; + } + + q = ht->arBuckets[num_index & ht->nTableMask]; + while (q != NULL) { + if (!q->nKeyLength && q->h == num_index) { + break; + } + q = q->pNext; + } + } 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)) { + 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)) { + break; + } + q = q->pNext; + } + } else { + return FAILURE; + } + + HANDLE_BLOCK_INTERRUPTIONS(); + + if (q) { + 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; + } + 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; + } + if (ht->pDestructor) { + ht->pDestructor(p->pData); + } + if (p->pData != &p->pDataPtr) { + pefree(p->pData, ht->persistent); + } + pefree(p, ht->persistent); + ht->nNumOfElements--; + 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; + } + if (ht->pDestructor) { + ht->pDestructor(q->pData); + } + if (q->pData != &q->pDataPtr) { + pefree(q->pData, ht->persistent); + } + pefree(q, ht->persistent); + ht->nNumOfElements--; + } + + 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; + } + + if (key_type == HASH_KEY_IS_LONG) { + p->h = num_index; + } 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); + } + } + + CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]); + ht->arBuckets[p->h & ht->nTableMask] = p; + HANDLE_UNBLOCK_INTERRUPTIONS(); + + return SUCCESS; + } else { + return FAILURE; + } +} + +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; + + IS_CONSISTENT(ht); + + if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */ + return SUCCESS; + } + arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent); + if (!arTmp) { + return FAILURE; + } + 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; + } else { + arTmp[0]->pListNext = NULL; + } + ht->pListTail = arTmp[i-1]; + + pefree(arTmp, ht->persistent); + HANDLE_UNBLOCK_INTERRUPTIONS(); + + if (renumber) { + p = ht->pListHead; + i=0; + while (p != NULL) { + p->nKeyLength = 0; + p->h = i++; + p = p->pListNext; + } + ht->nNextFreeElement = i; + zend_hash_rehash(ht); + } + return SUCCESS; +} + + +ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC) +{ + Bucket *p1, *p2 = NULL; + int result; + void *pData2; + + IS_CONSISTENT(ht1); + IS_CONSISTENT(ht2); + + HASH_PROTECT_RECURSION(ht1); + HASH_PROTECT_RECURSION(ht2); + + result = ht1->nNumOfElements - ht2->nNumOfElements; + if (result!=0) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return result; + } + + p1 = ht1->pListHead; + if (ordered) { + p2 = ht2->pListHead; + } + + 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 */ + result = p1->h - p2->h; + if (result!=0) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return result; + } + } else { /* string indices */ + result = p1->nKeyLength - p2->nKeyLength; + if (result!=0) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return result; + } + result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength); + if (result!=0) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return result; + } + } + pData2 = p2->pData; + } else { + if (p1->nKeyLength==0) { /* numeric index */ + if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) { + 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) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return 1; + } + } + } + result = compar(p1->pData, pData2 TSRMLS_CC); + if (result!=0) { + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return result; + } + p1 = p1->pListNext; + if (ordered) { + p2 = p2->pListNext; + } + } + + HASH_UNPROTECT_RECURSION(ht1); + HASH_UNPROTECT_RECURSION(ht2); + return 0; +} + + +ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC) +{ + Bucket *p, *res; + + IS_CONSISTENT(ht); + + if (ht->nNumOfElements == 0 ) { + *pData=NULL; + return FAILURE; + } + + res = p = ht->pListHead; + while ((p = p->pListNext)) { + if (flag) { + if (compar(&res, &p TSRMLS_CC) < 0) { /* max */ + res = p; + } + } else { + if (compar(&res, &p TSRMLS_CC) > 0) { /* min */ + res = p; + } + } + } + *pData = res->pData; + return SUCCESS; +} + +ZEND_API ulong zend_hash_next_free_element(const HashTable *ht) +{ + IS_CONSISTENT(ht); + + return ht->nNextFreeElement; + +} + + +#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 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ |