test/unit/set/test_set.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_SET_H
  32 #define CDSUNIT_SET_TEST_SET_H
  33
  34 #include "test_set_data.h"
  35
  36 #include <cds/opt/hash.h>
  37
  38 namespace cds_test {
  39
  40     class container_set : public container_set_data
  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             size_t const nSetSize = kSize;
  52
  53             typedef typename Set::value_type value_type;
  54
  55             std::vector< value_type > data;
  56             std::vector< size_t> indices;
  57             data.reserve( kSize );
  58             indices.reserve( kSize );
  59             for ( size_t key = 0; key < kSize; ++key ) {
  60                 data.push_back( value_type( static_cast<int>(key) ) );
  61                 indices.push_back( key );
  62             }
  63             shuffle( indices.begin(), indices.end() );
  64
  65             // insert/find
  66             for ( auto idx : indices ) {
  67                 auto& i = data[idx];
  68
  69                 ASSERT_FALSE( s.contains( i.nKey ) );
  70                 ASSERT_FALSE( s.contains( i ) );
  71                 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
  72                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
  73                 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
  74                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
  75
  76                 std::pair<bool, bool> updResult;
  77
  78                 std::string str;
  79                 updResult = s.update( i.key(), []( bool, value_type&, int )
  80                 {
  81                     ASSERT_TRUE( false );
  82                 }, false );
  83                 EXPECT_FALSE( updResult.first );
  84                 EXPECT_FALSE( updResult.second );
  85
  86                 switch ( idx % 8 ) {
  87                 case 0:
  88                     ASSERT_TRUE( s.insert( i ));
  89                     ASSERT_FALSE( s.insert( i ));
  90                     updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg)
  91                         {
  92                             EXPECT_FALSE( bNew );
  93                             EXPECT_EQ( val.key(), arg.key() );
  94                         }, false );
  95                     EXPECT_TRUE( updResult.first );
  96                     EXPECT_FALSE( updResult.second );
  97                     break;
  98                 case 1:
  99                     ASSERT_TRUE( s.insert( i.key() ));
 100                     ASSERT_FALSE( s.insert( i.key() ));
 101                     updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg)
 102                         {
 103                             EXPECT_FALSE( bNew );
 104                             EXPECT_EQ( val.key(), arg );
 105                         }, false );
 106                     EXPECT_TRUE( updResult.first );
 107                     EXPECT_FALSE( updResult.second );
 108                     break;
 109                 case 2:
 110                     ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 111                     ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
 112                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 113                         {
 114                             EXPECT_EQ( v.key(), key );
 115                             EXPECT_EQ( v.nFindCount, 1u );
 116                         }));
 117                     break;
 118                 case 3:
 119                     ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 120                     ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
 121                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 122                         {
 123                             EXPECT_EQ( v.key(), key );
 124                             EXPECT_EQ( v.nFindCount, 1u );
 125                         }));
 126                     break;
 127                 case 4:
 128                     updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
 129                         {
 130                             EXPECT_TRUE( bNew );
 131                             EXPECT_EQ( v.key(), arg.key() );
 132                             ++v.nUpdateNewCount;
 133                         });
 134                     EXPECT_TRUE( updResult.first );
 135                     EXPECT_TRUE( updResult.second );
 136
 137                     updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg )
 138                         {
 139                             EXPECT_FALSE( bNew );
 140                             EXPECT_EQ( v.key(), arg.key() );
 141                             ++v.nUpdateNewCount;
 142                         }, false );
 143                     EXPECT_TRUE( updResult.first );
 144                     EXPECT_FALSE( updResult.second );
 145
 146                     ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
 147                         {
 148                             EXPECT_EQ( v.key(), key );
 149                             EXPECT_EQ( v.nUpdateNewCount, 2u );
 150                         }));
 151                     break;
 152                 case 5:
 153                     updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
 154                         {
 155                             EXPECT_TRUE( bNew );
 156                             EXPECT_EQ( v.key(), arg );
 157                             ++v.nUpdateNewCount;
 158                         });
 159                     EXPECT_TRUE( updResult.first );
 160                     EXPECT_TRUE( updResult.second );
 161
 162                     updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg )
 163                         {
 164                             EXPECT_FALSE( bNew );
 165                             EXPECT_EQ( v.key(), arg );
 166                             ++v.nUpdateNewCount;
 167                         }, false );
 168                     EXPECT_TRUE( updResult.first );
 169                     EXPECT_FALSE( updResult.second );
 170
 171                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 172                         {
 173                             EXPECT_EQ( v.key(), arg.key() );
 174                             EXPECT_EQ( v.nUpdateNewCount, 2u );
 175                         }));
 176                     break;
 177                 case 6:
 178                     ASSERT_TRUE( s.emplace( i.key()));
 179                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 180                         {
 181                             EXPECT_EQ( v.key(), arg.key() );
 182                             EXPECT_EQ( v.nVal, arg.nVal );
 183                         }));
 184                     break;
 185                 case 7:
 186                     str = "Hello!";
 187                     ASSERT_TRUE( s.emplace( i.key(), std::move( str )));
 188                     EXPECT_TRUE( str.empty());
 189                     ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
 190                         {
 191                             EXPECT_EQ( v.key(), arg.key() );
 192                             EXPECT_EQ( v.nVal, arg.nVal );
 193                             EXPECT_EQ( v.strVal, std::string( "Hello!" ));
 194                         } ) );
 195                     break;
 196                 default:
 197                     // forgot anything?..
 198                     ASSERT_TRUE( false );
 199                 }
 200
 201                 ASSERT_TRUE( s.contains( i.nKey ) );
 202                 ASSERT_TRUE( s.contains( i ) );
 203                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
 204                 ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) );
 205                 ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) );
 206                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) );
 207             }
 208
 209             ASSERT_FALSE( s.empty() );
 210             ASSERT_CONTAINER_SIZE( s, nSetSize );
 211
 212             // erase
 213             shuffle( indices.begin(), indices.end() );
 214             for ( auto idx : indices ) {
 215                 auto& i = data[idx];
 216
 217                 ASSERT_TRUE( s.contains( i.nKey ) );
 218                 ASSERT_TRUE( s.contains( i ) );
 219                 ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
 220                 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int )
 221                     {
 222                         v.nFindCount = 1;
 223                     }));
 224                 ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& )
 225                     {
 226                         EXPECT_EQ( ++v.nFindCount, 2u );
 227                     }));
 228                 ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& )
 229                     {
 230                         EXPECT_EQ( ++v.nFindCount, 3u );
 231                     }));
 232
 233                 int nKey = i.key() - 1;
 234                 switch ( idx % 6 ) {
 235                 case 0:
 236                     ASSERT_TRUE( s.erase( i.key()));
 237                     ASSERT_FALSE( s.erase( i.key()));
 238                     break;
 239                 case 1:
 240                     ASSERT_TRUE( s.erase( i ));
 241                     ASSERT_FALSE( s.erase( i ));
 242                     break;
 243                 case 2:
 244                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
 245                     ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
 246                     break;
 247                 case 3:
 248                     ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
 249                         {
 250                             nKey = v.key();
 251                         } ));
 252                     EXPECT_EQ( i.key(), nKey );
 253
 254                     nKey = i.key() - 1;
 255                     ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
 256                         {
 257                             nKey = v.key();
 258                         } ));
 259                     EXPECT_EQ( i.key(), nKey + 1 );
 260                     break;
 261                 case 4:
 262                     ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v )
 263                         {
 264                             nKey = v.key();
 265                         } ));
 266                     EXPECT_EQ( i.key(), nKey );
 267
 268                     nKey = i.key() - 1;
 269                     ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v )
 270                         {
 271                             nKey = v.key();
 272                         } ));
 273                     EXPECT_EQ( i.key(), nKey + 1 );
 274                     break;
 275                 case 5:
 276                     ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
 277                         {
 278                             nKey = v.key();
 279                         } ));
 280                     EXPECT_EQ( i.key(), nKey );
 281
 282                     nKey = i.key() - 1;
 283                     ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
 284                         {
 285                             nKey = v.key();
 286                         } ));
 287                     EXPECT_EQ( i.key(), nKey + 1 );
 288                     break;
 289                 }
 290
 291                 ASSERT_FALSE( s.contains( i.nKey ) );
 292                 ASSERT_FALSE( s.contains( i ) );
 293                 ASSERT_FALSE( s.contains( other_item( i.key() ), other_less()));
 294                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
 295                 ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
 296                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 297             }
 298             ASSERT_TRUE( s.empty() );
 299             ASSERT_CONTAINER_SIZE( s, 0u );
 300
 301
 302             // clear
 303             for ( auto& i : data ) {
 304                 ASSERT_TRUE( s.insert( i ) );
 305             }
 306
 307             ASSERT_FALSE( s.empty() );
 308             ASSERT_CONTAINER_SIZE( s, nSetSize );
 309
 310             s.clear();
 311
 312             ASSERT_TRUE( s.empty() );
 313             ASSERT_CONTAINER_SIZE( s, 0u );
 314
 315             ASSERT_TRUE( s.begin() == s.end() );
 316             ASSERT_TRUE( s.cbegin() == s.cend() );
 317         }
 318     };
 319
 320 } // namespace cds_test
 321
 322 #endif // CDSUNIT_SET_TEST_SET_H