/*
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:
// 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
//@cond
//@cond
const size_t 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
//@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
};
projects / libcds.git / blobdiff