text: /*
     +----------------------------------------------------------------------+
     | 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:
   */
  