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
 230             The function searches the item with key equal to \p key
 231             and returns the pointer to an element found or \p nullptr.
 232
 233             Note the hash functor specified for class \p Traits template parameter
 234             should accept a parameter of type \p Q that can be not the same as \p value_type.
 235         */
 236         template <typename Q>
 237         value_type * contains( Q const& key )
 238         {
 239             return bucket( key ).contains( key );
 240         }
 241         //@cond
 242         template <typename Q>
 243         CDS_DEPRECATED("use contains()")
 244         value_type * find( Q const& key )
 245         {
 246             return contains( key );
 247         }
 248         //@endcond
 249
 250         /// Checks whether the set contains \p key using \p pred predicate for searching
 251         /**
 252             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 253             \p Less functor has the interface like \p std::less.
 254             \p Less must imply the same element order as the comparator used for building the set.
 255         */
 256         template <typename Q, typename Less>
 257         value_type * contains( Q const& key, Less pred )
 258         {
 259             return bucket( key ).contains( key, pred );
 260         }
 261         //@cond
 262         template <typename Q, typename Less>
 263         CDS_DEPRECATED("use contains()")
 264         value_type * find_with( Q const& key, Less pred )
 265         {
 266             return contains( key, pred );
 267         }
 268         //@endcond
 269
 270         /// Finds the key \p key
 271         /** \anchor cds_intrusive_MichaelHashSet_nogc_find_func
 272             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 273             The interface of \p Func functor is:
 274             \code
 275             struct functor {
 276                 void operator()( value_type& item, Q& key );
 277             };
 278             \endcode
 279             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 280
 281             The functor can change non-key fields of \p item.
 282             The functor does not serialize simultaneous access to the set \p item. If such access is
 283             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 284
 285             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 286             can modify both arguments.
 287
 288             Note the hash functor specified for class \p Traits template parameter
 289             should accept a parameter of type \p Q that can be not the same as \p value_type.
 290
 291             The function returns \p true if \p key is found, \p false otherwise.
 292         */
 293         template <typename Q, typename Func>
 294         bool find( Q& key, Func f )
 295         {
 296             return bucket( key ).find( key, f );
 297         }
 298         //@cond
 299         template <typename Q, typename Func>
 300         bool find( Q const& key, Func f )
 301         {
 302             return bucket( key ).find( key, f );
 303         }
 304         //@endcond
 305
 306         /// Finds the key \p key using \p pred predicate for searching
 307         /**
 308             The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_func "find(Q&, Func)"
 309             but \p pred is used for key comparing.
 310             \p Less functor has the interface like \p std::less.
 311             \p pred must imply the same element order as the comparator used for building the set.
 312         */
 313         template <typename Q, typename Less, typename Func>
 314         bool find_with( Q& key, Less pred, Func f )
 315         {
 316             return bucket( key ).find_with( key, pred, f );
 317         }
 318         //@cond
 319         template <typename Q, typename Less, typename Func>
 320         bool find_with( Q const& key, Less pred, Func f )
 321         {
 322             return bucket( key ).find_with( key, pred, f );
 323         }
 324         //@endcond
 325
 326         /// Clears the set (non-atomic)
 327         /**
 328             The function unlink all items from the set.
 329             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 330             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
 331             <tt> empty() </tt> may return \p true but the set may contain item(s).
 332             Therefore, \p clear may be used only for debugging purposes.
 333
 334             For each item the \p disposer is called after unlinking.
 335         */
 336         void clear()
 337         {
 338             for ( size_t i = 0; i < bucket_count(); ++i )
 339                 m_Buckets[i].clear();
 340             m_ItemCounter.reset();
 341         }
 342
 343
 344         /// Checks if the set is empty
 345         /**
 346             Emptiness is checked by item counting: if item count is zero then the set is empty.
 347             Thus, the correct item counting feature is an important part of Michael's set implementation.
 348         */
 349         bool empty() const
 350         {
 351             return size() == 0;
 352         }
 353
 354         /// Returns item count in the set
 355         size_t size() const
 356         {
 357             return m_ItemCounter;
 358         }
 359
 360         /// Returns the size of hash table
 361         /**
 362             Since \p %MichaelHashSet cannot dynamically extend the hash table size,
 363             the value returned is an constant depending on object initialization parameters;
 364             see MichaelHashSet::MichaelHashSet for explanation.
 365         */
 366         size_t bucket_count() const
 367         {
 368             return m_nHashBitmask + 1;
 369         }
 370
 371     };
 372
 373 }} // namespace cds::intrusive
 374
 375 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_NOGC_H
 376