cds/intrusive/michael_set_nogc.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_NOGC_H
  32 #define CDSLIB_INTRUSIVE_MICHAEL_SET_NOGC_H
  33
  34 #include <cds/intrusive/details/michael_set_base.h>
  35 #include <cds/gc/nogc.h>
  36
  37 namespace cds { namespace intrusive {
  38
  39     /// Michael's hash set (template specialization for gc::nogc)
  40     /** @ingroup cds_intrusive_map
  41         \anchor cds_intrusive_MichaelHashSet_nogc
  42
  43         This specialization is so-called append-only when no item
  44         reclamation may be performed. The set does not support deleting of list item.
  45
  46         See \ref cds_intrusive_MichaelHashSet_hp "MichaelHashSet" for description of template parameters.
  47         The template parameter \p OrderedList should be any \p cds::gc::nogc -derived ordered list, for example,
  48         \ref cds_intrusive_MichaelList_nogc "append-only MichaelList".
  49     */
  50     template <
  51         class OrderedList,
  52 #ifdef CDS_DOXYGEN_INVOKED
  53         class Traits = michael_set::traits
  54 #else
  55         class Traits
  56 #endif
  57     >
  58     class MichaelHashSet< cds::gc::nogc, OrderedList, Traits >
  59     {
  60     public:
  61         typedef cds::gc::nogc gc;           ///< Garbage collector
  62         typedef OrderedList   ordered_list; ///< type of ordered list used as a bucket implementation
  63         typedef Traits        traits;       ///< Set traits
  64
  65         typedef typename ordered_list::value_type     value_type;     ///< type of value to be stored in the set
  66         typedef typename ordered_list::key_comparator key_comparator; ///< key comparing functor
  67         typedef typename ordered_list::disposer       disposer;       ///< Node disposer functor
  68 #ifdef CDS_DOXYGEN_INVOKED
  69         typedef typename ordered_list::stat           stat;           ///< Internal statistics
  70 #endif
  71
  72         /// Hash functor for \p value_type and all its derivatives that you use
  73         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
  74         typedef typename traits::item_counter item_counter; ///< Item counter type
  75         typedef typename traits::allocator    allocator;    ///< Bucket table allocator
  76
  77         // GC and OrderedList::gc must be the same
  78         static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
  79
  80         // atomicity::empty_item_counter is not allowed as a item counter
  81         static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
  82             "atomicity::empty_item_counter is not allowed as a item counter");
  83
  84     protected:
  85         //@cond
  86         typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
  87
  88         typedef typename ordered_list::template rebind_traits<
  89             cds::opt::item_counter< cds::atomicity::empty_item_counter >
  90             , cds::opt::stat< typename bucket_stat::wrapped_stat >
  91         >::type internal_bucket_type;
  92
  93         typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
  94         //@endcond
  95
  96     public:
  97         //@cond
  98         typedef typename bucket_stat::stat stat;
  99         //@endcond
 100
 101     protected:
 102         //@cond
 103         hash                    m_HashFunctor; ///< Hash functor
 104         const size_t            m_nHashBitmask;
 105         internal_bucket_type *  m_Buckets;     ///< bucket table
 106         item_counter            m_ItemCounter; ///< Item counter
 107         stat                    m_Stat;        ///< Internal statistics
 108         //@endcond
 109
 110     protected:
 111         //@cond
 112         /// Calculates hash value of \p key
 113         template <typename Q>
 114         size_t hash_value( Q const & key ) const
 115         {
 116             return m_HashFunctor( key ) & m_nHashBitmask;
 117         }
 118
 119         /// Returns the bucket (ordered list) for \p key
 120         template <typename Q>
 121         internal_bucket_type&    bucket( Q const & key )
 122         {
 123             return m_Buckets[ hash_value( key ) ];
 124         }
 125         //@endcond
 126
 127     public:
 128     ///@name Forward iterators
 129     //@{
 130         /// Forward iterator
 131         /**
 132             The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
 133             - it has no post-increment operator
 134             - it iterates items in unordered fashion
 135
 136             The iterator interface:
 137             \code
 138             class iterator {
 139             public:
 140                 // Default constructor
 141                 iterator();
 142
 143                 // Copy construtor
 144                 iterator( iterator const& src );
 145
 146                 // Dereference operator
 147                 value_type * operator ->() const;
 148
 149                 // Dereference operator
 150                 value_type& operator *() const;
 151
 152                 // Preincrement operator
 153                 iterator& operator ++();
 154
 155                 // Assignment operator
 156                 iterator& operator = (iterator const& src);
 157
 158                 // Equality operators
 159                 bool operator ==(iterator const& i ) const;
 160                 bool operator !=(iterator const& i ) const;
 161             };
 162             \endcode
 163         */
 164         typedef michael_set::details::iterator< internal_bucket_type, false >    iterator;
 165
 166         /// Const forward iterator
 167         /**
 168             For iterator's features and requirements see \ref iterator
 169         */
 170         typedef michael_set::details::iterator< internal_bucket_type, true >     const_iterator;
 171
 172         /// Returns a forward iterator addressing the first element in a set
 173         /**
 174             For empty set \code begin() == end() \endcode
 175         */
 176         iterator begin()
 177         {
 178             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count());
 179         }
 180
 181         /// Returns an iterator that addresses the location succeeding the last element in a set
 182         /**
 183             Do not use the value returned by <tt>end</tt> function to access any item.
 184             The returned value can be used only to control reaching the end of the set.
 185             For empty set \code begin() == end() \endcode
 186         */
 187         iterator end()
 188         {
 189             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count());
 190         }
 191
 192         /// Returns a forward const iterator addressing the first element in a set
 193         const_iterator begin() const
 194         {
 195             return cbegin();
 196         }
 197         /// Returns a forward const iterator addressing the first element in a set
 198         const_iterator cbegin() const
 199         {
 200             return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count());
 201         }
 202
 203         /// Returns an const iterator that addresses the location succeeding the last element in a set
 204         const_iterator end() const
 205         {
 206             return cend();
 207         }
 208         /// Returns an const iterator that addresses the location succeeding the last element in a set
 209         const_iterator cend() const
 210         {
 211             return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count());
 212         }
 213     //@}
 214
 215     public:
 216         /// Initializes hash set
 217         /**
 218             The Michael's hash set is an unbounded container, but its hash table is non-expandable.
 219             At construction time you should pass estimated maximum item count and a load factor.
 220             The load factor is average size of one bucket - a small number between 1 and 10.
 221             The bucket is an ordered single-linked list, searching in the bucket has linear complexity <tt>O(nLoadFactor)</tt>.
 222             The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
 223         */
 224         MichaelHashSet(
 225             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 226             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 227         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 228           , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
 229         {
 230             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
 231                 construct_bucket<bucket_stat>( it );
 232         }
 233
 234         /// Clears hash set object and destroys it
 235         ~MichaelHashSet()
 236         {
 237             clear();
 238
 239             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
 240                 it->~internal_bucket_type();
 241             bucket_table_allocator().deallocate( m_Buckets, bucket_count());
 242         }
 243
 244         /// Inserts new node
 245         /**
 246             The function inserts \p val in the set if it does not contain
 247             an item with key equal to \p val.
 248
 249             Returns \p true if \p val is placed into the set, \p false otherwise.
 250         */
 251         bool insert( value_type& val )
 252         {
 253             bool bRet = bucket( val ).insert( val );
 254             if ( bRet )
 255                 ++m_ItemCounter;
 256             return bRet;
 257         }
 258
 259         /// Updates the element
 260         /**
 261             The operation performs inserting or changing data with lock-free manner.
 262
 263             If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
 264             Otherwise, the functor \p func is called with item found.
 265             The functor signature is:
 266             \code
 267                 struct functor {
 268                     void operator()( bool bNew, value_type& item, value_type& val );
 269                 };
 270             \endcode
 271             with arguments:
 272             - \p bNew - \p true if the item has been inserted, \p false otherwise
 273             - \p item - item of the set
 274             - \p val - argument \p val passed into the \p %update() function
 275             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 276             refers to the same thing.
 277
 278             The functor may change non-key fields of the \p item.
 279
 280             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
 281             \p second is \p true if new item has been added or \p false if the item with \p key
 282             already is in the set.
 283
 284             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 285             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 286             synchronization.
 287         */
 288         template <typename Func>
 289         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 290         {
 291             std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
 292             if ( bRet.second )
 293                 ++m_ItemCounter;
 294             return bRet;
 295         }
 296         //@cond
 297         template <typename Func>
 298         CDS_DEPRECATED("ensure() is deprecated, use update()")
 299         std::pair<bool, bool> ensure( value_type& val, Func func )
 300         {
 301             return update( val, func, true );
 302         }
 303         //@endcond
 304
 305         /// Checks whether the set contains \p key
 306         /**
 307
 308             The function searches the item with key equal to \p key
 309             and returns the pointer to an element found or \p nullptr.
 310
 311             Note the hash functor specified for class \p Traits template parameter
 312             should accept a parameter of type \p Q that can be not the same as \p value_type.
 313         */
 314         template <typename Q>
 315         value_type * contains( Q const& key )
 316         {
 317             return bucket( key ).contains( key );
 318         }
 319         //@cond
 320         template <typename Q>
 321         CDS_DEPRECATED("use contains()")
 322         value_type * find( Q const& key )
 323         {
 324             return contains( key );
 325         }
 326         //@endcond
 327
 328         /// Checks whether the set contains \p key using \p pred predicate for searching
 329         /**
 330             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 331             \p Less functor has the interface like \p std::less.
 332             \p Less must imply the same element order as the comparator used for building the set.
 333         */
 334         template <typename Q, typename Less>
 335         value_type * contains( Q const& key, Less pred )
 336         {
 337             return bucket( key ).contains( key, pred );
 338         }
 339         //@cond
 340         template <typename Q, typename Less>
 341         CDS_DEPRECATED("use contains()")
 342         value_type * find_with( Q const& key, Less pred )
 343         {
 344             return contains( key, pred );
 345         }
 346         //@endcond
 347
 348         /// Finds the key \p key
 349         /** \anchor cds_intrusive_MichaelHashSet_nogc_find_func
 350             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 351             The interface of \p Func functor is:
 352             \code
 353             struct functor {
 354                 void operator()( value_type& item, Q& key );
 355             };
 356             \endcode
 357             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 358
 359             The functor can change non-key fields of \p item.
 360             The functor does not serialize simultaneous access to the set \p item. If such access is
 361             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 362
 363             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 364             can modify both arguments.
 365
 366             Note the hash functor specified for class \p Traits template parameter
 367             should accept a parameter of type \p Q that can be not the same as \p value_type.
 368
 369             The function returns \p true if \p key is found, \p false otherwise.
 370         */
 371         template <typename Q, typename Func>
 372         bool find( Q& key, Func f )
 373         {
 374             return bucket( key ).find( key, f );
 375         }
 376         //@cond
 377         template <typename Q, typename Func>
 378         bool find( Q const& key, Func f )
 379         {
 380             return bucket( key ).find( key, f );
 381         }
 382         //@endcond
 383
 384         /// Finds the key \p key using \p pred predicate for searching
 385         /**
 386             The function is an analog of \ref cds_intrusive_MichaelHashSet_nogc_find_func "find(Q&, Func)"
 387             but \p pred is used for key comparing.
 388             \p Less functor has the interface like \p std::less.
 389             \p pred must imply the same element order as the comparator used for building the set.
 390         */
 391         template <typename Q, typename Less, typename Func>
 392         bool find_with( Q& key, Less pred, Func f )
 393         {
 394             return bucket( key ).find_with( key, pred, f );
 395         }
 396         //@cond
 397         template <typename Q, typename Less, typename Func>
 398         bool find_with( Q const& key, Less pred, Func f )
 399         {
 400             return bucket( key ).find_with( key, pred, f );
 401         }
 402         //@endcond
 403
 404         /// Clears the set (non-atomic)
 405         /**
 406             The function unlink all items from the set.
 407             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
 408             If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
 409             <tt> empty() </tt> may return \p true but the set may contain item(s).
 410             Therefore, \p %clear() may be used only for debugging purposes.
 411
 412             For each item the \p disposer is called after unlinking.
 413         */
 414         void clear()
 415         {
 416             for ( size_t i = 0; i < bucket_count(); ++i )
 417                 m_Buckets[i].clear();
 418             m_ItemCounter.reset();
 419         }
 420
 421
 422         /// Checks if the set is empty
 423         /**
 424             Emptiness is checked by item counting: if item count is zero then the set is empty.
 425             Thus, the correct item counting feature is an important part of Michael's set implementation.
 426         */
 427         bool empty() const
 428         {
 429             return size() == 0;
 430         }
 431
 432         /// Returns item count in the set
 433         size_t size() const
 434         {
 435             return m_ItemCounter;
 436         }
 437
 438         /// Returns the size of hash table
 439         /**
 440             Since \p %MichaelHashSet cannot dynamically extend the hash table size,
 441             the value returned is an constant depending on object initialization parameters;
 442             see MichaelHashSet::MichaelHashSet for explanation.
 443         */
 444         size_t bucket_count() const
 445         {
 446             return m_nHashBitmask + 1;
 447         }
 448
 449         /// Returns const reference to internal statistics
 450         stat const& statistics() const
 451         {
 452             return m_Stat;
 453         }
 454
 455     private:
 456         //@cond
 457         template <typename Stat>
 458         typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
 459         {
 460             new (bucket) internal_bucket_type;
 461         }
 462
 463         template <typename Stat>
 464         typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
 465         {
 466             new (bucket) internal_bucket_type( m_Stat );
 467         }
 468         //@endcond
 469     };
 470
 471 }} // namespace cds::intrusive
 472
 473 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_NOGC_H
 474