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