Re: array_unique and some questions on Zend hash internals
| From: | Stig Venaas | Date: | Wed, 07 Jun 2000 21:10:35 +0000 |
| Subject: | Re: array_unique and some questions on Zend hash internals | ||
| References: | 1 2 3 4 | Groups: | php.dev |
| Request: | Send a blank email to php-dev+get-20513@lists.php.net to get a copy of this message | ||
On Mon, Jun 05, 2000 at 08:47:41AM -0500, Andrei Zmievski wrote:
> On Sun, 04 Jun 2000, Stig Venaas wrote:
> > Unless it gets too complicated and slow I will try to preserve keys and
> > compact indices (similar to array_splice, array_merge...).
>
> How would you compact indices?
I see two ways, one is to insert everything in a new hash like in splice,
or as below (as in for instance zend_hash_sort)
for ( i = 0, p = ht->pListHead; p; p = p->pListNext)
if (!p->nKeyLength)
p->h = i++;
ht->nNextFreeElement = i;
zend_hash_rehash(ht);
I think this is a little faster, especially when most elements have
keys rather than indices, but you know the code better than me.
Think perhaps it's possible to write a quicker renumbering routine by
using the hash internals directly, which is a bit nasty.
> > I think that array_pop, array_shift, array_pad and some of the other
> > functions could be faster. They use _phpi_splice which copies a lot
> > of data around. Perhaps I'll look into this later on.
>
> Originally, I wrote array_pop and array_shift using zend_hash_del() for
> removing entries. However, it had side effect in that the indices of the
> array stayed the same, which did not seem correct, e.g.:
Yes, but you could at least use del when the removed entry has a key.
Here's my new array_unique function, what do you think? I'm still using
buckets slightly, do you want me to avoid it completely? If so, is there
a better way than copying the entire hash and sorting with zend_hash_sort?
If you like it, I can add it to CVS myself. I don't see many people posting
patches, would you prefer if I submitted things some other way? BTW, I'm
still wondering where/when I should use BLOCK/UNBLOCK.
Stig
/* {{{ proto array array_unique(array input)
Removes duplicate values from array */
PHP_FUNCTION(array_unique)
{
zval **array;
HashTable *target_hash;
Bucket **arTmp, **cmpdata, **lastkept;
Bucket *p;
int i;
if (ARG_COUNT(ht) != 1 || zend_get_parameters_ex(1, &array) == FAILURE) {
WRONG_PARAM_COUNT;
}
target_hash = HASH_OF(*array);
if (!target_hash) {
php_error(E_WARNING, "Wrong datatype in array_unique() call");
RETURN_FALSE;
}
/* Copy the original array */
*return_value = **array;
zval_copy_ctor(return_value);
if (target_hash->nNumOfElements <= 1) /* Nothing to do */
return;
/* create and sort array with pointers to the target_hash buckets */
arTmp = (Bucket **) pemalloc((target_hash->nNumOfElements + 1) * sizeof(Bucket *),
target_hash->persistent);
if (!arTmp)
RETURN_FALSE;
HANDLE_BLOCK_INTERRUPTIONS(); /* Necessary, and where? */
for (i = 0, p = target_hash->pListHead; p; i++, p = p->pListNext)
arTmp[i] = p;
arTmp[i] = NULL;
qsort((void *) arTmp, i, sizeof(Bucket *), array_data_compare);
/* go through the sorted array and delete duplicates from the copy */
lastkept = arTmp;
for (cmpdata = arTmp + 1; *cmpdata; cmpdata++) {
if (array_data_compare(lastkept, cmpdata)) {
lastkept = cmpdata;
} else {
p = *cmpdata;
if (p->nKeyLength)
zend_hash_del(return_value->value.ht, p->arKey, p->nKeyLength);
else
zend_hash_index_del(return_value->value.ht, p->h);
}
}
HANDLE_UNBLOCK_INTERRUPTIONS(); /* Necessary, and where? */
pefree(arTmp, target_hash->persistent);
for ( i = 0, p = return_value->value.ht->pListHead; p; p = p->pListNext)
if (!p->nKeyLength)
p->h = i++;
return_value->value.ht->nNextFreeElement = i;
zend_hash_rehash(return_value->value.ht);
}
/* }}} */