redblack.js
redblack.js copied to clipboard
tree.find: fix the issue that null key cased 100% cpu usage.
If the arg key of tree.find is null, the node couldn't be responsive because of the 100% cpu usage.
@melote Would tree.find
enter an infinite loop? Could you provide a minimal test case to demonstrate this?
@scttnlsn OK,this is a mocha test case, I don't know whether tree.find enter an infinite loop, but I guest so, I got this issue in my project. anyway, thanks for your nice redblack.O(∩_∩)O
it("should return null if key is null." ,function() {
var tree = redblack.tree();
tree.insert('foo', 'bar');
var node = tree.get(null);
assert.equal(null, node); //freeze here.
)};
@melote Ahh, I see. Yeah, looks like there's an infinite loop in that case. Perhaps we should also prevent null
keys from being inserted. Could you also remove the comment about 100% CPU usage or change it to something about infinite looping? Then I'll merge this in.
Thanks!
@scttnlsn, yeah,that would be great! I will remove it.