test/unit/tree/test_intrusive_tree_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_INTRUSIVE_TREE_HP_H
  32 #define CDSUNIT_TREE_TEST_INTRUSIVE_TREE_HP_H
  33
  34 #include "test_intrusive_tree.h"
  35
  36 // forward declaration
  37 namespace cds { namespace intrusive {}}
  38
  39 namespace cds_test {
  40
  41     namespace ci = cds::intrusive;
  42
  43     class intrusive_tree_hp: public intrusive_tree
  44     {
  45         typedef intrusive_tree base_class;
  46
  47     protected:
  48
  49         template <class Tree>
  50         void test( Tree& t )
  51         {
  52             // Precondition: tree is empty
  53             // Postcondition: tree is empty
  54
  55             base_class::test( t );
  56
  57             ASSERT_TRUE( t.empty() );
  58             ASSERT_CONTAINER_SIZE( t, 0 );
  59
  60             typedef typename Tree::value_type value_type;
  61
  62             std::vector< value_type > data;
  63             std::vector< size_t> indices;
  64             data.reserve( kSize );
  65             indices.reserve( kSize );
  66             for ( size_t key = 0; key < kSize; ++key ) {
  67                 data.push_back( value_type( static_cast<int>(key) ) );
  68                 indices.push_back( key );
  69             }
  70             shuffle( indices.begin(), indices.end() );
  71
  72             typename Tree::guarded_ptr gp;
  73
  74             // get/extract from empty tree
  75             for ( auto idx : indices ) {
  76                 auto& i = data[idx];
  77
  78                 gp = t.get( i );
  79                 ASSERT_TRUE( !gp );
  80                 gp = t.get( i.key() );
  81                 ASSERT_TRUE( !gp );
  82                 gp = t.get_with( other_item( i.key()), other_less());
  83                 ASSERT_TRUE( !gp );
  84
  85                 gp = t.extract( i );
  86                 ASSERT_TRUE( !gp );
  87                 gp = t.extract( i.key());
  88                 ASSERT_TRUE( !gp );
  89                 gp = t.extract_with( other_item( i.key()), other_less());
  90                 ASSERT_TRUE( !gp );
  91
  92                 gp = t.extract_min();
  93                 ASSERT_TRUE( !gp );
  94                 gp = t.extract_max();
  95                 ASSERT_TRUE( !gp );
  96             }
  97
  98             // fill tree
  99             for ( auto& i : data ) {
 100                 i.nDisposeCount = 0;
 101                 ASSERT_TRUE( t.insert( i ) );
 102             }
 103
 104             // get/extract
 105             for ( auto idx : indices ) {
 106                 auto& i = data[idx];
 107
 108                 EXPECT_EQ( i.nFindCount, 0 );
 109                 gp = t.get( i );
 110                 ASSERT_FALSE( !gp );
 111                 ++gp->nFindCount;
 112                 EXPECT_EQ( i.nFindCount, 1 );
 113
 114                 gp = t.get( i.key() );
 115                 ASSERT_FALSE( !gp );
 116                 ++gp->nFindCount;
 117                 EXPECT_EQ( i.nFindCount, 2 );
 118
 119                 gp = t.get_with( other_item( i.key()), other_less());
 120                 ASSERT_FALSE( !gp );
 121                 ++gp->nFindCount;
 122                 EXPECT_EQ( i.nFindCount, 3 );
 123
 124                 EXPECT_EQ( i.nEraseCount, 0 );
 125                 switch ( i.key() % 3 ) {
 126                 case 0:
 127                     gp = t.extract( i.key());
 128                     break;
 129                 case 1:
 130                     gp = t.extract( i );
 131                     break;
 132                 case 2:
 133                     gp = t.extract_with( other_item( i.key() ), other_less() );
 134                     break;
 135                 }
 136                 ASSERT_FALSE( !gp );
 137                 ++gp->nEraseCount;
 138                 EXPECT_EQ( i.nEraseCount, 1 );
 139
 140                 gp = t.extract( i );
 141                 ASSERT_TRUE( !gp );
 142                 gp = t.extract( i.key() );
 143                 ASSERT_TRUE( !gp );
 144                 gp = t.extract_with( other_item( i.key() ), other_less() );
 145                 ASSERT_TRUE( !gp );
 146             }
 147
 148             gp.release();
 149
 150             ASSERT_TRUE( t.empty() );
 151             ASSERT_CONTAINER_SIZE( t, 0 );
 152
 153             // Force retiring cycle
 154             Tree::gc::force_dispose();
 155             for ( auto& i : data ) {
 156                 EXPECT_EQ( i.nDisposeCount, 1 );
 157             }
 158
 159             // extract_min
 160             for ( auto& i : data ) {
 161                 i.nDisposeCount = 0;
 162                 ASSERT_TRUE( t.insert( i ) );
 163             }
 164
 165             size_t nCount = 0;
 166             int nKey = -1;
 167             while ( !t.empty() ) {
 168                 gp = t.extract_min();
 169                 ASSERT_FALSE( !gp );
 170                 EXPECT_EQ( gp->key(), nKey + 1 );
 171                 ++nCount;
 172                 nKey = gp->key();
 173             }
 174             gp.release();
 175             ASSERT_TRUE( t.empty() );
 176             ASSERT_CONTAINER_SIZE( t, 0 );
 177             EXPECT_EQ( nCount, data.size() );
 178
 179             // Force retiring cycle
 180             Tree::gc::force_dispose();
 181             for ( auto& i : data ) {
 182                 EXPECT_EQ( i.nDisposeCount, 1 );
 183             }
 184
 185             // extract_max
 186             for ( auto& i : data ) {
 187                 i.nDisposeCount = 0;
 188                 ASSERT_TRUE( t.insert( i ) );
 189             }
 190
 191             nCount = 0;
 192             nKey = static_cast<int>( data.size());
 193             while ( !t.empty() ) {
 194                 gp = t.extract_max();
 195                 ASSERT_FALSE( !gp );
 196                 EXPECT_EQ( gp->key(), nKey - 1 );
 197                 ++nCount;
 198                 nKey = gp->key();
 199             }
 200             gp.release();
 201             ASSERT_TRUE( t.empty() );
 202             ASSERT_CONTAINER_SIZE( t, 0 );
 203             EXPECT_EQ( nCount, data.size() );
 204
 205             // Force retiring cycle
 206             Tree::gc::force_dispose();
 207             for ( auto& i : data ) {
 208                 EXPECT_EQ( i.nDisposeCount, 1 );
 209             }
 210
 211         }
 212     };
 213
 214 } // namespace cds_test
 215
 216 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_HP_H