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