/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
-
+
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
#define CDSLIB_INTRUSIVE_MICHAEL_SET_H
#include <cds/intrusive/details/michael_set_base.h>
-#include <cds/details/allocator.h>
#include <cds/intrusive/details/iterable_list_base.h>
namespace cds { namespace intrusive {
Template parameters are:
- \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for \p OrderedList
- - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList, \p LazyList.
+ - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations:
+ \p MichaelList, \p LazyList, \p IterableList.
The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
the ordered list.
\code
// Our node type
struct Foo {
- std::string key_; // key field
+ std::string key_; // key field
// ... other fields
};
public:
typedef GC gc; ///< Garbage collector
typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
- typedef ordered_list bucket_type; ///< bucket type
- typedef Traits traits; ///< Set traits
+ typedef Traits traits; ///< Set traits
- typedef typename ordered_list::value_type value_type ; ///< type of value to be stored in the set
- typedef typename ordered_list::key_comparator key_comparator ; ///< key comparing functor
- typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
+ typedef typename ordered_list::value_type value_type ; ///< type of value to be stored in the set
+ typedef typename ordered_list::key_comparator key_comparator ; ///< key comparing functor
+ typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef typename ordered_list::stat stat ; ///< Internal statistics
+#endif
/// Hash functor for \p value_type and all its derivatives that you use
typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
typedef typename traits::item_counter item_counter; ///< Item counter type
+ typedef typename traits::allocator allocator; ///< Bucket table allocator
typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
- /// Bucket table allocator
- typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
-
/// Count of hazard pointer required for the algorithm
static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount;
+ // GC and OrderedList::gc must be the same
+ static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
+
protected:
- item_counter m_ItemCounter; ///< Item counter
- hash m_HashFunctor; ///< Hash functor
- bucket_type * m_Buckets; ///< bucket table
+ //@cond
+ typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
- private:
+ typedef typename ordered_list::template rebind_traits<
+ cds::opt::item_counter< cds::atomicity::empty_item_counter >
+ , cds::opt::stat< typename bucket_stat::wrapped_stat >
+ >::type internal_bucket_type;
+
+ typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
+ //@endcond
+
+ public:
//@cond
- const size_t m_nHashBitmask;
+ typedef typename bucket_stat::stat stat;
//@endcond
protected:
//@cond
- /// Calculates hash value of \p key
- template <typename Q>
- size_t hash_value( const Q& key ) const
- {
- return m_HashFunctor( key ) & m_nHashBitmask;
- }
-
- /// Returns the bucket (ordered list) for \p key
- template <typename Q>
- bucket_type& bucket( const Q& key )
- {
- return m_Buckets[ hash_value( key ) ];
- }
+ hash m_HashFunctor; ///< Hash functor
+ size_t const m_nHashBitmask;
+ internal_bucket_type* m_Buckets; ///< bucket table
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_Stat; ///< Internal statistics
//@endcond
public:
Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
Use this iterator on the concurrent container for debugging purpose only.
- for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
-
*/
- typedef michael_set::details::iterator< bucket_type, false > iterator;
+ typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
/// Const forward iterator
/**
For iterator's features and requirements see \ref iterator
*/
- typedef michael_set::details::iterator< bucket_type, true > const_iterator;
+ typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
/// Returns a forward iterator addressing the first element in a set
/**
*/
iterator begin()
{
- return iterator( m_Buckets[0].begin(), bucket_begin(), bucket_end() );
+ return iterator( m_Buckets[0].begin(), bucket_begin(), bucket_end());
}
/// Returns an iterator that addresses the location succeeding the last element in a set
*/
iterator end()
{
- return iterator( m_Buckets[bucket_count() - 1].end(), bucket_end() + 1, bucket_end() );
+ return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
}
/// Returns a forward const iterator addressing the first element in a set
}
//@}
- private:
- //@cond
- bucket_type * bucket_begin() const
- {
- return m_Buckets;
- }
-
- bucket_type * bucket_end() const
- {
- return m_Buckets + bucket_count();
- }
-
- const_iterator get_const_begin() const
- {
- return const_iterator( m_Buckets[0].cbegin(), bucket_begin(), bucket_end() );
- }
- const_iterator get_const_end() const
- {
- return const_iterator( m_Buckets[bucket_count() - 1].cend(), bucket_end() - 1, bucket_end() );
- }
- //@endcond
-
public:
/// Initializes hash set
- /** @anchor cds_intrusive_MichaelHashSet_hp_ctor
+ /**
The Michael's hash set is an unbounded container, but its hash table is non-expandable.
At construction time you should pass estimated maximum item count and a load factor.
The load factor is average size of one bucket - a small number between 1 and 10.
size_t nMaxItemCount, ///< estimation of max item count in the hash set
size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10.
) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
+ , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
{
- // GC and OrderedList::gc must be the same
- static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
-
- // atomicity::empty_item_counter is not allowed as a item counter
- static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
- "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
- m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
+ for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+ construct_bucket<bucket_stat>( it );
}
/// Clears hash set object and destroys it
~MichaelHashSet()
{
clear();
- bucket_table_allocator().Delete( m_Buckets, bucket_count() );
+
+ for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+ it->~internal_bucket_type();
+ bucket_table_allocator().deallocate( m_Buckets, bucket_count());
}
/// Inserts new node
std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
#else
template <typename Q>
- typename std::enable_if<
+ typename std::enable_if<
std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
std::pair<bool, bool>
>::type
return false;
}
+ /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
+ /**
+ Returns \p true if the operation is successful, \p false otherwise.
+ The function can return \p false if the node the iterator points to has already been deleted
+ by other thread.
+
+ The function does not invalidate the iterator, it remains valid and can be used for further traversing.
+
+ @note \p %erase_at() is supported only for \p %MichaelHashSet based on \p IterableList.
+ */
+#ifdef CDS_DOXYGEN_INVOKED
+ bool erase_at( iterator const& iter )
+#else
+ template <typename Iterator>
+ typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
+ erase_at( Iterator const& iter )
+#endif
+ {
+ assert( iter != end());
+ assert( iter.bucket() != nullptr );
+
+ if ( iter.bucket()->erase_at( iter.underlying_iterator())) {
+ --m_ItemCounter;
+ return true;
+ }
+ return false;
+ }
+
/// Extracts the item with specified \p key
/** \anchor cds_intrusive_MichaelHashSet_hp_extract
The function searches an item with key equal to \p key,
#endif
find( Q& key )
{
- bucket_type& b = bucket( key );
- typename ordered_list::iterator it = b.find( key );
- if ( it == b.end() )
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find( key );
+ if ( it == b.end())
return end();
return iterator( it, &b, bucket_end());
}
typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
find( Q const& key )
{
- bucket_type& b = bucket( key );
- typename ordered_list::iterator it = b.find( key );
- if ( it == b.end() )
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find( key );
+ if ( it == b.end())
return end();
- return iterator( it, &b, bucket_end() );
+ return iterator( it, &b, bucket_end());
}
//@endcond
#endif
find_with( Q& key, Less pred )
{
- bucket_type& b = bucket( key );
- typename ordered_list::iterator it = b.find_with( key, pred );
- if ( it == b.end() )
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find_with( key, pred );
+ if ( it == b.end())
return end();
- return iterator( it, &b, bucket_end() );
+ return iterator( it, &b, bucket_end());
}
//@cond
template <typename Q, typename Less>
typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
find_with( Q const& key, Less pred )
{
- bucket_type& b = bucket( key );
- typename ordered_list::iterator it = b.find_with( key, pred );
- if ( it == b.end() )
+ internal_bucket_type& b = bucket( key );
+ typename internal_bucket_type::iterator it = b.find_with( key, pred );
+ if ( it == b.end())
return end();
- return iterator( it, &b, bucket_end() );
+ return iterator( it, &b, bucket_end());
}
//@endcond
/// Checks if the set is empty
/**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of Michael's set implementation.
+ @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns \p true.
*/
bool empty() const
{
}
/// Returns item count in the set
+ /**
+ If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+ the function always returns 0.
+ */
size_t size() const
{
return m_ItemCounter;
}
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return m_Stat;
+ }
+
/// Returns the size of hash table
/**
Since \p %MichaelHashSet cannot dynamically extend the hash table size,
{
return m_nHashBitmask + 1;
}
+
+ private:
+ //@cond
+ internal_bucket_type * bucket_begin() const
+ {
+ return m_Buckets;
+ }
+
+ internal_bucket_type * bucket_end() const
+ {
+ return m_Buckets + bucket_count();
+ }
+
+ const_iterator get_const_begin() const
+ {
+ return const_iterator( m_Buckets[0].cbegin(), bucket_begin(), bucket_end());
+ }
+ const_iterator get_const_end() const
+ {
+ return const_iterator( bucket_end()[-1].cend(), bucket_end() - 1, bucket_end());
+ }
+
+ template <typename Stat>
+ typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type * b )
+ {
+ new (b) internal_bucket_type;
+ }
+
+ template <typename Stat>
+ typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type * b )
+ {
+ new (b) internal_bucket_type( m_Stat );
+ }
+
+ /// Calculates hash value of \p key
+ template <typename Q>
+ size_t hash_value( const Q& key ) const
+ {
+ return m_HashFunctor( key ) & m_nHashBitmask;
+ }
+
+ /// Returns the bucket (ordered list) for \p key
+ template <typename Q>
+ internal_bucket_type& bucket( const Q& key )
+ {
+ return m_Buckets[hash_value( key )];
+ }
+ //@endcond
};
}} // namespace cds::intrusive
projects / libcds.git / blobdiff