redblack.js icon indicating copy to clipboard operation
redblack.js copied to clipboard

tree.find: fix the issue that null key cased 100% cpu usage.

Open melochale opened this issue 10 years ago • 4 comments

If the arg key of tree.find is null, the node couldn't be responsive because of the 100% cpu usage.

melochale avatar Oct 29 '14 02:10 melochale

@melote Would tree.find enter an infinite loop? Could you provide a minimal test case to demonstrate this?

scttnlsn avatar Oct 29 '14 15:10 scttnlsn

@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.
)};

melochale avatar Oct 30 '14 05:10 melochale

@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 avatar Oct 30 '14 14:10 scttnlsn

@scttnlsn, yeah,that would be great! I will remove it.

melochale avatar Oct 31 '14 00:10 melochale