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