cds/intrusive/michael_set_nogc.h

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