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