reorganized file layout (part 2: edits)

[org.ibex.core.git] / src / org / ibex / util / BalancedTree.java

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index 36d8542..615db24 100644 (file)
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -27,7 +27,7 @@ public class BalancedTree {
 
     /** the number of elements in the tree */
     public final int treeSize() { return root == 0 ? 0 : size[root]; }
-    
+
     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
     public final synchronized void insertNode(int index, Object o) {
         if(o == null) throw new Error("can't insert nulls in the balanced tree");
@@ -169,14 +169,13 @@ public class BalancedTree {
         // collisions when a single Object is inserted into multiple
         // trees
         int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
-        if (dest == 0) dest = 1;
         Object search = alloc ? null : o;
         int odest = dest;
         boolean plus = true;
         int tries = 1;
         while (objects[dest] != search || !(alloc || root(dest) == root)) {
+            if (dest == 0) dest++;
             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
-            if (dest == 0) dest=1;
             if (plus) tries++;
             plus = !plus;
             // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
@@ -224,11 +223,13 @@ public class BalancedTree {
         int c = left[d];
         if (d <= 0) throw new Error("rotation error");
         left[d] = b;
-        right[b] = c <= 0 ? -d : c;
+        if(size[b] <= 3) // b is now a leaf
+            right[b] = -d;
+        else
+            right[b] = c;
         parent[b] = d;
         parent[d] = p;
         if(c > 0) parent[c] = b;
-        
         if (p == 0)              root = d;
         else if (left[p] == b)   left[p] = d;
         else if (right[p] == b)  right[p] = d;
@@ -332,6 +333,7 @@ public class BalancedTree {
 
         // we found the node to delete
         } else {
+
             // fast path: it has no children
             if (left[slot] <= 0 && right[slot] <= 0) {
                 if (p == 0) root = 0;
@@ -339,6 +341,7 @@ public class BalancedTree {
                     int[] side = left[p] == slot ? left : right;
                     side[p] = side[slot];      // fix parent's pointer
                 }
+                
             // fast path: it has no left child, so we replace it with its right child
             } else if (left[slot] <= 0) {
                 if (p == 0) root = right[slot];