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