org.amino.mcas
Class LockFreeBSTree<T,V>

java.lang.Object
  extended by org.amino.mcas.LockFreeBSTree<T,V>
Type Parameters:
T - Type of key
V - Type of value

public class LockFreeBSTree<T,V>
extends java.lang.Object

This is an implementation of a lock-free binary search tree.

The implementation is according to the technical report Practical lock-freedom by Keir Fraser, 2004. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf

Lock-free binary search trees (BSTs) are complicated by the problem of deleting a node with two non-empty subtrees. The classical algorithm replaces the deleted node with either the smallest node in its right subtree or the largest node in its left subtree; these nodes can be easily removed from their current position as they have at most one subtree. Implementing this without adding extra synchronization to search operations is difficult because it requires the replacement node to be atomically removed from its current location and inserted in place of the deleted node.

The problem of making an atomic update to multiple memory locations, to effect the simultaneous deletion and reinsertion, is solved by using MCAS. Although this ensures that all the updated memory locations change to their new value at the same instant in time, this is insufficient to ensure consistency of concurrent search operations (see Fig. 4.5 in the paper). Instead Fraser use a threaded tree representation in which pointers to empty subtrees are instead linked to the immediate predecessor or successor node in the tree (see Fig. 4.6 in the paper).

Sample performance results here

The following operations are thread-safe and scalable (but see notes in method javadoc): find, remove, update.

The following operations are not thread-safe:

Author:
Xiao Jun Dai

Constructor Summary
LockFreeBSTree()
          Default constructor.
 
Method Summary
 V find(T key)
          Find key in the tree.
 boolean isEmpty()
          Is the tree empty?
 V remove(T key)
          Remove key in the tree.
 V update(T key, V value)
          update value with key in the tree.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

LockFreeBSTree

public LockFreeBSTree()
Default constructor.

Method Detail

find

public V find(T key)
Find key in the tree.

Parameters:
key - key to search
Returns:
value with key,, otherwise null

update

public V update(T key,
                V value)
update value with key in the tree.

Parameters:
key - key to be updated
value - new value
Returns:
oldValue if key is found, otherwise return null

remove

public V remove(T key)
Remove key in the tree. Deletion is the most time-consuming operation to implement because of the number of different tree configurations which must be handled.

Parameters:
key - key to be removed
Returns:
value with key, otherwise null

isEmpty

public boolean isEmpty()
Is the tree empty?

Returns:
true if the tree is empty, otherwise false


Copyright © 2008. All Rights Reserved.