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         /**
 254             The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
 255             when you create an object.
 256             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
 257             Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
 258             Note, that many popular STL hash map implementation uses load factor 1.
 259
 260             The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
 261         */
 262         MichaelHashMap(
 263             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 264             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 265         ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 266         {
 267             // GC and OrderedList::gc must be the same
 268             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
 269
 270             // atomicity::empty_item_counter is not allowed as a item counter
 271             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
 272                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 273
 274             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 275         }
 276
 277         /// Clears hash set and destroys it
 278         ~MichaelHashMap()
 279         {
 280             clear();
 281             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 282         }
 283
 284         /// Inserts new node with key and default value
 285         /**
 286             The function creates a node with \p key and default value, and then inserts the node created into the map.
 287
 288             Preconditions:
 289             - The \ref key_type should be constructible from value of type \p K.
 290                 In trivial case, \p K is equal to \ref key_type.
 291             - The \ref mapped_type should be default-constructible.
 292
 293             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 294         */
 295         template <typename K>
 296         iterator insert( const K& key )
 297         {
 298             bucket_type& refBucket = bucket( key );
 299             bucket_iterator it = refBucket.insert( key );
 300
 301             if ( it != refBucket.end() ) {
 302                 ++m_ItemCounter;
 303                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 304             }
 305
 306             return end();
 307         }
 308
 309         /// Inserts new node
 310         /**
 311             The function creates a node with copy of \p val value
 312             and then inserts the node created into the map.
 313
 314             Preconditions:
 315             - The \ref key_type should be constructible from \p key of type \p K.
 316             - The \ref mapped_type should be constructible from \p val of type \p V.
 317
 318             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 319         */
 320         template <typename K, typename V>
 321         iterator insert( K const& key, V const& val )
 322         {
 323             bucket_type& refBucket = bucket( key );
 324             bucket_iterator it = refBucket.insert( key, val );
 325
 326             if ( it != refBucket.end() ) {
 327                 ++m_ItemCounter;
 328                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 329             }
 330
 331             return end();
 332         }
 333
 334         /// Inserts new node and initialize it by a functor
 335         /**
 336             This function inserts new node with key \p key and if inserting is successful then it calls
 337             \p func functor with signature
 338             \code
 339             struct functor {
 340                 void operator()( value_type& item );
 341             };
 342             \endcode
 343
 344             The argument \p item of user-defined functor \p func is the reference
 345             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 346
 347             The user-defined functor it is called only if the inserting is successful.
 348             The \p 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             @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 361             \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
 362             synchronization.
 363         */
 364         template <typename K, typename Func>
 365         iterator insert_with( const K& key, Func func )
 366         {
 367             bucket_type& refBucket = bucket( key );
 368             bucket_iterator it = refBucket.insert_with( key, func );
 369
 370             if ( it != refBucket.end() ) {
 371                 ++m_ItemCounter;
 372                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 373             }
 374
 375             return end();
 376         }
 377
 378         /// For key \p key inserts data of type \p mapped_type created from \p args
 379         /**
 380             \p key_type should be constructible from type \p K
 381
 382             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 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
 398         /// Updates the item
 399         /**
 400             If \p key is not in the map and \p bAllowInsert is \p true, the function inserts a new item.
 401             Otherwise, the function returns an iterator pointing to the item found.
 402
 403             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 404             item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
 405             \p second is true if new item has been added or \p false if the item
 406             already is in the map.
 407
 408             @warning For \ref cds_nonintrusive_MichaelKVList_nogc "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 409             \ref cds_nonintrusive_LazyKVList_nogc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
 410             synchronization.
 411         */
 412         template <typename K>
 413         std::pair<iterator, bool> update( const K& key, bool bAllowInsert = true )
 414         {
 415             bucket_type& refBucket = bucket( key );
 416             std::pair<bucket_iterator, bool> ret = refBucket.update( key, bAllowInsert );
 417
 418             if ( ret.second  )
 419                 ++m_ItemCounter;
 420
 421             return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
 422         }
 423         //@cond
 424         // Deprecated, use update()
 425         template <typename K>
 426         std::pair<iterator, bool> ensure( K const& key )
 427         {
 428             return update( key, true );
 429         }
 430         //@endcond
 431
 432         /// Checks whether the map contains \p key
 433         /**
 434             The function searches the item with key equal to \p key
 435             and returns an iterator pointed to item found and \ref end() otherwise
 436         */
 437         template <typename K>
 438         iterator contains( K const& key )
 439         {
 440             bucket_type& refBucket = bucket( key );
 441             bucket_iterator it = refBucket.contains( key );
 442
 443             if ( it != refBucket.end() )
 444                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 445
 446             return end();
 447         }
 448         //@cond
 449         // Deprecated, use contains()
 450         template <typename K>
 451         iterator find( K const& key )
 452         {
 453             return contains( key );
 454         }
 455         //@endcond
 456
 457         /// Checks whether the map contains \p key using \p pred predicate for searching
 458         /**
 459             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 460             \p Less functor has the interface like \p std::less.
 461             \p pred must imply the same element order as the comparator used for building the map.
 462         */
 463         template <typename K, typename Less>
 464         iterator contains( K const& key, Less pred )
 465         {
 466             bucket_type& refBucket = bucket( key );
 467             bucket_iterator it = refBucket.contains( key, pred );
 468
 469             if ( it != refBucket.end() )
 470                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 471
 472             return end();
 473         }
 474         //@cond
 475         // Deprecated, use contains()
 476         template <typename K, typename Less>
 477         iterator find_with( K const& key, Less pred )
 478         {
 479             return contains( key, pred );
 480         }
 481         //@endcond
 482
 483         /// Clears the map (not atomic)
 484         void clear()
 485         {
 486             for ( size_t i = 0; i < bucket_count(); ++i )
 487                 m_Buckets[i].clear();
 488             m_ItemCounter.reset();
 489         }
 490
 491         /// Checks whether the map is empty
 492         /**
 493             Emptiness is checked by item counting: if item count is zero then the map is empty.
 494             Thus, the correct item counting feature is an important part of Michael's map implementation.
 495         */
 496         bool empty() const
 497         {
 498             return size() == 0;
 499         }
 500
 501         /// Returns item count in the map
 502         size_t size() const
 503         {
 504             return m_ItemCounter;
 505         }
 506
 507         /// Returns the size of hash table
 508         /**
 509             Since \p %MichaelHashMap cannot dynamically extend the hash table size,
 510             the value returned is an constant depending on object initialization parameters;
 511             see \p MichaelHashMap::MichaelHashMap for explanation.
 512         */
 513         size_t bucket_count() const
 514         {
 515             return m_nHashBitmask + 1;
 516         }
 517     };
 518 }} // namespace cds::container
 519
 520 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_NOGC_H