From 4c5b385ff53ae9f0b52572e98c4db801f56603b0 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 07:56:37 +0300 Subject: [PATCH] More careful iterators update. --- Zend/tests/foreach_009.phpt | 40 +++++++++++++++++++++++ Zend/zend_hash.c | 65 +++++++++++++++++++++++++++++-------- Zend/zend_hash.h | 3 +- ext/standard/array.c | 7 ++-- 4 files changed, 95 insertions(+), 20 deletions(-) create mode 100644 Zend/tests/foreach_009.phpt diff --git a/Zend/tests/foreach_009.phpt b/Zend/tests/foreach_009.phpt new file mode 100644 index 0000000000..6ce8384642 --- /dev/null +++ b/Zend/tests/foreach_009.phpt @@ -0,0 +1,40 @@ +--TEST-- +Nested foreach by reference and array modification with resize +--FILE-- + +--EXPECT-- +4-4 +4-5 +4-6 +4-7 +5-4 +5-5 +5-6 +5-7 +5-8 +6-4 +6-5 +6-6 +6-7 +6-8 +7-4 +7-5 +7-6 +7-7 +7-8 +8-4 +8-5 +8-6 +8-7 +8-8 diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c index dd175c7c00..82617edf18 100644 --- a/Zend/zend_hash.c +++ b/Zend/zend_hash.c @@ -296,35 +296,73 @@ static zend_always_inline void iterators_del(HashTable *ht) } } -static zend_never_inline void _iterators_update(HashTable *ht, HashPosition pos) +static zend_never_inline void _iterators_update(HashTable *ht, HashPosition from, HashPosition to) { HashTableIterator *iter = EG(ht_iterators); HashTableIterator *end = iter + EG(ht_iterators_used); while (iter != end) { - if (iter->ht == ht && iter->pos == ht->nInternalPointer) { - iter->pos = pos; + if (iter->ht == ht && iter->pos == from) { + iter->pos = to; } iter++; } } -static zend_always_inline void iterators_update(HashTable *ht, HashPosition pos) +static zend_always_inline void iterators_update(HashTable *ht, HashPosition from, HashPosition to) { if (UNEXPECTED(ht->u.v.nIteratorsCount)) { - _iterators_update(ht, pos); + _iterators_update(ht, from, to); } } -ZEND_API void zend_hash_iterators_update(HashTable *ht, HashPosition pos) +static zend_never_inline void _iterators_update_to_next(HashTable *ht, HashPosition from) +{ + uint32_t to = from; + + while (1) { + to++; + if (to >= ht->nNumUsed) { + to = INVALID_IDX; + break; + } else if (Z_TYPE(ht->arData[to].val) != IS_UNDEF) { + break; + } + } + _iterators_update(ht, from, to); +} + +static zend_always_inline void iterators_update_to_next(HashTable *ht, HashPosition from) +{ + if (UNEXPECTED(ht->u.v.nIteratorsCount)) { + _iterators_update_to_next(ht, from); + } +} + +ZEND_API void zend_hash_iterators_update(HashTable *ht, HashPosition from, HashPosition to) +{ + if (UNEXPECTED(ht->u.v.nIteratorsCount)) { + HashTableIterator *iter = EG(ht_iterators); + HashTableIterator *end = iter + EG(ht_iterators_used); + + while (iter != end) { + if (iter->ht == ht && iter->pos == from) { + iter->pos = to; + } + iter++; + } + } +} + +ZEND_API void zend_hash_iterators_reset(HashTable *ht) { if (UNEXPECTED(ht->u.v.nIteratorsCount)) { HashTableIterator *iter = EG(ht_iterators); HashTableIterator *end = iter + EG(ht_iterators_used); while (iter != end) { - if (iter->ht == ht && iter->pos == ht->nInternalPointer) { - iter->pos = pos; + if (iter->ht == ht) { + iter->pos = ht->nInternalPointer; } iter++; } @@ -441,9 +479,9 @@ add_to_hash: idx = ht->nNumUsed++; ht->nNumOfElements++; if (ht->nInternalPointer == INVALID_IDX) { - iterators_update(ht, idx); ht->nInternalPointer = idx; } + iterators_update(ht, INVALID_IDX, idx); p = ht->arData + idx; p->h = h = zend_string_hash_val(key); p->key = key; @@ -609,9 +647,9 @@ add_to_packed: } ht->nNumOfElements++; if (ht->nInternalPointer == INVALID_IDX) { - iterators_update(ht, h); ht->nInternalPointer = h; } + iterators_update(ht, INVALID_IDX, h); if ((zend_long)h >= (zend_long)ht->nNextFreeElement) { ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX; } @@ -652,9 +690,9 @@ add_to_hash: idx = ht->nNumUsed++; ht->nNumOfElements++; if (ht->nInternalPointer == INVALID_IDX) { - iterators_update(ht, idx); ht->nInternalPointer = idx; } + iterators_update(ht, INVALID_IDX, idx); if ((zend_long)h >= (zend_long)ht->nNextFreeElement) { ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX; } @@ -741,9 +779,9 @@ ZEND_API int zend_hash_rehash(HashTable *ht) if (i != j) { ht->arData[j] = ht->arData[i]; if (ht->nInternalPointer == i) { - iterators_update(ht, j); ht->nInternalPointer = j; } + iterators_update(ht, i, j); } nIndex = ht->arData[j].h & ht->nTableMask; Z_NEXT(ht->arData[j].val) = ht->arHash[nIndex]; @@ -770,15 +808,14 @@ static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, } while (ht->nNumUsed > 0 && (Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)); } ht->nNumOfElements--; + iterators_update_to_next(ht, idx); if (ht->nInternalPointer == idx) { while (1) { idx++; if (idx >= ht->nNumUsed) { - iterators_update(ht, INVALID_IDX); ht->nInternalPointer = INVALID_IDX; break; } else if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { - iterators_update(ht, idx); ht->nInternalPointer = idx; break; } diff --git a/Zend/zend_hash.h b/Zend/zend_hash.h index c8218f1112..749846aaf9 100644 --- a/Zend/zend_hash.h +++ b/Zend/zend_hash.h @@ -229,7 +229,8 @@ ZEND_API int _zend_handle_numeric_str_ex(const char *key, size_t length, zend_ul ZEND_API uint32_t zend_hash_iterator_add(HashTable *ht); ZEND_API HashPosition zend_hash_iterator_pos(uint32_t idx, HashTable *ht); ZEND_API void zend_hash_iterator_del(uint32_t idx); -ZEND_API void zend_hash_iterators_update(HashTable *ht, HashPosition pos); +ZEND_API void zend_hash_iterators_update(HashTable *ht, HashPosition from, HashPosition to); +ZEND_API void zend_hash_iterators_reset(HashTable *ht); END_EXTERN_C() diff --git a/ext/standard/array.c b/ext/standard/array.c index 397bb88f0b..49c6cd0789 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -2203,9 +2203,7 @@ PHP_FUNCTION(array_shift) q->key = NULL; ZVAL_COPY_VALUE(&q->val, &p->val); ZVAL_UNDEF(&p->val); - if (idx == Z_ARRVAL_P(stack)->nInternalPointer) { - zend_hash_iterators_update(Z_ARRVAL_P(stack), k); - } + zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); } k++; } @@ -2268,14 +2266,13 @@ PHP_FUNCTION(array_unshift) } } ZEND_HASH_FOREACH_END(); - new_hash.nInternalPointer = Z_ARRVAL_P(stack)->nInternalPointer; new_hash.u.v.nIteratorsCount = Z_ARRVAL_P(stack)->u.v.nIteratorsCount; Z_ARRVAL_P(stack)->u.v.nIteratorsCount = 0; Z_ARRVAL_P(stack)->pDestructor = NULL; zend_hash_destroy(Z_ARRVAL_P(stack)); *Z_ARRVAL_P(stack) = new_hash; - zend_hash_iterators_update(Z_ARRVAL_P(stack), 0); zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack)); + zend_hash_iterators_reset(Z_ARRVAL_P(stack)); /* Clean up and return the number of elements in the stack */ RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack))); -- 2.49.0