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