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