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