test/unit/tree/test_intrusive_tree_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-2017
   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_TREE_RCU_H
  32 #define CDSUNIT_TREE_TEST_INTRUSIVE_TREE_RCU_H
  33
  34 #include "test_intrusive_tree.h"
  35
  36
  37 // forward declaration
  38 namespace cds { namespace intrusive {}}
  39
  40 namespace cds_test {
  41
  42     namespace ci = cds::intrusive;
  43
  44     class intrusive_tree_rcu: public intrusive_tree
  45     {
  46         typedef intrusive_tree base_class;
  47
  48     protected:
  49
  50
  51         template <class Tree>
  52         void test( Tree& t )
  53         {
  54             // Precondition: tree is empty
  55             // Postcondition: tree is empty
  56
  57             base_class::test( t );
  58
  59             ASSERT_TRUE( t.empty());
  60             ASSERT_CONTAINER_SIZE( t, 0 );
  61
  62             typedef typename Tree::value_type value_type;
  63             typedef typename Tree::rcu_lock   rcu_lock;
  64
  65             std::vector< value_type > data;
  66             std::vector< size_t> indices;
  67             data.reserve( kSize );
  68             indices.reserve( kSize );
  69             for ( size_t key = 0; key < kSize; ++key ) {
  70                 data.push_back( value_type( static_cast<int>(key)));
  71                 indices.push_back( key );
  72             }
  73             shuffle( indices.begin(), indices.end());
  74
  75             typename Tree::exempt_ptr xp;
  76
  77             // get/extract from empty tree
  78             for ( auto idx : indices ) {
  79                 auto& i = data[idx];
  80
  81                 {
  82                     rcu_lock l;
  83                     value_type * p = t.get( i );
  84                     ASSERT_TRUE( p == nullptr );
  85                     p = t.get( i.key());
  86                     ASSERT_TRUE( !p );
  87                     p = t.get_with( other_item( i.key()), other_less());
  88                     ASSERT_TRUE( p == nullptr );
  89                 }
  90
  91                 xp = t.extract( i );
  92                 ASSERT_TRUE( !xp );
  93                 xp = t.extract( i.key());
  94                 ASSERT_TRUE( !xp );
  95                 xp = t.extract_with( other_item( i.key()), other_less());
  96                 ASSERT_TRUE( !xp );
  97
  98                 xp = t.extract_min();
  99                 ASSERT_TRUE( !xp );
 100                 xp = t.extract_max();
 101                 ASSERT_TRUE( !xp );
 102             }
 103
 104             // fill tree
 105             for ( auto idx : indices ) {
 106                 auto& i = data[idx];
 107                 i.nDisposeCount = 0;
 108                 ASSERT_TRUE( t.insert( i ));
 109             }
 110
 111             // get/extract
 112             for ( auto idx : indices ) {
 113                 auto& i = data[idx];
 114
 115                 {
 116                     rcu_lock l;
 117
 118                     value_type * p;
 119                     EXPECT_EQ( i.nFindCount, 0u );
 120                     p = t.get( i );
 121                     ASSERT_FALSE( !p );
 122                     ++p->nFindCount;
 123                     EXPECT_EQ( i.nFindCount, 1u );
 124
 125                     p = t.get( i.key());
 126                     ASSERT_FALSE( !p );
 127                     ++p->nFindCount;
 128                     EXPECT_EQ( i.nFindCount, 2u );
 129
 130                     p = t.get_with( other_item( i.key()), other_less());
 131                     ASSERT_FALSE( !p );
 132                     ++p->nFindCount;
 133                     EXPECT_EQ( i.nFindCount, 3u );
 134                 }
 135
 136                 EXPECT_EQ( i.nEraseCount, 0u );
 137                 switch ( i.key() % 3 ) {
 138                 case 0:
 139                     xp = t.extract( i.key());
 140                     break;
 141                 case 1:
 142                     xp = t.extract( i );
 143                     break;
 144                 case 2:
 145                     xp = t.extract_with( other_item( i.key()), other_less());
 146                     break;
 147                 }
 148                 ASSERT_FALSE( !xp );
 149                 ++xp->nEraseCount;
 150                 EXPECT_EQ( i.nEraseCount, 1u );
 151
 152                 xp = t.extract( i );
 153                 ASSERT_TRUE( !xp );
 154                 xp = t.extract( i.key());
 155                 ASSERT_TRUE( !xp );
 156                 xp = t.extract_with( other_item( i.key()), other_less());
 157                 ASSERT_TRUE( !xp );
 158             }
 159
 160             ASSERT_TRUE( t.empty());
 161             ASSERT_CONTAINER_SIZE( t, 0u );
 162
 163             // Force retiring cycle
 164             Tree::gc::force_dispose();
 165             for ( auto& i : data ) {
 166                 EXPECT_EQ( i.nDisposeCount, 1u );
 167             }
 168
 169             // extract_min
 170             for ( auto idx : indices ) {
 171                 auto& i = data[idx];
 172                 i.nDisposeCount = 0;
 173                 ASSERT_TRUE( t.insert( i ));
 174             }
 175
 176             size_t nCount = 0;
 177             int nKey = -1;
 178             while ( !t.empty()) {
 179                 xp = t.extract_min();
 180                 ASSERT_FALSE( !xp );
 181                 EXPECT_EQ( xp->key(), nKey + 1 );
 182                 ++nCount;
 183                 nKey = xp->key();
 184             }
 185             xp.release();
 186             ASSERT_TRUE( t.empty());
 187             ASSERT_CONTAINER_SIZE( t, 0u );
 188             EXPECT_EQ( nCount, data.size());
 189
 190             // Force retiring cycle
 191             Tree::gc::force_dispose();
 192             for ( auto& i : data ) {
 193                 EXPECT_EQ( i.nDisposeCount, 1u );
 194             }
 195
 196             // extract_max
 197             for ( auto idx : indices ) {
 198                 auto& i = data[idx];
 199                 i.nDisposeCount = 0;
 200                 ASSERT_TRUE( t.insert( i ));
 201             }
 202
 203             nCount = 0;
 204             nKey = static_cast<int>( data.size());
 205             while ( !t.empty()) {
 206                 xp = t.extract_max();
 207                 ASSERT_FALSE( !xp );
 208                 EXPECT_EQ( xp->key(), nKey - 1 );
 209                 ++nCount;
 210                 nKey = xp->key();
 211             }
 212             xp.release();
 213             ASSERT_TRUE( t.empty());
 214             ASSERT_CONTAINER_SIZE( t, 0u );
 215             EXPECT_EQ( nCount, data.size());
 216
 217             // Force retiring cycle
 218             Tree::gc::force_dispose();
 219             for ( auto& i : data ) {
 220                 EXPECT_EQ( i.nDisposeCount, 1u );
 221             }
 222         }
 223     };
 224
 225 } // namespace cds_test
 226
 227 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_RCU_H