cds/container/michael_map_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_MICHAEL_MAP_NOGC_H
   4 #define __CDS_CONTAINER_MICHAEL_MAP_NOGC_H
   5
   6 #include <cds/container/michael_map_base.h>
   7 #include <cds/gc/nogc.h>
   8 #include <cds/details/allocator.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// Michael's hash map (template specialization for gc::nogc)
  13     /** @ingroup cds_nonintrusive_map
  14         \anchor cds_nonintrusive_MichaelHashMap_nogc
  15
  16         This specialization is intended for so-called persistent usage when no item
  17         reclamation may be performed. The class does not support deleting of map item.
  18
  19         See \ref cds_nonintrusive_MichaelHashMap_hp "MichaelHashMap" for description of template parameters.
  20
  21         The interface of the specialization is a little different.
  22     */
  23     template <
  24         class OrderedList,
  25 #ifdef CDS_DOXYGEN_INVOKED
  26         class Traits = michael_map::type_traits
  27 #else
  28         class Traits
  29 #endif
  30     >
  31     class MichaelHashMap<gc::nogc, OrderedList, Traits>
  32     {
  33     public:
  34         typedef OrderedList bucket_type     ;   ///< type of ordered list used as a bucket implementation
  35         typedef Traits      options         ;   ///< Traits template parameters
  36
  37         typedef typename bucket_type::key_type          key_type        ;   ///< key type
  38         typedef typename bucket_type::mapped_type       mapped_type     ;   ///< type of value stored in the list
  39         typedef typename bucket_type::value_type        value_type      ;   ///< Pair used as the some functor's argument
  40
  41         typedef gc::nogc                                gc              ;   ///< No garbage collector
  42         typedef typename bucket_type::key_comparator    key_comparator  ;   ///< key comparison functor
  43
  44         /// Hash functor for \ref key_type and all its derivatives that you use
  45         typedef typename cds::opt::v::hash_selector< typename options::hash >::type   hash;
  46         typedef typename options::item_counter          item_counter    ;   ///< Item counter type
  47
  48         /// Bucket table allocator
  49         typedef cds::details::Allocator< bucket_type, typename options::allocator >  bucket_table_allocator;
  50
  51     protected:
  52         //@cond
  53         typedef typename bucket_type::iterator          bucket_iterator;
  54         typedef typename bucket_type::const_iterator    bucket_const_iterator;
  55         //@endcond
  56
  57     protected:
  58         item_counter    m_ItemCounter   ;   ///< Item counter
  59         hash            m_HashFunctor   ;   ///< Hash functor
  60
  61         bucket_type *   m_Buckets       ;   ///< bucket table
  62
  63     private:
  64         //@cond
  65         const size_t    m_nHashBitmask;
  66         //@endcond
  67
  68     protected:
  69         /// Calculates hash value of \p key
  70         size_t hash_value( key_type const & key ) const
  71         {
  72             return m_HashFunctor( key ) & m_nHashBitmask;
  73         }
  74
  75         /// Returns the bucket (ordered list) for \p key
  76         bucket_type&    bucket( key_type const& key )
  77         {
  78             return m_Buckets[ hash_value( key ) ];
  79         }
  80
  81     protected:
  82             protected:
  83         /// Forward iterator
  84         /**
  85             \p IsConst - constness boolean flag
  86
  87             The forward iterator for Michael's map is based on \p OrderedList forward iterator and has some features:
  88             - it has no post-increment operator, only pre-increment
  89             - it iterates items in unordered fashion
  90         */
  91         template <bool IsConst>
  92         class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
  93         {
  94             //@cond
  95             typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >  base_class;
  96             friend class MichaelHashMap;
  97             //@endcond
  98
  99         protected:
 100             //@cond
 101             //typedef typename base_class::bucket_type    bucket_type;
 102             typedef typename base_class::bucket_ptr     bucket_ptr;
 103             typedef typename base_class::list_iterator  list_iterator;
 104
 105             //typedef typename bucket_type::key_type      key_type;
 106             //@endcond
 107
 108         public:
 109             /// Value pointer type (const for const_iterator)
 110             typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer   value_ptr;
 111             /// Value reference type (const for const_iterator)
 112             typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
 113
 114             /// Key-value pair pointer type (const for const_iterator)
 115             typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer   pair_ptr;
 116             /// Key-value pair reference type (const for const_iterator)
 117             typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
 118
 119         protected:
 120             //@cond
 121             iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
 122                 : base_class( it, pFirst, pLast )
 123             {}
 124             //@endcond
 125
 126         public:
 127             /// Default ctor
 128             iterator_type()
 129                 : base_class()
 130             {}
 131
 132             /// Copy ctor
 133             iterator_type( const iterator_type& src )
 134                 : base_class( src )
 135             {}
 136
 137             /// Dereference operator
 138             pair_ptr operator ->() const
 139             {
 140                 assert( base_class::m_pCurBucket != nullptr );
 141                 return base_class::m_itList.operator ->();
 142             }
 143
 144             /// Dereference operator
 145             pair_ref operator *() const
 146             {
 147                 assert( base_class::m_pCurBucket != nullptr );
 148                 return base_class::m_itList.operator *();
 149             }
 150
 151             /// Pre-increment
 152             iterator_type& operator ++()
 153             {
 154                 base_class::operator++();
 155                 return *this;
 156             }
 157
 158             /// Assignment operator
 159             iterator_type& operator = (const iterator_type& src)
 160             {
 161                 base_class::operator =(src);
 162                 return *this;
 163             }
 164
 165             /// Returns current bucket (debug function)
 166             bucket_ptr bucket() const
 167             {
 168                 return base_class::bucket();
 169             }
 170
 171             /// Equality operator
 172             template <bool C>
 173             bool operator ==(iterator_type<C> const& i )
 174             {
 175                 return base_class::operator ==( i );
 176             }
 177             /// Equality operator
 178             template <bool C>
 179             bool operator !=(iterator_type<C> const& i )
 180             {
 181                 return !( *this == i );
 182             }
 183         };
 184
 185
 186     public:
 187         /// Forward iterator
 188         typedef iterator_type< false >    iterator;
 189
 190         /// Const forward iterator
 191         typedef iterator_type< true >     const_iterator;
 192
 193         /// Returns a forward iterator addressing the first element in a set
 194         /**
 195             For empty set \code begin() == end() \endcode
 196         */
 197         iterator begin()
 198         {
 199             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 200         }
 201
 202         /// Returns an iterator that addresses the location succeeding the last element in a set
 203         /**
 204             Do not use the value returned by <tt>end</tt> function to access any item.
 205             The returned value can be used only to control reaching the end of the set.
 206             For empty set \code begin() == end() \endcode
 207         */
 208         iterator end()
 209         {
 210             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 211         }
 212
 213         /// Returns a forward const iterator addressing the first element in a set
 214         //@{
 215         const_iterator begin() const
 216         {
 217             return get_const_begin();
 218         }
 219         const_iterator cbegin()
 220         {
 221             return get_const_begin();
 222         }
 223         //@}
 224
 225         /// Returns an const iterator that addresses the location succeeding the last element in a set
 226         //@{
 227         const_iterator end() const
 228         {
 229             return get_const_end();
 230         }
 231         const_iterator cend()
 232         {
 233             return get_const_end();
 234         }
 235         //@}
 236
 237     private:
 238         //@{
 239         const_iterator get_const_begin() const
 240         {
 241             return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
 242         }
 243         const_iterator get_const_end() const
 244         {
 245             return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 246         }
 247         //@}
 248
 249     public:
 250         /// Initialize the map
 251         /**
 252             The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
 253             when you create an object.
 254             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
 255             Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
 256             Note, that many popular STL hash map implementation uses load factor 1.
 257
 258             The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
 259         */
 260         MichaelHashMap(
 261             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 262             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 263         ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 264         {
 265             // GC and OrderedList::gc must be the same
 266             static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
 267
 268             // atomicity::empty_item_counter is not allowed as a item counter
 269             static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ),"atomicity::empty_item_counter is not allowed as a item counter");
 270
 271             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 272         }
 273
 274         /// Clear hash set and destroy it
 275         ~MichaelHashMap()
 276         {
 277             clear();
 278             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 279         }
 280
 281         /// Inserts new node with key and default value
 282         /**
 283             The function creates a node with \p key and default value, and then inserts the node created into the map.
 284
 285             Preconditions:
 286             - The \ref key_type should be constructible from value of type \p K.
 287                 In trivial case, \p K is equal to \ref key_type.
 288             - The \ref mapped_type should be default-constructible.
 289
 290             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 291         */
 292         template <typename K>
 293         iterator insert( const K& key )
 294         {
 295             bucket_type& refBucket = bucket( key );
 296             bucket_iterator it = refBucket.insert( key );
 297
 298             if ( it != refBucket.end() ) {
 299                 ++m_ItemCounter;
 300                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 301             }
 302
 303             return end();
 304         }
 305
 306         /// Inserts new node
 307         /**
 308             The function creates a node with copy of \p val value
 309             and then inserts the node created into the map.
 310
 311             Preconditions:
 312             - The \ref key_type should be constructible from \p key of type \p K.
 313             - The \ref mapped_type should be constructible from \p val of type \p V.
 314
 315             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 316         */
 317         template <typename K, typename V>
 318         iterator insert( K const& key, V const& val )
 319         {
 320             bucket_type& refBucket = bucket( key );
 321             bucket_iterator it = refBucket.insert( key, val );
 322
 323             if ( it != refBucket.end() ) {
 324                 ++m_ItemCounter;
 325                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 326             }
 327
 328             return end();
 329         }
 330
 331         /// Inserts new node and initialize it by a functor
 332         /**
 333             This function inserts new node with key \p key and if inserting is successful then it calls
 334             \p func functor with signature
 335             \code
 336             struct functor {
 337                 void operator()( value_type& item );
 338             };
 339             \endcode
 340
 341             The argument \p item of user-defined functor \p func is the reference
 342             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 343             User-defined functor \p func should guarantee that during changing item's value no any other changes
 344             could be made on this map's item by concurrent threads.
 345             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 346             and it is called only if the inserting is successful.
 347
 348             The key_type should be constructible from value of type \p K.
 349
 350             The function allows to split creating of new item into two part:
 351             - create item from \p key;
 352             - insert new item into the map;
 353             - if inserting is successful, initialize the value of item by calling \p f functor
 354
 355             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 356             it is preferable that the initialization should be completed only if inserting is successful.
 357
 358             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 359         */
 360         template <typename K, typename Func>
 361         iterator insert_key( const K& key, Func func )
 362         {
 363             bucket_type& refBucket = bucket( key );
 364             bucket_iterator it = refBucket.insert_key( key, func );
 365
 366             if ( it != refBucket.end() ) {
 367                 ++m_ItemCounter;
 368                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 369             }
 370
 371             return end();
 372         }
 373
 374 #   ifdef CDS_EMPLACE_SUPPORT
 375         /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 376         /**
 377             \p key_type should be constructible from type \p K
 378
 379             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 380
 381             This function is available only for compiler that supports
 382             variadic template and move semantics
 383         */
 384         template <typename K, typename... Args>
 385         iterator emplace( K&& key, Args&&... args )
 386         {
 387             bucket_type& refBucket = bucket( key );
 388             bucket_iterator it = refBucket.emplace( std::forward<K>(key), std::forward<Args>(args)... );
 389
 390             if ( it != refBucket.end() ) {
 391                 ++m_ItemCounter;
 392                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 393             }
 394
 395             return end();
 396         }
 397 #   endif
 398
 399         /// Ensures that the key \p key exists in the map
 400         /**
 401             The operation inserts new item if the key \p key is not found in the map.
 402             Otherwise, the function returns an iterator that points to item found.
 403
 404             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 405             item found or inserted, \p second is true if new item has been added or \p false if the item
 406             already is in the list.
 407         */
 408         template <typename K>
 409         std::pair<iterator, bool> ensure( const K& key )
 410         {
 411             bucket_type& refBucket = bucket( key );
 412             std::pair<bucket_iterator, bool> ret = refBucket.ensure( key );
 413
 414             if ( ret.second  )
 415                 ++m_ItemCounter;
 416
 417             return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
 418         }
 419
 420         /// Find the key \p key
 421         /** \anchor cds_nonintrusive_MichaelMap_nogc_find
 422
 423             The function searches the item with key equal to \p key
 424             and returns an iterator pointed to item found if the key is found,
 425             and \ref end() otherwise
 426         */
 427         template <typename K>
 428         iterator find( const K& key )
 429         {
 430             bucket_type& refBucket = bucket( key );
 431             bucket_iterator it = refBucket.find( key );
 432
 433             if ( it != refBucket.end() )
 434                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 435
 436             return end();
 437         }
 438
 439         /// Finds the key \p val using \p pred predicate for searching
 440         /**
 441             The function is an analog of \ref cds_nonintrusive_MichaelMap_nogc_find "find(K const&)"
 442             but \p pred is used for key comparing.
 443             \p Less functor has the interface like \p std::less.
 444             \p Less must imply the same element order as the comparator used for building the map.
 445         */
 446         template <typename K, typename Less>
 447         iterator find_with( const K& key, Less pred )
 448         {
 449             bucket_type& refBucket = bucket( key );
 450             bucket_iterator it = refBucket.find_with( key, pred );
 451
 452             if ( it != refBucket.end() )
 453                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 454
 455             return end();
 456         }
 457
 458         /// Clears the map (non-atomic)
 459         /**
 460             The function deletes all items from the map.
 461             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 462             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 463             <tt> empty() </tt> may return \p true but the map may contain item(s).
 464         */
 465         void clear()
 466         {
 467             for ( size_t i = 0; i < bucket_count(); ++i )
 468                 m_Buckets[i].clear();
 469             m_ItemCounter.reset();
 470         }
 471
 472
 473         /// Checks if the map is empty
 474         /**
 475             Emptiness is checked by item counting: if item count is zero then the map is empty.
 476             Thus, the correct item counting feature is an important part of Michael's map implementation.
 477         */
 478         bool empty() const
 479         {
 480             return size() == 0;
 481         }
 482
 483         /// Returns item count in the map
 484         size_t size() const
 485         {
 486             return m_ItemCounter;
 487         }
 488
 489         /// Returns the size of hash table
 490         /**
 491             Since MichaelHashMap cannot dynamically extend the hash table size,
 492             the value returned is an constant depending on object initialization parameters;
 493             see MichaelHashMap::MichaelHashMap for explanation.
 494         */
 495         size_t bucket_count() const
 496         {
 497             return m_nHashBitmask + 1;
 498         }
 499
 500     };
 501 }} // namespace cds::container
 502
 503 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_NOGC_H