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