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-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_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::key_type    list_key_type;
 151             typedef typename List::mapped_type list_mapped_type;
 152             typedef typename List::value_type  list_value_type;
 153
 154             struct key_val {
 155                 int key;
 156                 int val;
 157             };
 158             key_val arr[nSize];
 159
 160             for ( size_t i = 0; i < nSize; ++i ) {
 161                 arr[i].key = static_cast<int>(i) + 1;
 162                 arr[i].val = arr[i].key * 10;
 163             }
 164             shuffle( arr, arr + nSize );
 165
 166             ASSERT_TRUE( l.empty() );
 167             ASSERT_CONTAINER_SIZE( l, 0 );
 168
 169             // insert/find
 170             for ( key_val const& i : arr ) {
 171                 EXPECT_TRUE( l.contains( i.key ) == l.end());
 172                 EXPECT_TRUE( l.contains( key_type( i.key )) == l.end());
 173                 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) == l.end());
 174
 175                 switch ( i.key % 5 ) {
 176                     case 0:
 177                     {
 178                         auto it = l.insert( i.key );
 179                         ASSERT_FALSE( it == l.end());
 180                         EXPECT_EQ( it->first.key, i.key );
 181                         EXPECT_EQ( it->second.val, 0 );
 182                         it = l.contains( i.key );
 183                         EXPECT_FALSE( it == l.end() );
 184                         EXPECT_EQ( it->first.key, i.key );
 185                         EXPECT_EQ( it->second.val, 0 );
 186                         it = l.insert( i.key );
 187                         EXPECT_TRUE( it == l.end() );
 188                         break;
 189                     }
 190                     case 1:
 191                     {
 192                         auto it = l.insert( i.key, i.val );
 193                         ASSERT_FALSE( it == l.end() );
 194                         EXPECT_EQ( it->first.key, i.key );
 195                         EXPECT_EQ( it->second.val, i.val );
 196                         it = l.contains( key_type( i.key ));
 197                         EXPECT_FALSE( it == l.end() );
 198                         EXPECT_EQ( it->first.key, i.key );
 199                         EXPECT_EQ( it->second.val, i.val );
 200                         it = l.insert( key_type( i.key ), i.val );
 201                         EXPECT_TRUE( it == l.end() );
 202                         break;
 203                     }
 204                     case 2:
 205                     {
 206                         auto it = l.emplace( i.key, i.key * 100 );
 207                         ASSERT_FALSE( it == l.end() );
 208                         EXPECT_EQ( it->first.key, i.key );
 209                         EXPECT_EQ( it->second.val, i.key * 100 );
 210                         it = l.contains( other_key( i.key ), other_less());
 211                         ASSERT_FALSE( it == l.end() );
 212                         EXPECT_EQ( it->first.key, i.key );
 213                         EXPECT_EQ( it->second.val, i.key * 100 );
 214                         it = l.emplace( i.key, i.key * 50 );
 215                         EXPECT_TRUE( it == l.end() );
 216                         break;
 217                     }
 218                     case 3:
 219                     {
 220                         auto pair = l.update( i.key, false );
 221                         EXPECT_TRUE( pair.first == l.end());
 222                         EXPECT_FALSE( pair.second );
 223
 224                         pair = l.update( i.key );
 225                         ASSERT_FALSE( pair.first == l.end() );
 226                         EXPECT_TRUE( pair.second );
 227                         pair.first->second.val = i.key * 3;
 228
 229                         auto it = l.contains( other_key( i.key ), other_less() );
 230                         ASSERT_FALSE( it == l.end() );
 231                         EXPECT_TRUE( it == pair.first );
 232                         EXPECT_EQ( it->first.key, i.key );
 233                         EXPECT_EQ( it->second.val, i.key * 3 );
 234
 235                         pair = l.update( i.key, false );
 236                         ASSERT_FALSE( pair.first == l.end() );
 237                         EXPECT_TRUE( pair.first == it );
 238                         EXPECT_FALSE( pair.second );
 239                         EXPECT_EQ( pair.first->first.key, i.key );
 240                         pair.first->second.val = i.key * 5;
 241
 242                         it = l.contains( other_key( i.key ), other_less() );
 243                         ASSERT_FALSE( it == l.end() );
 244                         EXPECT_TRUE( it == pair.first );
 245                         EXPECT_EQ( it->first.key, i.key );
 246                         EXPECT_EQ( it->second.val, i.key * 5 );
 247                         break;
 248                     }
 249                     case 4:
 250                     {
 251                         auto it = l.insert_with( key_type( i.key ), [&i]( list_value_type& n ) {
 252                             EXPECT_EQ( i.key, n.first.key );
 253                             n.second.val = n.first.key * 7;
 254                         });
 255                         ASSERT_FALSE( it == l.end() );
 256                         EXPECT_EQ( it->first.key, i.key );
 257                         EXPECT_EQ( it->second.val, i.key * 7 );
 258                         it = l.contains( i.key );
 259                         ASSERT_FALSE( it == l.end() );
 260                         EXPECT_EQ( it->first.key, i.key );
 261                         EXPECT_EQ( it->second.val, i.key * 7 );
 262                         it = l.insert_with( i.key, []( list_value_type& ) {
 263                             EXPECT_TRUE( false );
 264                         });
 265                         EXPECT_TRUE( it == l.end() );
 266                         break;
 267                     }
 268                 }
 269
 270                 EXPECT_TRUE( l.contains( i.key ) != l.end());
 271                 EXPECT_TRUE( l.contains( key_type( i.key )) != l.end());
 272                 EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) != l.end());
 273
 274                 EXPECT_FALSE( l.empty() );
 275             }
 276
 277             ASSERT_FALSE( l.empty() );
 278             EXPECT_CONTAINER_SIZE( l, nSize );
 279
 280             l.clear();
 281
 282             ASSERT_TRUE( l.empty() );
 283             EXPECT_CONTAINER_SIZE( l, 0 );
 284
 285             // empty list iterator test
 286             {
 287                 List const& cl = l;
 288                 EXPECT_TRUE( l.begin() == l.end());
 289                 EXPECT_TRUE( l.cbegin() == l.cend());
 290                 EXPECT_TRUE( cl.begin() == cl.end());
 291                 EXPECT_TRUE( l.begin() == l.cend());
 292                 EXPECT_TRUE( cl.begin() == l.end());
 293             }
 294         }
 295
 296         template <typename List>
 297         void test_ordered_iterator( List& l )
 298         {
 299             // Precondition: list is empty
 300             // Postcondition: list is empty
 301
 302             static const size_t nSize = 20;
 303             typedef typename List::key_type    list_key_type;
 304             typedef typename List::mapped_type list_mapped_type;
 305             typedef typename List::value_type  list_value_type;
 306
 307             struct key_val {
 308                 int key;
 309                 int val;
 310             };
 311             key_val arr[nSize];
 312
 313             for ( size_t i = 0; i < nSize; ++i ) {
 314                 arr[i].key = static_cast<int>(i);
 315                 arr[i].val = arr[i].key;
 316             }
 317             shuffle( arr, arr + nSize );
 318
 319             ASSERT_TRUE( l.empty() );
 320             ASSERT_CONTAINER_SIZE( l, 0 );
 321
 322             for ( auto& i : arr )
 323                 EXPECT_TRUE( l.insert( i.key, i.val ) != l.end());
 324
 325             int key = 0;
 326             for ( auto& it : l ) {
 327                 EXPECT_EQ( key, it.first.key );
 328                 EXPECT_EQ( it.second.val, it.first.key );
 329                 it.second.val = it.first.key * 10;
 330                 ++key;
 331             }
 332             EXPECT_EQ( static_cast<size_t>(key), nSize );
 333
 334             key = 0;
 335             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 336                 EXPECT_EQ( key, it->first.key );
 337                 EXPECT_EQ( key, (*it).first.key );
 338                 EXPECT_EQ( it->first.key * 10, it->second.val );
 339                 ++key;
 340             }
 341             EXPECT_EQ( static_cast<size_t>(key), nSize );
 342
 343             key = 0;
 344             for ( auto it = l.begin(); it != l.end(); ++it ) {
 345                 EXPECT_EQ( key, it->first.key );
 346                 EXPECT_EQ( it->first.key * 10, it->second.val );
 347                 it->second.val = it->first.key * 2;
 348                 ++key;
 349             }
 350             EXPECT_EQ( static_cast<size_t>(key), nSize );
 351
 352             List const& cl = l;
 353             key = 0;
 354             for ( auto it = cl.begin(); it != cl.end(); ++it ) {
 355                 EXPECT_EQ( key, it->first.key );
 356                 EXPECT_EQ( it->first.key * 2, it->second.val );
 357                 ++key;
 358             }
 359             EXPECT_EQ( static_cast<size_t>(key), nSize );
 360
 361             l.clear();
 362             ASSERT_TRUE( l.empty() );
 363             EXPECT_CONTAINER_SIZE( l, 0 );
 364         }
 365     };
 366
 367 } // namespace cds_test
 368
 369 #endif // CDSUNIT_LIST_TEST_KV_LIST_NOGC_H