3 #ifndef CDSUNIT_SET_TYPE_MICHAEL_H
4 #define CDSUNIT_SET_TYPE_MICHAEL_H
6 #include "set2/set_type.h"
8 #include <cds/container/multilevel_hashset_hp.h>
9 #include <cds/container/multilevel_hashset_dhp.h>
10 #include <cds/container/multilevel_hashset_rcu.h>
12 #include "print_multilevel_hashset_stat.h"
13 #include "hashing/hash_func.h"
17 template <class GC, typename T, typename Traits = cc::multilevel_hashset::traits>
18 class MultiLevelHashSet : public cc::MultiLevelHashSet< GC, T, Traits >
20 typedef cc::MultiLevelHashSet< GC, T, Traits > base_class;
23 struct get_extracted_ptr
25 typedef typename base_class::guarded_ptr extracted_ptr;
28 template <typename RCU>
29 struct get_extracted_ptr<cds::urcu::gc<RCU>>
31 typedef typename base_class::exempt_ptr extracted_ptr;
35 typedef typename T::hasher hasher ;
36 typedef typename get_extracted_ptr<GC>::extracted_ptr extracted_ptr;
38 template <class Config>
39 MultiLevelHashSet( Config const& cfg )
40 : base_class( cfg.c_nMultiLevelSet_HeadBits, cfg.c_nMultiLevelSet_ArrayBits )
44 bool erase( Q const& key )
46 return base_class::erase( hasher()( key ));
49 template <typename Q, typename Func>
50 bool erase( Q const& key, Func f )
52 return base_class::erase( hasher()( key ), f );
56 extracted_ptr extract(Q const& key)
58 return base_class::extract( hasher()(key) );
62 bool contains( Q const& key )
64 return base_class::contains( hasher()(key) );
68 static CDS_CONSTEXPR bool const c_bExtractSupported = true;
69 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
70 static CDS_CONSTEXPR bool const c_bEraseExactKey = true;
73 struct tag_MultiLevelHashSet;
75 template <typename Key, typename Val>
76 struct set_type< tag_MultiLevelHashSet, Key, Val >: public set_type_base< Key, Val >
78 typedef set_type_base< Key, Val > base_class;
79 typedef typename base_class::compare compare;
80 typedef typename base_class::less less;
81 typedef typename base_class::hash hash;
82 typedef typename base_class::key_type key_type;
83 typedef typename base_class::value_type value_type;
85 template <typename Hasher>
88 typedef Hasher hasher;
89 typedef typename hasher::hash_type type;
92 template <typename TH>
93 struct hash_type<std::hash<TH>>
95 typedef std::hash<TH> hasher;
99 template <typename Hasher>
100 struct key_val: base_class::key_val
102 typedef typename base_class::key_val base;
103 typedef Hasher hasher;
104 typedef typename hash_type<hasher>::type hash_type;
108 /*explicit*/ key_val( key_type const& k ): base(k), hash( hasher()( k )) {}
109 key_val( key_type const& k, value_type const& v ): base(k, v), hash( hasher()( k )) {}
111 template <typename K>
112 /*explicit*/ key_val( K const& k ): base(k), hash( hasher()( k )) {}
114 template <typename K, typename T>
115 key_val( K const& k, T const& v ): base(k, v), hash( hasher()( k )) {}
118 struct default_traits : public cc::multilevel_hashset::traits
120 struct hash_accessor {
121 template <typename Hasher>
122 typename key_val<Hasher>::hash_type const& operator()( key_val<Hasher> const& kv )
129 typedef MultiLevelHashSet< cds::gc::HP, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_hp_stdhash;
130 typedef MultiLevelHashSet< cds::gc::DHP, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_dhp_stdhash;
131 typedef MultiLevelHashSet< rcu_gpi, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_rcu_gpi_stdhash;
132 typedef MultiLevelHashSet< rcu_gpb, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_rcu_gpb_stdhash;
133 typedef MultiLevelHashSet< rcu_gpt, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_rcu_gpt_stdhash;
134 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
135 typedef MultiLevelHashSet< rcu_shb, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_rcu_shb_stdhash;
136 typedef MultiLevelHashSet< rcu_sht, key_val<std::hash<key_type>>, default_traits > MultiLevelHashSet_rcu_sht_stdhash;
139 struct traits_MultiLevelHashSet_stat: public cc::multilevel_hashset::make_traits<
140 co::type_traits< default_traits >,
141 co::stat< cc::multilevel_hashset::stat<>>
145 typedef MultiLevelHashSet< cds::gc::HP, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_hp_stdhash_stat;
146 typedef MultiLevelHashSet< cds::gc::DHP, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_dhp_stdhash_stat;
147 typedef MultiLevelHashSet< rcu_gpi, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_rcu_gpi_stdhash_stat;
148 typedef MultiLevelHashSet< rcu_gpb, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_rcu_gpb_stdhash_stat;
149 typedef MultiLevelHashSet< rcu_gpt, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_rcu_gpt_stdhash_stat;
150 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
151 typedef MultiLevelHashSet< rcu_shb, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_rcu_shb_stdhash_stat;
152 typedef MultiLevelHashSet< rcu_sht, key_val<std::hash<key_type>>, traits_MultiLevelHashSet_stat > MultiLevelHashSet_rcu_sht_stdhash_stat;
156 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_hp_sha256;
157 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_dhp_sha256;
158 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_rcu_gpi_sha256;
159 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_rcu_gpb_sha256;
160 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_rcu_gpt_sha256;
161 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
162 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_rcu_shb_sha256;
163 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::sha256>, default_traits > MultiLevelHashSet_rcu_sht_sha256;
166 struct traits_MultiLevelHashSet_sha256_stat : public default_traits
168 typedef cc::multilevel_hashset::stat<> stat;
170 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_hp_sha256_stat;
171 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_dhp_sha256_stat;
172 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_rcu_gpi_sha256_stat;
173 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_rcu_gpb_sha256_stat;
174 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_rcu_gpt_sha256_stat;
175 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
176 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_rcu_shb_sha256_stat;
177 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::sha256>, traits_MultiLevelHashSet_sha256_stat > MultiLevelHashSet_rcu_sht_sha256_stat;
181 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_hp_md5;
182 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_dhp_md5;
183 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_rcu_gpi_md5;
184 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_rcu_gpb_md5;
185 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_rcu_gpt_md5;
186 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
187 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_rcu_shb_md5;
188 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::md5>, default_traits > MultiLevelHashSet_rcu_sht_md5;
191 struct traits_MultiLevelHashSet_md5_stat : public default_traits
193 typedef cc::multilevel_hashset::stat<> stat;
195 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_hp_md5_stat;
196 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_dhp_md5_stat;
197 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_rcu_gpi_md5_stat;
198 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_rcu_gpb_md5_stat;
199 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_rcu_gpt_md5_stat;
200 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
201 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_rcu_shb_md5_stat;
202 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::md5>, traits_MultiLevelHashSet_md5_stat > MultiLevelHashSet_rcu_sht_md5_stat;
206 #if CDS_BUILD_BITS == 64
207 struct traits_MultiLevelHashSet_city64 : public default_traits
209 typedef ::hashing::city64::less less;
211 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_hp_city64;
212 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_dhp_city64;
213 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_rcu_gpi_city64;
214 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_rcu_gpb_city64;
215 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_rcu_gpt_city64;
216 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
217 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_rcu_shb_city64;
218 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64 > MultiLevelHashSet_rcu_sht_city64;
221 struct traits_MultiLevelHashSet_city64_stat : public traits_MultiLevelHashSet_city64
223 typedef cc::multilevel_hashset::stat<> stat;
225 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_hp_city64_stat;
226 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_dhp_city64_stat;
227 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_rcu_gpi_city64_stat;
228 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_rcu_gpb_city64_stat;
229 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_rcu_gpt_city64_stat;
230 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
231 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_rcu_shb_city64_stat;
232 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::city64>, traits_MultiLevelHashSet_city64_stat > MultiLevelHashSet_rcu_sht_city64_stat;
235 struct traits_MultiLevelHashSet_city128 : public default_traits
237 typedef ::hashing::city128::less less;
239 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_hp_city128;
240 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_dhp_city128;
241 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_rcu_gpi_city128;
242 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_rcu_gpb_city128;
243 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_rcu_gpt_city128;
244 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
245 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_rcu_shb_city128;
246 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128 > MultiLevelHashSet_rcu_sht_city128;
249 struct traits_MultiLevelHashSet_city128_stat : public traits_MultiLevelHashSet_city128
251 typedef cc::multilevel_hashset::stat<> stat;
253 typedef MultiLevelHashSet< cds::gc::HP, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_hp_city128_stat;
254 typedef MultiLevelHashSet< cds::gc::DHP, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_dhp_city128_stat;
255 typedef MultiLevelHashSet< rcu_gpi, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_rcu_gpi_city128_stat;
256 typedef MultiLevelHashSet< rcu_gpb, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_rcu_gpb_city128_stat;
257 typedef MultiLevelHashSet< rcu_gpt, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_rcu_gpt_city128_stat;
258 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
259 typedef MultiLevelHashSet< rcu_shb, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_rcu_shb_city128_stat;
260 typedef MultiLevelHashSet< rcu_sht, key_val<::hashing::city128>, traits_MultiLevelHashSet_city128_stat > MultiLevelHashSet_rcu_sht_city128_stat;
263 #endif // #if CDS_BUILD_BITS == 64
266 // for fixed-sized key
267 // No hash function is necessary
269 struct fixed_sized_key
271 typedef typename set_type_base< Key, Val >::key_type key_type;
272 struct key_val : public set_type_base< Key, Val >::key_val
274 typedef typename set_type_base< Key, Val >::key_val base_class;
276 /*explicit*/ key_val(key_type const& k) : base_class(k) {}
277 key_val(key_type const& k, value_type const& v) : base_class(k, v) {}
279 template <typename K>
280 /*explicit*/ key_val(K const& k) : base_class(k) {}
282 template <typename K, typename T>
283 key_val(K const& k, T const& v) : base_class(k, v) {}
287 template <typename Q>
288 key_type operator()( Q const& k ) const
290 return key_type( k );
295 struct traits : public cc::multilevel_hashset::traits
297 struct hash_accessor {
298 key_type operator()(key_val const& kv)
305 struct traits_stat : public traits
307 typedef cc::multilevel_hashset::stat<> stat;
311 typedef MultiLevelHashSet< cds::gc::HP, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_hp_fixed;
312 typedef MultiLevelHashSet< cds::gc::DHP, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_dhp_fixed;
313 typedef MultiLevelHashSet< rcu_gpi, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_rcu_gpi_fixed;
314 typedef MultiLevelHashSet< rcu_gpb, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_rcu_gpb_fixed;
315 typedef MultiLevelHashSet< rcu_gpt, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_rcu_gpt_fixed;
316 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
317 typedef MultiLevelHashSet< rcu_shb, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_rcu_shb_fixed;
318 typedef MultiLevelHashSet< rcu_sht, typename fixed_sized_key::key_val, typename fixed_sized_key::traits > MultiLevelHashSet_rcu_sht_fixed;
321 typedef MultiLevelHashSet< cds::gc::HP, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_hp_fixed_stat;
322 typedef MultiLevelHashSet< cds::gc::DHP, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_dhp_fixed_stat;
323 typedef MultiLevelHashSet< rcu_gpi, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_rcu_gpi_fixed_stat;
324 typedef MultiLevelHashSet< rcu_gpb, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_rcu_gpb_fixed_stat;
325 typedef MultiLevelHashSet< rcu_gpt, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_rcu_gpt_fixed_stat;
326 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
327 typedef MultiLevelHashSet< rcu_shb, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_rcu_shb_fixed_stat;
328 typedef MultiLevelHashSet< rcu_sht, typename fixed_sized_key::key_val, typename fixed_sized_key::traits_stat > MultiLevelHashSet_rcu_sht_fixed_stat;
333 template <typename GC, typename T, typename Traits >
334 static inline void print_stat( MultiLevelHashSet< GC, T, Traits > const& s )
336 CPPUNIT_MSG( s.statistics() );
341 #endif // #ifndef CDSUNIT_SET_TYPE_MICHAEL_H