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