test/unit/list/test_kv_iterable_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-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_LIST_TEST_KV_ITERABLE_LIST_H
  32 #define CDSUNIT_LIST_TEST_KV_ITERABLE_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_iterable_list : 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::mapped_type list_mapped_type;
 162             typedef typename List::value_type  list_value_type;
 163             struct key_val {
 164                 int key;
 165                 int val;
 166             };
 167             key_val arr[nSize];
 168
 169             for ( size_t i = 0; i < nSize; ++i ) {
 170                 arr[i].key = static_cast<int>(i) + 1;
 171                 arr[i].val = arr[i].key * 10;
 172             }
 173             shuffle( arr, arr + nSize );
 174
 175             ASSERT_TRUE( l.empty() );
 176             ASSERT_CONTAINER_SIZE( l, 0 );
 177
 178             // insert/find
 179             for ( auto const& i : arr ) {
 180                 EXPECT_FALSE( l.contains( i.key ));
 181                 EXPECT_FALSE( l.contains( key_type( i.key )));
 182                 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
 183                 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
 184                 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
 185                 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
 186                 EXPECT_TRUE( l.find( i.key ) == l.end() );
 187                 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less()) == l.end());
 188
 189                 switch ( i.key % 6 ) {
 190                     case 0:
 191                         EXPECT_TRUE( l.insert( i.key ));
 192                         EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 193                             EXPECT_EQ( n.second.val, 0 );
 194                         } ));
 195                         EXPECT_FALSE( l.insert( i.key ));
 196                         break;
 197
 198                     case 1:
 199                         EXPECT_TRUE( l.insert( i.key, i.val ));
 200                         EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) {
 201                             EXPECT_EQ( n.second.val, n.first.nKey * 10 );
 202                         } ));
 203                         EXPECT_FALSE( l.insert( key_type( i.key )));
 204                         break;
 205
 206                     case 2:
 207                         EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) {
 208                             n.second.val = n.first.nKey * 2;
 209                         }));
 210                         EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 211                             EXPECT_EQ( n.second.val, n.first.key() * 2 );
 212                         } ));
 213                         EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) {
 214                             n.second.val = n.first.nKey * 3;
 215                         } ));
 216                         EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 217                             EXPECT_EQ( n.second.val, n.first.key() * 2 );
 218                         } ));
 219                         break;
 220
 221                     case 3:
 222                         {
 223                             key_type k( i.key );
 224                             EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 ));
 225                             EXPECT_EQ( k.key(), 0 );
 226                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 227                                 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
 228                             } ));
 229                             k.nKey = i.key;
 230                             EXPECT_FALSE( l.emplace( std::move( k ), i.key ));
 231                             //EXPECT_EQ( k.key(), i.key ); // ???
 232                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 233                                 EXPECT_EQ( n.second.val, n.first.nKey * 100 );
 234                             } ));
 235                         }
 236                         break;
 237
 238                     case 4:
 239                         {
 240                             auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) {
 241                                 ASSERT_TRUE( false );
 242                             }, false );
 243                             EXPECT_FALSE( pair.first );
 244                             EXPECT_FALSE( pair.second );
 245
 246                             pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) {
 247                                 EXPECT_TRUE( old == nullptr );
 248                                 n.second.val = n.first.nKey * 3;
 249                             });
 250                             EXPECT_TRUE( pair.first );
 251                             EXPECT_TRUE( pair.second );
 252
 253                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 254                                 EXPECT_EQ( n.second.val, n.first.key() * 3 );
 255                             } ));
 256
 257                             pair = l.update( list_key_type(i.key), []( list_value_type& n, list_value_type* old ) {
 258                                 EXPECT_FALSE( old == nullptr );
 259                                 n.second.val = n.first.nKey * 5;
 260                             });
 261                             EXPECT_TRUE( pair.first );
 262                             EXPECT_FALSE( pair.second );
 263
 264                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 265                                 EXPECT_EQ( n.second.val, n.first.key() * 5 );
 266                             } ));
 267                         }
 268                         break;
 269                     case 5:
 270                         {
 271                             auto ret = l.upsert( i.key, i.val, false );
 272                             EXPECT_FALSE( ret.first );
 273                             EXPECT_FALSE( ret.second );
 274                             EXPECT_FALSE( l.contains( i.key ));
 275
 276                             ret = l.upsert( i.key, i.val );
 277                             EXPECT_TRUE( ret.first );
 278                             EXPECT_TRUE( ret.second );
 279                             EXPECT_TRUE( l.contains( i.key ) );
 280
 281                             ret = l.upsert( i.key, i.val * 12 );
 282                             EXPECT_TRUE( ret.first );
 283                             EXPECT_FALSE( ret.second );
 284                             EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 285                                 EXPECT_EQ( n.second.val, n.first.key() * 12 );
 286                             }));
 287                         }
 288                         break;
 289                 }
 290
 291                 EXPECT_TRUE( l.contains( i.key ));
 292                 EXPECT_TRUE( l.contains( list_key_type(i.key)));
 293                 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()));
 294                 EXPECT_TRUE( l.find( i.key, []( list_value_type& n  ) {
 295                     n.second.val = n.first.nKey;
 296                 } ));
 297                 EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) {
 298                     EXPECT_EQ( n.first.nKey, n.second.val );
 299                     n.second.val = n.first.nKey * 5;
 300                 } ));
 301                 EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) {
 302                     EXPECT_EQ( n.first.nKey * 5, n.second.val );
 303                 } ));
 304
 305                 auto pair = l.update( i.key, []( list_value_type& n, list_value_type* old ) {
 306                     EXPECT_FALSE( old == nullptr );
 307                     EXPECT_EQ( n.first.nKey * 5, n.second.val );
 308                     n.second.val = n.first.nKey * 3;
 309                 }, false );
 310                 EXPECT_TRUE( pair.first );
 311                 EXPECT_FALSE( pair.second );
 312
 313                 EXPECT_FALSE( l.find( i.key ) == l.end() );
 314                 EXPECT_EQ( l.find( i.key )->first.nKey, i.key );
 315                 EXPECT_EQ( l.find( i.key )->second.val, i.key * 3 );
 316                 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less() ) == l.end() );
 317                 EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->first.nKey, i.key );
 318                 EXPECT_EQ( l.find_with( other_key( i.key ), other_less())->second.val, i.key * 3 );
 319
 320                 EXPECT_FALSE( l.empty() );
 321             }
 322
 323             ASSERT_FALSE( l.empty() );
 324             EXPECT_CONTAINER_SIZE( l, nSize );
 325
 326             // erase
 327             for ( auto const&i : arr ) {
 328                 switch ( i.key % 4 ) {
 329                     case 0:
 330                         EXPECT_TRUE( l.erase( i.key ));
 331                         break;
 332                     case 1:
 333                         EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less()));
 334                         break;
 335                     case 2:
 336                         EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) {
 337                             EXPECT_EQ( n.first.nKey, i.key );
 338                             EXPECT_EQ( n.first.nKey * 3, n.second.val );
 339                         }));
 340                         break;
 341                     case 3:
 342                         EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) {
 343                             EXPECT_EQ( n.first.nKey, i.key );
 344                             EXPECT_EQ( n.first.nKey * 3, n.second.val );
 345                         } ));
 346                 }
 347
 348                 EXPECT_FALSE( l.contains( i.key ));
 349                 EXPECT_FALSE( l.contains( key_type( i.key )));
 350                 EXPECT_FALSE( l.contains( other_key( i.key ), other_less()));
 351                 EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} ));
 352                 EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} ));
 353                 EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} ));
 354             }
 355
 356             ASSERT_TRUE( l.empty() );
 357             EXPECT_CONTAINER_SIZE( l, 0 );
 358
 359             // clear test
 360             for ( auto& i : arr )
 361                 EXPECT_TRUE( l.insert( i.key, i.val ));
 362
 363             ASSERT_FALSE( l.empty() );
 364             EXPECT_CONTAINER_SIZE( l, nSize );
 365
 366             l.clear();
 367
 368             ASSERT_TRUE( l.empty() );
 369             EXPECT_CONTAINER_SIZE( l, 0 );
 370
 371             // empty list iterator test
 372             {
 373                 List const& cl = l;
 374                 EXPECT_TRUE( l.begin() == l.end());
 375                 EXPECT_TRUE( l.cbegin() == l.cend());
 376                 EXPECT_TRUE( cl.begin() == cl.end());
 377                 EXPECT_TRUE( l.begin() == l.cend());
 378                 EXPECT_TRUE( cl.begin() == l.end());
 379             }
 380         }
 381
 382         template <typename List>
 383         void test_ordered_iterator( List& l )
 384         {
 385             // Precondition: list is empty
 386             // Postcondition: list is empty
 387
 388             static const size_t nSize = 20;
 389             struct key_val {
 390                 int key;
 391                 int val;
 392             };
 393             key_val arr[nSize];
 394
 395             for ( size_t i = 0; i < nSize; ++i ) {
 396                 arr[i].key = static_cast<int>(i);
 397                 arr[i].val = arr[i].key;
 398             }
 399             shuffle( arr, arr + nSize );
 400
 401             ASSERT_TRUE( l.empty() );
 402             ASSERT_CONTAINER_SIZE( l, 0 );
 403
 404             for ( auto& i : arr )
 405                 EXPECT_TRUE( l.insert( i.key, i.val ));
 406
 407             int key = 0;
 408             for ( auto& it : l ) {
 409                 EXPECT_EQ( key, it.first.key() );
 410                 EXPECT_EQ( it.second.val, it.first.key() );
 411                 it.second.val = it.first.key() * 10;
 412                 ++key;
 413             }
 414             EXPECT_EQ( static_cast<size_t>(key), nSize );
 415
 416             key = 0;
 417             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 418                 EXPECT_EQ( key, it->first.key() );
 419                 EXPECT_EQ( it->first.key() * 10, it->second.val );
 420                 ++key;
 421             }
 422             EXPECT_EQ( static_cast<size_t>(key), nSize );
 423
 424             key = 0;
 425             for ( auto it = l.begin(); it != l.end(); ++it ) {
 426                 EXPECT_EQ( key, it->first.key() );
 427                 EXPECT_EQ( it->first.key() * 10, it->second.val );
 428                 it->second.val = it->first.key() * 2;
 429                 ++key;
 430             }
 431             EXPECT_EQ( static_cast<size_t>(key), nSize );
 432
 433             List const& cl = l;
 434             key = 0;
 435             for ( auto it = cl.begin(); it != cl.end(); ++it ) {
 436                 EXPECT_EQ( key, it->first.nKey );
 437                 EXPECT_EQ( it->first.nKey * 2, it->second.val );
 438                 ++key;
 439             }
 440             EXPECT_EQ( static_cast<size_t>(key), nSize );
 441
 442             l.clear();
 443             ASSERT_TRUE( l.empty() );
 444             EXPECT_CONTAINER_SIZE( l, 0 );
 445         }
 446     };
 447
 448 } // namespace cds_test
 449
 450 #endif // CDSUNIT_LIST_TEST_KV_ITERABLE_LIST_H