Re: [libvirt] [PATCH] util: hash: Append to hash buckets when adding new entries
On Tue, Apr 16, 2019 at 04:09:54PM +0200, Peter Krempa wrote:
In cases when the hash function for a name collides with other entry
already in the hash we prepend to the bucket. This creates a 'stack
effect' on the buckets if we then iterate through the hash. Normally
this is not a problem, but in tests we want deterministic results.
Since it does not matter where we add the entry and it's usually more
probable that a different entry will be accessed next change it to
append to the end of the bucket. Luckily we already iterate throught the
bucket once thus we can easily find the last entry and just connect the
new entry after it.
I'm not understanding how this change makes the tests any more
deterministic than before.
The determinism for hash bucket placement is already ensured by
having a non-random impl forvirHashCodeGen in
tests/virdeterministichashmock.c
This change simply reverses the order in which we iterate over values
when many keys hash to the same bucket. If this mattered for tests
then surely, this change would have to update the test suite too to
take account of the new reversed ordering ?
Regards,
Daniel
--
|: https://berrange.com -o- https://www.flickr.com/photos/dberrange :|
|: https://libvirt.org -o- https://fstop138.berrange.com :|
|: https://entangle-photo.org -o- https://www.instagram.com/dberrange :|