Mercury Bugs - mercury
View Issue Details
0000068mercuryBugpublic2008-07-14 10:442009-03-26 17:33
Assigned Towangp 
PlatformOSOS Version
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? vht_delete.m (1,341) 2008-07-14 10:44
? ht_delete.m (1,564) 2008-08-07 15:57

2008-08-07 15:57   
Non-version hash tables, i.e. in library/hash_table.m, exhibit the same behaviour.
I'll add a test case for them too.
2008-08-07 16:23   
The bug can be reproduced with just the following keys:

2008-08-07 16:38   
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.
2008-08-07 16:43   
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.
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?

2008-08-07 16:58   
Let's just switch to separate chaining. Deleting is important.
2008-08-07 17:07   
In that case, yes.

Issue History
2008-07-14 10:44wangpNew Issue
2008-07-14 10:44wangpFile Added: vht_delete.m
2008-08-07 15:57juliensfNote Added: 0000118
2008-08-07 15:57juliensfFile Added: ht_delete.m
2008-08-07 15:58juliensfStatusnew => confirmed
2008-08-07 16:23juliensfNote Added: 0000119
2008-08-07 16:38wangpNote Added: 0000120
2008-08-07 16:43juliensfNote Added: 0000121
2008-08-07 16:52juliensfNote Added: 0000122
2008-08-07 16:52juliensfNote Edited: 0000122
2008-08-07 16:58wangpNote Added: 0000123
2008-08-07 17:07juliensfNote Added: 0000124
2009-03-26 17:33wangpStatusconfirmed => resolved
2009-03-26 17:33wangpResolutionopen => fixed
2009-03-26 17:33wangpAssigned To => wangp