Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

HashMap and LinkMap Bug

Moderators: kris

Posted: 07/16/07 02:16:53 Modified: 07/16/07 02:34:57

I have found a bug in tango.util.collection.HashMap? and tango.util.collection.LinkMap?,here is the test code:

program 1 :

import  tango.util.collection.HashMap;
import  tango.util.collection.LinkMap;
import  tango.io.Stdout;
import	tango.math.Random;
import  tango.util.time.Clock;
import  tango.io.digest.Md5;
import  Integer = tango.text.convert.Integer;

int main()
{
        Stdout("-- start ---");
	HashMap!(char[],Person) hmap = new HashMap!(char[],Person);
	LinkMap!(char[],Person) lmap = new LinkMap!(char[],Person);

	Person p1 = new Person(Util.generateUUID());
	Person p2 = new Person(Util.generateUUID());

	hmap.add(p1.id,p1);
	lmap.add(p2.id,p2);
  

	Stdout("\n-- end ---");

	return 0;
}

class Person
{
	char[] id;

	this(char[] id)
	{
		this.id = id;
	}
}

class Util {
	static Md5 md5;
	static Random rand;

	static this() 
	{
		md5 = new Md5();
	    rand = new Random();
	}

	static char[] generateUUID()
	{	
		char[] seed = Integer.toUtf8(Clock.now);
        
		for(int i=0; i<5; i++)
		{
			seed ~= Integer.toUtf8(rand.next());
		}

		md5.update(cast(ubyte[]) seed);
        return md5.hexDigest;
	}
}

compile the program 1,it will work well,output is --- start --- --- end ---

program 2 :

import  tango.util.collection.HashMap;
import  tango.util.collection.LinkMap;
import  tango.io.Stdout;
import	tango.math.Random;
import  tango.util.time.Clock;
import  tango.io.digest.Md5;
import  Integer = tango.text.convert.Integer;

int main()
{
	Stdout("-- start ---");
	HashMap!(char[],Person) hmap = new HashMap!(char[],Person);
	LinkMap!(char[],Person) lmap = new LinkMap!(char[],Person);

	Person p1 = new Person(Util.generateUUID());
	Person p2 = new Person(Util.generateUUID());

	hmap.add(p1.id,p1);
	lmap.add(p2.id,p2);
   
    
	for(int i=0;i<30;i++)
	{
		Person p = new Person(Util.generateUUID());
		Stdout.formatln("--- add a new person id {0} , i is {1} ---",p.id,i);
		hmap.add(p.id,p);
	}

	Stdout("\n-- end ---");

	return 0;
}

class Person
{
	char[] id;

	this(char[] id)
	{
		this.id = id;
	}
}

class Util {
	static Md5 md5;
	static Random rand;

	static this() 
	{
		md5 = new Md5();
	    rand = new Random();
	}

	static char[] generateUUID()
	{	
		char[] seed = Integer.toUtf8(Clock.now);
        
		for(int i=0; i<5; i++)
		{
			seed ~= Integer.toUtf8(rand.next());
		}

		md5.update(cast(ubyte[]) seed);
        return md5.hexDigest;
	}
}

compile program 2 and run it, it will paused at " hmap.add(p.id,p); " in for loop, you can find the point in Stdout contents,and the same time the cpu's rate is very high, almost 100%, the difference with program 1 is that add more elements into map instance, I test that in Windows and linux,all occured this problem, now I don't understand the implemetation of HashMap? and linkMap,so hope the authors can deal this program,thank you!

Author Message

Posted: 08/11/07 11:00:27 -- Modified: 08/11/07 11:02:04 by
Armin

I have the same behaviour (programm stands and processor load is at 100%) with the following code (last line):

LinkMap!(char[], int) nodes = new LinkMap!(char[], int)();
nodes.add("test1", 1);
nodes.add("test2", 2);
nodes.add("test3", 3);

Posted: 08/11/07 18:23:05

thanks; will take a look at this next week when I get back

Posted: 09/04/07 08:24:32

Armin wrote:

I have the same behaviour (programm stands and processor load is at 100%) with the following code (last line):

LinkMap!(char[], int) nodes = new LinkMap!(char[], int)();
nodes.add("test1", 1);
nodes.add("test2", 2);
nodes.add("test3", 3);

Just curious, what happens if you .dup the string literals when you add? That's often the problem when anything involving foo[] doesn't work as you expect in D. Unless Tango's map is doing something special to handle char[], it's going to just copy the pointer to the string passed in. Just one of the joys of built-in arrays that don't /quite/ act like value types.

Posted: 09/04/07 14:08:27

Here is the problem. It is in tango/util/collection/impl/LLPair.d:

        public final LLPair findKey(K key)
        {
                for (auto p=this; p; p = cast(LLPair)cast(void*)next_)
                {
                     if (p.key() == key)
                         return p;
                }
                return null;
        }

Note in the for loop, the incremental statement continues to use next_ instead of p.next_. This continues to be non-null, which makes the loop infinite.

The loop should be:

                for (auto p=this; p; p = cast(LLPair)cast(void*)p.next_)

In fact, all loops in LLPair.d have this problem.

I'll file a ticket.

BTW, why the double cast? Couldn't you just cast to LLPair? i.e.:

                for (auto p=this; p; p = cast(LLPair)p.next_)

-Steve

Posted: 09/04/07 14:17:58

Ticket 611: http://www.dsource.org/projects/tango/ticket/611

Posted: 09/04/07 14:36:40

Thank you, and fixed in SVN head recently :)