cds/intrusive/details/michael_set_base.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_DETAILS_MICHAEL_SET_BASE_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
  33
  34 #include <cds/intrusive/details/base.h>
  35 #include <cds/opt/compare.h>
  36 #include <cds/opt/hash.h>
  37 #include <cds/algo/bitop.h>
  38 #include <cds/algo/atomic.h>
  39
  40 namespace cds { namespace intrusive {
  41
  42     /// MichaelHashSet related definitions
  43     /** @ingroup cds_intrusive_helper
  44     */
  45     namespace michael_set {
  46         /// MichaelHashSet traits
  47         struct traits {
  48             /// Hash function
  49             /**
  50                 Hash function converts the key fields of struct \p T stored in the hash-set
  51                 into value of type \p size_t called hash value that is an index of hash table.
  52
  53                 This is mandatory type and has no predefined one.
  54             */
  55             typedef opt::none hash;
  56
  57             /// Item counter
  58             /**
  59                 The item counting is an important part of \p MichaelHashSet algorithm:
  60                 the \p empty() member function depends on correct item counting.
  61                 You may use \p atomicity::empty_item_counter if don't need \p empty() and \p size()
  62                 member functions.
  63
  64                 Default is \p atomicity::item_counter; to avoid false sharing you may use \p atomicity::cache_friendly_item_counter
  65             */
  66             typedef cds::atomicity::item_counter item_counter;
  67
  68             /// Bucket table allocator
  69             /**
  70                 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
  71                 The allocator uses only in constructor for allocating bucket table
  72                 and in destructor for destroying bucket table
  73             */
  74             typedef CDS_DEFAULT_ALLOCATOR   allocator;
  75         };
  76
  77         /// Metafunction converting option list to traits struct
  78         /**
  79             Available \p Options:
  80             - \p opt::hash - mandatory option, specifies hash functor.
  81             - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
  82                 for default type.
  83             - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
  84         */
  85         template <typename... Options>
  86         struct make_traits {
  87             typedef typename cds::opt::make_options< traits, Options...>::type type;   ///< Metafunction result
  88         };
  89
  90         //@cond
  91         namespace details {
  92             static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
  93             {
  94                 if ( nLoadFactor == 0 )
  95                     nLoadFactor = 1;
  96                 if ( nMaxItemCount == 0 )
  97                     nMaxItemCount = 4;
  98                 const size_t nBucketCount = nMaxItemCount / nLoadFactor;
  99                 const size_t exp2 = size_t( 1 ) << cds::bitop::MSB( nBucketCount );
 100
 101                 return ( exp2 < nBucketCount ? exp2 * 2 : exp2 ) - 1;
 102             }
 103
 104             template <typename OrderedList, bool IsConst>
 105             struct list_iterator_selector;
 106
 107             template <typename OrderedList>
 108             struct list_iterator_selector< OrderedList, false>
 109             {
 110                 typedef OrderedList * bucket_ptr;
 111                 typedef typename OrderedList::iterator  type;
 112             };
 113
 114             template <typename OrderedList>
 115             struct list_iterator_selector< OrderedList, true>
 116             {
 117                 typedef OrderedList const * bucket_ptr;
 118                 typedef typename OrderedList::const_iterator  type;
 119             };
 120
 121             template <typename OrderedList, bool IsConst>
 122             class iterator
 123             {
 124                 friend class iterator< OrderedList, !IsConst >;
 125
 126             protected:
 127                 typedef OrderedList bucket_type;
 128                 typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
 129                 typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
 130
 131                 bucket_ptr      m_pCurBucket;
 132                 list_iterator   m_itList;
 133                 bucket_ptr      m_pEndBucket;
 134
 135                 void next()
 136                 {
 137                     if ( m_pCurBucket < m_pEndBucket ) {
 138                         if ( ++m_itList != m_pCurBucket->end())
 139                             return;
 140                         while ( ++m_pCurBucket < m_pEndBucket ) {
 141                             m_itList = m_pCurBucket->begin();
 142                             if ( m_itList != m_pCurBucket->end())
 143                                 return;
 144                         }
 145                     }
 146                     m_pCurBucket = m_pEndBucket - 1;
 147                     m_itList = m_pCurBucket->end();
 148                 }
 149
 150             public:
 151                 typedef typename list_iterator::value_ptr   value_ptr;
 152                 typedef typename list_iterator::value_ref   value_ref;
 153
 154             public:
 155                 iterator()
 156                     : m_pCurBucket( nullptr )
 157                     , m_itList()
 158                     , m_pEndBucket( nullptr )
 159                 {}
 160
 161                 iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
 162                     : m_pCurBucket( pFirst )
 163                     , m_itList( it )
 164                     , m_pEndBucket( pLast )
 165                 {
 166                     if ( it == pFirst->end())
 167                         next();
 168                 }
 169
 170                 iterator( iterator const& src )
 171                     : m_pCurBucket( src.m_pCurBucket )
 172                     , m_itList( src.m_itList )
 173                     , m_pEndBucket( src.m_pEndBucket )
 174                 {}
 175
 176                 value_ptr operator ->() const
 177                 {
 178                     assert( m_pCurBucket != nullptr );
 179                     return m_itList.operator ->();
 180                 }
 181
 182                 value_ref operator *() const
 183                 {
 184                     assert( m_pCurBucket != nullptr );
 185                     return m_itList.operator *();
 186                 }
 187
 188                 /// Pre-increment
 189                 iterator& operator ++()
 190                 {
 191                     next();
 192                     return *this;
 193                 }
 194
 195                 iterator& operator = (const iterator& src)
 196                 {
 197                     m_pCurBucket = src.m_pCurBucket;
 198                     m_pEndBucket = src.m_pEndBucket;
 199                     m_itList = src.m_itList;
 200                     return *this;
 201                 }
 202
 203                 bucket_ptr bucket() const
 204                 {
 205                     return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
 206                 }
 207
 208                 list_iterator const& underlying_iterator() const
 209                 {
 210                     return m_itList;
 211                 }
 212
 213                 template <bool C>
 214                 bool operator ==(iterator<bucket_type, C> const& i) const
 215                 {
 216                     return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
 217                 }
 218                 template <bool C>
 219                 bool operator !=(iterator<OrderedList, C> const& i ) const
 220                 {
 221                     return !( *this == i );
 222                 }
 223             };
 224         }
 225         //@endcond
 226     } // namespace michael_set
 227
 228     //@cond
 229     // Forward declarations
 230     template <class GC, class OrderedList, class Traits = michael_set::traits>
 231     class MichaelHashSet;
 232     //@endcond
 233
 234 }} // namespace cds::intrusive
 235
 236 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H