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
 183
 184     public:
 185         /// Forward iterator
 186         typedef iterator_type< false >    iterator;
 187
 188         /// Const forward iterator
 189         typedef iterator_type< true >     const_iterator;
 190
 191         /// Returns a forward iterator addressing the first element in a set
 192         /**
 193             For empty set \code begin() == end() \endcode
 194         */
 195         iterator begin()
 196         {
 197             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 198         }
 199
 200         /// Returns an iterator that addresses the location succeeding the last element in a set
 201         /**
 202             Do not use the value returned by <tt>end</tt> function to access any item.
 203             The returned value can be used only to control reaching the end of the set.
 204             For empty set \code begin() == end() \endcode
 205         */
 206         iterator end()
 207         {
 208             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 209         }
 210
 211         /// Returns a forward const iterator addressing the first element in a set
 212         //@{
 213         const_iterator begin() const
 214         {
 215             return get_const_begin();
 216         }
 217         const_iterator cbegin() const
 218         {
 219             return get_const_begin();
 220         }
 221         //@}
 222
 223         /// Returns an const iterator that addresses the location succeeding the last element in a set
 224         //@{
 225         const_iterator end() const
 226         {
 227             return get_const_end();
 228         }
 229         const_iterator cend() const
 230         {
 231             return get_const_end();
 232         }
 233         //@}
 234
 235     private:
 236         //@cond
 237         const_iterator get_const_begin() const
 238         {
 239             return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
 240         }
 241         const_iterator get_const_end() const
 242         {
 243             return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 244         }
 245         //@endcond
 246
 247     public:
 248         /// Initialize the map
 249         /** @copydetails cds_nonintrusive_MichaelHashMap_hp_ctor
 250         */
 251         MichaelHashMap(
 252             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 253             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 254         ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 255         {
 256             // GC and OrderedList::gc must be the same
 257             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
 258
 259             // atomicity::empty_item_counter is not allowed as a item counter
 260             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
 261                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 262
 263             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 264         }
 265
 266         /// Clears hash set and destroys it
 267         ~MichaelHashMap()
 268         {
 269             clear();
 270             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 271         }
 272
 273         /// Inserts new node with key and default value
 274         /**
 275             The function creates a node with \p key and default value, and then inserts the node created into the map.
 276
 277             Preconditions:
 278             - The \ref key_type should be constructible from value of type \p K.
 279                 In trivial case, \p K is equal to \ref key_type.
 280             - The \ref mapped_type should be default-constructible.
 281
 282             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 283         */
 284         template <typename K>
 285         iterator insert( const K& key )
 286         {
 287             bucket_type& refBucket = bucket( key );
 288             bucket_iterator it = refBucket.insert( key );
 289
 290             if ( it != refBucket.end() ) {
 291                 ++m_ItemCounter;
 292                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 293             }
 294
 295             return end();
 296         }
 297
 298         /// Inserts new node
 299         /**
 300             The function creates a node with copy of \p val value
 301             and then inserts the node created into the map.
 302
 303             Preconditions:
 304             - The \ref key_type should be constructible from \p key of type \p K.
 305             - The \ref mapped_type should be constructible from \p val of type \p V.
 306
 307             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 308         */
 309         template <typename K, typename V>
 310         iterator insert( K const& key, V const& val )
 311         {
 312             bucket_type& refBucket = bucket( key );
 313             bucket_iterator it = refBucket.insert( key, val );
 314
 315             if ( it != refBucket.end() ) {
 316                 ++m_ItemCounter;
 317                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 318             }
 319
 320             return end();
 321         }
 322
 323         /// Inserts new node and initialize it by a functor
 324         /**
 325             This function inserts new node with key \p key and if inserting is successful then it calls
 326             \p func functor with signature
 327             \code
 328             struct functor {
 329                 void operator()( value_type& item );
 330             };
 331             \endcode
 332
 333             The argument \p item of user-defined functor \p func is the reference
 334             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 335
 336             The user-defined functor it is called only if the inserting is successful.
 337             The \p key_type should be constructible from value of type \p K.
 338
 339             The function allows to split creating of new item into two part:
 340             - create item from \p key;
 341             - insert new item into the map;
 342             - if inserting is successful, initialize the value of item by calling \p f functor
 343
 344             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 345             it is preferable that the initialization should be completed only if inserting is successful.
 346
 347             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 348
 349             @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 350             \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
 351             synchronization.
 352         */
 353         template <typename K, typename Func>
 354         iterator insert_key( const K& key, Func func )
 355         {
 356             bucket_type& refBucket = bucket( key );
 357             bucket_iterator it = refBucket.insert_key( key, func );
 358
 359             if ( it != refBucket.end() ) {
 360                 ++m_ItemCounter;
 361                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 362             }
 363
 364             return end();
 365         }
 366
 367         /// For key \p key inserts data of type \p mapped_type created from \p args
 368         /**
 369             \p key_type should be constructible from type \p K
 370
 371             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 372         */
 373         template <typename K, typename... Args>
 374         iterator emplace( K&& key, Args&&... args )
 375         {
 376             bucket_type& refBucket = bucket( key );
 377             bucket_iterator it = refBucket.emplace( std::forward<K>(key), std::forward<Args>(args)... );
 378
 379             if ( it != refBucket.end() ) {
 380                 ++m_ItemCounter;
 381                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 382             }
 383
 384             return end();
 385         }
 386
 387         /// Ensures that the key \p key exists in the map
 388         /**
 389             The operation inserts new item if the key \p key is not found in the map.
 390             Otherwise, the function returns an iterator that points to item found.
 391
 392             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 393             item found or inserted, \p second is true if new item has been added or \p false if the item
 394             already is in the list.
 395
 396             @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 397             \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
 398             synchronization.
 399         */
 400         template <typename K>
 401         std::pair<iterator, bool> ensure( const K& key )
 402         {
 403             bucket_type& refBucket = bucket( key );
 404             std::pair<bucket_iterator, bool> ret = refBucket.ensure( key );
 405
 406             if ( ret.second  )
 407                 ++m_ItemCounter;
 408
 409             return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
 410         }
 411
 412         /// Find the key \p key
 413         /** \anchor cds_nonintrusive_MichaelMap_nogc_find
 414
 415             The function searches the item with key equal to \p key
 416             and returns an iterator pointed to item found if the key is found,
 417             and \ref end() otherwise
 418         */
 419         template <typename K>
 420         iterator find( const K& key )
 421         {
 422             bucket_type& refBucket = bucket( key );
 423             bucket_iterator it = refBucket.find( key );
 424
 425             if ( it != refBucket.end() )
 426                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 427
 428             return end();
 429         }
 430
 431         /// Finds the key \p val using \p pred predicate for searching
 432         /**
 433             The function is an analog of \ref cds_nonintrusive_MichaelMap_nogc_find "find(K const&)"
 434             but \p pred is used for key comparing.
 435             \p Less functor has the interface like \p std::less.
 436             \p Less must imply the same element order as the comparator used for building the map.
 437         */
 438         template <typename K, typename Less>
 439         iterator find_with( const K& key, Less pred )
 440         {
 441             bucket_type& refBucket = bucket( key );
 442             bucket_iterator it = refBucket.find_with( key, pred );
 443
 444             if ( it != refBucket.end() )
 445                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 446
 447             return end();
 448         }
 449
 450         /// Clears the map (not atomic)
 451         void clear()
 452         {
 453             for ( size_t i = 0; i < bucket_count(); ++i )
 454                 m_Buckets[i].clear();
 455             m_ItemCounter.reset();
 456         }
 457
 458         /// Checks whether the map is empty
 459         /**
 460             Emptiness is checked by item counting: if item count is zero then the map is empty.
 461             Thus, the correct item counting feature is an important part of Michael's map implementation.
 462         */
 463         bool empty() const
 464         {
 465             return size() == 0;
 466         }
 467
 468         /// Returns item count in the map
 469         size_t size() const
 470         {
 471             return m_ItemCounter;
 472         }
 473
 474         /// Returns the size of hash table
 475         /**
 476             Since \p %MichaelHashMap cannot dynamically extend the hash table size,
 477             the value returned is an constant depending on object initialization parameters;
 478             see \p MichaelHashMap::MichaelHashMap for explanation.
 479         */
 480         size_t bucket_count() const
 481         {
 482             return m_nHashBitmask + 1;
 483         }
 484     };
 485 }} // namespace cds::container
 486
 487 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_NOGC_H