cds/container/michael_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H
   4 #define CDSLIB_CONTAINER_MICHAEL_MAP_H
   5
   6 #include <cds/container/details/michael_map_base.h>
   7 #include <cds/details/allocator.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Michael's hash map
  12     /** @ingroup cds_nonintrusive_map
  13         \anchor cds_nonintrusive_MichaelHashMap_hp
  14
  15         Source:
  16             - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
  17
  18         Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
  19         The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
  20         to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
  21         However, each bucket may contain unbounded number of items.
  22
  23         Template parameters are:
  24         - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
  25             from the \p libcds library.
  26             Note the \p GC must be the same as the GC used for \p OrderedList
  27         - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, \p MichaelKVList
  28             or \p LazyKVList. The ordered list implementation specifies the \p Key and \p Value types stored in the hash-map,
  29             the reclamation schema \p GC used by hash-map, the comparison functor for the type \p Key and other features
  30             specific for the ordered list.
  31         - \p Traits - map traits, default is \p michael_map::traits.
  32             Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction.
  33
  34         Many of the class function take a key argument of type \p K that in general is not \p key_type.
  35         \p key_type and an argument of template type \p K must meet the following requirements:
  36         - \p key_type should be constructible from value of type \p K;
  37         - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
  38             <tt> hash( key_type(key) ) == hash( key ) </tt>
  39         - values of type \p key_type and \p K should be comparable
  40
  41         There are the specializations:
  42         - for \ref cds_urcu_desc "RCU" - declared in <tt>cds/container/michael_map_rcu.h</tt>,
  43             see \ref cds_nonintrusive_MichaelHashMap_rcu "MichaelHashMap<RCU>".
  44         - for \p cds::gc::nogc declared in <tt>cds/container/michael_map_nogc.h</tt>,
  45             see \ref cds_nonintrusive_MichaelHashMap_nogc "MichaelHashMap<gc::nogc>".
  46
  47         <b>Iterators</b>
  48
  49         The class supports a forward iterator (\ref iterator and \ref const_iterator).
  50         The iteration is unordered.
  51         The iterator object is thread-safe: the element pointed by the iterator object is guarded,
  52         so, the element cannot be reclaimed while the iterator object is alive.
  53         However, passing an iterator object between threads is dangerous.
  54
  55         @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
  56         all elements in the set: any concurrent deletion can exclude the element
  57         pointed by the iterator from the set, and your iteration can be terminated
  58         before end of the set. Therefore, such iteration is more suitable for debugging purpose only
  59
  60         Remember, each iterator object requires an additional hazard pointer, that may be
  61         a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of
  62         guards is unlimited).
  63
  64         The iterator class supports the following minimalistic interface:
  65         \code
  66         struct iterator {
  67         // Default ctor
  68         iterator();
  69
  70         // Copy ctor
  71         iterator( iterator const& s);
  72
  73         value_type * operator ->() const;
  74         value_type& operator *() const;
  75
  76         // Pre-increment
  77         iterator& operator ++();
  78
  79         // Copy assignment
  80         iterator& operator = (const iterator& src);
  81
  82         bool operator ==(iterator const& i ) const;
  83         bool operator !=(iterator const& i ) const;
  84         };
  85         \endcode
  86         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
  87
  88         \anchor cds_nonintrusive_MichaelHashMap_how_touse
  89         <b>How to use</b>
  90
  91         Suppose, you want to make \p int to \p int map for Hazard Pointer garbage collector. You should
  92         choose suitable ordered list class that will be used as a bucket for the map; it may be \p MichaelKVList.
  93         \code
  94         #include <cds/container/michael_kvlist_hp.h>    // MichaelKVList for gc::HP
  95         #include <cds/container/michael_map.h>          // MichaelHashMap
  96
  97         // List traits based on std::less predicate
  98         struct list_traits: public cds::container::michael_list::traits
  99         {
 100             typedef std::less<int>      less;
 101         };
 102
 103         // Ordered list
 104         typedef cds::container::MichaelKVList< cds::gc::HP, int, int, list_traits> int2int_list;
 105
 106         // Map traits
 107         struct map_traits: public cds::container::michael_map::traits
 108         {
 109             struct hash {
 110                 size_t operator()( int i ) const
 111                 {
 112                     return cds::opt::v::hash<int>()( i );
 113                 }
 114             }
 115         };
 116
 117         // Your map
 118         typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list, map_traits > int2int_map;
 119
 120         // Now you can use int2int_map class
 121
 122         int main()
 123         {
 124             int2int_map theMap;
 125
 126             theMap.insert( 100 );
 127             ...
 128         }
 129         \endcode
 130
 131         You may use option-based declaration:
 132         \code
 133         #include <cds/container/michael_kvlist_hp.h>    // MichaelKVList for gc::HP
 134         #include <cds/container/michael_map.h>          // MichaelHashMap
 135
 136         // Ordered list
 137         typedef cds::container::MichaelKVList< cds::gc::HP, int, int,
 138             typename cds::container::michael_list::make_traits<
 139                 cds::container::opt::less< std::less<int> >     // item comparator option
 140             >::type
 141         >  int2int_list;
 142
 143         // Map
 144         typedef cds::container::MichaelHashMap< cds::gc::HP, int2int_list,
 145             cds::container::michael_map::make_traits<
 146                 cc::opt::hash< cds::opt::v::hash<int> >
 147             >
 148         > int2int_map;
 149         \endcode
 150     */
 151     template <
 152         class GC,
 153         class OrderedList,
 154 #ifdef CDS_DOXYGEN_INVOKED
 155         class Traits = michael_map::traits
 156 #else
 157         class Traits
 158 #endif
 159     >
 160     class MichaelHashMap
 161     {
 162     public:
 163         typedef GC          gc;          ///< Garbage collector
 164         typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket
 165         typedef Traits      traits;      ///< Map traits
 166
 167         typedef typename bucket_type::key_type    key_type;    ///< key type
 168         typedef typename bucket_type::mapped_type mapped_type; ///< value type
 169         typedef typename bucket_type::value_type  value_type;  ///< key/value pair stored in the map
 170
 171         typedef typename bucket_type::key_comparator key_comparator;  ///< key compare functor
 172
 173         /// Hash functor for \ref key_type and all its derivatives that you use
 174         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
 175         typedef typename traits::item_counter  item_counter;   ///< Item counter type
 176
 177         /// Bucket table allocator
 178         typedef cds::details::Allocator< bucket_type, typename traits::allocator >  bucket_table_allocator;
 179         typedef typename bucket_type::guarded_ptr  guarded_ptr; ///< Guarded pointer
 180
 181         //@cond
 182         typedef cds::container::michael_map::implementation_tag implementation_tag;
 183         //@endcond
 184
 185     protected:
 186         item_counter    m_ItemCounter; ///< Item counter
 187         hash            m_HashFunctor; ///< Hash functor
 188         bucket_type *   m_Buckets;     ///< bucket table
 189
 190     private:
 191         //@cond
 192         const size_t    m_nHashBitmask;
 193         //@endcond
 194
 195     protected:
 196         //@cond
 197         /// Calculates hash value of \p key
 198         template <typename Q>
 199         size_t hash_value( Q const& key ) const
 200         {
 201             return m_HashFunctor( key ) & m_nHashBitmask;
 202         }
 203
 204         /// Returns the bucket (ordered list) for \p key
 205         template <typename Q>
 206         bucket_type&    bucket( Q const& key )
 207         {
 208             return m_Buckets[ hash_value( key ) ];
 209         }
 210         //@endcond
 211
 212     protected:
 213         //@cond
 214         /// Forward iterator
 215         template <bool IsConst>
 216         class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
 217         {
 218             typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >  base_class;
 219             friend class MichaelHashMap;
 220
 221         protected:
 222             typedef typename base_class::bucket_ptr     bucket_ptr;
 223             typedef typename base_class::list_iterator  list_iterator;
 224
 225         public:
 226             /// Value pointer type (const for const_iterator)
 227             typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer   value_ptr;
 228             /// Value reference type (const for const_iterator)
 229             typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
 230
 231             /// Key-value pair pointer type (const for const_iterator)
 232             typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer   pair_ptr;
 233             /// Key-value pair reference type (const for const_iterator)
 234             typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
 235
 236         protected:
 237             iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
 238                 : base_class( it, pFirst, pLast )
 239             {}
 240
 241         public:
 242             /// Default ctor
 243             iterator_type()
 244                 : base_class()
 245             {}
 246
 247             /// Copy ctor
 248             iterator_type( const iterator_type& src )
 249                 : base_class( src )
 250             {}
 251
 252             /// Dereference operator
 253             pair_ptr operator ->() const
 254             {
 255                 assert( base_class::m_pCurBucket != nullptr );
 256                 return base_class::m_itList.operator ->();
 257             }
 258
 259             /// Dereference operator
 260             pair_ref operator *() const
 261             {
 262                 assert( base_class::m_pCurBucket != nullptr );
 263                 return base_class::m_itList.operator *();
 264             }
 265
 266             /// Pre-increment
 267             iterator_type& operator ++()
 268             {
 269                 base_class::operator++();
 270                 return *this;
 271             }
 272
 273             /// Assignment operator
 274             iterator_type& operator = (const iterator_type& src)
 275             {
 276                 base_class::operator =(src);
 277                 return *this;
 278             }
 279
 280             /// Returns current bucket (debug function)
 281             bucket_ptr bucket() const
 282             {
 283                 return base_class::bucket();
 284             }
 285
 286             /// Equality operator
 287             template <bool C>
 288             bool operator ==(iterator_type<C> const& i )
 289             {
 290                 return base_class::operator ==( i );
 291             }
 292             /// Equality operator
 293             template <bool C>
 294             bool operator !=(iterator_type<C> const& i )
 295             {
 296                 return !( *this == i );
 297             }
 298         };
 299         //@endcond
 300
 301     public:
 302         /// Forward iterator
 303         typedef iterator_type< false >    iterator;
 304
 305         /// Const forward iterator
 306         typedef iterator_type< true >     const_iterator;
 307
 308         /// Returns a forward iterator addressing the first element in a map
 309         /**
 310             For empty map \code begin() == end() \endcode
 311         */
 312         iterator begin()
 313         {
 314             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 315         }
 316
 317         /// Returns an iterator that addresses the location succeeding the last element in a map
 318         /**
 319             Do not use the value returned by <tt>end</tt> function to access any item.
 320             The returned value can be used only to control reaching the end of the map.
 321             For empty map \code begin() == end() \endcode
 322         */
 323         iterator end()
 324         {
 325             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 326         }
 327
 328         /// Returns a forward const iterator addressing the first element in a map
 329         //@{
 330         const_iterator begin() const
 331         {
 332             return get_const_begin();
 333         }
 334         const_iterator cbegin() const
 335         {
 336             return get_const_begin();
 337         }
 338         //@}
 339
 340         /// Returns an const iterator that addresses the location succeeding the last element in a map
 341         //@{
 342         const_iterator end() const
 343         {
 344             return get_const_end();
 345         }
 346         const_iterator cend() const
 347         {
 348             return get_const_end();
 349         }
 350         //@}
 351
 352     private:
 353         //@cond
 354         const_iterator get_const_begin() const
 355         {
 356             return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
 357         }
 358         const_iterator get_const_end() const
 359         {
 360             return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 361         }
 362         //@endcond
 363
 364     public:
 365         /// Initializes the map
 366         /** @anchor cds_nonintrusive_MichaelHashMap_hp_ctor
 367             The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
 368             when you create an object.
 369             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
 370             Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
 371             Note, that many popular STL hash map implementation uses load factor 1.
 372
 373             The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
 374         */
 375         MichaelHashMap(
 376             size_t nMaxItemCount,   ///< estimation of max item count in the hash map
 377             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 378         ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 379         {
 380             // GC and OrderedList::gc must be the same
 381             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
 382
 383             // atomicity::empty_item_counter is not allowed as a item counter
 384             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
 385                            "atomicity::empty_item_counter is not allowed as a item counter");
 386
 387             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 388         }
 389
 390         /// Clears hash map and destroys it
 391         ~MichaelHashMap()
 392         {
 393             clear();
 394             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 395         }
 396
 397         /// Inserts new node with key and default value
 398         /**
 399             The function creates a node with \p key and default value, and then inserts the node created into the map.
 400
 401             Preconditions:
 402             - The \p key_type should be constructible from value of type \p K.
 403                 In trivial case, \p K is equal to \p key_type.
 404             - The \p mapped_type should be default-constructible.
 405
 406             Returns \p true if inserting successful, \p false otherwise.
 407         */
 408         template <typename K>
 409         bool insert( const K& key )
 410         {
 411             const bool bRet = bucket( key ).insert( key );
 412             if ( bRet )
 413                 ++m_ItemCounter;
 414             return bRet;
 415         }
 416
 417         /// Inserts new node
 418         /**
 419             The function creates a node with copy of \p val value
 420             and then inserts the node created into the map.
 421
 422             Preconditions:
 423             - The \p key_type should be constructible from \p key of type \p K.
 424             - The \p mapped_type should be constructible from \p val of type \p V.
 425
 426             Returns \p true if \p val is inserted into the map, \p false otherwise.
 427         */
 428         template <typename K, typename V>
 429         bool insert( K const& key, V const& val )
 430         {
 431             const bool bRet = bucket( key ).insert( key, val );
 432             if ( bRet )
 433                 ++m_ItemCounter;
 434             return bRet;
 435         }
 436
 437         /// Inserts new node and initialize it by a functor
 438         /**
 439             This function inserts new node with key \p key and if inserting is successful then it calls
 440             \p func functor with signature
 441             \code
 442                 struct functor {
 443                     void operator()( value_type& item );
 444                 };
 445             \endcode
 446
 447             The argument \p item of user-defined functor \p func is the reference
 448             to the map's item inserted:
 449                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 450                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 451
 452             The user-defined functor is called only if inserting is successful.
 453
 454             The \p key_type should be constructible from value of type \p K.
 455
 456             The function allows to split creating of new item into two part:
 457             - create item from \p key;
 458             - insert new item into the map;
 459             - if inserting is successful, initialize the value of item by calling \p func functor
 460
 461             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 462             it is preferable that the initialization should be completed only if inserting is successful.
 463
 464             @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 465             \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
 466             synchronization.
 467         */
 468         template <typename K, typename Func>
 469         bool insert_with( const K& key, Func func )
 470         {
 471             const bool bRet = bucket( key ).insert_with( key, func );
 472             if ( bRet )
 473                 ++m_ItemCounter;
 474             return bRet;
 475         }
 476
 477         /// Updates data by \p key
 478         /**
 479             The operation performs inserting or replacing the element with lock-free manner.
 480
 481             If the \p key not found in the map, then the new item created from \p key
 482             will be inserted into the map iff \p bAllowInsert is \p true.
 483             (note that in this case the \ref key_type should be constructible from type \p K).
 484             Otherwise, if \p key is found, the functor \p func is called with item found.
 485
 486             The functor \p Func signature is:
 487             \code
 488                 struct my_functor {
 489                     void operator()( bool bNew, value_type& item );
 490                 };
 491             \endcode
 492             with arguments:
 493             - \p bNew - \p true if the item has been inserted, \p false otherwise
 494             - \p item - the item found or inserted
 495
 496             The functor may change any fields of the \p item.second that is \p mapped_type.
 497
 498             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 499             \p second is true if new item has been added or \p false if the item with \p key
 500             already exists.
 501
 502             @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 503             \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
 504             synchronization.
 505         */
 506         template <typename K, typename Func >
 507         std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
 508         {
 509             std::pair<bool, bool> bRet = bucket( key ).update( key, func, bAllowInsert );
 510             if ( bRet.first && bRet.second )
 511                 ++m_ItemCounter;
 512             return bRet;
 513         }
 514         //@cond
 515         // Deprecated
 516         template <typename K, typename Func>
 517         std::pair<bool, bool> ensure( K const& key, Func func )
 518         {
 519             std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
 520             if ( bRet.first && bRet.second )
 521                 ++m_ItemCounter;
 522             return bRet;
 523         }
 524         //@endcond
 525
 526         /// For key \p key inserts data of type \p mapped_type created from \p args
 527         /**
 528             \p key_type should be constructible from type \p K
 529
 530             Returns \p true if inserting successful, \p false otherwise.
 531         */
 532         template <typename K, typename... Args>
 533         bool emplace( K&& key, Args&&... args )
 534         {
 535             const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
 536             if ( bRet )
 537                 ++m_ItemCounter;
 538             return bRet;
 539         }
 540
 541         /// Deletes \p key from the map
 542         /** \anchor cds_nonintrusive_MichaelMap_erase_val
 543
 544             Return \p true if \p key is found and deleted, \p false otherwise
 545         */
 546         template <typename K>
 547         bool erase( K const& key )
 548         {
 549             const bool bRet = bucket( key ).erase( key );
 550             if ( bRet )
 551                 --m_ItemCounter;
 552             return bRet;
 553         }
 554
 555         /// Deletes the item from the map using \p pred predicate for searching
 556         /**
 557             The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_val "erase(K const&)"
 558             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 map.
 561         */
 562         template <typename K, typename Less>
 563         bool erase_with( K const& key, Less pred )
 564         {
 565             const bool bRet = bucket( key ).erase_with( key, pred );
 566             if ( bRet )
 567                 --m_ItemCounter;
 568             return bRet;
 569         }
 570
 571         /// Deletes \p key from the map
 572         /** \anchor cds_nonintrusive_MichaelMap_erase_func
 573
 574             The function searches an item with key \p key, calls \p f functor
 575             and deletes the item. If \p key is not found, the functor is not called.
 576
 577             The functor \p Func interface:
 578             \code
 579             struct extractor {
 580                 void operator()(value_type& item) { ... }
 581             };
 582             \endcode
 583
 584             Return \p true if key is found and deleted, \p false otherwise
 585         */
 586         template <typename K, typename Func>
 587         bool erase( K const& key, Func f )
 588         {
 589             const bool bRet = bucket( key ).erase( key, f );
 590             if ( bRet )
 591                 --m_ItemCounter;
 592             return bRet;
 593         }
 594
 595         /// Deletes the item from the map using \p pred predicate for searching
 596         /**
 597             The function is an analog of \ref cds_nonintrusive_MichaelMap_erase_func "erase(K const&, Func)"
 598             but \p pred is used for key comparing.
 599             \p Less functor has the interface like \p std::less.
 600             \p Less must imply the same element order as the comparator used for building the map.
 601         */
 602         template <typename K, typename Less, typename Func>
 603         bool erase_with( K const& key, Less pred, Func f )
 604         {
 605             const bool bRet = bucket( key ).erase_with( key, pred, f );
 606             if ( bRet )
 607                 --m_ItemCounter;
 608             return bRet;
 609         }
 610
 611         /// Extracts the item with specified \p key
 612         /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
 613             The function searches an item with key equal to \p key,
 614             unlinks it from the set, and returns it as \p guarded_ptr.
 615             If \p key is not found the function returns an empty guarded pointer.
 616
 617             Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
 618
 619             The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
 620             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 621
 622             Usage:
 623             \code
 624             typedef cds::container::MichaelHashMap< your_template_args > michael_map;
 625             michael_map theMap;
 626             // ...
 627             {
 628                 michael_map::guarded_ptr gp( theMap.extract( 5 ));
 629                 if ( gp ) {
 630                     // Deal with gp
 631                     // ...
 632                 }
 633                 // Destructor of gp releases internal HP guard
 634             }
 635             \endcode
 636         */
 637         template <typename K>
 638         guarded_ptr extract( K const& key )
 639         {
 640             guarded_ptr gp( bucket( key ).extract( key ));
 641             if ( gp )
 642                 --m_ItemCounter;
 643             return gp;
 644         }
 645
 646         /// Extracts the item using compare functor \p pred
 647         /**
 648             The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_extract "extract(K const&)"
 649             but \p pred predicate is used for key comparing.
 650
 651             \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
 652             in any order.
 653             \p pred must imply the same element order as the comparator used for building the map.
 654         */
 655         template <typename K, typename Less>
 656         guarded_ptr extract_with( K const& key, Less pred )
 657         {
 658             guarded_ptr gp( bucket( key ).extract_with( key, pred ));
 659             if ( gp )
 660                 --m_ItemCounter;
 661             return gp;
 662         }
 663
 664         /// Finds the key \p key
 665         /** \anchor cds_nonintrusive_MichaelMap_find_cfunc
 666
 667             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 668             The interface of \p Func functor is:
 669             \code
 670             struct functor {
 671                 void operator()( value_type& item );
 672             };
 673             \endcode
 674             where \p item is the item found.
 675
 676             The functor may change \p item.second. Note that the functor is only guarantee
 677             that \p item cannot be disposed during functor is executing.
 678             The functor does not serialize simultaneous access to the map's \p item. If such access is
 679             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 680
 681             The function returns \p true if \p key is found, \p false otherwise.
 682         */
 683         template <typename K, typename Func>
 684         bool find( K const& key, Func f )
 685         {
 686             return bucket( key ).find( key, f );
 687         }
 688
 689         /// Finds the key \p val using \p pred predicate for searching
 690         /**
 691             The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
 692             but \p pred is used for key comparing.
 693             \p Less functor has the interface like \p std::less.
 694             \p Less must imply the same element order as the comparator used for building the map.
 695         */
 696         template <typename K, typename Less, typename Func>
 697         bool find_with( K const& key, Less pred, Func f )
 698         {
 699             return bucket( key ).find_with( key, pred, f );
 700         }
 701
 702         /// Checks whether the map contains \p key
 703         /**
 704             The function searches the item with key equal to \p key
 705             and returns \p true if it is found, and \p false otherwise.
 706         */
 707         template <typename K>
 708         bool contains( K const& key )
 709         {
 710             return bucket( key ).contains( key );
 711         }
 712         //@cond
 713         // Deprecated
 714         template <typename K>
 715         bool find( K const& key )
 716         {
 717             return bucket( key ).contains( key );
 718         }
 719         //@endcond
 720
 721         /// Checks whether the map contains \p key using \p pred predicate for searching
 722         /**
 723             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 724             \p Less functor has the interface like \p std::less.
 725             \p Less must imply the same element order as the comparator used for building the map.
 726         */
 727         template <typename K, typename Less>
 728         bool contains( K const& key, Less pred )
 729         {
 730             return bucket( key ).contains( key, pred );
 731         }
 732         //@cond
 733         // Deprecated
 734         template <typename K, typename Less>
 735         bool find_with( K const& key, Less pred )
 736         {
 737             return bucket( key ).contains( key, pred );
 738         }
 739         //@endcond
 740
 741         /// Finds \p key and return the item found
 742         /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
 743             The function searches the item with key equal to \p key
 744             and returns the guarded pointer to the item found.
 745             If \p key is not found the function returns an empty guarded pointer,
 746
 747             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 748
 749             Usage:
 750             \code
 751             typedef cds::container::MichaeHashMap< your_template_params >  michael_map;
 752             michael_map theMap;
 753             // ...
 754             {
 755                 michael_map::guarded_ptr gp( theMap.get( 5 ));
 756                 if ( gp ) {
 757                     // Deal with gp
 758                     //...
 759                 }
 760                 // Destructor of guarded_ptr releases internal HP guard
 761             }
 762             \endcode
 763
 764             Note the compare functor specified for \p OrderedList template parameter
 765             should accept a parameter of type \p K that can be not the same as \p key_type.
 766         */
 767         template <typename K>
 768         guarded_ptr get( K const& key )
 769         {
 770             return bucket( key ).get( key );
 771         }
 772
 773         /// Finds \p key and return the item found
 774         /**
 775             The function is an analog of \ref cds_nonintrusive_MichaelHashMap_hp_get "get( K const&)"
 776             but \p pred is used for comparing the keys.
 777
 778             \p Less functor has the semantics like \p std::less but should take arguments of type \p key_type and \p K
 779             in any order.
 780             \p pred must imply the same element order as the comparator used for building the map.
 781         */
 782         template <typename K, typename Less>
 783         guarded_ptr get_with( K const& key, Less pred )
 784         {
 785             return bucket( key ).get_with( key, pred );
 786         }
 787
 788         /// Clears the map (not atomic)
 789         void clear()
 790         {
 791             for ( size_t i = 0; i < bucket_count(); ++i )
 792                 m_Buckets[i].clear();
 793             m_ItemCounter.reset();
 794         }
 795
 796         /// Checks if the map is empty
 797         /**
 798             Emptiness is checked by item counting: if item count is zero then the map is empty.
 799             Thus, the correct item counting is an important part of the map implementation.
 800         */
 801         bool empty() const
 802         {
 803             return size() == 0;
 804         }
 805
 806         /// Returns item count in the map
 807         size_t size() const
 808         {
 809             return m_ItemCounter;
 810         }
 811
 812         /// Returns the size of hash table
 813         /**
 814             Since \p %MichaelHashMap cannot dynamically extend the hash table size,
 815             the value returned is an constant depending on object initialization parameters;
 816             see \p MichaelHashMap::MichaelHashMap for explanation.
 817         */
 818         size_t bucket_count() const
 819         {
 820             return m_nHashBitmask + 1;
 821         }
 822     };
 823 }}  // namespace cds::container
 824
 825 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H