From ce86068374907076f98cdd0367806e4a5585b02a Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 17 Aug 2015 09:09:31 +0300 Subject: [PATCH] [draft] container::MultiLevelHashMap --- cds/container/details/make_skip_list_map.h | 4 +- .../details/multilevel_hashmap_base.h | 214 +++++++++++ .../details/multilevel_hashset_base.h | 2 +- cds/container/impl/multilevel_hashmap.h | 343 ++++++++++++++++++ cds/container/impl/skip_list_map.h | 4 +- cds/container/multilevel_hashmap_dhp.h | 9 + cds/container/multilevel_hashmap_hp.h | 9 + cds/intrusive/impl/multilevel_hashset.h | 188 +++++----- projects/Win/vc12/cds.vcxproj | 4 + projects/Win/vc12/cds.vcxproj.filters | 12 + 10 files changed, 695 insertions(+), 94 deletions(-) create mode 100644 cds/container/details/multilevel_hashmap_base.h create mode 100644 cds/container/impl/multilevel_hashmap.h create mode 100644 cds/container/multilevel_hashmap_dhp.h create mode 100644 cds/container/multilevel_hashmap_hp.h diff --git a/cds/container/details/make_skip_list_map.h b/cds/container/details/make_skip_list_map.h index 60e99e64..94d8b06c 100644 --- a/cds/container/details/make_skip_list_map.h +++ b/cds/container/details/make_skip_list_map.h @@ -49,9 +49,9 @@ namespace cds { namespace container { namespace details { init_tower( nHeight, pTower ); } - private: - node_type() ; // no default ctor + node_type() = delete; + private: void init_tower( unsigned int nHeight, atomic_marked_ptr * pTower ) { if ( nHeight > 1 ) { diff --git a/cds/container/details/multilevel_hashmap_base.h b/cds/container/details/multilevel_hashmap_base.h new file mode 100644 index 00000000..7f7753cb --- /dev/null +++ b/cds/container/details/multilevel_hashmap_base.h @@ -0,0 +1,214 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H +#define CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H + +#include +#include +#include + +namespace cds { namespace container { + /// \p MultiLevelHashMap related definitions + /** @ingroup cds_nonintrusive_helper + */ + namespace multilevel_hashmap { + + /// \p MultiLevelHashMap internal statistics, see cds::intrusive::multilevel_hashset::stat + template + using stat = cds::intrusive::multilevel_hashset::stat< EventCounter >; + + /// \p MultiLevelHashMap empty internal statistics + typedef cds::intrusive::multilevel_hashset::empty_stat empty_stat; + + /// Bit-wise memcmp-based comparator for hash value \p T + template + using bitwise_compare = cds::intrusive::multilevel_hashset::bitwise_compare< T >; + + /// \p MultiLevelHashMap traits + struct traits + { + /// Hash functor, default is \p std::hash + /** + \p MultiLevelHashMap may use any hash functor converting key to + fixed-sized bit-string, for example, SHA1, SHA2, + MurmurHash, + CityHash + or its successor FarmHash. + */ + typedef opt::none hash; + + /// Hash comparing functor + /** + @copydetails cds::intrusive::multilevel_hashset::traits::compare + */ + typedef cds::opt::none compare; + + /// Specifies binary predicate used for hash compare. + /** + @copydetails cds::intrusive::multilevel_hashset::traits::less + */ + typedef cds::opt::none less; + + /// Item counter + /** + @copydetails cds::intrusive::multilevel_hashset::traits::item_counter + */ + typedef cds::atomicity::item_counter item_counter; + + /// Item allocator + /** + Default is \ref CDS_DEFAULT_ALLOCATOR + */ + typedef CDS_DEFAULT_ALLOCATOR allocator; + + /// Array node allocator + /** + @copydetails cds::intrusive::multilevel_hashset::traits::node_allocator + */ + typedef CDS_DEFAULT_ALLOCATOR node_allocator; + + /// C++ memory ordering model + /** + @copydetails cds::intrusive::multilevel_hashset::traits::memory_model + */ + typedef cds::opt::v::relaxed_ordering memory_model; + + /// Back-off strategy + typedef cds::backoff::Default back_off; + + /// Internal statistics + /** + @copydetails cds::intrusive::multilevel_hashset::traits::stat + */ + typedef empty_stat stat; + + /// RCU deadlock checking policy (only for \ref cds_container_MultilevelHashSet_rcu "RCU-based MultilevelHashSet") + /** + @copydetails cds::intrusive::multilevel_hashset::traits::rcu_check_deadlock + */ + typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock; + }; + + /// Metafunction converting option list to \p multilevel_hashmap::traits + /** + Supported \p Options are: + - \p opt::hash - a hash functor, default is \p std::hash + @copydetails traits::hash + - \p opt::allocator - item allocator + @copydetails traits::allocator + - \p opt::node_allocator - array node allocator. + @copydetails traits::node_allocator + - \p opt::compare - hash comparison functor. No default functor is provided. + If the option is not specified, the \p opt::less is used. + - \p opt::less - specifies binary predicate used for hash comparison. + @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 + - \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). + To enable it use \p multilevel_hashmap::stat + - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet" + Default is \p opt::v::rcu_throw_deadlock + */ + template + struct make_traits + { +# ifdef CDS_DOXYGEN_INVOKED + typedef implementation_defined type ; ///< Metafunction result +# else + typedef typename cds::opt::make_options< + typename cds::opt::find_type_traits< traits, Options... >::type + ,Options... + >::type type; +# endif + }; + } // namespace multilevel_hashmap + + //@cond + // Forward declaration + template < class GC, typename Key, typename T, class Traits = multilevel_hashmap::traits > + class MultiLevelHashMap; + //@endcond + + //@cond + namespace details { + + template + struct make_multilevel_hashmap + { + typedef GC gc; + typedef Key key_type; + typedef T mapped_type; + typedef Traits original_traits; + typedef typename cds::opt::v::hash_selector< typename original_traits::hash >::type hasher; + + typedef typename std::decay< + typename std::remove_reference< + decltype( hasher()( std::declval()) ) + >::type + >::type hash_type; + //typedef typename std::result_of< hasher( std::declval()) >::type hash_type; + static_assert( !std::is_pointer::value, "hash functor should return a reference to hash value" ); + + struct node_type + { + std::pair< key_type const, mapped_type> m_Value; + hash_type const m_hash; + + node_type() = delete; + node_type( node_type const& ) = delete; + + template + node_type( hasher& h, Q const& key ) + : m_Value( std::make_pair( key, mapped_type())) + , m_hash( h( m_Value.first )) + {} + + template + node_type( hasher& h, Q const& key, U const& val ) + : m_Value( std::make_pair( key, val )) + , m_hash( h( m_Value.first )) + {} + + template + node_type( hasher& h, Q&& key, Args&&... args ) + : m_Value( std::forward(key), std::move( mapped_type( std::forward(args)... ))) + , m_hash( h( m_Value.first )) + {} + }; + + typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator; + + struct node_disposer + { + void operator()( node_type * p ) const + { + cxx_node_allocator().Delete( p ); + } + }; + + struct get_node_hash + { + hash_type const& operator()( node_type const& n ) + { + return n.m_hash; + } + }; + + struct intrusive_traits: public original_traits + { + typedef get_node_hash hash_accesor; + typedef node_disposer disposer; + }; + + // Metafunction result + typedef cds::intrusive::MultiLevelHashSet< GC, node_type, intrusive_traits > type; + }; + } // namespace details + //@endcond + +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H diff --git a/cds/container/details/multilevel_hashset_base.h b/cds/container/details/multilevel_hashset_base.h index be1b994e..2ecc8ac1 100644 --- a/cds/container/details/multilevel_hashset_base.h +++ b/cds/container/details/multilevel_hashset_base.h @@ -7,7 +7,7 @@ #include namespace cds { namespace container { - /// MultiLevelHashSet related definitions + /// \p MultiLevelHashSet related definitions /** @ingroup cds_nonintrusive_helper */ namespace multilevel_hashset { diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h new file mode 100644 index 00000000..dffa4537 --- /dev/null +++ b/cds/container/impl/multilevel_hashmap.h @@ -0,0 +1,343 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H +#define CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H + +#include +#include + +namespace cds { namespace container { + + /// Hash map based on multi-level array + /** @ingroup cds_nonintrusive_map + @anchor cds_container_MultilevelHashMap_hp + + Source: + - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: + Wait-free Extensible Hash Maps" + + [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform + a global resize, the process of redistributing the elements in a hash map that occurs when adding new + buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all + threads will be forced to wait on the thread that is performing the involved process of resizing the hash map + and redistributing the elements. \p %MultilevelHashSet implementation avoids global resizes through new array + allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize, + which facilitates concurrent operations. + + The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure; + which, in combination with perfect hashing, means that each element has a unique final, as well as current, position. + It is important to note that the perfect hash function required by our hash map is trivial to realize as + any hash function that permutes the bits of the key is suitable. This is possible because of our approach + to the hash function; we require that it produces hash values that are equal in size to that of the key. + We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys + are not provided for in the standard semantics of a hash map. + + \p %MultiLevelHashMap is a multi-level array which has an internal structure similar to a tree: + @image html multilevel_hashset.png + The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node. + A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated + with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked. + A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB) + of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node; + any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds + an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark + on the second-least significant bit. + + \p %MultiLevelHashMap multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array + called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length; + a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength. + The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node. + 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 + string and rehash incrementally. + + @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap: + - all keys is converted to fixed-size bit-string by hash functor provided. + You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap, + but real key in the map will be fixed-ize hash values of your keys. + For the strings you may use well-known hashing algorithms like SHA1, SHA2, + MurmurHash, CityHash + 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, + it maintains its fixed-size hash value. + + The set 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" + - \p Key - a key type to be stored in the map + - \p T - a value type to be stored in the map + - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction. + + There are several specializations of \p %MultiLevelHashMap for each \p GC. You should include: + - for \p gc::HP garbage collector + - for \p gc::DHP garbage collector + - for \ref cds_intrusive_MultiLevelHashSet_rcu "RCU type". RCU specialization + has a slightly different interface. + */ + template < + class GC + ,typename Key + ,typename T +#ifdef CDS_DOXYGEN_INVOKED + ,class Traits = multilevel_hashmap::traits +#else + ,class Traits +#endif + > + class MultiLevelHashMap +#ifdef CDS_DOXYGEN_INVOKED + : protected cds::intrusive::MultiLevelHashSet< GC, std::pair, Traits > +#else + : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Hasher, Traits >::type +#endif + { + //@cond + typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, Hasher, Traits > maker; + typedef typename maker::type base_class; + //@endcond + public: + typedef GC gc; ///< Garbage collector + typedef Key key_type; ///< Key type + typedef T mapped_type; ///< Mapped type + typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map + typedef Traits traits; ///< Map traits +#ifdef CDS_DOXYGEN_INVOKED + typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash +#else + typedef typename maker::hasher hasher; +#endif + + typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type + typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less + + typedef typename traits::item_counter item_counter; ///< Item counter type + typedef typename traits::allocator allocator; ///< Element allocator + typedef typename traits::node_allocator node_allocator; ///< Array node allocator + typedef typename traits::memory_model memory_model; ///< Memory model + 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; + + protected: + //@cond + 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; + //@endcond + + protected: + //@cond + hasher m_Hasher; + //@endcond + + public: + /// Creates empty map + /** + @param head_bits: 2head_bits specifies the size of head array, minimum is 4. + @param array_bits: 2array_bits specifies the size of array node, minimum is 2. + + Equation for \p head_bits and \p array_bits: + \code + sizeof(hash_type) * 8 == head_bits + N * array_bits + \endcode + where \p N is multi-level array depth. + */ + MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 ) + : base_class( head_bits, array_bits ) + {} + + /// Destructs the map and frees all data + ~MultiLevelHashMap() + {} + + /// Inserts new element with key and default value + /** + The function creates an element with \p key and default value, and then inserts the node created into the map. + + Preconditions: + - The \p key_type should be constructible from a value of type \p K. + In trivial case, \p K is equal to \p key_type. + - The \p mapped_type should be default-constructible. + + Returns \p true if inserting successful, \p false otherwise. + */ + template + bool insert( K const& key ) + { + scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key )); + if ( base_class::insert( *sp )) { + sp.release(); + return true; + } + return false; + } + + /// Inserts new element + /** + The function creates a node with copy of \p val value + and then inserts the node created into the map. + + Preconditions: + - 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. + */ + template + bool insert( K const& key, V const& val ) + { + scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key, val )); + if ( base_class::insert( *sp )) { + sp.release(); + return true; + } + return false; + } + + /// Inserts new element and initialize it by a functor + /** + This function inserts new element with key \p key and if inserting is successful then it calls + \p func functor with signature + \code + struct functor { + void operator()( value_type& item ); + }; + \endcode + + The argument \p item of user-defined functor \p func is the reference + to the map's item inserted: + - item.first is a const reference to item's key that cannot be changed. + - item.second is a reference to item's value that may be changed. + + \p key_type should be constructible from value of type \p K. + + The function allows to split creating of new item into two part: + - create item from \p key; + - insert new item into the map; + - if inserting is successful, initialize the value of item by calling \p func functor + + This can be useful if complete initialization of object of \p value_type is heavyweight and + it is preferable that the initialization should be completed only if inserting is successful. + */ + template + bool insert_with( K const& key, Func func ) + { + scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key )); + if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) { + sp.release(); + return true; + } + return false; + } + + /// For key \p key inserts data of type \p value_type created in-place from std::forward(args)... + /** + Returns \p true if inserting successful, \p false otherwise. + */ + template + bool emplace( K&& key, Args&&... args ) + { + scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, std::forward(key), std::forward(args)... )); + if ( base_class::insert( *sp )) { + sp.release(); + return true; + } + return false; + } + + /// Updates data by \p key + /** + The operation performs inserting or changing data with lock-free manner. + + If the \p key not found in the map, then the new item created from \p key + will be inserted into the map iff \p bInsert is \p true + (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: + \code + struct my_functor { + void operator()( bool bNew, value_type& item ); + }; + \endcode + where: + - \p bNew - \p true if the item has been inserted, \p false otherwise + - \p item - item of the map + + The functor may change any fields of the \p item.second that is \ref value_type. + + Returns std::pair where \p first is \p true if operation is successfull, + \p second is \p true if new item has been added or \p false if \p key already exists. + + @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" + */ + template + std::pair update( K const& key, Func func, bool bInsert = true ) + { + scoped_node_ptr sp( cxx_node_allocator().New( m_Hasher, key )); + std::pair result = base_class::do_update( *sp, [&func]( bool bNew, node_type& node ) { func( bNew, node.m_Value );}, bInsert ); + if ( !result.first ) + sp.release(); + return result; + } + + /// Delete \p key from the map + /** + \p key_type must be constructible from value of type \p K. + + Return \p true if \p key is found and deleted, \p false otherwise. + */ + template + bool erase( K const& key ) + { + hash_type h = m_Hasher( key_type( key )); + return base_class::erase( h ); + } + + /// 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 functor \p Func interface: + \code + struct extractor { + void operator()(value_type& item) { ... } + }; + \endcode + \p key_type must be constructible from value of type \p K. + + Return \p true if key is found and deleted, \p false otherwise + */ + template + bool erase( K const& key, Func f ) + { + hash_type h = m_Hasher( key_type( key )); + return base_class::erase( h, [&f]( node_type& node) { f( node.m_Value ); } ); + } + + /// Deletes the element pointed by iterator \p iter + /** + Returns \p true if the operation is successful, \p false otherwise. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + */ + bool erase_at( iterator const& iter ) + { + //TODO + } + + + }; + +}} // namespace cds::container + +#endif // #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H diff --git a/cds/container/impl/skip_list_map.h b/cds/container/impl/skip_list_map.h index 80e1ccc5..1f47541c 100644 --- a/cds/container/impl/skip_list_map.h +++ b/cds/container/impl/skip_list_map.h @@ -121,7 +121,7 @@ namespace cds { namespace container { typedef T mapped_type; ///< Mapped type typedef Traits traits; ///< Map traits # ifdef CDS_DOXYGEN_INVOKED - typedef std::pair< K const, T> value_type; ///< Key-value pair to be stored in the map + typedef std::pair< Key const, T> value_type; ///< Key-value pair to be stored in the map # else typedef typename maker::value_type value_type; # endif @@ -270,7 +270,7 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. */ template - bool insert_with( const K& key, Func func ) + bool insert_with( K const& key, Func func ) { scoped_node_ptr pNode( node_allocator().New( random_level(), key )); if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) { diff --git a/cds/container/multilevel_hashmap_dhp.h b/cds/container/multilevel_hashmap_dhp.h new file mode 100644 index 00000000..1f898b59 --- /dev/null +++ b/cds/container/multilevel_hashmap_dhp.h @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H +#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H + +#include +#include + +#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H diff --git a/cds/container/multilevel_hashmap_hp.h b/cds/container/multilevel_hashmap_hp.h new file mode 100644 index 00000000..f38c6267 --- /dev/null +++ b/cds/container/multilevel_hashmap_hp.h @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H +#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H + +#include +#include + +#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h index a6e13f5e..b3c211b0 100644 --- a/cds/intrusive/impl/multilevel_hashset.h +++ b/cds/intrusive/impl/multilevel_hashset.h @@ -615,87 +615,7 @@ namespace cds { namespace intrusive { */ std::pair update( value_type& val, bool bInsert = true ) { - hash_type const& hash = hash_accessor()( val ); - hash_splitter splitter( hash ); - hash_comparator cmp; - typename gc::Guard guard; - back_off bkoff; - - array_node * pArr = m_Head; - size_t nSlot = splitter.cut( m_Metrics.head_node_size_log ); - assert( nSlot < m_Metrics.head_node_size ); - size_t nOffset = m_Metrics.head_node_size_log; - - while ( true ) { - node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire ); - if ( slot.bits() == flag_array_node ) { - // array node, go down the tree - assert( slot.ptr() != nullptr ); - nSlot = splitter.cut( m_Metrics.array_node_size_log ); - assert( nSlot < m_Metrics.array_node_size ); - pArr = to_array( slot.ptr() ); - nOffset += m_Metrics.array_node_size_log; - } - else if ( slot.bits() == flag_array_converting ) { - // the slot is converting to array node right now - bkoff(); - m_Stat.onSlotConverting(); - } - else { - // data node - assert(slot.bits() == 0 ); - - // protect data node by hazard pointer - if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) { - // slot value has been changed - retry - m_Stat.onSlotChanged(); - } - else if ( slot.ptr() ) { - if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) { - // the item with that hash value already exists - // Replace it with val - if ( slot.ptr() == &val ) { - m_Stat.onUpdateExisting(); - return std::make_pair( true, false ); - } - - if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) { - // slot can be disposed - gc::template retire( slot.ptr() ); - m_Stat.onUpdateExisting(); - return std::make_pair( true, false ); - } - - m_Stat.onUpdateRetry(); - continue; - } - - // the slot must be expanded - expand_slot( pArr, nSlot, slot, nOffset ); - } - else { - // the slot is empty, try to insert data node - if ( bInsert ) { - node_ptr pNull; - if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) - { - // the new data node has been inserted - ++m_ItemCounter; - m_Stat.onUpdateNew(); - return std::make_pair( true, true ); - } - } - else { - m_Stat.onUpdateFailed(); - return std::make_pair( false, false ); - } - - // insert failed - slot has been changed by another thread - // retry updating - m_Stat.onUpdateRetry(); - } - } - } // while + return do_update(val, [](bool, value_type&) {}, bInsert ); } /// Unlinks the item \p val from the set @@ -767,25 +687,25 @@ namespace cds { namespace intrusive { return false; } - /// Deletes the item pointed by iterator \p it + /// Deletes the item pointed by iterator \p iter /** Returns \p true if the operation is successful, \p false otherwise. The function does not invalidate the iterator, it remains valid and can be used for further traversing. */ - bool erase_at( iterator const& it ) + bool erase_at( iterator const& iter ) { - if ( it.m_set != this ) + if ( iter.m_set != this ) return false; - if ( it.m_pNode == m_Head && it.m_idx >= head_size()) + if ( iter.m_pNode == m_Head && iter.m_idx >= head_size()) return false; - if ( it.m_idx >= array_node_size() ) + if ( iter.m_idx >= array_node_size() ) return false; for (;;) { - node_ptr slot = it.m_pNode->nodes[it.m_idx].load( memory_model::memory_order_acquire ); - if ( slot.bits() == 0 && slot.ptr() == it.pointer() ) { - if ( it.m_pNode->nodes[it.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) { + node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire ); + if ( slot.bits() == 0 && slot.ptr() == iter.pointer() ) { + if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed) ) { // the item is guarded by iterator, so we may retire it safely gc::template retire( slot.ptr() ); --m_ItemCounter; @@ -1235,7 +1155,10 @@ namespace cds { namespace intrusive { m_Stat.onArrayNodeCreated(); return true; } + //@endcond + protected: + //@cond value_type * search( hash_type const& hash, typename gc::Guard& guard ) { hash_splitter splitter( hash ); @@ -1334,6 +1257,93 @@ namespace cds { namespace intrusive { } // while } + template + std::pair do_update( value_type& val, Func f, bool bInsert = true ) + { + hash_type const& hash = hash_accessor()( val ); + hash_splitter splitter( hash ); + hash_comparator cmp; + typename gc::Guard guard; + back_off bkoff; + + array_node * pArr = m_Head; + size_t nSlot = splitter.cut( m_Metrics.head_node_size_log ); + assert( nSlot < m_Metrics.head_node_size ); + size_t nOffset = m_Metrics.head_node_size_log; + + while ( true ) { + node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire ); + if ( slot.bits() == flag_array_node ) { + // array node, go down the tree + assert( slot.ptr() != nullptr ); + nSlot = splitter.cut( m_Metrics.array_node_size_log ); + assert( nSlot < m_Metrics.array_node_size ); + pArr = to_array( slot.ptr() ); + nOffset += m_Metrics.array_node_size_log; + } + else if ( slot.bits() == flag_array_converting ) { + // the slot is converting to array node right now + bkoff(); + m_Stat.onSlotConverting(); + } + else { + // data node + assert(slot.bits() == 0 ); + + // protect data node by hazard pointer + if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) { + // slot value has been changed - retry + m_Stat.onSlotChanged(); + } + else if ( slot.ptr() ) { + if ( cmp( hash, hash_accessor()( *slot.ptr() )) == 0 ) { + // the item with that hash value already exists + // Replace it with val + if ( slot.ptr() == &val ) { + m_Stat.onUpdateExisting(); + return std::make_pair( true, false ); + } + + if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) { + // slot can be disposed + f( false, val ); + gc::template retire( slot.ptr() ); + m_Stat.onUpdateExisting(); + return std::make_pair( true, false ); + } + + m_Stat.onUpdateRetry(); + continue; + } + + // the slot must be expanded + expand_slot( pArr, nSlot, slot, nOffset ); + } + else { + // the slot is empty, try to insert data node + if ( bInsert ) { + node_ptr pNull; + if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) + { + // the new data node has been inserted + f( true, val ); + ++m_ItemCounter; + m_Stat.onUpdateNew(); + return std::make_pair( true, true ); + } + } + else { + m_Stat.onUpdateFailed(); + return std::make_pair( false, false ); + } + + // insert failed - slot has been changed by another thread + // retry updating + m_Stat.onUpdateRetry(); + } + } + } // while + } //@endcond }; }} // namespace cds::intrusive diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index b720b44e..ee2a355b 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -670,6 +670,7 @@ + @@ -686,6 +687,7 @@ + @@ -700,6 +702,8 @@ + + diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index a5803140..e5928da4 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -1211,5 +1211,17 @@ Header Files\cds\container + + Header Files\cds\container\details + + + Header Files\cds\container\impl + + + Header Files\cds\container + + + Header Files\cds\container + \ No newline at end of file -- 2.34.1