Added stripped uRCU to stress tests
[libcds.git] / test / stress / set / set_type_striped.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8     
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.     
29 */
30
31 #ifndef CDSUNIT_SET_TYPE_STRIPED_H
32 #define CDSUNIT_SET_TYPE_STRIPED_H
33
34 #include "set_type.h"
35
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>
41
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>
50 #endif
51 #include <cds/container/striped_set.h>
52
53 namespace set {
54
55     struct tag_StripedSet;
56
57     template <typename Key, typename Val>
58     struct set_type< tag_StripedSet, Key, Val >: public set_type_base< Key, Val >
59     {
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;
67
68
69         // ***************************************************************************
70         // StripedSet
71
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> >
78                 , Options...
79             >
80         {
81             typedef cc::StripedSet< BucketEntry,
82                 co::mutex_policy< cc::striped_set::striping<> >
83                 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
84                 , Options...
85             > base_class;
86             typedef typename base_class::resizing_policy resizing_policy_t;
87
88             resizing_policy_t   m_placeHolder;
89         public:
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 )) )
93             {}
94
95             /*
96             template <typename Q, typename Less>
97             bool erase_with( Q const& v, Less pred )
98             {
99                 return base_class::erase( v );
100             }
101             */
102
103             // for testing
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;
107         };
108
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> >
114                 , Options...
115             >
116         {
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> >
120                 , Options...
121             > base_class;
122             typedef typename base_class::resizing_policy resizing_policy_t;
123
124             resizing_policy_t   m_placeHolder;
125         public:
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 )) )
129             {}
130
131             /*
132             template <typename Q, typename Less>
133             bool erase_with( Q const& v, Less pred )
134             {
135                 return base_class::erase( v );
136             }
137             */
138
139             // for testing
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;
143         };
144
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<> >
151                 , Options...
152             >
153         {
154             typedef cc::StripedSet< BucketEntry,
155                co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
156                 ,co::mutex_policy< cc::striped_set::striping<> >
157                 , Options...
158             > base_class;
159             typedef typename base_class::resizing_policy resizing_policy_t;
160
161             resizing_policy_t   m_placeHolder;
162         public:
163             template <class Config>
164             StripedHashSet_ord( Config const& cfg )
165                 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nMaxLoadFactor * 1024 )) )
166             {}
167
168             // for testing
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;
172         };
173
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<> >
179                 , Options...
180             >
181         {
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<> >
185                 , Options...
186             > base_class;
187             typedef typename base_class::resizing_policy resizing_policy_t;
188
189             resizing_policy_t   m_placeHolder;
190         public:
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 )))
194             {}
195
196             // for testing
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;
200         };
201
202         typedef StripedHashSet_seq<
203             std::list< key_val >
204             , co::hash< hash2 >
205             , co::less< less >
206         > StripedSet_list;
207
208         typedef StripedHashSet_seq_rational<
209             std::list< key_val >
210             , co::hash< hash2 >
211             , co::less< less >
212         > StripedSet_rational_list;
213
214         typedef StripedHashSet_seq<
215             std::vector< key_val >
216             , co::hash< hash2 >
217             , co::less< less >
218         > StripedSet_vector;
219
220         typedef StripedHashSet_seq_rational<
221             std::vector< key_val >
222             , co::hash< hash2 >
223             , co::less< less >
224         > StripedSet_rational_vector;
225
226 #if BOOST_VERSION >= 104800
227         typedef StripedHashSet_seq<
228             boost::container::slist< key_val >
229             , co::hash< hash2 >
230             , co::less< less >
231         > StripedSet_boost_slist;
232
233         typedef StripedHashSet_seq_rational<
234             boost::container::slist< key_val >
235             , co::hash< hash2 >
236             , co::less< less >
237         > StripedSet_rational_boost_slist;
238
239         typedef StripedHashSet_seq<
240             boost::container::list< key_val >
241             , co::hash< hash2 >
242             , co::less< less >
243         > StripedSet_boost_list;
244
245         typedef StripedHashSet_seq_rational<
246             boost::container::list< key_val >
247             , co::hash< hash2 >
248             , co::less< less >
249         > StripedSet_rational_boost_list;
250
251         typedef StripedHashSet_seq<
252             boost::container::vector< key_val >
253             , co::hash< hash2 >
254             , co::less< less >
255         > StripedSet_boost_vector;
256
257         typedef StripedHashSet_seq_rational<
258             boost::container::vector< key_val >
259             , co::hash< hash2 >
260             , co::less< less >
261         > StripedSet_rational_boost_vector;
262
263         typedef StripedHashSet_seq<
264             boost::container::stable_vector< key_val >
265             , co::hash< hash2 >
266             , co::less< less >
267         > StripedSet_boost_stable_vector;
268
269         typedef StripedHashSet_seq_rational<
270             boost::container::stable_vector< key_val >
271             , co::hash< hash2 >
272             , co::less< less >
273         > StripedSet_rational_boost_stable_vector;
274 #endif
275
276         typedef StripedHashSet_ord<
277             std::set< key_val, less >
278             , co::hash< hash2 >
279         > StripedSet_set;
280
281         typedef StripedHashSet_ord_rational<
282             std::set< key_val, less >
283             , co::hash< hash2 >
284         > StripedSet_rational_set;
285
286         typedef StripedHashSet_ord<
287             std::unordered_set< key_val, hash, equal_to >
288             , co::hash< hash2 >
289         > StripedSet_hashset;
290
291         typedef StripedHashSet_ord_rational<
292             std::unordered_set< key_val, hash, equal_to >
293             , co::hash< hash2 >
294         > StripedSet_rational_hashset;
295
296 #if BOOST_VERSION >= 104800
297         typedef StripedHashSet_ord<
298             boost::container::set< key_val, less >
299             , co::hash< hash2 >
300         > StripedSet_boost_set;
301
302         typedef StripedHashSet_ord_rational<
303             boost::container::set< key_val, less >
304             , co::hash< hash2 >
305         > StripedSet_rational_boost_set;
306
307         typedef StripedHashSet_ord<
308             boost::container::flat_set< key_val, less >
309             , co::hash< hash2 >
310         > StripedSet_boost_flat_set;
311
312         typedef StripedHashSet_ord_rational<
313             boost::container::flat_set< key_val, less >
314             , co::hash< hash2 >
315         > StripedSet_rational_boost_flat_set;
316 #endif
317
318         typedef StripedHashSet_ord<
319             boost::unordered_set< key_val, hash, equal_to >
320             , co::hash< hash2 >
321         > StripedSet_boost_unordered_set;
322
323         typedef StripedHashSet_ord_rational<
324             boost::unordered_set< key_val, hash, equal_to >
325             , co::hash< hash2 >
326         > StripedSet_rational_boost_unordered_set;
327
328
329         // ***************************************************************************
330         // RefinableSet
331
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> >
338             , Options...
339             >
340         {
341             typedef cc::StripedSet< BucketEntry,
342                 co::mutex_policy< cc::striped_set::refinable<> >
343                 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
344                 , Options...
345             > base_class;
346             typedef typename base_class::resizing_policy resizing_policy_t;
347
348             resizing_policy_t   m_placeHolder;
349         public:
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 )) )
353             {}
354
355             /*
356             template <typename Q, typename Less>
357             bool erase_with( Q const& v, Less pred )
358             {
359                 return base_class::erase( v );
360             }
361             */
362
363             // for testing
364             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
365             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
366         };
367
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> >
373             , Options...
374             >
375         {
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> >
379                 , Options...
380             > base_class;
381             typedef typename base_class::resizing_policy resizing_policy_t;
382
383             resizing_policy_t   m_placeHolder;
384         public:
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 )))
388             {}
389
390             // for testing
391             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
392             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
393         };
394
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<> >
401                 , Options...
402             >
403         {
404             typedef cc::StripedSet< BucketEntry,
405                 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
406                 ,co::mutex_policy< cc::striped_set::refinable<> >
407                 , Options...
408             > base_class;
409             typedef typename base_class::resizing_policy resizing_policy_t;
410
411             resizing_policy_t   m_placeHolder;
412         public:
413             template <class Config>
414             RefinableHashSet_ord( Config const& cfg )
415                 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.s_nMaxLoadFactor * 1024 )) )
416             {}
417
418             // for testing
419             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
420             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
421         };
422
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<> >
428                 , Options...
429             >
430         {
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<> >
434                 , Options...
435             > base_class;
436             typedef typename base_class::resizing_policy resizing_policy_t;
437
438             resizing_policy_t   m_placeHolder;
439         public:
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 )))
443             {}
444
445             // for testing
446             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
447             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
448         };
449
450         typedef RefinableHashSet_seq<
451             std::list< key_val >
452             , co::hash< hash2 >
453             , co::less< less >
454         > RefinableSet_list;
455
456         typedef RefinableHashSet_seq_rational<
457             std::list< key_val >
458             , co::hash< hash2 >
459             , co::less< less >
460         > RefinableSet_rational_list;
461
462         typedef RefinableHashSet_seq<
463             std::vector< key_val >
464             , co::hash< hash2 >
465             , co::less< less >
466         > RefinableSet_vector;
467
468         typedef RefinableHashSet_seq_rational<
469             std::vector< key_val >
470             , co::hash< hash2 >
471             , co::less< less >
472         > RefinableSet_rational_vector;
473
474 #if BOOST_VERSION >= 104800
475         typedef RefinableHashSet_seq<
476             boost::container::slist< key_val >
477             , co::hash< hash2 >
478             , co::less< less >
479         > RefinableSet_boost_slist;
480
481         typedef RefinableHashSet_seq_rational<
482             boost::container::slist< key_val >
483             , co::hash< hash2 >
484             , co::less< less >
485         > RefinableSet_rational_boost_slist;
486
487         typedef RefinableHashSet_seq<
488             boost::container::list< key_val >
489             , co::hash< hash2 >
490             , co::less< less >
491         > RefinableSet_boost_list;
492
493         typedef RefinableHashSet_seq_rational<
494             boost::container::list< key_val >
495             , co::hash< hash2 >
496             , co::less< less >
497         > RefinableSet_rational_boost_list;
498
499         typedef RefinableHashSet_seq<
500             boost::container::vector< key_val >
501             , co::hash< hash2 >
502             , co::less< less >
503         > RefinableSet_boost_vector;
504
505         typedef RefinableHashSet_seq_rational<
506             boost::container::vector< key_val >
507             , co::hash< hash2 >
508             , co::less< less >
509         > RefinableSet_rational_boost_vector;
510
511         typedef RefinableHashSet_seq<
512             boost::container::stable_vector< key_val >
513             , co::hash< hash2 >
514             , co::less< less >
515         > RefinableSet_boost_stable_vector;
516
517         typedef RefinableHashSet_seq_rational<
518             boost::container::stable_vector< key_val >
519             , co::hash< hash2 >
520             , co::less< less >
521         > RefinableSet_rational_boost_stable_vector;
522 #endif
523
524         typedef RefinableHashSet_ord<
525             std::set< key_val, less >
526             , co::hash< hash2 >
527         > RefinableSet_set;
528
529         typedef RefinableHashSet_ord_rational<
530             std::set< key_val, less >
531             , co::hash< hash2 >
532         > RefinableSet_rational_set;
533
534         typedef RefinableHashSet_ord<
535             std::unordered_set< key_val, hash, equal_to >
536             , co::hash< hash2 >
537         > RefinableSet_hashset;
538
539         typedef RefinableHashSet_ord_rational<
540             std::unordered_set< key_val, hash, equal_to >
541             , co::hash< hash2 >
542         > RefinableSet_rational_hashset;
543
544 #if BOOST_VERSION >= 104800
545         typedef RefinableHashSet_ord<
546             boost::container::set< key_val, less >
547             , co::hash< hash2 >
548         > RefinableSet_boost_set;
549
550         typedef RefinableHashSet_ord_rational<
551             boost::container::set< key_val, less >
552             , co::hash< hash2 >
553         > RefinableSet_rational_boost_set;
554
555         typedef RefinableHashSet_ord<
556             boost::container::flat_set< key_val, less >
557             , co::hash< hash2 >
558         > RefinableSet_boost_flat_set;
559
560         typedef RefinableHashSet_ord_rational<
561             boost::container::flat_set< key_val, less >
562             , co::hash< hash2 >
563         > RefinableSet_rational_boost_flat_set;
564 #endif
565
566         typedef RefinableHashSet_ord<
567             boost::unordered_set< key_val, hash, equal_to >
568             , co::hash< hash2 >
569         > RefinableSet_boost_unordered_set;
570
571         typedef RefinableHashSet_ord_rational<
572             boost::unordered_set< key_val, hash, equal_to >
573             , co::hash< hash2 >
574         > RefinableSet_rational_boost_unordered_set;
575     };
576
577 } // namespace set
578
579 #define CDSSTRESS_StripedSet_case( fixture, test_case, striped_set_type, key_type, value_type ) \
580     TEST_P( fixture, striped_set_type ) \
581     { \
582         typedef set::set_type< tag_StripedSet, key_type, value_type >::striped_set_type set_type; \
583         test_case<set_type>(); \
584     }
585
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 )
603
604 #endif // #ifndef CDSUNIT_SET_TYPE_STRIPED_H