|
||||||||||
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 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:
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 |