cds/intrusive/michael_set_rcu.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_RCU_H
  32 #define CDSLIB_INTRUSIVE_MICHAEL_SET_RCU_H
  33
  34 #include <cds/intrusive/details/michael_set_base.h>
  35
  36 namespace cds { namespace intrusive {
  37
  38     /// Michael's hash set, \ref cds_urcu_desc "RCU" specialization
  39     /** @ingroup cds_intrusive_map
  40         \anchor cds_intrusive_MichaelHashSet_rcu
  41
  42         Source:
  43             - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
  44
  45         Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
  46         The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
  47         to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
  48         However, each bucket may contain unbounded number of items.
  49
  50         Template parameters are:
  51         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  52         - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
  53             The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
  54             schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
  55             the ordered list.
  56         - \p Traits - type traits, default is \p michael_set::traits.
  57             Instead of defining \p Traits struct you can use option-based syntax with \p michael_set::make_traits metafunction.
  58
  59         \par Usage
  60             Before including <tt><cds/intrusive/michael_set_rcu.h></tt> you should include appropriate RCU header file,
  61             see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  62             For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
  63             \code
  64             #include <cds/urcu/general_buffered.h>
  65             #include <cds/intrusive/michael_list_rcu.h>
  66             #include <cds/intrusive/michael_set_rcu.h>
  67
  68             struct Foo { ... };
  69             // Hash functor for struct Foo
  70             struct foo_hash {
  71                 size_t operator()( Foo const& foo ) const { return ... }
  72             };
  73
  74             // Now, you can declare Michael's list for type Foo and default traits:
  75             typedef cds::intrusive::MichaelList<cds::urcu::gc< general_buffered<> >, Foo > rcu_michael_list;
  76
  77             // Declare Michael's set with MichaelList as bucket type
  78             typedef cds::intrusive::MichaelSet<
  79                 cds::urcu::gc< general_buffered<> >,
  80                 rcu_michael_list,
  81                 cds::intrusive::michael_set::make_traits<
  82                     cds::opt::::hash< foo_hash >
  83                 >::type
  84             > rcu_michael_set;
  85
  86             // Declares hash set for 1000000 items with load factor 2
  87             rcu_michael_set theSet( 1000000, 2 );
  88
  89             // Now you can use theSet object in many threads without any synchronization.
  90             \endcode
  91     */
  92     template <
  93         class RCU,
  94         class OrderedList,
  95 #ifdef CDS_DOXYGEN_INVOKED
  96         class Traits = michael_set::traits
  97 #else
  98         class Traits
  99 #endif
 100     >
 101     class MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
 102     {
 103     public:
 104         typedef cds::urcu::gc< RCU > gc;            ///< RCU schema
 105         typedef OrderedList          ordered_list;  ///< type of ordered list used as a bucket implementation
 106         typedef Traits               traits;        ///< Set traits
 107
 108         typedef typename ordered_list::value_type     value_type;       ///< type of value stored in the list
 109         typedef typename ordered_list::key_comparator key_comparator;   ///< key comparing functor
 110         typedef typename ordered_list::disposer       disposer;         ///< Node disposer functor
 111 #ifdef CDS_DOXYGEN_INVOKED
 112         typedef typename ordered_list::stat           stat;             ///< Internal statistics
 113 #endif
 114
 115         /// Hash functor for \ref value_type and all its derivatives that you use
 116         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
 117         typedef typename traits::item_counter item_counter;   ///< Item counter type
 118         typedef typename traits::allocator    allocator;      ///< Bucket table allocator
 119
 120         typedef typename ordered_list::rcu_lock    rcu_lock;   ///< RCU scoped lock
 121         /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
 122         static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
 123
 124         // GC and OrderedList::gc must be the same
 125         static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 126
 127         // atomicity::empty_item_counter is not allowed as a item counter
 128         static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
 129             "atomicity::empty_item_counter is not allowed as a item counter");
 130
 131     protected:
 132         //@cond
 133         typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
 134
 135         typedef typename ordered_list::template rebind_traits<
 136             cds::opt::item_counter< cds::atomicity::empty_item_counter >
 137             , cds::opt::stat< typename bucket_stat::wrapped_stat >
 138         >::type internal_bucket_type;
 139
 140         typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
 141         //@endcond
 142
 143     public:
 144         typedef typename internal_bucket_type::exempt_ptr  exempt_ptr; ///< pointer to extracted node
 145         typedef typename internal_bucket_type::raw_ptr     raw_ptr;    ///< Return type of \p get() member function and its derivatives
 146
 147         //@cond
 148         typedef typename bucket_stat::stat stat;
 149         //@endcond
 150
 151     private:
 152         //@cond
 153         hash                    m_HashFunctor;   ///< Hash functor
 154         size_t const            m_nHashBitmask;
 155         internal_bucket_type*   m_Buckets;       ///< bucket table
 156         item_counter            m_ItemCounter;   ///< Item counter
 157         stat                    m_Stat;          ///< Internal statistics
 158         //@endcond
 159
 160     public:
 161     ///@name Forward iterators (thread-safe under RCU lock)
 162     //@{
 163         /// Forward iterator
 164         /**
 165             The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
 166             - it has no post-increment operator
 167             - it iterates items in unordered fashion
 168
 169             You may safely use iterators in multi-threaded environment only under RCU lock.
 170             Otherwise, a crash is possible if another thread deletes the element the iterator points to.
 171
 172             The iterator interface:
 173             \code
 174             class iterator {
 175             public:
 176                 // Default constructor
 177                 iterator();
 178
 179                 // Copy construtor
 180                 iterator( iterator const& src );
 181
 182                 // Dereference operator
 183                 value_type * operator ->() const;
 184
 185                 // Dereference operator
 186                 value_type& operator *() const;
 187
 188                 // Preincrement operator
 189                 iterator& operator ++();
 190
 191                 // Assignment operator
 192                 iterator& operator = (iterator const& src);
 193
 194                 // Equality operators
 195                 bool operator ==(iterator const& i ) const;
 196                 bool operator !=(iterator const& i ) const;
 197             };
 198             \endcode
 199         */
 200         typedef michael_set::details::iterator< internal_bucket_type, false >    iterator;
 201
 202         /// Const forward iterator
 203         /**
 204             For iterator's features and requirements see \ref iterator
 205         */
 206         typedef michael_set::details::iterator< internal_bucket_type, true >     const_iterator;
 207
 208         /// Returns a forward iterator addressing the first element in a set
 209         /**
 210             For empty set \code begin() == end() \endcode
 211         */
 212         iterator begin()
 213         {
 214             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 215         }
 216
 217         /// Returns an iterator that addresses the location succeeding the last element in a set
 218         /**
 219             Do not use the value returned by <tt>end</tt> function to access any item.
 220             The returned value can be used only to control reaching the end of the set.
 221             For empty set \code begin() == end() \endcode
 222         */
 223         iterator end()
 224         {
 225             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 226         }
 227
 228         /// Returns a forward const iterator addressing the first element in a set
 229         const_iterator begin() const
 230         {
 231             return cbegin();
 232         }
 233
 234         /// Returns a forward const iterator addressing the first element in a set
 235         const_iterator cbegin() const
 236         {
 237             return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
 238         }
 239
 240         /// Returns an const iterator that addresses the location succeeding the last element in a set
 241         const_iterator end() const
 242         {
 243             return cend();
 244         }
 245
 246         /// Returns an const iterator that addresses the location succeeding the last element in a set
 247         const_iterator cend() const
 248         {
 249             return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 250         }
 251     //@}
 252
 253     public:
 254         /// Initialize hash set
 255         /**
 256             The Michael's hash set is an unbounded container, but its hash table is non-expandable.
 257             At construction time you should pass estimated maximum item count and a load factor.
 258             The load factor is average size of one bucket - a small number between 1 and 10.
 259             The bucket is an ordered single-linked list, the complexity of searching in the bucket is linear <tt>O(nLoadFactor)</tt>.
 260             The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
 261         */
 262         MichaelHashSet(
 263             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 264             size_t nLoadFactor      ///< load factor: average size of the bucket
 265         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 266           , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
 267         {
 268             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
 269                 construct_bucket<bucket_stat>( it );
 270         }
 271
 272         /// Clear hash set and destroy it
 273         ~MichaelHashSet()
 274         {
 275             clear();
 276
 277             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
 278                 it->~internal_bucket_type();
 279             bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
 280         }
 281
 282         /// Inserts new node
 283         /**
 284             The function inserts \p val in the set if it does not contain
 285             an item with key equal to \p val.
 286
 287             Returns \p true if \p val is placed into the set, \p false otherwise.
 288         */
 289         bool insert( value_type& val )
 290         {
 291             bool bRet = bucket( val ).insert( val );
 292             if ( bRet )
 293                 ++m_ItemCounter;
 294             return bRet;
 295         }
 296
 297         /// Inserts new node
 298         /**
 299             This function is intended for derived non-intrusive containers.
 300
 301             The function allows to split creating of new item into two part:
 302             - create item with key only
 303             - insert new item into the set
 304             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 305
 306             The functor signature is:
 307             \code
 308                 void func( value_type& val );
 309             \endcode
 310             where \p val is the item inserted.
 311             The user-defined functor is called only if the inserting is success.
 312
 313             @warning For \ref cds_intrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 314             \ref cds_intrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
 315             synchronization.
 316         */
 317         template <typename Func>
 318         bool insert( value_type& val, Func f )
 319         {
 320             bool bRet = bucket( val ).insert( val, f );
 321             if ( bRet )
 322                 ++m_ItemCounter;
 323             return bRet;
 324         }
 325
 326         /// Updates the element
 327         /**
 328             The operation performs inserting or changing data with lock-free manner.
 329
 330             If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
 331             Otherwise, the functor \p func is called with item found.
 332             The functor signature is:
 333             \code
 334                 struct functor {
 335                     void operator()( bool bNew, value_type& item, value_type& val );
 336                 };
 337             \endcode
 338             with arguments:
 339             - \p bNew - \p true if the item has been inserted, \p false otherwise
 340             - \p item - item of the set
 341             - \p val - argument \p val passed into the \p %update() function
 342             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 343             refers to the same thing.
 344
 345             The functor may change non-key fields of the \p item.
 346
 347             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
 348             \p second is \p true if new item has been added or \p false if the item with \p key
 349             already is in the set.
 350
 351             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 352             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 353             synchronization.
 354         */
 355         template <typename Func>
 356         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 357         {
 358             std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
 359             if ( bRet.second )
 360                 ++m_ItemCounter;
 361             return bRet;
 362         }
 363         //@cond
 364         template <typename Func>
 365         CDS_DEPRECATED("ensure() is deprecated, use update()")
 366         std::pair<bool, bool> ensure( value_type& val, Func func )
 367         {
 368             return update( val, func, true );
 369         }
 370         //@endcond
 371
 372         /// Unlinks the item \p val from the set
 373         /**
 374             The function searches the item \p val in the set and unlink it from the set
 375             if it is found and is equal to \p val.
 376
 377             The function returns \p true if success and \p false otherwise.
 378         */
 379         bool unlink( value_type& val )
 380         {
 381             bool bRet = bucket( val ).unlink( val );
 382             if ( bRet )
 383                 --m_ItemCounter;
 384             return bRet;
 385         }
 386
 387         /// Deletes the item from the set
 388         /** \anchor cds_intrusive_MichaelHashSet_rcu_erase
 389             The function searches an item with key equal to \p key in the set,
 390             unlinks it from the set, and returns \p true.
 391             If the item with key equal to \p key is not found the function return \p false.
 392
 393             Note the hash functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 394         */
 395         template <typename Q>
 396         bool erase( Q const& key )
 397         {
 398             if ( bucket( key ).erase( key )) {
 399                 --m_ItemCounter;
 400                 return true;
 401             }
 402             return false;
 403         }
 404
 405         /// Deletes the item from the set using \p pred predicate for searching
 406         /**
 407             The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_erase "erase(Q const&)"
 408             but \p pred is used for key comparing.
 409             \p Less functor has the interface like \p std::less.
 410             \p pred must imply the same element order as the comparator used for building the set.
 411         */
 412         template <typename Q, typename Less>
 413         bool erase_with( Q const& key, Less pred )
 414         {
 415             if ( bucket( key ).erase_with( key, pred )) {
 416                 --m_ItemCounter;
 417                 return true;
 418             }
 419             return false;
 420         }
 421
 422         /// Deletes the item from the set
 423         /** \anchor cds_intrusive_MichaelHashSet_rcu_erase_func
 424             The function searches an item with key equal to \p key in the set,
 425             call \p f functor with item found, and unlinks it from the set.
 426             The \ref disposer specified in \p OrderedList class template parameter is called
 427             by garbage collector \p GC asynchronously.
 428
 429             The \p Func interface is
 430             \code
 431             struct functor {
 432                 void operator()( value_type const& item );
 433             };
 434             \endcode
 435
 436             If the item with key equal to \p key is not found the function return \p false.
 437
 438             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 439         */
 440         template <typename Q, typename Func>
 441         bool erase( const Q& key, Func f )
 442         {
 443             if ( bucket( key ).erase( key, f )) {
 444                 --m_ItemCounter;
 445                 return true;
 446             }
 447             return false;
 448         }
 449
 450         /// Deletes the item from the set using \p pred predicate for searching
 451         /**
 452             The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_erase_func "erase(Q const&)"
 453             but \p pred is used for key comparing.
 454             \p Less functor has the interface like \p std::less.
 455             \p pred must imply the same element order as the comparator used for building the set.
 456         */
 457         template <typename Q, typename Less, typename Func>
 458         bool erase_with( const Q& key, Less pred, Func f )
 459         {
 460             if ( bucket( key ).erase_with( key, pred, f )) {
 461                 --m_ItemCounter;
 462                 return true;
 463             }
 464             return false;
 465         }
 466
 467         /// Extracts an item from the set
 468         /** \anchor cds_intrusive_MichaelHashSet_rcu_extract
 469             The function searches an item with key equal to \p key in the set,
 470             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 471             If the item with the key equal to \p key is not found the function returns an empty \p exempt_ptr.
 472
 473             Depends on \p ordered_list you should or should not lock RCU before calling of this function:
 474             - for the set based on \ref cds_intrusive_MichaelList_rcu "MichaelList" RCU should not be locked
 475             - for the set based on \ref cds_intrusive_LazyList_rcu "LazyList" RCU should be locked
 476
 477             See ordered list implementation for details.
 478
 479             \code
 480             #include <cds/urcu/general_buffered.h>
 481             #include <cds/intrusive/michael_list_rcu.h>
 482             #include <cds/intrusive/michael_set_rcu.h>
 483
 484             typedef cds::urcu::gc< general_buffered<> > rcu;
 485             typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
 486             typedef cds::intrusive::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
 487
 488             rcu_michael_set theSet;
 489             // ...
 490
 491             typename rcu_michael_set::exempt_ptr p;
 492
 493             // For MichaelList we should not lock RCU
 494
 495             // Now, you can apply extract function
 496             // Note that you must not delete the item found inside the RCU lock
 497             p = theSet.extract( 10 )
 498             if ( p ) {
 499                 // do something with p
 500                 ...
 501             }
 502
 503             // We may safely release p here
 504             // release() passes the pointer to RCU reclamation cycle:
 505             // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
 506             p.release();
 507             \endcode
 508         */
 509         template <typename Q>
 510         exempt_ptr extract( Q const& key )
 511         {
 512             exempt_ptr p( bucket( key ).extract( key ) );
 513             if ( p )
 514                 --m_ItemCounter;
 515             return p;
 516         }
 517
 518         /// Extracts an item from the set using \p pred predicate for searching
 519         /**
 520             The function is an analog of \p extract(Q const&) but \p pred is used for key comparing.
 521             \p Less functor has the interface like \p std::less.
 522             \p pred must imply the same element order as the comparator used for building the set.
 523         */
 524         template <typename Q, typename Less>
 525         exempt_ptr extract_with( Q const& key, Less pred )
 526         {
 527             exempt_ptr p( bucket( key ).extract_with( key, pred ) );
 528             if ( p )
 529                 --m_ItemCounter;
 530             return p;
 531         }
 532
 533         /// Checks whether the set contains \p key
 534         /**
 535
 536             The function searches the item with key equal to \p key
 537             and returns \p true if the key is found, and \p false otherwise.
 538
 539             Note the hash functor specified for class \p Traits template parameter
 540             should accept a parameter of type \p Q that can be not the same as \p value_type.
 541         */
 542         template <typename Q>
 543         bool contains( Q const& key )
 544         {
 545             return bucket( key ).contains( key );
 546         }
 547         //@cond
 548         template <typename Q>
 549         CDS_DEPRECATED("use contains()")
 550         bool find( Q const& key )
 551         {
 552             return contains( key );
 553         }
 554         //@endcond
 555
 556         /// Checks whether the set contains \p key using \p pred predicate for searching
 557         /**
 558             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 559             \p Less functor has the interface like \p std::less.
 560             \p Less must imply the same element order as the comparator used for building the set.
 561         */
 562         template <typename Q, typename Less>
 563         bool contains( Q const& key, Less pred )
 564         {
 565             return bucket( key ).contains( key, pred );
 566         }
 567         //@cond
 568         template <typename Q, typename Less>
 569         CDS_DEPRECATED("use contains()")
 570         bool find_with( Q const& key, Less pred )
 571         {
 572             return contains( key, pred );
 573         }
 574         //@endcond
 575
 576         /// Find the key \p key
 577         /** \anchor cds_intrusive_MichaelHashSet_rcu_find_func
 578             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 579             The interface of \p Func functor is:
 580             \code
 581             struct functor {
 582                 void operator()( value_type& item, Q& key );
 583             };
 584             \endcode
 585             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 586
 587             The functor can change non-key fields of \p item.
 588             The functor does not serialize simultaneous access to the set \p item. If such access is
 589             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 590
 591             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 592             can modify both arguments.
 593
 594             Note the hash functor specified for class \p Traits template parameter
 595             should accept a parameter of type \p Q that can be not the same as \p value_type.
 596
 597             The function returns \p true if \p key is found, \p false otherwise.
 598         */
 599         template <typename Q, typename Func>
 600         bool find( Q& key, Func f )
 601         {
 602             return bucket( key ).find( key, f );
 603         }
 604         //@cond
 605         template <typename Q, typename Func>
 606         bool find( Q const& key, Func f )
 607         {
 608             return bucket( key ).find( key, f );
 609         }
 610         //@endcond
 611
 612         /// Finds the key \p key using \p pred predicate for searching
 613         /**
 614             The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_find_func "find(Q&, Func)"
 615             but \p pred is used for key comparing.
 616             \p Less functor has the interface like \p std::less.
 617             \p pred must imply the same element order as the comparator used for building the set.
 618         */
 619         template <typename Q, typename Less, typename Func>
 620         bool find_with( Q& key, Less pred, Func f )
 621         {
 622             return bucket( key ).find_with( key, pred, f );
 623         }
 624         //@cond
 625         template <typename Q, typename Less, typename Func>
 626         bool find_with( Q const& key, Less pred, Func f )
 627         {
 628             return bucket( key ).find_with( key, pred, f );
 629         }
 630         //@endcond
 631
 632         /// Finds the key \p key and return the item found
 633         /** \anchor cds_intrusive_MichaelHashSet_rcu_get
 634             The function searches the item with key equal to \p key and returns the pointer to item found.
 635             If \p key is not found it returns \p nullptr.
 636             Note the type of returned value depends on underlying \p ordered_list.
 637             For details, see documentation of ordered list you use.
 638
 639             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 640
 641             RCU should be locked before call of this function.
 642             Returned item is valid only while RCU is locked:
 643             \code
 644             typedef cds::intrusive::MichaelHashSet< your_template_parameters > hash_set;
 645             hash_set theSet;
 646             // ...
 647             // Result of get() call
 648             typename hash_set::raw_ptr ptr;
 649             {
 650                 // Lock RCU
 651                 hash_set::rcu_lock lock;
 652
 653                 ptr = theSet.get( 5 );
 654                 if ( ptr ) {
 655                     // Deal with ptr
 656                     //...
 657                 }
 658                 // Unlock RCU by rcu_lock destructor
 659                 // ptr can be reclaimed by disposer at any time after RCU has been unlocked
 660             }
 661             \endcode
 662         */
 663         template <typename Q>
 664         raw_ptr get( Q const& key )
 665         {
 666             return bucket( key ).get( key );
 667         }
 668
 669         /// Finds the key \p key and return the item found
 670         /**
 671             The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_get "get(Q const&)"
 672             but \p pred is used for comparing the keys.
 673
 674             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 675             in any order.
 676             \p pred must imply the same element order as the comparator used for building the set.
 677         */
 678         template <typename Q, typename Less>
 679         raw_ptr get_with( Q const& key, Less pred )
 680         {
 681             return bucket( key ).get_with( key, pred );
 682         }
 683
 684         /// Clears the set (non-atomic)
 685         /**
 686             The function unlink all items from the set.
 687             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 688             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 689             <tt> empty() </tt> may return \p true but the set may contain item(s).
 690             Therefore, \p clear may be used only for debugging purposes.
 691
 692             For each item the \p disposer is called after unlinking.
 693         */
 694         void clear()
 695         {
 696             for ( size_t i = 0; i < bucket_count(); ++i )
 697                 m_Buckets[i].clear();
 698             m_ItemCounter.reset();
 699         }
 700
 701
 702         /// Checks if the set is empty
 703         /**
 704             Emptiness is checked by item counting: if item count is zero then the set is empty.
 705             Thus, the correct item counting feature is an important part of Michael's set implementation.
 706         */
 707         bool empty() const
 708         {
 709             return size() == 0;
 710         }
 711
 712         /// Returns item count in the set
 713         size_t size() const
 714         {
 715             return m_ItemCounter;
 716         }
 717
 718         /// Returns the size of hash table
 719         /**
 720             Since %MichaelHashSet cannot dynamically extend the hash table size,
 721             the value returned is an constant depending on object initialization parameters;
 722             see \ref cds_intrusive_MichaelHashSet_hp "MichaelHashSet" for explanation.
 723         */
 724         size_t bucket_count() const
 725         {
 726             return m_nHashBitmask + 1;
 727         }
 728
 729         /// Returns const reference to internal statistics
 730         stat const& statistics() const
 731         {
 732             return m_Stat;
 733         }
 734
 735     private:
 736         //@cond
 737         template <typename Stat>
 738         typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
 739         {
 740             new (bucket) internal_bucket_type;
 741         }
 742
 743         template <typename Stat>
 744         typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
 745         {
 746             new (bucket) internal_bucket_type( m_Stat );
 747         }
 748
 749         /// Calculates hash value of \p key
 750         template <typename Q>
 751         size_t hash_value( Q const& key ) const
 752         {
 753             return m_HashFunctor( key ) & m_nHashBitmask;
 754         }
 755
 756         /// Returns the bucket (ordered list) for \p key
 757         template <typename Q>
 758         internal_bucket_type& bucket( Q const& key )
 759         {
 760             return m_Buckets[hash_value( key )];
 761         }
 762         template <typename Q>
 763         internal_bucket_type const& bucket( Q const& key ) const
 764         {
 765             return m_Buckets[hash_value( key )];
 766         }
 767         //@endcond
 768     };
 769
 770 }} // namespace cds::intrusive
 771
 772 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_NOGC_H