test/unit/tree/test_tree_map_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-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_TREE_TEST_TREE_MAP_HP_H
  32 #define CDSUNIT_TREE_TEST_TREE_MAP_HP_H
  33
  34 #include "test_tree_map.h"
  35
  36 namespace cds_test {
  37
  38     class container_tree_map_hp: public container_tree_map
  39     {
  40         typedef container_tree_map base_class;
  41
  42     protected:
  43         template <class Map>
  44         void test( Map& m )
  45         {
  46             // Precondition: map is empty
  47             // Postcondition: map is empty
  48
  49             base_class::test( m );
  50
  51             ASSERT_TRUE( m.empty());
  52             ASSERT_CONTAINER_SIZE( m, 0 );
  53
  54             typedef typename Map::value_type map_pair;
  55             size_t const kkSize = base_class::kSize;
  56
  57             std::vector<key_type> arrKeys;
  58             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
  59                 arrKeys.push_back( key_type( i ));
  60             shuffle( arrKeys.begin(), arrKeys.end());
  61
  62             std::vector< value_type > arrVals;
  63             for ( size_t i = 0; i < kkSize; ++i ) {
  64                 value_type val;
  65                 val.nVal = static_cast<int>( i );
  66                 val.strVal = std::to_string( i );
  67                 arrVals.push_back( val );
  68             }
  69
  70             for ( auto const& i : arrKeys )
  71                 ASSERT_TRUE( m.insert( i ) );
  72             ASSERT_FALSE( m.empty() );
  73             ASSERT_CONTAINER_SIZE( m, kkSize );
  74
  75             // get/extract
  76             typedef typename Map::guarded_ptr guarded_ptr;
  77             guarded_ptr gp;
  78
  79             for ( auto const& i : arrKeys ) {
  80                 value_type const& val = arrVals.at( i.nKey );
  81
  82                 gp = m.get( i.nKey );
  83                 ASSERT_FALSE( !gp );
  84                 ASSERT_EQ( gp->first.nKey, i.nKey );
  85                 gp.release();
  86                 gp = m.get( i );
  87                 ASSERT_FALSE( !gp );
  88                 ASSERT_EQ( gp->first.nKey, i.nKey );
  89                 gp.release();
  90                 gp = m.get_with( other_item( i.nKey ), other_less());
  91                 ASSERT_FALSE( !gp );
  92                 ASSERT_EQ( gp->first.nKey, i.nKey );
  93
  94                 switch ( i.nKey % 4 ) {
  95                 case 0:
  96                     gp = m.extract( i.nKey );
  97                     break;
  98                 case 1:
  99                     gp = m.extract( i );
 100                     break;
 101                 case 2:
 102                     gp = m.extract( val.strVal );
 103                     break;
 104                 case 3:
 105                     gp = m.extract_with( other_item( i.nKey ), other_less());
 106                     break;
 107                 }
 108                 ASSERT_FALSE( !gp );
 109                 ASSERT_EQ( gp->first.nKey, i.nKey );
 110                 gp.release();
 111
 112                 gp = m.get( i.nKey );
 113                 ASSERT_TRUE( !gp );
 114                 gp = m.get( i );
 115                 ASSERT_TRUE( !gp );
 116                 gp = m.get_with( other_item( i.nKey ), other_less());
 117                 ASSERT_TRUE( !gp );
 118             }
 119             ASSERT_TRUE( m.empty() );
 120             ASSERT_CONTAINER_SIZE( m, 0 );
 121
 122             gp = m.extract_min();
 123             EXPECT_TRUE( !gp );
 124             gp = m.extract_max();
 125             EXPECT_TRUE( !gp );
 126
 127             for ( auto const& i : arrKeys )
 128                 ASSERT_TRUE( m.insert( i ) );
 129             ASSERT_FALSE( m.empty() );
 130             ASSERT_CONTAINER_SIZE( m, kkSize );
 131
 132             // extract_min
 133             int nKey = -1;
 134             size_t nCount = 0;
 135             while ( !m.empty() ) {
 136                 gp = m.extract_min();
 137                 ASSERT_FALSE( !gp );
 138                 EXPECT_EQ( gp->first.nKey, nKey + 1 );
 139                 nKey = gp->first.nKey;
 140                 ++nCount;
 141             }
 142             ASSERT_TRUE( m.empty() );
 143             ASSERT_CONTAINER_SIZE( m, 0 );
 144             EXPECT_EQ( nCount, kkSize );
 145
 146             // extract_max
 147             for ( auto const& i : arrKeys )
 148                 ASSERT_TRUE( m.insert( i ) );
 149             ASSERT_FALSE( m.empty() );
 150             ASSERT_CONTAINER_SIZE( m, kkSize );
 151
 152             nKey = kkSize;
 153             nCount = 0;
 154             while ( !m.empty() ) {
 155                 gp = m.extract_max();
 156                 ASSERT_FALSE( !gp );
 157                 EXPECT_EQ( gp->first.nKey, nKey - 1 );
 158                 nKey = gp->first.nKey;
 159                 ++nCount;
 160             }
 161             ASSERT_TRUE( m.empty() );
 162             ASSERT_CONTAINER_SIZE( m, 0 );
 163             EXPECT_EQ( nCount, kkSize );
 164
 165             ASSERT_TRUE( m.check_consistency());
 166         }
 167     };
 168
 169 } // namespace cds_test
 170
 171 #endif // #ifndef CDSUNIT_TREE_TEST_TREE_MAP_HP_H