js_bintrees icon indicating copy to clipboard operation
js_bintrees copied to clipboard

Infinite loop when inserting Array into RBTree

Open nk327 opened this issue 7 years ago • 2 comments

Somewhat of an edge case, but can lead to a bad state in applications using this library -- hanging and high CPU usage.

Repro case:

let rbtree = new RBTree(function(a, b) { return a.value - b.value; });
rbtree.insert( [ ] );
rbtree.insert( [ ] );  // <-- infinite loop

This works ok with BinTree though.

nk327 avatar Apr 14 '17 17:04 nk327

Found in package version 1.0.1

nk327 avatar Apr 14 '17 17:04 nk327

I can confirm this bug is still present in v1.0.2. The obvious workaround is to create a child class of RBTree and override the insert method with a check Array.isArray(item) == true and abort.

Are there any plans/suggestions for an official fix?

Ekliptor avatar Sep 04 '17 14:09 Ekliptor