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     protected:
 108         //@cond
 109         typedef typename base_class::node_type  node_type;
 110         typedef typename base_class::node_scoped_lock node_scoped_lock;
 111         typedef typename maker::cxx_allocator   cxx_allocator;
 112
 113         using base_class::update_flags;
 114         //@endcond
 115
 116     public:
 117         /// Creates empty map
 118         BronsonAVLTreeMap()
 119         {}
 120
 121         /// Destroys the map
 122         ~BronsonAVLTreeMap()
 123         {}
 124
 125         /// Inserts new node with \p key and default value
 126         /**
 127             The function creates a node with \p key and default value, and then inserts the node created into the map.
 128
 129             Preconditions:
 130             - The \p key_type should be constructible from a value of type \p K.
 131             - The \p mapped_type should be default-constructible.
 132
 133             RCU \p synchronize() can be called. RCU should not be locked.
 134
 135             Returns \p true if inserting successful, \p false otherwise.
 136         */
 137         template <typename K>
 138         bool insert( K const& key )
 139         {
 140             return base_class::do_update(key, key_comparator(),
 141                 []( node_type * pNode ) -> mapped_type*
 142                 {
 143                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 144                     return cxx_allocator().New();
 145                 },
 146                 update_flags::allow_insert
 147             ) == update_flags::result_insert;
 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                     return cxx_allocator().New( val );
 171                 },
 172                 update_flags::allow_insert
 173             ) == update_flags::result_insert;
 174         }
 175
 176         /// Inserts new node and initialize it by a functor
 177         /**
 178             This function inserts new node with key \p key and if inserting is successful then it calls
 179             \p func functor with signature
 180             \code
 181                 struct functor {
 182                     void operator()( mapped_type& item );
 183                 };
 184             \endcode
 185
 186             The key_type should be constructible from value of type \p K.
 187
 188             The function allows to split creating of new item into two part:
 189             - create item from \p key;
 190             - insert new item into the map;
 191             - if inserting is successful, initialize the value of item by calling \p func functor
 192
 193             This can be useful if complete initialization of object of \p value_type is heavyweight and
 194             it is preferable that the initialization should be completed only if inserting is successful.
 195             The functor is called under the node lock.
 196
 197             RCU \p synchronize() method can be called. RCU should not be locked.
 198         */
 199         template <typename K, typename Func>
 200         bool insert_with( K const& key, Func func )
 201         {
 202             return base_class::do_update( key, key_comparator(),
 203                 [&func]( node_type * pNode ) -> mapped_type*
 204                 {
 205                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 206                     mapped_type * pVal = cxx_allocator().New();
 207                     func( *pVal );
 208                     return pVal;
 209                 },
 210                 update_flags::allow_insert
 211             ) == update_flags::result_insert;
 212         }
 213
 214         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
 215         /**
 216             Returns \p true if inserting successful, \p false otherwise.
 217
 218             RCU \p synchronize() method can be called. RCU should not be locked.
 219         */
 220         template <typename K, typename... Args>
 221         bool emplace( K&& key, Args&&... args )
 222         {
 223             return base_class::do_update( key, key_comparator(),
 224                 [&]( node_type * pNode ) -> mapped_type*
 225                 {
 226                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 227                     return cxx_allocator().New( std::forward<Args>(args)...);
 228                 },
 229                 update_flags::allow_insert
 230             ) == update_flags::result_insert;
 231         }
 232
 233         /// Ensures that the \p key exists in the map
 234         /**
 235             The operation performs inserting or changing data with lock-free manner.
 236
 237             If the \p key not found in the map, then the new item created from \p key
 238             is inserted into the map (note that in this case the \ref key_type should be
 239             constructible from type \p K).
 240             Otherwise, the functor \p func is called with item found.
 241             The functor \p Func may be a functor:
 242             \code
 243                 struct my_functor {
 244                     void operator()( bool bNew, mapped_type& item );
 245                 };
 246             \endcode
 247
 248             with arguments:
 249             - \p bNew - \p true if the item has been inserted, \p false otherwise
 250             - \p item - value
 251
 252             The functor may change any fields of the \p item. The functor is called under the node lock.
 253
 254             RCU \p synchronize() method can be called. RCU should not be locked.
 255
 256             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 257             \p second is \p true if new item has been added or \p false if the item with \p key
 258             already is in the tree.
 259         */
 260         template <typename K, typename Func>
 261         std::pair<bool, bool> update( K const& key, Func func )
 262         {
 263             int result = base_class::do_update( key, key_comparator(),
 264                 [&func]( node_type * pNode ) -> mapped_type*
 265                 {
 266                     mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed ));
 267                     if ( !pVal ) {
 268                         pVal = cxx_allocator().New();
 269                         func( true, *pVal );
 270                     }
 271                     else
 272                         func( false, *pVal );
 273                     return pVal;
 274                 },
 275                 update_flags::allow_insert | update_flags::allow_update
 276             );
 277             return std::make_pair( result != 0, (result & update_flags::result_insert) != 0 );
 278         }
 279
 280         /// Delete \p key from the map
 281         /**
 282             RCU \p synchronize() method can be called. RCU should not be locked.
 283
 284             Return \p true if \p key is found and deleted, \p false otherwise
 285         */
 286         template <typename K>
 287         bool erase( K const& key )
 288         {
 289             //TODO
 290         }
 291
 292         /// Deletes the item from the map using \p pred predicate for searching
 293         /**
 294             The function is an analog of \p erase(K const&)
 295             but \p pred is used for key comparing.
 296             \p Less functor has the interface like \p std::less.
 297             \p Less must imply the same element order as the comparator used for building the map.
 298         */
 299         template <typename K, typename Less>
 300         bool erase_with( K const& key, Less pred )
 301         {
 302             CDS_UNUSED( pred );
 303             //TODO
 304         }
 305
 306         /// Delete \p key from the map
 307         /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
 308
 309             The function searches an item with key \p key, calls \p f functor
 310             and deletes the item. If \p key is not found, the functor is not called.
 311
 312             The functor \p Func interface:
 313             \code
 314             struct extractor {
 315                 void operator()(mapped_type& item) { ... }
 316             };
 317             \endcode
 318
 319             RCU \p synchronize method can be called. RCU should not be locked.
 320
 321             Return \p true if key is found and deleted, \p false otherwise
 322         */
 323         template <typename K, typename Func>
 324         bool erase( K const& key, Func f )
 325         {
 326             //TODO
 327         }
 328
 329         /// Deletes the item from the map using \p pred predicate for searching
 330         /**
 331             The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
 332             but \p pred is used for key comparing.
 333             \p Less functor has the interface like \p std::less.
 334             \p Less must imply the same element order as the comparator used for building the map.
 335         */
 336         template <typename K, typename Less, typename Func>
 337         bool erase_with( K const& key, Less pred, Func f )
 338         {
 339             CDS_UNUSED( pred );
 340             //TODO
 341         }
 342
 343         /// Extracts an item with minimal key from the map
 344         /**
 345             Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the leftmost item.
 346             If the set is empty, returns empty \p exempt_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 release() member function is called.
 357         */
 358         exempt_ptr extract_min()
 359         {
 360             //TODO
 361         }
 362
 363         /// Extracts an item with maximal key from the map
 364         /**
 365             Returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the rightmost item.
 366             If the set is empty, returns empty \p exempt_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 release() is called.
 377             @note Before reusing \p result object you should call its \p release() method.
 378         */
 379         exempt_ptr extract_max()
 380         {
 381             //TODO
 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 \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to an item found.
 388             If \p key is not found the function returns an empty \p exempt_ptr.
 389
 390             RCU \p synchronize method can be called. RCU should NOT be locked.
 391             The function does not destroy the item found.
 392             The dealloctor will be implicitly invoked when the returned object is destroyed or when
 393             its \p release() member function is called.
 394         */
 395         template <typename Q>
 396         exempt_ptr extract( Q const& key )
 397         {
 398             //TODO
 399         }
 400
 401         /// Extracts an item from the map using \p pred for searching
 402         /**
 403             The function is an analog of \p extract(exempt_ptr&, 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         exempt_ptr extract_with( Q const& val, Less pred )
 411         {
 412             CDS_UNUSED( pred );
 413             //TODO
 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         /// Finds \p key and return the item found
 478         /**
 479             The function searches the item with key equal to \p key and returns the pointer to item found.
 480             If \p key is not found it returns \p nullptr.
 481
 482             RCU should be locked before call the function.
 483             Returned pointer is valid while RCU is locked.
 484         */
 485         template <typename Q>
 486         mapped_type * get( Q const& key ) const
 487         {
 488             //TODO
 489         }
 490
 491         /// Finds \p key with \p pred predicate and return the item found
 492         /**
 493             The function is an analog of \p get(Q const&)
 494             but \p pred is used for comparing the keys.
 495
 496             \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type
 497             and \p Q in any order.
 498             \p pred must imply the same element order as the comparator used for building the map.
 499         */
 500         template <typename Q, typename Less>
 501         mapped_type * get_with( Q const& key, Less pred ) const
 502         {
 503             CDS_UNUSED( pred );
 504             //TODO
 505         }
 506
 507         /// Clears the map
 508         void clear()
 509         {
 510             base_class::clear();
 511         }
 512
 513         /// Checks if the map is empty
 514         bool empty() const
 515         {
 516             return base_class::empty();
 517         }
 518
 519         /// Returns item count in the map
 520         /**
 521             Only leaf nodes containing user data are counted.
 522
 523             The value returned depends on item counter type provided by \p Traits template parameter.
 524             If it is \p atomicity::empty_item_counter this function always returns 0.
 525
 526             The function is not suitable for checking the tree emptiness, use \p empty()
 527             member function for this purpose.
 528         */
 529         size_t size() const
 530         {
 531             return base_class::size();
 532         }
 533
 534         /// Returns const reference to internal statistics
 535         stat const& statistics() const
 536         {
 537             return base_class::statistics();
 538         }
 539
 540         /// Checks internal consistency (not atomic, not thread-safe)
 541         /**
 542             The debugging function to check internal consistency of the tree.
 543         */
 544         bool check_consistency() const
 545         {
 546             return base_class::check_consistency();
 547         }
 548
 549     };
 550 }} // namespace cds::container
 551
 552 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H