| View Issue Details [ Jump to Notes ] | [ Issue History ] [ Print ] | ||||||||
| ID | Project | Category | View Status | Date Submitted | Last Update | ||||
|---|---|---|---|---|---|---|---|---|---|
| 0000068 | mercury | Bug | public | 2008-07-14 10:44 | 2009-03-26 17:33 | ||||
| Reporter | wangp | ||||||||
| Assigned To | wangp | ||||||||
| Priority | normal | Severity | minor | Reproducibility | always | ||||
| Status | resolved | Resolution | fixed | ||||||
| Product Version | |||||||||
| Target Version | Fixed in Version | ||||||||
| Summary | 0000068: version_hash_table.delete is buggy | ||||||||
| Description | version_hash_table.delete doesn't always delete the element. See the test case. | ||||||||
| Tags | No tags attached. | ||||||||
| Attached Files |
| ||||||||
 Relationships |
|
 Relationships |
| Notes |
|
|
juliensf (administrator) 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. |
|
juliensf (administrator) 2008-08-07 16:23 |
The bug can be reproduced with just the following keys: "abandoned", "abase", "abases" |
|
wangp (developer) 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. |
|
juliensf (administrator) 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. |
|
juliensf (administrator) 2008-08-07 16:52 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? |
|
wangp (developer) 2008-08-07 16:58 |
Let's just switch to separate chaining. Deleting is important. |
|
juliensf (administrator) 2008-08-07 17:07 |
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 |