--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
+#define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
+
+#include <cds/intrusive/details/feldman_hashset_base.h>
+#include <cds/container/details/base.h>
+#include <cds/opt/hash.h>
+
+namespace cds { namespace container {
+ /// \p FeldmanHashMap related definitions
+ /** @ingroup cds_nonintrusive_helper
+ */
+ namespace feldman_hashmap {
+ /// \p FeldmanHashMap internal statistics, see cds::intrusive::feldman_hashset::stat
+ template <typename EventCounter = cds::atomicity::event_counter>
+ using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
+
+ /// \p FeldmanHashMap empty internal statistics
+ typedef cds::intrusive::feldman_hashset::empty_stat empty_stat;
+
+ /// Bit-wise memcmp-based comparator for hash value \p T
+ template <typename T>
+ using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
+
+ /// \p FeldmanHashMap traits
+ struct traits
+ {
+ /// Hash functor, default is \p opt::none
+ /**
+ \p FeldmanHashMap may use any hash functor converting a key to
+ fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
+ <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
+
+ If you use a fixed-sized key you may use it directly instead of a hash.
+ In such case \p %traits::hash should be specified as \p opt::none.
+ However, if you want to use the hash values or if your key type is not fixed-sized
+ you must specify a proper hash functor in your traits.
+ For example:
+ fixed-sized key - IP4 address map
+ @code
+ // Key - IP address
+ struct ip4_address {
+ uint8_t ip[4];
+ };
+
+ // IP compare
+ struct ip4_cmp {
+ int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
+ {
+ return memcmp( &lhs, &rhs, sizeof(lhs));
+ }
+ };
+
+ // Value - statistics for the IP address
+ struct statistics {
+ // ...
+ };
+
+ // Traits
+ // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
+ struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
+ {
+ typedef ip4_cmp compare;
+ };
+
+ // IP4 address - statistics map
+ typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
+ @endcode
+
+ variable-size key requires a hash functor: URL map
+ @code
+ // Value - statistics for the URL
+ struct statistics {
+ // ...
+ };
+
+ // Traits
+ // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
+ // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
+ struct url_map_traits: public cds::container::multilevl_hashmap::traits
+ {
+ typedef std::hash<std::string> hash;
+ };
+
+ // URL statistics map
+ typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
+ @endcode
+ */
+ typedef opt::none hash;
+
+ /// Hash comparing functor
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::compare
+ */
+ typedef cds::opt::none compare;
+
+ /// Specifies binary predicate used for hash compare.
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::less
+ */
+ typedef cds::opt::none less;
+
+ /// Item counter
+ /**
+ @copydetails cds::intrusive::feldman_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::feldman_hashset::traits::node_allocator
+ */
+ typedef CDS_DEFAULT_ALLOCATOR node_allocator;
+
+ /// C++ memory ordering model
+ /**
+ @copydetails cds::intrusive::feldman_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::feldman_hashset::traits::stat
+ */
+ typedef empty_stat stat;
+
+ /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
+ */
+ typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
+ };
+
+ /// Metafunction converting option list to \p feldman_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::feldman_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::container::feldman_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 feldman_hashmap::empty_stat).
+ To enable it use \p feldman_hashmap::stat
+ - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
+ Default is \p opt::v::rcu_throw_deadlock
+ */
+ template <typename... Options>
+ 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 feldman_hashmap
+
+ //@cond
+ // Forward declaration
+ template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
+ class FeldmanHashMap;
+ //@endcond
+
+ //@cond
+ namespace details {
+
+ template <typename Key, typename Value, typename Hash>
+ struct hash_selector
+ {
+ typedef Key key_type;
+ typedef Value mapped_type;
+ typedef Hash hasher;
+
+ typedef typename std::decay<
+ typename std::remove_reference<
+ decltype(hasher()(std::declval<key_type>()))
+ >::type
+ >::type hash_type;
+
+ 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 <typename Q>
+ node_type(hasher& h, Q const& key)
+ : m_Value(std::move(std::make_pair(key, mapped_type())))
+ , m_hash(h(m_Value.first))
+ {}
+
+ template <typename Q, typename U >
+ node_type(hasher& h, Q const& key, U const& val)
+ : m_Value(std::move(std::make_pair(key, mapped_type(val))))
+ , m_hash(h(m_Value.first))
+ {}
+
+ template <typename Q, typename... Args>
+ node_type(hasher& h, Q&& key, Args&&... args)
+ : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
+ , m_hash(h(m_Value.first))
+ {}
+ };
+
+ struct hash_accessor
+ {
+ hash_type const& operator()(node_type const& node) const
+ {
+ return node.m_hash;
+ }
+ };
+ };
+
+ template <typename Key, typename Value>
+ struct hash_selector<Key, Value, opt::none>
+ {
+ typedef Key key_type;
+ typedef Value mapped_type;
+
+ struct hasher {
+ key_type const& operator()(key_type const& k) const
+ {
+ return k;
+ }
+ };
+ typedef key_type hash_type;
+
+ struct node_type
+ {
+ std::pair< key_type const, mapped_type> m_Value;
+
+ node_type() = delete;
+ node_type(node_type const&) = delete;
+
+ template <typename Q>
+ node_type(hasher /*h*/, Q const& key)
+ : m_Value(std::move(std::make_pair(key, mapped_type())))
+ {}
+
+ template <typename Q, typename U >
+ node_type(hasher /*h*/, Q const& key, U const& val)
+ : m_Value(std::move(std::make_pair(key, mapped_type(val))))
+ {}
+
+ template <typename Q, typename... Args>
+ node_type(hasher /*h*/, Q&& key, Args&&... args)
+ : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
+ {}
+ };
+
+ struct hash_accessor
+ {
+ hash_type const& operator()(node_type const& node) const
+ {
+ return node.m_Value.first;
+ }
+ };
+ };
+
+ template <typename GC, typename Key, typename T, typename Traits>
+ struct make_feldman_hashmap
+ {
+ typedef GC gc;
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef Traits original_traits;
+
+
+ typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
+ typedef typename select::hasher hasher;
+ typedef typename select::hash_type hash_type;
+ typedef typename select::node_type node_type;
+
+ 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 intrusive_traits: public original_traits
+ {
+ typedef typename select::hash_accessor hash_accessor;
+ typedef node_disposer disposer;
+ };
+
+ // Metafunction result
+ typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
+ };
+ } // namespace details
+ //@endcond
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHSET_BASE_H
+#define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHSET_BASE_H
+
+#include <cds/intrusive/details/feldman_hashset_base.h>
+#include <cds/container/details/base.h>
+
+namespace cds { namespace container {
+ /// \p FeldmanHashSet related definitions
+ /** @ingroup cds_nonintrusive_helper
+ */
+ namespace feldman_hashset {
+ /// Hash accessor option
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::hash_accessor
+ */
+ template <typename Accessor>
+ using hash_accessor = cds::intrusive::feldman_hashset::hash_accessor< Accessor >;
+
+ /// \p FeldmanHashSet internal statistics, see cds::intrusive::feldman_hashset::stat
+ template <typename EventCounter = cds::atomicity::event_counter>
+ using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
+
+ /// \p FeldmanHashSet empty internal statistics
+ typedef cds::intrusive::feldman_hashset::empty_stat empty_stat;
+
+ /// Bit-wise memcmp-based comparator for hash value \p T
+ template <typename T>
+ using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
+
+ /// \p FeldmanHashSet traits
+ struct traits
+ {
+ /// Mandatory functor to get hash value from data node
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::hash_accessor
+ */
+ typedef cds::opt::none hash_accessor;
+
+ /// Hash comparing functor
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::compare
+ */
+ typedef cds::opt::none compare;
+
+ /// Specifies binary predicate used for hash compare.
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::less
+ */
+ typedef cds::opt::none less;
+
+ /// Item counter
+ /**
+ @copydetails cds::intrusive::feldman_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::feldman_hashset::traits::node_allocator
+ */
+ typedef CDS_DEFAULT_ALLOCATOR node_allocator;
+
+ /// C++ memory ordering model
+ /**
+ @copydetails cds::intrusive::feldman_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::feldman_hashset::traits::stat
+ */
+ typedef empty_stat stat;
+
+ /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashSet_rcu "RCU-based FeldmanHashSet")
+ /**
+ @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
+ */
+ typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
+ };
+
+ /// Metafunction converting option list to \p feldman_hashset::traits
+ /**
+ Supported \p Options are:
+ - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor.
+ @copydetails traits::hash_accessor
+ - \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::feldman_hashset::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::feldman_hashset::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 feldman_hashset::empty_stat).
+ To enable it use \p feldman_hashset::stat
+ - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
+ Default is \p opt::v::rcu_throw_deadlock
+ */
+ template <typename... Options>
+ 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 feldman_hashset
+
+ //@cond
+ // Forward declaration
+ template < class GC, typename T, class Traits = cds::container::feldman_hashset::traits >
+ class FeldmanHashSet;
+ //@endcond
+
+ //@cond
+ namespace details {
+
+ template <typename GC, typename T, typename Traits>
+ struct make_feldman_hashset
+ {
+ typedef GC gc;
+ typedef T value_type;
+ typedef Traits original_traits;
+
+ typedef cds::details::Allocator< value_type, typename original_traits::allocator > cxx_node_allocator;
+
+ struct node_disposer
+ {
+ void operator()( value_type * p ) const
+ {
+ cxx_node_allocator().Delete( p );
+ }
+ };
+
+ struct intrusive_traits: public original_traits
+ {
+ typedef node_disposer disposer;
+ };
+
+ // Metafunction result
+ typedef cds::intrusive::FeldmanHashSet< GC, T, intrusive_traits > type;
+ };
+ } // namespace details
+ //@endcond
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHSET_BASE_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
-#define CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHMAP_BASE_H
-
-#include <cds/intrusive/details/multilevel_hashset_base.h>
-#include <cds/container/details/base.h>
-#include <cds/opt/hash.h>
-
-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 <typename EventCounter = cds::atomicity::event_counter>
- 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 <typename T>
- using bitwise_compare = cds::intrusive::multilevel_hashset::bitwise_compare< T >;
-
- /// \p MultiLevelHashMap traits
- struct traits
- {
- /// Hash functor, default is \p opt::none
- /**
- \p MultiLevelHashMap may use any hash functor converting a key to
- fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
- <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
-
- If you use a fixed-sized key you may use it directly instead of a hash.
- In such case \p %traits::hash should be specified as \p opt::none.
- However, if you want to use the hash values or if your key type is not fixed-sized
- you must specify a proper hash functor in your traits.
- For example:
- fixed-sized key - IP4 address map
- @code
- // Key - IP address
- struct ip4_address {
- uint8_t ip[4];
- };
-
- // IP compare
- struct ip4_cmp {
- int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
- {
- return memcmp( &lhs, &rhs, sizeof(lhs));
- }
- };
-
- // Value - statistics for the IP address
- struct statistics {
- // ...
- };
-
- // Traits
- // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
- struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
- {
- typedef ip4_cmp compare;
- };
-
- // IP4 address - statistics map
- typedef cds::container::MultiLevelHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
- @endcode
-
- variable-size key requires a hash functor: URL map
- @code
- // Value - statistics for the URL
- struct statistics {
- // ...
- };
-
- // Traits
- // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
- // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
- struct url_map_traits: public cds::container::multilevl_hashmap::traits
- {
- typedef std::hash<std::string> hash;
- };
-
- // URL statistics map
- typedef cds::container::MultiLevelHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
- @endcode
- */
- 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_MultilevelHashMap_rcu "RCU-based MultilevelHashMap")
- /**
- @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::container::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 <typename... Options>
- 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 <typename Key, typename Value, typename Hash>
- struct hash_selector
- {
- typedef Key key_type;
- typedef Value mapped_type;
- typedef Hash hasher;
-
- typedef typename std::decay<
- typename std::remove_reference<
- decltype(hasher()(std::declval<key_type>()))
- >::type
- >::type hash_type;
-
- 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 <typename Q>
- node_type(hasher& h, Q const& key)
- : m_Value(std::move(std::make_pair(key, mapped_type())))
- , m_hash(h(m_Value.first))
- {}
-
- template <typename Q, typename U >
- node_type(hasher& h, Q const& key, U const& val)
- : m_Value(std::move(std::make_pair(key, mapped_type(val))))
- , m_hash(h(m_Value.first))
- {}
-
- template <typename Q, typename... Args>
- node_type(hasher& h, Q&& key, Args&&... args)
- : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
- , m_hash(h(m_Value.first))
- {}
- };
-
- struct hash_accessor
- {
- hash_type const& operator()(node_type const& node) const
- {
- return node.m_hash;
- }
- };
- };
-
- template <typename Key, typename Value>
- struct hash_selector<Key, Value, opt::none>
- {
- typedef Key key_type;
- typedef Value mapped_type;
-
- struct hasher {
- key_type const& operator()(key_type const& k) const
- {
- return k;
- }
- };
- typedef key_type hash_type;
-
- struct node_type
- {
- std::pair< key_type const, mapped_type> m_Value;
-
- node_type() = delete;
- node_type(node_type const&) = delete;
-
- template <typename Q>
- node_type(hasher /*h*/, Q const& key)
- : m_Value(std::move(std::make_pair(key, mapped_type())))
- {}
-
- template <typename Q, typename U >
- node_type(hasher /*h*/, Q const& key, U const& val)
- : m_Value(std::move(std::make_pair(key, mapped_type(val))))
- {}
-
- template <typename Q, typename... Args>
- node_type(hasher /*h*/, Q&& key, Args&&... args)
- : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
- {}
- };
-
- struct hash_accessor
- {
- hash_type const& operator()(node_type const& node) const
- {
- return node.m_Value.first;
- }
- };
- };
-
- template <typename GC, typename Key, typename T, typename Traits>
- struct make_multilevel_hashmap
- {
- typedef GC gc;
- typedef Key key_type;
- typedef T mapped_type;
- typedef Traits original_traits;
-
-
- typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
- typedef typename select::hasher hasher;
- typedef typename select::hash_type hash_type;
- typedef typename select::node_type node_type;
-
- 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 intrusive_traits: public original_traits
- {
- typedef typename select::hash_accessor hash_accessor;
- 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
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHSET_BASE_H
-#define CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHSET_BASE_H
-
-#include <cds/intrusive/details/multilevel_hashset_base.h>
-#include <cds/container/details/base.h>
-
-namespace cds { namespace container {
- /// \p MultiLevelHashSet related definitions
- /** @ingroup cds_nonintrusive_helper
- */
- namespace multilevel_hashset {
- /// Hash accessor option
- /**
- @copydetails cds::intrusive::multilevel_hashset::traits::hash_accessor
- */
- template <typename Accessor>
- using hash_accessor = cds::intrusive::multilevel_hashset::hash_accessor< Accessor >;
-
- /// \p MultiLevelHashSet internal statistics, see cds::intrusive::multilevel_hashset::stat
- template <typename EventCounter = cds::atomicity::event_counter>
- using stat = cds::intrusive::multilevel_hashset::stat< EventCounter >;
-
- /// \p MultiLevelHashSet empty internal statistics
- typedef cds::intrusive::multilevel_hashset::empty_stat empty_stat;
-
- /// Bit-wise memcmp-based comparator for hash value \p T
- template <typename T>
- using bitwise_compare = cds::intrusive::multilevel_hashset::bitwise_compare< T >;
-
- /// \p MultiLevelHashSet traits
- struct traits
- {
- /// Mandatory functor to get hash value from data node
- /**
- @copydetails cds::intrusive::multilevel_hashset::traits::hash_accessor
- */
- typedef cds::opt::none hash_accessor;
-
- /// 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_hashset::traits
- /**
- Supported \p Options are:
- - \p multilevel_hashset::hash_accessor - mandatory option, hash accessor functor.
- @copydetails traits::hash_accessor
- - \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_hashset::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_hashset::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_hashset::empty_stat).
- To enable it use \p multilevel_hashset::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 <typename... Options>
- 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_hashset
-
- //@cond
- // Forward declaration
- template < class GC, typename T, class Traits = cds::container::multilevel_hashset::traits >
- class MultiLevelHashSet;
- //@endcond
-
- //@cond
- namespace details {
-
- template <typename GC, typename T, typename Traits>
- struct make_multilevel_hashset
- {
- typedef GC gc;
- typedef T value_type;
- typedef Traits original_traits;
-
- typedef cds::details::Allocator< value_type, typename original_traits::allocator > cxx_node_allocator;
-
- struct node_disposer
- {
- void operator()( value_type * p ) const
- {
- cxx_node_allocator().Delete( p );
- }
- };
-
- struct intrusive_traits: public original_traits
- {
- typedef node_disposer disposer;
- };
-
- // Metafunction result
- typedef cds::intrusive::MultiLevelHashSet< GC, T, intrusive_traits > type;
- };
- } // namespace details
- //@endcond
-
-}} // namespace cds::container
-
-#endif // #ifndef CDSLIB_CONTAINER_DETAILS_MULTILEVEL_HASHSET_BASE_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_DHP_H
+#define CDSLIB_CONTAINER_FELDMAN_HASHMAP_DHP_H
+
+#include <cds/container/impl/feldman_hashmap.h>
+#include <cds/gc/dhp.h>
+
+#endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_DHP_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_HP_H
+#define CDSLIB_CONTAINER_FELDMAN_HASHMAP_HP_H
+
+#include <cds/container/impl/feldman_hashmap.h>
+#include <cds/gc/hp.h>
+
+#endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_HP_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H
+#define CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H
+
+#include <cds/intrusive/feldman_hashset_rcu.h>
+#include <cds/container/details/feldman_hashmap_base.h>
+
+namespace cds { namespace container {
+
+ /// Hash map based on multi-level array
+ /** @ingroup cds_nonintrusive_map
+ @anchor cds_container_FeldmanHashMap_rcu
+
+ Source:
+ - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
+ Wait-free Extensible Hash Maps"
+
+ See algorithm short description @ref cds_container_FeldmanHashMap_hp "here"
+
+ @note Two important things you should keep in mind when you're using \p %FeldmanHashMap:
+ - 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 %FeldmanHashMap,
+ but real key in the map will be fixed-size hash values of your keys.
+ For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
+ converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %FeldmanHashMap.
+ If your key is fixed-sized the hash functor is optional, see \p feldman_hashmap::traits::hash for explanation and examples.
+ - \p %FeldmanHashMap 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 map. \p %FeldmanHashMap does not maintain the key,
+ it maintains its fixed-size hash value.
+
+ The map supports @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional thread-safe iterators".
+
+ Template parameters:
+ - \p RCU - one of \ref cds_urcu_gc "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 feldman_hashmap::traits or result of \p feldman_hashmap::make_traits metafunction.
+
+ @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
+ see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
+ */
+ template <
+ class RCU
+ ,typename Key
+ ,typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ ,class Traits = feldman_hashmap::traits
+#else
+ ,class Traits
+#endif
+ >
+ class FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
+#ifdef CDS_DOXYGEN_INVOKED
+ : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
+#else
+ : protected cds::container::details::make_feldman_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
+#endif
+ {
+ //@cond
+ typedef cds::container::details::make_feldman_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
+ typedef typename maker::type base_class;
+ //@endcond
+ public:
+ typedef cds::urcu::gc< RCU > gc; ///< RCU 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 feldman_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 traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+ typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
+ static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
+
+ 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;
+ typedef typename base_class::check_deadlock_policy check_deadlock_policy;
+
+ struct node_cast
+ {
+ value_type * operator()(node_type * p) const
+ {
+ return p ? &p->m_Value : nullptr;
+ }
+ };
+
+ public:
+ /// pointer to extracted node
+ using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
+
+ protected:
+ template <bool IsConst>
+ class bidirectional_iterator: public base_class::iterator_base
+ {
+ friend class FeldmanHashMap;
+ typedef typename base_class::iterator_base iterator_base;
+
+ protected:
+ static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
+
+ public:
+ typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
+
+ public:
+ bidirectional_iterator() CDS_NOEXCEPT
+ {}
+
+ bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ : iterator_base( rhs )
+ {}
+
+ bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ {
+ iterator_base::operator=( rhs );
+ return *this;
+ }
+
+ bidirectional_iterator& operator++()
+ {
+ iterator_base::operator++();
+ return *this;
+ }
+
+ bidirectional_iterator& operator--()
+ {
+ iterator_base::operator--();
+ return *this;
+ }
+
+ value_ptr operator ->() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ return p ? &p->m_Value : nullptr;
+ }
+
+ value_ref operator *() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ assert( p );
+ return p->m_Value;
+ }
+
+ void release()
+ {
+ iterator_base::release();
+ }
+
+ template <bool IsConst2>
+ 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
+ {
+ return !( *this == rhs );
+ }
+
+ public: // for internal use only!
+ bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
+ : iterator_base( set, pNode, idx, false )
+ {}
+
+ bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
+ : iterator_base( set, pNode, idx )
+ {}
+ };
+
+ /// Reverse bidirectional iterator
+ template <bool IsConst>
+ class reverse_bidirectional_iterator : public base_class::iterator_base
+ {
+ friend class FeldmanHashMap;
+ typedef typename base_class::iterator_base iterator_base;
+
+ public:
+ typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
+
+ public:
+ reverse_bidirectional_iterator() CDS_NOEXCEPT
+ : iterator_base()
+ {}
+
+ reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ : iterator_base( rhs )
+ {}
+
+ reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ {
+ iterator_base::operator=( rhs );
+ return *this;
+ }
+
+ reverse_bidirectional_iterator& operator++()
+ {
+ iterator_base::operator--();
+ return *this;
+ }
+
+ reverse_bidirectional_iterator& operator--()
+ {
+ iterator_base::operator++();
+ return *this;
+ }
+
+ value_ptr operator ->() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ return p ? &p->m_Value : nullptr;
+ }
+
+ value_ref operator *() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ assert( p );
+ return p->m_Value;
+ }
+
+ void release()
+ {
+ iterator_base::release();
+ }
+
+ template <bool IsConst2>
+ 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)
+ {
+ return !( *this == rhs );
+ }
+
+ public: // for internal use only!
+ reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
+ : iterator_base( set, pNode, idx, false )
+ {}
+
+ reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
+ : iterator_base( set, pNode, idx, false )
+ {
+ iterator_base::backward();
+ }
+ };
+ //@endcond
+
+ public:
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional iterator" type
+ typedef implementation_defined const_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional const iterator" type
+ typedef implementation_defined reverse_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional reverse iterator" type
+ typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional reverse const iterator" type
+#else
+ typedef bidirectional_iterator<false> iterator;
+ typedef bidirectional_iterator<true> const_iterator;
+ typedef reverse_bidirectional_iterator<false> reverse_iterator;
+ typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
+#endif
+
+ protected:
+ //@cond
+ hasher m_Hasher;
+ //@endcond
+
+ public:
+ /// Creates empty map
+ /**
+ @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
+ @param array_bits: 2<sup>array_bits</sup> 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.
+ */
+ FeldmanHashMap( size_t head_bits = 8, size_t array_bits = 4 )
+ : base_class( head_bits, array_bits )
+ {}
+
+ /// Destructs the map and frees all data
+ ~FeldmanHashMap()
+ {}
+
+ /// 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.
+
+ The function locks RCU internally.
+ */
+ template <typename K>
+ bool insert( 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;
+ }
+ 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 map, \p false otherwise.
+
+ The function locks RCU internally.
+ */
+ 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)));
+ 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:
+ - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
+ - <tt>item.second</tt> 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.
+
+ The function locks RCU internally.
+ */
+ 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)));
+ 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 <tt>std::forward<Args>(args)...</tt>
+ /**
+ Returns \p true if inserting successful, \p false otherwise.
+
+ The function locks RCU internally.
+ */
+ 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)... ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Updates data by \p key
+ /**
+ The operation performs inserting or replacing the element 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, it is replaced with a new item created from
+ \p key.
+ The functor \p Func signature:
+ \code
+ struct my_functor {
+ void operator()( value_type& item, value_type * old );
+ };
+ \endcode
+ where:
+ - \p item - item of the map
+ - \p old - old item of the map, if \p nullptr - the new item was inserted
+
+ 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,
+ \p second is \p true if new item has been added or \p false if \p key already exists.
+
+ The function locks RCU internally.
+
+ @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)));
+ 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 );
+ 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.
+ The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
+
+ Return \p true if \p key is found and deleted, \p false otherwise.
+
+ RCU should not be locked. The function locks RCU internally.
+ */
+ template <typename K>
+ bool erase( K const& key )
+ {
+ return base_class::erase(m_Hasher(key_type(key)));
+ }
+
+ /// Delete \p key from the map
+ /**
+ The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
+ 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
+ where \p item is the element found.
+
+ \p key_type must be constructible from value of type \p K.
+
+ Return \p true if key is found and deleted, \p false otherwise
+
+ RCU should not be locked. The function locks RCU internally.
+ */
+ 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 ); });
+ }
+
+ /// Extracts the item from the map with specified \p key
+ /**
+ The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
+ unlinks it from the map, and returns a guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not call the disposer for the item found.
+ The disposer will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
+ Example:
+ \code
+ typedef cds::container::FeldmanHashMap< cds::urcu::gc< cds::urcu::general_buffered<>>, int, foo, my_traits > map_type;
+ map_type theMap;
+ // ...
+
+ typename map_type::exempt_ptr ep( theMap.extract( 5 ));
+ if ( ep ) {
+ // Deal with ep
+ //...
+
+ // Dispose returned item.
+ ep.release();
+ }
+ \endcode
+ */
+ template <typename K>
+ exempt_ptr extract( K const& key )
+ {
+ check_deadlock_policy::check();
+
+ node_type * p;
+ {
+ rcu_lock rcuLock;
+ p = base_class::do_erase( m_Hasher( key_type(key)), [](node_type const&) -> bool {return true;});
+ }
+ return exempt_ptr(p);
+ }
+
+ /// Checks whether the map contains \p key
+ /**
+ The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
+ and returns \p true if it is found, or \p false otherwise.
+ */
+ template <typename K>
+ bool contains( K const& key )
+ {
+ return base_class::contains( m_Hasher( key_type( key )) );
+ }
+
+ /// Find the key \p key
+ /**
+
+ The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
+ and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+
+ The functor may change \p item.second.
+
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ 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 );});
+ }
+
+ /// Finds the key \p key and return the item found
+ /**
+ The function searches the item by its \p hash
+ and returns the pointer to the item found.
+ If \p hash is not found the function returns \p nullptr.
+
+ RCU should be locked before the function invocation.
+ Returned pointer is valid only while RCU is locked.
+
+ Usage:
+ \code
+ typedef cds::container::FeldmanHashMap< your_template_params > my_map;
+ my_map theMap;
+ // ...
+ {
+ // lock RCU
+ my_map::rcu_lock;
+
+ foo * p = theMap.get( 5 );
+ if ( p ) {
+ // Deal with p
+ //...
+ }
+ }
+ \endcode
+ */
+ template <typename K>
+ value_type * get( K const& key )
+ {
+ node_type * p = base_class::get( m_Hasher( key_type( key )));
+ return p ? &p->m_Value : nullptr;
+ }
+
+ /// Clears the map (non-atomic)
+ /**
+ The function unlink all data node from the map.
+ The function is not atomic but is thread-safe.
+ After \p %clear() the map may not be empty because another threads may insert items.
+ */
+ void clear()
+ {
+ base_class::clear();
+ }
+
+ /// Checks if the map is empty
+ /**
+ Emptiness is checked by item counting: if item count is zero then the map is empty.
+ Thus, the correct item counting feature is an important part of the map implementation.
+ */
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Returns item count in the map
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+
+ /// Returns the size of head node
+ size_t head_size() const
+ {
+ return base_class::head_size();
+ }
+
+ /// Returns the size of the array node
+ size_t array_node_size() const
+ {
+ return base_class::array_node_size();
+ }
+
+ public:
+ ///@name Thread-safe iterators
+ /** @anchor cds_container_FeldmanHashMap_rcu_iterators
+ The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment
+ under explicit RCU lock.
+ RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map
+ since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
+ while your thread is iterating.
+
+ A typical example is:
+ \code
+ struct foo {
+ // ... other fields
+ uint32_t payload; // only for example
+ };
+ typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
+ typedef cds::container::FeldmanHashMap< rcu, std::string, foo> map_type;
+
+ map_type m;
+
+ // ...
+
+ // iterate over the map
+ {
+ // lock the RCU.
+ typename set_type::rcu_lock l; // scoped RCU lock
+
+ // traverse the map
+ for ( auto i = m.begin(); i != s.end(); ++i ) {
+ // deal with i. Remember, erasing is prohibited here!
+ i->second.payload++;
+ }
+ } // at this point RCU lock is released
+ /endcode
+
+ Each iterator object supports the common interface:
+ - dereference operators:
+ @code
+ value_type [const] * operator ->() noexcept
+ value_type [const] & operator *() noexcept
+ @endcode
+ - pre-increment and pre-decrement. Post-operators is not supported
+ - equality operators <tt>==</tt> and <tt>!=</tt>.
+ Iterators are equal iff they point to the same cell of the same array node.
+ Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
+ does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
+
+ @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
+ in an array node that is being splitted.
+ */
+ ///@{
+ /// Returns an iterator to the beginning of the map
+ iterator begin()
+ {
+ return base_class::template init_begin<iterator>();
+ }
+
+ /// Returns an const iterator to the beginning of the map
+ const_iterator begin() const
+ {
+ return base_class::template init_begin<const_iterator>();
+ }
+
+ /// Returns an const iterator to the beginning of the map
+ const_iterator cbegin()
+ {
+ return base_class::template init_begin<const_iterator>();
+ }
+
+ /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ iterator end()
+ {
+ return base_class::template init_end<iterator>();
+ }
+
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator end() const
+ {
+ return base_class::template init_end<const_iterator>();
+ }
+
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator cend()
+ {
+ return base_class::template init_end<const_iterator>();
+ }
+
+ /// Returns a reverse iterator to the first element of the reversed map
+ reverse_iterator rbegin()
+ {
+ return base_class::template init_rbegin<reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed map
+ const_reverse_iterator rbegin() const
+ {
+ return base_class::template init_rbegin<const_reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed map
+ const_reverse_iterator crbegin()
+ {
+ return base_class::template init_rbegin<const_reverse_iterator>();
+ }
+
+ /// Returns a reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ reverse_iterator rend()
+ {
+ return base_class::template init_rend<reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator rend() const
+ {
+ return base_class::template init_rend<const_reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator crend()
+ {
+ return base_class::template init_rend<const_reverse_iterator>();
+ }
+ ///@}
+ };
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_DHP_H
+#define CDSLIB_CONTAINER_FELDMAN_HASHSET_DHP_H
+
+#include <cds/container/impl/feldman_hashset.h>
+#include <cds/gc/dhp.h>
+
+#endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_DHP_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_HP_H
+#define CDSLIB_CONTAINER_FELDMAN_HASHSET_HP_H
+
+#include <cds/container/impl/feldman_hashset.h>
+#include <cds/gc/hp.h>
+
+#endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_HP_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
+#define CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
+
+#include <cds/intrusive/feldman_hashset_rcu.h>
+#include <cds/container/details/feldman_hashset_base.h>
+
+namespace cds { namespace container {
+
+ /// Hash set based on multi-level array, \ref cds_urcu_desc "RCU" specialization
+ /** @ingroup cds_nonintrusive_set
+ @anchor cds_container_FeldmanHashSet_rcu
+
+ Source:
+ - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
+ Wait-free Extensible Hash Maps"
+
+ See algorithm short description @ref cds_intrusive_FeldmanHashSet_hp "here"
+
+ @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
+ - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
+ Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
+ converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
+ - \p %FeldmanHashSet 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 %FeldmanHashSet does not maintain the key,
+ it maintains its fixed-size hash value.
+
+ The set supports @ref cds_container_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
+
+ Template parameters:
+ - \p RCU - one of \ref cds_urcu_gc "RCU type"
+ - \p T - a value type to be stored in the set
+ - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
+ \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
+ to hash value of \p T. The set algorithm does not calculate that hash value.
+
+ @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
+ see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
+
+ The set supports @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional thread-safe iterators"
+ with some restrictions.
+ */
+ template <
+ class RCU
+ , typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ , class Traits = feldman_hashset::traits
+#else
+ , class Traits
+#endif
+ >
+ class FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
+#ifdef CDS_DOXYGEN_INVOKED
+ : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
+#else
+ : protected cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits >::type
+#endif
+ {
+ //@cond
+ typedef cds::container::details::make_feldman_hashset< cds::urcu::gc< RCU >, T, Traits > maker;
+ typedef typename maker::type base_class;
+ //@endcond
+
+ public:
+ typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
+ typedef T value_type; ///< type of value stored in the set
+ typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
+
+ typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
+ typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
+ typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
+
+ 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 traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+ typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
+ static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
+ typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node
+
+ typedef typename base_class::iterator iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional iterator" type
+ typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional const iterator" type
+ typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse iterator" type
+ typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_FeldmanHashSet_rcu_iterators "bidirectional reverse const iterator" type
+
+ protected:
+ //@cond
+ typedef typename maker::cxx_node_allocator cxx_node_allocator;
+ typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
+ //@endcond
+
+ public:
+ /// Creates empty set
+ /**
+ @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
+ @param array_bits: 2<sup>array_bits</sup> 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.
+ */
+ FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
+ : base_class( head_bits, array_bits )
+ {}
+
+ /// Destructs the set and frees all data
+ ~FeldmanHashSet()
+ {}
+
+ /// Inserts new element
+ /**
+ The function creates an element with copy of \p val value and then inserts it into the set.
+
+ The type \p Q should contain as minimum the complete hash for the element.
+ The object of \ref value_type should be constructible from a value of type \p Q.
+ In trivial case, \p Q is equal to \ref value_type.
+
+ Returns \p true if \p val is inserted into the set, \p false otherwise.
+
+ The function locks RCU internally.
+ */
+ template <typename Q>
+ bool insert( Q const& val )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( val ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Inserts new element
+ /**
+ The function allows to split creating of new item into two part:
+ - create item with key only
+ - insert new item into the set
+ - if inserting is success, calls \p f functor to initialize value-fields of \p val.
+
+ The functor signature is:
+ \code
+ void func( value_type& val );
+ \endcode
+ where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
+ \p val no any other changes could be made on this set's item by concurrent threads.
+ The user-defined functor is called only if the inserting is success.
+
+ The function locks RCU internally.
+ */
+ template <typename Q, typename Func>
+ bool insert( Q const& val, Func f )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( val ));
+ if ( base_class::insert( *sp, f )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Updates the element
+ /**
+ The operation performs inserting or replacing with lock-free manner.
+
+ If the \p val key not found in the set, then the new item created from \p val
+ will be inserted into the set iff \p bInsert is \p true.
+ Otherwise, if \p val is found, it is replaced with new item created from \p val
+ and previous item is disposed.
+ In both cases \p func functor is called.
+
+ The functor \p Func signature:
+ \code
+ struct my_functor {
+ void operator()( value_type& cur, value_type * prev );
+ };
+ \endcode
+ where:
+ - \p cur - current element
+ - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
+ if \p cur was just inserted.
+
+ The functor may change non-key fields of the \p item; however, \p func must guarantee
+ that during changing no any other modifications could be made on this item by concurrent threads.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ i.e. the item has been inserted or updated,
+ \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
+ already exists.
+ */
+ template <typename Q, typename Func>
+ std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( val ));
+ std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
+ if ( bRes.first )
+ sp.release();
+ return bRes;
+ }
+
+ /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
+ /**
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ template <typename... Args>
+ bool emplace( Args&&... args )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( std::forward<Args>(args)... ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Deletes the item from the set
+ /**
+ The function searches \p hash in the set,
+ deletes the item found, and returns \p true.
+ If that item is not found the function returns \p false.
+
+ RCU should not be locked. The function locks RCU internally.
+ */
+ bool erase( hash_type const& hash )
+ {
+ return base_class::erase( hash );
+ }
+
+ /// Deletes the item from the set
+ /**
+ The function searches \p hash in the set,
+ call \p f functor with item found, and deltes the element from the set.
+
+ The \p Func interface is
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+
+ If \p hash is not found the function returns \p false.
+
+ RCU should not be locked. The function locks RCU internally.
+ */
+ template <typename Func>
+ bool erase( hash_type const& hash, Func f )
+ {
+ return base_class::erase( hash, f );
+ }
+
+ /// Extracts the item with specified \p hash
+ /**
+ The function searches \p hash in the set,
+ unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
+ If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
+
+ RCU \p synchronize method can be called. RCU should NOT be locked.
+ The function does not call the disposer for the item found.
+ The disposer will be implicitly invoked when the returned object is destroyed or when
+ its \p release() member function is called.
+ Example:
+ \code
+ typedef cds::container::FeldmanHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
+ set_type theSet;
+ // ...
+
+ typename set_type::exempt_ptr ep( theSet.extract( 5 ));
+ if ( ep ) {
+ // Deal with ep
+ //...
+
+ // Dispose returned item.
+ ep.release();
+ }
+ \endcode
+ */
+ exempt_ptr extract( hash_type const& hash )
+ {
+ return base_class::extract( hash );
+ }
+
+ /// Finds an item by it's \p hash
+ /**
+ The function searches the item by \p hash and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+
+ The functor may change non-key fields of \p item. Note that the functor is only guarantee
+ that \p item cannot be disposed during the functor is executing.
+ The functor does not serialize simultaneous access to the set's \p item. If such access is
+ possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
+
+ The function returns \p true if \p hash is found, \p false otherwise.
+ */
+ template <typename Func>
+ bool find( hash_type const& hash, Func f )
+ {
+ return base_class::find( hash, f );
+ }
+
+ /// Checks whether the set contains \p hash
+ /**
+ The function searches the item by its \p hash
+ and returns \p true if it is found, or \p false otherwise.
+ */
+ bool contains( hash_type const& hash )
+ {
+ return base_class::contains( hash );
+ }
+
+ /// Finds an item by it's \p hash and returns the item found
+ /**
+ The function searches the item by its \p hash
+ and returns the pointer to the item found.
+ If \p hash is not found the function returns \p nullptr.
+
+ RCU should be locked before the function invocation.
+ Returned pointer is valid only while RCU is locked.
+
+ Usage:
+ \code
+ typedef cds::container::FeldmanHashSet< your_template_params > my_set;
+ my_set theSet;
+ // ...
+ {
+ // lock RCU
+ my_set::rcu_lock;
+
+ foo * p = theSet.get( 5 );
+ if ( p ) {
+ // Deal with p
+ //...
+ }
+ }
+ \endcode
+ */
+ value_type * get( hash_type const& hash )
+ {
+ return base_class::get( hash );
+ }
+
+ /// Clears the set (non-atomic)
+ /**
+ The function unlink all data node from the set.
+ The function is not atomic but is thread-safe.
+ After \p %clear() the set may not be empty because another threads may insert items.
+ */
+ void clear()
+ {
+ base_class::clear();
+ }
+
+ /// Checks if the set is empty
+ /**
+ Emptiness is checked by item counting: if item count is zero then the set is empty.
+ Thus, the correct item counting feature is an important part of the set implementation.
+ */
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Returns item count in the set
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+
+ /// Returns the size of head node
+ size_t head_size() const
+ {
+ return base_class::head_size();
+ }
+
+ /// Returns the size of the array node
+ size_t array_node_size() const
+ {
+ return base_class::array_node_size();
+ }
+
+ public:
+ ///@name Thread-safe iterators
+ /** @anchor cds_container_FeldmanHashSet_rcu_iterators
+ The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment
+ under explicit RCU lock.
+ RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
+ since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
+ while your thread is iterating.
+
+ A typical example is:
+ \code
+ struct foo {
+ uint32_t hash;
+ // ... other fields
+ uint32_t payload; // only for example
+ };
+ struct set_traits: cds::container::feldman_hashset::traits
+ {
+ struct hash_accessor {
+ uint32_t operator()( foo const& src ) const
+ {
+ retur src.hash;
+ }
+ };
+ };
+
+ typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
+ typedef cds::container::FeldmanHashSet< rcu, foo, set_traits > set_type;
+
+ set_type s;
+
+ // ...
+
+ // iterate over the set
+ {
+ // lock the RCU.
+ typename set_type::rcu_lock l; // scoped RCU lock
+
+ // traverse the set
+ for ( auto i = s.begin(); i != s.end(); ++i ) {
+ // deal with i. Remember, erasing is prohibited here!
+ i->payload++;
+ }
+ } // at this point RCU lock is released
+ /endcode
+
+ Each iterator object supports the common interface:
+ - dereference operators:
+ @code
+ value_type [const] * operator ->() noexcept
+ value_type [const] & operator *() noexcept
+ @endcode
+ - pre-increment and pre-decrement. Post-operators is not supported
+ - equality operators <tt>==</tt> and <tt>!=</tt>.
+ Iterators are equal iff they point to the same cell of the same array node.
+ Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
+ does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
+
+ @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
+ in an array node that is being splitted.
+ */
+ ///@{
+
+ /// Returns an iterator to the beginning of the set
+ iterator begin()
+ {
+ return base_class::begin();
+ }
+
+ /// Returns an const iterator to the beginning of the set
+ const_iterator begin() const
+ {
+ return base_class::begin();
+ }
+
+ /// Returns an const iterator to the beginning of the set
+ const_iterator cbegin()
+ {
+ return base_class::cbegin();
+ }
+
+ /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ iterator end()
+ {
+ return base_class::end();
+ }
+
+ /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator end() const
+ {
+ return base_class::end();
+ }
+
+ /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator cend()
+ {
+ return base_class::cend();
+ }
+
+ /// Returns a reverse iterator to the first element of the reversed set
+ reverse_iterator rbegin()
+ {
+ return base_class::rbegin();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed set
+ const_reverse_iterator rbegin() const
+ {
+ return base_class::rbegin();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed set
+ const_reverse_iterator crbegin()
+ {
+ return base_class::crbegin();
+ }
+
+ /// Returns a reverse iterator to the element following the last element of the reversed set
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ reverse_iterator rend()
+ {
+ return base_class::rend();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed set
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator rend() const
+ {
+ return base_class::rend();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed set
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator crend()
+ {
+ return base_class::crend();
+ }
+ ///@}
+ };
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHSET_RCU_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
+#define CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
+
+#include <cds/intrusive/impl/feldman_hashset.h>
+#include <cds/container/details/feldman_hashmap_base.h>
+#include <cds/container/details/guarded_ptr_cast.h>
+
+namespace cds { namespace container {
+
+ /// Hash map based on multi-level array
+ /** @ingroup cds_nonintrusive_map
+ @anchor cds_container_FeldmanHashMap_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 %FeldmanHashSet 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 <b>perfect hashing</b>, 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 %FeldmanHashMap is a multi-level array which has an internal structure similar to a tree:
+ @image html feldman_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 %FeldmanHashMap 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 map uses an extensible hashing scheme; <b> the hash value is treated as a bit
+ string</b> and rehash incrementally.
+
+ @note Two important things you should keep in mind when you're using \p %FeldmanHashMap:
+ - 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 %FeldmanHashMap,
+ but real key in the map will be fixed-size hash values of your keys.
+ For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
+ converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %FeldmanHashMap.
+ If your key is fixed-sized the hash functor is optional, see \p feldman_hashmap::traits::hash for explanation and examples.
+ - \p %FeldmanHashMap 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 map. \p %FeldmanHashMap does not maintain the key,
+ it maintains its fixed-size hash value.
+
+ The map supports @ref cds_container_FeldmanHashMap_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 feldman_hashmap::traits or result of \p feldman_hashmap::make_traits metafunction.
+
+ There are several specializations of \p %FeldmanHashMap for each \p GC. You should include:
+ - <tt><cds/container/feldman_hashmap_hp.h></tt> for \p gc::HP garbage collector
+ - <tt><cds/container/feldman_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
+ - <tt><cds/container/feldman_hashmap_rcu.h></tt> for \ref cds_intrusive_FeldmanHashMap_rcu "RCU type". RCU specialization
+ has a slightly different interface.
+ */
+ template <
+ class GC
+ ,typename Key
+ ,typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ ,class Traits = feldman_hashmap::traits
+#else
+ ,class Traits
+#endif
+ >
+ class FeldmanHashMap
+#ifdef CDS_DOXYGEN_INVOKED
+ : protected cds::intrusive::FeldmanHashSet< GC, std::pair<Key const, T>, Traits >
+#else
+ : protected cds::container::details::make_feldman_hashmap< GC, Key, T, Traits >::type
+#endif
+ {
+ //@cond
+ typedef cds::container::details::make_feldman_hashmap< GC, Key, T, 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 feldman_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
+
+ /// 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;
+
+ template <bool IsConst>
+ class bidirectional_iterator: public base_class::iterator_base
+ {
+ friend class FeldmanHashMap;
+ typedef typename base_class::iterator_base iterator_base;
+
+ protected:
+ static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
+
+ public:
+ typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
+
+ public:
+ bidirectional_iterator() CDS_NOEXCEPT
+ {}
+
+ bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ : iterator_base( rhs )
+ {}
+
+ bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ {
+ iterator_base::operator=( rhs );
+ return *this;
+ }
+
+ bidirectional_iterator& operator++()
+ {
+ iterator_base::operator++();
+ return *this;
+ }
+
+ bidirectional_iterator& operator--()
+ {
+ iterator_base::operator--();
+ return *this;
+ }
+
+ value_ptr operator ->() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ return p ? &p->m_Value : nullptr;
+ }
+
+ value_ref operator *() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ assert( p );
+ return p->m_Value;
+ }
+
+ void release()
+ {
+ iterator_base::release();
+ }
+
+ template <bool IsConst2>
+ 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
+ {
+ return !( *this == rhs );
+ }
+
+ public: // for internal use only!
+ bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
+ : iterator_base( set, pNode, idx, false )
+ {}
+
+ bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
+ : iterator_base( set, pNode, idx )
+ {}
+ };
+
+ /// Reverse bidirectional iterator
+ template <bool IsConst>
+ class reverse_bidirectional_iterator : public base_class::iterator_base
+ {
+ friend class FeldmanHashMap;
+ typedef typename base_class::iterator_base iterator_base;
+
+ public:
+ typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
+ typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
+
+ public:
+ reverse_bidirectional_iterator() CDS_NOEXCEPT
+ : iterator_base()
+ {}
+
+ reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
+ : iterator_base( rhs )
+ {}
+
+ reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
+ {
+ iterator_base::operator=( rhs );
+ return *this;
+ }
+
+ reverse_bidirectional_iterator& operator++()
+ {
+ iterator_base::operator--();
+ return *this;
+ }
+
+ reverse_bidirectional_iterator& operator--()
+ {
+ iterator_base::operator++();
+ return *this;
+ }
+
+ value_ptr operator ->() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ return p ? &p->m_Value : nullptr;
+ }
+
+ value_ref operator *() const CDS_NOEXCEPT
+ {
+ node_type * p = iterator_base::pointer();
+ assert( p );
+ return p->m_Value;
+ }
+
+ void release()
+ {
+ iterator_base::release();
+ }
+
+ template <bool IsConst2>
+ 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)
+ {
+ return !( *this == rhs );
+ }
+
+ public: // for internal use only!
+ reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
+ : iterator_base( set, pNode, idx, false )
+ {}
+
+ reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
+ : iterator_base( set, pNode, idx, false )
+ {
+ iterator_base::backward();
+ }
+ };
+
+ //@endcond
+
+ public:
+#ifdef CDS_DOXYGEN_INVOKED
+ /// Guarded pointer
+ typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
+#else
+ typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+#endif
+
+#ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional iterator" type
+ typedef implementation_defined const_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional const iterator" type
+ typedef implementation_defined reverse_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional reverse iterator" type
+ typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional reverse const iterator" type
+#else
+ typedef bidirectional_iterator<false> iterator;
+ typedef bidirectional_iterator<true> const_iterator;
+ typedef reverse_bidirectional_iterator<false> reverse_iterator;
+ typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
+#endif
+
+ protected:
+ //@cond
+ hasher m_Hasher;
+ //@endcond
+
+ public:
+ /// Creates empty map
+ /**
+ @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
+ @param array_bits: 2<sup>array_bits</sup> 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.
+ */
+ FeldmanHashMap( size_t head_bits = 8, size_t array_bits = 4 )
+ : base_class( head_bits, array_bits )
+ {}
+
+ /// Destructs the map and frees all data
+ ~FeldmanHashMap()
+ {}
+
+ /// 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 <typename K>
+ bool insert( 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;
+ }
+ 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 map, \p false otherwise.
+ */
+ 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)));
+ 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:
+ - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
+ - <tt>item.second</tt> 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 <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)));
+ 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 <tt>std::forward<Args>(args)...</tt>
+ /**
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ 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)... ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Updates data by \p key
+ /**
+ The operation performs inserting or replacing the element 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, it is replaced with a new item created from
+ \p key.
+ The functor \p Func signature:
+ \code
+ struct my_functor {
+ void operator()( value_type& item, value_type * old );
+ };
+ \endcode
+ where:
+ - \p item - item of the map
+ - \p old - old item of the map, if \p nullptr - the new item was inserted
+
+ 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,
+ \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)));
+ 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 );
+ 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.
+ The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
+
+ Return \p true if \p key is found and deleted, \p false otherwise.
+ */
+ template <typename K>
+ bool erase( K const& key )
+ {
+ return base_class::erase( m_Hasher( key_type( key )));
+ }
+
+ /// Delete \p key from the map
+ /**
+ The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
+ 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
+ where \p item is the element found.
+
+ \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 <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 ); } );
+ }
+
+ /// 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 )
+ {
+ return base_class::do_erase_at( iter );
+ }
+ //@cond
+ bool erase_at( reverse_iterator const& iter )
+ {
+ return base_class::do_erase_at( iter );
+ }
+ //@endcond
+
+ /// Extracts the item from the map with specified \p key
+ /**
+ The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
+ unlinks it from the map, and returns a guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
+
+ The item extracted is freed automatically by garbage collector \p GC
+ when returned \p guarded_ptr object will be destroyed or released.
+ @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::container::FeldmanHashMap< cds::gc::HP, int, foo, my_traits > map_type;
+ map_type theMap;
+ // ...
+ {
+ map_type::guarded_ptr gp( theMap.extract( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ // ...
+ }
+ // Destructor of gp releases internal HP guard and frees the pointer
+ }
+ \endcode
+ */
+ 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;
+ }
+
+ /// Checks whether the map contains \p key
+ /**
+ The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
+ and returns \p true if it is found, or \p false otherwise.
+ */
+ template <typename K>
+ bool contains( K const& key )
+ {
+ return base_class::contains( m_Hasher( key_type( key )) );
+ }
+
+ /// Find the key \p key
+ /**
+
+ The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
+ and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+
+ The functor may change \p item.second.
+
+ The function returns \p true if \p key is found, \p false otherwise.
+ */
+ 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 );});
+ }
+
+ /// Finds the key \p key and return the item found
+ /**
+ The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
+ and returns a guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
+
+ It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
+ In this case the item will be freed later by garbage collector \p GC automatically
+ when \p guarded_ptr object will be destroyed or released.
+ @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::container::FeldmanHashMap< cds::gc::HP, int, foo, my_traits > map_type;
+ map_type theMap;
+ // ...
+ {
+ map_type::guarded_ptr gp( theMap.get( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ //...
+ }
+ // Destructor of guarded_ptr releases internal HP guard
+ }
+ \endcode
+ */
+ 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;
+ }
+
+ /// Clears the map (non-atomic)
+ /**
+ The function unlink all data node from the map.
+ The function is not atomic but is thread-safe.
+ After \p %clear() the map may not be empty because another threads may insert items.
+ */
+ void clear()
+ {
+ base_class::clear();
+ }
+
+ /// Checks if the map is empty
+ /**
+ Emptiness is checked by item counting: if item count is zero then the map is empty.
+ Thus, the correct item counting feature is an important part of the map implementation.
+ */
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Returns item count in the map
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+
+ /// Returns the size of head node
+ size_t head_size() const
+ {
+ return base_class::head_size();
+ }
+
+ /// Returns the size of the array node
+ size_t array_node_size() const
+ {
+ return base_class::array_node_size();
+ }
+
+ public:
+ ///@name Thread-safe iterators
+ /** @anchor cds_container_FeldmanHashMap_iterators
+ The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
+ It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
+ Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
+
+ @note Since the iterator object contains hazard pointer that is a thread-local resource,
+ the iterator should not be passed to another thread.
+
+ Each iterator object supports the common interface:
+ - dereference operators:
+ @code
+ value_type [const] * operator ->() noexcept
+ value_type [const] & operator *() noexcept
+ @endcode
+ - pre-increment and pre-decrement. Post-operators is not supported
+ - equality operators <tt>==</tt> and <tt>!=</tt>.
+ Iterators are equal iff they point to the same cell of the same array node.
+ Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
+ does not entail <tt> &(*it1) == &(*it2) </tt>
+ - helper member function \p release() that clears internal hazard pointer.
+ After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
+
+ During iteration you may safely erase any item from the set;
+ @ref erase_at() function call doesn't invalidate any iterator.
+ If some iterator points to the item to be erased, that item is not deleted immediately
+ but only after that iterator will be advanced forward or backward.
+
+ @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
+ in array node that is being splitted.
+ */
+ ///@{
+ /// Returns an iterator to the beginning of the map
+ iterator begin()
+ {
+ return base_class::template init_begin<iterator>();
+ }
+
+ /// Returns an const iterator to the beginning of the map
+ const_iterator begin() const
+ {
+ return base_class::template init_begin<const_iterator>();
+ }
+
+ /// Returns an const iterator to the beginning of the map
+ const_iterator cbegin()
+ {
+ return base_class::template init_begin<const_iterator>();
+ }
+
+ /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ iterator end()
+ {
+ return base_class::template init_end<iterator>();
+ }
+
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator end() const
+ {
+ return base_class::template init_end<const_iterator>();
+ }
+
+ /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator cend()
+ {
+ return base_class::template init_end<const_iterator>();
+ }
+
+ /// Returns a reverse iterator to the first element of the reversed map
+ reverse_iterator rbegin()
+ {
+ return base_class::template init_rbegin<reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed map
+ const_reverse_iterator rbegin() const
+ {
+ return base_class::template init_rbegin<const_reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed map
+ const_reverse_iterator crbegin()
+ {
+ return base_class::template init_rbegin<const_reverse_iterator>();
+ }
+
+ /// Returns a reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ reverse_iterator rend()
+ {
+ return base_class::template init_rend<reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator rend() const
+ {
+ return base_class::template init_rend<const_reverse_iterator>();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed map
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator crend()
+ {
+ return base_class::template init_rend<const_reverse_iterator>();
+ }
+ ///@}
+ };
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHSET_H
+#define CDSLIB_CONTAINER_IMPL_FELDMAN_HASHSET_H
+
+#include <cds/intrusive/impl/feldman_hashset.h>
+#include <cds/container/details/feldman_hashset_base.h>
+
+namespace cds { namespace container {
+
+ /// Hash set based on multi-level array
+ /** @ingroup cds_nonintrusive_set
+ @anchor cds_container_FeldmanHashSet_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 %FeldmanHashSet 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 <b>perfect hashing</b>, 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 %FeldmanHashSet is a multi-level array which has an internal structure similar to a tree:
+ @image html feldman_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 %FeldmanHashSet 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; <b> the hash value is treated as a bit
+ string</b> and rehash incrementally.
+
+ @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
+ - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
+ Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
+ <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
+ or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
+ converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %FeldmanHashSet.
+ - \p %FeldmanHashSet 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 %FeldmanHashSet does not maintain the key,
+ it maintains its fixed-size hash value.
+
+ The set supports @ref cds_container_FeldmanHashSet_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 T - a value type to be stored in the set
+ - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
+ \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
+ to hash value of \p T. The set algorithm does not calculate that hash value.
+
+ There are several specializations of \p %FeldmanHashSet for each \p GC. You should include:
+ - <tt><cds/container/feldman_hashset_hp.h></tt> for \p gc::HP garbage collector
+ - <tt><cds/container/feldman_hashset_dhp.h></tt> for \p gc::DHP garbage collector
+ - <tt><cds/container/feldman_hashset_rcu.h></tt> for \ref cds_intrusive_FeldmanHashSet_rcu "RCU type". RCU specialization
+ has a slightly different interface.
+ */
+ template <
+ class GC
+ , typename T
+#ifdef CDS_DOXYGEN_INVOKED
+ , class Traits = feldman_hashset::traits
+#else
+ , class Traits
+#endif
+ >
+ class FeldmanHashSet
+#ifdef CDS_DOXYGEN_INVOKED
+ : protected cds::intrusive::FeldmanHashSet< GC, T, Traits >
+#else
+ : protected cds::container::details::make_feldman_hashset< GC, T, Traits >::type
+#endif
+ {
+ //@cond
+ typedef cds::container::details::make_feldman_hashset< GC, T, Traits > maker;
+ typedef typename maker::type base_class;
+ //@endcond
+
+ public:
+ typedef GC gc; ///< Garbage collector
+ typedef T value_type; ///< type of value stored in the set
+ typedef Traits traits; ///< Traits template parameter, see \p feldman_hashset::traits
+
+ typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
+ typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
+ typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
+
+ 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;
+
+ typedef typename base_class::iterator iterator; ///< @ref cds_container_FeldmanHashSet_iterators "bidirectional iterator" type
+ typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_FeldmanHashSet_iterators "bidirectional const iterator" type
+ typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_FeldmanHashSet_iterators "bidirectional reverse iterator" type
+ typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
+
+ protected:
+ //@cond
+ typedef typename maker::cxx_node_allocator cxx_node_allocator;
+ typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
+ //@endcond
+
+ public:
+ /// Creates empty set
+ /**
+ @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
+ @param array_bits: 2<sup>array_bits</sup> 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.
+ */
+ FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
+ : base_class( head_bits, array_bits )
+ {}
+
+ /// Destructs the set and frees all data
+ ~FeldmanHashSet()
+ {}
+
+ /// Inserts new element
+ /**
+ The function creates an element with copy of \p val value and then inserts it into the set.
+
+ The type \p Q should contain as minimum the complete hash for the element.
+ The object of \ref value_type should be constructible from a value of type \p Q.
+ In trivial case, \p Q is equal to \ref value_type.
+
+ Returns \p true if \p val is inserted into the set, \p false otherwise.
+ */
+ template <typename Q>
+ bool insert( Q const& val )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( val ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Inserts new element
+ /**
+ The function allows to split creating of new item into two part:
+ - create item with key only
+ - insert new item into the set
+ - if inserting is success, calls \p f functor to initialize value-fields of \p val.
+
+ The functor signature is:
+ \code
+ void func( value_type& val );
+ \endcode
+ where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
+ \p val no any other changes could be made on this set's item by concurrent threads.
+ The user-defined functor is called only if the inserting is success.
+ */
+ template <typename Q, typename Func>
+ bool insert( Q const& val, Func f )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( val ));
+ if ( base_class::insert( *sp, f )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Updates the element
+ /**
+ The operation performs inserting or replacing with lock-free manner.
+
+ If the \p val key not found in the set, then the new item created from \p val
+ will be inserted into the set iff \p bInsert is \p true.
+ Otherwise, if \p val is found, it is replaced with new item created from \p val
+ and previous item is disposed.
+ In both cases \p func functor is called.
+
+ The functor \p Func signature:
+ \code
+ struct my_functor {
+ void operator()( value_type& cur, value_type * prev );
+ };
+ \endcode
+ where:
+ - \p cur - current element
+ - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
+ if \p cur was just inserted.
+
+ The functor may change non-key fields of the \p item; however, \p func must guarantee
+ that during changing no any other modifications could be made on this item by concurrent threads.
+
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ i.e. the item has been inserted or updated,
+ \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
+ already exists.
+ */
+ template <typename Q, typename Func>
+ std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( val ));
+ std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
+ if ( bRes.first )
+ sp.release();
+ return bRes;
+ }
+
+ /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
+ /**
+ Returns \p true if inserting successful, \p false otherwise.
+ */
+ template <typename... Args>
+ bool emplace( Args&&... args )
+ {
+ scoped_node_ptr sp( cxx_node_allocator().New( std::forward<Args>(args)... ));
+ if ( base_class::insert( *sp )) {
+ sp.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Deletes the item from the set
+ /**
+ The function searches \p hash in the set,
+ deletes the item found, and returns \p true.
+ If that item is not found the function returns \p false.
+ */
+ bool erase( hash_type const& hash )
+ {
+ return base_class::erase( hash );
+ }
+
+ /// Deletes the item from the set
+ /**
+ The function searches \p hash in the set,
+ call \p f functor with item found, and deltes the element from the set.
+
+ The \p Func interface is
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+
+ If \p hash is not found the function returns \p false.
+ */
+ template <typename Func>
+ bool erase( hash_type const& hash, Func f )
+ {
+ return base_class::erase( hash, f );
+ }
+
+ /// 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& iter )
+ {
+ return base_class::erase_at( iter );
+ }
+ //@cond
+ bool erase_at( reverse_iterator const& iter )
+ {
+ return base_class::erase_at( iter );
+ }
+ //@endcond
+
+ /// Extracts the item with specified \p hash
+ /**
+ The function searches \p hash in the set,
+ unlinks it from the set, and returns a guarded pointer to the item extracted.
+ If \p hash is not found the function returns an empty guarded pointer.
+
+ The item returned is reclaimed by garbage collector \p GC
+ when returned \ref guarded_ptr object to be destroyed or released.
+ @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::container::FeldmanHashSet< your_template_args > my_set;
+ my_set theSet;
+ // ...
+ {
+ my_set::guarded_ptr gp( theSet.extract( 5 ));
+ if ( gp ) {
+ // Deal with gp
+ // ...
+ }
+ // Destructor of gp releases internal HP guard
+ }
+ \endcode
+ */
+ guarded_ptr extract( hash_type const& hash )
+ {
+ return base_class::extract( hash );
+ }
+
+ /// Finds an item by it's \p hash
+ /**
+ The function searches the item by \p hash and calls the functor \p f for item found.
+ The interface of \p Func functor is:
+ \code
+ struct functor {
+ void operator()( value_type& item );
+ };
+ \endcode
+ where \p item is the item found.
+
+ The functor may change non-key fields of \p item. Note that the functor is only guarantee
+ that \p item cannot be disposed during the functor is executing.
+ The functor does not serialize simultaneous access to the set's \p item. If such access is
+ possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
+
+ The function returns \p true if \p hash is found, \p false otherwise.
+ */
+ template <typename Func>
+ bool find( hash_type const& hash, Func f )
+ {
+ return base_class::find( hash, f );
+ }
+
+ /// Checks whether the set contains \p hash
+ /**
+ The function searches the item by its \p hash
+ and returns \p true if it is found, or \p false otherwise.
+ */
+ bool contains( hash_type const& hash )
+ {
+ return base_class::contains( hash );
+ }
+
+ /// Finds an item by it's \p hash and returns the item found
+ /**
+ The function searches the item by its \p hash
+ and returns the guarded pointer to the item found.
+ If \p hash is not found the function returns an empty \p guarded_ptr.
+
+ @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
+
+ Usage:
+ \code
+ typedef cds::container::FeldmanHashSet< your_template_params > my_set;
+ my_set theSet;
+ // ...
+ {
+ my_set::guarded_ptr gp( theSet.get( 5 ));
+ if ( theSet.get( 5 )) {
+ // Deal with gp
+ //...
+ }
+ // Destructor of guarded_ptr releases internal HP guard
+ }
+ \endcode
+ */
+ guarded_ptr get( hash_type const& hash )
+ {
+ return base_class::get( hash );
+ }
+
+ /// Clears the set (non-atomic)
+ /**
+ The function unlink all data node from the set.
+ The function is not atomic but is thread-safe.
+ After \p %clear() the set may not be empty because another threads may insert items.
+ */
+ void clear()
+ {
+ base_class::clear();
+ }
+
+ /// Checks if the set is empty
+ /**
+ Emptiness is checked by item counting: if item count is zero then the set is empty.
+ Thus, the correct item counting feature is an important part of the set implementation.
+ */
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Returns item count in the set
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+
+ /// Returns the size of head node
+ size_t head_size() const
+ {
+ return base_class::head_size();
+ }
+
+ /// Returns the size of the array node
+ size_t array_node_size() const
+ {
+ return base_class::array_node_size();
+ }
+
+ public:
+ ///@name Thread-safe iterators
+ /** @anchor cds_container_FeldmanHashSet_iterators
+ The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
+ It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
+ Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
+
+ @note Since the iterator object contains hazard pointer that is a thread-local resource,
+ the iterator should not be passed to another thread.
+
+ Each iterator object supports the common interface:
+ - dereference operators:
+ @code
+ value_type [const] * operator ->() noexcept
+ value_type [const] & operator *() noexcept
+ @endcode
+ - pre-increment and pre-decrement. Post-operators is not supported
+ - equality operators <tt>==</tt> and <tt>!=</tt>.
+ Iterators are equal iff they point to the same cell of the same array node.
+ Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
+ does not entail <tt> &(*it1) == &(*it2) </tt>
+ - helper member function \p release() that clears internal hazard pointer.
+ After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
+
+ During iteration you may safely erase any item from the set;
+ @ref erase_at() function call doesn't invalidate any iterator.
+ If some iterator points to the item to be erased, that item is not deleted immediately
+ but only after that iterator will be advanced forward or backward.
+
+ @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
+ in array node that is being splitted.
+ */
+ ///@{
+
+ /// Returns an iterator to the beginning of the set
+ iterator begin()
+ {
+ return base_class::begin();
+ }
+
+ /// Returns an const iterator to the beginning of the set
+ const_iterator begin() const
+ {
+ return base_class::begin();
+ }
+
+ /// Returns an const iterator to the beginning of the set
+ const_iterator cbegin()
+ {
+ return base_class::cbegin();
+ }
+
+ /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ iterator end()
+ {
+ return base_class::end();
+ }
+
+ /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator end() const
+ {
+ return base_class::end();
+ }
+
+ /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
+ const_iterator cend()
+ {
+ return base_class::cend();
+ }
+
+ /// Returns a reverse iterator to the first element of the reversed set
+ reverse_iterator rbegin()
+ {
+ return base_class::rbegin();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed set
+ const_reverse_iterator rbegin() const
+ {
+ return base_class::rbegin();
+ }
+
+ /// Returns a const reverse iterator to the first element of the reversed set
+ const_reverse_iterator crbegin()
+ {
+ return base_class::crbegin();
+ }
+
+ /// Returns a reverse iterator to the element following the last element of the reversed set
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ reverse_iterator rend()
+ {
+ return base_class::rend();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed set
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator rend() const
+ {
+ return base_class::rend();
+ }
+
+ /// Returns a const reverse iterator to the element following the last element of the reversed set
+ /**
+ It corresponds to the element preceding the first element of the non-reversed container.
+ This element acts as a placeholder, attempting to access it results in undefined behavior.
+ */
+ const_reverse_iterator crend()
+ {
+ return base_class::crend();
+ }
+ ///@}
+ };
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHSET_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
-#define CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
-
-#include <cds/intrusive/impl/multilevel_hashset.h>
-#include <cds/container/details/multilevel_hashmap_base.h>
-#include <cds/container/details/guarded_ptr_cast.h>
-
-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 <b>perfect hashing</b>, 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 map uses an extensible hashing scheme; <b> the hash value is treated as a bit
- string</b> 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-size hash values of your keys.
- For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
- converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.
- If your key is fixed-sized the hash functor is optional, see \p multilevel_hashmap::traits::hash for explanation and examples.
- - \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 map. \p %MultiLevelHashMap does not maintain the key,
- it maintains its fixed-size hash value.
-
- The map 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:
- - <tt><cds/container/multilevel_hashmap_hp.h></tt> for \p gc::HP garbage collector
- - <tt><cds/container/multilevel_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
- - <tt><cds/container/multilevel_hashmap_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashMap_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<Key const, T>, Traits >
-#else
- : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits >::type
-#endif
- {
- //@cond
- typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, 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
-
- /// 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;
-
- template <bool IsConst>
- class bidirectional_iterator: public base_class::iterator_base
- {
- friend class MultiLevelHashMap;
- typedef typename base_class::iterator_base iterator_base;
-
- protected:
- static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
-
- public:
- typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
- typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
-
- public:
- bidirectional_iterator() CDS_NOEXCEPT
- {}
-
- bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
- : iterator_base( rhs )
- {}
-
- bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
- {
- iterator_base::operator=( rhs );
- return *this;
- }
-
- bidirectional_iterator& operator++()
- {
- iterator_base::operator++();
- return *this;
- }
-
- bidirectional_iterator& operator--()
- {
- iterator_base::operator--();
- return *this;
- }
-
- value_ptr operator ->() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- return p ? &p->m_Value : nullptr;
- }
-
- value_ref operator *() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- assert( p );
- return p->m_Value;
- }
-
- void release()
- {
- iterator_base::release();
- }
-
- template <bool IsConst2>
- 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
- {
- return !( *this == rhs );
- }
-
- public: // for internal use only!
- bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
- : iterator_base( set, pNode, idx, false )
- {}
-
- bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
- : iterator_base( set, pNode, idx )
- {}
- };
-
- /// Reverse bidirectional iterator
- template <bool IsConst>
- class reverse_bidirectional_iterator : public base_class::iterator_base
- {
- friend class MultiLevelHashMap;
- typedef typename base_class::iterator_base iterator_base;
-
- public:
- typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
- typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
-
- public:
- reverse_bidirectional_iterator() CDS_NOEXCEPT
- : iterator_base()
- {}
-
- reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
- : iterator_base( rhs )
- {}
-
- reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
- {
- iterator_base::operator=( rhs );
- return *this;
- }
-
- reverse_bidirectional_iterator& operator++()
- {
- iterator_base::operator--();
- return *this;
- }
-
- reverse_bidirectional_iterator& operator--()
- {
- iterator_base::operator++();
- return *this;
- }
-
- value_ptr operator ->() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- return p ? &p->m_Value : nullptr;
- }
-
- value_ref operator *() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- assert( p );
- return p->m_Value;
- }
-
- void release()
- {
- iterator_base::release();
- }
-
- template <bool IsConst2>
- 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)
- {
- return !( *this == rhs );
- }
-
- public: // for internal use only!
- reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
- : iterator_base( set, pNode, idx, false )
- {}
-
- reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
- : iterator_base( set, pNode, idx, false )
- {
- iterator_base::backward();
- }
- };
-
- //@endcond
-
- public:
-#ifdef CDS_DOXYGEN_INVOKED
- /// Guarded pointer
- typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
-#else
- typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
-#endif
-
-#ifdef CDS_DOXYGEN_INVOKED
- typedef implementation_defined iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional iterator" type
- typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional const iterator" type
- typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse iterator" type
- typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse const iterator" type
-#else
- typedef bidirectional_iterator<false> iterator;
- typedef bidirectional_iterator<true> const_iterator;
- typedef reverse_bidirectional_iterator<false> reverse_iterator;
- typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
-#endif
-
- protected:
- //@cond
- hasher m_Hasher;
- //@endcond
-
- public:
- /// Creates empty map
- /**
- @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
- @param array_bits: 2<sup>array_bits</sup> 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 <typename K>
- bool insert( 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;
- }
- 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 map, \p false otherwise.
- */
- 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)));
- 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:
- - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
- - <tt>item.second</tt> 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 <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)));
- 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 <tt>std::forward<Args>(args)...</tt>
- /**
- Returns \p true if inserting successful, \p false otherwise.
- */
- 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)... ));
- if ( base_class::insert( *sp )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Updates data by \p key
- /**
- The operation performs inserting or replacing the element 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, it is replaced with a new item created from
- \p key.
- The functor \p Func signature:
- \code
- struct my_functor {
- void operator()( value_type& item, value_type * old );
- };
- \endcode
- where:
- - \p item - item of the map
- - \p old - old item of the map, if \p nullptr - the new item was inserted
-
- 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,
- \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)));
- 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 );
- 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.
- The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
-
- Return \p true if \p key is found and deleted, \p false otherwise.
- */
- template <typename K>
- bool erase( K const& key )
- {
- return base_class::erase( m_Hasher( key_type( key )));
- }
-
- /// Delete \p key from the map
- /**
- The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
- 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
- where \p item is the element found.
-
- \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 <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 ); } );
- }
-
- /// 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 )
- {
- return base_class::do_erase_at( iter );
- }
- //@cond
- bool erase_at( reverse_iterator const& iter )
- {
- return base_class::do_erase_at( iter );
- }
- //@endcond
-
- /// Extracts the item from the map with specified \p key
- /**
- The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
- unlinks it from the map, and returns a guarded pointer to the item found.
- If \p key is not found the function returns an empty guarded pointer.
-
- The item extracted is freed automatically by garbage collector \p GC
- when returned \p guarded_ptr object will be destroyed or released.
- @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
-
- Usage:
- \code
- typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
- map_type theMap;
- // ...
- {
- map_type::guarded_ptr gp( theMap.extract( 5 ));
- if ( gp ) {
- // Deal with gp
- // ...
- }
- // Destructor of gp releases internal HP guard and frees the pointer
- }
- \endcode
- */
- 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;
- }
-
- /// Checks whether the map contains \p key
- /**
- The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
- and returns \p true if it is found, or \p false otherwise.
- */
- template <typename K>
- bool contains( K const& key )
- {
- return base_class::contains( m_Hasher( key_type( key )) );
- }
-
- /// Find the key \p key
- /**
-
- The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
- and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item );
- };
- \endcode
- where \p item is the item found.
-
- The functor may change \p item.second.
-
- The function returns \p true if \p key is found, \p false otherwise.
- */
- 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 );});
- }
-
- /// Finds the key \p key and return the item found
- /**
- The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
- and returns a guarded pointer to the item found.
- If \p key is not found the function returns an empty guarded pointer.
-
- It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
- In this case the item will be freed later by garbage collector \p GC automatically
- when \p guarded_ptr object will be destroyed or released.
- @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
-
- Usage:
- \code
- typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
- map_type theMap;
- // ...
- {
- map_type::guarded_ptr gp( theMap.get( 5 ));
- if ( gp ) {
- // Deal with gp
- //...
- }
- // Destructor of guarded_ptr releases internal HP guard
- }
- \endcode
- */
- 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;
- }
-
- /// Clears the map (non-atomic)
- /**
- The function unlink all data node from the map.
- The function is not atomic but is thread-safe.
- After \p %clear() the map may not be empty because another threads may insert items.
- */
- void clear()
- {
- base_class::clear();
- }
-
- /// Checks if the map is empty
- /**
- Emptiness is checked by item counting: if item count is zero then the map is empty.
- Thus, the correct item counting feature is an important part of the map implementation.
- */
- bool empty() const
- {
- return base_class::empty();
- }
-
- /// Returns item count in the map
- size_t size() const
- {
- return base_class::size();
- }
-
- /// Returns const reference to internal statistics
- stat const& statistics() const
- {
- return base_class::statistics();
- }
-
- /// Returns the size of head node
- size_t head_size() const
- {
- return base_class::head_size();
- }
-
- /// Returns the size of the array node
- size_t array_node_size() const
- {
- return base_class::array_node_size();
- }
-
- public:
- ///@name Thread-safe iterators
- /** @anchor cds_container_MultilevelHashMap_iterators
- The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
- It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
- Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
-
- @note Since the iterator object contains hazard pointer that is a thread-local resource,
- the iterator should not be passed to another thread.
-
- Each iterator object supports the common interface:
- - dereference operators:
- @code
- value_type [const] * operator ->() noexcept
- value_type [const] & operator *() noexcept
- @endcode
- - pre-increment and pre-decrement. Post-operators is not supported
- - equality operators <tt>==</tt> and <tt>!=</tt>.
- Iterators are equal iff they point to the same cell of the same array node.
- Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
- does not entail <tt> &(*it1) == &(*it2) </tt>
- - helper member function \p release() that clears internal hazard pointer.
- After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
-
- During iteration you may safely erase any item from the set;
- @ref erase_at() function call doesn't invalidate any iterator.
- If some iterator points to the item to be erased, that item is not deleted immediately
- but only after that iterator will be advanced forward or backward.
-
- @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
- in array node that is being splitted.
- */
- ///@{
- /// Returns an iterator to the beginning of the map
- iterator begin()
- {
- return base_class::template init_begin<iterator>();
- }
-
- /// Returns an const iterator to the beginning of the map
- const_iterator begin() const
- {
- return base_class::template init_begin<const_iterator>();
- }
-
- /// Returns an const iterator to the beginning of the map
- const_iterator cbegin()
- {
- return base_class::template init_begin<const_iterator>();
- }
-
- /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
- iterator end()
- {
- return base_class::template init_end<iterator>();
- }
-
- /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator end() const
- {
- return base_class::template init_end<const_iterator>();
- }
-
- /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator cend()
- {
- return base_class::template init_end<const_iterator>();
- }
-
- /// Returns a reverse iterator to the first element of the reversed map
- reverse_iterator rbegin()
- {
- return base_class::template init_rbegin<reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed map
- const_reverse_iterator rbegin() const
- {
- return base_class::template init_rbegin<const_reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed map
- const_reverse_iterator crbegin()
- {
- return base_class::template init_rbegin<const_reverse_iterator>();
- }
-
- /// Returns a reverse iterator to the element following the last element of the reversed map
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- reverse_iterator rend()
- {
- return base_class::template init_rend<reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed map
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator rend() const
- {
- return base_class::template init_rend<const_reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed map
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator crend()
- {
- return base_class::template init_rend<const_reverse_iterator>();
- }
- ///@}
- };
-
-}} // namespace cds::container
-
-#endif // #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHSET_H
-#define CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHSET_H
-
-#include <cds/intrusive/impl/multilevel_hashset.h>
-#include <cds/container/details/multilevel_hashset_base.h>
-
-namespace cds { namespace container {
-
- /// Hash set based on multi-level array
- /** @ingroup cds_nonintrusive_set
- @anchor cds_container_MultilevelHashSet_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 <b>perfect hashing</b>, 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 %MultiLevelHashSet 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 %MultiLevelHashSet 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; <b> the hash value is treated as a bit
- string</b> and rehash incrementally.
-
- @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:
- - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.
- Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
- converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.
- - \p %MultiLevelHashSet 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 %MultiLevelHashSet does not maintain the key,
- it maintains its fixed-size hash value.
-
- The set supports @ref cds_container_MultilevelHashSet_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 T - a value type to be stored in the set
- - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.
- \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor"
- to hash value of \p T. The set algorithm does not calculate that hash value.
-
- There are several specializations of \p %MultiLevelHashSet for each \p GC. You should include:
- - <tt><cds/container/multilevel_hashset_hp.h></tt> for \p gc::HP garbage collector
- - <tt><cds/container/multilevel_hashset_dhp.h></tt> for \p gc::DHP garbage collector
- - <tt><cds/container/multilevel_hashset_rcu.h></tt> for \ref cds_intrusive_MultilevelHashSet_rcu "RCU type". RCU specialization
- has a slightly different interface.
- */
- template <
- class GC
- , typename T
-#ifdef CDS_DOXYGEN_INVOKED
- , class Traits = multilevel_hashset::traits
-#else
- , class Traits
-#endif
- >
- class MultiLevelHashSet
-#ifdef CDS_DOXYGEN_INVOKED
- : protected cds::intrusive::MultiLevelHashSet< GC, T, Traits >
-#else
- : protected cds::container::details::make_multilevel_hashset< GC, T, Traits >::type
-#endif
- {
- //@cond
- typedef cds::container::details::make_multilevel_hashset< GC, T, Traits > maker;
- typedef typename maker::type base_class;
- //@endcond
-
- public:
- typedef GC gc; ///< Garbage collector
- typedef T value_type; ///< type of value stored in the set
- typedef Traits traits; ///< Traits template parameter, see \p multilevel_hashset::traits
-
- typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
- typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
- typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
-
- 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;
-
- typedef typename base_class::iterator iterator; ///< @ref cds_container_MultilevelHashSet_iterators "bidirectional iterator" type
- typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_MultilevelHashSet_iterators "bidirectional const iterator" type
- typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_MultilevelHashSet_iterators "bidirectional reverse iterator" type
- typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_MultilevelHashSet_iterators "bidirectional reverse const iterator" type
-
- protected:
- //@cond
- typedef typename maker::cxx_node_allocator cxx_node_allocator;
- typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
- //@endcond
-
- public:
- /// Creates empty set
- /**
- @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
- @param array_bits: 2<sup>array_bits</sup> 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.
- */
- MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
- : base_class( head_bits, array_bits )
- {}
-
- /// Destructs the set and frees all data
- ~MultiLevelHashSet()
- {}
-
- /// Inserts new element
- /**
- The function creates an element with copy of \p val value and then inserts it into the set.
-
- The type \p Q should contain as minimum the complete hash for the element.
- The object of \ref value_type should be constructible from a value of type \p Q.
- In trivial case, \p Q is equal to \ref value_type.
-
- Returns \p true if \p val is inserted into the set, \p false otherwise.
- */
- template <typename Q>
- bool insert( Q const& val )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( val ));
- if ( base_class::insert( *sp )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Inserts new element
- /**
- The function allows to split creating of new item into two part:
- - create item with key only
- - insert new item into the set
- - if inserting is success, calls \p f functor to initialize value-fields of \p val.
-
- The functor signature is:
- \code
- void func( value_type& val );
- \endcode
- where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
- \p val no any other changes could be made on this set's item by concurrent threads.
- The user-defined functor is called only if the inserting is success.
- */
- template <typename Q, typename Func>
- bool insert( Q const& val, Func f )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( val ));
- if ( base_class::insert( *sp, f )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Updates the element
- /**
- The operation performs inserting or replacing with lock-free manner.
-
- If the \p val key not found in the set, then the new item created from \p val
- will be inserted into the set iff \p bInsert is \p true.
- Otherwise, if \p val is found, it is replaced with new item created from \p val
- and previous item is disposed.
- In both cases \p func functor is called.
-
- The functor \p Func signature:
- \code
- struct my_functor {
- void operator()( value_type& cur, value_type * prev );
- };
- \endcode
- where:
- - \p cur - current element
- - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
- if \p cur was just inserted.
-
- The functor may change non-key fields of the \p item; however, \p func must guarantee
- that during changing no any other modifications could be made on this item by concurrent threads.
-
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
- i.e. the item has been inserted or updated,
- \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
- already exists.
- */
- template <typename Q, typename Func>
- std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( val ));
- std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
- if ( bRes.first )
- sp.release();
- return bRes;
- }
-
- /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
- /**
- Returns \p true if inserting successful, \p false otherwise.
- */
- template <typename... Args>
- bool emplace( Args&&... args )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( std::forward<Args>(args)... ));
- if ( base_class::insert( *sp )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Deletes the item from the set
- /**
- The function searches \p hash in the set,
- deletes the item found, and returns \p true.
- If that item is not found the function returns \p false.
- */
- bool erase( hash_type const& hash )
- {
- return base_class::erase( hash );
- }
-
- /// Deletes the item from the set
- /**
- The function searches \p hash in the set,
- call \p f functor with item found, and deltes the element from the set.
-
- The \p Func interface is
- \code
- struct functor {
- void operator()( value_type& item );
- };
- \endcode
-
- If \p hash is not found the function returns \p false.
- */
- template <typename Func>
- bool erase( hash_type const& hash, Func f )
- {
- return base_class::erase( hash, f );
- }
-
- /// 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& iter )
- {
- return base_class::erase_at( iter );
- }
- //@cond
- bool erase_at( reverse_iterator const& iter )
- {
- return base_class::erase_at( iter );
- }
- //@endcond
-
- /// Extracts the item with specified \p hash
- /**
- The function searches \p hash in the set,
- unlinks it from the set, and returns a guarded pointer to the item extracted.
- If \p hash is not found the function returns an empty guarded pointer.
-
- The item returned is reclaimed by garbage collector \p GC
- when returned \ref guarded_ptr object to be destroyed or released.
- @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
-
- Usage:
- \code
- typedef cds::container::MultiLevelHashSet< your_template_args > my_set;
- my_set theSet;
- // ...
- {
- my_set::guarded_ptr gp( theSet.extract( 5 ));
- if ( gp ) {
- // Deal with gp
- // ...
- }
- // Destructor of gp releases internal HP guard
- }
- \endcode
- */
- guarded_ptr extract( hash_type const& hash )
- {
- return base_class::extract( hash );
- }
-
- /// Finds an item by it's \p hash
- /**
- The function searches the item by \p hash and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item );
- };
- \endcode
- where \p item is the item found.
-
- The functor may change non-key fields of \p item. Note that the functor is only guarantee
- that \p item cannot be disposed during the functor is executing.
- The functor does not serialize simultaneous access to the set's \p item. If such access is
- possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
-
- The function returns \p true if \p hash is found, \p false otherwise.
- */
- template <typename Func>
- bool find( hash_type const& hash, Func f )
- {
- return base_class::find( hash, f );
- }
-
- /// Checks whether the set contains \p hash
- /**
- The function searches the item by its \p hash
- and returns \p true if it is found, or \p false otherwise.
- */
- bool contains( hash_type const& hash )
- {
- return base_class::contains( hash );
- }
-
- /// Finds an item by it's \p hash and returns the item found
- /**
- The function searches the item by its \p hash
- and returns the guarded pointer to the item found.
- If \p hash is not found the function returns an empty \p guarded_ptr.
-
- @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
-
- Usage:
- \code
- typedef cds::container::MultiLevelHashSet< your_template_params > my_set;
- my_set theSet;
- // ...
- {
- my_set::guarded_ptr gp( theSet.get( 5 ));
- if ( theSet.get( 5 )) {
- // Deal with gp
- //...
- }
- // Destructor of guarded_ptr releases internal HP guard
- }
- \endcode
- */
- guarded_ptr get( hash_type const& hash )
- {
- return base_class::get( hash );
- }
-
- /// Clears the set (non-atomic)
- /**
- The function unlink all data node from the set.
- The function is not atomic but is thread-safe.
- After \p %clear() the set may not be empty because another threads may insert items.
- */
- void clear()
- {
- base_class::clear();
- }
-
- /// Checks if the set is empty
- /**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of the set implementation.
- */
- bool empty() const
- {
- return base_class::empty();
- }
-
- /// Returns item count in the set
- size_t size() const
- {
- return base_class::size();
- }
-
- /// Returns const reference to internal statistics
- stat const& statistics() const
- {
- return base_class::statistics();
- }
-
- /// Returns the size of head node
- size_t head_size() const
- {
- return base_class::head_size();
- }
-
- /// Returns the size of the array node
- size_t array_node_size() const
- {
- return base_class::array_node_size();
- }
-
- public:
- ///@name Thread-safe iterators
- /** @anchor cds_container_MultilevelHashSet_iterators
- The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
- It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
- Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
-
- @note Since the iterator object contains hazard pointer that is a thread-local resource,
- the iterator should not be passed to another thread.
-
- Each iterator object supports the common interface:
- - dereference operators:
- @code
- value_type [const] * operator ->() noexcept
- value_type [const] & operator *() noexcept
- @endcode
- - pre-increment and pre-decrement. Post-operators is not supported
- - equality operators <tt>==</tt> and <tt>!=</tt>.
- Iterators are equal iff they point to the same cell of the same array node.
- Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
- does not entail <tt> &(*it1) == &(*it2) </tt>
- - helper member function \p release() that clears internal hazard pointer.
- After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
-
- During iteration you may safely erase any item from the set;
- @ref erase_at() function call doesn't invalidate any iterator.
- If some iterator points to the item to be erased, that item is not deleted immediately
- but only after that iterator will be advanced forward or backward.
-
- @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
- in array node that is being splitted.
- */
- ///@{
-
- /// Returns an iterator to the beginning of the set
- iterator begin()
- {
- return base_class::begin();
- }
-
- /// Returns an const iterator to the beginning of the set
- const_iterator begin() const
- {
- return base_class::begin();
- }
-
- /// Returns an const iterator to the beginning of the set
- const_iterator cbegin()
- {
- return base_class::cbegin();
- }
-
- /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
- iterator end()
- {
- return base_class::end();
- }
-
- /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator end() const
- {
- return base_class::end();
- }
-
- /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator cend()
- {
- return base_class::cend();
- }
-
- /// Returns a reverse iterator to the first element of the reversed set
- reverse_iterator rbegin()
- {
- return base_class::rbegin();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed set
- const_reverse_iterator rbegin() const
- {
- return base_class::rbegin();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed set
- const_reverse_iterator crbegin()
- {
- return base_class::crbegin();
- }
-
- /// Returns a reverse iterator to the element following the last element of the reversed set
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- reverse_iterator rend()
- {
- return base_class::rend();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed set
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator rend() const
- {
- return base_class::rend();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed set
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator crend()
- {
- return base_class::crend();
- }
- ///@}
- };
-
-}} // namespace cds::container
-
-#endif // #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHSET_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H
-#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H
-
-#include <cds/container/impl/multilevel_hashmap.h>
-#include <cds/gc/dhp.h>
-
-#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_DHP_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H
-#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H
-
-#include <cds/container/impl/multilevel_hashmap.h>
-#include <cds/gc/hp.h>
-
-#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_HP_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
-#define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
-
-#include <cds/intrusive/multilevel_hashset_rcu.h>
-#include <cds/container/details/multilevel_hashmap_base.h>
-
-namespace cds { namespace container {
-
- /// Hash map based on multi-level array
- /** @ingroup cds_nonintrusive_map
- @anchor cds_container_MultilevelHashMap_rcu
-
- Source:
- - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
- Wait-free Extensible Hash Maps"
-
- See algorithm short description @ref cds_container_MultilevelHashMap_hp "here"
-
- @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-size hash values of your keys.
- For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
- converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.
- If your key is fixed-sized the hash functor is optional, see \p multilevel_hashmap::traits::hash for explanation and examples.
- - \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 map. \p %MultiLevelHashMap does not maintain the key,
- it maintains its fixed-size hash value.
-
- The map supports @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional thread-safe iterators".
-
- Template parameters:
- - \p RCU - one of \ref cds_urcu_gc "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.
-
- @note Before including <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> you should include appropriate RCU header file,
- see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
- */
- template <
- class RCU
- ,typename Key
- ,typename T
-#ifdef CDS_DOXYGEN_INVOKED
- ,class Traits = multilevel_hashmap::traits
-#else
- ,class Traits
-#endif
- >
- class MultiLevelHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
-#ifdef CDS_DOXYGEN_INVOKED
- : protected cds::intrusive::MultiLevelHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
-#else
- : protected cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
-#endif
- {
- //@cond
- typedef cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
- typedef typename maker::type base_class;
- //@endcond
- public:
- typedef cds::urcu::gc< RCU > gc; ///< RCU 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 traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
- typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
- static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
-
- 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;
- typedef typename base_class::check_deadlock_policy check_deadlock_policy;
-
- struct node_cast
- {
- value_type * operator()(node_type * p) const
- {
- return p ? &p->m_Value : nullptr;
- }
- };
-
- public:
- /// pointer to extracted node
- using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
-
- protected:
- template <bool IsConst>
- class bidirectional_iterator: public base_class::iterator_base
- {
- friend class MultiLevelHashMap;
- typedef typename base_class::iterator_base iterator_base;
-
- protected:
- static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
-
- public:
- typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
- typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
-
- public:
- bidirectional_iterator() CDS_NOEXCEPT
- {}
-
- bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
- : iterator_base( rhs )
- {}
-
- bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
- {
- iterator_base::operator=( rhs );
- return *this;
- }
-
- bidirectional_iterator& operator++()
- {
- iterator_base::operator++();
- return *this;
- }
-
- bidirectional_iterator& operator--()
- {
- iterator_base::operator--();
- return *this;
- }
-
- value_ptr operator ->() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- return p ? &p->m_Value : nullptr;
- }
-
- value_ref operator *() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- assert( p );
- return p->m_Value;
- }
-
- void release()
- {
- iterator_base::release();
- }
-
- template <bool IsConst2>
- 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
- {
- return !( *this == rhs );
- }
-
- public: // for internal use only!
- bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
- : iterator_base( set, pNode, idx, false )
- {}
-
- bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
- : iterator_base( set, pNode, idx )
- {}
- };
-
- /// Reverse bidirectional iterator
- template <bool IsConst>
- class reverse_bidirectional_iterator : public base_class::iterator_base
- {
- friend class MultiLevelHashMap;
- typedef typename base_class::iterator_base iterator_base;
-
- public:
- typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
- typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
-
- public:
- reverse_bidirectional_iterator() CDS_NOEXCEPT
- : iterator_base()
- {}
-
- reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
- : iterator_base( rhs )
- {}
-
- reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
- {
- iterator_base::operator=( rhs );
- return *this;
- }
-
- reverse_bidirectional_iterator& operator++()
- {
- iterator_base::operator--();
- return *this;
- }
-
- reverse_bidirectional_iterator& operator--()
- {
- iterator_base::operator++();
- return *this;
- }
-
- value_ptr operator ->() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- return p ? &p->m_Value : nullptr;
- }
-
- value_ref operator *() const CDS_NOEXCEPT
- {
- node_type * p = iterator_base::pointer();
- assert( p );
- return p->m_Value;
- }
-
- void release()
- {
- iterator_base::release();
- }
-
- template <bool IsConst2>
- 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)
- {
- return !( *this == rhs );
- }
-
- public: // for internal use only!
- reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
- : iterator_base( set, pNode, idx, false )
- {}
-
- reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
- : iterator_base( set, pNode, idx, false )
- {
- iterator_base::backward();
- }
- };
- //@endcond
-
- public:
-#ifdef CDS_DOXYGEN_INVOKED
- typedef implementation_defined iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional iterator" type
- typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional const iterator" type
- typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse iterator" type
- typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse const iterator" type
-#else
- typedef bidirectional_iterator<false> iterator;
- typedef bidirectional_iterator<true> const_iterator;
- typedef reverse_bidirectional_iterator<false> reverse_iterator;
- typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
-#endif
-
- protected:
- //@cond
- hasher m_Hasher;
- //@endcond
-
- public:
- /// Creates empty map
- /**
- @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
- @param array_bits: 2<sup>array_bits</sup> 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.
-
- The function locks RCU internally.
- */
- template <typename K>
- bool insert( 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;
- }
- 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 map, \p false otherwise.
-
- The function locks RCU internally.
- */
- 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)));
- 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:
- - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
- - <tt>item.second</tt> 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.
-
- The function locks RCU internally.
- */
- 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)));
- 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 <tt>std::forward<Args>(args)...</tt>
- /**
- Returns \p true if inserting successful, \p false otherwise.
-
- The function locks RCU internally.
- */
- 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)... ));
- if ( base_class::insert( *sp )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Updates data by \p key
- /**
- The operation performs inserting or replacing the element 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, it is replaced with a new item created from
- \p key.
- The functor \p Func signature:
- \code
- struct my_functor {
- void operator()( value_type& item, value_type * old );
- };
- \endcode
- where:
- - \p item - item of the map
- - \p old - old item of the map, if \p nullptr - the new item was inserted
-
- 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,
- \p second is \p true if new item has been added or \p false if \p key already exists.
-
- The function locks RCU internally.
-
- @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)));
- 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 );
- 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.
- The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
-
- Return \p true if \p key is found and deleted, \p false otherwise.
-
- RCU should not be locked. The function locks RCU internally.
- */
- template <typename K>
- bool erase( K const& key )
- {
- return base_class::erase(m_Hasher(key_type(key)));
- }
-
- /// Delete \p key from the map
- /**
- The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
- 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
- where \p item is the element found.
-
- \p key_type must be constructible from value of type \p K.
-
- Return \p true if key is found and deleted, \p false otherwise
-
- RCU should not be locked. The function locks RCU internally.
- */
- 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 ); });
- }
-
- /// Extracts the item from the map with specified \p key
- /**
- The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
- unlinks it from the map, and returns a guarded pointer to the item found.
- If \p key is not found the function returns an empty guarded pointer.
-
- RCU \p synchronize method can be called. RCU should NOT be locked.
- The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when the returned object is destroyed or when
- its \p release() member function is called.
- Example:
- \code
- typedef cds::container::MultiLevelHashMap< cds::urcu::gc< cds::urcu::general_buffered<>>, int, foo, my_traits > map_type;
- map_type theMap;
- // ...
-
- typename map_type::exempt_ptr ep( theMap.extract( 5 ));
- if ( ep ) {
- // Deal with ep
- //...
-
- // Dispose returned item.
- ep.release();
- }
- \endcode
- */
- template <typename K>
- exempt_ptr extract( K const& key )
- {
- check_deadlock_policy::check();
-
- node_type * p;
- {
- rcu_lock rcuLock;
- p = base_class::do_erase( m_Hasher( key_type(key)), [](node_type const&) -> bool {return true;});
- }
- return exempt_ptr(p);
- }
-
- /// Checks whether the map contains \p key
- /**
- The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
- and returns \p true if it is found, or \p false otherwise.
- */
- template <typename K>
- bool contains( K const& key )
- {
- return base_class::contains( m_Hasher( key_type( key )) );
- }
-
- /// Find the key \p key
- /**
-
- The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
- and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item );
- };
- \endcode
- where \p item is the item found.
-
- The functor may change \p item.second.
-
- The function returns \p true if \p key is found, \p false otherwise.
- */
- 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 );});
- }
-
- /// Finds the key \p key and return the item found
- /**
- The function searches the item by its \p hash
- and returns the pointer to the item found.
- If \p hash is not found the function returns \p nullptr.
-
- RCU should be locked before the function invocation.
- Returned pointer is valid only while RCU is locked.
-
- Usage:
- \code
- typedef cds::container::MultiLevelHashMap< your_template_params > my_map;
- my_map theMap;
- // ...
- {
- // lock RCU
- my_map::rcu_lock;
-
- foo * p = theMap.get( 5 );
- if ( p ) {
- // Deal with p
- //...
- }
- }
- \endcode
- */
- template <typename K>
- value_type * get( K const& key )
- {
- node_type * p = base_class::get( m_Hasher( key_type( key )));
- return p ? &p->m_Value : nullptr;
- }
-
- /// Clears the map (non-atomic)
- /**
- The function unlink all data node from the map.
- The function is not atomic but is thread-safe.
- After \p %clear() the map may not be empty because another threads may insert items.
- */
- void clear()
- {
- base_class::clear();
- }
-
- /// Checks if the map is empty
- /**
- Emptiness is checked by item counting: if item count is zero then the map is empty.
- Thus, the correct item counting feature is an important part of the map implementation.
- */
- bool empty() const
- {
- return base_class::empty();
- }
-
- /// Returns item count in the map
- size_t size() const
- {
- return base_class::size();
- }
-
- /// Returns const reference to internal statistics
- stat const& statistics() const
- {
- return base_class::statistics();
- }
-
- /// Returns the size of head node
- size_t head_size() const
- {
- return base_class::head_size();
- }
-
- /// Returns the size of the array node
- size_t array_node_size() const
- {
- return base_class::array_node_size();
- }
-
- public:
- ///@name Thread-safe iterators
- /** @anchor cds_container_MultilevelHashMap_rcu_iterators
- The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment
- under explicit RCU lock.
- RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map
- since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
- while your thread is iterating.
-
- A typical example is:
- \code
- struct foo {
- // ... other fields
- uint32_t payload; // only for example
- };
- typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
- typedef cds::container::MultiLevelHashMap< rcu, std::string, foo> map_type;
-
- map_type m;
-
- // ...
-
- // iterate over the map
- {
- // lock the RCU.
- typename set_type::rcu_lock l; // scoped RCU lock
-
- // traverse the map
- for ( auto i = m.begin(); i != s.end(); ++i ) {
- // deal with i. Remember, erasing is prohibited here!
- i->second.payload++;
- }
- } // at this point RCU lock is released
- /endcode
-
- Each iterator object supports the common interface:
- - dereference operators:
- @code
- value_type [const] * operator ->() noexcept
- value_type [const] & operator *() noexcept
- @endcode
- - pre-increment and pre-decrement. Post-operators is not supported
- - equality operators <tt>==</tt> and <tt>!=</tt>.
- Iterators are equal iff they point to the same cell of the same array node.
- Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
- does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
-
- @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
- in an array node that is being splitted.
- */
- ///@{
- /// Returns an iterator to the beginning of the map
- iterator begin()
- {
- return base_class::template init_begin<iterator>();
- }
-
- /// Returns an const iterator to the beginning of the map
- const_iterator begin() const
- {
- return base_class::template init_begin<const_iterator>();
- }
-
- /// Returns an const iterator to the beginning of the map
- const_iterator cbegin()
- {
- return base_class::template init_begin<const_iterator>();
- }
-
- /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
- iterator end()
- {
- return base_class::template init_end<iterator>();
- }
-
- /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator end() const
- {
- return base_class::template init_end<const_iterator>();
- }
-
- /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator cend()
- {
- return base_class::template init_end<const_iterator>();
- }
-
- /// Returns a reverse iterator to the first element of the reversed map
- reverse_iterator rbegin()
- {
- return base_class::template init_rbegin<reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed map
- const_reverse_iterator rbegin() const
- {
- return base_class::template init_rbegin<const_reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed map
- const_reverse_iterator crbegin()
- {
- return base_class::template init_rbegin<const_reverse_iterator>();
- }
-
- /// Returns a reverse iterator to the element following the last element of the reversed map
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- reverse_iterator rend()
- {
- return base_class::template init_rend<reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed map
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator rend() const
- {
- return base_class::template init_rend<const_reverse_iterator>();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed map
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator crend()
- {
- return base_class::template init_rend<const_reverse_iterator>();
- }
- ///@}
- };
-}} // namespace cds::container
-
-#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHSET_DHP_H
-#define CDSLIB_CONTAINER_MULTILEVEL_HASHSET_DHP_H
-
-#include <cds/container/impl/multilevel_hashset.h>
-#include <cds/gc/dhp.h>
-
-#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHSET_DHP_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHSET_HP_H
-#define CDSLIB_CONTAINER_MULTILEVEL_HASHSET_HP_H
-
-#include <cds/container/impl/multilevel_hashset.h>
-#include <cds/gc/hp.h>
-
-#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHSET_HP_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHSET_RCU_H
-#define CDSLIB_CONTAINER_MULTILEVEL_HASHSET_RCU_H
-
-#include <cds/intrusive/multilevel_hashset_rcu.h>
-#include <cds/container/details/multilevel_hashset_base.h>
-
-namespace cds { namespace container {
-
- /// Hash set based on multi-level array, \ref cds_urcu_desc "RCU" specialization
- /** @ingroup cds_nonintrusive_set
- @anchor cds_container_MultilevelHashSet_rcu
-
- Source:
- - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
- Wait-free Extensible Hash Maps"
-
- See algorithm short description @ref cds_intrusive_MultilevelHashSet_hp "here"
-
- @note Two important things you should keep in mind when you're using \p %MultiLevelHashSet:
- - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %MultiLevelHashSet.
- Instead, for the strings you should use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
- <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
- or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
- converts variable-length strings to fixed-length bit-strings, and use that hash as a key in \p %MultiLevelHashSet.
- - \p %MultiLevelHashSet 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 %MultiLevelHashSet does not maintain the key,
- it maintains its fixed-size hash value.
-
- The set supports @ref cds_container_MultilevelHashSet_iterators "bidirectional thread-safe iterators".
-
- Template parameters:
- - \p RCU - one of \ref cds_urcu_gc "RCU type"
- - \p T - a value type to be stored in the set
- - \p Traits - type traits, the structure based on \p multilevel_hashset::traits or result of \p multilevel_hashset::make_traits metafunction.
- \p Traits is the mandatory argument because it has one mandatory type - an @ref multilevel_hashset::traits::hash_accessor "accessor"
- to hash value of \p T. The set algorithm does not calculate that hash value.
-
- @note Before including <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> you should include appropriate RCU header file,
- see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
-
- The set supports @ref cds_container_MultilevelHashSet_rcu_iterators "bidirectional thread-safe iterators"
- with some restrictions.
- */
- template <
- class RCU
- , typename T
-#ifdef CDS_DOXYGEN_INVOKED
- , class Traits = multilevel_hashset::traits
-#else
- , class Traits
-#endif
- >
- class MultiLevelHashSet< cds::urcu::gc< RCU >, T, Traits >
-#ifdef CDS_DOXYGEN_INVOKED
- : protected cds::intrusive::MultiLevelHashSet< cds::urcu::gc< RCU >, T, Traits >
-#else
- : protected cds::container::details::make_multilevel_hashset< cds::urcu::gc< RCU >, T, Traits >::type
-#endif
- {
- //@cond
- typedef cds::container::details::make_multilevel_hashset< cds::urcu::gc< RCU >, T, Traits > maker;
- typedef typename maker::type base_class;
- //@endcond
-
- public:
- typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
- typedef T value_type; ///< type of value stored in the set
- typedef Traits traits; ///< Traits template parameter, see \p multilevel_hashset::traits
-
- typedef typename base_class::hash_accessor hash_accessor; ///< Hash accessor functor
- typedef typename base_class::hash_type hash_type; ///< Hash type deduced from \p hash_accessor return type
- typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p opt::compare and \p opt::less option setter
-
- 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 traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
- typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
- static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
- typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node
-
- typedef typename base_class::iterator iterator; ///< @ref cds_container_MultilevelHashSet_rcu_iterators "bidirectional iterator" type
- typedef typename base_class::const_iterator const_iterator; ///< @ref cds_container_MultilevelHashSet_rcu_iterators "bidirectional const iterator" type
- typedef typename base_class::reverse_iterator reverse_iterator; ///< @ref cds_container_MultilevelHashSet_rcu_iterators "bidirectional reverse iterator" type
- typedef typename base_class::const_reverse_iterator const_reverse_iterator; ///< @ref cds_container_MultilevelHashSet_rcu_iterators "bidirectional reverse const iterator" type
-
- protected:
- //@cond
- typedef typename maker::cxx_node_allocator cxx_node_allocator;
- typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
- //@endcond
-
- public:
- /// Creates empty set
- /**
- @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
- @param array_bits: 2<sup>array_bits</sup> 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.
- */
- MultiLevelHashSet( size_t head_bits = 8, size_t array_bits = 4 )
- : base_class( head_bits, array_bits )
- {}
-
- /// Destructs the set and frees all data
- ~MultiLevelHashSet()
- {}
-
- /// Inserts new element
- /**
- The function creates an element with copy of \p val value and then inserts it into the set.
-
- The type \p Q should contain as minimum the complete hash for the element.
- The object of \ref value_type should be constructible from a value of type \p Q.
- In trivial case, \p Q is equal to \ref value_type.
-
- Returns \p true if \p val is inserted into the set, \p false otherwise.
-
- The function locks RCU internally.
- */
- template <typename Q>
- bool insert( Q const& val )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( val ));
- if ( base_class::insert( *sp )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Inserts new element
- /**
- The function allows to split creating of new item into two part:
- - create item with key only
- - insert new item into the set
- - if inserting is success, calls \p f functor to initialize value-fields of \p val.
-
- The functor signature is:
- \code
- void func( value_type& val );
- \endcode
- where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
- \p val no any other changes could be made on this set's item by concurrent threads.
- The user-defined functor is called only if the inserting is success.
-
- The function locks RCU internally.
- */
- template <typename Q, typename Func>
- bool insert( Q const& val, Func f )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( val ));
- if ( base_class::insert( *sp, f )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Updates the element
- /**
- The operation performs inserting or replacing with lock-free manner.
-
- If the \p val key not found in the set, then the new item created from \p val
- will be inserted into the set iff \p bInsert is \p true.
- Otherwise, if \p val is found, it is replaced with new item created from \p val
- and previous item is disposed.
- In both cases \p func functor is called.
-
- The functor \p Func signature:
- \code
- struct my_functor {
- void operator()( value_type& cur, value_type * prev );
- };
- \endcode
- where:
- - \p cur - current element
- - \p prev - pointer to previous element with such hash. \p prev is \p nullptr
- if \p cur was just inserted.
-
- The functor may change non-key fields of the \p item; however, \p func must guarantee
- that during changing no any other modifications could be made on this item by concurrent threads.
-
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
- i.e. the item has been inserted or updated,
- \p second is \p true if the new item has been added or \p false if the item with key equal to \p val
- already exists.
- */
- template <typename Q, typename Func>
- std::pair<bool, bool> update( Q const& val, Func func, bool bInsert = true )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( val ));
- std::pair<bool, bool> bRes = base_class::do_update( *sp, func, bInsert );
- if ( bRes.first )
- sp.release();
- return bRes;
- }
-
- /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
- /**
- Returns \p true if inserting successful, \p false otherwise.
- */
- template <typename... Args>
- bool emplace( Args&&... args )
- {
- scoped_node_ptr sp( cxx_node_allocator().New( std::forward<Args>(args)... ));
- if ( base_class::insert( *sp )) {
- sp.release();
- return true;
- }
- return false;
- }
-
- /// Deletes the item from the set
- /**
- The function searches \p hash in the set,
- deletes the item found, and returns \p true.
- If that item is not found the function returns \p false.
-
- RCU should not be locked. The function locks RCU internally.
- */
- bool erase( hash_type const& hash )
- {
- return base_class::erase( hash );
- }
-
- /// Deletes the item from the set
- /**
- The function searches \p hash in the set,
- call \p f functor with item found, and deltes the element from the set.
-
- The \p Func interface is
- \code
- struct functor {
- void operator()( value_type& item );
- };
- \endcode
-
- If \p hash is not found the function returns \p false.
-
- RCU should not be locked. The function locks RCU internally.
- */
- template <typename Func>
- bool erase( hash_type const& hash, Func f )
- {
- return base_class::erase( hash, f );
- }
-
- /// Extracts the item with specified \p hash
- /**
- The function searches \p hash in the set,
- unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
- If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
-
- RCU \p synchronize method can be called. RCU should NOT be locked.
- The function does not call the disposer for the item found.
- The disposer will be implicitly invoked when the returned object is destroyed or when
- its \p release() member function is called.
- Example:
- \code
- typedef cds::container::MultiLevelHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > set_type;
- set_type theSet;
- // ...
-
- typename set_type::exempt_ptr ep( theSet.extract( 5 ));
- if ( ep ) {
- // Deal with ep
- //...
-
- // Dispose returned item.
- ep.release();
- }
- \endcode
- */
- exempt_ptr extract( hash_type const& hash )
- {
- return base_class::extract( hash );
- }
-
- /// Finds an item by it's \p hash
- /**
- The function searches the item by \p hash and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item );
- };
- \endcode
- where \p item is the item found.
-
- The functor may change non-key fields of \p item. Note that the functor is only guarantee
- that \p item cannot be disposed during the functor is executing.
- The functor does not serialize simultaneous access to the set's \p item. If such access is
- possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
-
- The function returns \p true if \p hash is found, \p false otherwise.
- */
- template <typename Func>
- bool find( hash_type const& hash, Func f )
- {
- return base_class::find( hash, f );
- }
-
- /// Checks whether the set contains \p hash
- /**
- The function searches the item by its \p hash
- and returns \p true if it is found, or \p false otherwise.
- */
- bool contains( hash_type const& hash )
- {
- return base_class::contains( hash );
- }
-
- /// Finds an item by it's \p hash and returns the item found
- /**
- The function searches the item by its \p hash
- and returns the pointer to the item found.
- If \p hash is not found the function returns \p nullptr.
-
- RCU should be locked before the function invocation.
- Returned pointer is valid only while RCU is locked.
-
- Usage:
- \code
- typedef cds::container::MultiLevelHashSet< your_template_params > my_set;
- my_set theSet;
- // ...
- {
- // lock RCU
- my_set::rcu_lock;
-
- foo * p = theSet.get( 5 );
- if ( p ) {
- // Deal with p
- //...
- }
- }
- \endcode
- */
- value_type * get( hash_type const& hash )
- {
- return base_class::get( hash );
- }
-
- /// Clears the set (non-atomic)
- /**
- The function unlink all data node from the set.
- The function is not atomic but is thread-safe.
- After \p %clear() the set may not be empty because another threads may insert items.
- */
- void clear()
- {
- base_class::clear();
- }
-
- /// Checks if the set is empty
- /**
- Emptiness is checked by item counting: if item count is zero then the set is empty.
- Thus, the correct item counting feature is an important part of the set implementation.
- */
- bool empty() const
- {
- return base_class::empty();
- }
-
- /// Returns item count in the set
- size_t size() const
- {
- return base_class::size();
- }
-
- /// Returns const reference to internal statistics
- stat const& statistics() const
- {
- return base_class::statistics();
- }
-
- /// Returns the size of head node
- size_t head_size() const
- {
- return base_class::head_size();
- }
-
- /// Returns the size of the array node
- size_t array_node_size() const
- {
- return base_class::array_node_size();
- }
-
- public:
- ///@name Thread-safe iterators
- /** @anchor cds_container_MultilevelHashSet_rcu_iterators
- The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment
- under explicit RCU lock.
- RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the set
- since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
- while your thread is iterating.
-
- A typical example is:
- \code
- struct foo {
- uint32_t hash;
- // ... other fields
- uint32_t payload; // only for example
- };
- struct set_traits: cds::container::multilevel_hashset::traits
- {
- struct hash_accessor {
- uint32_t operator()( foo const& src ) const
- {
- retur src.hash;
- }
- };
- };
-
- typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
- typedef cds::container::MultiLevelHashSet< rcu, foo, set_traits > set_type;
-
- set_type s;
-
- // ...
-
- // iterate over the set
- {
- // lock the RCU.
- typename set_type::rcu_lock l; // scoped RCU lock
-
- // traverse the set
- for ( auto i = s.begin(); i != s.end(); ++i ) {
- // deal with i. Remember, erasing is prohibited here!
- i->payload++;
- }
- } // at this point RCU lock is released
- /endcode
-
- Each iterator object supports the common interface:
- - dereference operators:
- @code
- value_type [const] * operator ->() noexcept
- value_type [const] & operator *() noexcept
- @endcode
- - pre-increment and pre-decrement. Post-operators is not supported
- - equality operators <tt>==</tt> and <tt>!=</tt>.
- Iterators are equal iff they point to the same cell of the same array node.
- Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
- does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
-
- @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
- in an array node that is being splitted.
- */
- ///@{
-
- /// Returns an iterator to the beginning of the set
- iterator begin()
- {
- return base_class::begin();
- }
-
- /// Returns an const iterator to the beginning of the set
- const_iterator begin() const
- {
- return base_class::begin();
- }
-
- /// Returns an const iterator to the beginning of the set
- const_iterator cbegin()
- {
- return base_class::cbegin();
- }
-
- /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
- iterator end()
- {
- return base_class::end();
- }
-
- /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator end() const
- {
- return base_class::end();
- }
-
- /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
- const_iterator cend()
- {
- return base_class::cend();
- }
-
- /// Returns a reverse iterator to the first element of the reversed set
- reverse_iterator rbegin()
- {
- return base_class::rbegin();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed set
- const_reverse_iterator rbegin() const
- {
- return base_class::rbegin();
- }
-
- /// Returns a const reverse iterator to the first element of the reversed set
- const_reverse_iterator crbegin()
- {
- return base_class::crbegin();
- }
-
- /// Returns a reverse iterator to the element following the last element of the reversed set
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- reverse_iterator rend()
- {
- return base_class::rend();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed set
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator rend() const
- {
- return base_class::rend();
- }
-
- /// Returns a const reverse iterator to the element following the last element of the reversed set
- /**
- It corresponds to the element preceding the first element of the non-reversed container.
- This element acts as a placeholder, attempting to access it results in undefined behavior.
- */
- const_reverse_iterator crend()
- {
- return base_class::crend();
- }
- ///@}
- };
-
-}} // namespace cds::container
-
-#endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHSET_RCU_H
--- /dev/null
+//$$CDS-header$$
+
+#ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
+#define CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
+
+#include <memory.h> // memcmp, memcpy
+#include <type_traits>
+
+#include <cds/intrusive/details/base.h>
+#include <cds/opt/compare.h>
+#include <cds/algo/atomic.h>
+#include <cds/algo/split_bitstring.h>
+#include <cds/details/marked_ptr.h>
+#include <cds/urcu/options.h>
+
+namespace cds { namespace intrusive {
+
+ /// FeldmanHashSet related definitions
+ /** @ingroup cds_intrusive_helper
+ */
+ namespace feldman_hashset {
+ /// Hash accessor option
+ /**
+ @copydetails traits::hash_accessor
+ */
+ template <typename Accessor>
+ struct hash_accessor {
+ //@cond
+ template <typename Base> struct pack: public Base
+ {
+ typedef Accessor hash_accessor;
+ };
+ //@endcond
+ };
+
+ /// \p FeldmanHashSet internal statistics
+ template <typename EventCounter = cds::atomicity::event_counter>
+ struct stat {
+ typedef EventCounter event_counter ; ///< Event counter type
+
+ event_counter m_nInsertSuccess; ///< Number of success \p insert() operations
+ event_counter m_nInsertFailed; ///< Number of failed \p insert() operations
+ event_counter m_nInsertRetry; ///< Number of attempts to insert new item
+ event_counter m_nUpdateNew; ///< Number of new item inserted for \p update()
+ event_counter m_nUpdateExisting; ///< Number of existing item updates
+ event_counter m_nUpdateFailed; ///< Number of failed \p update() call
+ event_counter m_nUpdateRetry; ///< Number of attempts to update the item
+ event_counter m_nEraseSuccess; ///< Number of successful \p erase(), \p unlink(), \p extract() operations
+ event_counter m_nEraseFailed; ///< Number of failed \p erase(), \p unlink(), \p extract() operations
+ event_counter m_nEraseRetry; ///< Number of attempts to \p erase() an item
+ event_counter m_nFindSuccess; ///< Number of successful \p find() and \p get() operations
+ event_counter m_nFindFailed; ///< Number of failed \p find() and \p get() operations
+
+ event_counter m_nExpandNodeSuccess; ///< Number of succeeded attempts converting data node to array node
+ event_counter m_nExpandNodeFailed; ///< Number of failed attempts converting data node to array node
+ event_counter m_nSlotChanged; ///< Number of array node slot changing by other thread during an operation
+ event_counter m_nSlotConverting; ///< Number of events when we encounter a slot while it is converting to array node
+
+ event_counter m_nArrayNodeCount; ///< Number of array nodes
+ event_counter m_nHeight; ///< Current height of the tree
+
+ //@cond
+ void onInsertSuccess() { ++m_nInsertSuccess; }
+ void onInsertFailed() { ++m_nInsertFailed; }
+ void onInsertRetry() { ++m_nInsertRetry; }
+ void onUpdateNew() { ++m_nUpdateNew; &n
projects / libcds.git / commitdiff