src/org/ibex/util/BalancedTree.java

   1 // Copyright (C) 2003 Adam Megacz <adam@ibex.org> all rights reserved.
   2 //
   3 // You may modify, copy, and redistribute this code under the terms of
   4 // the GNU Library Public License version 2.1, with the exception of
   5 // the portion of clause 6a after the semicolon (aka the "obnoxious
   6 // relink clause")
   7
   8 package org.ibex.util;
   9
  10 // FEATURE: private void intersection() { }
  11 // FEATURE: private void union() { }
  12 // FEATURE: private void subset() { }
  13 // FEATURE: grow if we run out of slots
  14
  15 // FEATURE: Add the cached_index stuff back in
  16
  17 /** a weight-balanced tree with fake leaves */
  18 public class BalancedTree {
  19     private static final boolean DEBUG = true;
  20
  21     // Instance Variables ///////////////////////////////////////////////////////////////////
  22
  23     private int root = 0;                         ///< the slot of the root element
  24
  25     private int cached_index = -1;
  26     private int cached_slot = -1;
  27
  28     private FinalizationHelper fh;
  29
  30     // Public API //////////////////////////////////////////////////////////////////////////
  31
  32     /** the number of elements in the tree */
  33     public final int treeSize() {
  34         synchronized(BalancedTree.class) {
  35             return root == 0 ? 0 : size[root];
  36         }
  37     }
  38
  39     /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
  40     public final void insertNode(int index, Object o) {
  41         synchronized(BalancedTree.class) {
  42         if(o == null) throw new Error("can't insert nulls in the balanced tree");
  43         cached_slot = cached_index = -1;
  44         if (index < 0) index = 0;
  45         if (index > treeSize()) index = treeSize();
  46         int arg = allocateSlot(o);
  47         if (root != 0) {
  48             insert(index, arg, root, 0, false, false);
  49         } else {
  50             if(fh == null) fh = new FinalizationHelper(this);
  51             root = arg;
  52             left[arg] = right[arg] = parent[arg] = 0;
  53             size[arg] = 1;
  54         }
  55         if(DEBUG) check();
  56         }
  57     }
  58
  59     /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
  60     public final void replaceNode(int index, Object o) {
  61         synchronized(BalancedTree.class) {
  62         if(o == null) throw new Error("can't insert nulls in the balanced tree");
  63         cached_slot = cached_index = -1;
  64         if(root == 0) throw new Error("called replaceNode() on an empty tree");
  65         if (index < 0) index = 0;
  66         if (index >= treeSize()) index = treeSize() - 1;
  67         int arg = allocateSlot(o);
  68         insert(index, arg, root, 0, true, false);
  69         if(DEBUG) check();
  70         }
  71     }
  72
  73     /** returns the index of o; runs in O((log n)^2) time unless cache hit */
  74     public final int indexNode(Object o) {
  75         synchronized(BalancedTree.class) {
  76         if(o == null) return -1;
  77         if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;
  78
  79         int slot = getSlot(o);
  80         if(slot == -1) return -1;
  81
  82         int index = 0;
  83         while(true) {
  84             // everything to the left is before us so add that to the index
  85             index += sizeof(left[slot]);
  86             // we are before anything on the right
  87             while(left[parent[slot]] == slot) slot = parent[slot];
  88             // we end of the first node who isn't on the left, go to the node that has as its child
  89             slot = parent[slot];
  90             // if we just processed the root we're done
  91             if(slot == 0) break;
  92             // count the node we're currently on towards the index
  93             index++;
  94         }
  95         return index;
  96         }
  97     }
  98
  99     /** returns the object at index; runs in O(log n) time unless cache hit */
 100     public final Object getNode(int index) {
 101         synchronized(BalancedTree.class) {
 102         if (index == cached_index) return objects[cached_slot];
 103
 104         if (cached_index != -1) {
 105             int distance = Math.abs(index - cached_index);
 106             // if the in-order distance between the cached node and the
 107             // target node is less than log(n), it's probably faster to
 108             // search directly.
 109             if ((distance < 16) && ((2 << distance) < treeSize())) {
 110                 while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
 111                 while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
 112                 return objects[cached_slot];
 113             }
 114         }
 115         /*
 116         cached_index = index;
 117         cached_slot = get(index, root);
 118         return objects[cached_slot];
 119         */
 120         return objects[get(index, root)];
 121         }
 122     }
 123
 124     /** deletes the object at index, returning the deleted object */
 125     public final Object deleteNode(int index) {
 126         synchronized(BalancedTree.class) {
 127         cached_slot = cached_index = -1;
 128         // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
 129         int del = delete(index, root, 0);
 130         left[del] = right[del] = size[del] = parent[del] = 0;
 131         Object ret = objects[del];
 132         objects[del] = null;
 133         if(DEBUG) check();
 134         return ret;
 135         }
 136     }
 137
 138     public final void clear() {
 139         synchronized(BalancedTree.class) {
 140         if(root == 0) return;
 141         int i = leftmost(root);
 142         do {
 143             int next = next(i);
 144             objects[i] = null;
 145             left[i] = right[i] = size[i] = parent[i] = 0;
 146             i = next;
 147         } while(i != 0);
 148         root = 0;
 149         }
 150         if(DEBUG) check();
 151     }
 152
 153     // Node Data /////////////////////////////////////////////////////////////////////////
 154
 155     private final static int NUM_SLOTS = 64 * 1024;
 156     // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;
 157
 158     /**
 159      * Every object inserted into *any* tree gets a "slot" in this
 160      * array.  The slot is determined by hashcode modulo the length of
 161      * the array, with quadradic probing to resolve collisions.  NOTE
 162      * that the "slot" of a node is NOT the same as its index.
 163      * Furthermore, if an object is inserted into multiple trees, that
 164      * object will have multiple slots.
 165      */
 166     private static Object[] objects = new Object[NUM_SLOTS];
 167
 168     /// These two arrays hold the left and right children of each
 169     /// slot; in other words, left[x] is the *slot* of the left child
 170     /// of the node in slot x.
 171     ///
 172     /// If x has no left child, then left[x] is -1 multiplied by the
 173     /// slot of the node that precedes x; if x is the first node, then
 174     /// left[x] is 0.  The right[] array works the same way.
 175     ///
 176     private static int[] left = new int[NUM_SLOTS];
 177     private static int[] right = new int[NUM_SLOTS];
 178
 179     /// The parent of this node (0 if it is the root node)
 180     private static int[] parent = new int[NUM_SLOTS];
 181
 182     ///< the number of descendants of this node *including the node itself*
 183     private static int[] size = new int[NUM_SLOTS];
 184
 185
 186     // Slot Management //////////////////////////////////////////////////////////////////////
 187
 188     /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
 189     private int getSlot(Object o, boolean alloc) {
 190         // we XOR with our own hashcode so that we don't get tons of
 191         // collisions when a single Object is inserted into multiple
 192         // trees
 193         int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
 194         Object search = alloc ? null : o;
 195         int odest = dest;
 196         boolean plus = true;
 197         int tries = 1;
 198         if(dest == 0) dest=1;
 199         while (objects[dest] != search || !(alloc || root(dest) == root)) {
 200             dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
 201             if (dest == 0) dest=1;
 202             if (plus) tries++;
 203             plus = !plus;
 204             // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
 205         }
 206         return dest;
 207     }
 208
 209     /** returns the slots holding object o */
 210     private int getSlot(Object o) { return getSlot(o,false); }
 211
 212     /** allocates a new slot holding object o*/
 213     private int allocateSlot(Object o) {
 214         int slot = getSlot(o, true);
 215         // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
 216         objects[slot] = o;
 217         return slot;
 218     }
 219
 220
 221
 222     // Helpers /////////////////////////////////////////////////////////////////////////
 223
 224     // FEATURE: These might be faster if they aren't recursive
 225     private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
 226     private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
 227     private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
 228     private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }
 229
 230     private int next(int node) {
 231         if(right[node] > 0) {
 232             node = right[node];
 233             while(left[node] > 0) node = left[node];
 234             return node;
 235         } else {
 236             int p = parent[node];
 237             while(right[p] == node) { node = p; p = parent[node]; };
 238             return p;
 239         }
 240     }
 241
 242     private int prev(int node) {
 243         if(left[node] > 0) {
 244             node = left[node];
 245             while(right[node] > 0) node = right[node];
 246             return node;
 247         } else {
 248             int p = parent[node];
 249             while(left[p] == node) { node = p; p = parent[node]; }
 250             return p;
 251         }
 252     }
 253
 254     // Rotation and Balancing /////////////////////////////////////////////////////////////
 255
 256     //      p                  p
 257     //      |                  |
 258     //      b                  d
 259     //     / \                / \
 260     //    a   d    < == >    b   e
 261     //       / \            / \
 262     //      c   e          a   c
 263     // FIXME might be doing too much work here
 264     private void rotate(boolean toTheLeft, int b, int p) {
 265         int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
 266         int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
 267         int d = right[b];
 268         int c = left[d];
 269         if (d == 0) throw new Error("rotation error");
 270         left[d] = b;
 271         right[b] = c;
 272
 273         parent[b] = d;
 274         parent[d] = p;
 275         if(c != 0) parent[c] = b;
 276
 277         if (p == 0)              root = d;
 278         else if (left[p] == b)   left[p] = d;
 279         else if (right[p] == b)  right[p] = d;
 280         else throw new Error("rotate called with invalid parent");
 281         size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
 282         size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
 283     }
 284
 285     private void balance(int slot, int p) {
 286         if (slot <= 0) return;
 287         size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
 288         if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
 289         else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
 290     }
 291
 292
 293
 294     // Insert /////////////////////////////////////////////////////////////////////////
 295
 296     private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
 297         int diff = slot == 0 ? 0 : index - sizeof(left[slot]);
 298         if (slot != 0 && diff != 0) {
 299             if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
 300             else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
 301             balance(slot, p);
 302             return;
 303         }
 304
 305         if (size[arg] != 0) throw new Error("double insertion");
 306
 307         if(DEBUG) check();
 308
 309         // we are replacing an existing node
 310         if (replace) {
 311             if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
 312             if (p == 0)                 root = arg;
 313             else if (left[p] == slot)   left[p] = arg;
 314             else if (right[p] == slot)  right[p] = arg;
 315             else throw new Error("should never happen");
 316             left[arg] = left[slot];
 317             right[arg] = right[slot];
 318             size[arg] = size[slot];
 319             parent[arg] = parent[slot];
 320             if(left[slot] != 0) parent[left[slot]] = arg;
 321             if(right[slot] != 0) parent[right[slot]] = arg;
 322             objects[slot] = null;
 323             left[slot] = right[slot] = size[slot] = parent[slot] = 0;
 324             if(DEBUG) check();
 325
 326         // we become the child of a former leaf
 327         } else if (slot == 0) {
 328             int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
 329             int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
 330             // FEATURE: Might be doing too much work here
 331             left[arg] = slot;
 332             right[arg] = 0;
 333             parent[arg] = p;
 334             left[p] = arg;
 335             balance(arg, p);
 336
 337         // we take the place of a preexisting node
 338         } else {
 339             if(DEBUG) check();
 340             left[arg] = left[slot];   // steal slot's left subtree
 341             left[slot] = 0;
 342             right[arg] = slot;        // make slot our right subtree
 343             parent[arg] = parent[slot];
 344             parent[slot] = arg;
 345             if(left[arg] != 0) parent[left[arg]] = arg;
 346             if (slot == root) {
 347                 root = arg;
 348                 balance(slot, arg);
 349                 balance(arg, 0);
 350             } else {
 351                 if (left[p] == slot)        left[p] = arg;
 352                 else if (right[p] == slot)  right[p] = arg;
 353                 else throw new Error("should never happen");
 354                 balance(slot, arg);
 355                 balance(arg, p);
 356             }
 357         }
 358     }
 359
 360
 361     // Retrieval //////////////////////////////////////////////////////////////////////
 362
 363     private int get(int index, int slot) {
 364         int diff = index - sizeof(left[slot]);
 365         if (diff > 0) return get(diff - 1, right[slot]);
 366         else if (diff < 0) return get(index, left[slot]);
 367         else return slot;
 368     }
 369
 370
 371     // Deletion //////////////////////////////////////////////////////////////////////
 372
 373     private int delete(int index, int slot, int p) {
 374         int diff = index - sizeof(left[slot]);
 375         if (diff < 0) {
 376             int ret = delete(index, left[slot], slot);
 377             balance(slot, p);
 378             return ret;
 379
 380         } else if (diff > 0) {
 381             int ret = delete(diff - 1, right[slot], slot);
 382             balance(slot, p);
 383             return ret;
 384
 385         // we found the node to delete
 386         } else {
 387
 388             // fast path: it has no children
 389             if (left[slot] == 0 && right[slot] == 0) {
 390                 if (p == 0) root = 0;
 391                 else {
 392                     int[] side = left[p] == slot ? left : right;
 393                     side[p] = side[slot];      // fix parent's pointer
 394                 }
 395
 396             // fast path: it has no left child, so we replace it with its right child
 397             } else if (left[slot] == 0) {
 398                 if (p == 0) root = right[slot];
 399                 else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
 400                 parent[right[slot]] = p;
 401                 left[leftmost(right[slot])] = left[slot];                             // fix our successor-leaf's fake right ptr
 402                 balance(right[slot], p);
 403
 404             // fast path; it has no right child, so we replace it with its left child
 405             } else if (right[slot] == 0) {
 406                 if (p == 0) root = left[slot];
 407                 else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
 408                 parent[left[slot]] = p;
 409                 right[rightmost(left[slot])] = right[slot];                           // fix our successor-leaf's fake right ptr
 410                 balance(left[slot], p);
 411
 412             // node to be deleted has two children, so we replace it with its left child's rightmost descendant
 413             } else {
 414                 int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
 415                 left[left_childs_rightmost] = left[slot];
 416                 right[left_childs_rightmost] = right[slot];
 417                 if(left[slot] != 0) parent[left[slot]] = left_childs_rightmost;
 418                 if(right[slot] != 0) parent[right[slot]] = left_childs_rightmost;
 419                 parent[left_childs_rightmost] = parent[slot];
 420                 if (p == 0) root = left_childs_rightmost;
 421                 else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
 422                 balance(left_childs_rightmost, p);
 423             }
 424
 425             return slot;
 426         }
 427     }
 428
 429     static class FinalizationHelper {
 430         private BalancedTree bt;
 431         FinalizationHelper(BalancedTree bt) { this.bt = bt; }
 432         protected void finalize() { bt.clear(); }
 433     }
 434
 435     // Debugging ///////////////////////////////////////////////////////////////////////////
 436
 437     public void check() { check(false); }
 438     public void check(boolean expensive) {
 439         if(expensive) System.err.println("--> Running expensive balanced tree checks");
 440         try {
 441             if(expensive)
 442                 for(int i=0;i<NUM_SLOTS;i++)
 443                     if(left[i] < 0 || right[i] < 0) throw new Error("someone inserted a negative number");
 444             if(parent[root] != 0) throw new Error("parent of the root isn't 0");
 445             if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
 446                 throw new Error("someone messed with [0]");
 447
 448             int c = 0;
 449             int n = leftmost(root);
 450             while(n != 0) { c++; n = next(n); }
 451             if(c != size[root]) throw new Error("size[] mismatch");
 452
 453             if(root != 0) check(root);
 454         } catch(Error e) {
 455             printTree();
 456             throw e;
 457         }
 458     }
 459
 460     private void check(int node) {
 461         //if(next(node) != next2(node)) throw new Error("next(" + node + ") != next2(" + node + ")");
 462         //if(prev(node) != prev2(node)) throw new Error("prev(" + node + ") != prev2(" + node + ")");
 463
 464         if(left[node] > 0) {
 465             if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
 466             check(left[node]);
 467         }
 468         if(right[node] > 0) {
 469             if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
 470             check(right[node]);
 471         }
 472     }
 473
 474     public void printTree() {
 475         if(root == 0) System.err.println("Tree is empty");
 476         else printTree(root,0,false);
 477     }
 478
 479     private void printTree(int node,int indent,boolean l) {
 480         for(int i=0;i<indent;i++) System.err.print("   ");
 481         if(node == 0) System.err.println("None");
 482         else {
 483             System.err.print("" + node + ": " + objects[node]);
 484             System.err.println(" Parent: " + parent[node] + " Size: " + size[node]);
 485             printTree(left[node],indent+1,true);
 486             printTree(right[node],indent+1,false);
 487         }
 488     }
 489
 490     /*public static void main(String[] args) {
 491         BalancedTree t = new BalancedTree();
 492         for(int i=0;i<args.length;i++)
 493             t.insertNode(i,args[i]);
 494         t.printTree();
 495         for(int n = t.leftmost(t.root); n != 0; n = t.next(n)) {
 496             System.err.println("Next: " + n);
 497         }
 498         for(int n = t.rightmost(t.root); n != 0; n = t.prev(n)) {
 499             System.err.println("Prev: " + n);
 500         }
 501     }*/
 502 }