test/unit/list/test_kv_list.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-2017
   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_LIST_TEST_KV_LIST_H
  32 #define CDSUNIT_LIST_TEST_KV_LIST_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 namespace cds_test {
  38
  39     class kv_list_common : public fixture
  40     {
  41     public:
  42         struct key_type {
  43             int nKey;
  44
  45             key_type() = delete;
  46             explicit key_type( int n )
  47                 : nKey( n )
  48             {}
  49
  50             key_type( key_type const& s )
  51                 : nKey( s.nKey )
  52             {}
  53
  54             key_type( key_type&& s )
  55                 : nKey( s.nKey )
  56             {
  57                 s.nKey = 0;
  58             }
  59
  60             int key() const
  61             {
  62                 return nKey;
  63             }
  64         };
  65
  66         struct value_type {
  67             int val;
  68
  69             value_type()
  70                 : val( 0 )
  71             {}
  72
  73             explicit value_type( int n )
  74                 : val( n )
  75             {}
  76         };
  77
  78         struct lt
  79         {
  80             bool operator()( key_type const& lhs, key_type const& rhs ) const
  81             {
  82                 return lhs.key() < rhs.key();
  83             }
  84
  85             bool operator()( key_type const& lhs, int rhs ) const
  86             {
  87                 return lhs.key() < rhs;
  88             }
  89
  90             bool operator()( int lhs, key_type const& rhs ) const
  91             {
  92                 return lhs < rhs.key();
  93             }
  94
  95             template <typename T>
  96             bool operator ()( T const& v1, T const& v2 ) const
  97             {
  98                 return v1.key() < v2.key();
  99             }
 100         };
 101
 102         struct cmp
 103         {
 104             int operator()( key_type const& lhs, key_type const& rhs ) const
 105             {
 106                 return lhs.key() - rhs.key();
 107             }
 108
 109             int operator()( key_type const& lhs, int rhs ) const
 110             {
 111                 return lhs.key() - rhs;
 112             }
 113
 114             int operator()( int lhs, key_type const& rhs ) const
 115             {
 116                 return lhs - rhs.key();
 117             }
 118
 119             template <typename T>
 120             int operator ()( T const& lhs, T const& rhs ) const
 121             {
 122                 return lhs.key() - rhs.key();
 123             }
 124         };
 125
 126         struct other_key
 127         {
 128             int nKey;
 129
 130             other_key()
 131             {}
 132
 133             other_key( int n )
 134                 : nKey( n )
 135             {}
 136
 137             int key() const
 138             {
 139                 return nKey;
 140             }
 141         };
 142
 143         struct other_less
 144         {
 145             template <typename T1, typename T2>
 146             bool operator()( T1 const& t1, T2 const& t2 ) const
 147             {
 148                 return t1.key() < t2.key();
 149             }
 150         };
 151
 152     protected:
 153         template <typename List>
 154         void test_common( List& l )
 155         {
 156             // Precondition: list is empty
 157             // Postcondition: list is empty
 158
 159             static const size_t nSize = 20;
 160             typedef typename List::key_type    list_key_type;
 161             typedef typename List::value_type  list_value_type;
 162             struct key_val {
 163                 int key;
 164                 int val;
 165             };
 166             key_val arr[nSize];
 167
 168             for ( size_t i = 0; i < nSize; ++i ) {
 169                 arr[i].key = static_cast<int>(i) + 1;
 170                 arr[i].val = arr[i].key * 10;
 171             }
 172             shuffle( arr, arr + nSize );
 173
 174             ASSERT_TRUE( l.empty());
 175             ASSERT_CONTAINER_SIZE( l, 0 );
 176
 177             // insert/find
 178             for ( auto const& i : arr ) {
 179                 EXPECT_FALSE( l.contains( i.key ));
 180                 EXPECT_FALSE( l.contains( key_type( i.key )));
 181                 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
 182                 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
 183                 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
 184                 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
 185
 186                 switch ( i.key % 5 ) {
 187                     case 0:
 188                         EXPECT_TRUE( l.insert( i.key ));
 189                         EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 190                             EXPECT_EQ( n.second.val, 0 );
 191                         } ));
 192                         EXPECT_FALSE( l.insert( i.key ));
 193                         break;
 194
 195                     case 1:
 196                         EXPECT_TRUE( l.insert( i.key, i.val ));
 197                         EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) {
 198                             EXPECT_EQ( n.second.val, n.first.nKey * 10 );
 199                         } ));
 200                         EXPECT_FALSE( l.insert( key_type( i.key )));
 201                         break;
 202
 203                     case 2:
 204                         EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) {
 205                             n.second.val = n.first.nKey * 2;
 206                         }));
 207                         EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 208                             EXPECT_EQ( n.second.val, n.first.key() * 2 );
 209                         } ));
 210                         EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) {
 211                             n.second.val = n.first.nKey * 3;
 212                         } ));
 213                         EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 214                             EXPECT_EQ( n.second.val, n.first.key() * 2 );
 215                         } ));
 216                         break;
 217
 218                     case 3:
 219                         {
 220                             key_type k( i.key );
 221                             EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 ));
 222                             EXPECT_EQ( k.key(), 0 );
 223                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 224                                 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
 225                             } ));
 226                             k.nKey = i.key;
 227                             EXPECT_FALSE( l.emplace( std::move( k ), i.key ));
 228                             //EXPECT_EQ( k.key(), i.key ); // ???
 229                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 230                                 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
 231                             } ));
 232                         }
 233                         break;
 234                     case 4:
 235                         {
 236                             auto pair = l.update( i.key, []( bool, list_value_type& ) {
 237                                 ASSERT_TRUE( false );
 238                             }, false );
 239                             EXPECT_FALSE( pair.first );
 240                             EXPECT_FALSE( pair.second );
 241
 242                             pair = l.update( list_key_type(i.key), []( bool bNew, list_value_type& n ) {
 243                                 EXPECT_TRUE( bNew );
 244                                 n.second.val = n.first.nKey * 3;
 245                             });
 246                             EXPECT_TRUE( pair.first );
 247                             EXPECT_TRUE( pair.second );
 248
 249                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 250                                 EXPECT_EQ( n.second.val, n.first.key() * 3 );
 251                             } ));
 252
 253                             pair = l.update( list_key_type(i.key), []( bool bNew, list_value_type& n ) {
 254                                 EXPECT_FALSE( bNew );
 255                                 n.second.val = n.first.nKey * 5;
 256                             });
 257                             EXPECT_TRUE( pair.first );
 258                             EXPECT_FALSE( pair.second );
 259
 260                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 261                                 EXPECT_EQ( n.second.val, n.first.key() * 5 );
 262                             } ));
 263                         }
 264                         break;
 265                 }
 266
 267                 EXPECT_TRUE( l.contains( i.key ));
 268                 EXPECT_TRUE( l.contains( list_key_type(i.key)));
 269                 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()));
 270                 EXPECT_TRUE( l.find( i.key, []( list_value_type& n  ) {
 271                     n.second.val = n.first.nKey;
 272                 } ));
 273                 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 274                     EXPECT_EQ( n.first.nKey, n.second.val );
 275                     n.second.val = n.first.nKey * 5;
 276                 } ));
 277                 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) {
 278                     EXPECT_EQ( n.first.nKey * 5, n.second.val );
 279                 } ));
 280
 281                 auto pair = l.update( i.key, []( bool bNew, list_value_type& n ) {
 282                     EXPECT_FALSE( bNew );
 283                     EXPECT_EQ( n.first.nKey * 5, n.second.val );
 284                     n.second.val = n.first.nKey * 3;
 285                 }, false );
 286                 EXPECT_TRUE( pair.first );
 287                 EXPECT_FALSE( pair.second );
 288
 289                 EXPECT_FALSE( l.empty());
 290             }
 291
 292             ASSERT_FALSE( l.empty());
 293             EXPECT_CONTAINER_SIZE( l, nSize );
 294
 295             // erase
 296             for ( auto const&i : arr ) {
 297                 switch ( i.key & 3 ) {
 298                     case 0:
 299                         EXPECT_TRUE( l.erase( i.key ));
 300                         break;
 301                     case 1:
 302                         EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less()));
 303                         break;
 304                     case 2:
 305                         EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) {
 306                             EXPECT_EQ( n.first.nKey, i.key );
 307                             EXPECT_EQ( n.first.nKey * 3, n.second.val );
 308                         }));
 309                         break;
 310                     case 3:
 311                         EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) {
 312                             EXPECT_EQ( n.first.nKey, i.key );
 313                             EXPECT_EQ( n.first.nKey * 3, n.second.val );
 314                         } ));
 315                 }
 316
 317                 EXPECT_FALSE( l.contains( i.key ));
 318                 EXPECT_FALSE( l.contains( key_type( i.key )));
 319                 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
 320                 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
 321                 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
 322                 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
 323             }
 324
 325             ASSERT_TRUE( l.empty());
 326             EXPECT_CONTAINER_SIZE( l, 0 );
 327
 328             // clear test
 329             for ( auto& i : arr )
 330                 EXPECT_TRUE( l.insert( i.key, i.val ));
 331
 332             ASSERT_FALSE( l.empty());
 333             EXPECT_CONTAINER_SIZE( l, nSize );
 334
 335             l.clear();
 336
 337             ASSERT_TRUE( l.empty());
 338             EXPECT_CONTAINER_SIZE( l, 0 );
 339
 340             // empty list iterator test
 341             {
 342                 List const& cl = l;
 343                 EXPECT_TRUE( l.begin() == l.end());
 344                 EXPECT_TRUE( l.cbegin() == l.cend());
 345                 EXPECT_TRUE( cl.begin() == cl.end());
 346                 EXPECT_TRUE( l.begin() == l.cend());
 347                 EXPECT_TRUE( cl.begin() == l.end());
 348             }
 349         }
 350
 351         template <typename List>
 352         void test_ordered_iterator( List& l )
 353         {
 354             // Precondition: list is empty
 355             // Postcondition: list is empty
 356
 357             static const size_t nSize = 20;
 358             struct key_val {
 359                 int key;
 360                 int val;
 361             };
 362             key_val arr[nSize];
 363
 364             for ( size_t i = 0; i < nSize; ++i ) {
 365                 arr[i].key = static_cast<int>(i);
 366                 arr[i].val = arr[i].key;
 367             }
 368             shuffle( arr, arr + nSize );
 369
 370             ASSERT_TRUE( l.empty());
 371             ASSERT_CONTAINER_SIZE( l, 0 );
 372
 373             for ( auto& i : arr )
 374                 EXPECT_TRUE( l.insert( i.key, i.val ));
 375
 376             int key = 0;
 377             for ( auto& it : l ) {
 378                 EXPECT_EQ( key, it.first.key());
 379                 EXPECT_EQ( it.second.val, it.first.key());
 380                 it.second.val = it.first.key() * 10;
 381                 ++key;
 382             }
 383             EXPECT_EQ( static_cast<size_t>(key), nSize );
 384
 385             key = 0;
 386             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 387                 EXPECT_EQ( key, it->first.key());
 388                 EXPECT_EQ( it->first.key() * 10, it->second.val );
 389                 ++key;
 390             }
 391             EXPECT_EQ( static_cast<size_t>(key), nSize );
 392
 393             key = 0;
 394             for ( auto it = l.begin(); it != l.end(); ++it ) {
 395                 EXPECT_EQ( key, it->first.key());
 396                 EXPECT_EQ( it->first.key() * 10, it->second.val );
 397                 it->second.val = it->first.key() * 2;
 398                 ++key;
 399             }
 400             EXPECT_EQ( static_cast<size_t>(key), nSize );
 401
 402             List const& cl = l;
 403             key = 0;
 404             for ( auto it = cl.begin(); it != cl.end(); ++it ) {
 405                 EXPECT_EQ( key, it->first.nKey );
 406                 EXPECT_EQ( it->first.nKey * 2, it->second.val );
 407                 ++key;
 408             }
 409             EXPECT_EQ( static_cast<size_t>(key), nSize );
 410
 411             l.clear();
 412             ASSERT_TRUE( l.empty());
 413             EXPECT_CONTAINER_SIZE( l, 0 );
 414         }
 415     };
 416
 417 } // namespace cds_test
 418
 419 #endif // CDSUNIT_LIST_TEST_KV_LIST_H