test/unit/list/test_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_LIST_H
  32 #define CDSUNIT_LIST_TEST_LIST_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 namespace cds_test {
  38
  39     class list_common : 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_FALSE( l.find( i, []( value_type&, value_type const&) {} ));
 164                 EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} ));
 165                 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} ));
 166
 167                 switch ( i.nKey & 3 ) {
 168                     case 0:
 169                         EXPECT_TRUE( l.insert( i.nKey ));
 170                         EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
 171                             EXPECT_EQ( n.nVal, key * 2 );
 172                         } ));
 173                         EXPECT_FALSE( l.insert( i.nKey ));
 174                         break;
 175                     case 1:
 176                         EXPECT_TRUE( l.insert( i, []( value_type& n ) {
 177                             n.nVal = n.nKey * 3;
 178                         }));
 179                         EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
 180                             EXPECT_EQ( n.nVal, key * 3 );
 181                         } ));
 182                         EXPECT_FALSE( l.insert( i ));
 183                         break;
 184                     case 2:
 185                         EXPECT_TRUE( l.emplace( i.nKey, i.nKey * 100 ));
 186                         EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
 187                             EXPECT_EQ( n.nVal, key * 100 );
 188                         } ));
 189                         EXPECT_FALSE( l.insert( i ));
 190                         break;
 191                     case 3:
 192                     {
 193                         auto pair = l.update( i.nKey, []( bool bNew, value_type& n, int key ) {
 194                             EXPECT_TRUE( bNew );
 195                             EXPECT_EQ( key, n.nKey );
 196                             n.nVal = n.nKey * 3;
 197                         }, false );
 198                         EXPECT_FALSE( pair.first );
 199                         EXPECT_FALSE( pair.second );
 200
 201                         pair = l.update( i.nKey, []( bool bNew, value_type& n, int key ) {
 202                             EXPECT_TRUE( bNew );
 203                             EXPECT_EQ( key, n.nKey );
 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                 }
 216
 217                 EXPECT_TRUE( l.contains( i ));
 218                 EXPECT_TRUE( l.contains( i.nKey ));
 219                 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()));
 220                 EXPECT_TRUE( l.find( i, []( value_type& n, value_type const& arg ) {
 221                     EXPECT_EQ( arg.nKey, n.nKey );
 222                     n.nVal = n.nKey;
 223                 } ));
 224                 EXPECT_TRUE( l.find( i.nKey, []( value_type& n, int key ) {
 225                     EXPECT_EQ( key, n.nKey );
 226                     EXPECT_EQ( n.nKey, n.nVal );
 227                     n.nVal = n.nKey * 5;
 228                 } ));
 229                 EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& n, other_item const& key ) {
 230                     EXPECT_EQ( key.nKey, n.nKey );
 231                     EXPECT_EQ( n.nKey * 5, n.nVal );
 232                 } ));
 233
 234                 auto pair = l.update( i.nKey, []( bool bNew, value_type& n, int key ) {
 235                     EXPECT_FALSE( bNew );
 236                     EXPECT_EQ( key, n.nKey );
 237                     EXPECT_EQ( key * 5, n.nVal );
 238                     n.nVal = n.nKey * 3;
 239                 }, false );
 240                 EXPECT_TRUE( pair.first );
 241                 EXPECT_FALSE( pair.second );
 242
 243                 EXPECT_FALSE( l.empty());
 244             }
 245
 246             ASSERT_FALSE( l.empty());
 247             EXPECT_CONTAINER_SIZE( l, nSize );
 248
 249             // erase
 250             for ( auto const&i : arr ) {
 251                 switch ( i.nKey & 3 ) {
 252                     case 0:
 253                         EXPECT_TRUE( l.erase( i.nKey ));
 254                         break;
 255                     case 1:
 256                         EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less()));
 257                         break;
 258                     case 2:
 259                         EXPECT_TRUE( l.erase( i, [ &i ]( value_type const& n ) {
 260                             EXPECT_EQ( n.nKey, i.nKey );
 261                             EXPECT_EQ( n.nKey * 3, n.nVal );
 262                         }));
 263                         break;
 264                     case 3:
 265                         EXPECT_TRUE( l.erase_with( other_item( i.nKey ), other_less(), [ &i ]( value_type const& n) {
 266                             EXPECT_EQ( n.nKey, i.nKey );
 267                             EXPECT_EQ( n.nKey * 3, n.nVal );
 268                         } ));
 269                 }
 270
 271                 EXPECT_FALSE( l.contains( i ));
 272                 EXPECT_FALSE( l.contains( i.nKey ));
 273                 EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less()));
 274                 EXPECT_FALSE( l.find( i, []( value_type&, value_type const&) {} ));
 275                 EXPECT_FALSE( l.find( i.nKey, []( value_type&, int ) {} ));
 276                 EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type&, other_item const& ) {} ));
 277             }
 278
 279             ASSERT_TRUE( l.empty());
 280             EXPECT_CONTAINER_SIZE( l, 0 );
 281
 282             // clear test
 283             for ( auto& i : arr )
 284                 EXPECT_TRUE( l.insert( i ));
 285
 286             ASSERT_FALSE( l.empty());
 287             EXPECT_CONTAINER_SIZE( l, nSize );
 288
 289             l.clear();
 290
 291             ASSERT_TRUE( l.empty());
 292             EXPECT_CONTAINER_SIZE( l, 0 );
 293
 294             // empty list iterator test
 295             {
 296                 List const& cl = l;
 297                 EXPECT_TRUE( l.begin() == l.end());
 298                 EXPECT_TRUE( l.cbegin() == l.cend());
 299                 EXPECT_TRUE( cl.begin() == cl.end());
 300                 EXPECT_TRUE( l.begin() == l.cend());
 301                 EXPECT_TRUE( cl.begin() == l.end());
 302             }
 303         }
 304
 305         template <typename List>
 306         void test_ordered_iterator( List& l )
 307         {
 308             // Precondition: list is empty
 309             // Postcondition: list is empty
 310
 311             static const size_t nSize = 20;
 312             typedef typename List::value_type value_type;
 313             value_type arr[nSize];
 314
 315             for ( size_t i = 0; i < nSize; ++i ) {
 316                 arr[i].nKey = static_cast<int>(i);
 317                 arr[i].nVal = arr[i].nKey;
 318             }
 319             shuffle( arr, arr + nSize );
 320
 321             ASSERT_TRUE( l.empty());
 322             ASSERT_CONTAINER_SIZE( l, 0 );
 323
 324             for ( auto& i : arr )
 325                 EXPECT_TRUE( l.insert( i ));
 326
 327             int key = 0;
 328             for ( auto& it : l ) {
 329                 EXPECT_EQ( key, it.nKey );
 330                 EXPECT_EQ( it.nVal, it.nKey );
 331                 it.nVal = it.nKey * 10;
 332                 ++key;
 333             }
 334             EXPECT_EQ( static_cast<size_t>(key), nSize );
 335
 336             key = 0;
 337             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 338                 EXPECT_EQ( key, it->nKey );
 339                 EXPECT_EQ( key, (*it).nKey );
 340                 EXPECT_EQ( it->nKey * 10, it->nVal );
 341                 ++key;
 342             }
 343             EXPECT_EQ( static_cast<size_t>(key), nSize );
 344
 345             key = 0;
 346             for ( auto it = l.begin(); it != l.end(); ++it ) {
 347                 EXPECT_EQ( key, it->nKey );
 348                 EXPECT_EQ( key, (*it).nKey );
 349                 EXPECT_EQ( it->nKey * 10, it->nVal );
 350                 it->nVal = it->nKey * 2;
 351                 ++key;
 352             }
 353             EXPECT_EQ( static_cast<size_t>(key), nSize );
 354
 355             List const& cl = l;
 356             key = 0;
 357             for ( auto it = cl.begin(); it != cl.end(); ++it ) {
 358                 EXPECT_EQ( key, it->nKey );
 359                 EXPECT_EQ( key, (*it).nKey );
 360                 EXPECT_EQ( it->nKey * 2, it->nVal );
 361                 ++key;
 362             }
 363             EXPECT_EQ( static_cast<size_t>(key), nSize );
 364
 365             l.clear();
 366             ASSERT_TRUE( l.empty());
 367             EXPECT_CONTAINER_SIZE( l, 0 );
 368         }
 369     };
 370
 371 } // namespace cds_test
 372
 373 #endif // CDSUNIT_LIST_TEST_LIST_H