cds/container/michael_map_nogc.h

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