cds/container/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-2016
   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_CONTAINER_MICHAEL_SET_NOGC_H
  32 #define CDSLIB_CONTAINER_MICHAEL_SET_NOGC_H
  33
  34 #include <cds/container/details/michael_set_base.h>
  35 #include <cds/gc/nogc.h>
  36 #include <cds/details/allocator.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// Michael's hash set (template specialization for gc::nogc)
  41     /** @ingroup cds_nonintrusive_set
  42         \anchor cds_nonintrusive_MichaelHashSet_nogc
  43
  44         This specialization is so-called append-only when no item
  45         reclamation may be performed. The class does not support deleting of list item.
  46
  47         See \ref cds_nonintrusive_MichaelHashSet_hp "MichaelHashSet" for description of template parameters.
  48         The template parameter \p OrderedList should be any \p gc::nogc -derived ordered list, for example,
  49         \ref cds_nonintrusive_MichaelList_nogc "append-only MichaelList".
  50     */
  51     template <
  52         class OrderedList,
  53 #ifdef CDS_DOXYGEN_INVOKED
  54         class Traits = michael_set::traits
  55 #else
  56         class Traits
  57 #endif
  58     >
  59     class MichaelHashSet< cds::gc::nogc, OrderedList, Traits >
  60     {
  61     public:
  62         typedef cds::gc::nogc gc;        ///< Garbage collector
  63         typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation
  64         typedef Traits      traits;      ///< Set traits
  65
  66         typedef typename bucket_type::value_type        value_type;     ///< type of value stored in the list
  67         typedef typename bucket_type::key_comparator    key_comparator; ///< key comparison functor
  68
  69         /// Hash functor for \ref value_type and all its derivatives that you use
  70         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
  71         typedef typename traits::item_counter  item_counter; ///< Item counter type
  72
  73         /// Bucket table allocator
  74         typedef cds::details::Allocator< bucket_type, typename traits::allocator >  bucket_table_allocator;
  75
  76     protected:
  77         //@cond
  78         typedef typename bucket_type::iterator        bucket_iterator;
  79         typedef typename bucket_type::const_iterator  bucket_const_iterator;
  80         //@endcond
  81
  82     protected:
  83         item_counter    m_ItemCounter;   ///< Item counter
  84         hash            m_HashFunctor;   ///< Hash functor
  85         bucket_type *   m_Buckets;       ///< bucket table
  86
  87     private:
  88         //@cond
  89         const size_t    m_nHashBitmask;
  90         //@endcond
  91
  92     protected:
  93         //@cond
  94         /// Calculates hash value of \p key
  95         template <typename Q>
  96         size_t hash_value( const Q& key ) const
  97         {
  98             return m_HashFunctor( key ) & m_nHashBitmask;
  99         }
 100
 101         /// Returns the bucket (ordered list) for \p key
 102         template <typename Q>
 103         bucket_type&    bucket( const Q& key )
 104         {
 105             return m_Buckets[ hash_value( key ) ];
 106         }
 107         //@endcond
 108
 109     public:
 110     ///@name Forward iterators
 111     //@{
 112         /// Forward iterator
 113         /**
 114             The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
 115             - it has no post-increment operator
 116             - it iterates items in unordered fashion
 117
 118             The iterator interface:
 119             \code
 120             class iterator {
 121             public:
 122                 // Default constructor
 123                 iterator();
 124
 125                 // Copy construtor
 126                 iterator( iterator const& src );
 127
 128                 // Dereference operator
 129                 value_type * operator ->() const;
 130
 131                 // Dereference operator
 132                 value_type& operator *() const;
 133
 134                 // Preincrement operator
 135                 iterator& operator ++();
 136
 137                 // Assignment operator
 138                 iterator& operator = (iterator const& src);
 139
 140                 // Equality operators
 141                 bool operator ==(iterator const& i ) const;
 142                 bool operator !=(iterator const& i ) const;
 143             };
 144             \endcode
 145         */
 146         typedef michael_set::details::iterator< bucket_type, false >    iterator;
 147
 148         /// Const forward iterator
 149         /**
 150             For iterator's features and requirements see \ref iterator
 151         */
 152         typedef michael_set::details::iterator< bucket_type, true >     const_iterator;
 153
 154         /// Returns a forward iterator addressing the first element in a set
 155         /**
 156             For empty set \code begin() == end() \endcode
 157         */
 158         iterator begin()
 159         {
 160             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
 161         }
 162
 163         /// Returns an iterator that addresses the location succeeding the last element in a set
 164         /**
 165             Do not use the value returned by <tt>end</tt> function to access any item.
 166             The returned value can be used only to control reaching the end of the set.
 167             For empty set \code begin() == end() \endcode
 168         */
 169         iterator end()
 170         {
 171             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 172         }
 173
 174         /// Returns a forward const iterator addressing the first element in a set
 175         const_iterator begin() const
 176         {
 177             return get_const_begin();
 178         }
 179
 180         /// Returns a forward const iterator addressing the first element in a set
 181         const_iterator cbegin() const
 182         {
 183             return get_const_begin();
 184         }
 185
 186         /// Returns an const iterator that addresses the location succeeding the last element in a set
 187         const_iterator end() const
 188         {
 189             return get_const_end();
 190         }
 191
 192         /// Returns an const iterator that addresses the location succeeding the last element in a set
 193         const_iterator cend() const
 194         {
 195             return get_const_end();
 196         }
 197     //@}
 198
 199     private:
 200         //@cond
 201         const_iterator get_const_begin() const
 202         {
 203             return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
 204         }
 205         const_iterator get_const_end() const
 206         {
 207             return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
 208         }
 209         //@endcond
 210
 211     public:
 212         /// Initialize hash set
 213         /**
 214             The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
 215             when you create an object.
 216             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
 217             Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
 218
 219             The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
 220         */
 221         MichaelHashSet(
 222             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
 223             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
 224         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
 225         {
 226             // GC and OrderedList::gc must be the same
 227             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
 228
 229             // atomicity::empty_item_counter is not allowed as a item counter
 230             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
 231                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 232
 233             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
 234         }
 235
 236         /// Clears hash set and destroys it
 237         ~MichaelHashSet()
 238         {
 239             clear();
 240             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
 241         }
 242
 243         /// Inserts new node
 244         /**
 245             The function inserts \p val in the set if it does not contain
 246             an item with key equal to \p val.
 247
 248             Return an iterator pointing to inserted item if success, otherwise \ref end()
 249         */
 250         template <typename Q>
 251         iterator insert( const Q& val )
 252         {
 253             bucket_type& refBucket = bucket( val );
 254             bucket_iterator it = refBucket.insert( val );
 255
 256             if ( it != refBucket.end() ) {
 257                 ++m_ItemCounter;
 258                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 259             }
 260
 261             return end();
 262         }
 263
 264         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 265         /**
 266             Return an iterator pointing to inserted item if success \ref end() otherwise
 267         */
 268         template <typename... Args>
 269         iterator emplace( Args&&... args )
 270         {
 271             bucket_type& refBucket = bucket( value_type(std::forward<Args>(args)...));
 272             bucket_iterator it = refBucket.emplace( std::forward<Args>(args)... );
 273
 274             if ( it != refBucket.end() ) {
 275                 ++m_ItemCounter;
 276                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 277             }
 278
 279             return end();
 280         }
 281
 282         /// Updates the element
 283         /**
 284             The operation performs inserting or changing data with lock-free manner.
 285
 286             If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
 287
 288             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 289             item found or inserted, or \p end() if \p bAllowInsert is \p false,
 290
 291             \p second is true if new item has been added or \p false if the item is already in the set.
 292
 293             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
 294             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
 295             synchronization.
 296         */
 297         template <typename Q>
 298         std::pair<iterator, bool> update( Q const& val, bool bAllowInsert = true )
 299         {
 300             bucket_type& refBucket = bucket( val );
 301             std::pair<bucket_iterator, bool> ret = refBucket.update( val, bAllowInsert );
 302
 303             if ( ret.first != refBucket.end() ) {
 304                 if ( ret.second )
 305                     ++m_ItemCounter;
 306                 return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second );
 307             }
 308             return std::make_pair( end(), ret.second );
 309         }
 310         //@cond
 311         template <typename Q>
 312         CDS_DEPRECATED("ensure() is deprecated, use update()")
 313         std::pair<iterator, bool> ensure( Q const& val )
 314         {
 315             return update( val, true );
 316         }
 317         //@endcond
 318
 319         /// Checks whether the set contains \p key
 320         /**
 321             The function searches the item with key equal to \p key
 322             and returns an iterator pointed to item found if the key is found,
 323             or \ref end() otherwise.
 324
 325             Note the hash functor specified for class \p Traits template parameter
 326             should accept a parameter of type \p Q that can be not the same as \p value_type.
 327         */
 328         template <typename Q>
 329         iterator contains( Q const& key )
 330         {
 331             bucket_type& refBucket = bucket( key );
 332             bucket_iterator it = refBucket.contains( key );
 333             if ( it != refBucket.end() )
 334                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 335
 336             return end();
 337         }
 338         //@cond
 339         template <typename Q>
 340         CDS_DEPRECATED("use contains()")
 341         iterator find( Q const& key )
 342         {
 343             return contains( key );
 344         }
 345         //@endcond
 346
 347         /// Checks whether the set contains \p key using \p pred predicate for searching
 348         /**
 349             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 350             \p Less functor has the interface like \p std::less.
 351             \p Less must imply the same element order as the comparator used for building the set.
 352         */
 353         template <typename Q, typename Less>
 354         iterator contains( Q const& key, Less pred )
 355         {
 356             bucket_type& refBucket = bucket( key );
 357             bucket_iterator it = refBucket.contains( key, pred );
 358             if ( it != refBucket.end() )
 359                 return iterator( it, &refBucket, m_Buckets + bucket_count() );
 360
 361             return end();
 362         }
 363         //@cond
 364         template <typename Q, typename Less>
 365         CDS_DEPRECATED("use contains()")
 366         iterator find_with( Q const& key, Less pred )
 367         {
 368             return contains( key, pred );
 369         }
 370         //@endcond
 371
 372         /// Clears the set (not atomic)
 373         void clear()
 374         {
 375             for ( size_t i = 0; i < bucket_count(); ++i )
 376                 m_Buckets[i].clear();
 377             m_ItemCounter.reset();
 378         }
 379
 380         /// Checks if the set is empty
 381         /**
 382             The emptiness is checked by the item counting: if item count is zero then the set is empty.
 383             Thus, the correct item counting feature is an important part of Michael's set implementation.
 384         */
 385         bool empty() const
 386         {
 387             return size() == 0;
 388         }
 389
 390         /// Returns item count in the set
 391         size_t size() const
 392         {
 393             return m_ItemCounter;
 394         }
 395
 396         /// Returns the size of hash table
 397         /**
 398             Since \p %MichaelHashSet cannot dynamically extend the hash table size,
 399             the value returned is an constant depending on object initialization parameters;
 400             see MichaelHashSet::MichaelHashSet for explanation.
 401         */
 402         size_t bucket_count() const
 403         {
 404             return m_nHashBitmask + 1;
 405         }
 406     };
 407
 408 }} // cds::container
 409
 410 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_NOGC_H