Skip to content

Instantly share code, notes, and snippets.

@EvaGL
Created May 11, 2012 23:33
Show Gist options
  • Save EvaGL/2663096 to your computer and use it in GitHub Desktop.
Save EvaGL/2663096 to your computer and use it in GitHub Desktop.
Concurrent T-Tree
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();
}
}
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();
}
}
}
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());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment