2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
32 #define CDSLIB_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
34 #include <cds/container/details/ellen_bintree_base.h>
35 #include <cds/intrusive/ellen_bintree_rcu.h>
37 namespace cds { namespace container {
39 /// Map based on Ellen's et al binary search tree (RCU specialization)
40 /** @ingroup cds_nonintrusive_map
41 @ingroup cds_nonintrusive_tree
42 @anchor cds_container_EllenBinTreeMap_rcu
45 - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
47 %EllenBinTreeMap is an unbalanced leaf-oriented binary search tree that implements the <i>map</i>
48 abstract data type. Nodes maintains child pointers but not parent pointers.
49 Every internal node has exactly two children, and all data of type <tt>std::pair<Key const, T></tt>
50 currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
51 operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
52 may or may not be in the map.
53 Unlike \ref cds_container_EllenBinTreeSet_rcu "EllenBinTreeSet" keys are not a part of \p T type.
54 The map can be represented as a set containing <tt>std::pair< Key const, T> </tt> values.
56 Due to \p extract_min and \p extract_max member functions the \p %EllenBinTreeMap can act as
57 a <i>priority queue</i>. In this case you should provide unique compound key, for example,
58 the priority value plus some uniformly distributed random value.
60 @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
61 for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
63 @note In the current implementation we do not use helping technique described in original paper.
64 So, the current implementation is near to fine-grained lock-based tree.
65 Helping will be implemented in future release
67 <b>Template arguments</b> :
68 - \p RCU - one of \ref cds_urcu_gc "RCU type"
70 - \p T - value type to be stored in tree's leaf nodes.
71 - \p Traits - map traits, default is \p ellen_bintree::traits.
72 It is possible to declare option-based tree with \p ellen_bintree::make_map_traits metafunction
73 instead of \p Traits template argument.
75 @note Before including <tt><cds/container/ellen_bintree_map_rcu.h></tt> you should include appropriate RCU header file,
76 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
82 #ifdef CDS_DOXYGEN_INVOKED
83 class Traits = ellen_bintree::traits
88 class EllenBinTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
89 #ifdef CDS_DOXYGEN_INVOKED
90 : public cds::intrusive::EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
92 : public ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
96 typedef ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
97 typedef typename maker::type base_class;
100 typedef cds::urcu::gc<RCU> gc; ///< RCU Garbage collector
101 typedef Key key_type; ///< type of a key stored in the map
102 typedef T mapped_type; ///< type of value stored in the map
103 typedef std::pair< key_type const, mapped_type > value_type; ///< Key-value pair stored in leaf node of the mp
104 typedef Traits traits; ///< Traits template parameter
106 # ifdef CDS_DOXYGEN_INVOKED
107 typedef implementation_defined key_comparator ; ///< key compare functor based on \p Traits::compare and \p Traits::less
109 typedef typename maker::intrusive_traits::compare key_comparator;
111 typedef typename base_class::item_counter item_counter; ///< Item counting policy
112 typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
113 typedef typename base_class::node_allocator node_allocator_type; ///< allocator for maintaining internal node
114 typedef typename base_class::stat stat; ///< internal statistics
115 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
116 typedef typename traits::copy_policy copy_policy; ///< key copy policy
117 typedef typename traits::back_off back_off; ///< Back-off strategy
119 typedef typename traits::allocator allocator_type; ///< Allocator for leaf nodes
120 typedef typename base_class::node_allocator node_allocator; ///< Internal node allocator
121 typedef typename base_class::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
123 static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking
127 typedef typename base_class::value_type leaf_node;
128 typedef typename base_class::internal_node internal_node;
129 typedef typename base_class::update_desc update_desc;
131 typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
133 typedef std::unique_ptr< leaf_node, typename maker::leaf_deallocator > scoped_node_ptr;
137 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
139 /// pointer to extracted node
140 using exempt_ptr = cds::urcu::exempt_ptr < gc, leaf_node, value_type, typename maker::intrusive_traits::disposer,
141 cds::urcu::details::conventional_exempt_member_cast < leaf_node, value_type >
145 /// Default constructor
154 /// Inserts new node with key and default value
156 The function creates a node with \p key and default value, and then inserts the node created into the map.
159 - The \p key_type should be constructible from a value of type \p K.
160 - The \p mapped_type should be default-constructible.
162 RCU \p synchronize() can be called. RCU should not be locked.
164 Returns \p true if inserting successful, \p false otherwise.
166 template <typename K>
167 bool insert( K const& key )
169 return insert_with( key, [](value_type&){} );
174 The function creates a node with copy of \p val value
175 and then inserts the node created into the map.
178 - The \p key_type should be constructible from \p key of type \p K.
179 - The \p value_type should be constructible from \p val of type \p V.
181 RCU \p synchronize() method can be called. RCU should not be locked.
183 Returns \p true if \p val is inserted into the map, \p false otherwise.
185 template <typename K, typename V>
186 bool insert( K const& key, V const& val )
188 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key, val ));
189 if ( base_class::insert( *pNode ))
197 /// Inserts new node and initialize it by a functor
199 This function inserts new node with key \p key and if inserting is successful then it calls
200 \p func functor with signature
203 void operator()( value_type& item );
207 The argument \p item of user-defined functor \p func is the reference
208 to the map's item inserted:
209 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
210 - <tt>item.second</tt> is a reference to item's value that may be changed.
212 The key_type should be constructible from value of type \p K.
214 The function allows to split creating of new item into two part:
215 - create item from \p key;
216 - insert new item into the map;
217 - if inserting is successful, initialize the value of item by calling \p func functor
219 This can be useful if complete initialization of object of \p value_type is heavyweight and
220 it is preferable that the initialization should be completed only if inserting is successful.
222 RCU \p synchronize() method can be called. RCU should not be locked.
224 template <typename K, typename Func>
225 bool insert_with( K const& key, Func func )
227 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
228 if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { func( item.m_Value ); } )) {
235 /// For key \p key inserts data of type \p value_type created in-place from \p args
237 Returns \p true if inserting successful, \p false otherwise.
239 RCU \p synchronize() method can be called. RCU should not be locked.
241 template <typename K, typename... Args>
242 bool emplace( K&& key, Args&&... args )
244 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( std::forward<K>(key), std::forward<Args>(args)... ));
245 if ( base_class::insert( *pNode )) {
254 The operation performs inserting or changing data with lock-free manner.
256 If the item \p val is not found in the map, then \p val is inserted iff \p bAllowInsert is \p true.
257 Otherwise, the functor \p func is called with item found.
258 The functor \p func signature is:
261 void operator()( bool bNew, value_type& item );
266 - \p bNew - \p true if the item has been inserted, \p false otherwise
267 - \p item - item of the map
269 The functor may change any fields of the \p item.second that is \p mapped_type;
270 however, \p func must guarantee that during changing no any other modifications
271 could be made on this item by concurrent threads.
273 RCU \p synchronize() method can be called. RCU should not be locked.
275 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
276 i.e. the node has been inserted or updated,
277 \p second is \p true if new item has been added or \p false if the item with \p key
280 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
282 template <typename K, typename Func>
283 std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
285 scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
286 std::pair<bool, bool> res = base_class::update( *pNode,
287 [&func](bool bNew, leaf_node& item, leaf_node const& ){ func( bNew, item.m_Value ); },
290 if ( res.first && res.second )
295 template <typename K, typename Func>
296 CDS_DEPRECATED("ensure() is deprecated, use update()")
297 std::pair<bool, bool> ensure( K const& key, Func func )
299 return update( key, func, true );
303 /// Delete \p key from the map
304 /**\anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_val
306 RCU \p synchronize() method can be called. RCU should not be locked.
308 Return \p true if \p key is found and deleted, \p false otherwise
310 template <typename K>
311 bool erase( K const& key )
313 return base_class::erase(key);
316 /// Deletes the item from the map using \p pred predicate for searching
318 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_val "erase(K const&)"
319 but \p pred is used for key comparing.
320 \p Less functor has the interface like \p std::less.
321 \p Less must imply the same element order as the comparator used for building the map.
323 template <typename K, typename Less>
324 bool erase_with( K const& key, Less pred )
327 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
330 /// Delete \p key from the map
331 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_func
333 The function searches an item with key \p key, calls \p f functor
334 and deletes the item. If \p key is not found, the functor is not called.
336 The functor \p Func interface:
339 void operator()(value_type& item) { ... }
343 RCU \p synchronize method can be called. RCU should not be locked.
345 Return \p true if key is found and deleted, \p false otherwise
347 template <typename K, typename Func>
348 bool erase( K const& key, Func f )
350 return base_class::erase( key, [&f]( leaf_node& node) { f( node.m_Value ); } );
353 /// Deletes the item from the map using \p pred predicate for searching
355 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_func "erase(K const&, Func)"
356 but \p pred is used for key comparing.
357 \p Less functor has the interface like \p std::less.
358 \p Less must imply the same element order as the comparator used for building the map.
360 template <typename K, typename Less, typename Func>
361 bool erase_with( K const& key, Less pred, Func f )
364 return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
365 [&f]( leaf_node& node) { f( node.m_Value ); } );
368 /// Extracts an item with minimal key from the map
370 Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
371 If the set is empty, returns empty \p exempt_ptr.
373 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
374 It means that the function gets leftmost leaf of the tree and tries to unlink it.
375 During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
376 So, the function returns the item with minimum key at the moment of tree traversing.
378 RCU \p synchronize method can be called. RCU should NOT be locked.
379 The function does not free the item.
380 The deallocator will be implicitly invoked when the returned object is destroyed or when
381 its \p release() member function is called.
383 exempt_ptr extract_min()
385 return exempt_ptr( base_class::extract_min_());
388 /// Extracts an item with maximal key from the map
390 Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
391 If the set is empty, returns empty \p exempt_ptr.
393 @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
394 It means that the function gets rightmost leaf of the tree and tries to unlink it.
395 During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
396 So, the function returns the item with maximum key at the moment of tree traversing.
398 RCU \p synchronize method can be called. RCU should NOT be locked.
399 The function does not free the item.
400 The deallocator will be implicitly invoked when the returned object is destroyed or when
401 its \p release() is called.
402 @note Before reusing \p result object you should call its \p release() method.
404 exempt_ptr extract_max()
406 return exempt_ptr( base_class::extract_max_());
409 /// Extracts an item from the map
410 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_extract
411 The function searches an item with key equal to \p key in the tree,
412 unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
413 If \p key is not found the function returns an empty \p exempt_ptr.
415 RCU \p synchronize method can be called. RCU should NOT be locked.
416 The function does not destroy the item found.
417 The dealloctor will be implicitly invoked when the returned object is destroyed or when
418 its \p release() member function is called.
420 template <typename Q>
421 exempt_ptr extract( Q const& key )
423 return exempt_ptr( base_class::extract_( key, typename base_class::node_compare()));
426 /// Extracts an item from the map using \p pred for searching
428 The function is an analog of \p extract(Q const&)
429 but \p pred is used for key compare.
430 \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
431 "predicate requirements".
432 \p pred must imply the same element order as the comparator used for building the map.
434 template <typename Q, typename Less>
435 exempt_ptr extract_with( Q const& key, Less pred )
438 return exempt_ptr( base_class::extract_with_( key,
439 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() ));
442 /// Find the key \p key
443 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc
445 The function searches the item with key equal to \p key and calls the functor \p f for item found.
446 The interface of \p Func functor is:
449 void operator()( value_type& item );
452 where \p item is the item found.
454 The functor may change \p item.second.
456 The function applies RCU lock internally.
458 The function returns \p true if \p key is found, \p false otherwise.
460 template <typename K, typename Func>
461 bool find( K const& key, Func f )
463 return base_class::find( key, [&f](leaf_node& item, K const& ) { f( item.m_Value );});
466 /// Finds the key \p val using \p pred predicate for searching
468 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc "find(K const&, Func)"
469 but \p pred is used for key comparing.
470 \p Less functor has the interface like \p std::less.
471 \p Less must imply the same element order as the comparator used for building the map.
473 template <typename K, typename Less, typename Func>
474 bool find_with( K const& key, Less pred, Func f )
477 return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
478 [&f](leaf_node& item, K const& ) { f( item.m_Value );});
481 /// Checks whether the map contains \p key
483 The function searches the item with key equal to \p key
484 and returns \p true if it is found, and \p false otherwise.
486 The function applies RCU lock internally.
488 template <typename K>
489 bool contains( K const& key )
491 return base_class::contains( key );
494 template <typename K>
495 CDS_DEPRECATED("deprecated, use contains()")
496 bool find( K const& key )
498 return contains( key );
502 /// Checks whether the map contains \p key using \p pred predicate for searching
504 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
505 \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_rcu_less
506 "Predicate requirements".
507 \p Less must imply the same element order as the comparator used for building the set.
509 template <typename K, typename Less>
510 bool contains( K const& key, Less pred )
513 return base_class::contains( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
516 template <typename K, typename Less>
517 CDS_DEPRECATED("deprecated, use contains()")
518 bool find_with( K const& key, Less pred )
520 return contains( key, pred );
524 /// Finds \p key and return the item found
525 /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_get
526 The function searches the item with key equal to \p key and returns the pointer to item found.
527 If \p key is not found it returns \p nullptr.
529 RCU should be locked before call the function.
530 Returned pointer is valid while RCU is locked.
532 template <typename Q>
533 value_type * get( Q const& key ) const
535 leaf_node * pNode = base_class::get( key );
536 return pNode ? &pNode->m_Value : nullptr;
539 /// Finds \p key with \p pred predicate and return the item found
541 The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_get "get(Q const&)"
542 but \p pred is used for comparing the keys.
544 \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type
545 and \p Q in any order.
546 \p pred must imply the same element order as the comparator used for building the map.
548 template <typename Q, typename Less>
549 value_type * get_with( Q const& key, Less pred ) const
552 leaf_node * pNode = base_class::get_with( key,
553 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
554 return pNode ? &pNode->m_Value : nullptr;
563 /// Checks if the map is empty
566 return base_class::empty();
569 /// Returns item count in the map
571 Only leaf nodes containing user data are counted.
573 The value returned depends on item counter type provided by \p Traits template parameter.
574 If it is \p atomicity::empty_item_counter this function always returns 0.
576 The function is not suitable for checking the tree emptiness, use \p empty()
577 member function for this purpose.
581 return base_class::size();
584 /// Returns const reference to internal statistics
585 stat const& statistics() const
587 return base_class::statistics();
590 /// Checks internal consistency (not atomic, not thread-safe)
592 The debugging function to check internal consistency of the tree.
594 bool check_consistency() const
596 return base_class::check_consistency();
599 }} // namespace cds::container
601 #endif //#ifndef CDSLIB_CONTAINER_ELLEN_BINTREE_MAP_RCU_H