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