2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
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>
40 namespace cds { namespace intrusive {
42 /// MichaelHashSet related definitions
43 /** @ingroup cds_intrusive_helper
45 namespace michael_set {
46 /// MichaelHashSet traits
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.
53 This is mandatory type and has no predefined one.
55 typedef opt::none hash;
59 The item counting is an important part of \p MichaelHashSet algorithm:
60 the \p empty() member function depends on correct item counting.
61 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
63 Default is \p atomicity::item_counter.
65 typedef cds::atomicity::item_counter item_counter;
67 /// Bucket table allocator
69 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
70 The allocator uses only in constructor for allocating bucket table
71 and in destructor for destroying bucket table
73 typedef CDS_DEFAULT_ALLOCATOR allocator;
76 /// Metafunction converting option list to traits struct
79 - \p opt::hash - mandatory option, specifies hash functor.
80 - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
82 - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
84 template <typename... Options>
86 typedef typename cds::opt::make_options< traits, Options...>::type type; ///< Metafunction result
91 static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
93 if ( nLoadFactor == 0 )
95 if ( nMaxItemCount == 0 )
97 const size_t nBucketCount = nMaxItemCount / nLoadFactor;
98 const size_t exp2 = size_t( 1 ) << cds::bitop::MSB( nBucketCount );
100 return ( exp2 < nBucketCount ? exp2 * 2 : exp2 ) - 1;
103 template <typename OrderedList, bool IsConst>
104 struct list_iterator_selector;
106 template <typename OrderedList>
107 struct list_iterator_selector< OrderedList, false>
109 typedef OrderedList * bucket_ptr;
110 typedef typename OrderedList::iterator type;
113 template <typename OrderedList>
114 struct list_iterator_selector< OrderedList, true>
116 typedef OrderedList const * bucket_ptr;
117 typedef typename OrderedList::const_iterator type;
120 template <typename OrderedList, bool IsConst>
123 friend class iterator < OrderedList, !IsConst >;
125 typedef OrderedList bucket_type;
126 typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
127 typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
129 bucket_ptr m_pCurBucket;
130 list_iterator m_itList;
131 bucket_ptr m_pEndBucket;
135 if ( m_pCurBucket < m_pEndBucket ) {
136 if ( ++m_itList != m_pCurBucket->end() )
138 while ( ++m_pCurBucket < m_pEndBucket ) {
139 m_itList = m_pCurBucket->begin();
140 if ( m_itList != m_pCurBucket->end() )
144 m_pCurBucket = m_pEndBucket - 1;
145 m_itList = m_pCurBucket->end();
149 typedef typename list_iterator::value_ptr value_ptr;
150 typedef typename list_iterator::value_ref value_ref;
154 : m_pCurBucket( nullptr )
156 , m_pEndBucket( nullptr )
159 iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
160 : m_pCurBucket( pFirst )
162 , m_pEndBucket( pLast )
164 if ( it == pFirst->end() )
168 iterator( iterator const& src )
169 : m_pCurBucket( src.m_pCurBucket )
170 , m_itList( src.m_itList )
171 , m_pEndBucket( src.m_pEndBucket )
174 value_ptr operator ->() const
176 assert( m_pCurBucket != nullptr );
177 return m_itList.operator ->();
180 value_ref operator *() const
182 assert( m_pCurBucket != nullptr );
183 return m_itList.operator *();
187 iterator& operator ++()
193 iterator& operator = (const iterator& src)
195 m_pCurBucket = src.m_pCurBucket;
196 m_pEndBucket = src.m_pEndBucket;
197 m_itList = src.m_itList;
201 bucket_ptr bucket() const
203 return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
207 bool operator ==(iterator<bucket_type, C> const& i) const
209 return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
212 bool operator !=(iterator<OrderedList, C> const& i ) const
214 return !( *this == i );
220 } // namespace michael_set
223 // Forward declarations
224 template <class GC, class OrderedList, class Traits = michael_set::traits>
225 class MichaelHashSet;
228 }} // namespace cds::intrusive
230 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H