Saturday, 23 June 2012

Concurrent Ternary Search Tree

I was recently asked for implementing string processing and searching feature. I decided to use the ternary search data structure, as it consumes less memory than hash-based structures. Moreover hash-based data structures lookup performance heavily depends on how hash function is implemented. On the other side a ternary searh tree lookup performance would be satisfying assuming string insertions will be random.
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