cds/container/feldman_hashset_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
   4 #define CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
   5
   6 #include <cds/intrusive/feldman_hashset_rcu.h>
   7 #include <cds/container/details/feldman_hashset_base.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Hash set based on multi-level array, \ref cds_urcu_desc "RCU" specialization
  12     /** @ingroup cds_nonintrusive_set
  13         @anchor cds_container_FeldmanHashSet_rcu
  14
  15         Source:
  16         - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
  17                  Wait-free Extensible Hash Maps"
  18
  19         See algorithm short description @ref cds_intrusive_FeldmanHashSet_hp "here"
  20
  21         @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
  22         - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
  23           Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
  24           <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
  25           or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
  26           converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
  27         - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
  28           have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
  29           it maintains its fixed-size hash value.
  30
  31         The set supports @ref cds_container_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
  32
  33         Template parameters:
  34         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  35         - \p T - a value type to be stored in the set
  36         - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
  37             \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
  38             to hash value of \p T. The set algorithm does not calculate that hash value.
  39
  40             @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
  41             see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  42
  43             The set supports @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional thread-safe iterators"
  44             with some restrictions.
  45     */
  46     template <
  47         class RCU
  48         , typename T
  49 #ifdef CDS_DOXYGEN_INVOKED
  50         , class Traits = feldman_hashset::traits
  51 #else
  52         , class Traits
  53 #endif
  54     >
  55     class FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
  56 #ifdef CDS_DOXYGEN_INVOKED
  57         : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
  58 #else
  59         : protected cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits >::type
  60 #endif
  61     {
  62         //@cond
  63         typedef cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits > maker;
  64         typedef typename maker::type base_class;
  65         //@endcond
  66
  67     public:
  68         typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
  69         typedef T       value_type; ///< type of value stored in the set
  70         typedef Traits  traits;     ///< Traits template parameter, see \p feldman_hashset::traits
  71
  72         typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
  73         typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
  74         typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
  75
  76         typedef typename traits::item_counter   item_counter;   ///< Item counter type
  77         typedef typename traits::allocator      allocator;      ///< Element allocator
  78         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
  79         typedef typename traits::memory_model   memory_model;   ///< Memory model
  80         typedef typename traits::back_off       back_off;       ///< Backoff strategy
  81         typedef typename traits::stat           stat;           ///< Internal statistics type
  82         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
  83         typedef typename gc::scoped_lock       rcu_lock;        ///< RCU scoped lock
  84         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
  85         typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node
  86
  87         typedef typename base_class::iterator               iterator;       ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional iterator" type
  88         typedef typename base_class::const_iterator         const_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional const iterator" type
  89         typedef typename base_class::reverse_iterator       reverse_iterator;       ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse iterator" type
  90         typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse const iterator" type
  91
  92     protected:
  93         //@cond
  94         typedef typename maker::cxx_node_allocator cxx_node_allocator;
  95         typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
  96         //@endcond
  97
  98     public:
  99         /// Creates empty set
 100         /**
 101             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 102             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 103
 104             Equation for \p head_bits and \p array_bits:
 105             \code
 106             sizeof(hash_type) * 8 == head_bits + N * array_bits
 107             \endcode
 108             where \p N is multi-level array depth.
 109         */
 110         FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
 111             : base_class( head_bits, array_bits )
 112         {}
 113
 114         /// Destructs the set and frees all data
 115         ~FeldmanHashSet()
 116         {}
 117
 118         /// Inserts new element
 119         /**
 120             The function creates an element with copy of \p val value and then inserts it into the set.
 121
 122             The type \p Q should contain as minimum the complete hash for the element.
 123             The object of \ref value_type should be constructible from a value of type \p Q.
 124             In trivial case, \p Q is equal to \ref value_type.
 125
 126             Returns \p true if \p val is inserted into the set, \p false otherwise.
 127
 128             The function locks RCU internally.
 129         */
 130         template <typename Q>
 131         bool insert( Q const& val )
 132         {
 133             scoped_node_ptr sp( cxx_node_allocator().New( val ));
 134             if ( base_class::insert( *sp )) {
 135                 sp.release();
 136                 return true;
 137             }
 138             return false;
 139         }
 140
 141         /// Inserts new element
 142         /**
 143             The function allows to split creating of new item into two part:
 144             - create item with key only
 145             - insert new item into the set
 146             - if inserting is success, calls \p f functor to initialize value-fields of \p val.
 147
 148             The functor signature is:
 149             \code
 150                 void func( value_type& val );
 151             \endcode
 152             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 153             \p val no any other changes could be made on this set's item by concurrent threads.
 154             The user-defined functor is called only if the inserting is success.
 155
 156             The function locks RCU internally.
 157         */
 158         template <typename Q, typename Func>
 159         bool insert( Q const& val, Func f )
 160         {
 161             scoped_node_ptr sp( cxx_node_allocator().New( val ));
 162             if ( base_class::insert( *sp, f )) {
 163                 sp.release();
 164                 return true;
 165             }
 166             return false;
 167         }
 168
 169         /// Updates the element
 170         /**
 171             The operation performs inserting or replacing with lock-free manner.
 172
 173             If the \p val key not found in the set, then the new item created from \p val
 174             will be inserted into the set iff \p bInsert is \p true.
 175             Otherwise, if \p val is found, it is replaced with new item created from \p val
 176             and previous item is disposed.
 177             In both cases \p func functor is called.
 178
 179             The functor \p Func signature:
 180             \code
 181                 struct my_functor {
 182                     void operator()( value_type& cur, value_type * prev );
 183                 };
 184             \endcode
 185             where:
 186             - \p cur - current element
 187             - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
 188                  if \p cur was just inserted.
 189
 190             The functor may change non-key fields of the \p item; however, \p func must guarantee
 191             that during changing no any other modifications could be made on this item by concurrent threads.
 192
 193             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 194             i.e. the item has been inserted or updated,
 195             \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
 196             already exists.
 197         */
 198         template <typename Q, typename Func>
 199         std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
 200         {
 201             scoped_node_ptr sp( cxx_node_allocator().New( val ));
 202             std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
 203             if ( bRes.first )
 204                 sp.release();
 205             return bRes;
 206         }
 207
 208         /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 209         /**
 210             Returns \p true if inserting successful, \p false otherwise.
 211         */
 212         template <typename... Args>
 213         bool emplace( Args&&... args )
 214         {
 215             scoped_node_ptr sp( cxx_node_allocator().New( std::forward<Args>(args)... ));
 216             if ( base_class::insert( *sp )) {
 217                 sp.release();
 218                 return true;
 219             }
 220             return false;
 221         }
 222
 223         /// Deletes the item from the set
 224         /**
 225             The function searches \p hash in the set,
 226             deletes the item found, and returns \p true.
 227             If that item is not found the function returns \p false.
 228
 229             RCU should not be locked. The function locks RCU internally.
 230         */
 231         bool erase( hash_type const& hash )
 232         {
 233             return base_class::erase( hash );
 234         }
 235
 236         /// Deletes the item from the set
 237         /**
 238             The function searches \p hash in the set,
 239             call \p f functor with item found, and deltes the element from the set.
 240
 241             The \p Func interface is
 242             \code
 243             struct functor {
 244                 void operator()( value_type& item );
 245             };
 246             \endcode
 247
 248             If \p hash is not found the function returns \p false.
 249
 250             RCU should not be locked. The function locks RCU internally.
 251         */
 252         template <typename Func>
 253         bool erase( hash_type const& hash, Func f )
 254         {
 255             return base_class::erase( hash, f );
 256         }
 257
 258         /// Extracts the item with specified \p hash
 259         /**
 260             The function searches \p hash in the set,
 261             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 262             If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
 263
 264             RCU \p synchronize method can be called. RCU should NOT be locked.
 265             The function does not call the disposer for the item found.
 266             The disposer will be implicitly invoked when the returned object is destroyed or when
 267             its \p release() member function is called.
 268             Example:
 269             \code
 270             typedef cds::container::FeldmanHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
 271             set_type theSet;
 272             // ...
 273
 274             typename set_type::exempt_ptr ep( theSet.extract( 5 ));
 275             if ( ep ) {
 276                 // Deal with ep
 277                 //...
 278
 279                 // Dispose returned item.
 280                 ep.release();
 281             }
 282             \endcode
 283         */
 284         exempt_ptr extract( hash_type const& hash )
 285         {
 286             return base_class::extract( hash );
 287         }
 288
 289         /// Finds an item by it's \p hash
 290         /**
 291             The function searches the item by \p hash and calls the functor \p f for item found.
 292             The interface of \p Func functor is:
 293             \code
 294             struct functor {
 295                 void operator()( value_type& item );
 296             };
 297             \endcode
 298             where \p item is the item found.
 299
 300             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 301             that \p item cannot be disposed during the functor is executing.
 302             The functor does not serialize simultaneous access to the set's \p item. If such access is
 303             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 304
 305             The function returns \p true if \p hash is found, \p false otherwise.
 306         */
 307         template <typename Func>
 308         bool find( hash_type const& hash, Func f )
 309         {
 310             return base_class::find( hash, f );
 311         }
 312
 313         /// Checks whether the set contains \p hash
 314         /**
 315             The function searches the item by its \p hash
 316             and returns \p true if it is found, or \p false otherwise.
 317         */
 318         bool contains( hash_type const& hash )
 319         {
 320             return base_class::contains( hash );
 321         }
 322
 323         /// Finds an item by it's \p hash and returns the item found
 324         /**
 325             The function searches the item by its \p hash
 326             and returns the pointer to the item found.
 327             If \p hash is not found the function returns \p nullptr.
 328
 329             RCU should be locked before the function invocation.
 330             Returned pointer is valid only while RCU is locked.
 331
 332             Usage:
 333             \code
 334             typedef cds::container::FeldmanHashSet< your_template_params >  my_set;
 335             my_set theSet;
 336             // ...
 337             {
 338                 // lock RCU
 339                 my_set::rcu_lock;
 340
 341                 foo * p = theSet.get( 5 );
 342                 if ( p ) {
 343                     // Deal with p
 344                     //...
 345                 }
 346             }
 347             \endcode
 348         */
 349         value_type * get( hash_type const& hash )
 350         {
 351             return base_class::get( hash );
 352         }
 353
 354         /// Clears the set (non-atomic)
 355         /**
 356             The function unlink all data node from the set.
 357             The function is not atomic but is thread-safe.
 358             After \p %clear() the set may not be empty because another threads may insert items.
 359         */
 360         void clear()
 361         {
 362             base_class::clear();
 363         }
 364
 365         /// Checks if the set is empty
 366         /**
 367             Emptiness is checked by item counting: if item count is zero then the set is empty.
 368             Thus, the correct item counting feature is an important part of the set implementation.
 369         */
 370         bool empty() const
 371         {
 372             return base_class::empty();
 373         }
 374
 375         /// Returns item count in the set
 376         size_t size() const
 377         {
 378             return base_class::size();
 379         }
 380
 381         /// Returns const reference to internal statistics
 382         stat const& statistics() const
 383         {
 384             return base_class::statistics();
 385         }
 386
 387         /// Returns the size of head node
 388         size_t head_size() const
 389         {
 390             return base_class::head_size();
 391         }
 392
 393         /// Returns the size of the array node
 394         size_t array_node_size() const
 395         {
 396             return base_class::array_node_size();
 397         }
 398
 399     public:
 400         ///@name Thread-safe iterators
 401         /** @anchor cds_container_FeldmanHashSet_rcu_iterators
 402             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment
 403             under explicit RCU lock.
 404             RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
 405             since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
 406             while your thread is iterating.
 407
 408             A typical example is:
 409             \code
 410             struct foo {
 411                 uint32_t    hash;
 412                 // ... other fields
 413                 uint32_t    payload; // only for example
 414             };
 415             struct set_traits: cds::container::feldman_hashset::traits
 416             {
 417                 struct hash_accessor {
 418                     uint32_t operator()( foo const& src ) const
 419                     {
 420                         retur src.hash;
 421                     }
 422                 };
 423             };
 424
 425             typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
 426             typedef cds::container::FeldmanHashSet< rcu, foo, set_traits > set_type;
 427
 428             set_type s;
 429
 430             // ...
 431
 432             // iterate over the set
 433             {
 434                 // lock the RCU.
 435                 typename set_type::rcu_lock l; // scoped RCU lock
 436
 437                 // traverse the set
 438                 for ( auto i = s.begin(); i != s.end(); ++i ) {
 439                     // deal with i. Remember, erasing is prohibited here!
 440                     i->payload++;
 441                 }
 442             } // at this point RCU lock is released
 443             /endcode
 444
 445             Each iterator object supports the common interface:
 446             - dereference operators:
 447                 @code
 448                 value_type [const] * operator ->() noexcept
 449                 value_type [const] & operator *() noexcept
 450                 @endcode
 451             - pre-increment and pre-decrement. Post-operators is not supported
 452             - equality operators <tt>==</tt> and <tt>!=</tt>.
 453                 Iterators are equal iff they point to the same cell of the same array node.
 454                 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
 455                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 456
 457             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 458             in an array node that is being splitted.
 459         */
 460     ///@{
 461
 462         /// Returns an iterator to the beginning of the set
 463         iterator begin()
 464         {
 465             return base_class::begin();
 466         }
 467
 468         /// Returns an const iterator to the beginning of the set
 469         const_iterator begin() const
 470         {
 471             return base_class::begin();
 472         }
 473
 474         /// Returns an const iterator to the beginning of the set
 475         const_iterator cbegin()
 476         {
 477             return base_class::cbegin();
 478         }
 479
 480         /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 481         iterator end()
 482         {
 483             return base_class::end();
 484         }
 485
 486         /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 487         const_iterator end() const
 488         {
 489             return base_class::end();
 490         }
 491
 492         /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 493         const_iterator cend()
 494         {
 495             return base_class::cend();
 496         }
 497
 498         /// Returns a reverse iterator to the first element of the reversed set
 499         reverse_iterator rbegin()
 500         {
 501             return base_class::rbegin();
 502         }
 503
 504         /// Returns a const reverse iterator to the first element of the reversed set
 505         const_reverse_iterator rbegin() const
 506         {
 507             return base_class::rbegin();
 508         }
 509
 510         /// Returns a const reverse iterator to the first element of the reversed set
 511         const_reverse_iterator crbegin()
 512         {
 513             return base_class::crbegin();
 514         }
 515
 516         /// Returns a reverse iterator to the element following the last element of the reversed set
 517         /**
 518             It corresponds to the element preceding the first element of the non-reversed container.
 519             This element acts as a placeholder, attempting to access it results in undefined behavior.
 520         */
 521         reverse_iterator rend()
 522         {
 523             return base_class::rend();
 524         }
 525
 526         /// Returns a const reverse iterator to the element following the last element of the reversed set
 527         /**
 528             It corresponds to the element preceding the first element of the non-reversed container.
 529             This element acts as a placeholder, attempting to access it results in undefined behavior.
 530         */
 531         const_reverse_iterator rend() const
 532         {
 533             return base_class::rend();
 534         }
 535
 536         /// Returns a const reverse iterator to the element following the last element of the reversed set
 537         /**
 538             It corresponds to the element preceding the first element of the non-reversed container.
 539             This element acts as a placeholder, attempting to access it results in undefined behavior.
 540         */
 541         const_reverse_iterator crend()
 542         {
 543             return base_class::crend();
 544         }
 545     ///@}
 546     };
 547
 548 }} // namespace cds::container
 549
 550 #endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H