/*
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:
\p key_type and an argument of template type \p K must meet the following requirements:
- \p key_type should be constructible from value of type \p K;
- the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
- <tt> hash( key_type(key) ) == hash( key ) </tt>
+ <tt> hash( key_type(key)) == hash( key ) </tt>
- values of type \p key_type and \p K should be comparable
There are the specializations:
typedef typename traits::allocator allocator; ///< Bucket table allocator
typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
+#ifdef CDS_DOXYGEN_INVOKED
typedef typename ordered_list::stat stat; ///< Internal statistics
+ /// Guarded pointer - a result of \p get() and \p extract() functions
+ typedef typename ordered_list::guarded_ptr guarded_ptr;
+#endif
/// Hash functor for \ref key_type and all its derivatives that you use
typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
// 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,
- "atomicity::empty_item_counter is not allowed as a item counter");
-
static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
-#ifdef CDS_DOXYGEN_INVOKED
- /// Wrapped internal statistics for \p ordered_list
- typedef implementatin_specific bucket_stat;
-#else
+ //@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
-#endif
-#ifdef CDS_DOXYGEN_INVOKED
- /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics
- typedef modified_ordered_list internal_bucket_type;
-#else
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;
-#endif
- /// Guarded pointer - a result of \p get() and \p extract() functions
typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
-
- //@cond
- /// Bucket table allocator
typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
+ typedef typename bucket_stat::stat stat;
//@endcond
protected:
//@cond
const size_t m_nHashBitmask;
- internal_bucket_type * m_Buckets; ///< bucket table
- item_counter m_ItemCounter; ///< Item counter
+ internal_bucket_type* m_Buckets; ///< bucket table
hash m_HashFunctor; ///< Hash functor
- typename bucket_stat::stat m_Stat; ///< Internal statistics
+ item_counter m_ItemCounter; ///< Item counter
+ stat m_Stat; ///< Internal statistics
//@endcond
protected:
//@cond
/// Forward iterator
template <bool IsConst>
- class iterator_type: private cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
+ class iterator_type: protected cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
{
typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class;
friend class MichaelHashMap;
/// Equality operator
template <bool C>
- bool operator ==(iterator_type<C> const& i )
+ bool operator ==(iterator_type<C> const& i ) const
{
return base_class::operator ==( i );
}
/// Equality operator
template <bool C>
- bool operator !=(iterator_type<C> const& i )
+ bool operator !=(iterator_type<C> const& i ) const
{
return !( *this == i );
}
*/
iterator begin()
{
- return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end() );
+ return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
}
/// Returns an iterator that addresses the location succeeding the last element in a map
*/
iterator end()
{
- return iterator( bucket_end()[-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 map
size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
)
: m_nHashBitmask( michael_map::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 with key and default value
(note that in this case the \ref key_type should be constructible from type \p K).
Otherwise, if \p key is found, the functor \p func is called with item found.
- The functor \p func signature depends of \p OrderedList:
+ The functor \p func signature depends on \p OrderedList:
<b>for \p MichaelKVList, \p LazyKVList</b>
\code
\p second is true if new item has been added or \p false if the item with \p key
already exists.
- @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
+ @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
\ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
synchronization.
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val is not found in the map, then \p val is inserted iff \p bAllowInsert is \p true.
+ If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
Otherwise, the current element is changed to \p val, the old element will be retired later.
Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
#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 map)
+ /**
+ 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 %MichaelHashMap 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_MichaelHashMap_hp_extract
The function searches an item with key equal to \p key,
return bucket( key ).find( key, f );
}
+ /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
+ /**
+ If \p key is not found the function returns \p end().
+
+ @note This function is supported only for map based on \p IterableList
+ */
+ template <typename K>
+#ifdef CDS_DOXYGEN_INVOKED
+ iterator
+#else
+ typename std::enable_if< std::is_same<K,K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+ find( K const& key )
+ {
+ auto& b = bucket( key );
+ auto it = b.find( key );
+ if ( it == b.end())
+ return end();
+ return iterator( it, &b, bucket_end());
+ }
+
+
/// Finds the key \p val using \p pred predicate for searching
/**
The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
return bucket( key ).find_with( key, pred, f );
}
+ /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
+ /**
+ The function is an analog of \p find(K&) but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p pred must imply the same element order as the comparator used for building the set.
+
+ If \p key is not found the function returns \p end().
+
+ @note This function is supported only for map based on \p IterableList
+ */
+ template <typename K, typename Less>
+#ifdef CDS_DOXYGEN_INVOKED
+ iterator
+#else
+ typename std::enable_if< std::is_same<K, K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+ find_with( K const& key, Less pred )
+ {
+ auto& b = bucket( key );
+ auto it = b.find_with( key, pred );
+ if ( it == b.end())
+ return end();
+ return iterator( it, &b, bucket_end());
+ }
+
/// Checks whether the map contains \p key
/**
The function searches the item with key equal to \p key
{
return bucket( key ).contains( key );
}
- //@cond
- template <typename K>
- CDS_DEPRECATED("deprecated, use contains()")
- bool find( K const& key )
- {
- return bucket( key ).contains( key );
- }
- //@endcond
/// Checks whether the map contains \p key using \p pred predicate for searching
/**
{
return bucket( key ).contains( key, pred );
}
- //@cond
- template <typename K, typename Less>
- CDS_DEPRECATED("deprecated, use contains()")
- bool find_with( K const& key, Less pred )
- {
- return bucket( key ).contains( key, pred );
- }
- //@endcond
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_MichaelHashMap_hp_get
/// Checks if the map is empty
/**
- Emptiness is checked by item counting: if item count is zero then the map is empty.
- Thus, the correct item counting is an important part of the map 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 map
+ /**
+ 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 );
}
//@endcond
};