From 15a23b1218b3e38630d677751a975907daa2cd54 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Thu, 29 Jan 2015 21:05:02 +0300 Subject: Reimplement iteration magic with HashTableIterators (see https://wiki.php.net/rfc/php7_foreach#implementation_details) --- ext/standard/array.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'ext/standard/array.c') diff --git a/ext/standard/array.c b/ext/standard/array.c index 966ea0f1f6..397bb88f0b 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -2203,6 +2203,9 @@ 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); + } } k++; } @@ -2265,9 +2268,14 @@ 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)); /* Clean up and return the number of elements in the stack */ RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack))); -- cgit v1.2.1 From 4c5b385ff53ae9f0b52572e98c4db801f56603b0 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 07:56:37 +0300 Subject: More careful iterators update. --- ext/standard/array.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'ext/standard/array.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))); -- cgit v1.2.1 From cc4b7be41e2e2b9b0d7a3c8e98466b8886692e6e Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 12:24:31 +0300 Subject: Make internal function, operation on array passed by reference, to preserve foreach hash position --- ext/standard/array.c | 137 +++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 100 insertions(+), 37 deletions(-) (limited to 'ext/standard/array.c') diff --git a/ext/standard/array.c b/ext/standard/array.c index 49c6cd0789..526c9210c1 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -1877,26 +1877,49 @@ static void php_array_data_shuffle(zval *array) /* {{{ */ hash = Z_ARRVAL_P(array); n_left = n_elems; - if (hash->nNumUsed != hash->nNumOfElements) { - for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { - p = hash->arData + idx; - if (Z_TYPE(p->val) == IS_UNDEF) continue; - if (j != idx) { - hash->arData[j] = *p; + if (EXPECTED(hash->u.v.nIteratorsCount == 0)) { + if (hash->nNumUsed != hash->nNumOfElements) { + for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { + p = hash->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (j != idx) { + hash->arData[j] = *p; + } + j++; } - j++; } - } - while (--n_left) { - rnd_idx = php_rand(); - RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); - if (rnd_idx != n_left) { - temp = hash->arData[n_left]; - hash->arData[n_left] = hash->arData[rnd_idx]; - hash->arData[rnd_idx] = temp; + while (--n_left) { + rnd_idx = php_rand(); + RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); + if (rnd_idx != n_left) { + temp = hash->arData[n_left]; + hash->arData[n_left] = hash->arData[rnd_idx]; + hash->arData[rnd_idx] = temp; + } + } + } else { + if (hash->nNumUsed != hash->nNumOfElements) { + for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { + p = hash->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (j != idx) { + hash->arData[j] = *p; + zend_hash_iterators_update(hash, idx, j); + } + j++; + } + } + while (--n_left) { + rnd_idx = php_rand(); + RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); + if (rnd_idx != n_left) { + temp = hash->arData[n_left]; + hash->arData[n_left] = hash->arData[rnd_idx]; + hash->arData[rnd_idx] = temp; + zend_hash_iterators_update(hash, rnd_idx, n_left); + } } } - HANDLE_BLOCK_INTERRUPTIONS(); hash->nNumUsed = n_elems; hash->nInternalPointer = 0; @@ -2194,18 +2217,33 @@ PHP_FUNCTION(array_shift) if (Z_ARRVAL_P(stack)->u.flags & HASH_FLAG_PACKED) { uint32_t k = 0; - for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { - p = Z_ARRVAL_P(stack)->arData + idx; - if (Z_TYPE(p->val) == IS_UNDEF) continue; - if (idx != k) { - Bucket *q = Z_ARRVAL_P(stack)->arData + k; - q->h = k; - q->key = NULL; - ZVAL_COPY_VALUE(&q->val, &p->val); - ZVAL_UNDEF(&p->val); - zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + if (EXPECTED(Z_ARRVAL_P(stack)->u.v.nIteratorsCount == 0)) { + for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { + p = Z_ARRVAL_P(stack)->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (idx != k) { + Bucket *q = Z_ARRVAL_P(stack)->arData + k; + q->h = k; + q->key = NULL; + ZVAL_COPY_VALUE(&q->val, &p->val); + ZVAL_UNDEF(&p->val); + } + k++; + } + } else { + for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { + p = Z_ARRVAL_P(stack)->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (idx != k) { + Bucket *q = Z_ARRVAL_P(stack)->arData + k; + q->h = k; + q->key = NULL; + ZVAL_COPY_VALUE(&q->val, &p->val); + ZVAL_UNDEF(&p->val); + zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + } + k++; } - k++; } Z_ARRVAL_P(stack)->nNumUsed = k; Z_ARRVAL_P(stack)->nNextFreeElement = k; @@ -2258,21 +2296,46 @@ PHP_FUNCTION(array_unshift) } zend_hash_next_index_insert_new(&new_hash, &args[i]); } - ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { - if (key) { - zend_hash_add_new(&new_hash, key, value); - } else { - zend_hash_next_index_insert_new(&new_hash, value); - } - } ZEND_HASH_FOREACH_END(); + if (EXPECTED(Z_ARRVAL_P(stack)->u.v.nIteratorsCount == 0)) { + ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { + if (key) { + zend_hash_add_new(&new_hash, key, value); + } else { + zend_hash_next_index_insert_new(&new_hash, value); + } + } ZEND_HASH_FOREACH_END(); + } else { + uint32_t old_idx; + uint32_t new_idx = i; - new_hash.u.v.nIteratorsCount = Z_ARRVAL_P(stack)->u.v.nIteratorsCount; + ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { + if (key) { + zend_hash_add_new(&new_hash, key, value); + } else { + zend_hash_next_index_insert_new(&new_hash, value); + } + old_idx = (Bucket*)value - Z_ARRVAL_P(stack)->arData; + zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx); + new_idx++; + } ZEND_HASH_FOREACH_END(); + } + + /* replace HashTable data */ 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; + + Z_ARRVAL_P(stack)->u.v.flags = new_hash.u.v.flags; + Z_ARRVAL_P(stack)->nTableSize = new_hash.nTableSize; + Z_ARRVAL_P(stack)->nTableMask = new_hash.nTableMask; + Z_ARRVAL_P(stack)->nNumUsed = new_hash.nNumUsed; + Z_ARRVAL_P(stack)->nNumOfElements = new_hash.nNumOfElements; + Z_ARRVAL_P(stack)->nNextFreeElement = new_hash.nNextFreeElement; + Z_ARRVAL_P(stack)->arData = new_hash.arData; + Z_ARRVAL_P(stack)->arHash = new_hash.arHash; + Z_ARRVAL_P(stack)->pDestructor = new_hash.pDestructor; + 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))); -- cgit v1.2.1 From 08302c0d6d1cab279b9f2129df03a057baddf2ff Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 14:20:46 +0300 Subject: Make array_splice() to preserve foreach hash position --- ext/standard/array.c | 33 +++++++++++++++++++++++++++------ 1 file changed, 27 insertions(+), 6 deletions(-) (limited to 'ext/standard/array.c') diff --git a/ext/standard/array.c b/ext/standard/array.c index 526c9210c1..a7e60899dd 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -1989,7 +1989,6 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re for (pos = 0, idx = 0; pos < offset && idx < in_hash->nNumUsed; idx++) { p = in_hash->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; - pos++; /* Get entry and increase reference count */ entry = &p->val; @@ -1999,6 +1998,10 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + pos++; } /* If hash for removed entries exists, go until offset+length and copy the entries to it */ @@ -2024,10 +2027,12 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } } } else { /* otherwise just skip those entries */ - for ( ; pos < offset + length && idx < in_hash->nNumUsed; idx++) { + int pos2 = pos; + + for ( ; pos2 < offset + length && idx < in_hash->nNumUsed; idx++) { p = in_hash->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; - pos++; + pos2++; if (p->key == NULL) { zend_hash_index_del(in_hash, p->h); } else { @@ -2045,6 +2050,7 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re ZEND_HASH_FOREACH_VAL_IND(replace, entry) { if (Z_REFCOUNTED_P(entry)) Z_ADDREF_P(entry); zend_hash_next_index_insert_new(&out_hash, entry); + pos++; } ZEND_HASH_FOREACH_END(); } @@ -2058,13 +2064,28 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + pos++; } - zend_hash_internal_pointer_reset(&out_hash); - + /* replace HashTable data */ + in_hash->u.v.nIteratorsCount = 0; in_hash->pDestructor = NULL; zend_hash_destroy(in_hash); - *in_hash = out_hash; + + in_hash->u.v.flags = out_hash.u.v.flags; + in_hash->nTableSize = out_hash.nTableSize; + in_hash->nTableMask = out_hash.nTableMask; + in_hash->nNumUsed = out_hash.nNumUsed; + in_hash->nNumOfElements = out_hash.nNumOfElements; + in_hash->nNextFreeElement = out_hash.nNextFreeElement; + in_hash->arData = out_hash.arData; + in_hash->arHash = out_hash.arHash; + in_hash->pDestructor = out_hash.pDestructor; + + zend_hash_internal_pointer_reset(in_hash); } /* }}} */ -- cgit v1.2.1 From 5406f21b11e563069d64045e599693b51c444b63 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 18:08:43 +0300 Subject: Reduced alghorithms complexity --- ext/standard/array.c | 36 +++++++++++++++++++++++++++++------- 1 file changed, 29 insertions(+), 7 deletions(-) (limited to 'ext/standard/array.c') diff --git a/ext/standard/array.c b/ext/standard/array.c index a7e60899dd..f923ad9e7b 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -1898,13 +1898,18 @@ static void php_array_data_shuffle(zval *array) /* {{{ */ } } } else { + uint32_t iter_pos = zend_hash_iterators_lower_pos(hash, 0); + if (hash->nNumUsed != hash->nNumOfElements) { for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { p = hash->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; if (j != idx) { hash->arData[j] = *p; - zend_hash_iterators_update(hash, idx, j); + if (idx == iter_pos) { + zend_hash_iterators_update(hash, idx, j); + iter_pos = zend_hash_iterators_lower_pos(hash, iter_pos + 1); + } } j++; } @@ -1964,6 +1969,7 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re uint idx; Bucket *p; /* Pointer to hash bucket */ zval *entry; /* Hash entry */ + uint32_t iter_pos = zend_hash_iterators_lower_pos(in_hash, 0); /* Get number of entries in the input hash */ num_in = zend_hash_num_elements(in_hash); @@ -1998,8 +2004,11 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } - if (idx != pos) { - zend_hash_iterators_update(in_hash, idx, pos); + if (idx == iter_pos) { + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1); } pos++; } @@ -2044,6 +2053,7 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } } } + iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos); /* If there are entries to insert.. */ if (replace) { @@ -2064,8 +2074,11 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } - if (idx != pos) { - zend_hash_iterators_update(in_hash, idx, pos); + if (idx == iter_pos) { + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1); } pos++; } @@ -2252,6 +2265,8 @@ PHP_FUNCTION(array_shift) k++; } } else { + uint32_t iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), 0); + for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { p = Z_ARRVAL_P(stack)->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; @@ -2261,7 +2276,10 @@ PHP_FUNCTION(array_shift) q->key = NULL; ZVAL_COPY_VALUE(&q->val, &p->val); ZVAL_UNDEF(&p->val); - zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + if (idx == iter_pos) { + zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), iter_pos + 1); + } } k++; } @@ -2328,6 +2346,7 @@ PHP_FUNCTION(array_unshift) } else { uint32_t old_idx; uint32_t new_idx = i; + uint32_t iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), 0); ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { if (key) { @@ -2336,7 +2355,10 @@ PHP_FUNCTION(array_unshift) zend_hash_next_index_insert_new(&new_hash, value); } old_idx = (Bucket*)value - Z_ARRVAL_P(stack)->arData; - zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx); + if (old_idx == iter_pos) { + zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx); + iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), iter_pos + 1); + } new_idx++; } ZEND_HASH_FOREACH_END(); } -- cgit v1.2.1