Below is a simple lock-free TST implementation with concurrency support. In this implementation a node's character is assigned if and only if the node is null. This is achieved thanks to CAS instruction.
import java.util.concurrent.atomic.AtomicReference;
/**
* Ternary Search Tree with concurrency support
*
* @see <a href ="http://www.drdobbs.com/database/184410528">drdobbs</a>
* @see <a href ="http://en.wikipedia.org/wiki/Ternary_search_tree" >Ternary search tree</a>
*/
public class TstNode {
private final char ch;
private volatile boolean terminated = false;
private AtomicReference<TstNode> left = new AtomicReference();
private AtomicReference<TstNode> right = new AtomicReference();
private AtomicReference<TstNode> center = new AtomicReference();
public TstNode(char ch) {
this.ch = ch;
}
public boolean isTerminated() {
return terminated;
}
public TstNode search(String word) {
TstNode node;
node = this;
int i = 0;
while (null != node) {
char ch = word.charAt(i);
if (ch < node.ch)
node = node.left.get();
else if (ch == node.ch) {
i++;
if (word.length() == i) {
return (node.terminated) ? node : null;
}
node = node.center.get();
} else
node = node.right.get();
}
//not found
return null;
}
public TstNode insert(String word) {
int i = 0; char ch;
TstNode node = this;
while (i < word.length()) {
ch = word.charAt(i);
if (ch < node.ch) {
node = insertLeftNode(ch, node);
} else if (ch > node.ch) {
node = insertRightNode(ch, node);
} else {
++i;
if (i == word.length()) {
node.terminated = true;
break;
}
node = insertCenterNode(word, i, node);
}
}
return node;
}
private TstNode insertCenterNode(String word, int i, TstNode node) {
node.center.compareAndSet(null,
new TstNode(word.charAt(i)));
node = node.center.get();
return node;
}
private TstNode insertRightNode(char ch, TstNode node) {
node.right.compareAndSet(null, new TstNode(ch));
node = node.right.get();
return node;
}
private TstNode insertLeftNode(char ch, TstNode node) {
node.left.compareAndSet(null, new TstNode(ch));
node = node.left.get();
return node;
}
}
No comments:
Post a Comment