Re: Fix object re-hashing

From: Linus Torvalds <torvalds@osdl.org>
Date: Feb 12, 2006, 19:10 UTC
Message-ID: <Pine.LNX.4.64.0602121101040.3691@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0602121037460.3691@g5.osdl.org>

On Sun, 12 Feb 2006, Linus Torvalds wrote:

Show 11 quoted lines

> 
>  - the "overflow of the overflow": when the linear probing itself 
>    overflows the size of the hash queue, it will "change direction" by 
>    overflowing back to index zero.
> 
>    Happily, the re-hashing does not need to care about this case, because 
>    the new hash is bigger: the rule we have when doing the re-hashing is 
>    that as we re-hash, the "i" entries we have already re-hashed are all 
>    valid in the new hash, so even if overflow occurs, it will occur the 
>    right way (and if it overflows all the way past the current "i", we'll 
>    re-hash the already re-hashed entry anyway).

Btw, this is only always true if the new hash is at least twice the size of the old hash, I think. Otherwise a re-hash can fill up the new entries and overflow entirely before we've actually even re-hashed all the old entries, and then we'd need to re-hash even the overflowed entries (which are now below "i").

If the new size is at least twice the old size, the "upper area" cannot overflow completely (there has to be empty room), and we cannot be in the situation that we need to move even the overflowed entries when we remove an old hash entry.

Anyway, if all this makes you nervous, the conceptually much simpler way to do the re-sizing is to not do the in-place re-hashing. Instead of doing the xrealloc(), just do a "xmalloc()" of the new area, do the re-hashing (which now _must_ re-hash in just the "0..oldcount-1" old area) into the new area, and then free the old area after rehashing.

That would make things more obviously correct, and perhaps simpler.

Johannes, do you want to try that?

Btw, as it currently stands, I worry a tiny tiny bit about the

	obj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs)

thing, because I think that second "32" needs to be a "64" to be really safe (ie guarantee that the new obj_allocs value is always at least twice the old one).

Anyway, I'm pretty sure people smarter than me have already codified exactly what needs to be done for a in-place rehash of a linear probe hash overflow algorithm. This must all be in some "hashing 101" book. I had to think it through from first principles rather than "knowing" what the right answer was (which probably means that I slept through some fundamental algorithms class in University ;)

		Linus