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