2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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 )))
95 empty_stat statistics() const
101 template <typename Q, typename Less>
102 bool erase_with( Q const& v, Less pred )
104 return base_class::erase( v );
109 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
110 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
111 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
114 template <class BucketEntry, typename... Options>
115 class StripedHashSet_seq_rational:
116 public cc::StripedSet< BucketEntry,
117 co::mutex_policy< cc::striped_set::striping<> >
118 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
122 typedef cc::StripedSet< BucketEntry,
123 co::mutex_policy< cc::striped_set::striping<> >
124 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
127 typedef typename base_class::resizing_policy resizing_policy_t;
129 resizing_policy_t m_placeHolder;
131 template <class Config>
132 StripedHashSet_seq_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
133 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( 1, cfg.s_nLoadFactor )))
136 empty_stat statistics() const
142 template <typename Q, typename Less>
143 bool erase_with( Q const& v, Less pred )
145 return base_class::erase( v );
150 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
151 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
152 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
155 // for non-sequential ordered containers
156 template <class BucketEntry, typename... Options>
157 class StripedHashSet_ord:
158 public cc::StripedSet< BucketEntry,
159 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
160 ,co::mutex_policy< cc::striped_set::striping<> >
164 typedef cc::StripedSet< BucketEntry,
165 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
166 ,co::mutex_policy< cc::striped_set::striping<> >
169 typedef typename base_class::resizing_policy resizing_policy_t;
171 resizing_policy_t m_placeHolder;
173 template <class Config>
174 StripedHashSet_ord( Config const& cfg )
175 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nMaxLoadFactor * 1024 )))
178 empty_stat statistics() const
184 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
185 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
186 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
189 template <class BucketEntry, typename... Options>
190 class StripedHashSet_ord_rational:
191 public cc::StripedSet< BucketEntry,
192 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
193 ,co::mutex_policy< cc::striped_set::striping<> >
197 typedef cc::StripedSet< BucketEntry,
198 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
199 ,co::mutex_policy< cc::striped_set::striping<> >
202 typedef typename base_class::resizing_policy resizing_policy_t;
204 resizing_policy_t m_placeHolder;
206 template <class Config>
207 StripedHashSet_ord_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
208 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( 1024, cfg.s_nLoadFactor )))
211 empty_stat statistics() const
217 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
218 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
219 static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
222 typedef StripedHashSet_seq<
228 typedef StripedHashSet_seq_rational<
232 > StripedSet_rational_list;
234 typedef StripedHashSet_seq<
235 std::vector< key_val >
240 typedef StripedHashSet_seq_rational<
241 std::vector< key_val >
244 > StripedSet_rational_vector;
246 #if BOOST_VERSION >= 104800
247 typedef StripedHashSet_seq<
248 boost::container::slist< key_val >
251 > StripedSet_boost_slist;
253 typedef StripedHashSet_seq_rational<
254 boost::container::slist< key_val >
257 > StripedSet_rational_boost_slist;
259 typedef StripedHashSet_seq<
260 boost::container::list< key_val >
263 > StripedSet_boost_list;
265 typedef StripedHashSet_seq_rational<
266 boost::container::list< key_val >
269 > StripedSet_rational_boost_list;
271 typedef StripedHashSet_seq<
272 boost::container::vector< key_val >
275 > StripedSet_boost_vector;
277 typedef StripedHashSet_seq_rational<
278 boost::container::vector< key_val >
281 > StripedSet_rational_boost_vector;
283 typedef StripedHashSet_seq<
284 boost::container::stable_vector< key_val >
287 > StripedSet_boost_stable_vector;
289 typedef StripedHashSet_seq_rational<
290 boost::container::stable_vector< key_val >
293 > StripedSet_rational_boost_stable_vector;
296 typedef StripedHashSet_ord<
297 std::set< key_val, less >
301 typedef StripedHashSet_ord_rational<
302 std::set< key_val, less >
304 > StripedSet_rational_set;
306 typedef StripedHashSet_ord<
307 std::unordered_set< key_val, hash, equal_to >
309 > StripedSet_hashset;
311 typedef StripedHashSet_ord_rational<
312 std::unordered_set< key_val, hash, equal_to >
314 > StripedSet_rational_hashset;
316 #if BOOST_VERSION >= 104800
317 typedef StripedHashSet_ord<
318 boost::container::set< key_val, less >
320 > StripedSet_boost_set;
322 typedef StripedHashSet_ord_rational<
323 boost::container::set< key_val, less >
325 > StripedSet_rational_boost_set;
327 typedef StripedHashSet_ord<
328 boost::container::flat_set< key_val, less >
330 > StripedSet_boost_flat_set;
332 typedef StripedHashSet_ord_rational<
333 boost::container::flat_set< key_val, less >
335 > StripedSet_rational_boost_flat_set;
338 typedef StripedHashSet_ord<
339 boost::unordered_set< key_val, hash, equal_to >
341 > StripedSet_boost_unordered_set;
343 typedef StripedHashSet_ord_rational<
344 boost::unordered_set< key_val, hash, equal_to >
346 > StripedSet_rational_boost_unordered_set;
349 // ***************************************************************************
352 // for sequential containers
353 template <class BucketEntry, typename... Options>
354 class RefinableHashSet_seq:
355 public cc::StripedSet< BucketEntry,
356 co::mutex_policy< cc::striped_set::refinable<> >
357 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
361 typedef cc::StripedSet< BucketEntry,
362 co::mutex_policy< cc::striped_set::refinable<> >
363 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
366 typedef typename base_class::resizing_policy resizing_policy_t;
368 resizing_policy_t m_placeHolder;
370 template <class Config>
371 RefinableHashSet_seq( Config const& cfg )
372 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nLoadFactor )))
375 empty_stat statistics() const
381 template <typename Q, typename Less>
382 bool erase_with( Q const& v, Less pred )
384 return base_class::erase( v );
389 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
390 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
393 template <class BucketEntry, typename... Options>
394 class RefinableHashSet_seq_rational:
395 public cc::StripedSet< BucketEntry,
396 co::mutex_policy< cc::striped_set::refinable<> >
397 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
401 typedef cc::StripedSet< BucketEntry,
402 co::mutex_policy< cc::striped_set::refinable<> >
403 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
406 typedef typename base_class::resizing_policy resizing_policy_t;
408 resizing_policy_t m_placeHolder;
410 template <class Config>
411 RefinableHashSet_seq_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
412 : base_class( cfg.s_nSetSize / cfg.s_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( 1, cfg.s_nLoadFactor )))
415 empty_stat statistics() const
421 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
422 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
425 // for non-sequential ordered containers
426 template <class BucketEntry, typename... Options>
427 class RefinableHashSet_ord:
428 public cc::StripedSet< BucketEntry,
429 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
430 ,co::mutex_policy< cc::striped_set::refinable<> >
434 typedef cc::StripedSet< BucketEntry,
435 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
436 ,co::mutex_policy< cc::striped_set::refinable<> >
439 typedef typename base_class::resizing_policy resizing_policy_t;
441 resizing_policy_t m_placeHolder;
443 template <class Config>
444 RefinableHashSet_ord( Config const& cfg )
445 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nMaxLoadFactor * 1024 )))
448 empty_stat statistics() const
454 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
455 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
458 template <class BucketEntry, typename... Options>
459 class RefinableHashSet_ord_rational:
460 public cc::StripedSet< BucketEntry,
461 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
462 ,co::mutex_policy< cc::striped_set::refinable<> >
466 typedef cc::StripedSet< BucketEntry,
467 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
468 ,co::mutex_policy< cc::striped_set::refinable<> >
471 typedef typename base_class::resizing_policy resizing_policy_t;
473 resizing_policy_t m_placeHolder;
475 template <class Config>
476 RefinableHashSet_ord_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
477 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( 1024, cfg.s_nLoadFactor )))
480 empty_stat statistics() const
486 static CDS_CONSTEXPR bool const c_bExtractSupported = false;
487 static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
490 typedef RefinableHashSet_seq<
496 typedef RefinableHashSet_seq_rational<
500 > RefinableSet_rational_list;
502 typedef RefinableHashSet_seq<
503 std::vector< key_val >
506 > RefinableSet_vector;
508 typedef RefinableHashSet_seq_rational<
509 std::vector< key_val >
512 > RefinableSet_rational_vector;
514 #if BOOST_VERSION >= 104800
515 typedef RefinableHashSet_seq<
516 boost::container::slist< key_val >
519 > RefinableSet_boost_slist;
521 typedef RefinableHashSet_seq_rational<
522 boost::container::slist< key_val >
525 > RefinableSet_rational_boost_slist;
527 typedef RefinableHashSet_seq<
528 boost::container::list< key_val >
531 > RefinableSet_boost_list;
533 typedef RefinableHashSet_seq_rational<
534 boost::container::list< key_val >
537 > RefinableSet_rational_boost_list;
539 typedef RefinableHashSet_seq<
540 boost::container::vector< key_val >
543 > RefinableSet_boost_vector;
545 typedef RefinableHashSet_seq_rational<
546 boost::container::vector< key_val >
549 > RefinableSet_rational_boost_vector;
551 typedef RefinableHashSet_seq<
552 boost::container::stable_vector< key_val >
555 > RefinableSet_boost_stable_vector;
557 typedef RefinableHashSet_seq_rational<
558 boost::container::stable_vector< key_val >
561 > RefinableSet_rational_boost_stable_vector;
564 typedef RefinableHashSet_ord<
565 std::set< key_val, less >
569 typedef RefinableHashSet_ord_rational<
570 std::set< key_val, less >
572 > RefinableSet_rational_set;
574 typedef RefinableHashSet_ord<
575 std::unordered_set< key_val, hash, equal_to >
577 > RefinableSet_hashset;
579 typedef RefinableHashSet_ord_rational<
580 std::unordered_set< key_val, hash, equal_to >
582 > RefinableSet_rational_hashset;
584 #if BOOST_VERSION >= 104800
585 typedef RefinableHashSet_ord<
586 boost::container::set< key_val, less >
588 > RefinableSet_boost_set;
590 typedef RefinableHashSet_ord_rational<
591 boost::container::set< key_val, less >
593 > RefinableSet_rational_boost_set;
595 typedef RefinableHashSet_ord<
596 boost::container::flat_set< key_val, less >
598 > RefinableSet_boost_flat_set;
600 typedef RefinableHashSet_ord_rational<
601 boost::container::flat_set< key_val, less >
603 > RefinableSet_rational_boost_flat_set;
606 typedef RefinableHashSet_ord<
607 boost::unordered_set< key_val, hash, equal_to >
609 > RefinableSet_boost_unordered_set;
611 typedef RefinableHashSet_ord_rational<
612 boost::unordered_set< key_val, hash, equal_to >
614 > RefinableSet_rational_boost_unordered_set;
619 #define CDSSTRESS_StripedSet_case( fixture, test_case, striped_set_type, key_type, value_type ) \
620 TEST_P( fixture, striped_set_type ) \
622 typedef set::set_type< tag_StripedSet, key_type, value_type >::striped_set_type set_type; \
623 test_case<set_type>(); \
626 #define CDSSTRESS_StripedSet( fixture, test_case, key_type, value_type ) \
627 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_list, key_type, value_type ) \
628 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_list, key_type, value_type ) \
629 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_vector, key_type, value_type ) \
630 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_vector, key_type, value_type ) \
631 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_set, key_type, value_type ) \
632 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_set, key_type, value_type ) \
633 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_hashset, key_type, value_type ) \
634 CDSSTRESS_StripedSet_case( fixture, test_case, StripedSet_rational_hashset, key_type, value_type ) \
635 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_list, key_type, value_type ) \
636 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_list, key_type, value_type ) \
637 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_vector, key_type, value_type ) \
638 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_vector, key_type, value_type ) \
639 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_set, key_type, value_type ) \
640 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_set, key_type, value_type ) \
641 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_hashset, key_type, value_type ) \
642 CDSSTRESS_StripedSet_case( fixture, test_case, RefinableSet_rational_hashset, key_type, value_type )
644 #endif // #ifndef CDSUNIT_SET_TYPE_STRIPED_H