tests/unit/map2/map_type_bronson_avltree.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H
   4 #define CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H
   5
   6 #include "map2/map_type.h"
   7
   8 #include <cds/memory/vyukov_queue_pool.h>
   9 #include <cds/sync/pool_monitor.h>
  10 #include <cds/container/bronson_avltree_map_rcu.h>
  11
  12 #include "print_bronsonavltree_stat.h"
  13 #include "print_sync_monitor_stat.h"
  14
  15 namespace map2 {
  16
  17     template <class GC, typename Key, typename T, typename Traits = cc::bronson_avltree::traits >
  18     class BronsonAVLTreeMap : public cc::BronsonAVLTreeMap< GC, Key, T, Traits >
  19     {
  20         typedef cc::BronsonAVLTreeMap< GC, Key, T, Traits > base_class;
  21     public:
  22         template <typename Config>
  23         BronsonAVLTreeMap( Config const& /*cfg*/)
  24             : base_class()
  25         {}
  26
  27         // for testing
  28         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
  29         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  30         static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
  31     };
  32
  33     struct tag_BronsonAVLTreeMap;
  34
  35     template <typename Key, typename Value>
  36     struct map_type< tag_BronsonAVLTreeMap, Key, Value >: public map_type_base< Key, Value >
  37     {
  38         typedef map_type_base< Key, Value > base_class;
  39         typedef typename base_class::compare    compare;
  40         typedef typename base_class::less       less;
  41
  42         typedef cds::memory::vyukov_queue_pool< std::mutex > BronsonAVLTreeMap_simple_pool;
  43         typedef cds::memory::lazy_vyukov_queue_pool< std::mutex > BronsonAVLTreeMap_lazy_pool;
  44         typedef cds::memory::bounded_vyukov_queue_pool< std::mutex > BronsonAVLTreeMap_bounded_pool;
  45
  46         struct BronsonAVLTreeMap_less: public
  47             cc::bronson_avltree::make_traits<
  48                 co::less< less >
  49                 ,cc::bronson_avltree::relaxed_insert< false >
  50                 ,co::item_counter< cds::atomicity::item_counter >
  51             >::type
  52         {};
  53         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpi_less;
  54         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpb_less;
  55         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpt_less;
  56 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  57         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_shb_less;
  58         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_sht_less;
  59 #endif
  60         struct BronsonAVLTreeMap_cmp_stat: public
  61             cc::bronson_avltree::make_traits<
  62                 co::compare< compare >
  63                 ,cc::bronson_avltree::relaxed_insert< false >
  64                 ,co::item_counter< cds::atomicity::item_counter >
  65                 ,co::stat< cc::bronson_avltree::stat<>>
  66             >::type
  67         {};
  68         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpi_cmp_stat;
  69         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpb_cmp_stat;
  70         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpt_cmp_stat;
  71 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  72         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_shb_cmp_stat;
  73         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_sht_cmp_stat;
  74 #endif
  75
  76         struct BronsonAVLTreeMap_less_pool_simple: public BronsonAVLTreeMap_less
  77         {
  78             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_simple_pool> sync_monitor;
  79         };
  80         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpi_less_pool_simple;
  81         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpb_less_pool_simple;
  82         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpt_less_pool_simple;
  83 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  84         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_shb_less_pool_simple;
  85         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_sht_less_pool_simple;
  86 #endif
  87         struct BronsonAVLTreeMap_less_pool_simple_stat : public BronsonAVLTreeMap_less
  88         {
  89             typedef cc::bronson_avltree::stat<> stat;
  90             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_simple_pool, cds::opt::none, true > sync_monitor;
  91         };
  92         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_simple_stat;
  93         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_simple_stat;
  94         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat;
  95 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  96         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat;
  97         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_sht_less_pool_simple_stat;
  98 #endif
  99         struct BronsonAVLTreeMap_less_pool_lazy: public BronsonAVLTreeMap_less
 100         {
 101             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_lazy_pool> sync_monitor;
 102             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 103         };
 104         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpi_less_pool_lazy;
 105         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpb_less_pool_lazy;
 106         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy;
 107 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 108         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_shb_less_pool_lazy;
 109         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_sht_less_pool_lazy;
 110 #endif
 111         struct BronsonAVLTreeMap_less_pool_lazy_stat : public BronsonAVLTreeMap_less
 112         {
 113             typedef cc::bronson_avltree::stat<> stat;
 114             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_lazy_pool, cds::opt::none, true > sync_monitor;
 115             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 116         };
 117         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_lazy_stat;
 118         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_lazy_stat;
 119         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat;
 120 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 121         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat;
 122         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_sht_less_pool_lazy_stat;
 123 #endif
 124         struct BronsonAVLTreeMap_less_pool_bounded: public BronsonAVLTreeMap_less
 125         {
 126             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_bounded_pool> sync_monitor;
 127             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 128         };
 129         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpi_less_pool_bounded;
 130         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpb_less_pool_bounded;
 131         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded;
 132 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 133         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_shb_less_pool_bounded;
 134         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_sht_less_pool_bounded;
 135 #endif
 136         struct BronsonAVLTreeMap_less_pool_bounded_stat : public BronsonAVLTreeMap_less
 137         {
 138             typedef cc::bronson_avltree::stat<> stat;
 139             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_bounded_pool, cds::opt::none, true > sync_monitor;
 140             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 141         };
 142         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_bounded_stat;
 143         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_bounded_stat;
 144         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded_stat;
 145 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 146         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_shb_less_pool_bounded_stat;
 147         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_sht_less_pool_bounded_stat;
 148 #endif
 149     };
 150
 151     template <typename GC, typename Key, typename T, typename Traits>
 152     static inline void print_stat( BronsonAVLTreeMap<GC, Key, T, Traits> const& m )
 153     {
 154         CPPUNIT_MSG( m.statistics() );
 155         CPPUNIT_MSG( m.monitor().statistics() );
 156     }
 157
 158     template <typename GC, typename Key, typename T, typename Traits>
 159     static inline void check_before_cleanup( BronsonAVLTreeMap<GC, Key, T, Traits>& m )
 160     {
 161         CPPUNIT_MSG( "  Check internal consistency (single-threaded)..." );
 162         bool bOk = m.check_consistency([]( size_t nLevel, size_t hLeft, size_t hRight )
 163             {
 164                 CPPUNIT_MSG( "Tree violation on level=" << nLevel << ": hLeft=" << hLeft << ", hRight=" << hRight )
 165             });
 166         CPPUNIT_CHECK_CURRENT_EX( bOk, "check_consistency failed");
 167     }
 168
 169 }   // namespace map2
 170
 171 #endif // ifndef CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H