test/unit/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-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_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, 0 );
 124                     rp = s.get( i );
 125                     ASSERT_TRUE( rp );
 126                     ++rp->nFindCount;
 127                     EXPECT_EQ( i.nFindCount, 1 );
 128
 129                     rp = s.get( i.key() );
 130                     ASSERT_TRUE( rp );
 131                     ++rp->nFindCount;
 132                     EXPECT_EQ( i.nFindCount, 2 );
 133
 134                     rp = s.get_with( other_item( i.key()), other_less());
 135                     ASSERT_TRUE( rp );
 136                     ++rp->nFindCount;
 137                     EXPECT_EQ( i.nFindCount, 3 );
 138                 }
 139
 140                 if ( Set::c_bExtractLockExternal ) {
 141                     rcu_lock l;
 142
 143                     EXPECT_EQ( i.nEraseCount, 0 );
 144                     switch ( i.key() % 3 ) {
 145                     case 0:
 146                         xp = s.extract( i.key());
 147                         break;
 148                     case 1:
 149                         xp = s.extract( i );
 150                         break;
 151                     case 2:
 152                         xp = s.extract_with( other_item( i.key() ), other_less() );
 153                         break;
 154                     }
 155                     ASSERT_TRUE( xp );
 156                     ++xp->nEraseCount;
 157                     EXPECT_EQ( i.nEraseCount, 1 );
 158
 159                     xp = s.extract( i );
 160                     ASSERT_TRUE( !xp );
 161                     xp = s.extract( i.key() );
 162                     ASSERT_TRUE( !xp );
 163                     xp = s.extract_with( other_item( i.key() ), other_less() );
 164                     ASSERT_TRUE( !xp );
 165                 }
 166                 else {
 167                     EXPECT_EQ( i.nEraseCount, 0 );
 168                     switch ( i.key() % 3 ) {
 169                     case 0:
 170                         xp = s.extract( i.key());
 171                         break;
 172                     case 1:
 173                         xp = s.extract( i );
 174                         break;
 175                     case 2:
 176                         xp = s.extract_with( other_item( i.key() ), other_less() );
 177                         break;
 178                     }
 179                     ASSERT_TRUE( xp );
 180                     ++xp->nEraseCount;
 181                     EXPECT_EQ( i.nEraseCount, 1 );
 182
 183                     xp = s.extract( i );
 184                     ASSERT_TRUE( !xp );
 185                     xp = s.extract( i.key() );
 186                     ASSERT_TRUE( !xp );
 187                     xp = s.extract_with( other_item( i.key() ), other_less() );
 188                     ASSERT_TRUE( !xp );
 189                 }
 190             }
 191
 192             ASSERT_TRUE( s.empty() );
 193             ASSERT_CONTAINER_SIZE( s, 0 );
 194
 195             // Force retiring cycle
 196             Set::gc::force_dispose();
 197             for ( auto& i : data ) {
 198                 EXPECT_EQ( i.nDisposeCount, 1 );
 199             }
 200         }
 201     };
 202
 203 } // namespace cds_test
 204
 205 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_RCU_H