another balanced tree fix (vexi bug 90)

darcs-hash:20040507034933-24bed-7d26ae9d3f97a4845c31d7b6de6e9bfa74940d86.gz

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index 7d1c341..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(); }
@@ -173,9 +189,10 @@ public class BalancedTree {
         int odest = dest;
         boolean plus = true;
         int tries = 1;
+        if(dest == 0) dest=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;