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 cbegin();
 116         }
 117         const_iterator cbegin() const
 118         {
 119             return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
 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 cend();
 128         }
 129         const_iterator cend() const
 130         {
 131             return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 132         }
 133         //@}
 134
 135     public:
 136         /// Initializes hash set
 137         /** @copydetails cds_intrusive_MichaelHashSet_hp_ctor
 138         */
 139         MichaelHashSet(
 140             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 141             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 142         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 143         {
 144             // GC and OrderedList::gc must be the same
 145             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
 146
 147             // atomicity::empty_item_counter is not allowed as a item counter
 148             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
 149                            "atomicity::empty_item_counter is not allowed as a item counter");
 150
 151             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 152         }
 153
 154         /// Clears hash set object and destroys it
 155         ~MichaelHashSet()
 156         {
 157             clear();
 158             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 159         }
 160
 161         /// Inserts new node
 162         /**
 163             The function inserts \p val in the set if it does not contain
 164             an item with key equal to \p val.
 165
 166             Returns \p true if \p val is placed into the set, \p false otherwise.
 167         */
 168         bool insert( value_type& val )
 169         {
 170             bool bRet = bucket( val ).insert( val );
 171             if ( bRet )
 172                 ++m_ItemCounter;
 173             return bRet;
 174         }
 175
 176         /// Ensures that the \p item exists in the set
 177         /**
 178             The operation performs inserting or changing data with lock-free manner.
 179
 180             If the item \p val not found in the set, then \p val is inserted into the set.
 181             Otherwise, the functor \p func is called with item found.
 182             The functor signature is:
 183             \code
 184                 void func( bool bNew, value_type& item, value_type& val );
 185             \endcode
 186             with arguments:
 187             - \p bNew - \p true if the item has been inserted, \p false otherwise
 188             - \p item - item of the set
 189             - \p val - argument \p val passed into the \p ensure function
 190             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 191             refers to the same thing.
 192
 193             The functor can change non-key fields of the \p item.
 194
 195             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 196             \p second is \p true if new item has been added or \p false if the item with \p key
 197             already is in the set.
 198
 199             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 200             \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
 201             synchronization.
 202         */
 203         template <typename Func>
 204         std::pair<bool, bool> ensure( value_type& val, Func func )
 205         {
 206             std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
 207             if ( bRet.first && bRet.second )
 208                 ++m_ItemCounter;
 209             return bRet;
 210         }
 211
 212         /// Finds the key \p key
 213         /** \anchor cds_intrusive_MichaelHashSet_nogc_find_val
 214             The function searches the item with key equal to \p key
 215             and returns pointer to item found, otherwise \p nullptr.
 216
 217             Note the hash functor specified for class \p Traits template parameter
 218             should accept a parameter of type \p Q that can be not the same as \p value_type.
 219         */
 220         template <typename Q>
 221         value_type * find( Q const& key )
 222         {
 223             return bucket( key ).find( key );
 224         }
 225
 226         /// Finds the key \p key using \p pred predicate for searching
 227         /**
 228             The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_val "find(Q const&)"
 229             but \p pred is used for key comparing.
 230             \p Less functor has the interface like \p std::less.
 231             \p pred must imply the same element order as the comparator used for building the set.
 232         */
 233         template <typename Q, typename Less>
 234         value_type * find_with( Q const& key, Less pred )
 235         {
 236             return bucket( key ).find_with( key, pred );
 237         }
 238
 239         /// Finds the key \p key
 240         /** \anchor cds_intrusive_MichaelHashSet_nogc_find_func
 241             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 242             The interface of \p Func functor is:
 243             \code
 244             struct functor {
 245                 void operator()( value_type& item, Q& key );
 246             };
 247             \endcode
 248             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 249
 250             The functor can change non-key fields of \p item.
 251             The functor does not serialize simultaneous access to the set \p item. If such access is
 252             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 253
 254             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 255             can modify both arguments.
 256
 257             Note the hash functor specified for class \p Traits template parameter
 258             should accept a parameter of type \p Q that can be not the same as \p value_type.
 259
 260             The function returns \p true if \p key is found, \p false otherwise.
 261         */
 262         template <typename Q, typename Func>
 263         bool find( Q& key, Func f )
 264         {
 265             return bucket( key ).find( key, f );
 266         }
 267         //@cond
 268         template <typename Q, typename Func>
 269         bool find( Q const& key, Func f )
 270         {
 271             return bucket( key ).find( key, f );
 272         }
 273         //@endcond
 274
 275         /// Finds the key \p key using \p pred predicate for searching
 276         /**
 277             The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_func "find(Q&, Func)"
 278             but \p pred is used for key comparing.
 279             \p Less functor has the interface like \p std::less.
 280             \p pred must imply the same element order as the comparator used for building the set.
 281         */
 282         template <typename Q, typename Less, typename Func>
 283         bool find_with( Q& key, Less pred, Func f )
 284         {
 285             return bucket( key ).find_with( key, pred, f );
 286         }
 287         //@cond
 288         template <typename Q, typename Less, typename Func>
 289         bool find_with( Q const& key, Less pred, Func f )
 290         {
 291             return bucket( key ).find_with( key, pred, f );
 292         }
 293         //@endcond
 294
 295         /// Clears the set (non-atomic)
 296         /**
 297             The function unlink all items from the set.
 298             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 299             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 300             <tt> empty() </tt> may return \p true but the set may contain item(s).
 301             Therefore, \p clear may be used only for debugging purposes.
 302
 303             For each item the \p disposer is called after unlinking.
 304         */
 305         void clear()
 306         {
 307             for ( size_t i = 0; i < bucket_count(); ++i )
 308                 m_Buckets[i].clear();
 309             m_ItemCounter.reset();
 310         }
 311
 312
 313         /// Checks if the set is empty
 314         /**
 315             Emptiness is checked by item counting: if item count is zero then the set is empty.
 316             Thus, the correct item counting feature is an important part of Michael's set implementation.
 317         */
 318         bool empty() const
 319         {
 320             return size() == 0;
 321         }
 322
 323         /// Returns item count in the set
 324         size_t size() const
 325         {
 326             return m_ItemCounter;
 327         }
 328
 329         /// Returns the size of hash table
 330         /**
 331             Since \p %MichaelHashSet cannot dynamically extend the hash table size,
 332             the value returned is an constant depending on object initialization parameters;
 333             see MichaelHashSet::MichaelHashSet for explanation.
 334         */
 335         size_t bucket_count() const
 336         {
 337             return m_nHashBitmask + 1;
 338         }
 339
 340     };
 341
 342 }} // namespace cds::intrusive
 343
 344 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
 345