2019-08-21 13:39 AEST

View Issue Details Jump to Notes ]
IDProjectCategoryView StatusLast Update
0000068mercuryBugpublic2009-03-26 17:33
Reporterwangp 
Assigned Towangp 
PrioritynormalSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
Product Version 
Target VersionFixed in Version 
Summary0000068: version_hash_table.delete is buggy
Descriptionversion_hash_table.delete doesn't always delete the element. See the test case.
TagsNo tags attached.
Attached Files

-Relationships
+Relationships

-Notes

~0000118

juliensf (administrator)

Non-version hash tables, i.e. in library/hash_table.m, exhibit the same behaviour.
I'll add a test case for them too.

~0000119

juliensf (administrator)

The bug can be reproduced with just the following keys:

"abandoned",
"abase",
"abases"

~0000120

wangp (developer)

I think the problem is this:

    find_slot(HT, K) looks up key K in hash table HT and
    returns the index for the entry K in H. This is either the
    first free slot identified (K is not in the table, but here
    is where it would go) or the slot for K (K is in the table
    and this is its slot).

    Whether or not K is actually in the table can be decided
    by checking to see whether its bit in the bitmap is set
    or clear.

That's fine if keys never get deleted. But say two keys K1, K2 both
want to go into slot S1. K1 gets there first, so K2 must reprobe and
go into slot S2. Delete K1 so slot S1 becomes free. If you try to
search for K2, it won't be found since S1 is free so it won't bother
to look in S2.

~0000121

juliensf (administrator)

That's what I had concluded as well - I was just waiting for a workspace with deep tracing
in the library directory to compile in order to confirm it. For this sort of hash table the
deletion algorithm needs to traverse the entire array until it finds the key it is deleting
or until it get backs to where it starts.

~0000122

juliensf (administrator)

Last edited: 2008-08-07 16:52

Actually, supporting deletion at all would mean that you could insert duplicate keys
into the table without it being detected - maybe we should just not support deletion?

~0000123

wangp (developer)

Let's just switch to separate chaining. Deleting is important.

~0000124

juliensf (administrator)

In that case, yes.
+Notes

-Issue History
Date Modified Username Field Change
2008-07-14 10:44 wangp New Issue
2008-07-14 10:44 wangp File Added: vht_delete.m
2008-08-07 15:57 juliensf Note Added: 0000118
2008-08-07 15:57 juliensf File Added: ht_delete.m
2008-08-07 15:58 juliensf Status new => confirmed
2008-08-07 16:23 juliensf Note Added: 0000119
2008-08-07 16:38 wangp Note Added: 0000120
2008-08-07 16:43 juliensf Note Added: 0000121
2008-08-07 16:52 juliensf Note Added: 0000122
2008-08-07 16:52 juliensf Note Edited: 0000122
2008-08-07 16:58 wangp Note Added: 0000123
2008-08-07 17:07 juliensf Note Added: 0000124
2009-03-26 17:33 wangp Status confirmed => resolved
2009-03-26 17:33 wangp Resolution open => fixed
2009-03-26 17:33 wangp Assigned To => wangp
+Issue History