Permalink
Browse files

Fix CHVM8's TreeNode not properly recursing on non-comparable keys.

  • Loading branch information...
1 parent 2ba90ed commit e9e51e24bbdd7eeaf1701935057e23362f1d7b50 @thedarkone committed Dec 3, 2012
Showing with 20 additions and 16 deletions.
  1. +20 −16 ext/org/jruby/ext/thread_safe/jsr166e/ConcurrentHashMapV8.java
@@ -837,15 +837,18 @@ else if (pp.right == p)
!(k instanceof Comparable) ||
(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
- TreeNode r = null, s = null, pl, pr;
- if (dir >= 0) {
- if ((pl = p.left) != null && h <= pl.hash)
- s = pl;
+ if (dir == 0) { // if still stuck, need to check both sides
+ TreeNode r = null, pl, pr;
+ // try to recurse on the right
+ if ((pr = p.right) != null && h >= pr.hash && (r = getTreeNode(h, k, pr)) != null) {
+ return r;
+ // try to continue iterating on the left side
+ } else if ((pl = p.left) != null && h <= pl.hash) {
+ dir = -1;
+ } else { // no matching node found
+ return null;
+ }
}
- else if ((pr = p.right) != null && h >= pr.hash)
- s = pr;
- if (s != null && (r = getTreeNode(h, k, s)) != null)
- return r;
}
}
else
@@ -901,15 +904,16 @@ else if ((e.hash & HASH_BITS) == h && k.equals(e.key)) {
!(k instanceof Comparable) ||
(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
- TreeNode r = null, s = null, pl, pr;
- if (dir >= 0) {
- if ((pl = p.left) != null && h <= pl.hash)
- s = pl;
+ if (dir == 0) { // if still stuck, need to check both sides
+ TreeNode r = null, pl, pr;
+ // try to recurse on the right
+ if ((pr = p.right) != null && h >= pr.hash && (r = getTreeNode(h, k, pr)) != null) {
+ return r;
+ // try to continue iterating on the left side
+ } else if ((pl = p.left) != null && h <= pl.hash) {
+ dir = -1;
+ }
}
- else if ((pr = p.right) != null && h >= pr.hash)
- s = pr;
- if (s != null && (r = getTreeNode(h, k, s)) != null)
- return r;
}
}
else

0 comments on commit e9e51e2

Please sign in to comment.