X-Git-Url: http://git.megacz.com/?p=org.ibex.core.git;a=blobdiff_plain;f=src%2Forg%2Fibex%2Futil%2FBalancedTree.java;h=24c474dcc840cbd372737a93816a134a6fdcd06a;hp=7d1c34117755cf6442a04c0975f5afb8103337a9;hb=fffcafc33aa4066bdf85da7a32e1a1cdb9db2d6f;hpb=dd91e0e1c03af1b7d127280b56db74827eac9478

diff --git a/src/org/ibex/util/BalancedTree.java b/src/org/ibex/util/BalancedTree.java
index 7d1c341..24c474d 100644
--- a/src/org/ibex/util/BalancedTree.java
+++ b/src/org/ibex/util/BalancedTree.java
@@ -12,9 +12,11 @@ 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 {
-
+    private static final boolean DEBUG = true;
 
     // Instance Variables ///////////////////////////////////////////////////////////////////
 
@@ -22,14 +24,19 @@ public class BalancedTree {
 
     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 +49,13 @@ public class BalancedTree {
             left[arg] = right[arg] = parent[arg] = 0;
             size[arg] = 1;
         }
+        if(DEBUG) check();
+        }
     }
 
     /** 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 +63,13 @@ public class BalancedTree {
         if (index >= treeSize()) index = treeSize() - 1;
         int arg = allocateSlot(o);
         insert(index, arg, root, 0, true, false);
+        if(DEBUG) check();
+        }
     }
 
     /** 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 +90,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,20 +115,25 @@ 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);
         left[del] = right[del] = size[del] = parent[del] = 0;
         Object ret = objects[del];
         objects[del] = null;
+        if(DEBUG) check();
         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 +143,9 @@ public class BalancedTree {
             i = next;
         } while(i != 0);
         root = 0;
+        }
+        if(DEBUG) check();
     }
-    
-    protected void finalize() { clear(); }
-
 
     // Node Data /////////////////////////////////////////////////////////////////////////
 
@@ -173,9 +192,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 +218,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 +263,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 +291,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);
@@ -258,38 +301,45 @@ public class BalancedTree {
 
         if (size[arg] != 0) throw new Error("double insertion");
 
+        if(DEBUG) check();
+
         // we are replacing an existing node
         if (replace) {
             if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
             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;
-        
+            if(DEBUG) check();
+            
         // 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 {
+            if(DEBUG) check();
             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);
@@ -333,7 +383,7 @@ public class BalancedTree {
         } 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;
@@ -341,7 +391,7 @@ public class BalancedTree {
                 }
                 
             // 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;
@@ -349,7 +399,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;
@@ -361,8 +411,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
@@ -373,21 +423,73 @@ public class BalancedTree {
         }
     }
 
+    protected void finalize() { clear(); }
+
     // Debugging ///////////////////////////////////////////////////////////////////////////
     
+    public void check() { check(false); }
+    public void check(boolean expensive) {
+        if(expensive) System.err.println("--> Running expensive balanced tree checks");
+        try {
+            if(expensive) 
+                for(int i=0;i<NUM_SLOTS;i++) 
+                    if(left[i] < 0 || right[i] < 0) throw new Error("someone inserted a negative number");
+            if(parent[root] != 0) throw new Error("parent of the root isn't 0");
+            if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
+                throw new Error("someone messed with [0]");
+            
+            int c = 0;
+            int n = leftmost(root);
+            while(n != 0) { c++; n = next(n); }
+            if(c != size[root]) throw new Error("size[] mismatch");
+            
+            if(root != 0) check(root);
+        } catch(Error e) {
+            printTree();
+            throw e;
+        }
+    }
+    
+    private void check(int node) {
+        //if(next(node) != next2(node)) throw new Error("next(" + node + ") != next2(" + node + ")");
+        //if(prev(node) != prev2(node)) throw new Error("prev(" + node + ") != prev2(" + node + ")");
+        
+        if(left[node] > 0) {
+            if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
+            check(left[node]);
+        }
+        if(right[node] > 0) {
+            if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
+            check(right[node]);
+        }
+    }
+        
     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);
         }
     }
+    
+    /*public static void main(String[] args) {
+        BalancedTree t = new BalancedTree();
+        for(int i=0;i<args.length;i++)
+            t.insertNode(i,args[i]);
+        t.printTree();
+        for(int n = t.leftmost(t.root); n != 0; n = t.next(n)) {
+            System.err.println("Next: " + n);
+        }
+        for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
+            System.err.println("Prev: " + n);
+        }        
+    }*/
 }