#ifndef __CDS_CONTAINER_MICHAEL_SET_BASE_H
#define __CDS_CONTAINER_MICHAEL_SET_BASE_H
-#include <cds/intrusive/michael_set_base.h>
+#include <cds/intrusive/details/michael_set_base.h>
namespace cds { namespace container {
--- /dev/null
+//$$CDS-header$$
+
+#ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
+#define __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
+
+#include <cds/intrusive/details/base.h>
+#include <cds/opt/compare.h>
+#include <cds/opt/hash.h>
+#include <cds/algo/bitop.h>
+#include <cds/cxx11_atomic.h>
+#include <cds/ref.h>
+
+namespace cds { namespace intrusive {
+
+ /// MichaelHashSet related definitions
+ /** @ingroup cds_intrusive_helper
+ */
+ namespace michael_set {
+
+ /// Type traits for MichaelHashSet class
+ struct type_traits {
+ /// Hash function
+ /**
+ Hash function converts the key fields of struct \p T stored in the hash-set
+ into value of type \p size_t called hash value that is an index of hash table.
+
+ This is mandatory type and has no predefined one.
+ */
+ typedef opt::none hash;
+
+ /// Item counter
+ /**
+ The item counting is an important part of MichaelHashSet algorithm:
+ the <tt>empty()</tt> member function depends on correct item counting.
+ Therefore, atomicity::empty_item_counter is not allowed as a type of the option.
+
+ Default is atomicity::item_counter.
+ */
+ typedef atomicity::item_counter item_counter;
+
+ /// Bucket table allocator
+ /**
+ Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
+ The allocator uses only in ctor (for allocating bucket table)
+ and in dtor (for destroying bucket table)
+ */
+ typedef CDS_DEFAULT_ALLOCATOR allocator;
+ };
+
+ /// Metafunction converting option list to traits struct
+ /**
+ This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
+
+ Available \p Options:
+ - opt::hash - mandatory option, specifies hash functor.
+ - opt::item_counter - optional, specifies item counting policy. See type_traits::item_counter
+ for default type.
+ - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
+
+ See \ref MichaelHashSet, \ref type_traits.
+ */
+ template <typename... Options>
+ struct make_traits {
+ typedef typename cds::opt::make_options< type_traits, Options...>::type type ; ///< Result of metafunction
+ };
+
+ //@cond
+ namespace details {
+ static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
+ {
+ if ( nLoadFactor == 0 )
+ nLoadFactor = 1;
+ if ( nMaxItemCount == 0 )
+ nMaxItemCount = 4;
+ const size_t nBucketCount = (size_t)( nMaxItemCount / nLoadFactor );
+ const size_t nLog2 = cds::bitop::MSB( nBucketCount );
+
+ return (( size_t( 1 << nLog2 ) < nBucketCount ? size_t( 1 << (nLog2 + 1) ) : size_t( 1 << nLog2 ))) - 1;
+ }
+
+ template <typename OrderedList, bool IsConst>
+ struct list_iterator_selector;
+
+ template <typename OrderedList>
+ struct list_iterator_selector< OrderedList, false>
+ {
+ typedef OrderedList * bucket_ptr;
+ typedef typename OrderedList::iterator type;
+ };
+
+ template <typename OrderedList>
+ struct list_iterator_selector< OrderedList, true>
+ {
+ typedef OrderedList const * bucket_ptr;
+ typedef typename OrderedList::const_iterator type;
+ };
+
+ template <typename OrderedList, bool IsConst>
+ class iterator
+ {
+ protected:
+ typedef OrderedList bucket_type;
+ typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
+ typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
+
+ bucket_ptr m_pCurBucket;
+ list_iterator m_itList;
+ bucket_ptr m_pEndBucket;
+
+ void next()
+ {
+ if ( m_pCurBucket < m_pEndBucket ) {
+ if ( ++m_itList != m_pCurBucket->end() )
+ return;
+ while ( ++m_pCurBucket < m_pEndBucket ) {
+ m_itList = m_pCurBucket->begin();
+ if ( m_itList != m_pCurBucket->end() )
+ return;
+ }
+ }
+ m_pCurBucket = m_pEndBucket - 1;
+ m_itList = m_pCurBucket->end();
+ }
+
+ public:
+ typedef typename list_iterator::value_ptr value_ptr;
+ typedef typename list_iterator::value_ref value_ref;
+
+ public:
+ iterator()
+ : m_pCurBucket( nullptr )
+ , m_itList()
+ , m_pEndBucket( nullptr )
+ {}
+
+ iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
+ : m_pCurBucket( pFirst )
+ , m_itList( it )
+ , m_pEndBucket( pLast )
+ {
+ if ( it == pFirst->end() )
+ next();
+ }
+
+ iterator( iterator const& src )
+ : m_pCurBucket( src.m_pCurBucket )
+ , m_itList( src.m_itList )
+ , m_pEndBucket( src.m_pEndBucket )
+ {}
+
+ value_ptr operator ->() const
+ {
+ assert( m_pCurBucket != nullptr );
+ return m_itList.operator ->();
+ }
+
+ value_ref operator *() const
+ {
+ assert( m_pCurBucket != nullptr );
+ return m_itList.operator *();
+ }
+
+ /// Pre-increment
+ iterator& operator ++()
+ {
+ next();
+ return *this;
+ }
+
+ iterator& operator = (const iterator& src)
+ {
+ m_pCurBucket = src.m_pCurBucket;
+ m_pEndBucket = src.m_pEndBucket;
+ m_itList = src.m_itList;
+ return *this;
+ }
+
+ bucket_ptr bucket() const
+ {
+ return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
+ }
+
+ template <bool C>
+ bool operator ==(iterator<OrderedList, C> const& i ) const
+ {
+ return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
+ }
+ template <bool C>
+ bool operator !=(iterator<OrderedList, C> const& i ) const
+ {
+ return !( *this == i );
+ }
+
+ };
+ }
+ //@endcond
+ }
+
+ //@cond
+ // Forward declarations
+ template <class GC, class OrderedList, class Traits = michael_set::type_traits>
+ class MichaelHashSet;
+ //@endcond
+
+}} // namespace cds::intrusive
+
+#endif // #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
#ifndef __CDS_INTRUSIVE_MICHAEL_SET_H
#define __CDS_INTRUSIVE_MICHAEL_SET_H
-#include <cds/intrusive/michael_set_base.h>
+#include <cds/intrusive/details/michael_set_base.h>
#include <cds/details/allocator.h>
namespace cds { namespace intrusive {
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_INTRUSIVE_MICHAEL_SET_BASE_H
-#define __CDS_INTRUSIVE_MICHAEL_SET_BASE_H
-
-#include <cds/intrusive/details/base.h>
-#include <cds/opt/compare.h>
-#include <cds/opt/hash.h>
-#include <cds/algo/bitop.h>
-#include <cds/cxx11_atomic.h>
-#include <cds/ref.h>
-
-namespace cds { namespace intrusive {
-
- /// MichaelHashSet related definitions
- /** @ingroup cds_intrusive_helper
- */
- namespace michael_set {
-
- /// Type traits for MichaelHashSet class
- struct type_traits {
- /// Hash function
- /**
- Hash function converts the key fields of struct \p T stored in the hash-set
- into value of type \p size_t called hash value that is an index of hash table.
-
- This is mandatory type and has no predefined one.
- */
- typedef opt::none hash;
-
- /// Item counter
- /**
- The item counting is an important part of MichaelHashSet algorithm:
- the <tt>empty()</tt> member function depends on correct item counting.
- Therefore, atomicity::empty_item_counter is not allowed as a type of the option.
-
- Default is atomicity::item_counter.
- */
- typedef atomicity::item_counter item_counter;
-
- /// Bucket table allocator
- /**
- Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
- The allocator uses only in ctor (for allocating bucket table)
- and in dtor (for destroying bucket table)
- */
- typedef CDS_DEFAULT_ALLOCATOR allocator;
- };
-
- /// Metafunction converting option list to traits struct
- /**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
-
- Available \p Options:
- - opt::hash - mandatory option, specifies hash functor.
- - opt::item_counter - optional, specifies item counting policy. See type_traits::item_counter
- for default type.
- - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
-
- See \ref MichaelHashSet, \ref type_traits.
- */
- template <typename... Options>
- struct make_traits {
- typedef typename cds::opt::make_options< type_traits, Options...>::type type ; ///< Result of metafunction
- };
-
- //@cond
- namespace details {
- static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
- {
- if ( nLoadFactor == 0 )
- nLoadFactor = 1;
- if ( nMaxItemCount == 0 )
- nMaxItemCount = 4;
- const size_t nBucketCount = (size_t)( nMaxItemCount / nLoadFactor );
- const size_t nLog2 = cds::bitop::MSB( nBucketCount );
-
- return (( size_t( 1 << nLog2 ) < nBucketCount ? size_t( 1 << (nLog2 + 1) ) : size_t( 1 << nLog2 ))) - 1;
- }
-
- template <typename OrderedList, bool IsConst>
- struct list_iterator_selector;
-
- template <typename OrderedList>
- struct list_iterator_selector< OrderedList, false>
- {
- typedef OrderedList * bucket_ptr;
- typedef typename OrderedList::iterator type;
- };
-
- template <typename OrderedList>
- struct list_iterator_selector< OrderedList, true>
- {
- typedef OrderedList const * bucket_ptr;
- typedef typename OrderedList::const_iterator type;
- };
-
- template <typename OrderedList, bool IsConst>
- class iterator
- {
- protected:
- typedef OrderedList bucket_type;
- typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
- typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
-
- bucket_ptr m_pCurBucket;
- list_iterator m_itList;
- bucket_ptr m_pEndBucket;
-
- void next()
- {
- if ( m_pCurBucket < m_pEndBucket ) {
- if ( ++m_itList != m_pCurBucket->end() )
- return;
- while ( ++m_pCurBucket < m_pEndBucket ) {
- m_itList = m_pCurBucket->begin();
- if ( m_itList != m_pCurBucket->end() )
- return;
- }
- }
- m_pCurBucket = m_pEndBucket - 1;
- m_itList = m_pCurBucket->end();
- }
-
- public:
- typedef typename list_iterator::value_ptr value_ptr;
- typedef typename list_iterator::value_ref value_ref;
-
- public:
- iterator()
- : m_pCurBucket( nullptr )
- , m_itList()
- , m_pEndBucket( nullptr )
- {}
-
- iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
- : m_pCurBucket( pFirst )
- , m_itList( it )
- , m_pEndBucket( pLast )
- {
- if ( it == pFirst->end() )
- next();
- }
-
- iterator( iterator const& src )
- : m_pCurBucket( src.m_pCurBucket )
- , m_itList( src.m_itList )
- , m_pEndBucket( src.m_pEndBucket )
- {}
-
- value_ptr operator ->() const
- {
- assert( m_pCurBucket != nullptr );
- return m_itList.operator ->();
- }
-
- value_ref operator *() const
- {
- assert( m_pCurBucket != nullptr );
- return m_itList.operator *();
- }
-
- /// Pre-increment
- iterator& operator ++()
- {
- next();
- return *this;
- }
-
- iterator& operator = (const iterator& src)
- {
- m_pCurBucket = src.m_pCurBucket;
- m_pEndBucket = src.m_pEndBucket;
- m_itList = src.m_itList;
- return *this;
- }
-
- bucket_ptr bucket() const
- {
- return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
- }
-
- template <bool C>
- bool operator ==(iterator<OrderedList, C> const& i ) const
- {
- return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
- }
- template <bool C>
- bool operator !=(iterator<OrderedList, C> const& i ) const
- {
- return !( *this == i );
- }
-
- };
- }
- //@endcond
- }
-
- //@cond
- // Forward declarations
- template <class GC, class OrderedList, class Traits = michael_set::type_traits>
- class MichaelHashSet;
- //@endcond
-
-}} // namespace cds::intrusive
-
-#endif // #ifndef __CDS_INTRUSIVE_MICHAEL_SET_BASE_H
#ifndef __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
#define __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H
-#include <cds/intrusive/michael_set_base.h>
+#include <cds/intrusive/details/michael_set_base.h>
#include <cds/gc/nogc.h>
#include <cds/details/allocator.h>
#ifndef __CDS_INTRUSIVE_MICHAEL_SET_RCU_H
#define __CDS_INTRUSIVE_MICHAEL_SET_RCU_H
-#include <cds/intrusive/michael_set_base.h>
+#include <cds/intrusive/details/michael_set_base.h>
#include <cds/details/allocator.h>
namespace cds { namespace intrusive {
<ClInclude Include="..\..\..\cds\intrusive\details\ellen_bintree_base.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\details\lazy_list_base.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\details\michael_list_base.h" />\r
+ <ClInclude Include="..\..\..\cds\intrusive\details\michael_set_base.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\details\single_link_struct.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_hp.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_ptb.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\michael_list_nogc.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\michael_list_ptb.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\michael_set.h" />\r
- <ClInclude Include="..\..\..\cds\intrusive\michael_set_base.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\michael_set_nogc.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\moir_queue.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\msqueue.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\michael_set.h">\r
<Filter>Header Files\cds\intrusive</Filter>\r
</ClInclude>\r
- <ClInclude Include="..\..\..\cds\intrusive\michael_set_base.h">\r
- <Filter>Header Files\cds\intrusive</Filter>\r
- </ClInclude>\r
<ClInclude Include="..\..\..\cds\intrusive\michael_set_nogc.h">\r
<Filter>Header Files\cds\intrusive</Filter>\r
</ClInclude>\r
<ClInclude Include="..\..\..\cds\intrusive\impl\michael_list.h">\r
<Filter>Header Files\cds\intrusive\impl</Filter>\r
</ClInclude>\r
+ <ClInclude Include="..\..\..\cds\intrusive\details\michael_set_base.h">\r
+ <Filter>Header Files\cds\intrusive\details</Filter>\r
+ </ClInclude>\r
</ItemGroup>\r
</Project>
\ No newline at end of file
projects / libcds.git / commitdiff