Renamed MultiLevelHashSet/Map to FeldmanHashSet/Map
authorkhizmax <libcds.dev@gmail.com>
Tue, 20 Oct 2015 03:57:57 +0000 (06:57 +0300)
committerkhizmax <libcds.dev@gmail.com>
Tue, 20 Oct 2015 03:57:57 +0000 (06:57 +0300)
189 files changed:
cds/container/details/feldman_hashmap_base.h [new file with mode: 0644]
cds/container/details/feldman_hashset_base.h [new file with mode: 0644]
cds/container/details/multilevel_hashmap_base.h [deleted file]
cds/container/details/multilevel_hashset_base.h [deleted file]
cds/container/feldman_hashmap_dhp.h [new file with mode: 0644]
cds/container/feldman_hashmap_hp.h [new file with mode: 0644]
cds/container/feldman_hashmap_rcu.h [new file with mode: 0644]
cds/container/feldman_hashset_dhp.h [new file with mode: 0644]
cds/container/feldman_hashset_hp.h [new file with mode: 0644]
cds/container/feldman_hashset_rcu.h [new file with mode: 0644]
cds/container/impl/feldman_hashmap.h [new file with mode: 0644]
cds/container/impl/feldman_hashset.h [new file with mode: 0644]
cds/container/impl/multilevel_hashmap.h [deleted file]
cds/container/impl/multilevel_hashset.h [deleted file]
cds/container/multilevel_hashmap_dhp.h [deleted file]
cds/container/multilevel_hashmap_hp.h [deleted file]
cds/container/multilevel_hashmap_rcu.h [deleted file]
cds/container/multilevel_hashset_dhp.h [deleted file]
cds/container/multilevel_hashset_hp.h [deleted file]
cds/container/multilevel_hashset_rcu.h [deleted file]
cds/intrusive/details/feldman_hashset_base.h [new file with mode: 0644]
cds/intrusive/details/multilevel_hashset_base.h [deleted file]
cds/intrusive/feldman_hashset_dhp.h [new file with mode: 0644]
cds/intrusive/feldman_hashset_hp.h [new file with mode: 0644]
cds/intrusive/feldman_hashset_rcu.h [new file with mode: 0644]
cds/intrusive/impl/feldman_hashset.h [new file with mode: 0644]
cds/intrusive/impl/multilevel_hashset.h [deleted file]
cds/intrusive/multilevel_hashset_dhp.h [deleted file]
cds/intrusive/multilevel_hashset_hp.h [deleted file]
cds/intrusive/multilevel_hashset_rcu.h [deleted file]
projects/Win/vc12/cds.sln
projects/Win/vc12/cds.vcxproj
projects/Win/vc12/cds.vcxproj.filters
projects/Win/vc12/hdr-test-map.vcxproj
projects/Win/vc12/hdr-test-map.vcxproj.filters
projects/Win/vc12/hdr-test-set.vcxproj
projects/Win/vc12/hdr-test-set.vcxproj.filters
projects/Win/vc12/unit-map-delodd.vcxproj
projects/Win/vc12/unit-map-find.vcxproj
projects/Win/vc12/unit-map-find.vcxproj.filters
projects/Win/vc12/unit-map-insdel-item.vcxproj
projects/Win/vc12/unit-map-insdel-item.vcxproj.filters
projects/Win/vc12/unit-map-insdel.vcxproj
projects/Win/vc12/unit-map-insdel.vcxproj.filters
projects/Win/vc12/unit-map-insdelfind.vcxproj
projects/Win/vc12/unit-set-delodd.vcxproj
projects/Win/vc12/unit-set-insdel.vcxproj
projects/Win/vc12/unit-set-insdel.vcxproj.filters
projects/Win/vc12/unit-set-insdelfind.vcxproj
projects/Win/vc14/cds.sln
projects/Win/vc14/cds.vcxproj
projects/Win/vc14/cds.vcxproj.filters
projects/Win/vc14/hdr-test-map.vcxproj
projects/Win/vc14/hdr-test-map.vcxproj.filters
projects/Win/vc14/hdr-test-set.vcxproj
projects/Win/vc14/hdr-test-set.vcxproj.filters
projects/Win/vc14/unit-map-delodd.vcxproj
projects/Win/vc14/unit-map-find.vcxproj
projects/Win/vc14/unit-map-find.vcxproj.filters
projects/Win/vc14/unit-map-insdel-item.vcxproj
projects/Win/vc14/unit-map-insdel-item.vcxproj.filters
projects/Win/vc14/unit-map-insdel.vcxproj
projects/Win/vc14/unit-map-insdel.vcxproj.filters
projects/Win/vc14/unit-map-insdelfind.vcxproj
projects/Win/vc14/unit-set-delodd.vcxproj
projects/Win/vc14/unit-set-insdel.vcxproj
projects/Win/vc14/unit-set-insdel.vcxproj.filters
projects/Win/vc14/unit-set-insdelfind.vcxproj
projects/source.test-hdr.mk
projects/source.unit.map.mk
projects/source.unit.set.mk
tests/data/test-debug.conf
tests/data/test-express.conf
tests/data/test.conf
tests/test-hdr/CMakeLists.txt
tests/test-hdr/map/hdr_feldman_hashmap.h [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_dhp.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_hp.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_rcu_gpb.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_rcu_gpi.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_rcu_gpt.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_rcu_shb.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_feldman_hashmap_rcu_sht.cpp [new file with mode: 0644]
tests/test-hdr/map/hdr_multilevel_hashmap.h [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_dhp.cpp [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_hp.cpp [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpb.cpp [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpi.cpp [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_rcu_gpt.cpp [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_rcu_shb.cpp [deleted file]
tests/test-hdr/map/hdr_multilevel_hashmap_rcu_sht.cpp [deleted file]
tests/test-hdr/set/hdr_feldman_hashset.h [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_dhp.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_hp.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_rcu_gpb.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_rcu_gpi.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_rcu_gpt.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_rcu_shb.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_feldman_hashset_rcu_sht.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset.h [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_dhp.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_hp.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_rcu_gpb.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_rcu_gpi.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_rcu_gpt.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_rcu_shb.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_feldman_hashset_rcu_sht.cpp [new file with mode: 0644]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_dhp.cpp [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_hp.cpp [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpb.cpp [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpi.cpp [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_gpt.cpp [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_shb.cpp [deleted file]
tests/test-hdr/set/hdr_intrusive_multilevel_hashset_rcu_sht.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset.h [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_dhp.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_hp.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_rcu_gpb.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_rcu_gpi.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_rcu_gpt.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_rcu_shb.cpp [deleted file]
tests/test-hdr/set/hdr_multilevel_hashset_rcu_sht.cpp [deleted file]
tests/unit/map2/CMakeLists.txt
tests/unit/map2/map_defs.h
tests/unit/map2/map_delodd.cpp
tests/unit/map2/map_delodd.h
tests/unit/map2/map_delodd_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_delodd_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_find_int.cpp
tests/unit/map2/map_find_int.h
tests/unit/map2/map_find_int_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_find_int_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_find_string.cpp
tests/unit/map2/map_find_string.h
tests/unit/map2/map_find_string_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_find_string_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insdel_func.cpp
tests/unit/map2/map_insdel_func.h
tests/unit/map2/map_insdel_func_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insdel_func_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insdel_int.cpp
tests/unit/map2/map_insdel_int.h
tests/unit/map2/map_insdel_int_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insdel_int_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insdel_item_int.cpp
tests/unit/map2/map_insdel_item_int.h
tests/unit/map2/map_insdel_item_int_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insdel_item_int_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insdel_item_string.cpp
tests/unit/map2/map_insdel_item_string.h
tests/unit/map2/map_insdel_item_string_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insdel_item_string_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insdel_string.cpp
tests/unit/map2/map_insdel_string.h
tests/unit/map2/map_insdel_string_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insdel_string_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insdelfind.cpp
tests/unit/map2/map_insdelfind.h
tests/unit/map2/map_insdelfind_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insdelfind_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_insfind_int.cpp
tests/unit/map2/map_insfind_int.h
tests/unit/map2/map_insfind_int_feldmanhashmap.cpp [new file with mode: 0644]
tests/unit/map2/map_insfind_int_multilevelhashmap.cpp [deleted file]
tests/unit/map2/map_type_feldman_hashmap.h [new file with mode: 0644]
tests/unit/map2/map_type_multilevel_hashmap.h [deleted file]
tests/unit/print_feldman_hashset_stat.h [new file with mode: 0644]
tests/unit/print_multilevel_hashset_stat.h [deleted file]
tests/unit/set2/CMakeLists.txt
tests/unit/set2/set_defs.h
tests/unit/set2/set_delodd.cpp
tests/unit/set2/set_delodd.h
tests/unit/set2/set_delodd_feldmanhashset.cpp [new file with mode: 0644]
tests/unit/set2/set_delodd_multilevelhashset.cpp [deleted file]
tests/unit/set2/set_insdel_func.cpp
tests/unit/set2/set_insdel_func.h
tests/unit/set2/set_insdel_func_feldmanhashset.cpp [new file with mode: 0644]
tests/unit/set2/set_insdel_func_multilevelhashset.cpp [deleted file]
tests/unit/set2/set_insdel_string.cpp
tests/unit/set2/set_insdel_string.h
tests/unit/set2/set_insdel_string_feldmanhashset.cpp [new file with mode: 0644]
tests/unit/set2/set_insdel_string_multilevelhashset.cpp [deleted file]
tests/unit/set2/set_insdelfind.cpp
tests/unit/set2/set_insdelfind.h
tests/unit/set2/set_insdelfind_feldmanhashset.cpp [new file with mode: 0644]
tests/unit/set2/set_insdelfind_multilevelhashset.cpp [deleted file]
tests/unit/set2/set_type_feldman_hashset.h [new file with mode: 0644]
tests/unit/set2/set_type_multilevel_hashset.h [deleted file]

diff --git a/cds/container/details/feldman_hashmap_base.h b/cds/container/details/feldman_hashmap_base.h
new file mode 100644 (file)
index 0000000..20eab6b
--- /dev/null
@@ -0,0 +1,325 @@
+//$$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
diff --git a/cds/container/details/feldman_hashset_base.h b/cds/container/details/feldman_hashset_base.h
new file mode 100644 (file)
index 0000000..2f31962
--- /dev/null
@@ -0,0 +1,169 @@
+//$$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
diff --git a/cds/container/details/multilevel_hashmap_base.h b/cds/container/details/multilevel_hashmap_base.h
deleted file mode 100644 (file)
index b06b5cb..0000000
+++ /dev/null
@@ -1,325 +0,0 @@
-//$$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
diff --git a/cds/container/details/multilevel_hashset_base.h b/cds/container/details/multilevel_hashset_base.h
deleted file mode 100644 (file)
index f0c7fca..0000000
+++ /dev/null
@@ -1,169 +0,0 @@
-//$$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
diff --git a/cds/container/feldman_hashmap_dhp.h b/cds/container/feldman_hashmap_dhp.h
new file mode 100644 (file)
index 0000000..85ea7af
--- /dev/null
@@ -0,0 +1,9 @@
+//$$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
diff --git a/cds/container/feldman_hashmap_hp.h b/cds/container/feldman_hashmap_hp.h
new file mode 100644 (file)
index 0000000..50c66a8
--- /dev/null
@@ -0,0 +1,9 @@
+//$$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
diff --git a/cds/container/feldman_hashmap_rcu.h b/cds/container/feldman_hashmap_rcu.h
new file mode 100644 (file)
index 0000000..501766a
--- /dev/null
@@ -0,0 +1,780 @@
+//$$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
diff --git a/cds/container/feldman_hashset_dhp.h b/cds/container/feldman_hashset_dhp.h
new file mode 100644 (file)
index 0000000..ce87b59
--- /dev/null
@@ -0,0 +1,9 @@
+//$$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
diff --git a/cds/container/feldman_hashset_hp.h b/cds/container/feldman_hashset_hp.h
new file mode 100644 (file)
index 0000000..00ac704
--- /dev/null
@@ -0,0 +1,9 @@
+//$$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
diff --git a/cds/container/feldman_hashset_rcu.h b/cds/container/feldman_hashset_rcu.h
new file mode 100644 (file)
index 0000000..b8bbccf
--- /dev/null
@@ -0,0 +1,550 @@
+//$$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
diff --git a/cds/container/impl/feldman_hashmap.h b/cds/container/impl/feldman_hashmap.h
new file mode 100644 (file)
index 0000000..7fd1c14
--- /dev/null
@@ -0,0 +1,803 @@
+//$$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
diff --git a/cds/container/impl/feldman_hashset.h b/cds/container/impl/feldman_hashset.h
new file mode 100644 (file)
index 0000000..4e05f39
--- /dev/null
@@ -0,0 +1,562 @@
+//$$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
diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h
deleted file mode 100644 (file)
index 50a9d66..0000000
+++ /dev/null
@@ -1,803 +0,0 @@
-//$$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
diff --git a/cds/container/impl/multilevel_hashset.h b/cds/container/impl/multilevel_hashset.h
deleted file mode 100644 (file)
index 9d3341b..0000000
+++ /dev/null
@@ -1,562 +0,0 @@
-//$$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
diff --git a/cds/container/multilevel_hashmap_dhp.h b/cds/container/multilevel_hashmap_dhp.h
deleted file mode 100644 (file)
index 1f898b5..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-//$$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
diff --git a/cds/container/multilevel_hashmap_hp.h b/cds/container/multilevel_hashmap_hp.h
deleted file mode 100644 (file)
index f38c626..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-//$$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
diff --git a/cds/container/multilevel_hashmap_rcu.h b/cds/container/multilevel_hashmap_rcu.h
deleted file mode 100644 (file)
index c049b43..0000000
+++ /dev/null
@@ -1,780 +0,0 @@
-//$$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
diff --git a/cds/container/multilevel_hashset_dhp.h b/cds/container/multilevel_hashset_dhp.h
deleted file mode 100644 (file)
index 66b62b8..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-//$$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
diff --git a/cds/container/multilevel_hashset_hp.h b/cds/container/multilevel_hashset_hp.h
deleted file mode 100644 (file)
index 34dd032..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-//$$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
diff --git a/cds/container/multilevel_hashset_rcu.h b/cds/container/multilevel_hashset_rcu.h
deleted file mode 100644 (file)
index fdd1f5e..0000000
+++ /dev/null
@@ -1,550 +0,0 @@
-//$$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
diff --git a/cds/intrusive/details/feldman_hashset_base.h b/cds/intrusive/details/feldman_hashset_base.h
new file mode 100644 (file)
index 0000000..cb37cc2
--- /dev/null
@@ -0,0 +1,300 @@
+//$$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