// 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;
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");
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;
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) {
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);
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 {
i = next;
} while(i != 0);
root = 0;
+ }
}
protected void finalize() { clear(); }
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;