cvs: php4 / NEWS /ext/standard array.c

andrei Sun Jun 9 22:28:32 2002 EDT Modified files: /php4 NEWS /php4/ext/standard array.c Log: Fix bug #7045: shuffle() now provides consistent distribution of values in the array. Index: php4/NEWS diff -u php4/NEWS:1.1006 php4/NEWS:1.1007 --- php4/NEWS:1.1006 Sun Jun 9 13:05:17 2002 +++ php4/NEWS Sun Jun 9 22:28:31 2002 @@ -1,6 +1,7 @@ PHP 4 NEWS ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| ?? ??? 2002, Version 4.3.0 +- Fixed shuffle() to provide equal distribution of values. (Andrei) - Added --with-mysql-sock configure option which can be used to override the unix socket location. (e.g. NFS compiles, etc.) (imajes) - Fixed is_a() to properly work on extension registered classes. (Andrei) Index: php4/ext/standard/array.c diff -u php4/ext/standard/array.c:1.163 php4/ext/standard/array.c:1.164 --- php4/ext/standard/array.c:1.163 Mon Jun 3 13:49:48 2002 +++ php4/ext/standard/array.c Sun Jun 9 22:28:32 2002 @@ -21,7 +21,7 @@ +----------------------------------------------------------------------+ */ -/* $Id: array.c,v 1.163 2002/06/03 17:49:48 edink Exp $ */ +/* $Id: array.c,v 1.164 2002/06/10 02:28:32 andrei Exp $ */ #include "php.h" #include "php_ini.h" @@ -1435,24 +1435,68 @@ /* }}} */ -static int array_data_shuffle(const void *a, const void *b TSRMLS_DC) -{ - return (php_rand(TSRMLS_C) % 2) ? 1 : -1; -} - - /* {{{ proto bool shuffle(array array_arg) Randomly shuffle the contents of an array */ PHP_FUNCTION(shuffle) { zval *array; + Bucket **elems, *temp; + HashTable *hash; + int j, n_elems, cur_elem = 0, rnd_idx, n_left; + TSRMLS_FETCH(); if (zend_parse_parameters(1 TSRMLS_CC, "a", &array) == FAILURE) { RETURN_FALSE; } - if (zend_hash_sort(Z_ARRVAL_PP(&array), (sort_func_t)php_mergesort, array_data_shuffle, 1 TSRMLS_CC) == FAILURE) { - RETURN_FALSE; - } + + n_elems = zend_hash_num_elements(Z_ARRVAL_P(array)); + if (n_elems <= 1) { + RETURN_TRUE; + } + + elems = (Bucket **)emalloc(n_elems * sizeof(Bucket *)); + hash = Z_ARRVAL_P(array); + n_left = n_elems; + + for (j = 0, temp = hash->pListHead; temp; temp = temp->pListNext) + elems[j++] = temp; + while (--n_left) { + rnd_idx = php_rand(TSRMLS_C); + RAND_RANGE(rnd_idx, cur_elem, n_left, PHP_RAND_MAX); + if (rnd_idx != cur_elem) { + temp = elems[cur_elem]; + elems[cur_elem] = elems[rnd_idx]; + elems[rnd_idx] = temp; + } + cur_elem++; + } + + HANDLE_BLOCK_INTERRUPTIONS(); + hash->pListHead = elems[0]; + hash->pListTail = NULL; + hash->pInternalPointer = hash->pListHead; + + for (j = 0; j < n_elems; j++) { + if (hash->pListTail) { + hash->pListTail->pListNext = elems[j]; + } + elems[j]->pListLast = hash->pListTail; + elems[j]->pListNext = NULL; + hash->pListTail = elems[j]; + } + temp = hash->pListHead; + j = 0; + while (temp != NULL) { + temp->nKeyLength = 0; + temp->h = j++; + temp = temp->pListNext; + } + hash->nNextFreeElement = n_elems; + zend_hash_rehash(hash); + HANDLE_UNBLOCK_INTERRUPTIONS(); + + efree(elems); + RETURN_TRUE; } /* }}} */