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