2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H
34 #include <cds/intrusive/details/feldman_hashset_base.h>
35 #include <cds/container/details/base.h>
36 #include <cds/opt/hash.h>
38 namespace cds { namespace container {
39 /// \p FeldmanHashMap related definitions
40 /** @ingroup cds_nonintrusive_helper
42 namespace feldman_hashmap {
43 /// \p FeldmanHashMap internal statistics, see cds::intrusive::feldman_hashset::stat
44 template <typename EventCounter = cds::atomicity::event_counter>
45 using stat = cds::intrusive::feldman_hashset::stat< EventCounter >;
47 /// \p FeldmanHashMap empty internal statistics
48 typedef cds::intrusive::feldman_hashset::empty_stat empty_stat;
50 /// Bit-wise memcmp-based comparator for hash value \p T
52 using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
54 /// \p FeldmanHashMap level statistics
55 typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
57 /// \p FeldmanHashMap traits
60 /// Hash functor, default is \p opt::none
62 \p FeldmanHashMap may use any hash functor converting a key to
63 fixed-sized bit-string, for example, <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
64 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>,
65 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
66 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
68 If you use a fixed-sized key you may use it directly instead of a hash.
69 In such case \p %traits::hash should be specified as \p opt::none.
70 However, if you want to use the hash values or if your key type is not fixed-sized
71 you must specify a proper hash functor in your traits.
73 fixed-sized key - IP4 address map
82 int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
84 return memcmp( &lhs, &rhs, sizeof(lhs));
88 // Value - statistics for the IP address
94 // Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
95 struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
97 typedef ip4_cmp compare;
100 // IP4 address - statistics map
101 typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;
104 variable-size key requires a hash functor: URL map
106 // Value - statistics for the URL
112 // Key type (std::string) is variable-sized so we must provide a hash functor in our traits
113 // We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
114 struct url_map_traits: public cds::container::multilevl_hashmap::traits
116 typedef std::hash<std::string> hash;
119 // URL statistics map
120 typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;
123 typedef opt::none hash;
125 /// Hash comparing functor
127 @copydetails cds::intrusive::feldman_hashset::traits::compare
129 typedef cds::opt::none compare;
131 /// Specifies binary predicate used for hash compare.
133 @copydetails cds::intrusive::feldman_hashset::traits::less
135 typedef cds::opt::none less;
139 @copydetails cds::intrusive::feldman_hashset::traits::item_counter
141 typedef cds::atomicity::item_counter item_counter;
145 Default is \ref CDS_DEFAULT_ALLOCATOR
147 typedef CDS_DEFAULT_ALLOCATOR allocator;
149 /// Array node allocator
151 @copydetails cds::intrusive::feldman_hashset::traits::node_allocator
153 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
155 /// C++ memory ordering model
157 @copydetails cds::intrusive::feldman_hashset::traits::memory_model
159 typedef cds::opt::v::relaxed_ordering memory_model;
161 /// Back-off strategy
162 typedef cds::backoff::Default back_off;
164 /// Internal statistics
166 @copydetails cds::intrusive::feldman_hashset::traits::stat
168 typedef empty_stat stat;
170 /// RCU deadlock checking policy (only for \ref cds_container_FeldmanHashMap_rcu "RCU-based FeldmanHashMap")
172 @copydetails cds::intrusive::feldman_hashset::traits::rcu_check_deadlock
174 typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
177 /// Metafunction converting option list to \p feldman_hashmap::traits
179 Supported \p Options are:
180 - \p opt::hash - a hash functor, default is \p std::hash
181 @copydetails traits::hash
182 - \p opt::allocator - item allocator
183 @copydetails traits::allocator
184 - \p opt::node_allocator - array node allocator.
185 @copydetails traits::node_allocator
186 - \p opt::compare - hash comparison functor. No default functor is provided.
187 If the option is not specified, the \p opt::less is used.
188 - \p opt::less - specifies binary predicate used for hash comparison.
189 @copydetails cds::container::feldman_hashmap::traits::less
190 - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
191 - \p opt::item_counter - the type of item counting feature.
192 @copydetails cds::container::feldman_hashmap::traits::item_counter
193 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
194 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
195 - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashmap::empty_stat).
196 To enable it use \p feldman_hashmap::stat
197 - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
198 Default is \p opt::v::rcu_throw_deadlock
200 template <typename... Options>
203 # ifdef CDS_DOXYGEN_INVOKED
204 typedef implementation_defined type ; ///< Metafunction result
206 typedef typename cds::opt::make_options<
207 typename cds::opt::find_type_traits< traits, Options... >::type
212 } // namespace feldman_hashmap
215 // Forward declaration
216 template < class GC, typename Key, typename T, class Traits = feldman_hashmap::traits >
217 class FeldmanHashMap;
223 template <typename Key, typename Value, typename Hash>
226 typedef Key key_type;
227 typedef Value mapped_type;
230 typedef typename std::decay<
231 typename std::remove_reference<
232 decltype(hasher()(std::declval<key_type>()))
238 std::pair< key_type const, mapped_type> m_Value;
239 hash_type const m_hash;
241 node_type() = delete;
242 node_type(node_type const&) = delete;
244 template <typename Q>
245 node_type(hasher& h, Q const& key)
246 : m_Value(std::move(std::make_pair(key, mapped_type())))
247 , m_hash(h(m_Value.first))
250 template <typename Q, typename U >
251 node_type(hasher& h, Q const& key, U const& val)
252 : m_Value(std::move(std::make_pair(key, mapped_type(val))))
253 , m_hash(h(m_Value.first))
256 template <typename Q, typename... Args>
257 node_type(hasher& h, Q&& key, Args&&... args)
258 : m_Value(std::move(std::make_pair(std::forward<Q>(key), std::move(mapped_type(std::forward<Args>(args)...)))))
259 , m_hash(h(m_Value.first))
265 hash_type const& operator()(node_type const& node) const
272 template <typename Key, typename Value>
273 struct hash_selector<Key, Value, opt::none>
275 typedef Key key_type;
276 typedef Value mapped_type;
279 key_type const& operator()(key_type const& k) const
284 typedef key_type hash_type;
288 std::pair< key_type const, mapped_type> m_Value;
290 node_type() = delete;
291 node_type(node_type const&) = delete;
293 template <typename Q, typename... Args>
294 node_type( hasher /*h*/, Q&& key, Args&&... args )
295 : m_Value( std::make_pair( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>(args)...)))
301 hash_type const& operator()(node_type const& node) const
303 return node.m_Value.first;
308 template <typename GC, typename Key, typename T, typename Traits>
309 struct make_feldman_hashmap
312 typedef Key key_type;
313 typedef T mapped_type;
314 typedef Traits original_traits;
317 typedef hash_selector< key_type, mapped_type, typename original_traits::hash > select;
318 typedef typename select::hasher hasher;
319 typedef typename select::hash_type hash_type;
320 typedef typename select::node_type node_type;
322 typedef cds::details::Allocator< node_type, typename original_traits::allocator > cxx_node_allocator;
326 void operator()( node_type * p ) const
328 cxx_node_allocator().Delete( p );
332 struct intrusive_traits: public original_traits
334 typedef typename select::hash_accessor hash_accessor;
335 typedef node_disposer disposer;
338 // Metafunction result
339 typedef cds::intrusive::FeldmanHashSet< GC, node_type, intrusive_traits > type;
341 } // namespace details
344 }} // namespace cds::container
346 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_FELDMAN_HASHMAP_BASE_H