reorganized file layout (part 1: moves and renames)

[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 615db24..36d8542 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,13 +169,14 @@ 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;
@@ -223,13 +224,11 @@ public class BalancedTree {
         int c = left[d];
         if (d <= 0) throw new Error("rotation error");
         left[d] = b;
-        if(size[b] <= 3) // b is now a leaf
-            right[b] = -d;
-        else
-            right[b] = c;
+        right[b] = c <= 0 ? -d : 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;
@@ -333,7 +332,6 @@ 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;
@@ -341,7 +339,6 @@ 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];