

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.amino.mcas.LockFreeBSTree<T,V>
T
 Type of keyV
 Type of valuepublic class LockFreeBSTree<T,V>
This is an implementation of a lockfree binary search tree.
The implementation is according to the technical report Practical lockfreedom 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/UCAMCLTR579.pdf
Lockfree binary search trees (BSTs) are complicated by the problem of deleting a node with two nonempty 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 threadsafe and scalable (but see notes in method javadoc): find, remove, update.
The following operations are not threadsafe:
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 

public LockFreeBSTree()
Method Detail 

public V find(T key)
key
 key to search
public V update(T key, V value)
key
 key to be updatedvalue
 new value
public V remove(T key)
key
 key to be removed
public boolean isEmpty()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 