cds/container/bronson_avltree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
   4 #define CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
   5
   6 #include <cds/container/impl/bronson_avltree_map_rcu.h>
   7
   8 namespace cds { namespace container {
   9
  10     namespace bronson_avltree {
  11         //@cond
  12         namespace details {
  13             template < class RCU, typename Key, typename T, typename Traits>
  14             struct make_map
  15             {
  16                 typedef Key key_type;
  17                 typedef T mapped_type;
  18                 typedef Traits original_traits;
  19
  20                 typedef cds::details::Allocator< mapped_type, typename original_traits::allocator > cxx_allocator;
  21
  22                 struct traits : public original_traits
  23                 {
  24                     struct disposer {
  25                         void operator()( mapped_type * p ) const
  26                         {
  27                             cxx_allocator().Delete( p );
  28                         }
  29                     };
  30                 };
  31
  32                 // Metafunction result
  33                 typedef BronsonAVLTreeMap< RCU, Key, T *, traits > type;
  34             };
  35         } // namespace details
  36         //@endcond
  37     } // namespace bronson_avltree
  38
  39     /// Bronson et al AVL-tree (RCU specialization)
  40     /** @ingroup cds_nonintrusive_map
  41         @ingroup cds_nonintrusive_tree
  42         @anchor cds_container_BronsonAVLTreeMap_rcu
  43
  44         Source:
  45             - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
  46
  47         bla-bla-bla
  48
  49         <b>Template arguments</b>:
  50         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  51         - \p Key - key type
  52         - \p T - value type to be stored in tree's nodes.
  53         - \p Traits - tree traits, default is \p bronson_avltree::traits
  54             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
  55             instead of \p Traits template argument.
  56
  57         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
  58         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  59     */
  60     template <
  61         typename RCU,
  62         typename Key,
  63         typename T,
  64 #   ifdef CDS_DOXYGEN_INVOKED
  65         typename Traits = bronson_avltree::traits
  66 #else
  67         typename Traits
  68 #endif
  69     >
  70     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
  71 #ifdef CDS_DOXYGEN_INVOKED
  72         : private BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
  73 #else
  74         : private bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
  75 #endif
  76     {
  77         //@cond
  78         typedef bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
  79         typedef typename maker::type base_class;
  80         //@endcond
  81
  82     public:
  83         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
  84         typedef Key     key_type;    ///< type of a key stored in the map
  85         typedef T       mapped_type; ///< type of value stored in the map
  86         typedef Traits  traits;      ///< Traits template parameter
  87
  88         typedef typename base_class::key_comparator     key_comparator;     ///< key compare functor based on \p Traits::compare and \p Traits::less
  89         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
  90         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
  91         typedef typename traits::allocator              allocator_type;     ///< allocator for value
  92         typedef typename traits::node_allocator         node_allocator_type;///< allocator for maintaining internal nodes
  93         typedef typename traits::stat                   stat;               ///< internal statistics
  94         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
  95         typedef typename traits::back_off               back_off;           ///< Back-off strategy
  96         typedef typename traits::sync_monitor           sync_monitor;       ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
  97
  98         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
  99         static bool const c_bRelaxedInsert = traits::relaxed_insert;
 100
 101         /// Returned pointer to value of extracted node
 102         typedef typename base_class::unique_ptr unique_ptr;
 103
 104         typedef typename base_class::rcu_lock   rcu_lock;  ///< RCU scoped lock
 105
 106     protected:
 107         //@cond
 108         typedef typename base_class::node_type  node_type;
 109         typedef typename base_class::node_scoped_lock node_scoped_lock;
 110         typedef typename maker::cxx_allocator   cxx_allocator;
 111
 112         typedef typename base_class::update_flags update_flags;
 113         //@endcond
 114
 115     public:
 116         /// Creates empty map
 117         BronsonAVLTreeMap()
 118         {}
 119
 120         /// Destroys the map
 121         ~BronsonAVLTreeMap()
 122         {}
 123
 124         /// Inserts new node with \p key and default value
 125         /**
 126             The function creates a node with \p key and default value, and then inserts the node created into the map.
 127
 128             Preconditions:
 129             - The \p key_type should be constructible from a value of type \p K.
 130             - The \p mapped_type should be default-constructible.
 131
 132             RCU \p synchronize() can be called. RCU should not be locked.
 133
 134             Returns \p true if inserting successful, \p false otherwise.
 135         */
 136         template <typename K>
 137         bool insert( K const& key )
 138         {
 139             return base_class::do_update(key, key_comparator(),
 140                 []( node_type * pNode ) -> mapped_type*
 141                 {
 142                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 143                     CDS_UNUSED( pNode );
 144                     return cxx_allocator().New();
 145                 },
 146                     static_cast<int>(update_flags::allow_insert)
 147             ) == static_cast<int>(update_flags::result_inserted);
 148         }
 149
 150         /// Inserts new node
 151         /**
 152             The function creates a node with copy of \p val value
 153             and then inserts the node created into the map.
 154
 155             Preconditions:
 156             - The \p key_type should be constructible from \p key of type \p K.
 157             - The \p mapped_type should be constructible from \p val of type \p V.
 158
 159             RCU \p synchronize() method can be called. RCU should not be locked.
 160
 161             Returns \p true if \p val is inserted into the map, \p false otherwise.
 162         */
 163         template <typename K, typename V>
 164         bool insert( K const& key, V const& val )
 165         {
 166             return base_class::do_update( key, key_comparator(),
 167                 [&val]( node_type * pNode )
 168                 {
 169                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 170                     CDS_UNUSED( pNode );
 171                     return cxx_allocator().New( val );
 172                 },
 173                 static_cast<int>(update_flags::allow_insert)
 174             ) == static_cast<int>(update_flags::result_inserted);
 175         }
 176
 177         /// Inserts new node and initialize it by a functor
 178         /**
 179             This function inserts new node with key \p key and if inserting is successful then it calls
 180             \p func functor with signature
 181             \code
 182                 struct functor {
 183                     void operator()( key_type const& key, mapped_type& item );
 184                 };
 185             \endcode
 186
 187             The key_type should be constructible from value of type \p K.
 188
 189             The function allows to split creating of new item into two part:
 190             - create item from \p key;
 191             - insert new item into the map;
 192             - if inserting is successful, initialize the value of item by calling \p func functor
 193
 194             This can be useful if complete initialization of object of \p value_type is heavyweight and
 195             it is preferable that the initialization should be completed only if inserting is successful.
 196             The functor is called under the node lock.
 197
 198             RCU \p synchronize() method can be called. RCU should not be locked.
 199         */
 200         template <typename K, typename Func>
 201         bool insert_with( K const& key, Func func )
 202         {
 203             return base_class::do_update( key, key_comparator(),
 204                 [&func]( node_type * pNode ) -> mapped_type*
 205                 {
 206                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 207                     mapped_type * pVal = cxx_allocator().New();
 208                     func( pNode->m_key, *pVal );
 209                     return pVal;
 210                 },
 211                 static_cast<int>(update_flags::allow_insert)
 212             ) == static_cast<int>(update_flags::result_inserted);
 213         }
 214
 215         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
 216         /**
 217             Returns \p true if inserting successful, \p false otherwise.
 218
 219             RCU \p synchronize() method can be called. RCU should not be locked.
 220         */
 221         template <typename K, typename... Args>
 222         bool emplace( K&& key, Args&&... args )
 223         {
 224             return base_class::do_update( key, key_comparator(),
 225                 [&]( node_type * pNode ) -> mapped_type*
 226                 {
 227                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 228                     CDS_UNUSED( pNode );
 229                     return cxx_allocator().New( std::forward<Args>(args)...);
 230                 },
 231                 static_cast<int>(update_flags::allow_insert)
 232             ) == static_cast<int>(update_flags::result_inserted);
 233         }
 234
 235         /// Ensures that the \p key exists in the map
 236         /**
 237             The operation performs inserting or changing data with lock-free manner.
 238
 239             If the \p key not found in the map, then the new item created from \p key
 240             is inserted into the map (note that in this case the \ref key_type should be
 241             constructible from type \p K).
 242             Otherwise, the functor \p func is called with item found.
 243             The functor \p Func may be a functor:
 244             \code
 245                 struct my_functor {
 246                     void operator()( bool bNew, key_type const& key, mapped_type& item );
 247                 };
 248             \endcode
 249
 250             with arguments:
 251             - \p bNew - \p true if the item has been inserted, \p false otherwise
 252             - \p item - value
 253
 254             The functor may change any fields of the \p item. The functor is called under the node lock.
 255
 256             RCU \p synchronize() method can be called. RCU should not be locked.
 257
 258             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 259             \p second is \p true if new item has been added or \p false if the item with \p key
 260             already is in the tree.
 261         */
 262         template <typename K, typename Func>
 263         std::pair<bool, bool> update( K const& key, Func func )
 264         {
 265             int result = base_class::do_update( key, key_comparator(),
 266                 [&func]( node_type * pNode ) -> mapped_type*
 267                 {
 268                     mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 269                     if ( !pVal ) {
 270                         pVal = cxx_allocator().New();
 271                         func( true, pNode->m_key, *pVal );
 272                     }
 273                     else
 274                         func( false, pNode->m_key, *pVal );
 275                     return pVal;
 276                 },
 277                 update_flags::allow_insert | update_flags::allow_update
 278             );
 279             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 280         }
 281
 282         /// Delete \p key from the map
 283         /**
 284             RCU \p synchronize() method can be called. RCU should not be locked.
 285
 286             Return \p true if \p key is found and deleted, \p false otherwise
 287         */
 288         template <typename K>
 289         bool erase( K const& key )
 290         {
 291             return base_class::erase( key );
 292         }
 293
 294         /// Deletes the item from the map using \p pred predicate for searching
 295         /**
 296             The function is an analog of \p erase(K const&)
 297             but \p pred is used for key comparing.
 298             \p Less functor has the interface like \p std::less.
 299             \p Less must imply the same element order as the comparator used for building the map.
 300         */
 301         template <typename K, typename Less>
 302         bool erase_with( K const& key, Less pred )
 303         {
 304             return base_class::erase_with( key, pred );
 305         }
 306
 307         /// Delete \p key from the map
 308         /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
 309
 310             The function searches an item with key \p key, calls \p f functor
 311             and deletes the item. If \p key is not found, the functor is not called.
 312
 313             The functor \p Func interface:
 314             \code
 315             struct extractor {
 316                 void operator()(mapped_type& item) { ... }
 317             };
 318             \endcode
 319
 320             RCU \p synchronize method can be called. RCU should not be locked.
 321
 322             Return \p true if key is found and deleted, \p false otherwise
 323         */
 324         template <typename K, typename Func>
 325         bool erase( K const& key, Func f )
 326         {
 327             return base_class::erase( key, f );
 328         }
 329
 330         /// Deletes the item from the map using \p pred predicate for searching
 331         /**
 332             The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
 333             but \p pred is used for key comparing.
 334             \p Less functor has the interface like \p std::less.
 335             \p Less must imply the same element order as the comparator used for building the map.
 336         */
 337         template <typename K, typename Less, typename Func>
 338         bool erase_with( K const& key, Less pred, Func f )
 339         {
 340             return base_class::erase_with( key, pred, f );
 341         }
 342
 343         /// Extracts an item with minimal key from the map
 344         /**
 345             Returns \p std::unique_ptr pointer to the leftmost item.
 346             If the set is empty, returns empty \p std::unique_ptr.
 347
 348             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 349             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 350             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 351             So, the function returns the item with minimum key at the moment of tree traversing.
 352
 353             RCU \p synchronize method can be called. RCU should NOT be locked.
 354             The function does not free the item.
 355             The deallocator will be implicitly invoked when the returned object is destroyed or when
 356             its \p reset(nullptr) member function is called.
 357         */
 358         unique_ptr extract_min()
 359         {
 360             return base_class::extract_min();
 361         }
 362
 363         /// Extracts an item with maximal key from the map
 364         /**
 365             Returns \p std::unique_ptr pointer to the rightmost item.
 366             If the set is empty, returns empty \p std::unique_ptr.
 367
 368             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 369             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 370             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 371             So, the function returns the item with maximum key at the moment of tree traversing.
 372
 373             RCU \p synchronize method can be called. RCU should NOT be locked.
 374             The function does not free the item.
 375             The deallocator will be implicitly invoked when the returned object is destroyed or when
 376             its \p reset(nullptr) is called.
 377             @note Before reusing \p result object you should call its \p release() method.
 378         */
 379         unique_ptr extract_max()
 380         {
 381             return base_class::extract_min();
 382         }
 383
 384         /// Extracts an item from the map
 385         /**
 386             The function searches an item with key equal to \p key in the tree,
 387             unlinks it, and returns \p std::unique_ptr pointer to a value found.
 388             If \p key is not found the function returns an empty \p std::unique_ptr.
 389
 390             RCU \p synchronize method can be called. RCU should NOT be locked.
 391             The function does not destroy the value found.
 392             The dealloctor will be implicitly invoked when the returned object is destroyed or when
 393             its \p reset(nullptr) member function is called.
 394         */
 395         template <typename Q>
 396         unique_ptr extract( Q const& key )
 397         {
 398             return base_class::extract( key );
 399         }
 400
 401         /// Extracts an item from the map using \p pred for searching
 402         /**
 403             The function is an analog of \p extract(Q const&)
 404             but \p pred is used for key compare.
 405             \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
 406             "predicate requirements".
 407             \p pred must imply the same element order as the comparator used for building the map.
 408         */
 409         template <typename Q, typename Less>
 410         unique_ptr extract_with( Q const& key, Less pred )
 411         {
 412             return base_class::extract_with( key, pred );
 413         }
 414
 415         /// Find the key \p key
 416         /**
 417             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 418             The interface of \p Func functor is:
 419             \code
 420             struct functor {
 421                 void operator()( mapped_type& item );
 422             };
 423             \endcode
 424             where \p item is the item found.
 425             The functor is called under node-level lock.
 426
 427             The function applies RCU lock internally.
 428
 429             The function returns \p true if \p key is found, \p false otherwise.
 430         */
 431         template <typename K, typename Func>
 432         bool find( K const& key, Func f )
 433         {
 434             return base_class::find( key, f );
 435         }
 436
 437         /// Finds the key \p val using \p pred predicate for searching
 438         /**
 439             The function is an analog of \p find(K const&, Func)
 440             but \p pred is used for key comparing.
 441             \p Less functor has the interface like \p std::less.
 442             \p Less must imply the same element order as the comparator used for building the map.
 443         */
 444         template <typename K, typename Less, typename Func>
 445         bool find_with( K const& key, Less pred, Func f )
 446         {
 447             return base_class::find_with( key, pred, f );
 448         }
 449
 450         /// Find the key \p key
 451         /**
 452             The function searches the item with key equal to \p key
 453             and returns \p true if it is found, and \p false otherwise.
 454
 455             The function applies RCU lock internally.
 456         */
 457         template <typename K>
 458         bool find( K const& key )
 459         {
 460             return base_class::find( key );
 461         }
 462
 463         /// Finds the key \p val using \p pred predicate for searching
 464         /**
 465             The function is an analog of \p find(K const&)
 466             but \p pred is used for key comparing.
 467             \p Less functor has the interface like \p std::less.
 468             \p Less must imply the same element order as the comparator used for building the map.
 469         */
 470         template <typename K, typename Less>
 471         bool find_with( K const& key, Less pred )
 472         {
 473             return base_class::find_with( key, pred );
 474         }
 475
 476         /// Clears the map
 477         void clear()
 478         {
 479             base_class::clear();
 480         }
 481
 482         /// Checks if the map is empty
 483         bool empty() const
 484         {
 485             return base_class::empty();
 486         }
 487
 488         /// Returns item count in the map
 489         /**
 490             Only leaf nodes containing user data are counted.
 491
 492             The value returned depends on item counter type provided by \p Traits template parameter.
 493             If it is \p atomicity::empty_item_counter this function always returns 0.
 494
 495             The function is not suitable for checking the tree emptiness, use \p empty()
 496             member function for this purpose.
 497         */
 498         size_t size() const
 499         {
 500             return base_class::size();
 501         }
 502
 503         /// Returns const reference to internal statistics
 504         stat const& statistics() const
 505         {
 506             return base_class::statistics();
 507         }
 508
 509         /// Checks internal consistency (not atomic, not thread-safe)
 510         /**
 511             The debugging function to check internal consistency of the tree.
 512         */
 513         bool check_consistency() const
 514         {
 515             return base_class::check_consistency();
 516         }
 517     };
 518 }} // namespace cds::container
 519
 520 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H