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