test/stress/map/map_type_bronson_avltree.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_MAP_TYPE_BRONSON_AVLTREE_H
  32 #define CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H
  33
  34 #include "map_type.h"
  35
  36 #include <cds/memory/vyukov_queue_pool.h>
  37 #include <cds/sync/pool_monitor.h>
  38 #include <cds/container/bronson_avltree_map_rcu.h>
  39
  40 #include <cds_test/stat_bronson_avltree_out.h>
  41 #include <cds_test/stat_sync_monitor_out.h>
  42
  43 namespace map {
  44
  45     template <class GC, typename Key, typename T, typename Traits = cc::bronson_avltree::traits >
  46     class BronsonAVLTreeMap : public cc::BronsonAVLTreeMap< GC, Key, T, Traits >
  47     {
  48         typedef cc::BronsonAVLTreeMap< GC, Key, T, Traits > base_class;
  49     public:
  50         template <typename Config>
  51         BronsonAVLTreeMap( Config const& /*cfg*/ )
  52             : base_class()
  53         {}
  54
  55         std::pair<Key, bool> extract_min_key()
  56         {
  57             Key key;
  58             typename base_class::exempt_ptr xp = base_class::extract_min( [&key]( Key const& k ) { key = k; } );
  59             if ( xp )
  60                 return std::make_pair( key, true );
  61             return std::make_pair( key, false );
  62         }
  63
  64         std::pair<Key, bool> extract_max_key()
  65         {
  66             Key key;
  67             typename base_class::exempt_ptr xp = base_class::extract_max( [&key]( Key const& k ) { key = k; } );
  68             if ( xp )
  69                 return std::make_pair( key, true );
  70             return std::make_pair( key, false );
  71         }
  72
  73         // for testing
  74         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
  75         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  76         static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
  77     };
  78
  79     struct tag_BronsonAVLTreeMap;
  80
  81     template <typename Key, typename Value>
  82     struct map_type< tag_BronsonAVLTreeMap, Key, Value >: public map_type_base< Key, Value >
  83     {
  84         typedef map_type_base< Key, Value >      base_class;
  85         typedef typename base_class::key_compare compare;
  86         typedef typename base_class::key_less    less;
  87
  88         typedef cds::memory::vyukov_queue_pool< std::mutex >         BronsonAVLTreeMap_simple_pool;
  89         typedef cds::memory::lazy_vyukov_queue_pool< std::mutex >    BronsonAVLTreeMap_lazy_pool;
  90         typedef cds::memory::bounded_vyukov_queue_pool< std::mutex > BronsonAVLTreeMap_bounded_pool;
  91
  92         struct BronsonAVLTreeMap_less: public
  93             cc::bronson_avltree::make_traits<
  94                 co::less< less >
  95                 ,cc::bronson_avltree::relaxed_insert< false >
  96                 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
  97             >::type
  98         {};
  99         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpi_less;
 100         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpb_less;
 101         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpt_less;
 102 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 103         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_shb_less;
 104 #endif
 105         struct BronsonAVLTreeMap_cmp_stat: public
 106             cc::bronson_avltree::make_traits<
 107                 co::compare< compare >
 108                 ,cc::bronson_avltree::relaxed_insert< false >
 109                 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
 110                 ,co::stat< cc::bronson_avltree::stat<>>
 111             >::type
 112         {};
 113         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpi_cmp_stat;
 114         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpb_cmp_stat;
 115         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpt_cmp_stat;
 116 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 117         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_shb_cmp_stat;
 118 #endif
 119
 120         struct BronsonAVLTreeMap_less_pool_simple: public BronsonAVLTreeMap_less
 121         {
 122             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_simple_pool> sync_monitor;
 123         };
 124         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpi_less_pool_simple;
 125         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpb_less_pool_simple;
 126         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpt_less_pool_simple;
 127 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 128         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_shb_less_pool_simple;
 129 #endif
 130         struct BronsonAVLTreeMap_less_pool_simple_stat : public BronsonAVLTreeMap_less
 131         {
 132             typedef cc::bronson_avltree::stat<> stat;
 133             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_simple_pool, cds::opt::none, true > sync_monitor;
 134         };
 135         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_simple_stat;
 136         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_simple_stat;
 137         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat;
 138 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 139         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat;
 140 #endif
 141         struct BronsonAVLTreeMap_less_pool_lazy: public BronsonAVLTreeMap_less
 142         {
 143             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_lazy_pool> sync_monitor;
 144             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 145         };
 146         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpi_less_pool_lazy;
 147         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpb_less_pool_lazy;
 148         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy;
 149 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 150         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_shb_less_pool_lazy;
 151 #endif
 152         struct BronsonAVLTreeMap_less_pool_lazy_stat : public BronsonAVLTreeMap_less
 153         {
 154             typedef cc::bronson_avltree::stat<> stat;
 155             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_lazy_pool, cds::opt::none, true > sync_monitor;
 156             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 157         };
 158         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_lazy_stat;
 159         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_lazy_stat;
 160         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat;
 161 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 162         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat;
 163 #endif
 164         struct BronsonAVLTreeMap_less_pool_bounded: public BronsonAVLTreeMap_less
 165         {
 166             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_bounded_pool> sync_monitor;
 167             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 168         };
 169         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpi_less_pool_bounded;
 170         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpb_less_pool_bounded;
 171         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded;
 172 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 173         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_shb_less_pool_bounded;
 174 #endif
 175         struct BronsonAVLTreeMap_less_pool_bounded_stat : public BronsonAVLTreeMap_less
 176         {
 177             typedef cc::bronson_avltree::stat<> stat;
 178             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_bounded_pool, cds::opt::none, true > sync_monitor;
 179             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 180         };
 181         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_bounded_stat;
 182         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_bounded_stat;
 183         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded_stat;
 184 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 185         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_shb_less_pool_bounded_stat;
 186 #endif
 187     };
 188
 189     template <typename GC, typename Key, typename T, typename Traits>
 190     static inline void print_stat( cds_test::property_stream& o, BronsonAVLTreeMap<GC, Key, T, Traits> const& m )
 191     {
 192         o << m.statistics()
 193           << m.monitor().statistics();
 194     }
 195
 196     template <typename GC, typename Key, typename T, typename Traits>
 197     static inline void check_before_cleanup( BronsonAVLTreeMap<GC, Key, T, Traits>& m )
 198     {
 199         bool check_consistency_result = m.check_consistency([]( size_t nLevel, size_t hLeft, size_t hRight )
 200             {
 201                 EXPECT_TRUE( false ) << "Tree violation on level=" << nLevel << ": hLeft=" << hLeft << ", hRight=" << hRight;
 202             });
 203         EXPECT_TRUE( check_consistency_result ) << "Internal tree structure violation";
 204     }
 205
 206
 207 #define CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, bronson_map_type, key_type, value_type ) \
 208     TEST_F( fixture, bronson_map_type ) \
 209     { \
 210         typedef map::map_type< tag_BronsonAVLTreeMap, key_type, value_type >::bronson_map_type map_type; \
 211         test_case<map_type>(); \
 212     }
 213
 214 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 215 #   define CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
 216         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less,                   key_type, value_type ) \
 217         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_cmp_stat,               key_type, value_type ) \
 218         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_simple,       key_type, value_type ) \
 219         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat,  key_type, value_type ) \
 220         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_lazy,         key_type, value_type ) \
 221         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat,    key_type, value_type ) \
 222
 223 #else
 224 #   define CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
 225 #endif
 226
 227 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
 228 #   define CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type ) \
 229         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_cmp_stat,               key_type, value_type ) \
 230         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple,       key_type, value_type ) \
 231         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple_stat,  key_type, value_type ) \
 232         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy,         key_type, value_type ) \
 233         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy_stat,    key_type, value_type ) \
 234         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple,       key_type, value_type ) \
 235         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_simple_stat,  key_type, value_type ) \
 236         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy,         key_type, value_type ) \
 237         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat,    key_type, value_type ) \
 238         CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
 239
 240 #else
 241 #   define CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type )
 242 #endif
 243
 244 #define CDSSTRESS_BronsonAVLTreeMap( fixture, test_case, key_type, value_type ) \
 245     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less,                   key_type, value_type ) \
 246     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less,                   key_type, value_type ) \
 247     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less,                   key_type, value_type ) \
 248     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_cmp_stat,               key_type, value_type ) \
 249     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_cmp_stat,               key_type, value_type ) \
 250     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_simple,       key_type, value_type ) \
 251     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat,  key_type, value_type ) \
 252     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_lazy,         key_type, value_type ) \
 253     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy_stat,    key_type, value_type ) \
 254     CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type ) \
 255
 256 }   // namespace map
 257
 258 #endif // ifndef CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H