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