-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * 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_CUCKOO_MAP_H
#define CDSLIB_CONTAINER_CUCKOO_MAP_H
template <typename K>
node_type( K const& key )
- : m_val( std::make_pair( key_type(key), mapped_type() ))
+ : m_val( std::make_pair( key_type(key), mapped_type()))
{}
template <typename K, typename Q>
node_type( K const& key, Q const& v )
- : m_val( std::make_pair( key_type(key), mapped_type(v) ))
+ : m_val( std::make_pair( key_type(key), mapped_type(v)))
{}
template <typename K, typename... Args>
node_type( K&& key, Args&&... args )
- : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)) )
+ : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)))
{}
};
<b>About Cuckoo hashing</b>
[From "The Art of Multiprocessor Programming"]
- Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
+ <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
N = 2k we use a two-entry array of tables, and two independent hash functions,
<tt> h0, h1: KeyRange -> 0,...,k-1</tt>
the average search complexity is <tt>O(PROBE_SET/2)</tt>.
However, the overhead of sorting can eliminate a gain of ordered search.
- The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
- declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
- opt::equal_to option.
+ The probe set is ordered if \p compare or \p less is specified in \p Traits
+ template parameter. Otherwise, the probe set is unordered and \p Traits must contain
+ \p equal_to predicate.
Template arguments:
- \p Key - key type
- \p T - the type stored in the map.
- - \p Traits - map traits., default is \p cuckoo::traits.
+ - \p Traits - map traits, default is \p cuckoo::traits.
It is possible to declare option-based set with \p cuckoo::make_traits metafunction
result as \p Traits template argument.
/// item counter type
typedef typename traits::item_counter item_counter;
- //@cond
- typedef cds::container::cuckoo::implementation_tag implementation_tag;
- //@endcond
-
protected:
//@cond
typedef typename base_class::scoped_cell_lock scoped_cell_lock;
CuckooMap(
hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : base_class( std::forward<hash_tuple_type>(h) )
+ : base_class( std::forward<hash_tuple_type>(h))
{}
/// Constructs a map with given probe set properties and hash functor tuple (move semantics)
, unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
, hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
)
- : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
+ : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h))
{}
/// Destructor clears the map
return false;
}
- /// Ensures that the \p key exists in the map
+ /// Updates the node
/**
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
- is inserted into the map (note that in this case the \ref key_type should be
- constructible from type \p K).
+ If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
Otherwise, the functor \p func is called with item found.
- The functor \p Func may be a function with signature:
- \code
- void func( bool bNew, value_type& item );
- \endcode
- or a functor:
+ The functor \p func signature is:
\code
struct my_functor {
void operator()( bool bNew, value_type& item );
};
\endcode
-
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - item of the list
-
- The functor may change any fields of the \p item.second that is \ref value_type.
+ - \p item - an item of the map for \p key
- Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
- \p second is true if new item has been added or \p false if the item with \p key
- already is in the list.
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+ i.e. the node has been inserted or updated,
+ \p second is \p true if new item has been added or \p false if the item with \p key
+ already exists.
*/
template <typename K, typename Func>
- std::pair<bool, bool> ensure( K const& key, Func func )
+ std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
{
scoped_node_ptr pNode( alloc_node( key ));
- std::pair<bool, bool> res = base_class::ensure( *pNode,
- [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }
+ std::pair<bool, bool> res = base_class::update( *pNode,
+ [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); },
+ bAllowInsert
);
if ( res.first && res.second )
pNode.release();
return res;
}
+ //@cond
+ template <typename K, typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( K const& key, Func func )
+ {
+ return update( key, func, true );
+ }
+ //@endcond
/// Delete \p key from the map
/** \anchor cds_nonintrusive_CuckooMap_erase_val
bool erase_with( K const& key, Predicate pred, Func f )
{
CDS_UNUSED( pred );
- node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
+ node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
if ( pNode ) {
f( pNode->m_val );
free_node( pNode );
[&f](node_type& item, K const& ) { f( item.m_val );});
}
- /// Find the key \p key
- /** \anchor cds_nonintrusive_CuckooMap_find_val
-
+ /// Checks whether the map contains \p key
+ /**
The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
*/
template <typename K>
+ bool contains( K const& key )
+ {
+ return base_class::contains( key );
+ }
+ //@cond
+ template <typename K>
+ CDS_DEPRECATED("the function is deprecated, use contains()")
bool find( K const& key )
{
- return base_class::find( key );
+ return contains( key );
}
+ //@endcond
- /// Find the key \p val using \p pred predicate for comparing
+ /// Checks whether the map contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
- but \p pred is used for key comparison.
- If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
- If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
- \p pred must imply the same element order as the comparator used for building the map.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p Less must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Predicate>
- bool find_with( K const& key, Predicate pred )
+ bool contains( K const& key, Predicate pred )
{
CDS_UNUSED( pred );
- return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
+ return base_class::contains( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
+ }
+ //@cond
+ template <typename K, typename Predicate>
+ CDS_DEPRECATED("the function is deprecated, use contains()")
+ bool find_with( K const& key, Predicate pred )
+ {
+ return contains( key, pred );
}
+ //@endcond
/// Clears the map
void clear()
{
- base_class::clear_and_dispose( node_disposer() );
+ base_class::clear_and_dispose( node_disposer());
}
/// Checks if the map is empty
projects / libcds.git / blobdiff