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