X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fibex%2Futil%2FBalancedTree.java;h=dd993a0dc5e8984003da3e256b66c6c45a36c145;hb=8a6e58b0ea6c595a9bc89b72febf108ba5a66725;hp=1c42ef1643b1842da5bfd6abc8c572f874bc4ed3;hpb=2bfc4055cd215be961a882cab0256b038350f61a;p=org.ibex.core.git

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index 1c42ef1..dd993a0 100644
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -12,24 +12,29 @@ package org.ibex.util;
 // FEATURE: private void subset() { }
 // FEATURE: grow if we run out of slots
 
+// FEATURE: Add the cached_index stuff back in 
+
 /** a weight-balanced tree with fake leaves */
 public class BalancedTree {
-
-
     // Instance Variables ///////////////////////////////////////////////////////////////////
 
     private int root = 0;                         ///< the slot of the root element
 
     private int cached_index = -1;
     private int cached_slot = -1;
-
+    
     // 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,10 +138,8 @@ public class BalancedTree {
             i = next;
         } while(i != 0);
         root = 0;
+        }
     }
-    
-    protected void finalize() { clear(); }
-
 
     // Node Data /////////////////////////////////////////////////////////////////////////
 
@@ -173,9 +186,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;
@@ -198,13 +212,35 @@ public class BalancedTree {
 
     // Helpers /////////////////////////////////////////////////////////////////////////
 
+    // FEATURE: These might be faster if they aren't recursive
     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
-    private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
-    private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
     private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
     private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
 
+    private int next(int node) {
+        if(right[node] > 0) {
+            node = right[node];
+            while(left[node] > 0) node = left[node];
+            return node;
+        } else {
+            int p = parent[node];
+            while(right[p] == node) { node = p; p = parent[node]; };
+            return p;
+        }
+    }
+    
+    private int prev(int node) {
+        if(left[node] > 0) {
+            node = left[node];
+            while(right[node] > 0) node = right[node];
+            return node;
+        } else {
+            int p = parent[node];
+            while(left[p] == node) { node = p; p = parent[node]; }
+            return p;
+        }
+    }
 
     // Rotation and Balancing /////////////////////////////////////////////////////////////
 
@@ -221,19 +257,20 @@ public class BalancedTree {
         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
         int d = right[b];
         int c = left[d];
-        if (d <= 0) throw new Error("rotation error");
+        if (d == 0) throw new Error("rotation error");
         left[d] = b;
-        right[b] = c <= 0 ? -d : c;
+        right[b] = c;
+        
         parent[b] = d;
         parent[d] = p;
-        if(c > 0) parent[c] = b;
+        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;
         else throw new Error("rotate called with invalid parent");
         size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
-        size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
+        size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);        
     }
 
     private void balance(int slot, int p) {
@@ -248,8 +285,8 @@ public class BalancedTree {
     // Insert /////////////////////////////////////////////////////////////////////////
 
     private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
-        int diff = slot <= 0 ? 0 : index - sizeof(left[slot]);
-        if (slot > 0 && diff != 0) {
+        int diff = slot == 0 ? 0 : index - sizeof(left[slot]);
+        if (slot != 0 && diff != 0) {
             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
             else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
             balance(slot, p);
@@ -264,32 +301,35 @@ public class BalancedTree {
             if (p == 0)                 root = arg;
             else if (left[p] == slot)   left[p] = arg;
             else if (right[p] == slot)  right[p] = arg;
+            else throw new Error("should never happen");
             left[arg] = left[slot];
             right[arg] = right[slot];
             size[arg] = size[slot];
             parent[arg] = parent[slot];
-            if(left[slot] > 0) parent[left[slot]] = arg;
-            if(right[slot] > 0) parent[right[slot]] = arg;
+            if(left[slot] != 0) parent[left[slot]] = arg;
+            if(right[slot] != 0) parent[right[slot]] = arg;
             objects[slot] = null;
             left[slot] = right[slot] = size[slot] = parent[slot] = 0;
-        
+            
         // we become the child of a former leaf
-        } else if (slot <= 0) {
+        } else if (slot == 0) {
             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
+            // FEATURE: Might be doing too much work here
             left[arg] = slot;
-            left[p] = arg;
-            right[arg] = -1 * p;
+            right[arg] = 0;
             parent[arg] = p;
+            left[p] = arg;
             balance(arg, p);
 
         // we take the place of a preexisting node
         } else {
             left[arg] = left[slot];   // steal slot's left subtree
-            left[slot] = -1 * arg;
+            left[slot] = 0;
             right[arg] = slot;        // make slot our right subtree
             parent[arg] = parent[slot];
             parent[slot] = arg;
+            if(left[arg] != 0) parent[left[arg]] = arg;
             if (slot == root) {
                 root = arg;
                 balance(slot, arg);
@@ -331,15 +371,17 @@ public class BalancedTree {
 
         // we found the node to delete
         } else {
+
             // fast path: it has no children
-            if (left[slot] <= 0 && right[slot] <= 0) {
+            if (left[slot] == 0 && right[slot] == 0) {
                 if (p == 0) root = 0;
                 else {
                     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) {
+            } else if (left[slot] == 0) {
                 if (p == 0) root = right[slot];
                 else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
                 parent[right[slot]] = p;
@@ -347,7 +389,7 @@ public class BalancedTree {
                 balance(right[slot], p);
 
             // fast path; it has no right child, so we replace it with its left child
-            } else if (right[slot] <= 0) {
+            } else if (right[slot] == 0) {
                 if (p == 0) root = left[slot];
                 else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
                 parent[left[slot]] = p;
@@ -359,8 +401,8 @@ public class BalancedTree {
                 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
                 left[left_childs_rightmost] = left[slot];
                 right[left_childs_rightmost] = right[slot];
-                if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
-                if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
+                if(left[slot] != 0) parent[left[slot]] = left_childs_rightmost;
+                if(right[slot] != 0) parent[right[slot]] = left_childs_rightmost;
                 parent[left_childs_rightmost] = parent[slot];
                 if (p == 0) root = left_childs_rightmost;
                 else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
@@ -371,19 +413,19 @@ public class BalancedTree {
         }
     }
 
-    // Debugging ///////////////////////////////////////////////////////////////////////////
-    
+    protected void finalize() { clear(); }
+
     public void printTree() {
         if(root == 0) System.err.println("Tree is empty");
         else printTree(root,0,false);
     }
+    
     private void printTree(int node,int indent,boolean l) {
         for(int i=0;i<indent;i++) System.err.print("   ");
-        if(node < 0) System.err.println((l?"Prev: " : "Next: ") + -node);
-        else if(node == 0)  System.err.println(l ? "Start" : "End");
+        if(node == 0) System.err.println("None");
         else {
             System.err.print("" + node + ": " + objects[node]);
-            System.err.println(" Parent: " + parent[node]);
+            System.err.println(" Parent: " + parent[node] + " Size: " + size[node]);
             printTree(left[node],indent+1,true);
             printTree(right[node],indent+1,false);
         }