com php-src: Add zend_hash_reindex: Zend/zend_hash. c Zend/zend_hash.h ext/standard/array.c

Commit: 1aa8719e32663fbfcad9668364fbac0bc415b678 Author: Nikita Popov <nikic@php.net> Tue, 8 Apr 2014 11:17:17 +0200 Parents: eaf44ec397cc3286107166ce51bac03bf6bc8f83 Branches: PHP-5.6 master Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=1aa8719e32663fbfcad9668364fbac0bc415b678 Log: 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). Changed paths: M Zend/zend_hash.c M Zend/zend_hash.h M ext/standard/array.c Diff: diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c index f419e8a..d41ad43 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 d990c16..eb9a537 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 e84e019..90ef8e4 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; }