diff options
Diffstat (limited to 'Zend/zend_hash.c')
| -rw-r--r-- | Zend/zend_hash.c | 1278 |
1 files changed, 1278 insertions, 0 deletions
diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c new file mode 100644 index 0000000000..4d258b7759 --- /dev/null +++ b/Zend/zend_hash.c @@ -0,0 +1,1278 @@ +/* + +----------------------------------------------------------------------+ + | Zend Engine | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2000 Zend Technologies Ltd. (http://www.zend.com) | + +----------------------------------------------------------------------+ + | This source file is subject to version 0.92 of the Zend license, | + | that is bundled with this package in the file LICENSE, and is | + | available at through the world-wide-web at | + | http://www.zend.com/license/0_92.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> | + +----------------------------------------------------------------------+ +*/ + + +#include "zend.h" + +#include <stdio.h> + +#ifdef HAVE_STDLIB_H +# include <stdlib.h> +#endif + +#ifdef HAVE_LIMITS_H +# include <limits.h> +#endif + +#define HANDLE_NUMERIC(key, length, func) { \ + register char *tmp=key; \ + \ + if ((*tmp>='0' && *tmp<='9')) do { /* possibly a numeric index */ \ + char *end=tmp+length-1; \ + ulong idx; \ + \ + if (*tmp++=='0' && length>2) { /* don't accept numbers with leading zeros */ \ + break; \ + } \ + while (tmp<end) { \ + if (!(*tmp>='0' && *tmp<='9')) { \ + break; \ + } \ + tmp++; \ + } \ + if (tmp==end && *tmp=='\0') { /* a numeric index */ \ + idx = strtol(key, NULL, 10); \ + if (idx!=LONG_MAX) { \ + return func; \ + } \ + } \ + } while(0); \ +} + + +#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(HashTable *ht, 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=0x%08x is being destroyed", file, line, ht); + break; + case HT_DESTROYED: + zend_output_debug_string(1, "%s(%d) : ht=0x%08x is already destroyed", file, line, ht); + break; + case HT_CLEANING: + zend_output_debug_string(1, "%s(%d) : ht=0x%08x is being cleaned", 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_APPLY_BEGIN(ht) \ + if ((ht)->bApplyProtection) { \ + if ((ht)->nApplyCount>=3) { \ + zend_error(E_WARNING, "Nesting level too deep - recursive dependency?"); \ + return; \ + } \ + (ht)->nApplyCount++; \ + } + +#define HASH_APPLY_END(ht) \ + (ht)->nApplyCount--; + + +/* Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */ +static uint PrimeNumbers[] = + {5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793, 2097397, 4194103, 8388857, 16777447, 33554201, 67108961, 134217487, 268435697, 536870683, 1073741621, 2147483399}; +static uint nNumPrimeNumbers = sizeof(PrimeNumbers) / sizeof(uint); + +#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 hashpjw(char *arKey, uint nKeyLength) +{ + ulong h = 0, g; + char *arEnd=arKey+nKeyLength; + + while (arKey < arEnd) { + h = (h << 4) + *arKey++; + if ((g = (h & 0xF0000000))) { + h = h ^ (g >> 24); + h = h ^ g; + } + } + return h; +} + + +#define UPDATE_DATA(ht, p, pData, nDataSize) \ + if (nDataSize == sizeof(void*)) { \ + if (!(p)->pDataPtr) { \ + pefree((p)->pData, (ht)->persistent); \ + } \ + (p)->pDataPtr = *(void **)pData; \ + (p)->pData = &(p)->pDataPtr; \ + } else { \ + if ((p)->pDataPtr) { \ + (p)->pData = (void *) pemalloc(nDataSize, (ht)->persistent); \ + (p)->pDataPtr=NULL; \ + } \ + memcpy((p)->pData, pData, nDataSize); \ + } + +#define INIT_DATA(ht, p, pData, nDataSize); \ + if (nDataSize == sizeof(void*)) { \ + (p)->pDataPtr = *(void **)pData; \ + (p)->pData = &(p)->pDataPtr; \ + } else { \ + (p)->pData = (void *) pemalloc(nDataSize, (ht)->persistent); \ + if (!(p)->pData) { \ + pefree(p, (ht)->persistent); \ + return FAILURE; \ + } \ + memcpy((p)->pData, pData, nDataSize); \ + (p)->pDataPtr=NULL; \ + } + + +ZEND_API int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, int persistent) +{ + uint i; + + SET_INCONSISTENT(HT_OK); + + for (i = 0; i < nNumPrimeNumbers; i++) { + if (nSize <= PrimeNumbers[i]) { + nSize = PrimeNumbers[i]; + ht->nHashSizeIndex = i; + break; + } + } + if (i == nNumPrimeNumbers) { /* This shouldn't really happen unless the ask for a ridiculous size */ + nSize = PrimeNumbers[i - 1]; + ht->nHashSizeIndex = i - 1; + } + + /* Uses ecalloc() so that Bucket* == NULL */ + ht->arBuckets = (Bucket **) pecalloc(nSize, sizeof(Bucket *), persistent); + + if (!ht->arBuckets) { + return FAILURE; + } + if (pHashFunction == NULL) { + ht->pHashFunction = hashpjw; + } else { + ht->pHashFunction = pHashFunction; + } + ht->pDestructor = pDestructor; + ht->nTableSize = nSize; + 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, int persistent, zend_bool bApplyProtection) +{ + int retval = zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent); + + 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, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag) +{ + ulong h; + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + if (nKeyLength <= 0) { +#if ZEND_DEBUG + ZEND_PUTS("zend_hash_update: Can't put in empty key\n"); +#endif + return FAILURE; + } + + HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_update_or_next_insert(ht, idx, pData, nDataSize, pDest, flag)); + + h = ht->pHashFunction(arKey, nKeyLength); + nIndex = h % ht->nTableSize; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) && (p->nKeyLength == nKeyLength)) { + if (!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; + } + + p = (Bucket *) pemalloc(sizeof(Bucket)-1+nKeyLength, ht->persistent); + if (!p) { + return FAILURE; + } + memcpy(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, char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag) +{ + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + if (nKeyLength <= 0) { +#if ZEND_DEBUG + ZEND_PUTS("zend_hash_update: Can't put in empty key\n"); +#endif + return FAILURE; + } + + nIndex = h % ht->nTableSize; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) && (p->nKeyLength == nKeyLength)) { + if (!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; + } + + p = (Bucket *) pemalloc(sizeof(Bucket)-1+nKeyLength, ht->persistent); + if (!p) { + return FAILURE; + } + + memcpy(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_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag) +{ + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + if (flag & HASH_NEXT_INSERT) { + h = ht->nNextFreeElement; + } + nIndex = 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; + } + 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 (h >= ht->nNextFreeElement) { + ht->nNextFreeElement = h + 1; + } + if (pDest) { + *pDest = p->pData; + } + return SUCCESS; + } + p = p->pNext; + } + p = (Bucket *) pemalloc(sizeof(Bucket)-1, ht->persistent); + if (!p) { + return FAILURE; + } + 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 (h >= ht->nNextFreeElement) { + ht->nNextFreeElement = h + 1; + } + ht->nNumOfElements++; + ZEND_HASH_IF_FULL_DO_RESIZE(ht); + return SUCCESS; +} + + +static int zend_hash_do_resize(HashTable *ht) +{ + Bucket **t; + + IS_CONSISTENT(ht); + + if ((ht->nHashSizeIndex < nNumPrimeNumbers - 1)) { /* Let's double the table size */ + t = (Bucket **) perealloc_recoverable(ht->arBuckets, PrimeNumbers[ht->nHashSizeIndex + 1] * sizeof(Bucket *), ht->persistent); + if (t) { + HANDLE_BLOCK_INTERRUPTIONS(); + ht->arBuckets = t; + ht->nTableSize = PrimeNumbers[ht->nHashSizeIndex + 1]; + ht->nHashSizeIndex++; + 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); + + memset(ht->arBuckets, 0, PrimeNumbers[ht->nHashSizeIndex] * sizeof(Bucket *)); + p = ht->pListHead; + while (p != NULL) { + nIndex = p->h % ht->nTableSize; + 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, char *arKey, uint nKeyLength, ulong h, int flag) +{ + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + if (flag == HASH_DEL_KEY) { + HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_del_key_or_index(ht, arKey, nKeyLength, idx, HASH_DEL_INDEX)); + h = ht->pHashFunction(arKey, nKeyLength); + } + nIndex = h % ht->nTableSize; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) && ((p->nKeyLength == 0) || /* Numeric index */ + ((p->nKeyLength == nKeyLength) && (!memcmp(p->arKey, arKey, nKeyLength))))) { + 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->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->pDataPtr && q->pData) { + pefree(q->pData, ht->persistent); + } + pefree(q, ht->persistent); + } + pefree(ht->arBuckets, ht->persistent); + + SET_INCONSISTENT(HT_DESTROYED); +} + + +ZEND_API void zend_hash_clean(HashTable *ht) +{ + Bucket *p, *q; + + IS_CONSISTENT(ht); + + SET_INCONSISTENT(HT_CLEANING); + + p = ht->pListHead; + while (p != NULL) { + q = p; + p = p->pListNext; + if (ht->pDestructor) { + ht->pDestructor(q->pData); + } + if (!q->pDataPtr && q->pData) { + pefree(q->pData, ht->persistent); + } + pefree(q, ht->persistent); + } + memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *)); + ht->pListHead = NULL; + ht->pListTail = NULL; + ht->nNumOfElements = 0; + ht->nNextFreeElement = 0; + ht->pInternalPointer = NULL; + + SET_INCONSISTENT(HT_OK); +} + +/* 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; + + HANDLE_BLOCK_INTERRUPTIONS(); + + if (ht->pDestructor) { + ht->pDestructor(p->pData); + } + if (!p->pDataPtr) { + pefree(p->pData, ht->persistent); + } + retval = p->pListNext; + + if (p->pLast) { + p->pLast->pNext = p->pNext; + } else { + uint nIndex; + + nIndex = p->h % ht->nTableSize; + 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; + } + pefree(p, ht->persistent); + HANDLE_UNBLOCK_INTERRUPTIONS(); + ht->nNumOfElements--; + + 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); + } + pefree(ht->arBuckets, ht->persistent); + + SET_INCONSISTENT(HT_DESTROYED); +} + +/* This is used to selectively delete certain entries from a hashtable. + * destruct() receives the data and decides if the entry should be deleted + * or not + */ + + +ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func) +{ + Bucket *p; + + IS_CONSISTENT(ht); + + HASH_APPLY_BEGIN(ht); + p = ht->pListHead; + while (p != NULL) { + if (apply_func(p->pData)) { + p = zend_hash_apply_deleter(ht, p); + } else { + p = p->pListNext; + } + } + HASH_APPLY_END(ht); +} + + +ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument) +{ + Bucket *p; + + IS_CONSISTENT(ht); + + HASH_APPLY_BEGIN(ht); + p = ht->pListHead; + while (p != NULL) { + if (apply_func(p->pData, argument)) { + p = zend_hash_apply_deleter(ht, p); + } else { + p = p->pListNext; + } + } + HASH_APPLY_END(ht); +} + + +ZEND_API void zend_hash_apply_with_arguments(HashTable *ht, int (*destruct)(void *, int, va_list, zend_hash_key *), int num_args, ...) +{ + Bucket *p; + va_list args; + zend_hash_key hash_key; + + IS_CONSISTENT(ht); + + HASH_APPLY_BEGIN(ht); + + va_start(args, num_args); + p = ht->pListHead; + while (p != NULL) { + hash_key.arKey = p->arKey; + hash_key.nKeyLength = p->nKeyLength; + hash_key.h = p->h; + if (destruct(p->pData, num_args, args, &hash_key)) { + p = zend_hash_apply_deleter(ht, p); + } else { + p = p->pListNext; + } + } + va_end(args); + + HASH_APPLY_END(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; + + IS_CONSISTENT(source); + IS_CONSISTENT(target); + + p = source->pListHead; + while (p) { + if (p->nKeyLength) { + zend_hash_update(target, p->arKey, p->nKeyLength, 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; + } + 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) +{ + 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_add_or_update(target, p->arKey, p->nKeyLength, p->pData, size, &t, mode)==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; +} + + +ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, zend_bool (*pReplaceOrig)(void *orig, void *p_new)) +{ + Bucket *p; + void *t; + void *pOrig; + + IS_CONSISTENT(source); + IS_CONSISTENT(target); + + p = source->pListHead; + while (p) { + if (p->nKeyLength>0) { + if (zend_hash_find(target, p->arKey, p->nKeyLength, &pOrig)==FAILURE + || pReplaceOrig(pOrig, p->pData)) { + if (zend_hash_update(target, p->arKey, p->nKeyLength, p->pData, size, &t)==SUCCESS && pCopyConstructor) { + pCopyConstructor(t); + } + } + } else { + if (zend_hash_index_find(target, p->h, &pOrig)==FAILURE + || pReplaceOrig(pOrig, p->pData)) { + if (zend_hash_index_update(target, p->h, p->pData, size, &t)==SUCCESS && pCopyConstructor) { + pCopyConstructor(t); + } + } + } + p = p->pListNext; + } + target->pInternalPointer = target->pListHead; +} + + +ZEND_API ulong zend_get_hash_value(HashTable *ht, char *arKey, uint nKeyLength) +{ + IS_CONSISTENT(ht); + + return ht->pHashFunction(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(HashTable *ht, char *arKey, uint nKeyLength, void **pData) +{ + ulong h; + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_find(ht, idx, pData)); + + h = ht->pHashFunction(arKey, nKeyLength); + nIndex = h % ht->nTableSize; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) && (p->nKeyLength == nKeyLength)) { + if (!memcmp(p->arKey, arKey, nKeyLength)) { + *pData = p->pData; + return SUCCESS; + } + } + p = p->pNext; + } + return FAILURE; +} + + +ZEND_API int zend_hash_quick_find(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void **pData) +{ + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + nIndex = h % ht->nTableSize; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) && (p->nKeyLength == nKeyLength)) { + if (!memcmp(p->arKey, arKey, nKeyLength)) { + *pData = p->pData; + return SUCCESS; + } + } + p = p->pNext; + } + return FAILURE; +} + + +ZEND_API int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLength) +{ + ulong h; + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_exists(ht, idx)); + + h = ht->pHashFunction(arKey, nKeyLength); + nIndex = h % ht->nTableSize; + + p = ht->arBuckets[nIndex]; + while (p != NULL) { + if ((p->h == h) && (p->nKeyLength == nKeyLength)) { + if (!memcmp(p->arKey, arKey, nKeyLength)) { + return 1; + } + } + p = p->pNext; + } + return 0; +} + + +ZEND_API int zend_hash_index_find(HashTable *ht, ulong h, void **pData) +{ + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + nIndex = h % ht->nTableSize; + + 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(HashTable *ht, ulong h) +{ + uint nIndex; + Bucket *p; + + IS_CONSISTENT(ht); + + nIndex = h % ht->nTableSize; + + 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(HashTable *ht) +{ + IS_CONSISTENT(ht); + + return ht->nNumOfElements; +} + + +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(HashTable *ht, char **str_index, ulong *str_length, ulong *num_index, HashPosition *pos) +{ + Bucket *p; + + p = pos ? (*pos) : ht->pInternalPointer; + + IS_CONSISTENT(ht); + + if (p) { + if (p->nKeyLength) { + *str_index = (char *) pemalloc(p->nKeyLength, ht->persistent); + memcpy(*str_index, p->arKey, p->nKeyLength); + 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; + } +} + + +ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, + compare_func_t compar, int renumber) +{ + Bucket **arTmp; + Bucket *p; + int i, j; + + IS_CONSISTENT(ht); + + if (ht->nNumOfElements <= 1) { /* 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); + + HANDLE_BLOCK_INTERRUPTIONS(); + ht->pListHead = arTmp[0]; + ht->pListTail = NULL; + ht->pInternalPointer = ht->pListHead; + + for (j = 0; j < i; j++) { + if (ht->pListTail) { + ht->pListTail->pListNext = arTmp[j]; + } + arTmp[j]->pListLast = ht->pListTail; + arTmp[j]->pListNext = NULL; + ht->pListTail = arTmp[j]; + } + 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) +{ + Bucket *p1, *p2; + int result; + void *pData2; + + IS_CONSISTENT(ht1); + IS_CONSISTENT(ht2); + + result = ht1->nNumOfElements - ht2->nNumOfElements; + if (result!=0) { + return result; + } + + p1 = ht1->pListHead; + if (ordered) { + p2 = ht2->pListHead; + } + + while (p1) { + if (ordered && !p2) { + 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) { + return result; + } + } else { /* string indices */ + result = p1->nKeyLength - p2->nKeyLength; + if (result!=0) { + return result; + } + result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength); + if (result!=0) { + return result; + } + } + pData2 = p2->pData; + } else { + if (p1->nKeyLength==0) { /* numeric index */ + if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) { + return 1; + } + } else { /* string index */ + if (zend_hash_find(ht2, p1->arKey, p1->nKeyLength, &pData2)==FAILURE) { + return 1; + } + } + } + result = compar(p1->pData, pData2); + if (result!=0) { + return result; + } + p1 = p1->pListNext; + if (ordered) { + p2 = p2->pListNext; + } + } + + return 0; +} + + +ZEND_API int zend_hash_minmax(HashTable *ht, int (*compar) (const void *, const void *), int flag, void **pData) +{ + 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) < 0) { /* max */ + res = p; + } + } else { + if (compar(&res,&p) > 0) { /* min */ + res = p; + } + } + } + *pData = res->pData; + return SUCCESS; +} + +ZEND_API ulong zend_hash_next_free_element(HashTable *ht) +{ + IS_CONSISTENT(ht); + + return ht->nNextFreeElement; + +} + +#if ZEND_DEBUG +void zend_hash_display_pListTail(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(HashTable *ht) +{ + Bucket *p; + uint i; + + for (i = 0; i < ht->nTableSize; i++) { + p = ht->arBuckets[i]; + while (p != NULL) { + zend_output_debug_string(0, "%s <==> 0x%X\n", p->arKey, p->h); + p = p->pNext; + } + } + + p = ht->pListTail; + while (p != NULL) { + zend_output_debug_string(0, "%s <==> 0x%X\n", p->arKey, p->h); + p = p->pListLast; + } +} +#endif + +/* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * End: + */ |