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 CDSUNIT_SET_TYPE_STRIPED_H
32 #define CDSUNIT_SET_TYPE_STRIPED_H
36 #include <cds/container/striped_set/std_list.h>
37 #include <cds/container/striped_set/std_vector.h>
38 #include <cds/container/striped_set/std_set.h>
39 #include <cds/container/striped_set/std_hash_set.h>
40 #include <cds/container/striped_set/boost_unordered_set.h>
42 #include <boost/version.hpp>
43 #if BOOST_VERSION >= 104800
44 # include <cds/container/striped_set/boost_slist.h>
45 # include <cds/container/striped_set/boost_list.h>
46 # include <cds/container/striped_set/boost_vector.h>
47 # include <cds/container/striped_set/boost_stable_vector.h>
48 # include <cds/container/striped_set/boost_set.h>
49 # include <cds/container/striped_set/boost_flat_set.h>
51 #include <cds/container/striped_set.h>
55 struct tag_StripedSet;
57 template <typename Key, typename Val>
58 struct set_type< tag_StripedSet, Key, Val >: public set_type_base< Key, Val >
60 typedef set_type_base< Key, Val > base_class;
61 typedef typename base_class::key_val key_val;
62 typedef typename base_class::compare compare;
63 typedef typename base_class::less less;
64 typedef typename base_class::equal_to equal_to;
65 typedef typename base_class::hash hash;
66 typedef typename base_class::hash2 hash2;
69 // ***************************************************************************
72 // for sequential containers
73 template <class BucketEntry, typename... Options>
74 class StripedHashSet_seq:
75 public cc::StripedSet< BucketEntry,
76 co::mutex_policy< cc::striped_set::striping<> >
77 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
81 typedef cc::StripedSet< BucketEntry,
82 co::mutex_policy< cc::striped_set::striping<> >
83 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
86 typedef typename base_class::resizing_policy resizing_policy_t;
88 resizing_policy_t m_placeHolder;
90 template <class Config>
91 StripedHashSet_seq( Config const& cfg )
92 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nLoadFactor )) )
96 template <typename Q, typename Less>
97 bool erase_with( Q const& v, Less pred )
99 return base_class::erase( v );
104 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
105 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
106 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
109 template <class BucketEntry, typename... Options>
110 class StripedHashSet_seq_rational:
111 public cc::StripedSet< BucketEntry,
112 co::mutex_policy< cc::striped_set::striping<> >
113 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
117 typedef cc::StripedSet< BucketEntry,
118 co::mutex_policy< cc::striped_set::striping<> >
119 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
122 typedef typename base_class::resizing_policy resizing_policy_t;
124 resizing_policy_t m_placeHolder;
126 template <class Config>
127 StripedHashSet_seq_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
128 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( 1, cfg.s_nLoadFactor )) )
132 template <typename Q, typename Less>
133 bool erase_with( Q const& v, Less pred )
135 return base_class::erase( v );
140 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
141 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
142 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
145 // for non-sequential ordered containers
146 template <class BucketEntry, typename... Options>
147 class StripedHashSet_ord:
148 public cc::StripedSet< BucketEntry,
149 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
150 ,co::mutex_policy< cc::striped_set::striping<> >
154 typedef cc::StripedSet< BucketEntry,
155 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
156 ,co::mutex_policy< cc::striped_set::striping<> >
159 typedef typename base_class::resizing_policy resizing_policy_t;
161 resizing_policy_t m_placeHolder;
163 template <class Config>
164 StripedHashSet_ord( Config const& cfg )
165 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nMaxLoadFactor * 1024 )) )
169 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
170 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
171 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
174 template <class BucketEntry, typename... Options>
175 class StripedHashSet_ord_rational:
176 public cc::StripedSet< BucketEntry,
177 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
178 ,co::mutex_policy< cc::striped_set::striping<> >
182 typedef cc::StripedSet< BucketEntry,
183 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
184 ,co::mutex_policy< cc::striped_set::striping<> >
187 typedef typename base_class::resizing_policy resizing_policy_t;
189 resizing_policy_t m_placeHolder;
191 template <class Config>
192 StripedHashSet_ord_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
193 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( 1024, cfg.s_nLoadFactor )))
197 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
198 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
199 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
202 typedef StripedHashSet_seq<
208 typedef StripedHashSet_seq_rational<
212 > StripedSet_rational_list;
214 typedef StripedHashSet_seq<
215 std::vector< key_val >
220 typedef StripedHashSet_seq_rational<
221 std::vector< key_val >
224 > StripedSet_rational_vector;
226 #if BOOST_VERSION >= 104800
227 typedef StripedHashSet_seq<
228 boost::container::slist< key_val >
231 > StripedSet_boost_slist;
233 typedef StripedHashSet_seq_rational<
234 boost::container::slist< key_val >
237 > StripedSet_rational_boost_slist;
239 typedef StripedHashSet_seq<
240 boost::container::list< key_val >
243 > StripedSet_boost_list;
245 typedef StripedHashSet_seq_rational<
246 boost::container::list< key_val >
249 > StripedSet_rational_boost_list;
251 typedef StripedHashSet_seq<
252 boost::container::vector< key_val >
255 > StripedSet_boost_vector;
257 typedef StripedHashSet_seq_rational<
258 boost::container::vector< key_val >
261 > StripedSet_rational_boost_vector;
263 typedef StripedHashSet_seq<
264 boost::container::stable_vector< key_val >
267 > StripedSet_boost_stable_vector;
269 typedef StripedHashSet_seq_rational<
270 boost::container::stable_vector< key_val >
273 > StripedSet_rational_boost_stable_vector;
276 typedef StripedHashSet_ord<
277 std::set< key_val, less >
281 typedef StripedHashSet_ord_rational<
282 std::set< key_val, less >
284 > StripedSet_rational_set;
286 typedef StripedHashSet_ord<
287 std::unordered_set< key_val, hash, equal_to >
289 > StripedSet_hashset;
291 typedef StripedHashSet_ord_rational<
292 std::unordered_set< key_val, hash, equal_to >
294 > StripedSet_rational_hashset;
296 #if BOOST_VERSION >= 104800
297 typedef StripedHashSet_ord<
298 boost::container::set< key_val, less >
300 > StripedSet_boost_set;
302 typedef StripedHashSet_ord_rational<
303 boost::container::set< key_val, less >
305 > StripedSet_rational_boost_set;
307 typedef StripedHashSet_ord<
308 boost::container::flat_set< key_val, less >
310 > StripedSet_boost_flat_set;
312 typedef StripedHashSet_ord_rational<
313 boost::container::flat_set< key_val, less >
315 > StripedSet_rational_boost_flat_set;
318 typedef StripedHashSet_ord<
319 boost::unordered_set< key_val, hash, equal_to >
321 > StripedSet_boost_unordered_set;
323 typedef StripedHashSet_ord_rational<
324 boost::unordered_set< key_val, hash, equal_to >
326 > StripedSet_rational_boost_unordered_set;
329 // ***************************************************************************
332 // for sequential containers
333 template <class BucketEntry, typename... Options>
334 class RefinableHashSet_seq:
335 public cc::StripedSet< BucketEntry,
336 co::mutex_policy< cc::striped_set::refinable<> >
337 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
341 typedef cc::StripedSet< BucketEntry,
342 co::mutex_policy< cc::striped_set::refinable<> >
343 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
346 typedef typename base_class::resizing_policy resizing_policy_t;
348 resizing_policy_t m_placeHolder;
350 template <class Config>
351 RefinableHashSet_seq( Config const& cfg )
352 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nLoadFactor )) )
356 template <typename Q, typename Less>
357 bool erase_with( Q const& v, Less pred )
359 return base_class::erase( v );
364 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
365 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
368 template <class BucketEntry, typename... Options>
369 class RefinableHashSet_seq_rational:
370 public cc::StripedSet< BucketEntry,
371 co::mutex_policy< cc::striped_set::refinable<> >
372 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
376 typedef cc::StripedSet< BucketEntry,
377 co::mutex_policy< cc::striped_set::refinable<> >
378 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
381 typedef typename base_class::resizing_policy resizing_policy_t;
383 resizing_policy_t m_placeHolder;
385 template <class Config>
386 RefinableHashSet_seq_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
387 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( 1, cfg.s_nLoadFactor )))
391 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
392 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
395 // for non-sequential ordered containers
396 template <class BucketEntry, typename... Options>
397 class RefinableHashSet_ord:
398 public cc::StripedSet< BucketEntry,
399 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
400 ,co::mutex_policy< cc::striped_set::refinable<> >
404 typedef cc::StripedSet< BucketEntry,
405 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
406 ,co::mutex_policy< cc::striped_set::refinable<> >
409 typedef typename base_class::resizing_policy resizing_policy_t;
411 resizing_policy_t m_placeHolder;
413 template <class Config>
414 RefinableHashSet_ord( Config const& cfg )
415 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nMaxLoadFactor * 1024 )) )
419 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
420 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
423 template <class BucketEntry, typename... Options>
424 class RefinableHashSet_ord_rational:
425 public cc::StripedSet< BucketEntry,
426 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
427 ,co::mutex_policy< cc::striped_set::refinable<> >
431 typedef cc::StripedSet< BucketEntry,
432 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
433 ,co::mutex_policy< cc::striped_set::refinable<> >
436 typedef typename base_class::resizing_policy resizing_policy_t;
438 resizing_policy_t m_placeHolder;
440 template <class Config>
441 RefinableHashSet_ord_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
442 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( 1024, cfg.s_nLoadFactor )))
446 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
447 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
450 typedef RefinableHashSet_seq<
456 typedef RefinableHashSet_seq_rational<
460 > RefinableSet_rational_list;
462 typedef RefinableHashSet_seq<
463 std::vector< key_val >
466 > RefinableSet_vector;
468 typedef RefinableHashSet_seq_rational<
469 std::vector< key_val >
472 > RefinableSet_rational_vector;
474 #if BOOST_VERSION >= 104800
475 typedef RefinableHashSet_seq<
476 boost::container::slist< key_val >
479 > RefinableSet_boost_slist;
481 typedef RefinableHashSet_seq_rational<
482 boost::container::slist< key_val >
485 > RefinableSet_rational_boost_slist;
487 typedef RefinableHashSet_seq<
488 boost::container::list< key_val >
491 > RefinableSet_boost_list;
493 typedef RefinableHashSet_seq_rational<
494 boost::container::list< key_val >
497 > RefinableSet_rational_boost_list;
499 typedef RefinableHashSet_seq<
500 boost::container::vector< key_val >
503 > RefinableSet_boost_vector;
505 typedef RefinableHashSet_seq_rational<
506 boost::container::vector< key_val >
509 > RefinableSet_rational_boost_vector;
511 typedef RefinableHashSet_seq<
512 boost::container::stable_vector< key_val >
515 > RefinableSet_boost_stable_vector;
517 typedef RefinableHashSet_seq_rational<
518 boost::container::stable_vector< key_val >
521 > RefinableSet_rational_boost_stable_vector;
524 typedef RefinableHashSet_ord<
525 std::set< key_val, less >
529 typedef RefinableHashSet_ord_rational<
530 std::set< key_val, less >
532 > RefinableSet_rational_set;
534 typedef RefinableHashSet_ord<
535 std::unordered_set< key_val, hash, equal_to >
537 > RefinableSet_hashset;
539 typedef RefinableHashSet_ord_rational<
540 std::unordered_set< key_val, hash, equal_to >
542 > RefinableSet_rational_hashset;
544 #if BOOST_VERSION >= 104800
545 typedef RefinableHashSet_ord<
546 boost::container::set< key_val, less >
548 > RefinableSet_boost_set;
550 typedef RefinableHashSet_ord_rational<
551 boost::container::set< key_val, less >
553 > RefinableSet_rational_boost_set;
555 typedef RefinableHashSet_ord<
556 boost::container::flat_set< key_val, less >
558 > RefinableSet_boost_flat_set;
560 typedef RefinableHashSet_ord_rational<
561 boost::container::flat_set< key_val, less >
563 > RefinableSet_rational_boost_flat_set;
566 typedef RefinableHashSet_ord<
567 boost::unordered_set< key_val, hash, equal_to >
569 > RefinableSet_boost_unordered_set;
571 typedef RefinableHashSet_ord_rational<
572 boost::unordered_set< key_val, hash, equal_to >
574 > RefinableSet_rational_boost_unordered_set;
579 #define CDSSTRESS_StripedSet_case( fixture, test_case, striped_set_type, key_type, value_type ) \
580 TEST_P( fixture, striped_set_type ) \
582 typedef set::set_type< tag_StripedSet, key_type, value_type >::striped_set_type set_type; \
583 test_case<set_type>(); \
586 #define CDSSTRESS_StripedSet( fixture, test_case, key_type, value_type ) \
587 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_list, key_type, value_type ) \
588 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_list, key_type, value_type ) \
589 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_vector, key_type, value_type ) \
590 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_vector, key_type, value_type ) \
591 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_set, key_type, value_type ) \
592 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_set, key_type, value_type ) \
593 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_hashset, key_type, value_type ) \
594 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_hashset, key_type, value_type ) \
595 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_list, key_type, value_type ) \
596 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_list, key_type, value_type ) \
597 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_vector, key_type, value_type ) \
598 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_vector, key_type, value_type ) \
599 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_set, key_type, value_type ) \
600 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_set, key_type, value_type ) \
601 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_hashset, key_type, value_type ) \
602 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_hashset, key_type, value_type )
604 #endif // #ifndef CDSUNIT_SET_TYPE_STRIPED_H