Problematic Map_Put() / Map_Get() about cello HOT 7 CLOSED

Yes currently the Map data structure doesn't self balance. Sorry this is an improvement that really needs to be made which I've not found time to add as I've been very busy at my main job.

The good news is that I'm actually currently in the middle of a large revamp of Cello, which includes improving all of the data structures to remove the obvious problems like these and try to make them state-of-the-art. If you can wait a few months this may be ready then, otherwise I welcome pull requests.

Thanks

from cello.

The problem is not really about balancing. It is about that binary search in the tree may fail when it should not.

from cello.

Do you have an example of it failing I could use to debug?

from cello.

I have tried to replace Map's implementation using BSD API rb_tree_*.
Even after that I still got absurd exceptions in Map_Get(), and it turned out that something was seriously wrong in String_Lt().

In my case, String_Lt() tells rb_tree_find_node() that $(String, "od") < $(String, "oed"), and that $(String, "sd") < $(String, "oed"), etc.!

After replacing the comparison in String_Lt() with strncmp() < 0 ? True : False, it went smoothly.

from cello.

Thanks for checking this out. Don't know why I tried to write my own broken implementation of comparing strings. Must have been a moment of insanity! I'll fix that and just use strncmp instead.

from cello.

It seems my naive rb_tree implementation for Map works but it does break a test case, where the order of keys are required.

from cello.

Actually I think that test case is wrong along with the implementation - and that the new string comparison function is right. I changed it in the latests commits.

from cello.