php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Return to Bug #53866
Patch php-trunk-zend-hash-optimization revision 2011-01-28 12:36 UTC by marcin dot babij at nasza-klasa dot pl

Patch php-trunk-zend-hash-optimization for Scripting Engine problem Bug #53866

Patch version 2011-01-28 12:36 UTC

Return to Bug #53866 | Download this patch
Patch Revisions:

Developer: marcin.babij@nasza-klasa.pl

Index: ext/spl/spl_array.c
===================================================================
--- ext/spl/spl_array.c	(revision 307577)
+++ ext/spl/spl_array.c	(working copy)
@@ -117,12 +117,11 @@
 /*	IS_CONSISTENT(ht);*/
 
 /*	HASH_PROTECT_RECURSION(ht);*/
-	p = ht->arBuckets[intern->pos_h & ht->nTableMask];
-	while (p != NULL) {
+	uint nIndex = ZEND_HASH_BUCKET(ht, intern->pos_h);
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
 		if (p == intern->pos) {
 			return SUCCESS;
 		}
-		p = p->pNext;
 	}
 /*	HASH_UNPROTECT_RECURSION(ht); */
 	spl_array_rewind(intern TSRMLS_CC);
Index: Zend/zend_hash.c
===================================================================
--- Zend/zend_hash.c	(revision 307577)
+++ Zend/zend_hash.c	(working copy)
@@ -22,27 +22,6 @@
 #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
@@ -91,19 +70,11 @@
 	}
 
 
-#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) {												\
@@ -135,13 +106,6 @@
 		memcpy((p)->pData, pData, nDataSize);							\
 		(p)->pDataPtr=NULL;												\
 	}
-
-#define CHECK_INIT(ht) do {												\
-	if (UNEXPECTED((ht)->nTableMask == 0)) {								\
-		(ht)->nTableMask = (ht)->nTableSize - 1;						\
-		(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);	\
-	}																	\
-} while (0)
  
 static const Bucket *uninitialized_bucket = NULL;
 
@@ -158,12 +122,16 @@
 		while ((1U << i) < nSize) {
 			i++;
 		}
-		ht->nTableSize = 1 << i;
+		ht->nTableSize = 1 << (i+1);
+		if (ht->nTableSize < ZEND_HASH_MIN_TABLE_SIZE) {
+			ht->nTableSize = ZEND_HASH_MIN_TABLE_SIZE;
+		}
 	}
 
 	ht->nTableMask = 0;	/* 0 means that ht->arBuckets is uninitialized */
 	ht->pDestructor = pDestructor;
 	ht->arBuckets = (Bucket**)&uninitialized_bucket;
+	ht->arEmpty = NULL;
 	ht->pListHead = NULL;
 	ht->pListTail = NULL;
 	ht->nNumOfElements = 0;
@@ -210,36 +178,33 @@
 	CHECK_INIT(ht);
 
 	h = zend_inline_hash_func(arKey, nKeyLength);
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	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();
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, 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;
-				}
+			if (p->pData == pData) {
+				ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
 				HANDLE_UNBLOCK_INTERRUPTIONS();
-				return SUCCESS;
+				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) {
@@ -264,7 +229,7 @@
 
 	HANDLE_BLOCK_INTERRUPTIONS();
 	CONNECT_TO_GLOBAL_DLLIST(p, ht);
-	ht->arBuckets[nIndex] = p;
+	ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
 	HANDLE_UNBLOCK_INTERRUPTIONS();
 
 	ht->nNumOfElements++;
@@ -284,34 +249,31 @@
 	}
 
 	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();
+	nIndex = ZEND_HASH_BUCKET(ht, h);
+
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, 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;
-				}
+			if (p->pData == pData) {
+				ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
 				HANDLE_UNBLOCK_INTERRUPTIONS();
-				return SUCCESS;
+				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)) {
@@ -340,7 +302,7 @@
 	}
 
 	HANDLE_BLOCK_INTERRUPTIONS();
-	ht->arBuckets[nIndex] = p;
+	ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
 	CONNECT_TO_GLOBAL_DLLIST(p, ht);
 	HANDLE_UNBLOCK_INTERRUPTIONS();
 
@@ -369,11 +331,10 @@
 	if (flag & HASH_NEXT_INSERT) {
 		h = ht->nNextFreeElement;
 	}
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	p = ht->arBuckets[nIndex];
-	while (p != NULL) {
-		if ((p->nKeyLength == 0) && (p->h == h)) {
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_INDEX(p, h)) {
 			if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
 				return FAILURE;
 			}
@@ -398,7 +359,6 @@
 			}
 			return SUCCESS;
 		}
-		p = p->pNext;
 	}
 	p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent);
 	if (!p) {
@@ -415,7 +375,7 @@
 	CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
 
 	HANDLE_BLOCK_INTERRUPTIONS();
-	ht->arBuckets[nIndex] = p;
+	ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
 	CONNECT_TO_GLOBAL_DLLIST(p, ht);
 	HANDLE_UNBLOCK_INTERRUPTIONS();
 
@@ -427,91 +387,97 @@
 	return SUCCESS;
 }
 
-
-static int zend_hash_do_resize(HashTable *ht)
+ZEND_API int zend_hash_do_resize(HashTable *ht)
 {
-	Bucket **t;
+	void *t;
+	uint dest_size = ht->nTableSize <= ZEND_HASH_SMALL_TABLE_SIZE ? (ht->nTableSize << 2) : (ht->nTableSize << 1);
 
 	IS_CONSISTENT(ht);
+	CHECK_INIT(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;
+	if (dest_size > 0) {	/* Let's change the table size */
+		t = perealloc(ht->arBuckets, dest_size * (sizeof(Bucket *) + 1), ht->persistent);
+		if (!t) {
+			return FAILURE;
 		}
-		return FAILURE;
+		HANDLE_BLOCK_INTERRUPTIONS();
+		ht->nTableSize = dest_size;
+		ht->nTableMask = ht->nTableSize - 1;
+		ht->arBuckets = (Bucket**)t;
+		ht->arEmpty = ((uchar*)t) + (ht->nTableSize * (sizeof(Bucket*)));
+		zend_hash_rehash(ht);
+		HANDLE_UNBLOCK_INTERRUPTIONS();
+		return SUCCESS;
 	}
-	return SUCCESS;
+	return FAILURE;
 }
 
-ZEND_API int zend_hash_rehash(HashTable *ht)
+int zend_hash_rehash(HashTable *ht)
 {
 	Bucket *p;
 	uint nIndex;
 
 	IS_CONSISTENT(ht);
-	if (UNEXPECTED(ht->nNumOfElements == 0)) {
-		return SUCCESS;
+	if ((ht)->nTableMask == 0) {
+		return;
 	}
 
-	memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
+	memset(ht->arEmpty, 0, ht->nTableSize * 1);
+
 	p = ht->pListHead;
 	while (p != NULL) {
-		nIndex = p->h & ht->nTableMask;
+		nIndex = ZEND_HASH_BUCKET(ht, p->h);
+		ZEND_HASH_FIND_FREE(ht, nIndex);
+		ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
 		CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
-		ht->arBuckets[nIndex] = p;
 		p = p->pListNext;
 	}
 	return SUCCESS;
 }
 
+inline void zend_hash_free_bucket(HashTable *ht, uint nIndex) {
+	uint nIndexSlot = nIndex;
+	uint nSourceIndex;
+
+	ZEND_HASH_MAKE_ELEMENT_EMPTY(ht, nIndexSlot);
+	for(;;) {
+		ZEND_HASH_NEXT_INDEX(ht, nIndexSlot);
+		if (!ZEND_HASH_BUCKET_IS_OCCUPIED(ht, nIndexSlot)) {
+			break;
+		}
+		nSourceIndex = ZEND_HASH_BUCKET(ht, ht->arBuckets[nIndexSlot]->h);
+		if ((nIndex < nIndexSlot) ?
+				((nIndex < nSourceIndex) && (nSourceIndex <= nIndexSlot)) :
+				((nIndex < nSourceIndex) || (nSourceIndex <= nIndexSlot))) {
+			continue;
+		}
+		ZEND_HASH_FILL_BUCKET(ht, nIndex, ht->arBuckets[nIndexSlot]);
+		nIndex = nIndexSlot;
+		ZEND_HASH_MAKE_ELEMENT_EMPTY(ht, nIndexSlot);
+	}
+}
+
 ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
 {
 	uint nIndex;
 	Bucket *p;
 
 	IS_CONSISTENT(ht);
+	if ((ht)->nTableMask == 0) {
+		return FAILURE;
+	}
 
 	if (flag == HASH_DEL_KEY) {
 		h = zend_inline_hash_func(arKey, nKeyLength);
 	}
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	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 */
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, 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;
-			}
+			
+			REMOVE_FROM_HASH(p, nIndex, ht);
+
 			if (ht->pDestructor) {
 				ht->pDestructor(p->pData);
 			}
@@ -520,10 +486,8 @@
 			}
 			pefree(p, ht->persistent);
 			HANDLE_UNBLOCK_INTERRUPTIONS();
-			ht->nNumOfElements--;
 			return SUCCESS;
 		}
-		p = p->pNext;
 	}
 	return FAILURE;
 }
@@ -578,7 +542,7 @@
 		pefree(q, ht->persistent);
 	}
 	if (ht->nTableMask) {
-		memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
+		memset(ht->arEmpty, 0, ht->nTableSize*1);
 	}
 	ht->pListHead = NULL;
 	ht->pListTail = NULL;
@@ -591,43 +555,28 @@
 
 /* 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
+ * 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 (p->pLast) {
-		p->pLast->pNext = p->pNext;
-	} else {
-		uint nIndex;
+	uint nIndex;
 
-		nIndex = p->h & ht->nTableMask;
-		ht->arBuckets[nIndex] = p->pNext;
+	nIndex = ZEND_HASH_BUCKET(ht, p->h);
+	for (; ht->arBuckets[nIndex] != p; ZEND_HASH_NEXT_INDEX(ht, nIndex)) {
+#ifdef ZEND_DEBUG
+		if (!ZEND_HASH_BUCKET_IS_OCCUPIED(ht, nIndex)) {
+			zend_output_debug_string(1, "No element to delete");
+		}
+#endif
 	}
-	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_BLOCK_INTERRUPTIONS();
+
+	REMOVE_FROM_HASH(p, nIndex, ht);
+
 	HANDLE_UNBLOCK_INTERRUPTIONS();
 
 	if (ht->pDestructor) {
@@ -899,19 +848,19 @@
 	uint nIndex;
 	Bucket *p;
 
+	if (ht->nTableMask == 0) {
+		return FAILURE;
+	}
+
 	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;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+			*pData = p->pData;
+			return SUCCESS;
 		}
-		p = p->pNext;
 	}
 	return FAILURE;
 }
@@ -924,20 +873,19 @@
 
 	if (nKeyLength==0) {
 		return zend_hash_index_find(ht, h, pData);
+	} else if (ht->nTableMask == 0) {
+		return FAILURE;
 	}
 
 	IS_CONSISTENT(ht);
 
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	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;
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+			*pData = p->pData;
+			return SUCCESS;
 		}
-		p = p->pNext;
 	}
 	return FAILURE;
 }
@@ -949,18 +897,19 @@
 	uint nIndex;
 	Bucket *p;
 
+	if (ht->nTableMask == 0) {
+		return 0;
+	}
+
 	IS_CONSISTENT(ht);
 
 	h = zend_inline_hash_func(arKey, nKeyLength);
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	p = ht->arBuckets[nIndex];
-	while (p != NULL) {
-		if (p->arKey == arKey ||
-			((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
-				return 1;
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+			return 1;
 		}
-		p = p->pNext;
 	}
 	return 0;
 }
@@ -973,19 +922,18 @@
 
 	if (nKeyLength==0) {
 		return zend_hash_index_exists(ht, h);
+	} else if (ht->nTableMask == 0) {
+		return 0;
 	}
 
 	IS_CONSISTENT(ht);
 
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	p = ht->arBuckets[nIndex];
-	while (p != NULL) {
-		if (p->arKey == arKey ||
-			((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
-				return 1;
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+			return 1;
 		}
-		p = p->pNext;
 	}
 	return 0;
 
@@ -997,17 +945,19 @@
 	uint nIndex;
 	Bucket *p;
 
+	if (ht->nTableMask == 0) {
+		return FAILURE;
+	}
+
 	IS_CONSISTENT(ht);
 
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	p = ht->arBuckets[nIndex];
-	while (p != NULL) {
-		if ((p->h == h) && (p->nKeyLength == 0)) {
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_INDEX(p, h)) {
 			*pData = p->pData;
 			return SUCCESS;
 		}
-		p = p->pNext;
 	}
 	return FAILURE;
 }
@@ -1018,16 +968,18 @@
 	uint nIndex;
 	Bucket *p;
 
+	if (ht->nTableMask == 0) {
+		return 0;
+	}
+
 	IS_CONSISTENT(ht);
 
-	nIndex = h & ht->nTableMask;
+	nIndex = ZEND_HASH_BUCKET(ht, h);
 
-	p = ht->arBuckets[nIndex];
-	while (p != NULL) {
-		if ((p->h == h) && (p->nKeyLength == 0)) {
+	ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+		if (EQ_INDEX(p, h)) {
 			return 1;
 		}
-		p = p->pNext;
 	}
 	return 0;
 }
@@ -1059,15 +1011,18 @@
 		ht->pInternalPointer = NULL;
 	} else if (ht->pInternalPointer != ptr->pos) {
 		Bucket *p;
+		
+		if (ht->nTableMask == 0) {
+			return 0;
+		}
 
 		IS_CONSISTENT(ht);
-		p = ht->arBuckets[ptr->h & ht->nTableMask];
-		while (p != NULL) {
+		uint nIndex = ZEND_HASH_BUCKET(ht, ptr->h);
+		ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
 			if (p == ptr->pos) {
 				ht->pInternalPointer = p;
 				return 1;
 			}
-			p = p->pNext;
 		}
 		return 0;
 	}
@@ -1196,26 +1151,32 @@
 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;
+	Bucket *q;
+	uint nIndex;
 
 	p = pos ? (*pos) : ht->pInternalPointer;
 
+	if (ht->nTableMask == 0) {
+		return FAILURE;
+	}
+
 	IS_CONSISTENT(ht);
 
 	if (p) {
 		if (key_type == HASH_KEY_IS_LONG) {
 			str_length = 0;
-			if (!p->nKeyLength && p->h == num_index) {
+			if (EQ_INDEX(p, num_index)) {
 				return SUCCESS;
 			}
 
 			if (mode != HASH_UPDATE_KEY_ANYWAY) {
-				Bucket *q = ht->arBuckets[num_index & ht->nTableMask];
+				nIndex = ZEND_HASH_BUCKET(ht, num_index);
 				int found = 0;
 
-				while (q != NULL) {
+				ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, q) {
 					if (q == p) {
 						found = 1;
-					} else if (!q->nKeyLength && q->h == num_index) {
+					} else if (EQ_INDEX(q, num_index)) {
 						if (found) {
 							if (mode & HASH_UPDATE_KEY_IF_BEFORE) {
 								break;
@@ -1240,28 +1201,26 @@
 							}
 						}
 					}
-					q = q->pNext;
 				}
 			}
 
 			zend_hash_index_del(ht, num_index);
 		} else if (key_type == HASH_KEY_IS_STRING) {
 			if (p->nKeyLength == str_length &&
-			    memcmp(p->arKey, str_index, str_length) == 0) {
+					memcmp(p->arKey, str_index, str_length) == 0) {
 				return SUCCESS;
 			}
 
 			if (mode != HASH_UPDATE_KEY_ANYWAY) {
 				ulong h = zend_inline_hash_func(str_index, str_length);
-				Bucket *q = ht->arBuckets[h & ht->nTableMask];
+				nIndex = ZEND_HASH_BUCKET(ht, h);
 				int found = 0;
 
-				while (q != NULL) {
+				ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, q) {
 					if (q == p) {
 						found = 1;
-					} else if (q->h == h && q->nKeyLength == str_length && 
-					           memcmp(q->arKey, str_index, str_length) == 0) {
-					    if (found) {
+					} else if (EQ_HASH_KEYS(q, str_index, h, str_length)) {
+						if (found) {
 							if (mode & HASH_UPDATE_KEY_IF_BEFORE) {
 								break;
 							} else {
@@ -1285,7 +1244,6 @@
 							}
 						}
 					}
-					q = q->pNext;
 				}
 			}
 
@@ -1296,14 +1254,13 @@
 
 		HANDLE_BLOCK_INTERRUPTIONS();
 
-		if (p->pNext) {
-			p->pNext->pLast = p->pLast;
+		nIndex = ZEND_HASH_BUCKET(ht, p->h);
+		ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, q) {
+			if (p == q) {
+				zend_hash_free_bucket(ht, nIndex);
+				break;
+			}
 		}
-		if (p->pLast) {
-			p->pLast->pNext = p->pNext;
-		} else{
-			ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
-		}
 
 		if (p->nKeyLength != str_length) {
 			Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) + str_length, ht->persistent);
@@ -1345,8 +1302,10 @@
 			p->h = zend_inline_hash_func(str_index, str_length);
 		}
 
-		CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
-		ht->arBuckets[p->h & ht->nTableMask] = p;
+		nIndex = ZEND_HASH_BUCKET(ht, p->h);
+		CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
+		ZEND_HASH_FIND_FREE(ht, nIndex);
+		ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
 		HANDLE_UNBLOCK_INTERRUPTIONS();
 
 		return SUCCESS;
@@ -1539,7 +1498,6 @@
 
 }
 
-
 #if ZEND_DEBUG
 void zend_hash_display_pListTail(const HashTable *ht)
 {
@@ -1563,9 +1521,8 @@
 	}
 	for (i = 0; i < ht->nTableSize; i++) {
 		p = ht->arBuckets[i];
-		while (p != NULL) {
+		if (ZEND_HASH_BUCKET_IS_OCCUPIED(ht, i)) {
 			zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
-			p = p->pNext;
 		}
 	}
 
Index: Zend/zend_hash.h
===================================================================
--- Zend/zend_hash.h	(revision 307577)
+++ Zend/zend_hash.h	(working copy)
@@ -48,6 +48,7 @@
 typedef void (*dtor_func_t)(void *pDest);
 typedef void (*copy_ctor_func_t)(void *pElement);
 typedef void (*copy_ctor_param_func_t)(void *pElement, void *pParam);
+typedef unsigned char uchar;
 
 struct _hashtable;
 
@@ -58,8 +59,6 @@
 	void *pDataPtr;
 	struct bucket *pListNext;
 	struct bucket *pListLast;
-	struct bucket *pNext;
-	struct bucket *pLast;
 	char *arKey;
 } Bucket;
 
@@ -72,6 +71,7 @@
 	Bucket *pListHead;
 	Bucket *pListTail;
 	Bucket **arBuckets;
+	uchar *arEmpty;
 	dtor_func_t pDestructor;
 	zend_bool persistent;
 	unsigned char nApplyCount;
@@ -124,7 +124,95 @@
 
 ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength);
 
+ZEND_API int zend_hash_do_resize(HashTable *ht);
 
+#define ZEND_HASH_SMALL_TABLE_SIZE 64
+#define ZEND_HASH_MIN_TABLE_SIZE 4
+#define ZEND_HASH_SMALL_LOAD_FACTOR_TABLE_SIZE 16
+#define ZEND_HASH_SMALL_LOAD_FACTOR_INV 1.75
+#define ZEND_HASH_LOAD_FACTOR_INV 1.25
+
+#define ZEND_HASH_BUCKET(ht, index) \
+	(((index) + ((index)<<4)) & (ht)->nTableMask)
+
+#define EQ_KEYS(a,b,n) (!memcmp((a), (b), (n)))
+#define EQ_HASH_KEYS(ptr,key,hash,len) (EXPECTED(((ptr)->h == (hash)) && \
+	((ptr)->nKeyLength == (len)) && \
+	((len) == 0 || EQ_KEYS((ptr)->arKey,(key),(len)))))
+
+#define ZEND_HASH_NEXT_INDEX(ht, index) \
+	(index) = (((index)+1) & (ht)->nTableMask)
+#define ZEND_HASH_BUCKET_IS_OCCUPIED(ht, index) \
+	((ht)->arEmpty[(index)] != 0)
+#define ZEND_HASH_GET_BUCKET_AND_CHECK_OCCUPIED(ht, index, bucket) \
+	(bucket) = (ht)->arBuckets[(index)], ZEND_HASH_BUCKET_IS_OCCUPIED((ht), (index))
+#define ZEND_HASH_ITERATE_UNTIL_FREE(ht, index, bucket) \
+	for (; ZEND_HASH_GET_BUCKET_AND_CHECK_OCCUPIED((ht), (index), (bucket)); ZEND_HASH_NEXT_INDEX((ht), (index)))
+#define ZEND_HASH_FIND_FREE(ht, index) \
+	for (; ZEND_HASH_BUCKET_IS_OCCUPIED((ht), (index)); ZEND_HASH_NEXT_INDEX((ht), (index)))
+#define ZEND_HASH_FILL_BUCKET(ht, index, element) \
+	(ht)->arBuckets[(index)] = element; \
+	(ht)->arEmpty[(index)] = 1;
+#define ZEND_HASH_MAKE_ELEMENT_EMPTY(ht, index) \
+	(ht)->arEmpty[(index)] = 0;
+#define ZEND_HASH_IF_FULL_DO_RESIZE(ht)				\
+	if ((ht)->nTableSize <= ZEND_HASH_SMALL_LOAD_FACTOR_TABLE_SIZE ? \
+			((ht)->nNumOfElements*ZEND_HASH_SMALL_LOAD_FACTOR_INV > (ht)->nTableSize) : \
+			((ht)->nNumOfElements*ZEND_HASH_LOAD_FACTOR_INV > (ht)->nTableSize)) {   \
+		zend_hash_do_resize(ht);					\
+	}
+#define EQ_INDEX(ptr,index) \
+	(EXPECTED(((ptr)->nKeyLength == 0) && (ptr)->h == index))
+
+#define CONNECT_TO_BUCKET_DLLIST(element, list_head)
+#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);				\
+	}
+#define REMOVE_FROM_GLOBAL_DLLIST(element, ht)					\
+	if ((element)->pListLast != NULL) {							\
+		(element)->pListLast->pListNext = (element)->pListNext;	\
+	} else {													\
+		(ht)->pListHead = (element)->pListNext;					\
+	}															\
+	if ((element)->pListNext != NULL) {							\
+		(element)->pListNext->pListLast = (element)->pListLast;	\
+	} else {													\
+		(ht)->pListTail = (element)->pListLast;					\
+	}
+#define REMOVE_FROM_HASH(element, nIndex, ht)			\
+	zend_hash_free_bucket((ht), (nIndex));				\
+	REMOVE_FROM_GLOBAL_DLLIST((element), (ht))			\
+	if ((ht)->pInternalPointer == (element)) {			\
+		(ht)->pInternalPointer = (element)->pListNext;	\
+	}													\
+	(ht)->nNumOfElements--;
+#define ALLOC_BUCKETS(ht) do {														\
+	(ht)->nTableMask = (ht)->nTableSize - 1;										\
+	void* tmp;																		\
+	tmp = pemalloc_rel((ht)->nTableSize * (sizeof(Bucket*)+1), (ht)->persistent);	\
+	if (!tmp) {																		\
+		return FAILURE;																\
+	}																				\
+	(ht)->arBuckets = (Bucket**)tmp;												\
+	(ht)->arEmpty = ((uchar*)tmp) + ((ht)->nTableSize * (sizeof(Bucket*)));			\
+	memset((ht)->arEmpty, 0, (ht)->nTableSize * 1);									\
+} while (0)
+#define CHECK_INIT(ht) do {						\
+	if (UNEXPECTED((ht)->nTableMask == 0)) {	\
+		ALLOC_BUCKETS((ht));					\
+	}											\
+} while (0)
+
 #define ZEND_HASH_APPLY_KEEP				0
 #define ZEND_HASH_APPLY_REMOVE				1<<0
 #define ZEND_HASH_APPLY_STOP				1<<1
@@ -225,69 +313,33 @@
 
 ZEND_API int zend_hash_rehash(HashTable *ht);
 
-/*
- * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
- *
- * This is Daniel J. Bernstein's popular `times 33' hash function as
- * posted by him years ago on comp.lang.c. It basically uses a function
- * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
- * known hash functions for strings. Because it is both computed very
- * fast and distributes very well.
- *
- * The magic of number 33, i.e. why it works better than many other
- * constants, prime or not, has never been adequately explained by
- * anyone. So I try an explanation: if one experimentally tests all
- * multipliers between 1 and 256 (as RSE did now) one detects that even
- * numbers are not useable at all. The remaining 128 odd numbers
- * (except for the number 1) work more or less all equally well. They
- * all distribute in an acceptable way and this way fill a hash table
- * with an average percent of approx. 86%. 
- *
- * If one compares the Chi^2 values of the variants, the number 33 not
- * even has the best value. But the number 33 and a few other equally
- * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
- * advantage to the remaining numbers in the large set of possible
- * multipliers: their multiply operation can be replaced by a faster
- * operation based on just one shift plus either a single addition
- * or subtraction operation. And because a hash function has to both
- * distribute good _and_ has to be very fast to compute, those few
- * numbers should be preferred and seems to be the reason why Daniel J.
- * Bernstein also preferred it.
- *
- *
- *                  -- Ralf S. Engelschall <rse@engelschall.com>
- */
-
 static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
 {
-	register ulong hash = 5381;
+	ulong hash = 5381;
+	const ulong* ar = (ulong*)arKey;
 
-	/* variant with the hash unrolled eight times */
-	for (; nKeyLength >= 8; nKeyLength -= 8) {
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
-		hash = ((hash << 5) + hash) + *arKey++;
+	if (nKeyLength < sizeof(ulong)) {
+		switch (nKeyLength) {
+			case 7: hash = (hash<<8) | *arKey++; /* fallthrough... */
+			case 6: hash = (hash<<8) | *arKey++; /* fallthrough... */
+			case 5: hash = (hash<<8) | *arKey++; /* fallthrough... */
+			case 4: hash = (hash<<8) | *arKey++; /* fallthrough... */
+			case 3: hash = (hash<<8) | *arKey++; /* fallthrough... */
+			case 2: hash = (hash<<8) | *arKey++; /* fallthrough... */
+			case 1: hash = (hash<<8) | *arKey++; break;
+			case 0: break;
+			EMPTY_SWITCH_DEFAULT_CASE()
+		}
+	} else {
+		const ulong* arEnd = (ulong*)(arKey + nKeyLength - sizeof(ulong));
+		hash = *arEnd;
+		for (; ar < arEnd; ar++) {
+			hash = ((hash << 5) + hash) + *ar;
+		}
 	}
-	switch (nKeyLength) {
-		case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
-		case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
-		case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
-		case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
-		case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
-		case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
-		case 1: hash = ((hash << 5) + hash) + *arKey++; break;
-		case 0: break;
-EMPTY_SWITCH_DEFAULT_CASE()
-	}
-	return hash;
+	return (hash<<16)|(hash%65165);
 }
 
-
 ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength);
 
 #if ZEND_DEBUG
Index: Zend/zend_string.c
===================================================================
--- Zend/zend_string.c	(revision 307577)
+++ Zend/zend_string.c	(working copy)
@@ -37,7 +37,7 @@
 static void zend_interned_strings_snapshot_int(TSRMLS_D);
 static void zend_interned_strings_restore_int(TSRMLS_D);
 
-void zend_interned_strings_init(TSRMLS_D)
+int zend_interned_strings_init(TSRMLS_D)
 {
 #ifndef ZTS
 	size_t size = 1024 * 1024;
@@ -53,10 +53,9 @@
 	CG(interned_strings_end) = CG(interned_strings_start) + size;
 
 	zend_hash_init(&CG(interned_strings), 0, NULL, NULL, 1);
-	
-	CG(interned_strings).nTableMask = CG(interned_strings).nTableSize - 1;
-	CG(interned_strings).arBuckets = (Bucket **) pecalloc(CG(interned_strings).nTableSize, sizeof(Bucket *), CG(interned_strings).persistent);
 
+	ALLOC_BUCKETS(&CG(interned_strings));
+
 #if ZEND_DEBUG_INTERNED_STRINGS
 	mprotect(CG(interned_strings_start), CG(interned_strings_end) - CG(interned_strings_start), PROT_READ);
 #endif
@@ -66,6 +65,8 @@
 	zend_new_interned_string = zend_new_interned_string_int;
 	zend_interned_strings_snapshot = zend_interned_strings_snapshot_int;
 	zend_interned_strings_restore = zend_interned_strings_restore_int;
+
+	return SUCCESS;
 }
 
 void zend_interned_strings_dtor(TSRMLS_D)
@@ -91,18 +92,14 @@
 	}
 
 	h = zend_inline_hash_func(arKey, nKeyLength);
-	nIndex = h & CG(interned_strings).nTableMask;
-	p = CG(interned_strings).arBuckets[nIndex];
-	while (p != NULL) {
-		if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
-			if (!memcmp(p->arKey, arKey, nKeyLength)) {
-				if (free_src) {
-					efree((void *)arKey);
-				}
-				return p->arKey;
+	nIndex = ZEND_HASH_BUCKET(&CG(interned_strings), h);
+	ZEND_HASH_ITERATE_UNTIL_FREE(&CG(interned_strings), nIndex, p) {
+		if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+			if (free_src) {
+				efree((void *)arKey);
 			}
+			return p->arKey;
 		}
-		p = p->pNext;
 	}
 	
 	if (CG(interned_strings_top) + ZEND_MM_ALIGNED_SIZE(sizeof(Bucket) + nKeyLength) >=
@@ -127,46 +124,18 @@
 	p->h = h;
 	p->pData = &p->pDataPtr;
 	p->pDataPtr = p;
-	
-	p->pNext = CG(interned_strings).arBuckets[nIndex];
-	p->pLast = NULL;
-	if (p->pNext) {
-		p->pNext->pLast = p;
-	}
+	CONNECT_TO_BUCKET_DLLIST(p, &CG(interned_strings)->arBuckets[nIndex]);
 
 	HANDLE_BLOCK_INTERRUPTIONS();
-	
-	p->pListLast = CG(interned_strings).pListTail;
-	CG(interned_strings).pListTail = p;
-	p->pListNext = NULL;
-	if (p->pListLast != NULL) {
-		p->pListLast->pListNext = p;
-	}
-	if (!CG(interned_strings).pListHead) {
-		CG(interned_strings).pListHead = p;
-	}
 
-	CG(interned_strings).arBuckets[nIndex] = p;
+	CONNECT_TO_GLOBAL_DLLIST(p, &CG(interned_strings));
+	ZEND_HASH_FILL_BUCKET(&CG(interned_strings), nIndex, p);
 
 	HANDLE_UNBLOCK_INTERRUPTIONS();
 
 	CG(interned_strings).nNumOfElements++;
+	ZEND_HASH_IF_FULL_DO_RESIZE(&CG(interned_strings));
 
-	if (CG(interned_strings).nNumOfElements > CG(interned_strings).nTableSize) {
-		if ((CG(interned_strings).nTableSize << 1) > 0) {	/* Let's double the table size */
-			Bucket **t = (Bucket **) perealloc_recoverable(CG(interned_strings).arBuckets, (CG(interned_strings).nTableSize << 1) * sizeof(Bucket *), CG(interned_strings).persistent);
-
-			if (t) {
-				HANDLE_BLOCK_INTERRUPTIONS();
-				CG(interned_strings).arBuckets = t;
-				CG(interned_strings).nTableSize = (CG(interned_strings).nTableSize << 1);
-				CG(interned_strings).nTableMask = CG(interned_strings).nTableSize - 1;
-				zend_hash_rehash(&CG(interned_strings));
-				HANDLE_UNBLOCK_INTERRUPTIONS();
-			}
-		}
-	}
-
 #if ZEND_DEBUG_INTERNED_STRINGS
 	mprotect(CG(interned_strings_start), CG(interned_strings_end) - CG(interned_strings_start), PROT_READ);
 #endif
@@ -197,25 +166,13 @@
 #endif
 
 	for (i = 0; i < CG(interned_strings).nTableSize; i++) {
-		p = CG(interned_strings).arBuckets[i];
-		while (p && p->arKey > CG(interned_strings_top)) {
-			CG(interned_strings).nNumOfElements--;
-			if (p->pListLast != NULL) {
-				p->pListLast->pListNext = p->pListNext;
-			} else { 
-				CG(interned_strings).pListHead = p->pListNext;
+		for(;;) {
+			p = CG(interned_strings).arBuckets[i];
+			if (!ZEND_HASH_BUCKET_IS_OCCUPIED(&CG(interned_strings), i) || p->arKey <= CG(interned_strings_top)) {
+				break;
 			}
-			if (p->pListNext != NULL) {
-				p->pListNext->pListLast = p->pListLast;
-			} else {
-				CG(interned_strings).pListTail = p->pListLast;
-			}
-			p = p->pNext;
+			REMOVE_FROM_HASH(p, i, &CG(interned_strings));
 		}
-		if (p) {
-			p->pLast = NULL;
-		}
-		CG(interned_strings).arBuckets[i] = p;
 	}
 
 #if ZEND_DEBUG_INTERNED_STRINGS
Index: Zend/zend_string.h
===================================================================
--- Zend/zend_string.h	(revision 307577)
+++ Zend/zend_string.h	(working copy)
@@ -27,7 +27,7 @@
 ZEND_API extern void (*zend_interned_strings_snapshot)(TSRMLS_D);
 ZEND_API extern void (*zend_interned_strings_restore)(TSRMLS_D);
 
-void zend_interned_strings_init(TSRMLS_D);
+int zend_interned_strings_init(TSRMLS_D);
 void zend_interned_strings_dtor(TSRMLS_D);
 
 #ifndef ZTS
 
PHP Copyright © 2001-2020 The PHP Group
All rights reserved.
Last updated: Tue Feb 18 19:01:28 2020 UTC