Re: Re: qsort fix
| From: | Chad Cunningham | Date: | Sat, 29 May 1999 21:24:54 +0000 |
| Subject: | Re: Re: qsort fix | ||
| References: | 1 | Groups: | php.dev |
| Request: | Send a blank email to php-dev+get-6281@lists.php.net to get a copy of this message | ||
Richard Lynch wrote:
> I'm not up-to-speed on CVS yet, but...
>
> Since the only point of non-deterministic comparison would be for
> shuffle(), and since shuffle() should really be done with something linear
> rather than qsort which is O(n log n)...
>
> Wouldn't it be better to leave qsort alone and change shuffle()?...
Sounds too logical :) Below is my quick and dirty (tm) hack, works great. I'm
sure it can be done better, but it does what I need for now...
diff -brw php-devel/functions/basic_functions.c
php-3.0.8/functions/basic_functions.c
738a739,753
> static int array_data_shuffle(const void *a, const void*b) {
> return (
> /* This is just a little messy. */
> #ifdef HAVE_LRAND48
> lrand48()
> #else
> #ifdef HAVE_RANDOM
> random()
> #else
> rand()
> #endif
> #endif
> % 2) ? 1 : -1;
> }
>
757c772
< if (_php3_hash_shuffle(array->value.ht, 1) == FAILURE) {
---
> if (_php3_hash_sort(array->value.ht, array_data_shuffle,1) == FAILURE) {
diff -brw php-devel/php3_hash.c php-3.0.8/php3_hash.c
47,49d46
< #ifndef RAND_MAX
< #define RAND_MAX (1<<15)
< #endif
982,1058d978
< #ifdef HAVE_LRAND48
< #define PHP_RAND_MAX 2147483647
< #else
< #define PHP_RAND_MAX RAND_MAX
< #endif
<
< PHPAPI int _php3_hash_shuffle(HashTable *ht, int renumber)
< {
< Bucket **arTmp;
< Bucket *p, *t;
< int i, j, k, s;
<
< if (ht->nNumOfElements <= 1) { /* Doesn't require sorting */
< return SUCCESS;
< }
< arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *),ht-
>persistent);
< if (!arTmp) {
< return FAILURE;
< }
< p = ht->pListHead;
< i = 0;
< while (p) {
< arTmp[i] = p;
< p = p->pListNext;
< i++;
< }
<
< for (k=0; k<i-1; k++) {
< s = (k+1) + (int)((double)((i-1)-(k+1)+1) *
< #ifdef HAVE_LRAND48
< lrand48()
< #else
< #ifdef HAVE_RANDOM
< random()
< #else
< rand()
< #endif
< #endif
< /(PHP_RAND_MAX+1.0));
< t = arTmp[k];
< arTmp[k] = arTmp[s];
< arTmp[s] = t;
< }
<
< BLOCK_INTERRUPTIONS;
< ht->pListHead = arTmp[0];
< ht->pListTail = NULL;
< ht->pInternalPointer = ht->pListHead;
<
< for (j = 0; j < i; j++) {
< if (ht->pListTail) {
< ht->pListTail->pListNext = arTmp[j];
< }
< arTmp[j]->pListLast = ht->pListTail;
< arTmp[j]->pListNext = NULL;
< ht->pListTail = arTmp[j];
< }
< pefree(arTmp,ht->persistent);
< UNBLOCK_INTERRUPTIONS;
<
< if (renumber) {
< p = ht->pListHead;
< i=0;
< while (p != NULL) {
< if (p->arKey) {
< pefree(p->arKey,ht->persistent);
< }
< p->arKey = NULL;
< p->nKeyLength = 0;
< p->h = i++;
< p = p->pListNext;
< }
< ht->nNextFreeElement = i;
< _php3_hash_rehash(ht);
< }
< return SUCCESS;
< }
diff -brw php-devel/php3_hash.h php-3.0.8/php3_hash.h
141d140
< extern PHPAPI int _php3_hash_shuffle(HashTable *ht, int renumber);
--
Chad Cunningham
ccunning@math.ohio-state.edu
--
PHP Development Mailing List http://www.php.net/
To unsubscribe send an empty message to php-dev-unsubscribe@lists.php.net
For help: php-dev-help@lists.php.net