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