test/unit/tree/test_intrusive_ellen_bintree_rcu.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_TREE_TEST_INTRUSIVE_ELLEN_BINTREE_RCU_H
  32 #define CDSUNIT_TREE_TEST_INTRUSIVE_ELLEN_BINTREE_RCU_H
  33
  34 #include "test_intrusive_tree_rcu.h"
  35
  36 #include <cds/intrusive/ellen_bintree_rcu.h>
  37 #include <cds/memory/vyukov_queue_pool.h>
  38 #include <cds/memory/pool_allocator.h>
  39
  40
  41 // forward declaration
  42 namespace cds { namespace intrusive {}}
  43
  44 namespace {
  45
  46     namespace ci = cds::intrusive;
  47
  48     template <class RCU>
  49     class IntrusiveEllenBinTree: public cds_test::intrusive_tree_rcu
  50     {
  51         typedef cds_test::intrusive_tree_rcu base_class;
  52
  53     public:
  54         typedef cds::urcu::gc<RCU> rcu_type;
  55
  56         typedef base_class::key_type key_type;
  57
  58         typedef typename base_class::base_int_item< ci::ellen_bintree::node<rcu_type>> base_item_type;
  59         typedef ci::ellen_bintree::internal_node< key_type, base_item_type >           internal_base_node;
  60         typedef ci::ellen_bintree::update_desc< base_item_type, internal_base_node >   update_base_desc;
  61
  62         typedef typename base_class::member_int_item< ci::ellen_bintree::node<rcu_type>> member_item_type;
  63         typedef ci::ellen_bintree::internal_node< key_type, member_item_type >           internal_member_node;
  64         typedef ci::ellen_bintree::update_desc< member_item_type, internal_member_node > update_member_desc;
  65
  66         // update_desc pools
  67         struct pool_traits: public cds::memory::vyukov_queue_pool_traits
  68         {
  69             typedef cds::opt::v::static_buffer< update_base_desc, 256 > buffer;
  70         };
  71         typedef cds::memory::vyukov_queue_pool< update_base_desc, pool_traits > pool_type;
  72         typedef cds::memory::lazy_vyukov_queue_pool< update_base_desc, pool_traits > lazy_pool_type;
  73
  74         static pool_type *         s_Pool;
  75         static lazy_pool_type *    s_LazyPool;
  76
  77         struct pool_accessor
  78         {
  79             typedef typename pool_type::value_type value_type;
  80
  81             pool_type& operator()() const
  82             {
  83                 return *s_Pool;
  84             }
  85         };
  86
  87         struct lazy_pool_accessor
  88         {
  89             typedef typename lazy_pool_type::value_type value_type;
  90
  91             lazy_pool_type& operator()() const
  92             {
  93                 return *s_LazyPool;
  94             }
  95         };
  96
  97         static void SetUpTestCase()
  98         {
  99             ASSERT_TRUE( s_Pool == nullptr );
 100             ASSERT_TRUE( s_LazyPool == nullptr );
 101             s_Pool = new pool_type;
 102             s_LazyPool = new lazy_pool_type;
 103         }
 104
 105         static void TearDownTestCase()
 106         {
 107             ASSERT_TRUE( s_Pool != nullptr );
 108             ASSERT_TRUE( s_LazyPool != nullptr );
 109             delete s_LazyPool;
 110             delete s_Pool;
 111
 112             s_LazyPool = nullptr;
 113             s_Pool = nullptr;
 114         }
 115
 116         struct generic_traits: public ci::ellen_bintree::traits
 117         {
 118             typedef base_class::key_extractor key_extractor;
 119             typedef mock_disposer disposer;
 120         };
 121
 122     protected:
 123         void SetUp()
 124         {
 125             RCU::Construct();
 126             cds::threading::Manager::attachThread();
 127         }
 128
 129         void TearDown()
 130         {
 131             cds::threading::Manager::detachThread();
 132             RCU::Destruct();
 133         }
 134     };
 135
 136     /*static*/ template <typename RCU> typename IntrusiveEllenBinTree<RCU>::pool_type *      IntrusiveEllenBinTree<RCU>::s_Pool = nullptr;
 137     /*static*/ template <typename RCU> typename IntrusiveEllenBinTree<RCU>::lazy_pool_type * IntrusiveEllenBinTree<RCU>::s_LazyPool = nullptr;
 138
 139     TYPED_TEST_CASE_P( IntrusiveEllenBinTree );
 140
 141
 142     TYPED_TEST_P( IntrusiveEllenBinTree, base_cmp )
 143     {
 144         typedef typename TestFixture::rcu_type   rcu_type;
 145         typedef typename TestFixture::key_type   key_type;
 146         typedef typename TestFixture::base_item_type base_item_type;
 147         typedef typename TestFixture::generic_traits generic_traits;
 148
 149         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type,
 150             typename ci::ellen_bintree::make_traits<
 151                 ci::opt::type_traits< generic_traits >
 152                 , ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >>>
 153                 , ci::opt::compare< typename TestFixture::template cmp<base_item_type>>
 154             >::type
 155         > tree_type;
 156
 157         tree_type t;
 158         this->test( t );
 159     }
 160
 161     TYPED_TEST_P( IntrusiveEllenBinTree, base_less )
 162     {
 163         typedef typename TestFixture::rcu_type   rcu_type;
 164         typedef typename TestFixture::key_type   key_type;
 165         typedef typename TestFixture::base_item_type base_item_type;
 166         typedef typename TestFixture::generic_traits generic_traits;
 167
 168         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type,
 169             typename ci::ellen_bintree::make_traits<
 170                 ci::opt::type_traits< generic_traits >
 171                 , ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >>>
 172                 , ci::opt::less< typename TestFixture::template less<base_item_type>>
 173             >::type
 174         > tree_type;
 175
 176         tree_type t;
 177         this->test( t );
 178     }
 179
 180     TYPED_TEST_P( IntrusiveEllenBinTree, base_item_counter )
 181     {
 182         typedef typename TestFixture::rcu_type   rcu_type;
 183         typedef typename TestFixture::key_type   key_type;
 184         typedef typename TestFixture::base_item_type base_item_type;
 185         typedef typename TestFixture::generic_traits generic_traits;
 186
 187         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type,
 188             typename ci::ellen_bintree::make_traits<
 189                 ci::opt::type_traits< generic_traits >
 190                 , ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >>>
 191                 , ci::opt::compare< typename TestFixture::template cmp<base_item_type>>
 192                 , ci::opt::item_counter< typename TestFixture::simple_item_counter >
 193             >::type
 194         > tree_type;
 195
 196         tree_type t;
 197         this->test( t );
 198     }
 199
 200     TYPED_TEST_P( IntrusiveEllenBinTree, base_backoff )
 201     {
 202         typedef typename TestFixture::rcu_type   rcu_type;
 203         typedef typename TestFixture::key_type   key_type;
 204         typedef typename TestFixture::base_item_type base_item_type;
 205         typedef typename TestFixture::generic_traits generic_traits;
 206
 207         struct tree_traits: public generic_traits
 208         {
 209             typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook;
 210             typedef typename TestFixture::template cmp<base_item_type> compare;
 211             typedef typename TestFixture::template less<base_item_type> less;
 212             typedef cds::atomicity::item_counter item_counter;
 213             typedef cds::backoff::yield back_off;
 214         };
 215
 216         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type;
 217
 218         tree_type t;
 219         this->test( t );
 220     }
 221
 222     TYPED_TEST_P( IntrusiveEllenBinTree, base_seq_cst )
 223     {
 224         typedef typename TestFixture::rcu_type   rcu_type;
 225         typedef typename TestFixture::key_type   key_type;
 226         typedef typename TestFixture::base_item_type base_item_type;
 227         typedef typename TestFixture::generic_traits generic_traits;
 228
 229         struct tree_traits: public generic_traits
 230         {
 231             typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook;
 232             typedef typename TestFixture::template cmp<base_item_type> compare;
 233             typedef typename TestFixture::template less<base_item_type> less;
 234             typedef cds::atomicity::item_counter item_counter;
 235             typedef cds::backoff::pause back_off;
 236             typedef ci::opt::v::sequential_consistent memory_model;
 237         };
 238
 239         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type;
 240
 241         tree_type t;
 242         this->test( t );
 243     }
 244
 245     TYPED_TEST_P( IntrusiveEllenBinTree, base_update_desc_pool )
 246     {
 247         typedef typename TestFixture::rcu_type   rcu_type;
 248         typedef typename TestFixture::key_type   key_type;
 249         typedef typename TestFixture::base_item_type base_item_type;
 250         typedef typename TestFixture::generic_traits generic_traits;
 251
 252         struct tree_traits: public generic_traits
 253         {
 254             typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook;
 255             typedef typename TestFixture::template less<base_item_type> less;
 256             typedef cds::atomicity::item_counter item_counter;
 257             typedef cds::memory::pool_allocator< typename TestFixture::update_base_desc, typename TestFixture::pool_accessor> update_desc_allocator;
 258         };
 259
 260         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type;
 261
 262         tree_type t;
 263         this->test( t );
 264     }
 265
 266     TYPED_TEST_P( IntrusiveEllenBinTree, base_update_desc_lazy_pool )
 267     {
 268         typedef typename TestFixture::rcu_type   rcu_type;
 269         typedef typename TestFixture::key_type   key_type;
 270         typedef typename TestFixture::base_item_type base_item_type;
 271         typedef typename TestFixture::generic_traits generic_traits;
 272
 273         struct tree_traits: public generic_traits
 274         {
 275             typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook;
 276             typedef typename TestFixture::template less<base_item_type> less;
 277             typedef cds::atomicity::item_counter item_counter;
 278             typedef cds::memory::pool_allocator< typename TestFixture::update_base_desc, typename TestFixture::lazy_pool_accessor> update_desc_allocator;
 279         };
 280
 281         typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type;
 282
 283         tree_type t;
 284         this->test( t );
 285     }
 286
 287     // member hook
 288     TYPED_TEST_P( IntrusiveEllenBinTree, member_cmp )
 289     {
 290         typedef typename TestFixture::rcu_type   rcu_type;
 291         typedef typename TestFixture::key_type   key_type;
 292         typedef typename TestFixture::member_item_type member_item_type;
 293         typedef typename TestFixture::generic_traits   generic_traits;
 294
 295         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type,
 296             typename ci::ellen_bintree::make_traits<
 297                 ci::opt::type_traits< generic_traits >
 298                 , ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >>>
 299                 , ci::opt::compare< typename TestFixture::template cmp<member_item_type>>
 300             >::type
 301         > tree_type;
 302
 303         tree_type t;
 304         this->test( t );
 305     }
 306
 307     TYPED_TEST_P( IntrusiveEllenBinTree, member_less )
 308     {
 309         typedef typename TestFixture::rcu_type   rcu_type;
 310         typedef typename TestFixture::key_type   key_type;
 311         typedef typename TestFixture::member_item_type member_item_type;
 312         typedef typename TestFixture::generic_traits   generic_traits;
 313
 314         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type,
 315             typename ci::ellen_bintree::make_traits<
 316                 ci::opt::type_traits< generic_traits >
 317                 , ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >>>
 318                 , ci::opt::less< typename TestFixture::template less<member_item_type>>
 319             >::type
 320         > tree_type;
 321
 322         tree_type t;
 323         this->test( t );
 324     }
 325
 326     TYPED_TEST_P( IntrusiveEllenBinTree, member_item_counter )
 327     {
 328         typedef typename TestFixture::rcu_type   rcu_type;
 329         typedef typename TestFixture::key_type   key_type;
 330         typedef typename TestFixture::member_item_type member_item_type;
 331         typedef typename TestFixture::generic_traits   generic_traits;
 332
 333         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type,
 334             typename ci::ellen_bintree::make_traits<
 335                 ci::opt::type_traits< generic_traits >
 336                 , ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >>>
 337                 , ci::opt::compare< typename TestFixture::template cmp<member_item_type>>
 338                 , ci::opt::item_counter< typename TestFixture::simple_item_counter >
 339             >::type
 340         > tree_type;
 341
 342         tree_type t;
 343         this->test( t );
 344     }
 345
 346     TYPED_TEST_P( IntrusiveEllenBinTree, member_backoff )
 347     {
 348         typedef typename TestFixture::rcu_type   rcu_type;
 349         typedef typename TestFixture::key_type   key_type;
 350         typedef typename TestFixture::member_item_type member_item_type;
 351         typedef typename TestFixture::generic_traits   generic_traits;
 352
 353         struct tree_traits: public generic_traits
 354         {
 355             typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook;
 356             typedef typename TestFixture::template cmp<member_item_type> compare;
 357             typedef typename TestFixture::template less<member_item_type> less;
 358             typedef cds::atomicity::item_counter item_counter;
 359             typedef cds::backoff::yield back_off;
 360         };
 361
 362         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type;
 363
 364         tree_type t;
 365         this->test( t );
 366     }
 367
 368     TYPED_TEST_P( IntrusiveEllenBinTree, member_seq_cst )
 369     {
 370         typedef typename TestFixture::rcu_type   rcu_type;
 371         typedef typename TestFixture::key_type   key_type;
 372         typedef typename TestFixture::member_item_type member_item_type;
 373         typedef typename TestFixture::generic_traits   generic_traits;
 374
 375         struct tree_traits: public generic_traits
 376         {
 377             typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook;
 378             typedef typename TestFixture::template cmp<member_item_type> compare;
 379             typedef typename TestFixture::template less<member_item_type> less;
 380             typedef cds::atomicity::item_counter item_counter;
 381             typedef cds::backoff::pause back_off;
 382             typedef ci::opt::v::sequential_consistent memory_model;
 383         };
 384
 385         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type;
 386
 387         tree_type t;
 388         this->test( t );
 389     }
 390
 391     TYPED_TEST_P( IntrusiveEllenBinTree, member_update_desc_pool )
 392     {
 393         typedef typename TestFixture::rcu_type   rcu_type;
 394         typedef typename TestFixture::key_type   key_type;
 395         typedef typename TestFixture::member_item_type member_item_type;
 396         typedef typename TestFixture::generic_traits   generic_traits;
 397
 398         struct tree_traits: public generic_traits
 399         {
 400             typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook;
 401             typedef typename TestFixture::template less<member_item_type> less;
 402             typedef cds::atomicity::item_counter item_counter;
 403             typedef cds::memory::pool_allocator< typename TestFixture::update_member_desc, typename TestFixture::pool_accessor> update_desc_allocator;
 404         };
 405
 406         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type;
 407
 408         tree_type t;
 409         this->test( t );
 410     }
 411
 412     TYPED_TEST_P( IntrusiveEllenBinTree, member_update_desc_lazy_pool )
 413     {
 414         typedef typename TestFixture::rcu_type   rcu_type;
 415         typedef typename TestFixture::key_type   key_type;
 416         typedef typename TestFixture::member_item_type member_item_type;
 417         typedef typename TestFixture::generic_traits   generic_traits;
 418
 419         struct tree_traits: public generic_traits
 420         {
 421             typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook;
 422             typedef typename TestFixture::template less<member_item_type> less;
 423             typedef cds::atomicity::item_counter item_counter;
 424             typedef cds::memory::pool_allocator< typename TestFixture::update_member_desc, typename TestFixture::lazy_pool_accessor> update_desc_allocator;
 425         };
 426
 427         typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type;
 428
 429         tree_type t;
 430         this->test( t );
 431     }
 432
 433     REGISTER_TYPED_TEST_CASE_P( IntrusiveEllenBinTree,
 434         base_cmp, base_less, base_item_counter, base_backoff, base_seq_cst, base_update_desc_pool, base_update_desc_lazy_pool, member_cmp, member_less, member_item_counter, member_backoff, member_seq_cst, member_update_desc_pool, member_update_desc_lazy_pool
 435         );
 436
 437 } // namespace
 438
 439 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_ELLEN_BINTREE_RCU_H