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