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