HashMap and LinkMap Bug

eastbear Joined: 05/23/07 Posts: 2

Posted: 07/15/07 22:16:53 Modified: 07/15/07 22: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
Armin Joined: 08/11/07 Posts: 1	Posted: 08/11/07 07:00:27 -- Modified: 08/11/07 07: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);
kris Joined: 03/27/04 Posts: 581	Posted: 08/11/07 14:23:05 thanks; will take a look at this next week when I get back
baxissimo Joined: 10/23/06 Posts: 24	Posted: 09/04/07 04: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.
schveiguy Joined: 08/02/07 Posts: 128	Posted: 09/04/07 10: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
schveiguy Joined: 08/02/07 Posts: 128	Posted: 09/04/07 10:17:58 Ticket 611: http://www.dsource.org/projects/tango/ticket/611
kris Joined: 03/27/04 Posts: 581	Posted: 09/04/07 10:36:40 Thank you, and fixed in SVN head recently :)