From f49c4546f69116dc589a2c76caeefbeee5fd648c Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 18 Aug 2015 23:11:25 +0300 Subject: [PATCH] [draft] MultiLevelHashMap implementation --- .../details/multilevel_hashmap_base.h | 2 +- cds/container/impl/multilevel_hashmap.h | 404 +++++++++++++++++- cds/container/impl/multilevel_hashset.h | 2 +- cds/container/impl/skip_list_map.h | 2 +- cds/intrusive/impl/multilevel_hashset.h | 51 +-- 5 files changed, 424 insertions(+), 37 deletions(-) diff --git a/cds/container/details/multilevel_hashmap_base.h b/cds/container/details/multilevel_hashmap_base.h index 7f7753cb..ee24dfdb 100644 --- a/cds/container/details/multilevel_hashmap_base.h +++ b/cds/container/details/multilevel_hashmap_base.h @@ -104,7 +104,7 @@ namespace cds { namespace container { @copydetails cds::container::multilevel_hashmap::traits::less - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used. - \p opt::item_counter - the type of item counting feature. - @copydetails cds::intrusive::multilevel_hashmap::traits::item_counter + @copydetails cds::container::multilevel_hashmap::traits::item_counter - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) or \p opt::v::sequential_consistent (sequentially consisnent memory model). - \p opt::stat - internal statistics. By default, it is disabled (\p multilevel_hashmap::empty_stat). diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h index dffa4537..7875dea5 100644 --- a/cds/container/impl/multilevel_hashmap.h +++ b/cds/container/impl/multilevel_hashmap.h @@ -5,6 +5,7 @@ #include #include +#include namespace cds { namespace container { @@ -50,7 +51,7 @@ 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 we need to operate; this is initially one, because of \p head. - That approach to the structure of the hash set uses an extensible hashing scheme; the hash value is treated as a bit + That approach to the structure of the hash map uses an extensible hashing scheme; the hash value is treated as a bit string and rehash incrementally. @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap: @@ -62,10 +63,10 @@ namespace cds { namespace container { or its successor FarmHash and so on, which converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap. - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string, - have identical hash then you cannot insert both that keys in the set. \p %MultiLevelHashMap does not maintain the key, + have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key, it maintains its fixed-size hash value. - The set supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators". + The map supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators". Template parameters: - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type" @@ -122,8 +123,6 @@ namespace cds { namespace container { 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; @@ -132,8 +131,110 @@ namespace cds { namespace container { 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 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 + bool operator ==(It const& rhs) const CDS_NOEXCEPT + { + return base_class::operator==( rhs ); + } + + template + 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 > 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 iterator; + typedef bidirectional_iterator const_iterator; + typedef bidirectional_iterator reverse_iterator; + typedef bidirectional_iterator const_reverse_iterator; +#endif + protected: //@cond hasher m_Hasher; @@ -190,7 +291,7 @@ namespace cds { namespace container { - 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 bool insert( K const& key, V const& val ) @@ -292,6 +393,7 @@ namespace cds { namespace container { /// 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 hash( key_type( key )) Return \p true if \p key is found and deleted, \p false otherwise. */ @@ -304,8 +406,8 @@ namespace cds { namespace container { /// 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 hash( key_type( key )), + 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 @@ -313,6 +415,8 @@ namespace cds { namespace container { 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 @@ -332,10 +436,292 @@ namespace cds { namespace container { */ 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 hash( key_type( key )) 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 + 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 hash( key_type( key )) + and returns \p true if it is found, or \p false otherwise. + */ + template + 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 hash( key_type( key )) + 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 + 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 hash( key_type( key )) + 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 + 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. + It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to: + Hazard Pointer embedded into the iterator object protects the node from physical reclamation. + + @note Since the iterator object contains hazard pointer that is a thread-local resource, + the iterator should not be passed to another thread. + + Each iterator object supports the common interface: + - dereference operators: + @code + value_type [const] * operator ->() noexcept + value_type [const] & operator *() noexcept + @endcode + - pre-increment and pre-decrement. Post-operators is not supported + - equality operators == and !=. + 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 it1 == it2 + does not entail &(*it1) == &(*it2) + - helper member function \p release() that clears internal hazard pointer. + 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 diff --git a/cds/container/impl/multilevel_hashset.h b/cds/container/impl/multilevel_hashset.h index d0b2a94b..e33a0e05 100644 --- a/cds/container/impl/multilevel_hashset.h +++ b/cds/container/impl/multilevel_hashset.h @@ -451,7 +451,7 @@ namespace cds { namespace container { - equality operators == and !=. 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 it1 == it2 - does not entail &(*it1) == &(*it2) : welcome to concurrent containers + does not entail &(*it1) == &(*it2) - helper member function \p release() that clears internal hazard pointer. After \p release() call the iterator points to \p nullptr but it still remain valid: further iterating is possible. */ diff --git a/cds/container/impl/skip_list_map.h b/cds/container/impl/skip_list_map.h index 1f47541c..3192918b 100644 --- a/cds/container/impl/skip_list_map.h +++ b/cds/container/impl/skip_list_map.h @@ -587,7 +587,7 @@ namespace cds { namespace container { /// Finds the key \p key and return the item found /** \anchor cds_nonintrusive_SkipListMap_hp_get The function searches the item with key equal to \p key - and returns an guarded pointer to the item found. + 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. diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h index b3c211b0..46937daf 100644 --- a/cds/intrusive/impl/multilevel_hashset.h +++ b/cds/intrusive/impl/multilevel_hashset.h @@ -183,6 +183,9 @@ namespace cds { namespace intrusive { 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 @@ -241,13 +244,13 @@ namespace cds { namespace intrusive { } template - bool operator ==(bidirectional_iterator const& rhs) const + bool operator ==(bidirectional_iterator const& rhs) const CDS_NOEXCEPT { return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set; } template - bool operator !=(bidirectional_iterator const& rhs) const + bool operator !=(bidirectional_iterator const& rhs) const CDS_NOEXCEPT { return !( *this == rhs ); } @@ -462,10 +465,17 @@ namespace cds { namespace intrusive { //@endcond public: - typedef bidirectional_iterator iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional iterator" type - typedef bidirectional_iterator const_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional const iterator" type - typedef reverse_bidirectional_iterator reverse_iterator; ///< @ref cds_intrusive_MultilevelHashSet_iterators "bidirectional reverse iterator" type - typedef reverse_bidirectional_iterator 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 iterator; + typedef bidirectional_iterator const_iterator; + typedef reverse_bidirectional_iterator reverse_iterator; + typedef reverse_bidirectional_iterator const_reverse_iterator; +#endif private: //@cond @@ -630,15 +640,7 @@ namespace cds { namespace intrusive { 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( p ); - --m_ItemCounter; - m_Stat.onEraseSuccess(); - return true; - } - return false; + return p != nullptr; } /// Deletes the item from the set @@ -678,10 +680,7 @@ namespace cds { namespace intrusive { // p is guarded by HP if ( p ) { - gc::template retire( p ); - --m_ItemCounter; f( *p ); - m_Stat.onEraseSuccess(); return true; } return false; @@ -748,15 +747,11 @@ namespace cds { namespace intrusive { 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( p ); - --m_ItemCounter; - m_Stat.onEraseSuccess(); + if ( p ) gp.reset( p ); - } } return gp; } @@ -1240,8 +1235,14 @@ namespace cds { namespace intrusive { 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( slot.ptr() ); + --m_ItemCounter; + m_Stat.onEraseSuccess(); + return slot.ptr(); + } m_Stat.onEraseRetry(); continue; } -- 2.34.1