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