bugDotGNU Portable.NET - Bugs: bug #9113, bug in Generics.Hashtable.Remove()

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #9113: bug in Generics.Hashtable.Remove()

Submitter:  None
Submitted:  Wed 26 May 2004 03:32:47 PM UTC
   
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Fixed
Privacy:  Public Assigned to:  None
Open/Closed:  Closed

Tue 19 Jul 2005 01:02:04 PM UTC, comment #3: 

fixed in cvs

Deryk Robosson <drobosson>
Group Member
Thu 03 Jun 2004 09:33:40 AM UTC, comment #2: 

An example of the wrong behavior of Remove() is attached.

Here is a correct implementation of Remove() :

public bool Remove(KeyT inKey)
{
// Find an existing entry with the specified key.
if (this.capacity == 0)
{
return false;
}
int i = GetHash(inKey);
i = (int)(((uint)i) % ((uint)this.capacity));
int num = this.capacity;
while (num > 0)
{
if (!(this.table[i].HasEntry))
{
return false;
}
else if (KeyEquals(this.table[i].Key, inKey))
{
break;
}
i = (i + 1) % this.capacity;
--num;
}

// Remove entry at position i (Knuth - The Art of Computer Programming - Vol3 p527).
--this.count;
num = this.capacity;
int j, r;
while (true)
{
// R1
this.table[i].HasEntry = false;

j = i;

// R2
do
{
i = (i + 1) % this.capacity;
--num;
if (num == 0)
return true;

// R3
if (!this.table[i].HasEntry)
return true;

r = GetHash(this.table[i].Key);
r = (int)(((uint)r) % ((uint)this.capacity));
}
while (((j < r) && (r <= i)) || ((i < j) && (j < r)) || ((r <= i) && (i < j)));

// R4
this.table[j] = this.table[i];
}
}


Anonymous
Sat 29 May 2004 02:42:42 PM UTC, comment #1: 

Can I have a test case please ?.

Gopal.V <t3rmin4t0r>
Group administrator
Wed 26 May 2004 03:32:47 PM UTC, original submission:  

The method Remove() of Generics.Hashtable does not work properly. It should compactify the entries after the removed bucket.
See Knuth - The Art of Computer Programming - Vol3 p527 for the correct implementation.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #1375:  testhash.cs added by None (587B - text/plain - Example of wrong behavior of Remove())

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

 

Follow 3 latest changes.

Date Changed by Updated Field Previous Value => Replaced by
2005-07-19 drobosson StatusNone Fixed
    Open/ClosedOpen Closed
2004-06-03 None Attached File- Added testhash.cs, #1367

Back to the top

Powered by Savane 3.13-bb6a.
Corresponding source code