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