cds/intrusive/michael_set_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
   4 #define __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
   5
   6 #include <cds/intrusive/details/michael_set_base.h>
   7 #include <cds/gc/nogc.h>
   8 #include <cds/details/allocator.h>
   9
  10 namespace cds { namespace intrusive {
  11
  12     /// Michael's hash set (template specialization for gc::nogc)
  13     /** @ingroup cds_intrusive_map
  14         \anchor cds_intrusive_MichaelHashSet_nogc
  15
  16         This specialization is so-called append-only when no item
  17         reclamation may be performed. The set does not support deleting of list item.
  18
  19         See \ref cds_intrusive_MichaelHashSet_hp "MichaelHashSet" for description of template parameters.
  20         The template parameter \p OrderedList should be any \p cds::gc::nogc -derived ordered list, for example,
  21         \ref cds_intrusive_MichaelList_nogc "append-only MichaelList".
  22     */
  23     template <
  24         class OrderedList,
  25 #ifdef CDS_DOXYGEN_INVOKED
  26         class Traits = michael_set::traits
  27 #else
  28         class Traits
  29 #endif
  30     >
  31     class MichaelHashSet< cds::gc::nogc, OrderedList, Traits >
  32     {
  33     public:
  34         typedef cds::gc::nogc gc;        ///< Garbage collector
  35         typedef OrderedList bucket_type; ///< Type of ordered list to be used as buckets
  36         typedef Traits      traits;     ///< Set traits
  37
  38         typedef typename bucket_type::value_type     value_type;     ///< type of value to be stored in the set
  39         typedef typename bucket_type::key_comparator key_comparator; ///< key comparing functor
  40         typedef typename bucket_type::disposer       disposer;       ///< Node disposer functor
  41
  42         /// Hash functor for \p value_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         item_counter    m_ItemCounter; ///< Item counter
  51         hash            m_HashFunctor; ///< Hash functor
  52         bucket_type *   m_Buckets;     ///< bucket table
  53
  54     private:
  55         //@cond
  56         const size_t    m_nHashBitmask;
  57         //@endcond
  58
  59     protected:
  60         //@cond
  61         /// Calculates hash value of \p key
  62         template <typename Q>
  63         size_t hash_value( Q const & key ) const
  64         {
  65             return m_HashFunctor( key ) & m_nHashBitmask;
  66         }
  67
  68         /// Returns the bucket (ordered list) for \p key
  69         template <typename Q>
  70         bucket_type&    bucket( Q const & key )
  71         {
  72             return m_Buckets[ hash_value( key ) ];
  73         }
  74         //@endcond
  75
  76     public:
  77         /// Forward iterator
  78         /**
  79             The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
  80             - it has no post-increment operator
  81             - it iterates items in unordered fashion
  82         */
  83         typedef michael_set::details::iterator< bucket_type, false >    iterator;
  84
  85         /// Const forward iterator
  86         /**
  87             For iterator's features and requirements see \ref iterator
  88         */
  89         typedef michael_set::details::iterator< bucket_type, true >     const_iterator;
  90
  91         /// Returns a forward iterator addressing the first element in a set
  92         /**
  93             For empty set \code begin() == end() \endcode
  94         */
  95         iterator begin()
  96         {
  97             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
  98         }
  99
 100         /// Returns an iterator that addresses the location succeeding the last element in a set
 101         /**
 102             Do not use the value returned by <tt>end</tt> function to access any item.
 103             The returned value can be used only to control reaching the end of the set.
 104             For empty set \code begin() == end() \endcode
 105         */
 106         iterator end()
 107         {
 108             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 109         }
 110
 111         /// Returns a forward const iterator addressing the first element in a set
 112         //@{
 113         const_iterator begin() const
 114         {
 115             return get_const_begin();
 116         }
 117         const_iterator cbegin()
 118         {
 119             return get_const_begin();
 120         }
 121         //@}
 122
 123         /// Returns an const iterator that addresses the location succeeding the last element in a set
 124         //@{
 125         const_iterator end() const
 126         {
 127             return get_const_end();
 128         }
 129         const_iterator cend()
 130         {
 131             return get_const_end();
 132         }
 133         //@}
 134
 135     private:
 136         //@cond
 137         const_iterator get_const_begin() const
 138         {
 139             return const_iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 140         }
 141         const_iterator get_const_end() const
 142         {
 143             return const_iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 144         }
 145         //@endcond
 146
 147     public:
 148         /// Initializes hash set
 149         /** @copydetails cds_intrusive_MichaelHashSet_hp_ctor
 150         */
 151         MichaelHashSet(
 152             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 153             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 154         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 155         {
 156             // GC and OrderedList::gc must be the same
 157             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
 158
 159             // atomicity::empty_item_counter is not allowed as a item counter
 160             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
 161                            "atomicity::empty_item_counter is not allowed as a item counter");
 162
 163             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 164         }
 165
 166         /// Clears hash set object and destroys it
 167         ~MichaelHashSet()
 168         {
 169             clear();
 170             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 171         }
 172
 173         /// Inserts new node
 174         /**
 175             The function inserts \p val in the set if it does not contain
 176             an item with key equal to \p val.
 177
 178             Returns \p true if \p val is placed into the set, \p false otherwise.
 179         */
 180         bool insert( value_type& val )
 181         {
 182             bool bRet = bucket( val ).insert( val );
 183             if ( bRet )
 184                 ++m_ItemCounter;
 185             return bRet;
 186         }
 187
 188         /// Ensures that the \p item exists in the set
 189         /**
 190             The operation performs inserting or changing data with lock-free manner.
 191
 192             If the item \p val not found in the set, then \p val is inserted into the set.
 193             Otherwise, the functor \p func is called with item found.
 194             The functor signature is:
 195             \code
 196                 void func( bool bNew, value_type& item, value_type& val );
 197             \endcode
 198             with arguments:
 199             - \p bNew - \p true if the item has been inserted, \p false otherwise
 200             - \p item - item of the set
 201             - \p val - argument \p val passed into the \p ensure function
 202             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 203             refers to the same thing.
 204
 205             The functor can change non-key fields of the \p item.
 206
 207             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 208             \p second is \p true if new item has been added or \p false if the item with \p key
 209             already is in the set.
 210
 211             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 212             \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
 213             synchronization.
 214         */
 215         template <typename Func>
 216         std::pair<bool, bool> ensure( value_type& val, Func func )
 217         {
 218             std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
 219             if ( bRet.first && bRet.second )
 220                 ++m_ItemCounter;
 221             return bRet;
 222         }
 223
 224         /// Finds the key \p key
 225         /** \anchor cds_intrusive_MichaelHashSet_nogc_find_val
 226             The function searches the item with key equal to \p key
 227             and returns pointer to item found, otherwise \p nullptr.
 228
 229             Note the hash functor specified for class \p Traits template parameter
 230             should accept a parameter of type \p Q that can be not the same as \p value_type.
 231         */
 232         template <typename Q>
 233         value_type * find( Q const& key )
 234         {
 235             return bucket( key ).find( key );
 236         }
 237
 238         /// Finds the key \p key using \p pred predicate for searching
 239         /**
 240             The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_val "find(Q const&)"
 241             but \p pred is used for key comparing.
 242             \p Less functor has the interface like \p std::less.
 243             \p pred must imply the same element order as the comparator used for building the set.
 244         */
 245         template <typename Q, typename Less>
 246         value_type * find_with( Q const& key, Less pred )
 247         {
 248             return bucket( key ).find_with( key, pred );
 249         }
 250
 251         /// Finds the key \p key
 252         /** \anchor cds_intrusive_MichaelHashSet_nogc_find_func
 253             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 254             The interface of \p Func functor is:
 255             \code
 256             struct functor {
 257                 void operator()( value_type& item, Q& key );
 258             };
 259             \endcode
 260             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 261
 262             The functor can change non-key fields of \p item.
 263             The functor does not serialize simultaneous access to the set \p item. If such access is
 264             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 265
 266             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 267             can modify both arguments.
 268
 269             Note the hash functor specified for class \p Traits template parameter
 270             should accept a parameter of type \p Q that can be not the same as \p value_type.
 271
 272             The function returns \p true if \p key is found, \p false otherwise.
 273         */
 274         template <typename Q, typename Func>
 275         bool find( Q& key, Func f )
 276         {
 277             return bucket( key ).find( key, f );
 278         }
 279
 280         /// Finds the key \p key using \p pred predicate for searching
 281         /**
 282             The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_func "find(Q&, Func)"
 283             but \p pred is used for key comparing.
 284             \p Less functor has the interface like \p std::less.
 285             \p pred must imply the same element order as the comparator used for building the set.
 286         */
 287         template <typename Q, typename Less, typename Func>
 288         bool find_with( Q& key, Less pred, Func f )
 289         {
 290             return bucket( key ).find_with( key, pred, f );
 291         }
 292
 293         /// Clears the set (non-atomic)
 294         /**
 295             The function unlink all items from the set.
 296             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 297             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 298             <tt> empty() </tt> may return \p true but the set may contain item(s).
 299             Therefore, \p clear may be used only for debugging purposes.
 300
 301             For each item the \p disposer is called after unlinking.
 302         */
 303         void clear()
 304         {
 305             for ( size_t i = 0; i < bucket_count(); ++i )
 306                 m_Buckets[i].clear();
 307             m_ItemCounter.reset();
 308         }
 309
 310
 311         /// Checks if the set is empty
 312         /**
 313             Emptiness is checked by item counting: if item count is zero then the set is empty.
 314             Thus, the correct item counting feature is an important part of Michael's set implementation.
 315         */
 316         bool empty() const
 317         {
 318             return size() == 0;
 319         }
 320
 321         /// Returns item count in the set
 322         size_t size() const
 323         {
 324             return m_ItemCounter;
 325         }
 326
 327         /// Returns the size of hash table
 328         /**
 329             Since \p %MichaelHashSet cannot dynamically extend the hash table size,
 330             the value returned is an constant depending on object initialization parameters;
 331             see MichaelHashSet::MichaelHashSet for explanation.
 332         */
 333         size_t bucket_count() const
 334         {
 335             return m_nHashBitmask + 1;
 336         }
 337
 338     };
 339
 340 }} // namespace cds::intrusive
 341
 342 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
 343