/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
-
+
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSUNIT_MAP_TYPE_BRONSON_AVLTREE_H
typedef cc::BronsonAVLTreeMap< GC, Key, T, Traits > base_class;
public:
template <typename Config>
- BronsonAVLTreeMap( Config const& /*cfg*/)
+ BronsonAVLTreeMap( Config const& /*cfg*/ )
: base_class()
{}
+ std::pair<Key, bool> extract_min_key()
+ {
+ Key key;
+ typename base_class::exempt_ptr xp = base_class::extract_min( [&key]( Key const& k ) { key = k; } );
+ if ( xp )
+ return std::make_pair( key, true );
+ return std::make_pair( key, false );
+ }
+
+ std::pair<Key, bool> extract_max_key()
+ {
+ Key key;
+ typename base_class::exempt_ptr xp = base_class::extract_max( [&key]( Key const& k ) { key = k; } );
+ if ( xp )
+ return std::make_pair( key, true );
+ return std::make_pair( key, false );
+ }
+
// for testing
static CDS_CONSTEXPR bool const c_bExtractSupported = true;
static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
cc::bronson_avltree::make_traits<
co::less< less >
,cc::bronson_avltree::relaxed_insert< false >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
>::type
{};
typedef BronsonAVLTreeMap< rcu_gpi, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpi_less;
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_gpt_less;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_shb_less;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less > BronsonAVLTreeMap_rcu_sht_less;
#endif
struct BronsonAVLTreeMap_cmp_stat: public
cc::bronson_avltree::make_traits<
co::compare< compare >
,cc::bronson_avltree::relaxed_insert< false >
- ,co::item_counter< cds::atomicity::item_counter >
+ ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
,co::stat< cc::bronson_avltree::stat<>>
>::type
{};
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_gpt_cmp_stat;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_shb_cmp_stat;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_cmp_stat > BronsonAVLTreeMap_rcu_sht_cmp_stat;
#endif
struct BronsonAVLTreeMap_less_pool_simple: public BronsonAVLTreeMap_less
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_gpt_less_pool_simple;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_shb_less_pool_simple;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_simple > BronsonAVLTreeMap_rcu_sht_less_pool_simple;
#endif
struct BronsonAVLTreeMap_less_pool_simple_stat : public BronsonAVLTreeMap_less
{
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_simple_stat > BronsonAVLTreeMap_rcu_sht_less_pool_simple_stat;
#endif
struct BronsonAVLTreeMap_less_pool_lazy: public BronsonAVLTreeMap_less
{
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_shb_less_pool_lazy;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_lazy > BronsonAVLTreeMap_rcu_sht_less_pool_lazy;
#endif
struct BronsonAVLTreeMap_less_pool_lazy_stat : public BronsonAVLTreeMap_less
{
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_lazy_stat > BronsonAVLTreeMap_rcu_sht_less_pool_lazy_stat;
#endif
struct BronsonAVLTreeMap_less_pool_bounded: public BronsonAVLTreeMap_less
{
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_shb_less_pool_bounded;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_bounded > BronsonAVLTreeMap_rcu_sht_less_pool_bounded;
#endif
struct BronsonAVLTreeMap_less_pool_bounded_stat : public BronsonAVLTreeMap_less
{
typedef BronsonAVLTreeMap< rcu_gpt, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_gpt_less_pool_bounded_stat;
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
typedef BronsonAVLTreeMap< rcu_shb, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_shb_less_pool_bounded_stat;
- typedef BronsonAVLTreeMap< rcu_sht, Key, Value, BronsonAVLTreeMap_less_pool_bounded_stat > BronsonAVLTreeMap_rcu_sht_less_pool_bounded_stat;
#endif
};
{
EXPECT_TRUE( false ) << "Tree violation on level=" << nLevel << ": hLeft=" << hLeft << ", hRight=" << hRight;
});
- EXPECT_TRUE( check_consistency_result );
+ EXPECT_TRUE( check_consistency_result ) << "Internal tree structure violation";
}
#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
# define CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_cmp_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_cmp_stat, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_simple, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_simple, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_simple_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_simple_stat, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_lazy, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_lazy, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_shb_less_pool_lazy_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_sht_less_pool_lazy_stat, key_type, value_type )
#else
# define CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
#endif
+#if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 0
+# define CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type ) \
+ CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple, key_type, value_type ) \
+ CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy, key_type, value_type ) \
+ CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple, key_type, value_type ) \
+ CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy, key_type, value_type ) \
+ CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
+
+#else
+# define CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type )
+#endif
+
#define CDSSTRESS_BronsonAVLTreeMap( fixture, test_case, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_cmp_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_cmp_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_cmp_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_simple, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_simple_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_simple_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_simple_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy, key_type, value_type ) \
CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_lazy, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpi_less_pool_lazy_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpb_less_pool_lazy_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_case( fixture, test_case, BronsonAVLTreeMap_rcu_gpt_less_pool_lazy_stat, key_type, value_type ) \
- CDSSTRESS_BronsonAVLTreeMap_SHRCU( fixture, test_case, key_type, value_type )
+ CDSSTRESS_BronsonAVLTreeMap_1( fixture, test_case, key_type, value_type ) \
} // namespace map