[libvirt] [PATCH] util: hash: Append to hash buckets when adding new entries

[Peter Krempa]

On Tue, Apr 16, 2019 at 15:17:31 +0100, Daniel Berrange wrote:
> 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 ?

If you have a hash collision when adding into the hash and then use
virHashForeach the items are formatted in opposite order.

Thus if you use this to e.g. store things parsed from XML and then
format it back, every single iteration reverses the order. This is not a
problem per-se since we can use a different output file, but it's
inconvenient since we can't use the same output file.

Currently there aren't any collisions which would cause problems, but I
have one on my private branch.

Given that this change is rather simple I figured we could just stop
inverting them.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20190416/d2b17851/attachment-0001.sig>