#include <cds/intrusive/impl/multilevel_hashset.h>
#include <cds/container/details/multilevel_hashmap_base.h>
+#include <cds/container/details/guarded_ptr_cast.h>
namespace cds { namespace container {
We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which\r
we need to operate; this is initially one, because of \p head.\r
\r
- That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit\r
+ That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit\r
string</b> and rehash incrementally.\r
\r
@note Two important things you should keep in mind when you're using \p %MultiLevelHashMap:\r
or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which\r
converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.\r
- \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,\r
- have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashMap does not maintain the key,\r
+ have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,\r
it maintains its fixed-size hash value.\r
\r
- The set supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators".\r
+ The map supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators".\r
\r
Template parameters:\r
- \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"\r
typedef typename traits::back_off back_off; ///< Backoff strategy
typedef typename traits::stat stat; ///< Internal statistics type
- typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
-
/// Count of hazard pointers required
static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount;
typedef typename maker::node_type node_type;
typedef typename maker::cxx_node_allocator cxx_node_allocator;
typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
+
+ template <class Iterator>
+ class bidirectional_iterator : protected Iterator
+ {
+ friend class MultiLevelHashMap;
+ typedef Iterator base_class;
+ public:
+ typedef typename std::conditional< base_class::c_bConstantIterator, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< base_class::c_bConstantIterator, value_type const&, value_type&>::type value_ref; ///< Value reference
+
+ public:
+ bidirectional_iterator() CDS_NOEXCEPT
+ : base_class()
+ {}
+
+ bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ : base_class( rhs )
+ {}
+
+ bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ {
+ base_class::operator=( rhs );
+ return *this;
+ }
+
+ bidirectional_iterator& operator++()
+ {
+ base_class::operator++();
+ return *this;
+ }
+
+ bidirectional_iterator& operator--()
+ {
+ base_class::operator--();
+ return *this;
+ }
+
+ value_ptr operator ->() const CDS_NOEXCEPT
+ {
+ return pointer();
+ }
+
+ value_ref operator *() const CDS_NOEXCEPT
+ {
+ value_ptr p = pointer();
+ assert( p );
+ return *p;
+ }
+
+ void release()
+ {
+ base_class::release();
+ }
+
+ template <class It>
+ bool operator ==(It const& rhs) const CDS_NOEXCEPT
+ {
+ return base_class::operator==( rhs );
+ }
+
+ template <class It>
+ bool operator !=(It const& rhs) const CDS_NOEXCEPT
+ {
+ return !( *this == rhs );
+ }
+
+ protected:
+ bidirectional_iterator( base_class&& it ) CDS_NOEXCEPT
+ : base_class( it )
+ {}
+
+ value_ptr pointer() const CDS_NOEXCEPT
+ {
+ typename base_class::value_ptr p = base_class::pointer();
+ return p ? &p->m_Value : nullptr;
+ }
+
+ node_type * node_pointer() const CDS_NOEXCEPT
+ {
+ return base_class::pointer();
+ }
+ };
//@endcond
+ public:
+#ifdef CDS_DOXYGEN_INVOKED
+ /// Guarded pointer
+ typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
+#else
+ typedef typename gc::template guarded_ptr< node_type, value_type, cds::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+#endif
+
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional iterator" type
+ typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional const iterator" type
+ typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse iterator" type
+ typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse const iterator" type
+#else
+ typedef bidirectional_iterator<typename base_class::iterator> iterator;
+ typedef bidirectional_iterator<typename base_class::const_iterator> const_iterator;
+ typedef bidirectional_iterator<typename base_class::reverse_iterator> reverse_iterator;
+ typedef bidirectional_iterator<typename base_class::const_reverse_iterator> const_reverse_iterator;
+#endif
+
protected:
//@cond
hasher m_Hasher;
- The \p key_type should be constructible from \p key of type \p K.
- The \p value_type should be constructible from \p val of type \p V.
- Returns \p true if \p val is inserted into the set, \p false otherwise.
+ Returns \p true if \p val is inserted into the map, \p false otherwise.
*/
template <typename K, typename V>
bool insert( K const& key, V const& val )
/// Delete \p key from the map
/**
\p key_type must be constructible from value of type \p K.
+ The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
Return \p true if \p key is found and deleted, \p false otherwise.
*/
/// Delete \p key from the map
/**
- The function searches an item with key \p key, calls \p f functor
- and deletes the item. If \p key is not found, the functor is not called.
+ The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
+ calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
The functor \p Func interface:
\code
void operator()(value_type& item) { ... }
};
\endcode
+ where \p item is the element found.
+
\p key_type must be constructible from value of type \p K.
Return \p true if key is found and deleted, \p false otherwise
*/
bool erase_at( iterator const& iter )
{
- //TODO
+ return base_class::erase_at( iter );
+ }
+
+ /// Extracts the item from the map with specified \p key
+ /**
+ The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
+ unlinks it from the map, and returns a guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
+
+ The item extracted is freed automatically by garbage collector \p GC
+ when returned \p guarded_ptr object will be destroyed or released.
+ @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
+ map_type theMap;
+ // ...
+ {
+ map_type::guarded_ptr gp( theMap.extract( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ // ...
+ }
+ // Destructor of gp releases internal HP guard and frees the pointer
+ }
+ \endcode
+ */
+ template <typename K>
+ guarded_ptr extract( K const& key )
+ {
+ guarded_ptr gp;
+ typename gc::Guard guard;
+ node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} );
+
+ // p is guarded by HP
+ if ( p )
+ gp.reset( p );
+ return gp;
+ }
+
+ /// Extracts the item pointed by the iterator \p iter
+ /**
+ The item extracted is freed automatically by garbage collector \p GC
+ when returned \p guarded_ptr object will be destroyed or released.
+
+ @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+
+ Due to concurrent nature of the map the returned guarded pointer may be empty.
+ Check it before dereferencing.
+ */
+ guarded_ptr extract_at( iterator const& iter )
+ {
+ guarded_ptr gp;
+ if ( base_class::erase_at( iter )) {
+ // The element erased is guarded by iter so it is still alive
+ gp.reset( iter.node_pointer());
+ }
+ return gp;
+ }
+
+ /// Checks whether the map contains \p key
+ /**
+ The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
+ and returns \p true if it is found, or \p false otherwise.
+ */
+ template <typename K>
+ bool contains( K const& key )
+ {
+ return base_class::contains( m_Hasher( key_type( key )) );
+ }
+
+ /// Find the key \p key
+ /**
+
+ The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
+ and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+
+ The functor may change \p item.second.
+
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ template <typename K, typename Func>
+ bool find( K const& key, Func f )
+ {
+ return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
+ }
+
+ /// Finds the key \p key and return the item found
+ /**
+ The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
+ and returns a guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
+
+ It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
+ In this case the item will be freed later by garbage collector \p GC automatically
+ when \p guarded_ptr object will be destroyed or released.
+ @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
+ map_type theMap;
+ // ...
+ {
+ map_type::guarded_ptr gp( theMap.get( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ //...
+ }
+ // Destructor of guarded_ptr releases internal HP guard
+ }
+ \endcode
+ */
+ template <typename K>
+ guarded_ptr get( K const& key )
+ {
+ guarded_ptr gp;
+ {
+ typename gc::Guard guard;
+ gp.reset( base_class::search( m_Hasher( key_type( key )), guard ));
+ }
+ return gp;
}
+ /// Clears the map (non-atomic)
+ /**
+ The function unlink all data node from the map.
+ The function is not atomic but is thread-safe.
+ After \p %clear() the map may not be empty because another threads may insert items.
+ */
+ void clear()
+ {
+ base_class::clear();
+ }
+
+ /// 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 feature is an important part of the map implementation.
+ */
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Returns item count in the map
+ size_t size() const
+ {
+ return base_class::size();
+ }
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+
+ /// Returns the size of head node
+ size_t head_size() const
+ {
+ return base_class::head_size();
+ }
+
+ /// Returns the size of the array node
+ size_t array_node_size() const
+ {
+ return base_class::array_node_size();
+ }
+
+ public:
+ ///@name Thread-safe iterators
+ /** @anchor cds_container_MultilevelHashMap_iterators
+ The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.\r
+ It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:\r
+ Hazard Pointer embedded into the iterator object protects the node from physical reclamation.\r
+\r
+ @note Since the iterator object contains hazard pointer that is a thread-local resource,\r
+ the iterator should not be passed to another thread.\r
+\r
+ Each iterator object supports the common interface:\r
+ - dereference operators:\r
+ @code\r
+ value_type [const] * operator ->() noexcept\r
+ value_type [const] & operator *() noexcept\r
+ @endcode\r
+ - pre-increment and pre-decrement. Post-operators is not supported\r
+ - equality operators <tt>==</tt> and <tt>!=</tt>.\r
+ Iterators are equal iff they point to the same cell of the same array node.
+ Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
+ does not entail <tt> &(*it1) == &(*it2) </tt>
+ - helper member function \p release() that clears internal hazard pointer.\r
+ After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible.
+ */
+ ///@{
+ /// Returns an iterator to the beginning of the map
+ iterator begin()
+ {
+ return iterator( base_class::begin() );
+ }
+
+ /// Returns an const iterator to the beginning of the map
+ const_iterator begin() const
+ {
+ return const_iterator( base_class::begin());
+ }
+
+ /// Returns an const iterator to the beginning of the map
+ const_iterator cbegin()
+ {
+ return const_iterator( base_class::cbegin());
+ }
+
+ /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ iterator end()
+ {
+ return iterator( base_class::end());
+ }
+
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator end() const
+ {
+ return const_iterator( base_class::end());
+ }
+
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator cend()
+ {
+ return const_iterator( base_class::cend());
+ }
+
+ /// Returns a reverse iterator to the first element of the reversed map
+ reverse_iterator rbegin()
+ {
+ return reverse_iterator( base_class::rbegin());
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed map
+ const_reverse_iterator rbegin() const
+ {
+ return const_reverse_iterator( base_class::rbegin());
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed map
+ const_reverse_iterator crbegin()
+ {
+ return const_reverse_iterator( base_class::crbegin());
+ }
+
+ /// Returns a reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ reverse_iterator rend()
+ {
+ return reverse_iterator( base_class::rend());
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator rend() const
+ {
+ return const_reverse_iterator( base_class::rend());
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator crend()
+ {
+ return const_reverse_iterator( base_class::crend());
+ }
+ ///@}
};
}} // namespace cds::container
typename gc::Guard m_guard; ///< HP guard
MultiLevelHashSet const* m_set; ///< Hash set
+ protected:
+ static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
+
public:
typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
}
template <bool IsConst2>
- bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const
+ bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
{
return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
}
template <bool IsConst2>
- bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const
+ bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
{
return !( *this == rhs );
}
//@endcond
public:
- typedef bidirectional_iterator<false> iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
- typedef bidirectional_iterator<true> const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
- typedef reverse_bidirectional_iterator<false> reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
- typedef reverse_bidirectional_iterator<true> const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type
+ typedef implementation_defined const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type
+ typedef implementation_defined reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type
+ typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
+#else
+ typedef bidirectional_iterator<false> iterator;
+ typedef bidirectional_iterator<true> const_iterator;
+ typedef reverse_bidirectional_iterator<false> reverse_iterator;
+ typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
+#endif
private:
//@cond
typename gc::Guard guard;
auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
-
- // p is guarded by HP
- if ( p ) {
- gc::template retire<disposer>( p );
- --m_ItemCounter;
- m_Stat.onEraseSuccess();
- return true;
- }
- return false;
+ return p != nullptr;
}
/// Deletes the item from the set
// p is guarded by HP
if ( p ) {
- gc::template retire<disposer>( p );
- --m_ItemCounter;
f( *p );
- m_Stat.onEraseSuccess();
return true;
}
return false;
guarded_ptr gp;
{
typename gc::Guard guard;
- value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
+ value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
// p is guarded by HP
- if ( p ) {
- gc::template retire<disposer>( p );
- --m_ItemCounter;
- m_Stat.onEraseSuccess();
+ if ( p )
gp.reset( p );
- }
}
return gp;
}
else if ( slot.ptr() ) {
if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 && pred( *slot.ptr() )) {
// item found - replace it with nullptr
- if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed))
+ if ( pArr->nodes[nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) {
+ // slot is guarded by HP
+ gc::template retire<disposer>( slot.ptr() );
+ --m_ItemCounter;
+ m_Stat.onEraseSuccess();
+
return slot.ptr();
+ }
m_Stat.onEraseRetry();
continue;
}
projects / libcds.git / commitdiff