X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Ffeldman_hashmap.h;h=7ac74a0365c41b2d6ba2c4a36b89d4e34d9b7dfb;hb=bc8665dd5651cf4e78f2849fce1ec6ef44782ccf;hp=8c95e48ec692176d1292443020fce2055b8443fc;hpb=0be641638ba7a041e2f6c5d1470b1d5d4ae317f7;p=libcds.git diff --git a/cds/container/impl/feldman_hashmap.h b/cds/container/impl/feldman_hashmap.h index 8c95e48e..7ac74a03 100644 --- a/cds/container/impl/feldman_hashmap.h +++ b/cds/container/impl/feldman_hashmap.h @@ -1,11 +1,11 @@ /* 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: @@ -25,7 +25,7 @@ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H @@ -155,6 +155,12 @@ namespace cds { namespace container { /// Count of hazard pointers required static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; + /// The size of \p hash_type in bytes, see \p feldman_hashmap::traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size; + + /// Level statistics + typedef feldman_hashmap::level_statistics level_statistics; + protected: //@cond typedef typename maker::node_type node_type; @@ -182,7 +188,7 @@ namespace cds { namespace container { : iterator_base( rhs ) {} - bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT + bidirectional_iterator& operator=( bidirectional_iterator const& rhs ) CDS_NOEXCEPT { iterator_base::operator=( rhs ); return *this; @@ -219,13 +225,13 @@ namespace cds { namespace container { } template - bool operator ==(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + bool operator ==( bidirectional_iterator const& rhs ) const CDS_NOEXCEPT { return iterator_base::operator==( rhs ); } template - bool operator !=(bidirectional_iterator const& rhs) const CDS_NOEXCEPT + bool operator !=( bidirectional_iterator const& rhs ) const CDS_NOEXCEPT { return !( *this == rhs ); } @@ -297,13 +303,13 @@ namespace cds { namespace container { } template - bool operator ==(reverse_bidirectional_iterator const& rhs) const + bool operator ==( reverse_bidirectional_iterator const& rhs ) const { return iterator_base::operator==( rhs ); } template - bool operator !=(reverse_bidirectional_iterator const& rhs) + bool operator !=( reverse_bidirectional_iterator const& rhs ) { return !( *this == rhs ); } @@ -350,12 +356,12 @@ namespace cds { namespace container { 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. + @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 + c_hash_size * 8 == head_bits + N * array_bits \endcode where \p N is multi-level array depth. */ @@ -381,7 +387,7 @@ namespace cds { namespace container { template bool insert( K&& key ) { - scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key) )); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward( key ))); if ( base_class::insert( *sp )) { sp.release(); return true; @@ -403,7 +409,7 @@ namespace cds { namespace container { template bool insert( K&& key, V&& val ) { - scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key), std::forward(val))); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward( key ), std::forward( val ))); if ( base_class::insert( *sp )) { sp.release(); return true; @@ -439,7 +445,7 @@ namespace cds { namespace container { template bool insert_with( K&& key, Func func ) { - scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key))); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward( key ))); if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) { sp.release(); return true; @@ -454,7 +460,7 @@ namespace cds { namespace container { template bool emplace( K&& key, Args&&... args ) { - scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key), std::forward(args)... )); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward( key ), std::forward( args )... )); if ( base_class::insert( *sp )) { sp.release(); return true; @@ -483,7 +489,7 @@ namespace cds { namespace container { The functor may change any fields of the \p item.second. - Returns std::pair where \p first is \p true if operation is successfull, + Returns std::pair where \p first is \p true if operation is successful, \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" @@ -491,7 +497,7 @@ namespace cds { namespace container { template std::pair update( K&& key, Func func, bool bInsert = true ) { - scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward(key))); + scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward( key ))); std::pair result = base_class::do_update( *sp, [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );}, bInsert ); @@ -521,7 +527,7 @@ namespace cds { namespace container { The functor \p Func interface: \code struct extractor { - void operator()(value_type& item) { ... } + void operator()( value_type& item ) { ... } }; \endcode where \p item is the element found. @@ -533,7 +539,7 @@ namespace cds { namespace container { template bool erase( K const& key, Func f ) { - return base_class::erase( m_Hasher(key_type(key)), [&f]( node_type& node) { f( node.m_Value ); } ); + return base_class::erase( m_Hasher( key_type( key )), [&f]( node_type& node) { f( node.m_Value ); } ); } /// Deletes the element pointed by iterator \p iter @@ -551,6 +557,14 @@ namespace cds { namespace container { { return base_class::do_erase_at( iter ); } + bool erase_at( const_iterator const& iter ) + { + return base_class::do_erase_at( iter ); + } + bool erase_at( const_reverse_iterator const& iter ) + { + return base_class::do_erase_at( iter ); + } //@endcond /// Extracts the item from the map with specified \p key @@ -581,14 +595,7 @@ namespace cds { namespace container { 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; + return base_class::extract( m_Hasher( key_type( key ))); } /// Checks whether the map contains \p key @@ -599,7 +606,7 @@ namespace cds { namespace container { template bool contains( K const& key ) { - return base_class::contains( m_Hasher( key_type( key )) ); + return base_class::contains( m_Hasher( key_type( key ))); } /// Find the key \p key @@ -622,7 +629,7 @@ namespace cds { namespace container { 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 );}); + 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 @@ -654,12 +661,7 @@ namespace cds { namespace container { 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; + return base_class::get( m_Hasher( key_type( key ))); } /// Clears the map (non-atomic) @@ -716,7 +718,7 @@ namespace cds { namespace container { Result can be useful for estimating efficiency of hash functor you use. */ - void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const + void get_level_statistics( std::vector< feldman_hashmap::level_statistics>& stat) const { base_class::get_level_statistics( stat ); }