/*
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:
// 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");
- // 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");
-
//@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
//@cond
size_t const m_nHashBitmask;
internal_bucket_type * m_Buckets; ///< bucket table
- item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
+ item_counter m_ItemCounter; ///< Item counter
stat m_Stat; ///< Internal statistics
//@endcond
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
) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
- , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
+ , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
{
for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
construct_bucket<bucket_stat>( it );
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() );
+ bucket_table_allocator().deallocate( m_Buckets, bucket_count());
}
/// Inserts new node
where \p val is the item inserted.
The user-defined functor is called only if the inserting is success.
- @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
+ @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
@ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
synchronization.
#ifdef CDS_DOXYGEN_INVOKED
std::pair<bool, bool>
#else
- typename std::enable_if<
+ typename std::enable_if<
std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
std::pair<bool, bool>
>::type
return bRet;
}
+ /// 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_nonintrusive_MichaelHashSet_hp_extract
The function searches an item with key equal to \p key,
{
internal_bucket_type& b = bucket( key );
typename internal_bucket_type::iterator it = b.find( key );
- if ( it == b.end() )
+ if ( it == b.end())
return end();
return iterator( it, &b, bucket_end());
}
{
internal_bucket_type& b = bucket( key );
typename internal_bucket_type::iterator it = b.find( key );
- if ( it == b.end() )
+ if ( it == b.end())
return end();
- return iterator( it, &b, bucket_end() );
+ return iterator( it, &b, bucket_end());
}
//@endcond
{
internal_bucket_type& b = bucket( key );
typename internal_bucket_type::iterator it = b.find_with( key, pred );
- if ( it == b.end() )
+ if ( it == b.end())
return end();
- return iterator( it, &b, bucket_end() );
+ return iterator( it, &b, bucket_end());
}
//@cond
template <typename Q, typename Less>
{
internal_bucket_type& b = bucket( key );
typename internal_bucket_type::iterator it = b.find_with( key, pred );
- if ( it == b.end() )
+ 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
+ /**
+ @warning 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;
const_iterator get_const_begin() const
{
- return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end() );
+ return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end());
}
const_iterator get_const_end() const
{
- return const_iterator(( bucket_end() -1 )->cend(), bucket_end() - 1, bucket_end() );
+ 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* bucket )
+ typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* b )
{
- new (bucket) internal_bucket_type;
+ new (b) internal_bucket_type;
}
template <typename Stat>
- typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+ typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* b )
{
- new (bucket) internal_bucket_type( m_Stat );
+ new (b) internal_bucket_type( m_Stat );
}
template <typename List, typename... Args>
projects / libcds.git / blobdiff