Fix object re-hashing
authorLinus Torvalds <torvalds@osdl.org>
Sun, 12 Feb 2006 19:24:50 +0000 (11:24 -0800)
committerJunio C Hamano <junkio@cox.net>
Sun, 12 Feb 2006 19:24:50 +0000 (11:24 -0800)
commitd7ee090d0d425606c599327c01fcbcdb60f6b090
tree4520ebefd24e683a60a39a7e841e704049937b47
parent2b796360acbdf3186ab9a5dcb84fe416eda4ffd5
Fix object re-hashing

The hashed object lookup had a subtle bug in re-hashing: it did

for (i = 0; i < count; i++)
if (objs[i]) {
.. rehash ..

where "count" was the old hash couny. Oon the face of it is obvious, since
it clearly re-hashes all the old objects.

However, it's wrong.

If the last old hash entry before re-hashing was in use (or became in use
by the re-hashing), then when re-hashing could have inserted an object
into the hash entries with idx >= count due to overflow. When we then
rehash the last old entry, that old entry might become empty, which means
that the overflow entries should be re-hashed again.

In other words, the loop has to be fixed to either traverse the whole
array, rather than just the old count.

(There's room for a slight optimization: instead of counting all the way
up, we can break when we see the first empty slot that is above the old
"count". At that point we know we don't have any collissions that we might
have to fix up any more. This patch only does the trivial fix)

[jc: with trivial fix on trivial fix]

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
object.c