test/unit/list/test_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_LIST_NOGC_H
  32 #define CDSUNIT_LIST_TEST_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 list_nogc : 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( 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_TRUE( l.contains( i ) == l.end());
 161                 EXPECT_TRUE( l.contains( i.nKey ) == l.end());
 162                 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()) == l.end());
 163
 164                 switch ( i.nKey & 3 ) {
 165                     case 0:
 166                     {
 167                         auto it = l.insert( i.nKey );
 168                         EXPECT_FALSE( it == l.end());
 169                         EXPECT_EQ( it->nKey, i.nKey );
 170                         EXPECT_EQ( it->nVal, it->nKey * 2 );
 171                         it = l.contains( i.nKey );
 172                         EXPECT_FALSE( it == l.end());
 173                         EXPECT_EQ( it->nKey, i.nKey );
 174                         EXPECT_EQ( it->nVal, it->nKey * 2 );
 175                         it = l.insert( i.nKey );
 176                         EXPECT_TRUE( it == l.end());
 177                         break;
 178                     }
 179                     case 1:
 180                     {
 181                         auto it = l.insert( i );
 182                         EXPECT_FALSE( it == l.end());
 183                         EXPECT_EQ( it->nKey, i.nKey );
 184                         EXPECT_EQ( it->nVal, i.nVal );
 185                         it = l.contains( i );
 186                         EXPECT_FALSE( it == l.end());
 187                         EXPECT_EQ( it->nKey, i.nKey );
 188                         EXPECT_EQ( it->nVal, i.nVal );
 189                         it = l.insert( i );
 190                         EXPECT_TRUE( it == l.end());
 191                         break;
 192                     }
 193                     case 2:
 194                     {
 195                         auto it = l.emplace( i.nKey, i.nKey * 100 );
 196                         EXPECT_FALSE( it == l.end());
 197                         EXPECT_EQ( it->nKey, i.nKey );
 198                         EXPECT_EQ( it->nVal, i.nKey * 100 );
 199                         it = l.contains( other_item( i.nKey ), other_less());
 200                         EXPECT_FALSE( it == l.end());
 201                         EXPECT_EQ( it->nKey, i.nKey );
 202                         EXPECT_EQ( it->nVal, i.nKey * 100 );
 203                         it = l.emplace( i.nKey, i.nKey * 50 );
 204                         EXPECT_TRUE( it == l.end());
 205                         break;
 206                     }
 207                     case 3:
 208                     {
 209                         auto pair = l.update( i.nKey, false );
 210                         EXPECT_TRUE( pair.first == l.end());
 211                         EXPECT_FALSE( pair.second );
 212
 213                         pair = l.update( i.nKey );
 214                         EXPECT_FALSE( pair.first == l.end());
 215                         EXPECT_TRUE( pair.second );
 216                         pair.first->nVal = i.nKey * 3;
 217                         EXPECT_EQ( pair.first->nKey, i.nKey );
 218
 219                         auto it = l.contains( other_item( i.nKey ), other_less());
 220                         EXPECT_FALSE( it == l.end());
 221                         EXPECT_TRUE( it == pair.first );
 222                         EXPECT_EQ( it->nKey, i.nKey );
 223                         EXPECT_EQ( it->nVal, i.nKey * 3 );
 224
 225                         pair = l.update( i.nKey, false );
 226                         EXPECT_FALSE( pair.first == l.end());
 227                         EXPECT_TRUE( pair.first == it );
 228                         EXPECT_FALSE( pair.second );
 229                         EXPECT_EQ( pair.first->nKey, i.nKey );
 230                         pair.first->nVal = i.nKey * 5;
 231
 232                         it = l.contains( other_item( i.nKey ), other_less());
 233                         EXPECT_FALSE( it == l.end());
 234                         EXPECT_TRUE( it == pair.first );
 235                         EXPECT_EQ( it->nKey, i.nKey );
 236                         EXPECT_EQ( it->nVal, i.nKey * 5 );
 237                     }
 238                     break;
 239                 }
 240
 241                 EXPECT_TRUE( l.contains( i ) != l.end());
 242                 EXPECT_TRUE( l.contains( i.nKey ) != l.end());
 243                 EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()) != l.end());
 244
 245                 EXPECT_FALSE( l.empty());
 246             }
 247
 248             ASSERT_FALSE( l.empty());
 249             EXPECT_CONTAINER_SIZE( l, nSize );
 250
 251             l.clear();
 252
 253             ASSERT_TRUE( l.empty());
 254             EXPECT_CONTAINER_SIZE( l, 0 );
 255
 256             // empty list iterator test
 257             {
 258                 List const& cl = l;
 259                 EXPECT_TRUE( l.begin() == l.end());
 260                 EXPECT_TRUE( l.cbegin() == l.cend());
 261                 EXPECT_TRUE( cl.begin() == cl.end());
 262                 EXPECT_TRUE( l.begin() == l.cend());
 263                 EXPECT_TRUE( cl.begin() == l.end());
 264             }
 265         }
 266
 267         template <typename List>
 268         void test_ordered_iterator( List& l )
 269         {
 270             // Precondition: list is empty
 271             // Postcondition: list is empty
 272
 273             static const size_t nSize = 20;
 274             typedef typename List::value_type value_type;
 275             value_type arr[nSize];
 276
 277             for ( size_t i = 0; i < nSize; ++i ) {
 278                 arr[i].nKey = static_cast<int>(i);
 279                 arr[i].nVal = arr[i].nKey;
 280             }
 281             shuffle( arr, arr + nSize );
 282
 283             ASSERT_TRUE( l.empty());
 284             ASSERT_CONTAINER_SIZE( l, 0 );
 285
 286             for ( auto& i : arr )
 287                 EXPECT_TRUE( l.insert( i ) != l.end());
 288
 289             int key = 0;
 290             for ( auto& it : l ) {
 291                 EXPECT_EQ( key, it.nKey );
 292                 EXPECT_EQ( it.nVal, it.nKey );
 293                 it.nVal = it.nKey * 10;
 294                 ++key;
 295             }
 296             EXPECT_EQ( static_cast<size_t>(key), nSize );
 297
 298             key = 0;
 299             for ( auto it = l.cbegin(); it != l.cend(); ++it ) {
 300                 EXPECT_EQ( key, it->nKey );
 301                 EXPECT_EQ( key, (*it).nKey );
 302                 EXPECT_EQ( it->nKey * 10, it->nVal );
 303                 ++key;
 304             }
 305             EXPECT_EQ( static_cast<size_t>(key), nSize );
 306
 307             key = 0;
 308             for ( auto it = l.begin(); it != l.end(); ++it ) {
 309                 EXPECT_EQ( key, it->nKey );
 310                 EXPECT_EQ( key, (*it).nKey );
 311                 EXPECT_EQ( it->nKey * 10, it->nVal );
 312                 it->nVal = it->nKey * 2;
 313                 ++key;
 314             }
 315             EXPECT_EQ( static_cast<size_t>(key), nSize );
 316
 317             List const& cl = l;
 318             key = 0;
 319             for ( auto it = cl.begin(); it != cl.end(); ++it ) {
 320                 EXPECT_EQ( key, it->nKey );
 321                 EXPECT_EQ( key, (*it).nKey );
 322                 EXPECT_EQ( it->nKey * 2, it->nVal );
 323                 ++key;
 324             }
 325             EXPECT_EQ( static_cast<size_t>(key), nSize );
 326
 327             l.clear();
 328             ASSERT_TRUE( l.empty());
 329             EXPECT_CONTAINER_SIZE( l, 0 );
 330         }
 331     };
 332
 333 } // namespace cds_test
 334
 335 #endif // CDSUNIT_LIST_TEST_LIST_NOGC_H