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/details/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         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 201         /**
 202             Return an iterator pointing to inserted item if success \ref end() otherwise
 203         */
 204         template <typename... Args>
 205         iterator emplace( Args&&... args )
 206         {
 207             bucket_type& refBucket = bucket( value_type(std::forward<Args>(args)...));
 208             bucket_iterator it = refBucket.emplace( std::forward<Args>(args)... );
 209
 210             if ( it != refBucket.end() ) {
 211                 ++m_ItemCounter;
 212                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 213             }
 214
 215             return end();
 216         }
 217
 218         /// Ensures that the item \p val exists in the set
 219         /**
 220             The operation inserts new item if the key \p val is not found in the set.
 221             Otherwise, the function returns an iterator that points to item found.
 222
 223             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 224             item found or inserted, \p second is true if new item has been added or \p false if the item
 225             already is in the set.
 226         */
 227         template <typename Q>
 228         std::pair<iterator, bool> ensure( const Q& val )
 229         {
 230             bucket_type& refBucket = bucket( val );
 231             std::pair<bucket_iterator, bool> ret = refBucket.ensure( val );
 232
 233             if ( ret.first != refBucket.end() ) {
 234                 if ( ret.second )
 235                     ++m_ItemCounter;
 236                 return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
 237             }
 238
 239             return std::make_pair( end(), ret.second );
 240         }
 241
 242         /// Find the key \p key
 243         /** \anchor cds_nonintrusive_MichealSet_nogc_find
 244             The function searches the item with key equal to \p key
 245             and returns an iterator pointed to item found if the key is found,
 246             and \ref end() otherwise
 247         */
 248         template <typename Q>
 249         iterator find( Q const& key )
 250         {
 251             bucket_type& refBucket = bucket( key );
 252             bucket_iterator it = refBucket.find( key );
 253             if ( it != refBucket.end() )
 254                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 255
 256             return end();
 257         }
 258
 259         /// Finds the key \p val using \p pred predicate for searching
 260         /**
 261             The function is an analog of \ref cds_nonintrusive_MichealSet_nogc_find "find(Q const&)"
 262             but \p pred is used for key comparing.
 263             \p Less functor has the interface like \p std::less.
 264             \p Less must imply the same element order as the comparator used for building the set.
 265         */
 266         template <typename Q, typename Less>
 267         iterator find_with( Q const& key, Less pred )
 268         {
 269             bucket_type& refBucket = bucket( key );
 270             bucket_iterator it = refBucket.find_with( key, pred );
 271             if ( it != refBucket.end() )
 272                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 273
 274             return end();
 275         }
 276
 277
 278         /// Clears the set (non-atomic, not thread-safe)
 279         /**
 280             The function deletes all items from the set.
 281             The function is not atomic and even not thread-safe.
 282             It cleans up each bucket and then resets the item counter to zero.
 283             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 284             <tt> empty() </tt> may return \p true but the set may contain item(s).
 285         */
 286         void clear()
 287         {
 288             for ( size_t i = 0; i < bucket_count(); ++i )
 289                 m_Buckets[i].clear();
 290             m_ItemCounter.reset();
 291         }
 292
 293
 294         /// Checks if the set is empty
 295         /**
 296             Emptiness is checked by item counting: if item count is zero then the set is empty.
 297             Thus, the correct item counting feature is an important part of Michael's set implementation.
 298         */
 299         bool empty() const
 300         {
 301             return size() == 0;
 302         }
 303
 304         /// Returns item count in the set
 305         size_t size() const
 306         {
 307             return m_ItemCounter;
 308         }
 309
 310         /// Returns the size of hash table
 311         /**
 312             Since MichaelHashSet cannot dynamically extend the hash table size,
 313             the value returned is an constant depending on object initialization parameters;
 314             see MichaelHashSet::MichaelHashSet for explanation.
 315         */
 316         size_t bucket_count() const
 317         {
 318             return m_nHashBitmask + 1;
 319         }
 320     };
 321
 322 }} // cds::container
 323
 324 #endif // ifndef __CDS_CONTAINER_MICHAEL_SET_NOGC_H