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::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         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_sht_less;
 105 #endif
 106         struct BronsonAVLTreeMap_cmp_stat: public
 107             cc::bronson_avltree::make_traits<
 108                 co::compare< compare >
 109                 ,cc::bronson_avltree::relaxed_insert< false >
 110                 ,co::item_counter< cds::atomicity::item_counter >
 111                 ,co::stat< cc::bronson_avltree::stat<>>
 112             >::type
 113         {};
 114         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpi_cmp_stat;
 115         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpb_cmp_stat;
 116         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpt_cmp_stat;
 117 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 118         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_shb_cmp_stat;
 119         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_sht_cmp_stat;
 120 #endif
 121
 122         struct BronsonAVLTreeMap_less_pool_simple: public BronsonAVLTreeMap_less
 123         {
 124             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_simple_pool> sync_monitor;
 125         };
 126         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpi_less_pool_simple;
 127         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpb_less_pool_simple;
 128         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpt_less_pool_simple;
 129 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 130         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_shb_less_pool_simple;
 131         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_sht_less_pool_simple;
 132 #endif
 133         struct BronsonAVLTreeMap_less_pool_simple_stat : public BronsonAVLTreeMap_less
 134         {
 135             typedef cc::bronson_avltree::stat<> stat;
 136             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_simple_pool, cds::opt::none, true > sync_monitor;
 137         };
 138         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_simple_stat;
 139         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_simple_stat;
 140         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat;
 141 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 142         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat;
 143         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_sht_less_pool_simple_stat;
 144 #endif
 145         struct BronsonAVLTreeMap_less_pool_lazy: public BronsonAVLTreeMap_less
 146         {
 147             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_lazy_pool> sync_monitor;
 148             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 149         };
 150         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpi_less_pool_lazy;
 151         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpb_less_pool_lazy;
 152         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy;
 153 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 154         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_shb_less_pool_lazy;
 155         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_sht_less_pool_lazy;
 156 #endif
 157         struct BronsonAVLTreeMap_less_pool_lazy_stat : public BronsonAVLTreeMap_less
 158         {
 159             typedef cc::bronson_avltree::stat<> stat;
 160             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_lazy_pool, cds::opt::none, true > sync_monitor;
 161             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 162         };
 163         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_lazy_stat;
 164         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_lazy_stat;
 165         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat;
 166 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 167         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat;
 168         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_sht_less_pool_lazy_stat;
 169 #endif
 170         struct BronsonAVLTreeMap_less_pool_bounded: public BronsonAVLTreeMap_less
 171         {
 172             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_bounded_pool> sync_monitor;
 173             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 174         };
 175         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpi_less_pool_bounded;
 176         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpb_less_pool_bounded;
 177         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded;
 178 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 179         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_shb_less_pool_bounded;
 180         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_sht_less_pool_bounded;
 181 #endif
 182         struct BronsonAVLTreeMap_less_pool_bounded_stat : public BronsonAVLTreeMap_less
 183         {
 184             typedef cc::bronson_avltree::stat<> stat;
 185             typedef cds::sync::pool_monitor<BronsonAVLTreeMap_bounded_pool, cds::opt::none, true > sync_monitor;
 186             static CDS_CONSTEXPR bool const relaxed_insert = false; // relaxed insert can lead to test assert triggering
 187         };
 188         typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpi_less_pool_bounded_stat;
 189         typedef BronsonAVLTreeMap< rcu_gpb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpb_less_pool_bounded_stat;
 190         typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded_stat;
 191 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 192         typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_shb_less_pool_bounded_stat;
 193         typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_sht_less_pool_bounded_stat;
 194 #endif
 195     };
 196
 197     template <typename GC, typename Key, typename T, typename Traits>
 198     static inline void print_stat( cds_test::property_stream& o, BronsonAVLTreeMap<GC, Key, T, Traits> const& m )
 199     {
 200         o << m.statistics()
 201           << m.monitor().statistics();
 202     }
 203
 204     template <typename GC, typename Key, typename T, typename Traits>
 205     static inline void check_before_cleanup( BronsonAVLTreeMap<GC, Key, T, Traits>& m )
 206     {
 207         bool check_consistency_result = m.check_consistency([]( size_t nLevel, size_t hLeft, size_t hRight )
 208             {
 209                 EXPECT_TRUE( false ) << "Tree violation on level=" << nLevel << ": hLeft=" << hLeft << ", hRight=" << hRight;
 210             });
 211         EXPECT_TRUE( check_consistency_result ) << "Internal tree structure violation";
 212     }
 213
 214
 215 #define CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, bronson_map_type, key_type, value_type ) \
 216     TEST_F( fixture, bronson_map_type ) \
 217     { \
 218         typedef map::map_type< tag_BronsonAVLTreeMap, key_type, value_type >::bronson_map_type map_type; \
 219         test_case<map_type>(); \
 220     }
 221
 222 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 223 #   define CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
 224         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less,                   key_type, value_type ) \
 225         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less,                   key_type, value_type ) \
 226         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_cmp_stat,               key_type, value_type ) \
 227         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_cmp_stat,               key_type, value_type ) \
 228         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_simple,       key_type, value_type ) \
 229         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_simple,       key_type, value_type ) \
 230         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat,  key_type, value_type ) \
 231         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_simple_stat,  key_type, value_type ) \
 232         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_lazy,         key_type, value_type ) \
 233         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_lazy,         key_type, value_type ) \
 234         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat,    key_type, value_type ) \
 235         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_lazy_stat,    key_type, value_type )
 236
 237 #else
 238 #   define CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
 239 #endif
 240
 241 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
 242 #   define CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type ) \
 243         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_cmp_stat,               key_type, value_type ) \
 244         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple,       key_type, value_type ) \
 245         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple_stat,  key_type, value_type ) \
 246         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy,         key_type, value_type ) \
 247         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy_stat,    key_type, value_type ) \
 248         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple,       key_type, value_type ) \
 249         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_simple_stat,  key_type, value_type ) \
 250         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy,         key_type, value_type ) \
 251         CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat,    key_type, value_type ) \
 252         CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
 253
 254 #else
 255 #   define CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type )
 256 #endif
 257
 258 #define CDSSTRESS_BronsonAVLTreeMap( fixture, test_case, key_type, value_type ) \
 259     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less,                   key_type, value_type ) \
 260     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less,                   key_type, value_type ) \
 261     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less,                   key_type, value_type ) \
 262     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_cmp_stat,               key_type, value_type ) \
 263     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_cmp_stat,               key_type, value_type ) \
 264     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_simple,       key_type, value_type ) \
 265     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat,  key_type, value_type ) \
 266     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_lazy,         key_type, value_type ) \
 267     CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy_stat,    key_type, value_type ) \
 268     CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type ) \
 269
 270 }   // namespace map
 271
 272 #endif // ifndef CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H