-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ 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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
#ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
#define CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
/// 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;
: 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;
}
template <bool IsConst2>
- bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
+ bool operator ==( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
{
return iterator_base::operator==( rhs );
}
template <bool IsConst2>
- bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
+ bool operator !=( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
{
return !( *this == rhs );
}
}
template <bool IsConst2>
- bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
+ bool operator ==( reverse_bidirectional_iterator<IsConst2> const& rhs ) const
{
return iterator_base::operator==( rhs );
}
template <bool IsConst2>
- bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
+ bool operator !=( reverse_bidirectional_iterator<IsConst2> const& rhs )
{
return !( *this == rhs );
}
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.
*/
template <typename K>
bool insert( K&& key )
{
- scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
+ scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key )));
if ( base_class::insert( *sp )) {
sp.release();
return true;
template <typename K, typename V>
bool insert( K&& key, V&& val )
{
- scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
+ scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key ), std::forward<V>( val )));
if ( base_class::insert( *sp )) {
sp.release();
return true;
template <typename K, typename Func>
bool insert_with( K&& key, Func func )
{
- scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
+ scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key )));
if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
sp.release();
return true;
template <typename K, typename... Args>
bool emplace( K&& key, Args&&... args )
{
- scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
+ scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key ), std::forward<Args>( args )... ));
if ( base_class::insert( *sp )) {
sp.release();
return true;
The functor may change any fields of the \p item.second.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ Returns <tt> std::pair<bool, bool> </tt> 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"
template <typename K, typename Func>
std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
{
- scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
+ scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key )));
std::pair<bool, bool> result = base_class::do_update( *sp,
[&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
bInsert );
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.
template <typename K, typename Func>
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
{
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
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;
+ return base_class::extract( m_Hasher( key_type( key )));
}
/// Checks whether the map contains \p key
template <typename K>
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
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 );});
+ 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
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;
+ return base_class::get( m_Hasher( key_type( key )));
}
/// Clears the map (non-atomic)
}
/// Collects tree level statistics into \p stat
- /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
+ /**
+ The function traverses the set and collects statistics for each level of the tree
+ into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
+ represents statistics for level \p i, level 0 is head array.
+ The function is thread-safe and may be called in multi-threaded environment.
+
+ 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 );
}
projects / libcds.git / blobdiff