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