From 2786e84c0c71f4d1beb70316aba176fc1d98079d Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 2 Apr 2015 22:52:05 +0300 Subject: [PATCH] Fixed docs --- cds/container/bronson_avltree_map_rcu.h | 27 ++++++++++++++++--------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/cds/container/bronson_avltree_map_rcu.h b/cds/container/bronson_avltree_map_rcu.h index c25a1620..8707c3ac 100644 --- a/cds/container/bronson_avltree_map_rcu.h +++ b/cds/container/bronson_avltree_map_rcu.h @@ -46,16 +46,23 @@ namespace cds { namespace container { - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree" - Java implementation - This is a concurrent AVL tree algorithm that uses hand-over-hand optimistic validation, - a concurrency control mechanism for searching and navigating a binary search tree. - This mechanism minimizes spurious retries when concurrent structural changes cannot - affect the correctness of the search or navigation result. The algorithm is based on - partially external trees, a simple scheme that simplifies deletions by leaving a routing - node in the tree when deleting a node that has two children, then opportunistically unlinking - routing nodes during rebalancing. As in external trees, which store values only in leaf nodes, - deletions can be performed locally while holding a fixed number of locks. Partially - external trees, however, require far fewer routing nodes than an external tree for most sequences - of insertions and deletions. + This is a concurrent AVL tree algorithm that uses hand-over-hand optimistic validation, + a concurrency control mechanism for searching and navigating a binary search tree. + This mechanism minimizes spurious retries when concurrent structural changes cannot + affect the correctness of the search or navigation result. + The algorithm is based on partially external trees, a simple scheme that simplifies deletions + by leaving a routing node in the tree when deleting a node that has two children, + then opportunistically unlinking routing nodes during rebalancing. As in external trees, + which store values only in leaf nodes, deletions can be performed locally while holding + a fixed number of locks. Partially external trees, however, require far fewer routing nodes + than an external tree for most sequences of insertions and deletions. + The algorithm uses optimistic concurrency control, but carefully manage the + tree in such a way that all atomic regions have fixed read and write sets + that are known ahead of time. This allows to reduce practical overheads by embedding + the concurrency control directly. To perform tree operations using only fixed sized + atomic regions the algo uses the following mechanisms: search operations overlap atomic blocks as + in the hand-over-hand locking technique; mutations perform rebalancing separately; + and deletions occasionally leave a routing node in the tree. Template arguments: - \p RCU - one of \ref cds_urcu_gc "RCU type" -- 2.34.1