test/unit/tree/test_tree_set_hp.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_SET_TEST_TREE_SET_HP_H
  32 #define CDSUNIT_SET_TEST_TREE_SET_HP_H
  33
  34 #include "test_tree_set.h"
  35
  36 namespace cds_test {
  37
  38     class container_tree_set_hp: public container_tree_set
  39     {
  40         typedef container_tree_set base_class;
  41
  42     protected:
  43         template <typename Set>
  44         void test( Set& s )
  45         {
  46             // Precondition: set is empty
  47             // Postcondition: set is empty
  48
  49             ASSERT_TRUE( s.empty());
  50             ASSERT_CONTAINER_SIZE( s, 0 );
  51
  52             base_class::test( s );
  53
  54             typedef typename Set::value_type value_type;
  55
  56             size_t const nSetSize = kSize;
  57             std::vector< value_type > data;
  58             std::vector< size_t> indices;
  59             data.reserve( kSize );
  60             indices.reserve( kSize );
  61             for ( size_t key = 0; key < kSize; ++key ) {
  62                 data.push_back( value_type( static_cast<int>(key)));
  63                 indices.push_back( key );
  64             }
  65             shuffle( indices.begin(), indices.end());
  66
  67             for ( auto i : indices ) {
  68                 ASSERT_TRUE( s.insert( data[i] ));
  69             }
  70             ASSERT_FALSE( s.empty());
  71             ASSERT_CONTAINER_SIZE( s, nSetSize );
  72
  73             typedef typename Set::guarded_ptr guarded_ptr;
  74             guarded_ptr gp;
  75
  76             // get()
  77             for ( auto idx : indices ) {
  78                 auto& i = data[idx];
  79
  80                 ASSERT_TRUE( !gp );
  81                 switch ( idx % 3 ) {
  82                 case 0:
  83                     gp = s.get( i.key());
  84                     ASSERT_FALSE( !gp );
  85                     break;
  86                 case 1:
  87                     gp = s.get( i );
  88                     ASSERT_FALSE( !gp );
  89                     break;
  90                 case 2:
  91                     gp = s.get_with( other_item( i.key()), other_less());
  92                     ASSERT_FALSE( !gp );
  93                 }
  94                 EXPECT_EQ( gp->key(), i.key());
  95                 gp->nFindCount = gp->key() * 3;
  96
  97                 gp.release();
  98             }
  99
 100             // extract()
 101             for ( auto idx : indices ) {
 102                 auto& i = data[idx];
 103
 104                 ASSERT_TRUE( !gp );
 105                 switch ( idx % 3 ) {
 106                 case 0:
 107                     gp = s.extract( i.key());
 108                     ASSERT_FALSE( !gp );
 109                     break;
 110                 case 1:
 111                     gp = s.extract( i );
 112                     ASSERT_FALSE( !gp );
 113                     break;
 114                 case 2:
 115                     gp = s.extract_with( other_item( i.key()), other_less());
 116                     ASSERT_FALSE( !gp );
 117                     break;
 118                 }
 119                 EXPECT_EQ( gp->key(), i.key());
 120                 EXPECT_EQ( gp->nFindCount, static_cast<size_t>( i.key() * 3 ));
 121
 122                 switch ( idx % 3 ) {
 123                 case 0:
 124                     gp = s.extract( i.key());
 125                     break;
 126                 case 1:
 127                     gp = s.extract( i );
 128                     break;
 129                 case 2:
 130                     gp = s.extract_with( other_item( i.key()), other_less());
 131                     break;
 132                 }
 133                 ASSERT_TRUE( !gp );
 134             }
 135
 136             ASSERT_TRUE( s.empty());
 137             ASSERT_CONTAINER_SIZE( s, 0 );
 138
 139             for ( auto i : indices ) {
 140                 ASSERT_TRUE( s.insert( data[i] ));
 141             }
 142             ASSERT_FALSE( s.empty());
 143             ASSERT_CONTAINER_SIZE( s, nSetSize );
 144
 145             // extract_min
 146             size_t nCount = 0;
 147             int nKey = -1;
 148             while ( !s.empty()) {
 149                 gp = s.extract_min();
 150                 ASSERT_FALSE( !gp );
 151                 EXPECT_EQ( nKey + 1, gp->key());
 152                 ++nCount;
 153                 nKey = gp->key();
 154             }
 155             gp.release();
 156             EXPECT_EQ( nCount, nSetSize );
 157
 158             ASSERT_TRUE( s.empty());
 159             ASSERT_CONTAINER_SIZE( s, 0 );
 160
 161             // extract_max
 162             for ( auto i : indices ) {
 163                 ASSERT_TRUE( s.insert( data[i] ));
 164             }
 165             ASSERT_FALSE( s.empty());
 166             ASSERT_CONTAINER_SIZE( s, nSetSize );
 167
 168             nCount = 0;
 169             nKey = nSetSize;
 170             while ( !s.empty()) {
 171                 gp = s.extract_max();
 172                 ASSERT_FALSE( !gp );
 173                 EXPECT_EQ( nKey - 1, gp->key());
 174                 ++nCount;
 175                 nKey = gp->key();
 176             }
 177             gp.release();
 178             EXPECT_EQ( nCount, nSetSize );
 179
 180             ASSERT_TRUE( s.empty());
 181             ASSERT_CONTAINER_SIZE( s, 0 );
 182
 183         }
 184
 185     };
 186 } // namespace cds_test
 187
 188 #endif // CDSUNIT_SET_TEST_TREE_SET_HP_H