cds/container/michael_set_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_MICHAEL_SET_NOGC_H
   4 #define __CDS_CONTAINER_MICHAEL_SET_NOGC_H
   5
   6 #include <cds/container/michael_set_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 set (template specialization for gc::nogc)
  13     /** @ingroup cds_nonintrusive_set
  14         \anchor cds_nonintrusive_MichaelHashSet_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 list item.
  18
  19         See \ref cds_nonintrusive_MichaelHashSet_hp "MichaelHashSet" for description of template parameters.
  20         The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
  21         \ref cds_nonintrusive_MichaelList_nogc "persistent MichaelList".
  22
  23         The interface of the specialization is a slightly different.
  24     */
  25     template <
  26         class OrderedList,
  27 #ifdef CDS_DOXYGEN_INVOKED
  28         class Traits = michael_set::type_traits
  29 #else
  30         class Traits
  31 #endif
  32     >
  33     class MichaelHashSet< gc::nogc, OrderedList, Traits >
  34     {
  35     public:
  36         typedef OrderedList bucket_type     ;   ///< type of ordered list used as a bucket implementation
  37         typedef Traits      options         ;   ///< Traits template parameters
  38
  39         typedef typename bucket_type::value_type        value_type      ;   ///< type of value stored in the list
  40         typedef gc::nogc                                gc              ;   ///< Garbage collector
  41         typedef typename bucket_type::key_comparator    key_comparator  ;   ///< key comparison functor
  42
  43         /// Hash functor for \ref value_type and all its derivatives that you use
  44         typedef typename cds::opt::v::hash_selector< typename options::hash >::type   hash;
  45         typedef typename options::item_counter          item_counter    ;   ///< Item counter type
  46
  47         /// Bucket table allocator
  48         typedef cds::details::Allocator< bucket_type, typename options::allocator >  bucket_table_allocator;
  49
  50     protected:
  51         //@cond
  52         typedef typename bucket_type::iterator          bucket_iterator;
  53         typedef typename bucket_type::const_iterator    bucket_const_iterator;
  54         //@endcond
  55
  56     protected:
  57         item_counter    m_ItemCounter   ;   ///< Item counter
  58         hash            m_HashFunctor   ;   ///< Hash functor
  59
  60         bucket_type *   m_Buckets       ;   ///< bucket table
  61
  62     private:
  63         //@cond
  64         const size_t    m_nHashBitmask;
  65         //@endcond
  66
  67     protected:
  68         /// Calculates hash value of \p key
  69         template <typename Q>
  70         size_t hash_value( const Q& key ) const
  71         {
  72             return m_HashFunctor( key ) & m_nHashBitmask;
  73         }
  74
  75         /// Returns the bucket (ordered list) for \p key
  76         template <typename Q>
  77         bucket_type&    bucket( const Q& key )
  78         {
  79             return m_Buckets[ hash_value( key ) ];
  80         }
  81
  82     public:
  83         /// Forward iterator
  84         /**
  85             The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
  86             - it has no post-increment operator
  87             - it iterates items in unordered fashion
  88         */
  89         typedef michael_set::details::iterator< bucket_type, false >    iterator;
  90
  91         /// Const forward iterator
  92         /**
  93             For iterator's features and requirements see \ref iterator
  94         */
  95         typedef michael_set::details::iterator< bucket_type, true >     const_iterator;
  96
  97         /// Returns a forward iterator addressing the first element in a set
  98         /**
  99             For empty set \code begin() == end() \endcode
 100         */
 101         iterator begin()
 102         {
 103             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 104         }
 105
 106         /// Returns an iterator that addresses the location succeeding the last element in a set
 107         /**
 108             Do not use the value returned by <tt>end</tt> function to access any item.
 109             The returned value can be used only to control reaching the end of the set.
 110             For empty set \code begin() == end() \endcode
 111         */
 112         iterator end()
 113         {
 114             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 115         }
 116
 117         /// Returns a forward const iterator addressing the first element in a set
 118         //@{
 119         const_iterator begin() const
 120         {
 121             return get_const_begin();
 122         }
 123         const_iterator cbegin()
 124         {
 125             return get_const_begin();
 126         }
 127         //@}
 128
 129         /// Returns an const iterator that addresses the location succeeding the last element in a set
 130         //@{
 131         const_iterator end() const
 132         {
 133             return get_const_end();
 134         }
 135         const_iterator cend()
 136         {
 137             return get_const_end();
 138         }
 139         //@}
 140
 141     private:
 142         //@{
 143         const_iterator get_const_begin() const
 144         {
 145             return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
 146         }
 147         const_iterator get_const_end() const
 148         {
 149             return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 150         }
 151         //@}
 152
 153     public:
 154         /// Initialize hash set
 155         /**
 156             See \ref cds_nonintrusive_MichaelHashSet_hp "MichaelHashSet" ctor for explanation
 157         */
 158         MichaelHashSet(
 159             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 160             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 161         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 162         {
 163             // GC and OrderedList::gc must be the same
 164             static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
 165
 166             // atomicity::empty_item_counter is not allowed as a item counter
 167             static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
 168
 169             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 170         }
 171
 172         /// Clear hash set and destroy it
 173         ~MichaelHashSet()
 174         {
 175             clear();
 176             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 177         }
 178
 179         /// Inserts new node
 180         /**
 181             The function inserts \p val in the set if it does not contain
 182             an item with key equal to \p val.
 183
 184             Return an iterator pointing to inserted item if success, otherwise \ref end()
 185         */
 186         template <typename Q>
 187         iterator insert( const Q& val )
 188         {
 189             bucket_type& refBucket = bucket( val );
 190             bucket_iterator it = refBucket.insert( val );
 191
 192             if ( it != refBucket.end() ) {
 193                 ++m_ItemCounter;
 194                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 195             }
 196
 197             return end();
 198         }
 199
 200 #ifdef CDS_EMPLACE_SUPPORT
 201         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 202         /**
 203             Return an iterator pointing to inserted item if success \ref end() otherwise
 204
 205             This function is available only for compiler that supports
 206             variadic template and move semantics
 207         */
 208         template <typename... Args>
 209         iterator emplace( Args&&... args )
 210         {
 211             bucket_type& refBucket = bucket( value_type(std::forward<Args>(args)...));
 212             bucket_iterator it = refBucket.emplace( std::forward<Args>(args)... );
 213
 214             if ( it != refBucket.end() ) {
 215                 ++m_ItemCounter;
 216                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 217             }
 218
 219             return end();
 220         }
 221 #endif
 222
 223         /// Ensures that the item \p val exists in the set
 224         /**
 225             The operation inserts new item if the key \p val is not found in the set.
 226             Otherwise, the function returns an iterator that points to item found.
 227
 228             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 229             item found or inserted, \p second is true if new item has been added or \p false if the item
 230             already is in the set.
 231         */
 232         template <typename Q>
 233         std::pair<iterator, bool> ensure( const Q& val )
 234         {
 235             bucket_type& refBucket = bucket( val );
 236             std::pair<bucket_iterator, bool> ret = refBucket.ensure( val );
 237
 238             if ( ret.first != refBucket.end() ) {
 239                 if ( ret.second )
 240                     ++m_ItemCounter;
 241                 return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
 242             }
 243
 244             return std::make_pair( end(), ret.second );
 245         }
 246
 247         /// Find the key \p key
 248         /** \anchor cds_nonintrusive_MichealSet_nogc_find
 249             The function searches the item with key equal to \p key
 250             and returns an iterator pointed to item found if the key is found,
 251             and \ref end() otherwise
 252         */
 253         template <typename Q>
 254         iterator find( Q const& key )
 255         {
 256             bucket_type& refBucket = bucket( key );
 257             bucket_iterator it = refBucket.find( key );
 258             if ( it != refBucket.end() )
 259                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 260
 261             return end();
 262         }
 263
 264         /// Finds the key \p val using \p pred predicate for searching
 265         /**
 266             The function is an analog of \ref cds_nonintrusive_MichealSet_nogc_find "find(Q const&)"
 267             but \p pred is used for key comparing.
 268             \p Less functor has the interface like \p std::less.
 269             \p Less must imply the same element order as the comparator used for building the set.
 270         */
 271         template <typename Q, typename Less>
 272         iterator find_with( Q const& key, Less pred )
 273         {
 274             bucket_type& refBucket = bucket( key );
 275             bucket_iterator it = refBucket.find_with( key, pred );
 276             if ( it != refBucket.end() )
 277                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 278
 279             return end();
 280         }
 281
 282
 283         /// Clears the set (non-atomic, not thread-safe)
 284         /**
 285             The function deletes all items from the set.
 286             The function is not atomic and even not thread-safe.
 287             It cleans up each bucket and then resets the item counter to zero.
 288             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 289             <tt> empty() </tt> may return \p true but the set may contain item(s).
 290         */
 291         void clear()
 292         {
 293             for ( size_t i = 0; i < bucket_count(); ++i )
 294                 m_Buckets[i].clear();
 295             m_ItemCounter.reset();
 296         }
 297
 298
 299         /// Checks if the set is empty
 300         /**
 301             Emptiness is checked by item counting: if item count is zero then the set is empty.
 302             Thus, the correct item counting feature is an important part of Michael's set implementation.
 303         */
 304         bool empty() const
 305         {
 306             return size() == 0;
 307         }
 308
 309         /// Returns item count in the set
 310         size_t size() const
 311         {
 312             return m_ItemCounter;
 313         }
 314
 315         /// Returns the size of hash table
 316         /**
 317             Since MichaelHashSet cannot dynamically extend the hash table size,
 318             the value returned is an constant depending on object initialization parameters;
 319             see MichaelHashSet::MichaelHashSet for explanation.
 320         */
 321         size_t bucket_count() const
 322         {
 323             return m_nHashBitmask + 1;
 324         }
 325     };
 326
 327 }} // cds::container
 328
 329 #endif // ifndef __CDS_CONTAINER_MICHAEL_SET_NOGC_H