Add zend_hash_reindex

The implementation differs from the original in array.c in that it
rehashes the hashtable in the same loop. This is approximately two
times faster (not counting the rare case of a purely associative
array).

3 files changed, 26 insertions, 21 deletions

diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c
index f419e8a571..d41ad43969 100644
--- a/Zend/zend_hash.c
+++ b/Zend/zend_hash.c
@@ -466,16 +466,37 @@ ZEND_API int zend_hash_rehash(HashTable *ht)
 	}
 
 	memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
-	p = ht->pListHead;
-	while (p != NULL) {
+	for (p = ht->pListHead; p != NULL; p = p->pListNext) {
 		nIndex = p->h & ht->nTableMask;
 		CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
 		ht->arBuckets[nIndex] = p;
-		p = p->pListNext;
 	}
 	return SUCCESS;
 }
 
+ZEND_API void zend_hash_reindex(HashTable *ht) {
+	Bucket *p;
+	uint nIndex;
+	ulong offset = 0;
+
+	IS_CONSISTENT(ht);
+	if (UNEXPECTED(ht->nNumOfElements == 0)) {
+		return;
+	}
+
+	memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
+	for (p = ht->pListHead; p != NULL; p = p->pListNext) {
+		if (p->nKeyLength == 0) {
+			p->h = offset++;
+		}
+
+		nIndex = p->h & ht->nTableMask;
+		CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
+		ht->arBuckets[nIndex] = p;
+	}
+	ht->nNextFreeElement = offset;
+}
+
 ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
 {
 	uint nIndex;
diff --git a/Zend/zend_hash.h b/Zend/zend_hash.h
index d990c16674..eb9a53769e 100644
--- a/Zend/zend_hash.h
+++ b/Zend/zend_hash.h
@@ -227,6 +227,7 @@ ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int fl
 ZEND_API int zend_hash_num_elements(const HashTable *ht);
 
 ZEND_API int zend_hash_rehash(HashTable *ht);
+ZEND_API void zend_hash_reindex(HashTable *ht);
 
 /*
  * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
diff --git a/ext/standard/array.c b/ext/standard/array.c
index e84e019690..90ef8e47b8 100644
--- a/ext/standard/array.c
+++ b/ext/standard/array.c
@@ -1975,24 +1975,7 @@ static void _phpi_pop(INTERNAL_FUNCTION_PARAMETERS, int off_the_end)
 
 	/* If we did a shift... re-index like it did before */
 	if (!off_the_end) {
-		unsigned int k = 0;
-		int should_rehash = 0;
-		Bucket *p = Z_ARRVAL_P(stack)->pListHead;
-		while (p != NULL) {
-			if (p->nKeyLength == 0) {
-				if (p->h != k) {
-					p->h = k++;
-					should_rehash = 1;
-				} else {
-					k++;
-				}
-			}
-			p = p->pListNext;
-		}
-		Z_ARRVAL_P(stack)->nNextFreeElement = k;
-		if (should_rehash) {
-			zend_hash_rehash(Z_ARRVAL_P(stack));
-		}
+		zend_hash_reindex(Z_ARRVAL_P(stack));
 	} else if (!key_len && index >= Z_ARRVAL_P(stack)->nNextFreeElement - 1) {
 		Z_ARRVAL_P(stack)->nNextFreeElement = Z_ARRVAL_P(stack)->nNextFreeElement - 1;
 	}