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 idx : indices ) {
 100                 auto& i = data[idx];
 101                 i.nDisposeCount = 0;
 102                 ASSERT_TRUE( t.insert( i ));
 103             }
 104
 105             // get/extract
 106             for ( auto idx : indices ) {
 107                 auto& i = data[idx];
 108
 109                 EXPECT_EQ( i.nFindCount, 0u );
 110                 gp = t.get( i );
 111                 ASSERT_FALSE( !gp );
 112                 ++gp->nFindCount;
 113                 EXPECT_EQ( i.nFindCount, 1u );
 114
 115                 gp = t.get( i.key());
 116                 ASSERT_FALSE( !gp );
 117                 ++gp->nFindCount;
 118                 EXPECT_EQ( i.nFindCount, 2u );
 119
 120                 gp = t.get_with( other_item( i.key()), other_less());
 121                 ASSERT_FALSE( !gp );
 122                 ++gp->nFindCount;
 123                 EXPECT_EQ( i.nFindCount, 3u );
 124
 125                 EXPECT_EQ( i.nEraseCount, 0u );
 126                 switch ( i.key() % 3 ) {
 127                 case 0:
 128                     gp = t.extract( i.key());
 129                     break;
 130                 case 1:
 131                     gp = t.extract( i );
 132                     break;
 133                 case 2:
 134                     gp = t.extract_with( other_item( i.key()), other_less());
 135                     break;
 136                 }
 137                 ASSERT_FALSE( !gp );
 138                 ++gp->nEraseCount;
 139                 EXPECT_EQ( i.nEraseCount, 1u );
 140
 141                 gp = t.extract( i );
 142                 ASSERT_TRUE( !gp );
 143                 gp = t.extract( i.key());
 144                 ASSERT_TRUE( !gp );
 145                 gp = t.extract_with( other_item( i.key()), other_less());
 146                 ASSERT_TRUE( !gp );
 147             }
 148
 149             gp.release();
 150
 151             ASSERT_TRUE( t.empty());
 152             ASSERT_CONTAINER_SIZE( t, 0u );
 153
 154             // Force retiring cycle
 155             Tree::gc::force_dispose();
 156             for ( auto& i : data ) {
 157                 EXPECT_EQ( i.nDisposeCount, 1u );
 158             }
 159
 160             // extract_min
 161             for ( auto idx : indices ) {
 162                 auto& i = data[idx];
 163                 i.nDisposeCount = 0;
 164                 ASSERT_TRUE( t.insert( i ));
 165             }
 166
 167             size_t nCount = 0;
 168             int nKey = -1;
 169             while ( !t.empty()) {
 170                 gp = t.extract_min();
 171                 ASSERT_FALSE( !gp );
 172                 EXPECT_EQ( gp->key(), nKey + 1 );
 173                 ++nCount;
 174                 nKey = gp->key();
 175             }
 176             gp.release();
 177             ASSERT_TRUE( t.empty());
 178             ASSERT_CONTAINER_SIZE( t, 0u );
 179             EXPECT_EQ( nCount, data.size());
 180
 181             // Force retiring cycle
 182             Tree::gc::force_dispose();
 183             for ( auto& i : data ) {
 184                 EXPECT_EQ( i.nDisposeCount, 1u );
 185             }
 186
 187             // extract_max
 188             for ( auto idx : indices ) {
 189                 auto& i = data[idx];
 190                 i.nDisposeCount = 0;
 191                 ASSERT_TRUE( t.insert( i ));
 192             }
 193
 194             nCount = 0;
 195             nKey = static_cast<int>( data.size());
 196             while ( !t.empty()) {
 197                 gp = t.extract_max();
 198                 ASSERT_FALSE( !gp );
 199                 EXPECT_EQ( gp->key(), nKey - 1 );
 200                 ++nCount;
 201                 nKey = gp->key();
 202             }
 203             gp.release();
 204             ASSERT_TRUE( t.empty());
 205             ASSERT_CONTAINER_SIZE( t, 0u );
 206             EXPECT_EQ( nCount, data.size());
 207
 208             // Force retiring cycle
 209             Tree::gc::force_dispose();
 210             for ( auto& i : data ) {
 211                 EXPECT_EQ( i.nDisposeCount, 1u );
 212             }
 213
 214         }
 215     };
 216
 217 } // namespace cds_test
 218
 219 #endif // #ifndef CDSUNIT_TREE_TEST_INTRUSIVE_TREE_HP_H