From aaee2482f4783d828177db44f955017a9b493d60 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 2 Apr 2016 22:03:53 +0300 Subject: [PATCH] Minor improvements, docfix, beautifying code --- cds/container/details/feldman_hashmap_base.h | 14 +-- cds/container/impl/feldman_hashmap.h | 41 +++++--- cds/intrusive/impl/feldman_hashset.h | 98 ++++++++++---------- 3 files changed, 77 insertions(+), 76 deletions(-) diff --git a/cds/container/details/feldman_hashmap_base.h b/cds/container/details/feldman_hashmap_base.h index d1963f32..d72bd284 100644 --- a/cds/container/details/feldman_hashmap_base.h +++ b/cds/container/details/feldman_hashmap_base.h @@ -290,19 +290,9 @@ namespace cds { namespace container { node_type() = delete; node_type(node_type const&) = delete; - template - node_type(hasher /*h*/, Q const& key) - : m_Value(std::move(std::make_pair(key, mapped_type()))) - {} - - template - node_type(hasher /*h*/, Q const& key, U const& val) - : m_Value(std::move(std::make_pair(key, mapped_type(val)))) - {} - template - node_type(hasher /*h*/, Q&& key, Args&&... args) - : m_Value(std::move(std::make_pair(std::forward(key), std::move(mapped_type(std::forward(args)...))))) + node_type( hasher /*h*/, Q&& key, Args&&... args ) + : m_Value( std::make_pair( key_type( std::forward( key )), mapped_type( std::forward(args)...) )) {} }; diff --git a/cds/container/impl/feldman_hashmap.h b/cds/container/impl/feldman_hashmap.h index 8c95e48e..2e28e3e2 100644 --- a/cds/container/impl/feldman_hashmap.h +++ b/cds/container/impl/feldman_hashmap.h @@ -155,6 +155,9 @@ namespace cds { namespace container { /// Count of hazard pointers required static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; + /// Level statistics + typedef feldman_hashmap::level_statistics level_statistics; + protected: //@cond typedef typename maker::node_type node_type; @@ -182,7 +185,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 +222,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 +300,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 ); } @@ -355,7 +358,7 @@ namespace cds { namespace container { Equation for \p head_bits and \p array_bits: \code - sizeof(hash_type) * 8 == head_bits + N * array_bits + sizeof( hash_type ) * 8 == head_bits + N * array_bits \endcode where \p N is multi-level array depth. */ @@ -381,7 +384,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 +406,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 +442,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 +457,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; @@ -491,7 +494,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 +524,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 +536,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 +554,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 @@ -622,7 +633,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 @@ -716,7 +727,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 ); } diff --git a/cds/intrusive/impl/feldman_hashset.h b/cds/intrusive/impl/feldman_hashset.h index 76390125..c21646ce 100644 --- a/cds/intrusive/impl/feldman_hashset.h +++ b/cds/intrusive/impl/feldman_hashset.h @@ -189,7 +189,7 @@ namespace cds { namespace intrusive { m_guard.copy( rhs.m_guard ); } - iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT + iterator_base& operator=( iterator_base const& rhs ) CDS_NOEXCEPT { m_pNode = rhs.m_pNode; m_idx = rhs.m_idx; @@ -215,12 +215,12 @@ namespace cds { namespace intrusive { m_guard.clear(); } - bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT + bool operator ==( iterator_base const& rhs ) const CDS_NOEXCEPT { return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set; } - bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT + bool operator !=( iterator_base const& rhs ) const CDS_NOEXCEPT { return !( *this == rhs ); } @@ -273,7 +273,7 @@ namespace cds { namespace intrusive { else { if ( slot.ptr()) { // data node - if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) { + if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) { m_pNode = pNode; m_idx = idx; return; @@ -331,7 +331,7 @@ namespace cds { namespace intrusive { else { if ( slot.ptr()) { // data node - if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) { + if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) { m_pNode = pNode; m_idx = idx; return; @@ -405,7 +405,7 @@ namespace cds { namespace intrusive { : 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; @@ -441,13 +441,13 @@ namespace cds { namespace intrusive { } 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 ); } @@ -517,13 +517,13 @@ namespace cds { namespace intrusive { } 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 ); } @@ -567,7 +567,7 @@ namespace cds { namespace intrusive { Equation for \p head_bits and \p array_bits: \code - sizeof(hash_type) * 8 == head_bits + N * array_bits + sizeof( hash_type ) * 8 == head_bits + N * array_bits \endcode where \p N is multi-level array depth. */ @@ -590,7 +590,7 @@ namespace cds { namespace intrusive { */ bool insert( value_type& val ) { - return insert( val, [](value_type&) {} ); + return insert( val, []( value_type& ) {} ); } /// Inserts new node @@ -615,7 +615,7 @@ namespace cds { namespace intrusive { template bool insert( value_type& val, Func f ) { - hash_type const& hash = hash_accessor()(val); + hash_type const& hash = hash_accessor()( val ); traverse_data pos( hash, *this ); hash_comparator cmp; typename gc::template GuardArray<2> guards; @@ -626,13 +626,13 @@ namespace cds { namespace intrusive { assert( slot.bits() == 0 ); // protect data node by hazard pointer - if (guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) { + if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) { // slot value has been changed - retry stats().onSlotChanged(); } - if (slot.ptr()) { - if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) { + if ( slot.ptr()) { + if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) { // the item with that hash value already exists stats().onInsertFailed(); return false; @@ -644,13 +644,13 @@ namespace cds { namespace intrusive { else { // the slot is empty, try to insert data node node_ptr pNull; - if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed )) + if ( pos.pArr->nodes[pos.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(val); + f( val ); ++m_ItemCounter; stats().onInsertSuccess(); - stats().height(pos.nHeight); + stats().height( pos.nHeight ); return true; } @@ -678,7 +678,7 @@ namespace cds { namespace intrusive { */ std::pair update( value_type& val, bool bInsert = true ) { - return do_update(val, [](value_type&, value_type *) {}, bInsert ); + return do_update( val, []( value_type&, value_type* ) {}, bInsert ); } /// Unlinks the item \p val from the set @@ -691,7 +691,7 @@ namespace cds { namespace intrusive { bool unlink( value_type const& val ) { typename gc::Guard guard; - auto pred = [&val](value_type const& item) -> bool { return &item == &val; }; + auto pred = [&val]( value_type const& item ) -> bool { return &item == &val; }; value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred )); return p != nullptr; } @@ -706,7 +706,7 @@ namespace cds { namespace intrusive { */ bool erase( hash_type const& hash ) { - return erase(hash, [](value_type const&) {} ); + return erase( hash, []( value_type const& ) {} ); } /// Deletes the item from the set @@ -834,7 +834,7 @@ namespace cds { namespace intrusive { */ bool contains( hash_type const& hash ) { - return find( hash, [](value_type&) {} ); + return find( hash, []( value_type& ) {} ); } /// Finds an item by it's \p hash and returns the item found @@ -920,7 +920,7 @@ namespace cds { namespace intrusive { Result can be useful for estimating efficiency of hash functor you use. */ - void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const + void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const { base_class::get_level_statistics( stat ); } @@ -1061,7 +1061,7 @@ namespace cds { namespace intrusive { } else if ( slot.bits() == base_class::flag_array_converting ) { // the slot is converting to array node right now - while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) { + while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) { bkoff(); stats().onSlotConverting(); } @@ -1095,17 +1095,17 @@ namespace cds { namespace intrusive { traverse_data pos( hash, *this ); hash_comparator cmp; - while (true) { + while ( true ) { node_ptr slot = base_class::traverse( pos ); - assert(slot.bits() == 0); + assert( slot.bits() == 0 ); // protect data node by hazard pointer - if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) { + if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) { // slot value has been changed - retry stats().onSlotChanged(); continue; } - else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) { + else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) { // item found stats().onFindSuccess(); return slot.ptr(); @@ -1120,21 +1120,21 @@ namespace cds { namespace intrusive { { traverse_data pos( hash, *this ); hash_comparator cmp; - while (true) { + while ( true ) { node_ptr slot = base_class::traverse( pos ); - assert(slot.bits() == 0); + assert( slot.bits() == 0 ); // protect data node by hazard pointer - if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) { + if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) { // slot value has been changed - retry stats().onSlotChanged(); } - else if (slot.ptr()) { - if ( cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) { + else if ( slot.ptr()) { + if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) { // item found - replace it with nullptr - if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) { + if ( pos.pArr->nodes[pos.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()); + gc::template retire( slot.ptr()); --m_ItemCounter; stats().onEraseSuccess(); @@ -1168,7 +1168,7 @@ namespace cds { namespace intrusive { for (;;) { 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)) { + 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; @@ -1190,30 +1190,30 @@ namespace cds { namespace intrusive { typename gc::template GuardArray<2> guards; guards.assign( 1, &val ); - while (true) { + while ( true ) { node_ptr slot = base_class::traverse( pos ); - assert(slot.bits() == 0); + assert( slot.bits() == 0 ); // protect data node by hazard pointer - if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) { + if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) { // slot value has been changed - retry stats().onSlotChanged(); } else if ( slot.ptr()) { - if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) { + if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) { // the item with that hash value already exists // Replace it with val if ( slot.ptr() == &val ) { stats().onUpdateExisting(); - return std::make_pair(true, false); + return std::make_pair( true, false ); } - if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) { + if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) { // slot can be disposed f( val, slot.ptr()); gc::template retire( slot.ptr()); stats().onUpdateExisting(); - return std::make_pair(true, false); + return std::make_pair( true, false ); } stats().onUpdateRetry(); @@ -1226,26 +1226,26 @@ namespace cds { namespace intrusive { } else { stats().onUpdateFailed(); - return std::make_pair(false, false); + return std::make_pair( false, false ); } } else { // the slot is empty, try to insert data node if ( bInsert ) { node_ptr pNull; - if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) + if ( pos.pArr->nodes[pos.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(val, nullptr); + f( val, nullptr ); ++m_ItemCounter; stats().onUpdateNew(); stats().height( pos.nHeight ); - return std::make_pair(true, true); + return std::make_pair( true, true ); } } else { stats().onUpdateFailed(); - return std::make_pair(false, false); + return std::make_pair( false, false ); } // insert failed - slot has been changed by another thread -- 2.34.1