Concurrent T-Tree

Node.java

import java.util.Arrays;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class Node {

	static final int MIN_ELEMENTS = 30, MAX_ELEMENTS = 2 * MIN_ELEMENTS;
	private int[] data;
	private int len;
	private Node left, right, parent;
	private int h, balance;
	private ReentrantReadWriteLock lock;

	public Node(Node parent) {
		len = 0;
		data = new int[MAX_ELEMENTS];
		this.parent = parent;
		h = 1;
		balance = 0;
		lock = new ReentrantReadWriteLock();
	}

	public int isBoundingNode(int x) {
		if (len == 0)
			return 0;
		if (x < data[0])
			return -1;
		if (x > data[len - 1])
			return 1;
		return 0;
	}

	public void insert(int x) {
		if (len == MAX_ELEMENTS)
			return;
		int i = len;
		while (i > 0 && data[i - 1] > x) {
			data[i] = data[i - 1];
			i--;
		}
		data[i] = x;
		len++;
	}

	public void delete(int x) {
		int i = 0;
		while (data[i] != x && i < len)
			i++;
		if (i == len)
			return;
		while (i < len - 1) {
			data[i] = data[i + 1];
			i++;
		}
		len--;
	}

	public boolean isContains(int x) {
		return Arrays.binarySearch(data, 0, len, x) >= 0;
	}

	public int getLength() {
		return len;
	}

	public String toString() {
		String result = new String();
		for (int i = 0; i < len; i++)
			result += data[i] + " ";
		return result;
	}

	public boolean isLeaf() {
		return left == null || right == null;
	}

	public Node getLeft() {
		return left;
	}

	public Node getRight() {
		return right;
	}

	public Node getParent() {
		return parent;
	}

	public void setLeft(Node x) {
		left = x;
		updateBalance();
	}

	public void setRight(Node x) {
		right = x;
		updateBalance();
	}

	public int getMinimum() {
		return data[0];
	}

	public int getMaximum() {
		return data[len - 1];
	}
	
	public int getBalance() {
		return balance;
	}

	private void updateBalance() {
		int l = 0, r = 0;
		if (left != null)
			l = left.h;
		if (right != null)
			r = right.h;
		h = 1 + Math.max(l, r);
		balance = l - r;
	}

	public void rebalance() {
		updateBalance();
		if (balance == -2) {
			if (right.balance == -1)
				leftRotation();
			else {
				if (right.left.isLeaf() && right.right == null && left == null
						&& right.left.len == 1)
					replaceMin(right, right.left);
				right.rightRotation();
				leftRotation();
			}
		} else if (balance == 2) {
			if (left.balance == 1)
				rightRotation();
			else {
				if (left.right.isLeaf() && left.left == null && right == null
						&& left.right.len == 1)
					replaceMax(left, left.right);
				left.leftRotation();
				rightRotation();
			}
		}
	}

	private void replaceMin(Node from, Node to) {
		while (from.len != 1) {
			to.insert(from.getMinimum());
			from.delete(from.getMinimum());
		}
	}
	
	private void replaceMax(Node from, Node to) {
		while (from.len != 1) {
			to.insert(from.getMaximum());
			from.delete(from.getMaximum());
		}
	}

	private void leftRotation() {
		Node p = parent;
		Node r = right;

		right = r.left;
		if (r.left != null)
			r.left.parent = this;
		r.left = this;
		parent = r;
		if (p.left == this)
			p.left = r;
		else
			p.right = r;
		r.parent = p;
		updateBalance();
		r.updateBalance();
	}

	private void rightRotation() {
		Node p = parent;
		Node l = left;

		left = l.right;
		if (l.right != null)
			l.right.parent = this;
		l.right = this;
		parent = l;
		if (p.left == this)
			p.left = l;
		else
			p.right = l;
		l.parent = p;
		updateBalance();
		l.updateBalance();
	}
	
	public void lock(){
		lock.writeLock().lock();
	}
	
	public void unlock(){
		lock.writeLock().unlock();
	}
	
	public void readLock(){
		lock.readLock().lock();
	}
	
	public void readUnlock(){
		lock.readLock().unlock();
	}
}

Test.java

import java.util.Random;
import java.util.StringTokenizer;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class Test {

	private TTree tree = new TTree();
	private boolean[] wasAdded;
	
	public class Inserter implements Runnable {

		@Override
		public void run() {
			Random rand = new Random();
			for (int i = 0; i < 40000; i++) {
				int t = rand.nextInt(300000);
				tree.insert(t);
				wasAdded[t] = true;
				//System.out.println(i + " Insert " + t);
			}
		}
	}

	public class Searcher implements Runnable {

		@Override
		public void run() {
			Random rand = new Random();
			for (int i = 0; i < 20000; i++){
				int t = rand.nextInt(300000);
				tree.search(t);
				//System.out.println(i + " Search " + t + " - " + tree.search(t));
			}
		}
	}

	public void runRandomTest() {
		wasAdded = new boolean[300000];
		ExecutorService serv = Executors.newFixedThreadPool(8);
		for (int i = 0; i < 4; i++) {
			serv.execute(new Inserter());
			serv.execute(new Searcher());
		}
		serv.shutdown();
		try {
			serv.awaitTermination(60, TimeUnit.HOURS);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		boolean f = check(tree);
		if (!f) {
			System.out.println("ERROR!!!");
			System.out.println(tree);
			System.exit(1);
		}
		else
			System.out.println("OK");
	}

	private boolean check(TTree tree) {
		return tree.isBalanced() && isSortedAndNoRepeat(tree);
	}

	private boolean isSortedAndNoRepeat(TTree tree) {
		String s = tree.toString();
		StringTokenizer tokenizer = new StringTokenizer(s);
		int prev = -1;
		while (tokenizer.hasMoreTokens()) {
			int curr = Integer.parseInt(tokenizer.nextToken());
			if (curr <= prev)
				return false;
			prev = curr;
		}
		return true;
	}

	public static void main(String[] args) throws Exception {
		for (int i = 0; i < 300; i++){
			System.out.println("Random Test #" + i);
			new Test().runRandomTest();
		}
	}

}

TTree.java

import java.util.Stack;
import java.util.concurrent.locks.*;

public class TTree {
	private Node root;
	private Lock lock;
	private Boolean fixed;
	private Integer count;
	private Stack<Node> newNodes;

	public TTree() {
		root = new Node(null);
		Node t = new Node(root);
		root.setLeft(t);

		lock = new ReentrantLock();
		fixed = false;
		count = 0;
		newNodes = new Stack<Node>();
	}

	public boolean search(int x) {
		lock.lock();
		while (fixed) {
			lock.unlock();
			lock.lock();
		}
		count++;
		lock.unlock();
		return search(root.getLeft(), x);
	}

	private boolean search(Node curr, int x) {
		if (curr == null){
			lock.lock();
			count--;
			lock.unlock();
			return false;
		}
		curr.readLock();
		int t = curr.isBoundingNode(x);
		if (t == 0) {
			boolean res = curr.isContains(x);
			lock.lock();
			count--;
			lock.unlock();
			curr.readUnlock();
			return res;
		}
		curr.readUnlock();
		if (t < 0)
			return search(curr.getLeft(), x);
		return search(curr.getRight(), x);
	}

	public void insert(int x) {
		lock.lock();
		while (fixed) { // Very evil magic
			lock.unlock();
			lock.lock();
		}
		count++;
		lock.unlock();
		insert(root.getLeft(), x);
	}

	private void afterAdd(Node curr) {
		curr.unlock();
		lock.lock();
		count--;
		lock.unlock();
	}

	private void preFix(Node child) {
		lock.lock();
		newNodes.add(child);
		if (!fixed) {
			fixed = true;
			count--;
			lock.unlock();
			fixTree();
			return;
		}
		count--;
		lock.unlock();
	}

	private void insert(Node curr, int x) {
		curr.lock();
		int t = curr.isBoundingNode(x);
		if (t == 0) {
			if (curr.isContains(x)) {
				afterAdd(curr);
				return;
			}
			if (curr.getLength() != curr.MAX_ELEMENTS) {
				curr.insert(x);
				afterAdd(curr);
				return;
			}
			int min = curr.getMinimum();
			curr.delete(min);
			curr.insert(x);
			if (curr.getLeft() != null) {
				curr.unlock();
				insert(curr.getLeft(), min);
				return;
			}
			Node child = new Node(curr);
			child.insert(min);
			curr.setLeft(child);
			curr.unlock();
			preFix(child);
			return;
		}
		if (t > 0) {
			insertRight(curr, x);
			return;
		}
		insertLeft(curr, x);
	}

	private void insertRight(Node curr, int x) {
		if (curr.getRight() != null) {
			curr.unlock();
			insert(curr.getRight(), x);
			return;
		}
		if (curr.getLength() != curr.MAX_ELEMENTS) {
			curr.insert(x);
			afterAdd(curr);
			return;
		}
		Node child = new Node(curr);
		child.insert(x);
		curr.setRight(child);
		curr.unlock();
		preFix(child);
	}

	private void insertLeft(Node curr, int x) {
		if (curr.getLeft() != null) {
			curr.unlock();
			insert(curr.getLeft(), x);
			return;
		}
		if (curr.getLength() != curr.MAX_ELEMENTS) {
			curr.insert(x);
			afterAdd(curr);
			return;
		}
		Node child = new Node(curr);
		child.insert(x);
		curr.setLeft(child);
		curr.unlock();
		preFix(child);
	}

	private void fixTree() {
		lock.lock();
		while (count != 0) {
			lock.unlock();
			lock.lock();
		}
		lock.unlock();
		while (!newNodes.isEmpty()) {
			Node curr = newNodes.pop();
			while (curr != root) {
				curr.rebalance();
				curr = curr.getParent();
			}
		}
		lock.lock();
		fixed = false;
		lock.unlock();
	}

	public String toString() {
		return getAll(root.getLeft());
	}

	private String getAll(Node curr) {
		String res = new String();
		if (curr.getLeft() != null)
			res += getAll(curr.getLeft());
		res += curr.toString();
		if (curr.getRight() != null)
			res += getAll(curr.getRight());
		return res;
	}

	public boolean isBalanced() {
		return isBalanced(root.getLeft());
	}

	private boolean isBalanced(Node curr) {
		if (curr == null)
			return true;
		int b = curr.getBalance();
		return (b < 2) && (b > -2) && isBalanced(curr.getLeft())
				&& isBalanced(curr.getRight());
	}
}