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 "set2/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 set2 {
  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.c_nSetSize / cfg.c_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( cfg.c_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.c_nSetSize / cfg.c_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( 1, cfg.c_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.c_nMaxLoadFactor * 1024 )) )
 166             {}
 167
 168             /*
 169             template <typename Q, typename Less>
 170             bool erase_with( Q const& v, Less pred )
 171             {
 172                 return base_class::erase( v );
 173             }
 174             */
 175
 176             // for testing
 177             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
 178             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
 179             static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
 180         };
 181
 182         template <class BucketEntry, typename... Options>
 183         class StripedHashSet_ord_rational:
 184             public cc::StripedSet< BucketEntry,
 185                 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
 186                 ,co::mutex_policy< cc::striped_set::striping<> >
 187                 , Options...
 188             >
 189         {
 190             typedef cc::StripedSet< BucketEntry,
 191                co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
 192                 ,co::mutex_policy< cc::striped_set::striping<> >
 193                 , Options...
 194             > base_class;
 195             typedef typename base_class::resizing_policy resizing_policy_t;
 196
 197             resizing_policy_t   m_placeHolder;
 198         public:
 199             template <class Config>
 200             StripedHashSet_ord_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
 201                 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( 1024, cfg.c_nLoadFactor )))
 202             {}
 203
 204             /*
 205             template <typename Q, typename Less>
 206             bool erase_with( Q const& v, Less pred )
 207             {
 208                 return base_class::erase( v );
 209             }
 210             */
 211
 212             // for testing
 213             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
 214             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
 215             static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
 216         };
 217
 218         typedef StripedHashSet_seq<
 219             std::list< key_val >
 220             , co::hash< hash2 >
 221             , co::less< less >
 222         > StripedSet_list;
 223
 224         typedef StripedHashSet_seq_rational<
 225             std::list< key_val >
 226             , co::hash< hash2 >
 227             , co::less< less >
 228         > StripedSet_rational_list;
 229
 230         typedef StripedHashSet_seq<
 231             std::vector< key_val >
 232             , co::hash< hash2 >
 233             , co::less< less >
 234         > StripedSet_vector;
 235
 236         typedef StripedHashSet_seq_rational<
 237             std::vector< key_val >
 238             , co::hash< hash2 >
 239             , co::less< less >
 240         > StripedSet_rational_vector;
 241
 242 #if BOOST_VERSION >= 104800
 243         typedef StripedHashSet_seq<
 244             boost::container::slist< key_val >
 245             , co::hash< hash2 >
 246             , co::less< less >
 247         > StripedSet_boost_slist;
 248
 249         typedef StripedHashSet_seq_rational<
 250             boost::container::slist< key_val >
 251             , co::hash< hash2 >
 252             , co::less< less >
 253         > StripedSet_rational_boost_slist;
 254
 255         typedef StripedHashSet_seq<
 256             boost::container::list< key_val >
 257             , co::hash< hash2 >
 258             , co::less< less >
 259         > StripedSet_boost_list;
 260
 261         typedef StripedHashSet_seq_rational<
 262             boost::container::list< key_val >
 263             , co::hash< hash2 >
 264             , co::less< less >
 265         > StripedSet_rational_boost_list;
 266
 267         typedef StripedHashSet_seq<
 268             boost::container::vector< key_val >
 269             , co::hash< hash2 >
 270             , co::less< less >
 271         > StripedSet_boost_vector;
 272
 273         typedef StripedHashSet_seq_rational<
 274             boost::container::vector< key_val >
 275             , co::hash< hash2 >
 276             , co::less< less >
 277         > StripedSet_rational_boost_vector;
 278
 279         typedef StripedHashSet_seq<
 280             boost::container::stable_vector< key_val >
 281             , co::hash< hash2 >
 282             , co::less< less >
 283         > StripedSet_boost_stable_vector;
 284
 285         typedef StripedHashSet_seq_rational<
 286             boost::container::stable_vector< key_val >
 287             , co::hash< hash2 >
 288             , co::less< less >
 289         > StripedSet_rational_boost_stable_vector;
 290 #endif
 291
 292         typedef StripedHashSet_ord<
 293             std::set< key_val, less >
 294             , co::hash< hash2 >
 295         > StripedSet_set;
 296
 297         typedef StripedHashSet_ord_rational<
 298             std::set< key_val, less >
 299             , co::hash< hash2 >
 300         > StripedSet_rational_set;
 301
 302         typedef StripedHashSet_ord<
 303             std::unordered_set< key_val, hash, equal_to >
 304             , co::hash< hash2 >
 305         > StripedSet_hashset;
 306
 307         typedef StripedHashSet_ord_rational<
 308             std::unordered_set< key_val, hash, equal_to >
 309             , co::hash< hash2 >
 310         > StripedSet_rational_hashset;
 311
 312 #if BOOST_VERSION >= 104800
 313         typedef StripedHashSet_ord<
 314             boost::container::set< key_val, less >
 315             , co::hash< hash2 >
 316         > StripedSet_boost_set;
 317
 318         typedef StripedHashSet_ord_rational<
 319             boost::container::set< key_val, less >
 320             , co::hash< hash2 >
 321         > StripedSet_rational_boost_set;
 322
 323         typedef StripedHashSet_ord<
 324             boost::container::flat_set< key_val, less >
 325             , co::hash< hash2 >
 326         > StripedSet_boost_flat_set;
 327
 328         typedef StripedHashSet_ord_rational<
 329             boost::container::flat_set< key_val, less >
 330             , co::hash< hash2 >
 331         > StripedSet_rational_boost_flat_set;
 332 #endif
 333
 334         typedef StripedHashSet_ord<
 335             boost::unordered_set< key_val, hash, equal_to >
 336             , co::hash< hash2 >
 337         > StripedSet_boost_unordered_set;
 338
 339         typedef StripedHashSet_ord_rational<
 340             boost::unordered_set< key_val, hash, equal_to >
 341             , co::hash< hash2 >
 342         > StripedSet_rational_boost_unordered_set;
 343
 344
 345         // ***************************************************************************
 346         // RefinableSet
 347
 348         // for sequential containers
 349         template <class BucketEntry, typename... Options>
 350         class RefinableHashSet_seq:
 351             public cc::StripedSet< BucketEntry,
 352             co::mutex_policy< cc::striped_set::refinable<> >
 353             ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
 354             , Options...
 355             >
 356         {
 357             typedef cc::StripedSet< BucketEntry,
 358                 co::mutex_policy< cc::striped_set::refinable<> >
 359                 ,co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
 360                 , Options...
 361             > base_class;
 362             typedef typename base_class::resizing_policy resizing_policy_t;
 363
 364             resizing_policy_t   m_placeHolder;
 365         public:
 366             template <class Config>
 367             RefinableHashSet_seq( Config const& cfg )
 368                 : base_class( cfg.c_nSetSize / cfg.c_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( cfg.c_nLoadFactor )) )
 369             {}
 370
 371             /*
 372             template <typename Q, typename Less>
 373             bool erase_with( Q const& v, Less pred )
 374             {
 375                 return base_class::erase( v );
 376             }
 377             */
 378
 379             // for testing
 380             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
 381             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
 382         };
 383
 384         template <class BucketEntry, typename... Options>
 385         class RefinableHashSet_seq_rational:
 386             public cc::StripedSet< BucketEntry,
 387             co::mutex_policy< cc::striped_set::refinable<> >
 388             ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
 389             , Options...
 390             >
 391         {
 392             typedef cc::StripedSet< BucketEntry,
 393                 co::mutex_policy< cc::striped_set::refinable<> >
 394                 ,co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
 395                 , Options...
 396             > base_class;
 397             typedef typename base_class::resizing_policy resizing_policy_t;
 398
 399             resizing_policy_t   m_placeHolder;
 400         public:
 401             template <class Config>
 402             RefinableHashSet_seq_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
 403                 : base_class( cfg.c_nSetSize / cfg.c_nLoadFactor / 16, *(new(&m_placeHolder) resizing_policy_t( 1, cfg.c_nLoadFactor )))
 404             {}
 405
 406             /*
 407             template <typename Q, typename Less>
 408             bool erase_with( Q const& v, Less pred )
 409             {
 410                 return base_class::erase( v );
 411             }
 412             */
 413
 414             // for testing
 415             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
 416             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
 417         };
 418
 419         // for non-sequential ordered containers
 420         template <class BucketEntry, typename... Options>
 421         class RefinableHashSet_ord:
 422             public cc::StripedSet< BucketEntry,
 423                 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
 424                 ,co::mutex_policy< cc::striped_set::refinable<> >
 425                 , Options...
 426             >
 427         {
 428             typedef cc::StripedSet< BucketEntry,
 429                 co::resizing_policy<cc::striped_set::load_factor_resizing<0> >
 430                 ,co::mutex_policy< cc::striped_set::refinable<> >
 431                 , Options...
 432             > base_class;
 433             typedef typename base_class::resizing_policy resizing_policy_t;
 434
 435             resizing_policy_t   m_placeHolder;
 436         public:
 437             template <class Config>
 438             RefinableHashSet_ord( Config const& cfg )
 439                 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( cfg.c_nMaxLoadFactor * 1024 )) )
 440             {}
 441
 442             /*
 443             template <typename Q, typename Less>
 444             bool erase_with( Q const& v, Less pred )
 445             {
 446                 return base_class::erase( v );
 447             }
 448             */
 449
 450             // for testing
 451             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
 452             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
 453         };
 454
 455         template <class BucketEntry, typename... Options>
 456         class RefinableHashSet_ord_rational:
 457             public cc::StripedSet< BucketEntry,
 458                 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
 459                 ,co::mutex_policy< cc::striped_set::refinable<> >
 460                 , Options...
 461             >
 462         {
 463             typedef cc::StripedSet< BucketEntry,
 464                 co::resizing_policy<cc::striped_set::rational_load_factor_resizing<0> >
 465                 ,co::mutex_policy< cc::striped_set::refinable<> >
 466                 , Options...
 467             > base_class;
 468             typedef typename base_class::resizing_policy resizing_policy_t;
 469
 470             resizing_policy_t   m_placeHolder;
 471         public:
 472             template <class Config>
 473             RefinableHashSet_ord_rational( Config const& cfg ) // LoadFactor = 1 / nDenominator
 474                 : base_class( 0, *(new(&m_placeHolder) resizing_policy_t( 1024, cfg.c_nLoadFactor )))
 475             {}
 476
 477             /*
 478             template <typename Q, typename Less>
 479             bool erase_with( Q const& v, Less pred )
 480             {
 481                 return base_class::erase( v );
 482             }
 483             */
 484
 485             // for testing
 486             static CDS_CONSTEXPR bool const c_bExtractSupported = false;
 487             static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true;
 488         };
 489
 490         typedef RefinableHashSet_seq<
 491             std::list< key_val >
 492             , co::hash< hash2 >
 493             , co::less< less >
 494         > RefinableSet_list;
 495
 496         typedef RefinableHashSet_seq_rational<
 497             std::list< key_val >
 498             , co::hash< hash2 >
 499             , co::less< less >
 500         > RefinableSet_rational_list;
 501
 502         typedef RefinableHashSet_seq<
 503             std::vector< key_val >
 504             , co::hash< hash2 >
 505             , co::less< less >
 506         > RefinableSet_vector;
 507
 508         typedef RefinableHashSet_seq_rational<
 509             std::vector< key_val >
 510             , co::hash< hash2 >
 511             , co::less< less >
 512         > RefinableSet_rational_vector;
 513
 514 #if BOOST_VERSION >= 104800
 515         typedef RefinableHashSet_seq<
 516             boost::container::slist< key_val >
 517             , co::hash< hash2 >
 518             , co::less< less >
 519         > RefinableSet_boost_slist;
 520
 521         typedef RefinableHashSet_seq_rational<
 522             boost::container::slist< key_val >
 523             , co::hash< hash2 >
 524             , co::less< less >
 525         > RefinableSet_rational_boost_slist;
 526
 527         typedef RefinableHashSet_seq<
 528             boost::container::list< key_val >
 529             , co::hash< hash2 >
 530             , co::less< less >
 531         > RefinableSet_boost_list;
 532
 533         typedef RefinableHashSet_seq_rational<
 534             boost::container::list< key_val >
 535             , co::hash< hash2 >
 536             , co::less< less >
 537         > RefinableSet_rational_boost_list;
 538
 539         typedef RefinableHashSet_seq<
 540             boost::container::vector< key_val >
 541             , co::hash< hash2 >
 542             , co::less< less >
 543         > RefinableSet_boost_vector;
 544
 545         typedef RefinableHashSet_seq_rational<
 546             boost::container::vector< key_val >
 547             , co::hash< hash2 >
 548             , co::less< less >
 549         > RefinableSet_rational_boost_vector;
 550
 551         typedef RefinableHashSet_seq<
 552             boost::container::stable_vector< key_val >
 553             , co::hash< hash2 >
 554             , co::less< less >
 555         > RefinableSet_boost_stable_vector;
 556
 557         typedef RefinableHashSet_seq_rational<
 558             boost::container::stable_vector< key_val >
 559             , co::hash< hash2 >
 560             , co::less< less >
 561         > RefinableSet_rational_boost_stable_vector;
 562 #endif
 563
 564         typedef RefinableHashSet_ord<
 565             std::set< key_val, less >
 566             , co::hash< hash2 >
 567         > RefinableSet_set;
 568
 569         typedef RefinableHashSet_ord_rational<
 570             std::set< key_val, less >
 571             , co::hash< hash2 >
 572         > RefinableSet_rational_set;
 573
 574         typedef RefinableHashSet_ord<
 575             std::unordered_set< key_val, hash, equal_to >
 576             , co::hash< hash2 >
 577         > RefinableSet_hashset;
 578
 579         typedef RefinableHashSet_ord_rational<
 580             std::unordered_set< key_val, hash, equal_to >
 581             , co::hash< hash2 >
 582         > RefinableSet_rational_hashset;
 583
 584 #if BOOST_VERSION >= 104800
 585         typedef RefinableHashSet_ord<
 586             boost::container::set< key_val, less >
 587             , co::hash< hash2 >
 588         > RefinableSet_boost_set;
 589
 590         typedef RefinableHashSet_ord_rational<
 591             boost::container::set< key_val, less >
 592             , co::hash< hash2 >
 593         > RefinableSet_rational_boost_set;
 594
 595         typedef RefinableHashSet_ord<
 596             boost::container::flat_set< key_val, less >
 597             , co::hash< hash2 >
 598         > RefinableSet_boost_flat_set;
 599
 600         typedef RefinableHashSet_ord_rational<
 601             boost::container::flat_set< key_val, less >
 602             , co::hash< hash2 >
 603         > RefinableSet_rational_boost_flat_set;
 604 #endif
 605
 606         typedef RefinableHashSet_ord<
 607             boost::unordered_set< key_val, hash, equal_to >
 608             , co::hash< hash2 >
 609         > RefinableSet_boost_unordered_set;
 610
 611         typedef RefinableHashSet_ord_rational<
 612             boost::unordered_set< key_val, hash, equal_to >
 613             , co::hash< hash2 >
 614         > RefinableSet_rational_boost_unordered_set;
 615     };
 616
 617 } // namespace set2
 618
 619 #endif // #ifndef CDSUNIT_SET_TYPE_STRIPED_H