another balanced tree fix (vexi bug 90)

[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..82226c2 100644 (file)
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -26,10 +26,15 @@ public class BalancedTree {
     // Public API //////////////////////////////////////////////////////////////////////////
 
     /** the number of elements in the tree */
-    public final int treeSize() { return root == 0 ? 0 : size[root]; }
-    
+    public final int treeSize() {
+        synchronized(BalancedTree.class) {
+            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) {
+    public final void insertNode(int index, Object o) {
+        synchronized(BalancedTree.class) {
         if(o == null) throw new Error("can't insert nulls in the balanced tree");
         cached_slot = cached_index = -1;
         if (index < 0) index = 0;
@@ -42,10 +47,12 @@ public class BalancedTree {
             left[arg] = right[arg] = parent[arg] = 0;
             size[arg] = 1;
         }
+        }
     }
 
     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
-    public final synchronized void replaceNode(int index, Object o) {
+    public final void replaceNode(int index, Object o) {
+        synchronized(BalancedTree.class) {
         if(o == null) throw new Error("can't insert nulls in the balanced tree");
         cached_slot = cached_index = -1;
         if(root == 0) throw new Error("called replaceNode() on an empty tree");
@@ -53,10 +60,12 @@ public class BalancedTree {
         if (index >= treeSize()) index = treeSize() - 1;
         int arg = allocateSlot(o);
         insert(index, arg, root, 0, true, false);
+        }
     }
 
     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
-    public final synchronized int indexNode(Object o) { 
+    public final int indexNode(Object o) { 
+        synchronized(BalancedTree.class) {
         if(o == null) return -1;
         if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
 
@@ -77,10 +86,12 @@ public class BalancedTree {
             index++;
         }
         return index;
+        }
     }
 
     /** returns the object at index; runs in O(log n) time unless cache hit */
-    public final synchronized Object getNode(int index) {
+    public final Object getNode(int index) {
+        synchronized(BalancedTree.class) {
         if (index == cached_index) return objects[cached_slot];
 
         if (cached_index != -1) {
@@ -100,10 +111,12 @@ public class BalancedTree {
         return objects[cached_slot];
         */
         return objects[get(index, root)];
+        }
     }
 
     /** deletes the object at index, returning the deleted object */
-    public final synchronized Object deleteNode(int index) {
+    public final Object deleteNode(int index) {
+        synchronized(BalancedTree.class) {
         cached_slot = cached_index = -1;
         // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
         int del = delete(index, root, 0);
@@ -111,9 +124,11 @@ public class BalancedTree {
         Object ret = objects[del];
         objects[del] = null;
         return ret;
+        }
     }
     
-    public final synchronized void clear() {
+    public final void clear() {
+        synchronized(BalancedTree.class) {
         if(root == 0) return;
         int i = leftmost(root);
         do {
@@ -123,6 +138,7 @@ public class BalancedTree {
             i = next;
         } while(i != 0);
         root = 0;
+        }
     }
     
     protected void finalize() { clear(); }
@@ -169,11 +185,11 @@ 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;
+        if(dest == 0) dest=1;
         while (objects[dest] != search || !(alloc || root(dest) == root)) {
             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
             if (dest == 0) dest=1;
@@ -225,10 +241,10 @@ public class BalancedTree {
         if (d <= 0) throw new Error("rotation error");
         left[d] = b;
         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;
@@ -332,6 +348,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 +356,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];