set(PACKAGE_NAME stress-sequential)
add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/sequential-set)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/sequential-map)
set(CDSSTRESS_STACK_SOURCES
../main.cpp
DEPENDS
stress-sequential
stress-sequential-set
+ stress-sequential-map
)
--- /dev/null
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DCDSUNIT_USE_URCU")
+
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/delodd)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/del3)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/find_string)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_func)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_string)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_item_int)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdelfind)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/minmax)
+#add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/iter_erase)
+
+add_custom_target( stress-sequential-map
+ DEPENDS
+ stress-sequential-map-delodd
+ stress-sequential-map-del3
+ stress-sequential-map-find-string
+ stress-sequential-map-insdel-func
+ stress-sequential-map-insdel-string
+ stress-sequential-map-insdel-item-int
+ stress-sequential-map-insdelfind
+ stress-sequential-map-minmax
+ #stress-sequential-map-iter-erase
+)
--- /dev/null
+set(PACKAGE_NAME stress-sequential-map-del3)
+
+set(CDSSTRESS_MAP_DEL3_SOURCES
+ ../../../main.cpp
+ map_del3.cpp
+ map_del3_bronsonavltree.cpp
+ map_del3_cuckoo.cpp
+ map_del3_ellentree.cpp
+ map_del3_feldman_hashmap.cpp
+ map_del3_michael.cpp
+ map_del3_skip.cpp
+ map_del3_split.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_DEL3_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+
+namespace map {
+
+ size_t Map_Del3::s_nMapSize = 10000;
+ size_t Map_Del3::s_nInsThreadCount = 4;
+ size_t Map_Del3::s_nDelThreadCount = 4;
+ size_t Map_Del3::s_nExtractThreadCount = 4;
+ size_t Map_Del3::s_nFindThreadCount = 2;
+ size_t Map_Del3::s_nMaxLoadFactor = 8;
+ size_t Map_Del3::s_nInsertPassCount = 100;
+ size_t Map_Del3::s_nOriginalPassCount = 100;
+ size_t Map_Del3::s_nPassCount = 100;
+ size_t Map_Del3::s_nFeldmanPassCount = 100;
+ size_t Map_Del3::s_nBronsonAVLTreeMapPassCount = 100;
+ size_t Map_Del3::s_nEllenBinTreeMapPassCount= 100;
+ size_t Map_Del3::s_nMichaelMapPassCount= 100;
+ size_t Map_Del3::s_nSkipListMapPassCount= 100;
+
+ size_t Map_Del3::s_nCuckooInitialSize = 1024;
+ size_t Map_Del3::s_nCuckooProbesetSize = 16;
+ size_t Map_Del3::s_nCuckooProbesetThreshold = 0;
+
+ size_t Map_Del3::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_Del3::s_nFeldmanMap_ArrayBits = 4;
+
+ size_t Map_Del3::s_nLoadFactor = 1;
+ std::vector<size_t> Map_Del3::m_arrElements;
+
+ void Map_Del3::SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "sequential_real_map_delodd" );
+
+ s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nInsThreadCount = cfg.get_size_t( "InsThreadCount", s_nInsThreadCount );
+ if ( s_nInsThreadCount == 0 )
+ s_nInsThreadCount = 1;
+
+ s_nDelThreadCount = cfg.get_size_t( "DelThreadCount", s_nDelThreadCount );
+ s_nExtractThreadCount = cfg.get_size_t( "ExtractThreadCount", s_nExtractThreadCount );
+ s_nFindThreadCount = cfg.get_size_t( "FindThreadCount", s_nFindThreadCount );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ s_nInsertPassCount = cfg.get_size_t( "InsertPassCount", s_nInsertPassCount );
+ if ( s_nInsertPassCount == 0 )
+ s_nInsertPassCount = 100;
+
+ s_nPassCount = cfg.get_size_t("PassCount", s_nPassCount);
+ if (s_nPassCount == 0)
+ s_nPassCount = 100;
+ s_nOriginalPassCount = s_nPassCount;
+
+ s_nFeldmanPassCount =
+ cfg.get_size_t("FeldmanPassCount", s_nFeldmanPassCount);
+ if (s_nFeldmanPassCount == 0)
+ s_nFeldmanPassCount = 500;
+
+ s_nBronsonAVLTreeMapPassCount = cfg.get_size_t(
+ "BronsonAVLTreeMapPassCount", s_nBronsonAVLTreeMapPassCount);
+ if (s_nBronsonAVLTreeMapPassCount == 0)
+ s_nBronsonAVLTreeMapPassCount = 500;
+
+ s_nEllenBinTreeMapPassCount = cfg.get_size_t(
+ "EllenBinTreeMapPassCount", s_nEllenBinTreeMapPassCount);
+ if (s_nEllenBinTreeMapPassCount == 0)
+ s_nEllenBinTreeMapPassCount = 500;
+
+ s_nMichaelMapPassCount =
+ cfg.get_size_t("MichaelMapPassCount", s_nMichaelMapPassCount);
+ if (s_nMichaelMapPassCount == 0)
+ s_nMichaelMapPassCount = 500;
+
+ s_nSkipListMapPassCount =
+ cfg.get_size_t("SkipListMapPassCount", s_nSkipListMapPassCount);
+ if (s_nSkipListMapPassCount == 0)
+ s_nSkipListMapPassCount = 500;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+
+ m_arrElements.resize( s_nMapSize );
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ m_arrElements[i] = i;;
+ shuffle( m_arrElements.begin(), m_arrElements.end());
+ }
+
+ void Map_Del3::TearDownTestCase()
+ {
+ m_arrElements.clear();
+ }
+
+ std::vector<size_t> Map_Del3_LF::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_delodd" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_Del3_LF, ::testing::ValuesIn( Map_Del3_LF::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_Del3_LF, ::testing::ValuesIn( Map_Del3_LF::get_load_factors()));
+#endif
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+#include <cds/os/topology.h>
+
+namespace map {
+
+ namespace {
+ struct key_thread
+ {
+ uint32_t nKey;
+ uint16_t nThread;
+
+ key_thread( size_t key, size_t threadNo )
+ : nKey( static_cast<uint32_t>(key))
+ , nThread( static_cast<uint16_t>(threadNo))
+ {}
+
+ key_thread()
+ : nKey()
+ , nThread()
+ {}
+ };
+
+ static_assert(sizeof( key_thread ) % 8 == 0, "Key size mismatch!!!");
+ } // namespace
+
+ template <>
+ struct cmp<key_thread> {
+ int operator ()(key_thread const& k1, key_thread const& k2) const
+ {
+ if ( k1.nKey < k2.nKey )
+ return -1;
+ if ( k1.nKey > k2.nKey )
+ return 1;
+ if ( k1.nThread < k2.nThread )
+ return -1;
+ if ( k1.nThread > k2.nThread )
+ return 1;
+ return 0;
+ }
+ int operator ()(key_thread const& k1, size_t k2) const
+ {
+ if ( k1.nKey < k2 )
+ return -1;
+ if ( k1.nKey > k2 )
+ return 1;
+ return 0;
+ }
+ int operator ()(size_t k1, key_thread const& k2) const
+ {
+ if ( k1 < k2.nKey )
+ return -1;
+ if ( k1 > k2.nKey )
+ return 1;
+ return 0;
+ }
+ };
+
+ template <>
+ struct less<key_thread>
+ {
+ bool operator()( key_thread const& k1, key_thread const& k2 ) const
+ {
+ if ( k1.nKey <= k2.nKey )
+ return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
+ return false;
+ }
+ };
+
+ template <>
+ struct hash<key_thread>
+ {
+ typedef size_t result_type;
+ typedef key_thread argument_type;
+
+ size_t operator()( key_thread const& k ) const
+ {
+ return std::hash<size_t>()(k.nKey);
+ }
+ size_t operator()( size_t k ) const
+ {
+ return std::hash<size_t>()(k);
+ }
+ };
+
+ class Map_Del3: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nInsThreadCount; // insert thread count
+ static size_t s_nDelThreadCount; // delete thread count
+ static size_t s_nExtractThreadCount; // extract thread count
+ static size_t s_nMapSize; // max map size
+ static size_t s_nMaxLoadFactor; // maximum load factor
+ static size_t s_nInsertPassCount;
+ static size_t s_nOriginalPassCount;
+ static size_t s_nPassCount;
+ static size_t s_nBronsonAVLTreeMapPassCount;
+ static size_t s_nEllenBinTreeMapPassCount;
+ static size_t s_nFeldmanPassCount;
+ static size_t s_nMichaelMapPassCount;
+ static size_t s_nSkipListMapPassCount;
+
+ static size_t s_nFindThreadCount; // find thread count
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ static std::vector<size_t> m_arrElements;
+
+ static void SetUpTestCase();
+ static void TearDownTestCase();
+
+ template <typename Pred>
+ static void prepare_array( std::vector<size_t>& arr, Pred pred )
+ {
+ arr.reserve( m_arrElements.size());
+ for ( auto el : m_arrElements ) {
+ if ( pred( el ))
+ arr.push_back( el );
+ }
+ arr.resize( arr.size());
+ shuffle( arr.begin(), arr.end());
+ }
+
+ protected:
+ typedef key_thread key_type;
+ typedef size_t value_type;
+ typedef std::pair<key_type const, value_type> pair_type;
+
+ atomics::atomic<size_t> m_nInsThreadCount;
+
+ enum {
+ inserter_thread,
+ deleter_thread,
+ extractor_thread,
+ find_thread,
+ };
+
+ // Inserts keys from [0..N)
+ template <class Map>
+ class Inserter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ struct update_func
+ {
+ template <typename Q>
+ void operator()( bool /*bNew*/, Q const& ) const
+ {}
+
+ template <typename Q, typename V>
+ void operator()( bool /*bNew*/, Q const&, V& ) const
+ {}
+
+ // FeldmanHashMap
+ template <typename Q>
+ void operator()( Q&, Q*) const
+ {}
+ };
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t ) -> bool { return true; } );
+ for ( size_t i = 0; i < m_arr.size(); ++i ) {
+ if ( m_Map.insert( key_type( m_arr[i], id())))
+ ++m_nInsertInitSuccess;
+ else
+ ++m_nInsertInitFailed;
+ }
+ }
+
+ public:
+ size_t m_nInsertSuccess = 0;
+ size_t m_nInsertFailed = 0;
+ size_t m_nInsertInitSuccess = 0;
+ size_t m_nInsertInitFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Inserter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, inserter_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Inserter( Inserter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Inserter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+ Map_Del3& fixture = pool().template fixture<Map_Del3>();
+
+ update_func f;
+
+ for (auto el : m_arr) {
+ if (el & 3) {
+ if (rMap.insert(key_type(el, id())))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ m_arr.resize(0);
+ }
+ };
+
+ struct key_equal {
+ bool operator()( key_type const& k1, key_type const& k2 ) const
+ {
+ return k1.nKey == k2.nKey;
+ }
+ bool operator()( size_t k1, key_type const& k2 ) const
+ {
+ return k1 == k2.nKey;
+ }
+ bool operator()( key_type const& k1, size_t k2 ) const
+ {
+ return k1.nKey == k2;
+ }
+ };
+
+ struct key_less {
+ bool operator()( key_type const& k1, key_type const& k2 ) const
+ {
+ return k1.nKey < k2.nKey;
+ }
+ bool operator()( size_t k1, key_type const& k2 ) const
+ {
+ return k1 < k2.nKey;
+ }
+ bool operator()( key_type const& k1, size_t k2 ) const
+ {
+ return k1.nKey < k2;
+ }
+
+ typedef key_equal equal_to;
+ };
+
+ // Deletes odd keys from [0..N)
+ template <class Map>
+ class Deleter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
+ }
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Deleter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, deleter_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Deleter( Deleter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Deleter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ Map_Del3& fixture = pool().template fixture<Map_Del3>();
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ for (auto el : m_arr) {
+ for (size_t k = 0; k < nInsThreadCount; ++k) {
+ if (rMap.erase(key_type(el, k)))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ m_arr.resize( 0 );
+ }
+ };
+
+ // Deletes odd keys from [0..N)
+ template <class GC, class Map >
+ class Extractor: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
+ }
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Extractor( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, extractor_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Extractor( Extractor& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Extractor( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ typename Map::guarded_ptr gp;
+ Map_Del3& fixture = pool().template fixture<Map_Del3>();
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ for (auto el : m_arr) {
+ for (size_t k = 0; k < nInsThreadCount; ++k) {
+ gp = rMap.extract(key_type(el, k));
+ if (gp)
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ gp.release();
+ }
+ }
+ m_arr.resize( 0 );
+ }
+ };
+
+ template <class RCU, class Map >
+ class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
+ }
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Extractor( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, extractor_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Extractor( Extractor& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Extractor( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+ Map_Del3& fixture = pool().template fixture<Map_Del3>();
+
+ typename Map::exempt_ptr xp;
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ for (size_t k = 0; k < nInsThreadCount; ++k) {
+ for (auto el : m_arr) {
+ if (Map::c_bExtractLockExternal) {
+ typename Map::rcu_lock l;
+ xp = rMap.extract(key_type(el, k));
+ if (xp)
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ } else {
+ xp = rMap.extract(key_type(el, k));
+ if (xp)
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ xp.release();
+ }
+ }
+ m_arr.resize(0);
+ }
+ };
+
+ // Finds keys
+ template <class Map>
+ class Observer: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ size_t m_nFindEvenSuccess = 0;
+ size_t m_nFindEvenFailed = 0;
+ size_t m_nFindOddSuccess = 0;
+ size_t m_nFindOddFailed = 0;
+
+ public:
+ Observer( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, find_thread )
+ , m_Map( map )
+ {}
+
+ Observer( Observer& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Observer( *this );
+ }
+
+ virtual void test()
+ {
+ Map& map = m_Map;
+ Map_Del3& fixture = pool().template fixture<Map_Del3>();
+ std::vector<size_t> const& arr = m_arrElements;
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ for (size_t key : arr) {
+ if (key & 3) {
+ for (size_t k = 0; k < nInsThreadCount; ++k) {
+ if (map.contains(key_thread(key, k)))
+ ++m_nFindOddSuccess;
+ else
+ ++m_nFindOddFailed;
+ }
+ } else {
+ // even keys MUST be in the map
+ for (size_t k = 0; k < nInsThreadCount; ++k) {
+ if (map.contains(key_thread(key, k)))
+ ++m_nFindEvenSuccess;
+ else
+ ++m_nFindEvenFailed;
+ }
+ }
+ }
+ }
+ };
+
+ protected:
+ template <class Map>
+ void do_test( Map& testMap )
+ {
+ typedef Inserter<Map> insert_thread;
+ typedef Deleter<Map> delete_thread;
+ typedef Observer<Map> observer_thread;
+
+ m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
+ pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
+ if ( s_nFindThreadCount )
+ pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
+
+ propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+ << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+ << std::make_pair( "find_thread_count", s_nFindThreadCount )
+ << std::make_pair( "map_size", s_nMapSize )
+ << std::make_pair( "pass_count", s_nInsertPassCount );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertInitFailed = 0;
+ size_t nInsertInitSuccess = 0;
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+
+ size_t nFindEvenSuccess = 0;
+ size_t nFindEvenFailed = 0;
+ size_t nFindOddSuccess = 0;
+ size_t nFindOddFailed = 0;
+
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ cds_test::thread& thr = pool.get( i );
+ switch ( thr.type()) {
+ case inserter_thread:
+ {
+ insert_thread& inserter = static_cast<insert_thread&>( thr );
+ nInsertSuccess += inserter.m_nInsertSuccess;
+ nInsertFailed += inserter.m_nInsertFailed;
+ nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+ nInsertInitFailed += inserter.m_nInsertInitFailed;
+ }
+ break;
+ case deleter_thread:
+ {
+ delete_thread& deleter = static_cast<delete_thread&>( thr );
+ nDeleteSuccess += deleter.m_nDeleteSuccess;
+ nDeleteFailed += deleter.m_nDeleteFailed;
+ }
+ break;
+ case find_thread:
+ {
+ observer_thread& observer = static_cast<observer_thread&>( thr );
+ nFindEvenSuccess = observer.m_nFindEvenSuccess;
+ nFindEvenFailed = observer.m_nFindEvenFailed;
+ nFindOddSuccess = observer.m_nFindOddSuccess;
+ nFindOddFailed = observer.m_nFindOddFailed;
+ }
+ break;
+ }
+ }
+
+ size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
+
+ EXPECT_EQ( nInsertInitFailed, 0u );
+ EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
+ EXPECT_EQ( nFindEvenFailed, 0u );
+ EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
+ EXPECT_LE( nInsertSuccess, nDeleteSuccess );
+
+ propout()
+ << std::make_pair( "insert_init_success", nInsertInitSuccess )
+ << std::make_pair( "insert_init_failed", nInsertInitFailed )
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed )
+ << std::make_pair( "find_even_success", nFindEvenSuccess )
+ << std::make_pair( "find_even_failed", nFindEvenFailed )
+ << std::make_pair( "find_odd_success", nFindOddSuccess )
+ << std::make_pair( "find_odd_failed", nFindOddFailed );
+
+ analyze( testMap );
+ }
+
+ template <class Map>
+ void do_test_extract( Map& testMap )
+ {
+ typedef Inserter<Map> insert_thread;
+ typedef Deleter<Map> delete_thread;
+ typedef Extractor< typename Map::gc, Map > extract_thread;
+ typedef Observer<Map> observer_thread;
+
+ cds_test::thread_pool &pool = get_pool();
+ std::unique_ptr<insert_thread> inserter(
+ new insert_thread(pool, testMap));
+ std::unique_ptr<delete_thread> deleter(
+ new delete_thread(pool, testMap));
+ std::unique_ptr<extract_thread> extractor(
+ new extract_thread(pool, testMap));
+ std::unique_ptr<observer_thread> observer(
+ new observer_thread(pool, testMap));
+
+ for (size_t nPass = 0; nPass < s_nPassCount; ++nPass) {
+ testMap.clear();
+ inserter->test();
+ observer->test();
+ deleter->test();
+ observer->test();
+ testMap.clear();
+ inserter->test();
+ extractor->test();
+ observer->test();
+ }
+ }
+
+ template <class Map>
+ void analyze( Map& testMap )
+ {
+ // All even keys must be in the map
+ {
+ for ( size_t n = 0; n < s_nMapSize; n +=4 ) {
+ for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
+ EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
+ }
+ }
+ }
+
+ print_stat( propout(), testMap );
+
+ check_before_cleanup( testMap );
+ testMap.clear();
+ EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
+
+ additional_check( testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test_extract()
+ {
+ static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
+
+ size_t nMapSize = s_nMapSize;
+ s_nMapSize *= s_nInsThreadCount;
+
+ Map testMap( *this );
+
+ s_nMapSize = nMapSize;
+ do_test_extract( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ size_t nMapSize = s_nMapSize;
+ s_nMapSize *= s_nInsThreadCount;
+
+ Map testMap( *this );
+
+ s_nMapSize = nMapSize;
+ do_test( testMap );
+ }
+
+ template <class Map>
+ void run_feldman();
+
+ template <class Map>
+ void run_bronson_avl_tree();
+
+ template <class Map>
+ void run_ellen_bin_tree();
+
+ template <class Map>
+ void run_skip_list();
+
+ template <class Map>
+ void run_michael();
+ };
+
+ class Map_Del3_LF: public Map_Del3
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Map>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_Del3::run_test<Map>();
+ }
+
+ template <class Map>
+ void run_test_extract()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_Del3::run_test_extract<Map>();
+ }
+
+ static std::vector<size_t> get_load_factors();
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ template <class Map>
+ void Map_Del3::run_bronson_avl_tree()
+ {
+ Map_Del3::s_nPassCount = Map_Del3::s_nBronsonAVLTreeMapPassCount;
+ run_test_extract<Map>();
+ }
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_Del3, run_bronson_avl_tree, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_Del3, run_test, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ template <class Map>
+ void Map_Del3::run_ellen_bin_tree()
+ {
+ Map_Del3::s_nPassCount = Map_Del3::s_nEllenBinTreeMapPassCount;
+ run_test_extract<Map>();
+ }
+
+ CDSSTRESS_EllenBinTreeMap( Map_Del3, run_ellen_bin_tree, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ template <class Map>
+ void Map_Del3::run_feldman()
+ {
+ typedef typename Map::traits original_traits;
+ struct traits: public original_traits {
+ enum { hash_size = sizeof( uint32_t ) + sizeof( uint16_t ) };
+ };
+ typedef typename Map::template rebind_traits< traits >::result map_type;
+
+ Map_Del3::s_nPassCount = Map_Del3::s_nFeldmanPassCount;
+ run_test_extract<map_type>();
+ }
+
+ CDSSTRESS_FeldmanHashMap_fixed( Map_Del3, run_feldman, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ template <class Map>
+ void Map_Del3::run_michael()
+ {
+ Map_Del3::s_nPassCount = Map_Del3::s_nMichaelMapPassCount;
+ run_test_extract<Map>();
+ }
+
+ CDSSTRESS_MichaelMap( Map_Del3_LF, run_michael, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+ template <class Map>
+ void Map_Del3::run_skip_list()
+ {
+ Map_Del3::s_nPassCount = Map_Del3::s_nSkipListMapPassCount;
+ run_test_extract<Map>();
+ }
+
+ CDSSTRESS_SkipListMap( Map_Del3, run_skip_list, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_del3.h"
+#include "map_type_split_list.h"
+
+namespace map {
+
+ CDSSTRESS_SplitListMap( Map_Del3_LF, run_test_extract, key_thread, size_t )
+ CDSSTRESS_SplitListIterableMap( Map_Del3_LF, run_test_extract, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+set(PACKAGE_NAME stress-sequential-map-delodd)
+
+set(CDSSTRESS_MAP_DELODD_SOURCES
+ ../../../main.cpp
+ map_delodd.cpp
+ map_delodd_bronsonavltree.cpp
+ map_delodd_cuckoo.cpp
+ map_delodd_ellentree.cpp
+ map_delodd_feldman_hashmap.cpp
+ map_delodd_michael.cpp
+ map_delodd_skip.cpp
+ map_delodd_split.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_DELODD_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+
+namespace map {
+
+ size_t Map_DelOdd::s_nMapSize = 10000;
+ size_t Map_DelOdd::s_nInsThreadCount = 4;
+ size_t Map_DelOdd::s_nDelThreadCount = 4;
+ size_t Map_DelOdd::s_nExtractThreadCount = 4;
+ size_t Map_DelOdd::s_nFindThreadCount = 2;
+ size_t Map_DelOdd::s_nMaxLoadFactor = 8;
+ size_t Map_DelOdd::s_nInsertPassCount = 100;
+
+ size_t Map_DelOdd::s_nCuckooInitialSize = 1024;
+ size_t Map_DelOdd::s_nCuckooProbesetSize = 16;
+ size_t Map_DelOdd::s_nCuckooProbesetThreshold = 0;
+
+ size_t Map_DelOdd::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_DelOdd::s_nFeldmanMap_ArrayBits = 4;
+
+ size_t Map_DelOdd::s_nLoadFactor = 1;
+ std::vector<size_t> Map_DelOdd::m_arrElements;
+
+ void Map_DelOdd::SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "map_delodd" );
+
+ s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nInsThreadCount = cfg.get_size_t( "InsThreadCount", s_nInsThreadCount );
+ if ( s_nInsThreadCount == 0 )
+ s_nInsThreadCount = 1;
+
+ s_nDelThreadCount = cfg.get_size_t( "DelThreadCount", s_nDelThreadCount );
+ s_nExtractThreadCount = cfg.get_size_t( "ExtractThreadCount", s_nExtractThreadCount );
+ s_nFindThreadCount = cfg.get_size_t( "FindThreadCount", s_nFindThreadCount );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ s_nInsertPassCount = cfg.get_size_t( "PassCount", s_nInsertPassCount );
+ if ( s_nInsertPassCount == 0 )
+ s_nInsertPassCount = 100;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+
+ m_arrElements.resize( s_nMapSize );
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ m_arrElements[i] = i;;
+ shuffle( m_arrElements.begin(), m_arrElements.end());
+ }
+
+ void Map_DelOdd::TearDownTestCase()
+ {
+ m_arrElements.clear();
+ }
+
+ std::vector<size_t> Map_DelOdd_LF::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_delodd" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_DelOdd_LF, ::testing::ValuesIn( Map_DelOdd_LF::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_DelOdd_LF, ::testing::ValuesIn( Map_DelOdd_LF::get_load_factors()));
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+#include <cds/os/topology.h>
+
+namespace map {
+
+ namespace {
+ struct key_thread
+ {
+ uint32_t nKey;
+ uint16_t nThread;
+
+ key_thread( size_t key, size_t threadNo )
+ : nKey( static_cast<uint32_t>(key))
+ , nThread( static_cast<uint16_t>(threadNo))
+ {}
+
+ key_thread()
+ : nKey()
+ , nThread()
+ {}
+ };
+
+ static_assert(sizeof( key_thread ) % 8 == 0, "Key size mismatch!!!");
+ } // namespace
+
+ template <>
+ struct cmp<key_thread> {
+ int operator ()(key_thread const& k1, key_thread const& k2) const
+ {
+ if ( k1.nKey < k2.nKey )
+ return -1;
+ if ( k1.nKey > k2.nKey )
+ return 1;
+ if ( k1.nThread < k2.nThread )
+ return -1;
+ if ( k1.nThread > k2.nThread )
+ return 1;
+ return 0;
+ }
+ int operator ()(key_thread const& k1, size_t k2) const
+ {
+ if ( k1.nKey < k2 )
+ return -1;
+ if ( k1.nKey > k2 )
+ return 1;
+ return 0;
+ }
+ int operator ()(size_t k1, key_thread const& k2) const
+ {
+ if ( k1 < k2.nKey )
+ return -1;
+ if ( k1 > k2.nKey )
+ return 1;
+ return 0;
+ }
+ };
+
+ template <>
+ struct less<key_thread>
+ {
+ bool operator()( key_thread const& k1, key_thread const& k2 ) const
+ {
+ if ( k1.nKey <= k2.nKey )
+ return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
+ return false;
+ }
+ };
+
+ template <>
+ struct hash<key_thread>
+ {
+ typedef size_t result_type;
+ typedef key_thread argument_type;
+
+ size_t operator()( key_thread const& k ) const
+ {
+ return std::hash<size_t>()(k.nKey);
+ }
+ size_t operator()( size_t k ) const
+ {
+ return std::hash<size_t>()(k);
+ }
+ };
+
+ class Map_DelOdd: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nInsThreadCount; // insert thread count
+ static size_t s_nDelThreadCount; // delete thread count
+ static size_t s_nExtractThreadCount; // extract thread count
+ static size_t s_nMapSize; // max map size
+ static size_t s_nMaxLoadFactor; // maximum load factor
+ static size_t s_nInsertPassCount;
+ static size_t s_nFindThreadCount; // find thread count
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ static std::vector<size_t> m_arrElements;
+
+ static void SetUpTestCase();
+ static void TearDownTestCase();
+
+ template <typename Pred>
+ static void prepare_array( std::vector<size_t>& arr, Pred pred )
+ {
+ arr.reserve( m_arrElements.size());
+ for ( auto el : m_arrElements ) {
+ if ( pred( el ))
+ arr.push_back( el );
+ }
+ arr.resize( arr.size());
+ shuffle( arr.begin(), arr.end());
+ }
+
+ protected:
+ typedef key_thread key_type;
+ typedef size_t value_type;
+ typedef std::pair<key_type const, value_type> pair_type;
+
+ atomics::atomic<size_t> m_nInsThreadCount;
+
+ enum {
+ inserter_thread,
+ deleter_thread,
+ extractor_thread,
+ find_thread,
+ };
+
+ // Inserts keys from [0..N)
+ template <class Map>
+ class Inserter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ struct update_func
+ {
+ template <typename Q>
+ void operator()( bool /*bNew*/, Q const& ) const
+ {}
+
+ template <typename Q, typename V>
+ void operator()( bool /*bNew*/, Q const&, V& ) const
+ {}
+
+ // FeldmanHashMap
+ template <typename Q>
+ void operator()( Q&, Q*) const
+ {}
+ };
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t ) -> bool { return true; } );
+ for ( size_t i = 0; i < m_arr.size(); ++i ) {
+ if ( m_Map.insert( key_type( m_arr[i], id())))
+ ++m_nInsertInitSuccess;
+ else
+ ++m_nInsertInitFailed;
+ }
+ }
+
+ public:
+ size_t m_nInsertSuccess = 0;
+ size_t m_nInsertFailed = 0;
+ size_t m_nInsertInitSuccess = 0;
+ size_t m_nInsertInitFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Inserter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, inserter_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Inserter( Inserter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Inserter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+ Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
+
+ update_func f;
+
+ for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
+ if ( nPass & 1 ) {
+ // insert pass
+ for ( auto el : m_arr ) {
+ if ( el & 1 ) {
+ if ( rMap.insert( key_type( el, id())))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+ else {
+ // update pass
+ for ( auto el : m_arr ) {
+ if ( el & 1 ) {
+ bool success;
+ bool inserted;
+ std::tie( success, inserted ) = rMap.update( key_type( el, id()), f );
+ if ( success && inserted )
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+ }
+
+ fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
+ m_arr.resize( 0 );
+ }
+ };
+
+ struct key_equal {
+ bool operator()( key_type const& k1, key_type const& k2 ) const
+ {
+ return k1.nKey == k2.nKey;
+ }
+ bool operator()( size_t k1, key_type const& k2 ) const
+ {
+ return k1 == k2.nKey;
+ }
+ bool operator()( key_type const& k1, size_t k2 ) const
+ {
+ return k1.nKey == k2;
+ }
+ };
+
+ struct key_less {
+ bool operator()( key_type const& k1, key_type const& k2 ) const
+ {
+ return k1.nKey < k2.nKey;
+ }
+ bool operator()( size_t k1, key_type const& k2 ) const
+ {
+ return k1 < k2.nKey;
+ }
+ bool operator()( key_type const& k1, size_t k2 ) const
+ {
+ return k1.nKey < k2;
+ }
+
+ typedef key_equal equal_to;
+ };
+
+ // Deletes odd keys from [0..N)
+ template <class Map>
+ class Deleter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
+ }
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Deleter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, deleter_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Deleter( Deleter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Deleter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ do {
+ if ( id() & 1 ) {
+ for ( auto el: m_arr ) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ if ( rMap.erase( key_type( el, k )))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ }
+ else {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ for ( auto el: m_arr ) {
+ if ( rMap.erase( key_type( el, k )))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ }
+ } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+ m_arr.resize( 0 );
+ }
+ };
+
+ // Deletes odd keys from [0..N)
+ template <class GC, class Map >
+ class Extractor: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
+ }
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Extractor( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, extractor_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Extractor( Extractor& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Extractor( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ typename Map::guarded_ptr gp;
+ Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ do {
+ if ( id() & 1 ) {
+ for ( auto el : m_arr ) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ gp = rMap.extract( key_type( el, k ));
+ if ( gp )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ gp.release();
+ }
+ }
+ }
+ else {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ for ( auto el: m_arr ) {
+ gp = rMap.extract( key_type( el, k ));
+ if ( gp )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ gp.release();
+ }
+ }
+ }
+ } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+ m_arr.resize( 0 );
+ }
+ };
+
+ template <class RCU, class Map >
+ class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ void init_data()
+ {
+ prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
+ }
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ std::vector<size_t> m_arr;
+
+ public:
+ Extractor( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, extractor_thread )
+ , m_Map( map )
+ {
+ init_data();
+ }
+
+ Extractor( Extractor& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {
+ init_data();
+ }
+
+ virtual thread * clone()
+ {
+ return new Extractor( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+ Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
+
+ typename Map::exempt_ptr xp;
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ do {
+ if ( id() & 1 ) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ for ( auto el: m_arr ) {
+ if ( Map::c_bExtractLockExternal ) {
+ typename Map::rcu_lock l;
+ xp = rMap.extract( key_type( el, k ));
+ if ( xp )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ else {
+ xp = rMap.extract( key_type( el, k ));
+ if ( xp )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ xp.release();
+ }
+ }
+ }
+ else {
+ for ( auto el : m_arr ) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ if ( Map::c_bExtractLockExternal ) {
+ typename Map::rcu_lock l;
+ xp = rMap.extract( key_type( el, k ));
+ if ( xp )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ else {
+ xp = rMap.extract( key_type( el, k ));
+ if ( xp )
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ xp.release();
+ }
+ }
+ }
+ } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+ m_arr.resize( 0 );
+ }
+ };
+
+ // Finds keys
+ template <class Map>
+ class Observer: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ size_t m_nFindEvenSuccess = 0;
+ size_t m_nFindEvenFailed = 0;
+ size_t m_nFindOddSuccess = 0;
+ size_t m_nFindOddFailed = 0;
+
+ public:
+ Observer( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, find_thread )
+ , m_Map( map )
+ {}
+
+ Observer( Observer& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Observer( *this );
+ }
+
+ virtual void test()
+ {
+ Map& map = m_Map;
+ Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
+ std::vector<size_t> const& arr = m_arrElements;
+ size_t const nInsThreadCount = s_nInsThreadCount;
+
+ do {
+ for ( size_t key : arr ) {
+ if ( key & 1 ) {
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ if ( map.contains( key_thread( key, k )))
+ ++m_nFindOddSuccess;
+ else
+ ++m_nFindOddFailed;
+ }
+ }
+ else {
+ // even keys MUST be in the map
+ for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+ if ( map.contains( key_thread( key, k )))
+ ++m_nFindEvenSuccess;
+ else
+ ++m_nFindEvenFailed;
+ }
+ }
+ }
+ } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+ }
+ };
+
+ protected:
+ template <class Map>
+ void do_test( Map& testMap )
+ {
+ typedef Inserter<Map> insert_thread;
+ typedef Deleter<Map> delete_thread;
+ typedef Observer<Map> observer_thread;
+
+ m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
+ pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
+ if ( s_nFindThreadCount )
+ pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
+
+ propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+ << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+ << std::make_pair( "find_thread_count", s_nFindThreadCount )
+ << std::make_pair( "map_size", s_nMapSize )
+ << std::make_pair( "pass_count", s_nInsertPassCount );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertInitFailed = 0;
+ size_t nInsertInitSuccess = 0;
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+
+ size_t nFindEvenSuccess = 0;
+ size_t nFindEvenFailed = 0;
+ size_t nFindOddSuccess = 0;
+ size_t nFindOddFailed = 0;
+
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ cds_test::thread& thr = pool.get( i );
+ switch ( thr.type()) {
+ case inserter_thread:
+ {
+ insert_thread& inserter = static_cast<insert_thread&>( thr );
+ nInsertSuccess += inserter.m_nInsertSuccess;
+ nInsertFailed += inserter.m_nInsertFailed;
+ nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+ nInsertInitFailed += inserter.m_nInsertInitFailed;
+ }
+ break;
+ case deleter_thread:
+ {
+ delete_thread& deleter = static_cast<delete_thread&>( thr );
+ nDeleteSuccess += deleter.m_nDeleteSuccess;
+ nDeleteFailed += deleter.m_nDeleteFailed;
+ }
+ break;
+ case find_thread:
+ {
+ observer_thread& observer = static_cast<observer_thread&>( thr );
+ nFindEvenSuccess = observer.m_nFindEvenSuccess;
+ nFindEvenFailed = observer.m_nFindEvenFailed;
+ nFindOddSuccess = observer.m_nFindOddSuccess;
+ nFindOddFailed = observer.m_nFindOddFailed;
+ }
+ break;
+ }
+ }
+
+ size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
+
+ EXPECT_EQ( nInsertInitFailed, 0u );
+ EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
+ EXPECT_EQ( nFindEvenFailed, 0u );
+ EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
+ EXPECT_LE( nInsertSuccess, nDeleteSuccess );
+
+ propout()
+ << std::make_pair( "insert_init_success", nInsertInitSuccess )
+ << std::make_pair( "insert_init_failed", nInsertInitFailed )
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed )
+ << std::make_pair( "find_even_success", nFindEvenSuccess )
+ << std::make_pair( "find_even_failed", nFindEvenFailed )
+ << std::make_pair( "find_odd_success", nFindOddSuccess )
+ << std::make_pair( "find_odd_failed", nFindOddFailed );
+
+ analyze( testMap );
+ }
+
+ template <class Map>
+ void do_test_extract( Map& testMap )
+ {
+ typedef Inserter<Map> insert_thread;
+ typedef Deleter<Map> delete_thread;
+ typedef Extractor< typename Map::gc, Map > extract_thread;
+ typedef Observer<Map> observer_thread;
+
+ m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
+ if ( s_nDelThreadCount )
+ pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
+ if ( s_nExtractThreadCount )
+ pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
+ if ( s_nFindThreadCount )
+ pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
+
+ propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+ << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+ << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
+ << std::make_pair( "find_thread_count", s_nFindThreadCount )
+ << std::make_pair( "map_size", s_nMapSize )
+ << std::make_pair( "pass_count", s_nInsertPassCount );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertInitFailed = 0;
+ size_t nInsertInitSuccess = 0;
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+ size_t nExtractSuccess = 0;
+ size_t nExtractFailed = 0;
+
+ size_t nFindEvenSuccess = 0;
+ size_t nFindEvenFailed = 0;
+ size_t nFindOddSuccess = 0;
+ size_t nFindOddFailed = 0;
+
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ cds_test::thread& thr = pool.get( i );
+ switch ( thr.type()) {
+ case inserter_thread:
+ {
+ insert_thread& inserter = static_cast<insert_thread&>(thr);
+ nInsertSuccess += inserter.m_nInsertSuccess;
+ nInsertFailed += inserter.m_nInsertFailed;
+ nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+ nInsertInitFailed += inserter.m_nInsertInitFailed;
+ }
+ break;
+ case deleter_thread:
+ {
+ delete_thread& deleter = static_cast<delete_thread&>(thr);
+ nDeleteSuccess += deleter.m_nDeleteSuccess;
+ nDeleteFailed += deleter.m_nDeleteFailed;
+ }
+ break;
+ case extractor_thread:
+ {
+ extract_thread& extractor = static_cast<extract_thread&>(thr);
+ nExtractSuccess += extractor.m_nDeleteSuccess;
+ nExtractFailed += extractor.m_nDeleteFailed;
+ }
+ break;
+ case find_thread:
+ {
+ observer_thread& observer = static_cast<observer_thread&>( thr );
+ nFindEvenSuccess = observer.m_nFindEvenSuccess;
+ nFindEvenFailed = observer.m_nFindEvenFailed;
+ nFindOddSuccess = observer.m_nFindOddSuccess;
+ nFindOddFailed = observer.m_nFindOddFailed;
+ }
+ break;
+ default:
+ assert( false );
+ }
+ }
+
+ size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
+
+ EXPECT_EQ( nInsertInitFailed, 0u );
+ EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
+ EXPECT_EQ( nFindEvenFailed, 0u );
+ EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
+ EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
+
+ propout()
+ << std::make_pair( "insert_init_success", nInsertInitSuccess )
+ << std::make_pair( "insert_init_failed", nInsertInitFailed )
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed )
+ << std::make_pair( "extract_success", nExtractSuccess )
+ << std::make_pair( "extract_failed", nExtractFailed )
+ << std::make_pair( "find_even_success", nFindEvenSuccess )
+ << std::make_pair( "find_even_failed", nFindEvenFailed )
+ << std::make_pair( "find_odd_success", nFindOddSuccess )
+ << std::make_pair( "find_odd_failed", nFindOddFailed );
+
+ analyze( testMap );
+ }
+
+ template <class Map>
+ void analyze( Map& testMap )
+ {
+ // All even keys must be in the map
+ {
+ for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
+ for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
+ EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
+ }
+ }
+ }
+
+ print_stat( propout(), testMap );
+
+ check_before_cleanup( testMap );
+ testMap.clear();
+ EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
+
+ additional_check( testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test_extract()
+ {
+ static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
+
+ size_t nMapSize = s_nMapSize;
+ s_nMapSize *= s_nInsThreadCount;
+
+ Map testMap( *this );
+
+ s_nMapSize = nMapSize;
+ do_test_extract( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ size_t nMapSize = s_nMapSize;
+ s_nMapSize *= s_nInsThreadCount;
+
+ Map testMap( *this );
+
+ s_nMapSize = nMapSize;
+ do_test( testMap );
+ }
+
+ template <class Map>
+ void run_feldman();
+ };
+
+ class Map_DelOdd_LF: public Map_DelOdd
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Map>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_DelOdd::run_test<Map>();
+ }
+
+ template <class Map>
+ void run_test_extract()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_DelOdd::run_test_extract<Map>();
+ }
+
+ static std::vector<size_t> get_load_factors();
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_DelOdd, run_test_extract, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_DelOdd, run_test, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap( Map_DelOdd, run_test_extract, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ template <class Map>
+ void Map_DelOdd::run_feldman()
+ {
+ typedef typename Map::traits original_traits;
+ struct traits: public original_traits {
+ enum { hash_size = sizeof( uint32_t ) + sizeof( uint16_t ) };
+ };
+ typedef typename Map::template rebind_traits< traits >::result map_type;
+
+ run_test_extract<map_type>();
+ }
+
+ CDSSTRESS_FeldmanHashMap_fixed( Map_DelOdd, run_feldman, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ CDSSTRESS_MichaelMap( Map_DelOdd_LF, run_test_extract, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+ CDSSTRESS_SkipListMap( Map_DelOdd, run_test_extract, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_delodd.h"
+#include "map_type_split_list.h"
+
+namespace map {
+
+ CDSSTRESS_SplitListMap( Map_DelOdd_LF, run_test_extract, key_thread, size_t )
+ CDSSTRESS_SplitListIterableMap( Map_DelOdd_LF, run_test_extract, key_thread, size_t )
+
+} // namespace map
--- /dev/null
+set(PACKAGE_NAME stress-sequential-map-find-string)
+
+set(CDSSTRESS_MAP_FIND_STRING_SOURCES
+ ../../../main.cpp
+ map_find_string.cpp
+ map_find_string_bronsonavltree.cpp
+ map_find_string_cuckoo.cpp
+ map_find_string_ellentree.cpp
+ map_find_string_feldman_hashset.cpp
+ map_find_string_michael.cpp
+ map_find_string_skip.cpp
+ map_find_string_split.cpp
+ map_find_string_std.cpp
+ map_find_string_striped.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_FIND_STRING_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include <cds_test/hash_func.h>
+
+namespace map {
+
+ size_t Map_find_string::s_nThreadCount = 8;
+ size_t Map_find_string::s_nMapSize = 10000000;
+ size_t Map_find_string::s_nMaxLoadFactor = 8;
+ size_t Map_find_string::s_nPercentExists = 50;
+ size_t Map_find_string::s_nPassCount = 2;
+
+ size_t Map_find_string::s_nCuckooInitialSize = 1024;
+ size_t Map_find_string::s_nCuckooProbesetSize = 16;
+ size_t Map_find_string::s_nCuckooProbesetThreshold = 0;
+
+ size_t Map_find_string::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_find_string::s_nFeldmanMap_ArrayBits = 4;
+
+
+ size_t Map_find_string::s_nLoadFactor = 1;
+ Map_find_string::value_vector Map_find_string::s_Data;
+ std::vector<std::string> Map_find_string::s_arrString;
+
+ void Map_find_string::setup_test_case()
+ {
+ cds_test::config const& cfg = get_config( "map_find_string" );
+
+ s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+ if ( s_nThreadCount == 0 )
+ s_nThreadCount = 1;
+
+ s_nPercentExists = cfg.get_size_t( "PercentExists", s_nPercentExists );
+ if ( s_nPercentExists > 100 )
+ s_nPercentExists = 100;
+ else if ( s_nPercentExists < 1 )
+ s_nPercentExists = 1;
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+
+ s_arrString = load_dictionary();
+ }
+
+ void Map_find_string::TearDownTestCase()
+ {
+ s_arrString.clear();
+ s_Data.clear();
+ }
+
+ void Map_find_string::SetUpTestCase()
+ {
+ setup_test_case();
+
+ s_Data.clear();
+
+ size_t nSize = s_arrString.size();
+ if ( nSize > s_nMapSize )
+ nSize = s_nMapSize;
+ s_Data.reserve( nSize );
+
+ size_t nActualSize = 0;
+ for ( size_t i = 0; i < nSize; ++i ) {
+ bool bExists = rand( 100 ) <= s_nPercentExists;
+ if ( bExists )
+ ++nActualSize;
+ s_Data.push_back( { &s_arrString.at( i ), bExists } );
+ }
+ s_nMapSize = nActualSize;
+ }
+
+ template <typename Hash>
+ void Map_find_string::fill_string_array()
+ {
+ typedef Hash hasher;
+ typedef typename hasher::result_type hash_type;
+
+ std::map<hash_type, size_t> mapHash;
+ s_Data.clear();
+
+ size_t nSize = s_arrString.size();
+ if ( nSize > s_nMapSize )
+ nSize = s_nMapSize;
+ s_Data.reserve( nSize );
+
+ size_t nActualSize = 0;
+ size_t nDiffHash = 0;
+ hasher h;
+ for ( size_t i = 0; i < s_arrString.size(); ++i ) {
+ hash_type hash = h( s_arrString.at( i ));
+ if ( mapHash.insert( std::make_pair( hash, i )).second ) {
+ if ( ++nDiffHash >= nSize )
+ break;
+ bool bExists = rand( 100 ) <= s_nPercentExists;
+ if ( bExists )
+ ++nActualSize;
+ s_Data.push_back( { &s_arrString.at( i ), bExists } );
+ }
+ }
+ s_nMapSize = nActualSize;
+
+ }
+
+ void Map_find_string_stdhash::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<std::hash<std::string>>();
+ }
+
+#if CDS_BUILD_BITS == 64
+ void Map_find_string_city32::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<cds_test::city32>();
+ }
+
+ void Map_find_string_city64::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<cds_test::city64>();
+ }
+
+ void Map_find_string_city128::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<cds_test::city128>();
+ }
+
+#endif
+
+ std::vector<size_t> Map_find_string::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_find_string" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()));
+#endif
+
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+
+namespace map {
+
+ class Map_find_string: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nThreadCount; // thread count
+ static size_t s_nMapSize; // map size (count of searching item)
+ static size_t s_nPercentExists; // percent of existing keys in searching sequence
+ static size_t s_nPassCount;
+ static size_t s_nMaxLoadFactor; // maximum load factor
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CUckooMap probeset threshold (o - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ typedef std::string key_type;
+ struct value_type {
+ std::string const* pKey;
+ bool bExists ; // true - key in map, false - key not in map
+ };
+
+ typedef std::vector<value_type> value_vector;
+ static std::vector<std::string> s_arrString;
+ static value_vector s_Data;
+
+ static void SetUpTestCase();
+ static void TearDownTestCase();
+
+ static void setup_test_case();
+ static std::vector<size_t> get_load_factors();
+
+ private:
+ template <typename Iterator, typename Map>
+ static bool check_result( Iterator const& it, Map const& map )
+ {
+ return it != map.end();
+ }
+ template <typename Map>
+ static bool check_result( bool b, Map const& )
+ {
+ return b;
+ }
+
+ template <class Map>
+ class Worker: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ struct Stat {
+ size_t nSuccess = 0;
+ size_t nFailed = 0;
+ };
+
+ Stat m_KeyExists;
+ Stat m_KeyNotExists;
+
+ public:
+ Worker( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool )
+ , m_Map( map )
+ , m_KeyExists()
+ , m_KeyNotExists()
+ {}
+
+ Worker( Worker& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ , m_KeyExists()
+ , m_KeyNotExists()
+ {}
+
+ virtual thread * clone()
+ {
+ return new Worker( *this );
+ }
+ virtual void test()
+ {
+ size_t const nPassCount = s_nPassCount;
+
+ Map& rMap = m_Map;
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ if ( id() & 1 ) {
+ auto itEnd = s_Data.cend();
+ for ( auto it = s_Data.cbegin(); it != itEnd; ++it ) {
+ auto bFound = rMap.contains( *(it->pKey));
+ if ( it->bExists ) {
+ if ( check_result(bFound, rMap))
+ ++m_KeyExists.nSuccess;
+ else
+ ++m_KeyExists.nFailed;
+ }
+ else {
+ if ( check_result(bFound, rMap))
+ ++m_KeyNotExists.nFailed;
+ else
+ ++m_KeyNotExists.nSuccess;
+ }
+ }
+ }
+ else {
+ auto itEnd = s_Data.crend();
+ for ( auto it = s_Data.crbegin(); it != itEnd; ++it ) {
+ auto bFound = rMap.contains( *(it->pKey));
+ if ( it->bExists ) {
+ if ( check_result(bFound, rMap))
+ ++m_KeyExists.nSuccess;
+ else
+ ++m_KeyExists.nFailed;
+ }
+ else {
+ if ( check_result( bFound, rMap ))
+ ++m_KeyNotExists.nFailed;
+ else
+ ++m_KeyNotExists.nSuccess;
+ }
+ }
+ }
+ }
+ }
+ };
+
+ protected:
+ template <typename Hash>
+ static void fill_string_array();
+
+ template <class Map>
+ void test( Map& testMap )
+ {
+ typedef Worker<Map> worker;
+
+ // Fill the map
+ for ( size_t i = 0; i < s_Data.size(); ++i ) {
+ // All keys in arrData are unique, insert() must be successful
+ if ( s_Data[i].bExists ) {
+ EXPECT_TRUE( check_result( testMap.insert( *(s_Data[i].pKey), s_Data[i] ), testMap ));
+ }
+ }
+
+ propout() << std::make_pair( "thread_count", s_nThreadCount )
+ << std::make_pair( "map_size", s_nMapSize )
+ << std::make_pair( "percent_exist", s_nPercentExists )
+ << std::make_pair( "pass_count", s_nPassCount );
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new worker( pool, testMap ), s_nThreadCount );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nExistSuccess = 0;
+ size_t nExistFailed = 0;
+ size_t nMissingSuccess = 0;
+ size_t nMissingFailed = 0;
+
+ // Postcondition: the number of success searching == the number of map item
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ worker& w = static_cast<worker&>(pool.get( i ));
+ nExistSuccess += w.m_KeyExists.nSuccess;
+ nExistFailed += w.m_KeyExists.nFailed;
+ nMissingSuccess += w.m_KeyNotExists.nSuccess;
+ nMissingFailed += w.m_KeyNotExists.nFailed;
+
+ EXPECT_EQ( w.m_KeyExists.nSuccess, s_nMapSize * s_nPassCount ) << "thread " << i;
+ EXPECT_EQ( w.m_KeyExists.nFailed, 0u ) << "thread " << i;
+ EXPECT_EQ( w.m_KeyNotExists.nSuccess, (s_Data.size() - s_nMapSize) * s_nPassCount ) << "thread " << i;
+ EXPECT_EQ( w.m_KeyNotExists.nFailed, 0u ) << "thread " << i;
+ }
+
+ propout()
+ << std::make_pair( "exist_found", nExistSuccess )
+ << std::make_pair( "exist_not_found", nExistFailed ) // must = 0
+ << std::make_pair( "missing_not_found", nMissingSuccess )
+ << std::make_pair( "missing_found", nMissingFailed ); // must = 0
+
+ check_before_cleanup( testMap );
+
+ testMap.clear();
+ additional_check( testMap );
+ print_stat( propout(), testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ ASSERT_GT( s_Data.size(), 0u );
+
+ Map testMap( *this );
+ test( testMap );
+ }
+ };
+
+ class Map_find_string_stdhash: public Map_find_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_find_string::run_test<Map>();
+ }
+ };
+
+#if CDS_BUILD_BITS == 64
+ class Map_find_string_city32: public Map_find_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_find_string::run_test<Map>();
+ }
+ };
+
+ class Map_find_string_city64: public Map_find_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_find_string::run_test<Map>();
+ }
+ };
+
+ class Map_find_string_city128: public Map_find_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_find_string::run_test<Map>();
+ }
+ };
+
+#endif // #if CDS_BUILD_BITS == 64
+
+ class Map_find_string_LF: public Map_find_string
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Map>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_find_string::run_test<Map>();
+ }
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_find_string, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_find_string, run_test, std::string, Map_find_string::value_type )
+#if CDS_BUILD_BITS == 64
+// CDSSTRESS_CuckooMap_city64( Map_find_string, run_test, std::string, Map_find_string::value_type )
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap( Map_find_string, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ CDSSTRESS_FeldmanHashMap_stdhash( Map_find_string_stdhash, run_test, std::string, Map_find_string::value_type )
+#if CDS_BUILD_BITS == 64
+ CDSSTRESS_FeldmanHashMap_city64( Map_find_string_city64, run_test, std::string, Map_find_string::value_type )
+ CDSSTRESS_FeldmanHashMap_city128( Map_find_string_city128, run_test, std::string, Map_find_string::value_type )
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ CDSSTRESS_MichaelMap( Map_find_string_LF, run_test, std::string, Map_find_string::value_type )
+ CDSSTRESS_MichaelMap_nogc( Map_find_string_LF, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+ CDSSTRESS_SkipListMap( Map_find_string, run_test, std::string, Map_find_string::value_type )
+ CDSSTRESS_SkipListMap_nogc( Map_find_string, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_split_list.h"
+
+namespace map {
+
+ CDSSTRESS_SplitListMap( Map_find_string_LF, run_test, std::string, Map_find_string::value_type )
+ CDSSTRESS_SplitListIterableMap( Map_find_string_LF, run_test, std::string, Map_find_string::value_type )
+ CDSSTRESS_SplitListMap_nogc( Map_find_string_LF, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_std.h"
+
+namespace map {
+
+// CDSSTRESS_StdMap( Map_find_string, run_test, std::string, Map_find_string::value_type )
+// CDSSTRESS_StdMap_nolock( Map_find_string, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_find_string.h"
+#include "map_type_striped.h"
+
+namespace map {
+
+// CDSSTRESS_StripedMap( Map_find_string_LF, run_test, std::string, Map_find_string::value_type )
+
+} // namespace map
--- /dev/null
+set(PACKAGE_NAME stress-sequential-map-insdel-func)
+
+set(CDSSTRESS_MAP_INSDEL_FUNC_SOURCES
+ ../../../main.cpp
+ map_insdel_func.cpp
+ map_insdel_func_bronsonavltree.cpp
+ map_insdel_func_cuckoo.cpp
+ map_insdel_func_ellentree.cpp
+ map_insdel_func_feldman_hashset.cpp
+ map_insdel_func_michael.cpp
+ map_insdel_func_skip.cpp
+ map_insdel_func_split.cpp
+ map_insdel_func_striped.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_INSDEL_FUNC_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+
+namespace map {
+
+ size_t Map_InsDel_func::s_nMapSize = 1000000; // map size
+ size_t Map_InsDel_func::s_nInsertThreadCount = 4; // count of insertion thread
+ size_t Map_InsDel_func::s_nDeleteThreadCount = 4; // count of deletion thread
+ size_t Map_InsDel_func::s_nUpdateThreadCount = 4; // count of ensure thread
+ size_t Map_InsDel_func::s_nThreadPassCount = 4; // pass count for each thread
+ size_t Map_InsDel_func::s_nMaxLoadFactor = 8; // maximum load factor
+
+ size_t Map_InsDel_func::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+ size_t Map_InsDel_func::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+ size_t Map_InsDel_func::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+ size_t Map_InsDel_func::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_InsDel_func::s_nFeldmanMap_ArrayBits = 4;
+
+ size_t Map_InsDel_func::s_nLoadFactor = 1;
+ Map_InsDel_func::key_array Map_InsDel_func::s_arrKeys;
+
+ void Map_InsDel_func::SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "map_insdel_func" );
+
+ s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
+ if ( s_nInsertThreadCount == 0 )
+ s_nInsertThreadCount = 2;
+
+ s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
+ if ( s_nDeleteThreadCount == 0 )
+ s_nDeleteThreadCount = 2;
+
+ s_nUpdateThreadCount = cfg.get_size_t( "UpdateThreadCount", s_nUpdateThreadCount );
+ //if ( s_nUpdateThreadCount == 0 )
+ // s_nUpdateThreadCount = 2;
+
+ s_nThreadPassCount = cfg.get_size_t( "ThreadPassCount", s_nThreadPassCount );
+ if ( s_nThreadPassCount == 0 )
+ s_nThreadPassCount = 4;
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+
+ s_arrKeys.clear();
+ s_arrKeys.reserve( s_nMapSize );
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ s_arrKeys.push_back( i );
+ shuffle( s_arrKeys.begin(), s_arrKeys.end());
+ }
+
+ void Map_InsDel_func::TearDownTestCase()
+ {
+ s_arrKeys.clear();
+ }
+
+ std::vector<size_t> Map_InsDel_func_LF::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_insdel_func" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDel_func_LF, ::testing::ValuesIn( Map_InsDel_func_LF::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDel_func_LF, ::testing::ValuesIn( Map_InsDel_func_LF::get_load_factors()));
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+
+namespace map {
+
+ class Map_InsDel_func: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nMapSize; // map size
+ static size_t s_nInsertThreadCount; // count of insertion thread
+ static size_t s_nDeleteThreadCount; // count of deletion thread
+ static size_t s_nUpdateThreadCount; // count of updating thread
+ static size_t s_nThreadPassCount; // pass count for each thread
+ static size_t s_nMaxLoadFactor; // maximum load factor
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (o - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ static void SetUpTestCase();
+ static void TearDownTestCase();
+
+ typedef size_t key_type;
+ struct value_type {
+ size_t nKey;
+ size_t nData;
+ size_t nUpdateCall;
+ atomics::atomic<bool> bInitialized;
+ cds::OS::ThreadId threadId; // inserter thread id
+
+ typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
+ mutable lock_type m_access;
+
+ value_type()
+ : nKey(0)
+ , nData(0)
+ , nUpdateCall(0)
+ , bInitialized( false )
+ , threadId( cds::OS::get_current_thread_id())
+ {}
+
+ value_type( value_type const& s )
+ : nKey(s.nKey)
+ , nData(s.nData)
+ , nUpdateCall( s.nUpdateCall )
+ , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed))
+ , threadId( cds::OS::get_current_thread_id())
+ , m_access()
+ {}
+
+ // boost::container::flat_map requires operator =
+ // cppcheck-suppress operatorEqVarError
+ value_type& operator=( value_type const& v )
+ {
+ nKey = v.nKey;
+ nData = v.nData;
+ nUpdateCall = v.nUpdateCall;
+ threadId = v.threadId;
+ bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed);
+
+ return *this;
+ }
+ };
+
+ typedef std::vector<key_type> key_array;
+ static key_array s_arrKeys;
+
+ protected:
+ enum {
+ insert_thread,
+ delete_thread,
+ update_thread
+ };
+
+ template <class Map>
+ class Inserter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ struct insert_functor {
+ size_t nTestFunctorRef;
+
+ insert_functor()
+ : nTestFunctorRef(0)
+ {}
+
+ template <typename Pair>
+ void operator()( Pair& val )
+ {
+ operator()( val.first, val.second );
+ }
+
+ template <typename Key, typename Val >
+ void operator()( Key const& key, Val& v )
+ {
+ std::unique_lock< typename value_type::lock_type> ac( v.m_access );
+
+ v.nKey = key;
+ v.nData = key * 8;
+
+ ++nTestFunctorRef;
+ v.bInitialized.store( true, atomics::memory_order_relaxed);
+ }
+ };
+
+ public:
+ size_t m_nInsertSuccess = 0;
+ size_t m_nInsertFailed = 0;
+
+ size_t m_nTestFunctorRef = 0;
+
+ public:
+ Inserter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, insert_thread )
+ , m_Map( map )
+ {}
+
+ Inserter( Inserter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Inserter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ // func is passed by reference
+ insert_functor func;
+ size_t const nPassCount = s_nThreadPassCount;
+
+ if ( id() & 1 ) {
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ for ( key_array::const_iterator it = s_arrKeys.begin(), itEnd = s_arrKeys.end(); it != itEnd; ++it ) {
+ if ( rMap.insert_with( *it, std::ref(func)))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+ else {
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ for ( key_array::const_reverse_iterator it = s_arrKeys.rbegin(), itEnd = s_arrKeys.rend(); it != itEnd; ++it ) {
+ if ( rMap.insert_with( *it, std::ref(func)))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+
+ m_nTestFunctorRef = func.nTestFunctorRef;
+ }
+ };
+
+ template <class Map>
+ class Updater: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ struct update_functor {
+ size_t nCreated = 0;
+ size_t nModified = 0;
+
+ update_functor() = default;
+
+ template <typename Key, typename Val>
+ void operator()( bool /*bNew*/, Key const& key, Val& v )
+ {
+ std::unique_lock<typename value_type::lock_type> ac( v.m_access );
+ if ( !v.bInitialized.load( atomics::memory_order_acquire )) {
+ ++nCreated;
+ v.nKey = key;
+ v.nData = key * 8;
+ v.bInitialized.store( true, atomics::memory_order_relaxed);
+ }
+ else {
+ ++v.nUpdateCall;
+ ++nModified;
+ }
+ }
+
+ template <typename Pair>
+ void operator()( bool bNew, Pair& val )
+ {
+ operator()( bNew, val.first, val.second );
+ }
+
+ // For FeldmanHashMap, IterableList
+ template <typename Val>
+ void operator()( Val& cur, Val * old )
+ {
+ if ( old ) {
+ // If a key exists, FeldmanHashMap creates a new node too
+ // We should manually copy important values from old to cur
+ std::unique_lock<typename value_type::lock_type> ac( cur.second.m_access );
+ cur.second.nKey = cur.first;
+ cur.second.nData = cur.first * 8;
+ cur.second.bInitialized.store( true, atomics::memory_order_release );
+ }
+ operator()( old == nullptr, cur.first, cur.second );
+ }
+
+ private:
+ update_functor(const update_functor& ) = delete;
+ };
+
+ public:
+ size_t m_nUpdateFailed = 0;
+ size_t m_nUpdateCreated = 0;
+ size_t m_nUpdateExisted = 0;
+ size_t m_nFunctorCreated = 0;
+ size_t m_nFunctorModified = 0;
+
+ public:
+ Updater( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, update_thread )
+ , m_Map( map )
+ {}
+
+ Updater( Updater& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Updater( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ update_functor func;
+ size_t const nPassCount = s_nThreadPassCount;
+
+ if ( id() & 1 ) {
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ for ( key_array::const_iterator it = s_arrKeys.begin(), itEnd = s_arrKeys.end(); it != itEnd; ++it ) {
+ std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
+ if ( ret.first ) {
+ if ( ret.second )
+ ++m_nUpdateCreated;
+ else
+ ++m_nUpdateExisted;
+ }
+ else
+ ++m_nUpdateFailed;
+ }
+ }
+ }
+ else {
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ for ( key_array::const_reverse_iterator it = s_arrKeys.rbegin(), itEnd = s_arrKeys.rend(); it != itEnd; ++it ) {
+ std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
+ if ( ret.first ) {
+ if ( ret.second )
+ ++m_nUpdateCreated;
+ else
+ ++m_nUpdateExisted;
+ }
+ else
+ ++m_nUpdateFailed;
+ }
+ }
+ }
+
+ m_nFunctorCreated = func.nCreated;
+ m_nFunctorModified = func.nModified;
+ }
+ };
+
+ template <class Map>
+ class Deleter: public cds_test::thread
+ {
+ Map& m_Map;
+ typedef cds_test::thread base_class;
+ typedef typename Map::mapped_type value_type;
+
+ struct value_container
+ {
+ size_t nKeyExpected;
+
+ size_t nSuccessItem;
+ size_t nFailedItem;
+
+ value_container()
+ : nKeyExpected()
+ , nSuccessItem(0)
+ , nFailedItem(0)
+ {}
+ };
+
+ struct erase_functor {
+ value_container m_cnt;
+
+ template <typename Key, typename Val>
+ void operator()( Key const& /*key*/, Val& v )
+ {
+ while ( true ) {
+ if ( v.bInitialized.load( atomics::memory_order_relaxed )) {
+ std::unique_lock< typename value_type::lock_type> ac( v.m_access );
+
+ if ( m_cnt.nKeyExpected == v.nKey && m_cnt.nKeyExpected * 8 == v.nData )
+ ++m_cnt.nSuccessItem;
+ else
+ ++m_cnt.nFailedItem;
+ v.nData++;
+ v.nKey = 0;
+ break;
+ }
+ else
+ cds::backoff::yield()();
+ }
+ }
+
+ template <typename Pair>
+ void operator ()( Pair& item )
+ {
+ operator()( item.first, item.second );
+ }
+ };
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+ size_t m_nValueSuccess = 0;
+ size_t m_nValueFailed = 0;
+
+ public:
+ Deleter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, delete_thread )
+ , m_Map( map )
+ {}
+
+ Deleter( Deleter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Deleter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ erase_functor func;
+ size_t const nPassCount = s_nThreadPassCount;
+
+ if ( id() & 1 ) {
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ for ( key_array::const_iterator it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
+ func.m_cnt.nKeyExpected = *it;
+ if ( rMap.erase( *it, std::ref(func)))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ }
+ else {
+ for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+ for ( key_array::const_reverse_iterator it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
+ func.m_cnt.nKeyExpected = *it;
+ if ( rMap.erase( *it, std::ref(func)))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ }
+
+ m_nValueSuccess = func.m_cnt.nSuccessItem;
+ m_nValueFailed = func.m_cnt.nFailedItem;
+ }
+ };
+
+ protected:
+
+ template <class Map>
+ void do_test( Map& testMap )
+ {
+ typedef Inserter<Map> inserter;
+ typedef Deleter<Map> deleter;
+ typedef Updater<Map> updater;
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new inserter( pool, testMap ), s_nInsertThreadCount );
+ pool.add( new deleter( pool, testMap ), s_nDeleteThreadCount );
+ if ( s_nUpdateThreadCount )
+ pool.add( new updater( pool, testMap ), s_nUpdateThreadCount );
+
+ propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
+ << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
+ << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
+ << std::make_pair( "pass_count", s_nThreadPassCount )
+ << std::make_pair( "map_size", s_nMapSize );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+ size_t nDelValueSuccess = 0;
+ size_t nDelValueFailed = 0;
+ size_t nUpdateFailed = 0;
+ size_t nUpdateCreated = 0;
+ size_t nUpdateModified = 0;
+ size_t nEnsFuncCreated = 0;
+ size_t nEnsFuncModified = 0;
+ size_t nInsFuncCalled = 0;
+
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ cds_test::thread& thr = pool.get( i );
+ switch ( thr.type()) {
+ case insert_thread:
+ {
+ inserter& t = static_cast<inserter&>( thr );
+ nInsertSuccess += t.m_nInsertSuccess;
+ nInsertFailed += t.m_nInsertFailed;
+ nInsFuncCalled += t.m_nTestFunctorRef;
+ }
+ break;
+ case delete_thread:
+ {
+ deleter& t = static_cast<deleter&>(thr);
+ nDeleteSuccess += t.m_nDeleteSuccess;
+ nDeleteFailed += t.m_nDeleteFailed;
+ nDelValueSuccess += t.m_nValueSuccess;
+ nDelValueFailed += t.m_nValueFailed;
+ }
+ break;
+ case update_thread:
+ {
+ updater& t = static_cast<updater&>(thr);
+ nUpdateCreated += t.m_nUpdateCreated;
+ nUpdateModified += t.m_nUpdateExisted;
+ nUpdateFailed += t.m_nUpdateFailed;
+ nEnsFuncCreated += t.m_nFunctorCreated;
+ nEnsFuncModified += t.m_nFunctorModified;
+ }
+ break;
+ default:
+ assert( false );
+ }
+ }
+
+ propout()
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed )
+ << std::make_pair( "update_success", nUpdateCreated + nUpdateModified )
+ << std::make_pair( "update_failed", nUpdateFailed )
+ << std::make_pair( "update_functor_create", nEnsFuncCreated )
+ << std::make_pair( "update_functor_modify", nEnsFuncModified )
+ << std::make_pair( "finish_map_size", testMap.size());
+
+ EXPECT_EQ( nDelValueFailed, 0u );
+ EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
+ EXPECT_EQ( nUpdateFailed, 0u );
+ EXPECT_EQ( nUpdateCreated + nUpdateModified, nEnsFuncCreated + nEnsFuncModified );
+
+ // nInsFuncCalled is call count of insert functor
+ EXPECT_EQ( nInsFuncCalled, nInsertSuccess );
+
+ check_before_cleanup( testMap );
+
+ for ( size_t nItem = 0; nItem < s_nMapSize; ++nItem )
+ testMap.erase( nItem );
+
+ EXPECT_TRUE( testMap.empty());
+ EXPECT_EQ( testMap.size(), 0u );
+
+ additional_check( testMap );
+ print_stat( propout(), testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ Map testMap( *this );
+ do_test( testMap );
+ }
+
+ template <class Map>
+ void run_test2()
+ {
+ Map testMap( *this );
+ do_test( testMap );
+
+ if ( testMap.size() != 0 ) {
+ for ( auto it = testMap.begin(); it != testMap.end(); ++it ) {
+ std::cout << "key=" << it->first << std::endl;
+ }
+ }
+ }
+ };
+
+ class Map_InsDel_func_LF: public Map_InsDel_func
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Set>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_InsDel_func::run_test<Set>();
+ }
+
+ template <class Set>
+ void run_test2()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_InsDel_func::run_test2<Set>();
+ }
+
+ static std::vector<size_t> get_load_factors();
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_InsDel_func, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_InsDel_func, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap( Map_InsDel_func, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ CDSSTRESS_FeldmanHashMap_fixed( Map_InsDel_func, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ CDSSTRESS_MichaelMap( Map_InsDel_func_LF, run_test2, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+ CDSSTRESS_SkipListMap( Map_InsDel_func, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_split_list.h"
+
+namespace map {
+
+ CDSSTRESS_SplitListMap( Map_InsDel_func_LF, run_test, size_t, Map_InsDel_func::value_type )
+ CDSSTRESS_SplitListIterableMap( Map_InsDel_func_LF, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_func.h"
+#include "map_type_striped.h"
+
+namespace map {
+
+// CDSSTRESS_StripedMap( Map_InsDel_func_LF, run_test, size_t, Map_InsDel_func::value_type )
+
+} // namespace map
--- /dev/null
+set(PACKAGE_NAME stress-sequential-map-insdel-item-int)
+
+set(CDSSTRESS_MAP_INSDEL_ITEM_INT_SOURCES
+ ../../../main.cpp
+ map_insdel_item_int.cpp
+ map_insdel_item_int_bronsonavltree.cpp
+ map_insdel_item_int_cuckoo.cpp
+ map_insdel_item_int_ellentree.cpp
+ map_insdel_item_int_feldman_hashset.cpp
+ map_insdel_item_int_michael.cpp
+ map_insdel_item_int_skip.cpp
+ map_insdel_item_int_split.cpp
+ map_insdel_item_int_striped.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_INSDEL_ITEM_INT_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+
+namespace map {
+
+ size_t Map_InsDel_item_int::s_nMapSize = 10000; // map size
+ size_t Map_InsDel_item_int::s_nInsertThreadCount = 4; // count of insertion thread
+ size_t Map_InsDel_item_int::s_nDeleteThreadCount = 4; // count of deletion thread
+ size_t Map_InsDel_item_int::s_nMaxLoadFactor = 8; // maximum load factor
+
+ size_t Map_InsDel_item_int::s_nAttemptCount = 2000; // count of SUCCESS insert/delete for each thread
+ size_t Map_InsDel_item_int::s_nGoalItem = 5000;
+
+ size_t Map_InsDel_item_int::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+ size_t Map_InsDel_item_int::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+ size_t Map_InsDel_item_int::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+ size_t Map_InsDel_item_int::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_InsDel_item_int::s_nFeldmanMap_ArrayBits = 4;
+
+ size_t Map_InsDel_item_int::s_nLoadFactor = 1;
+
+ void Map_InsDel_item_int::SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "map_insdel_item_int" );
+
+ s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
+ if ( s_nInsertThreadCount == 0 )
+ s_nInsertThreadCount = 2;
+
+ s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
+ if ( s_nDeleteThreadCount == 0 )
+ s_nDeleteThreadCount = 2;
+
+ s_nGoalItem = cfg.get_size_t( "GoalItem", s_nGoalItem );
+ if ( s_nGoalItem >= s_nMapSize )
+ s_nGoalItem = s_nMapSize / 2;
+
+ s_nAttemptCount = cfg.get_size_t( "AttemptCount", s_nAttemptCount );
+ if ( s_nAttemptCount == 0 )
+ s_nAttemptCount = 1000;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+ }
+
+ std::vector<size_t> Map_InsDel_item_int_LF::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_insdel_item_int" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDel_item_int_LF, ::testing::ValuesIn( Map_InsDel_item_int_LF::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDel_item_int_LF, ::testing::ValuesIn( Map_InsDel_item_int_LF::get_load_factors()));
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+
+namespace map {
+
+ class Map_InsDel_item_int: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nMapSize; // map size
+ static size_t s_nInsertThreadCount; // count of insertion thread
+ static size_t s_nDeleteThreadCount; // count of deletion thread
+ static size_t s_nMaxLoadFactor; // maximum load factor
+
+ static size_t s_nAttemptCount; // count of SUCCESS insert/delete for each thread
+ static size_t s_nGoalItem;
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (o - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ static void SetUpTestCase();
+ //static void TearDownTestCase();
+
+ typedef size_t key_type;
+ typedef size_t value_type;
+
+ protected:
+ enum {
+ insert_thread,
+ delete_thread
+ };
+
+ template <class Map>
+ class Inserter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ struct update_func
+ {
+ void operator()( bool bNew, std::pair<key_type const, value_type>& item ) const
+ {
+ if ( bNew )
+ item.second = item.first;
+ }
+
+ // for boost::container::flat_map
+ void operator()( bool bNew, std::pair<key_type, value_type>& item ) const
+ {
+ if ( bNew )
+ item.second = item.first;
+ }
+
+ // for BronsonAVLTreeMap
+ void operator()( bool bNew, key_type key, value_type& val ) const
+ {
+ if ( bNew )
+ val = key;
+ }
+
+ // for FeldmanHashMap
+ void operator()( std::pair<key_type const, value_type>& item, std::pair<key_type const, value_type>* pOld ) const
+ {
+ if ( !pOld )
+ item.second = item.first;
+ }
+ };
+
+ public:
+ size_t m_nInsertSuccess = 0;
+ size_t m_nInsertFailed = 0;
+
+ public:
+ Inserter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, insert_thread )
+ , m_Map( map )
+ {}
+
+ Inserter( Inserter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Inserter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ size_t const nGoalItem = s_nGoalItem;
+ size_t const nAttemptCount = s_nAttemptCount;
+
+ for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
+ if ( nAttempt % 2 == 0 ) {
+ if ( rMap.insert( nGoalItem, nGoalItem )) {
+ ++m_nInsertSuccess;
+ ++nAttempt;
+ }
+ else
+ ++m_nInsertFailed;
+ }
+ else {
+ std::pair<bool, bool> updateResult = rMap.update( nGoalItem, update_func(), true );
+ if ( updateResult.second ) {
+ ++m_nInsertSuccess;
+ ++nAttempt;
+ }
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+ };
+
+ template <class Map>
+ class Deleter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ public:
+ Deleter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, delete_thread )
+ , m_Map( map )
+ {}
+
+ Deleter( Deleter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Deleter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ size_t const nGoalItem = s_nGoalItem;
+ size_t const nAttemptCount = s_nAttemptCount;
+ for ( size_t nAttempt = 0; nAttempt < nAttemptCount; ) {
+ if ( rMap.erase( nGoalItem )) {
+ ++m_nDeleteSuccess;
+ ++nAttempt;
+ }
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ };
+
+ protected:
+
+ template <class Map>
+ void do_test( Map& testMap )
+ {
+ typedef Inserter<Map> inserter;
+ typedef Deleter<Map> deleter;
+
+ // Fill the map
+ {
+ std::vector<key_type> v;
+ v.reserve( s_nMapSize );
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ v.push_back( i );
+ shuffle( v.begin(), v.end());
+ for ( auto i: v )
+ EXPECT_TRUE( testMap.insert( i, i ));
+ }
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new inserter( pool, testMap ), s_nInsertThreadCount );
+ pool.add( new deleter( pool, testMap ), s_nDeleteThreadCount );
+
+ propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
+ << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
+ << std::make_pair( "map_size", s_nMapSize )
+ << std::make_pair( "goal_item", s_nGoalItem )
+ << std::make_pair( "attempt_count", s_nAttemptCount );
+
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ cds_test::thread& thr = pool.get( i );
+ switch ( thr.type()) {
+ case insert_thread:
+ {
+ inserter& t = static_cast<inserter&>(thr);
+ EXPECT_EQ( t.m_nInsertSuccess, s_nAttemptCount ) << "thread=" << t.id();
+ nInsertSuccess += t.m_nInsertSuccess;
+ nInsertFailed += t.m_nInsertFailed;
+ }
+ break;
+ case delete_thread:
+ {
+ deleter& t = static_cast<deleter&>(thr);
+ EXPECT_EQ( t.m_nDeleteSuccess, s_nAttemptCount ) << "thread=" << t.id();
+ nDeleteSuccess += t.m_nDeleteSuccess;
+ nDeleteFailed += t.m_nDeleteFailed;
+ }
+ break;
+ default:
+ assert( false );
+ }
+ }
+
+ EXPECT_EQ( nInsertSuccess, nDeleteSuccess );
+ EXPECT_TRUE( testMap.contains( s_nGoalItem ));
+ EXPECT_CONTAINER_SIZE( testMap, s_nMapSize );
+
+ propout()
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed );
+
+ // Check if the map contains all items
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ EXPECT_TRUE( testMap.contains( i )) << "key=" << i;
+
+ check_before_cleanup( testMap );
+
+ testMap.clear();
+ additional_check( testMap );
+ print_stat( propout(), testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ Map testMap( *this );
+ do_test<Map>( testMap );
+ }
+ };
+
+ class Map_InsDel_item_int_LF: public Map_InsDel_item_int
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Set>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_InsDel_item_int::run_test<Set>();
+ }
+
+ static std::vector<size_t> get_load_factors();
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_InsDel_item_int, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_InsDel_item_int, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap( Map_InsDel_item_int, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ CDSSTRESS_FeldmanHashMap_fixed( Map_InsDel_item_int, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ CDSSTRESS_MichaelMap( Map_InsDel_item_int_LF, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+ CDSSTRESS_SkipListMap( Map_InsDel_item_int, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_split_list.h"
+
+namespace map {
+
+ CDSSTRESS_SplitListMap( Map_InsDel_item_int_LF, run_test, size_t, size_t )
+ CDSSTRESS_SplitListIterableMap( Map_InsDel_item_int_LF, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_item_int.h"
+#include "map_type_striped.h"
+
+namespace map {
+
+// CDSSTRESS_StripedMap( Map_InsDel_item_int_LF, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+set(PACKAGE_NAME stress-sequential-map-insdel-string)
+
+set(CDSSTRESS_MAP_INSDEL_STRING_SOURCES
+ ../../../main.cpp
+ map_insdel_string.cpp
+ map_insdel_string_bronsonavltree.cpp
+ map_insdel_string_cuckoo.cpp
+ map_insdel_string_ellentree.cpp
+ map_insdel_string_feldman_hashset.cpp
+ map_insdel_string_michael.cpp
+ map_insdel_string_skip.cpp
+ map_insdel_string_split.cpp
+ map_insdel_string_std.cpp
+ map_insdel_string_striped.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_INSDEL_STRING_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include <cds_test/hash_func.h>
+
+namespace map {
+
+ size_t Map_InsDel_string::s_nMapSize = 1000000; // map size
+ size_t Map_InsDel_string::s_nInsertThreadCount = 4; // count of insertion thread
+ size_t Map_InsDel_string::s_nDeleteThreadCount = 4; // count of deletion thread
+ size_t Map_InsDel_string::s_nThreadPassCount = 4; // pass count for each thread
+ size_t Map_InsDel_string::s_nMaxLoadFactor = 8; // maximum load factor
+
+ size_t Map_InsDel_string::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+ size_t Map_InsDel_string::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+ size_t Map_InsDel_string::s_nCuckooProbesetThreshold = 0; // CuckooSet probeset threshold (0 - use default)
+
+ size_t Map_InsDel_string::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_InsDel_string::s_nFeldmanMap_ArrayBits = 4;
+
+ size_t Map_InsDel_string::s_nLoadFactor = 1;
+ std::vector<std::string> Map_InsDel_string::s_arrKeys;
+
+ void Map_InsDel_string::setup_test_case()
+ {
+ cds_test::config const& cfg = get_config( "map_insdel_string" );
+
+ s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
+ if ( s_nInsertThreadCount == 0 )
+ s_nInsertThreadCount = 2;
+
+ s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
+ if ( s_nDeleteThreadCount == 0 )
+ s_nDeleteThreadCount = 2;
+
+ s_nThreadPassCount = cfg.get_size_t( "ThreadPassCount", s_nThreadPassCount );
+ if ( s_nThreadPassCount == 0 )
+ s_nThreadPassCount = 4;
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+ }
+
+ void Map_InsDel_string::SetUpTestCase()
+ {
+ setup_test_case();
+
+ s_arrKeys.clear();
+ s_arrKeys.reserve( s_nMapSize );
+ std::vector<std::string> dict = load_dictionary();
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ s_arrKeys.push_back( std::move( dict.at(i)));
+ }
+
+ void Map_InsDel_string::TearDownTestCase()
+ {
+ s_arrKeys.clear();
+ }
+
+ std::vector<size_t> Map_InsDel_string::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_insdel_string" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+ template <typename Hash>
+ void Map_InsDel_string::fill_string_array()
+ {
+ typedef Hash hasher;
+ typedef typename hasher::result_type hash_type;
+
+ std::map<hash_type, size_t> mapHash;
+ s_arrKeys.clear();
+ std::vector<std::string> dict = load_dictionary();
+
+ size_t nSize = dict.size();
+ if ( nSize > s_nMapSize )
+ nSize = s_nMapSize;
+ s_arrKeys.reserve( nSize );
+
+ size_t nDiffHash = 0;
+ hasher h;
+ for ( size_t i = 0; i < dict.size(); ++i ) {
+ hash_type hash = h( dict.at( i ));
+ if ( mapHash.insert( std::make_pair( hash, i )).second ) {
+ if ( ++nDiffHash >= nSize )
+ break;
+ s_arrKeys.push_back( std::move( dict.at( i )));
+ }
+ }
+ s_nMapSize = dict.size();
+ }
+
+ void Map_InsDel_string_stdhash::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<std::hash<std::string>>();
+ }
+
+#if CDS_BUILD_BITS == 64
+ void Map_InsDel_string_city32::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<cds_test::city32>();
+ }
+
+ void Map_InsDel_string_city64::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<cds_test::city64>();
+ }
+
+ void Map_InsDel_string_city128::SetUpTestCase()
+ {
+ setup_test_case();
+ fill_string_array<cds_test::city128>();
+ }
+
+#endif
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDel_string_LF, ::testing::ValuesIn( Map_InsDel_string::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDel_string_LF, ::testing::ValuesIn( Map_InsDel_string::get_load_factors()));
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+
+namespace map {
+
+#define TEST_CASE(TAG, X) void X();
+
+ class Map_InsDel_string: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nMapSize; // map size
+ static size_t s_nInsertThreadCount; // count of insertion thread
+ static size_t s_nDeleteThreadCount; // count of deletion thread
+ static size_t s_nThreadPassCount; // pass count for each thread
+ static size_t s_nMaxLoadFactor; // maximum load factor
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (o - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ static void SetUpTestCase();
+ static void TearDownTestCase();
+
+ static void setup_test_case();
+ static std::vector<size_t> get_load_factors();
+
+ typedef std::string key_type;
+ typedef size_t value_type;
+
+ static std::vector<std::string> s_arrKeys;
+
+ protected:
+ enum {
+ insert_thread,
+ delete_thread
+ };
+
+ template <class Map>
+ class Inserter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ size_t m_nInsertSuccess = 0;
+ size_t m_nInsertFailed = 0;
+
+ public:
+ Inserter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, insert_thread )
+ , m_Map( map )
+ {}
+
+ Inserter( Inserter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Inserter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ if ( id() & 1 ) {
+ for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
+ for ( auto it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
+ if ( rMap.insert( *it, 0 ))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+ else {
+ for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
+ for ( auto it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
+ if ( rMap.insert( *it, 1 ))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ }
+ }
+ }
+ };
+
+ template <class Map>
+ class Deleter: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+
+ public:
+ Deleter( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool, delete_thread )
+ , m_Map( map )
+ {}
+
+ Deleter( Deleter& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Deleter( *this );
+ }
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ if ( id() & 1 ) {
+ for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
+ for ( auto it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
+ if ( rMap.erase( *it ))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ }
+ else {
+ for ( size_t nPass = 0; nPass < s_nThreadPassCount; ++nPass ) {
+ for ( auto it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
+ if ( rMap.erase( *it ))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ }
+ }
+ }
+ }
+ };
+
+ protected:
+ template <typename Hash>
+ static void fill_string_array();
+
+ template <class Map>
+ void do_test( Map& testMap )
+ {
+ typedef Inserter<Map> inserter;
+ typedef Deleter<Map> deleter;
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new inserter( pool, testMap ), s_nInsertThreadCount );
+ pool.add( new deleter( pool, testMap ), s_nDeleteThreadCount );
+
+ propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
+ << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
+ << std::make_pair( "pass_count", s_nThreadPassCount )
+ << std::make_pair( "map_size", s_nMapSize );
+
+ std::chrono::milliseconds duration = pool.run();
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ cds_test::thread& thr = pool.get( i );
+ switch ( thr.type()) {
+ case insert_thread:
+ {
+ inserter& t = static_cast<inserter&>(thr);
+ nInsertSuccess += t.m_nInsertSuccess;
+ nInsertFailed += t.m_nInsertFailed;
+ }
+ break;
+ case delete_thread:
+ {
+ deleter& t = static_cast<deleter&>(thr);
+ nDeleteSuccess += t.m_nDeleteSuccess;
+ nDeleteFailed += t.m_nDeleteFailed;
+ }
+ break;
+ default:
+ assert( false );
+ }
+ }
+
+ propout()
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed )
+ << std::make_pair( "finish_map_size", testMap.size());
+
+ check_before_cleanup( testMap );
+
+ //testMap.clear();
+ for ( auto const& str: s_arrKeys )
+ testMap.erase( str );
+ EXPECT_TRUE( testMap.empty());
+ EXPECT_EQ( testMap.size(), 0u );
+
+ additional_check( testMap );
+ print_stat( propout(), testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ Map testMap( *this );
+ do_test( testMap );
+ }
+ };
+
+ class Map_InsDel_string_stdhash: public Map_InsDel_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_InsDel_string::run_test<Map>();
+ }
+ };
+
+#if CDS_BUILD_BITS == 64
+ class Map_InsDel_string_city32: public Map_InsDel_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_InsDel_string::run_test<Map>();
+ }
+ };
+
+ class Map_InsDel_string_city64: public Map_InsDel_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_InsDel_string::run_test<Map>();
+ }
+ };
+
+ class Map_InsDel_string_city128: public Map_InsDel_string
+ {
+ public:
+ static void SetUpTestCase();
+
+ template <class Map>
+ void run_test()
+ {
+ Map_InsDel_string::run_test<Map>();
+ }
+ };
+
+#endif // #if CDS_BUILD_BITS == 64
+
+ class Map_InsDel_string_LF: public Map_InsDel_string
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Map>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_InsDel_string::run_test<Map>();
+ }
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_InsDel_string, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_InsDel_string, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap( Map_InsDel_string, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ CDSSTRESS_FeldmanHashMap_stdhash( Map_InsDel_string_stdhash, run_test, std::string, size_t )
+#if CDS_BUILD_BITS == 64
+ CDSSTRESS_FeldmanHashMap_city64( Map_InsDel_string_city64, run_test, std::string, size_t )
+ CDSSTRESS_FeldmanHashMap_city128( Map_InsDel_string_city128, run_test, std::string, size_t )
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ CDSSTRESS_MichaelMap( Map_InsDel_string_LF, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+ CDSSTRESS_SkipListMap( Map_InsDel_string, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_split_list.h"
+
+namespace map {
+
+ CDSSTRESS_SplitListMap( Map_InsDel_string_LF, run_test, std::string, size_t )
+ CDSSTRESS_SplitListIterableMap( Map_InsDel_string_LF, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_std.h"
+
+namespace map {
+
+// CDSSTRESS_StdMap( Map_InsDel_string, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdel_string.h"
+#include "map_type_striped.h"
+
+namespace map {
+
+// CDSSTRESS_StripedMap( Map_InsDel_string_LF, run_test, std::string, size_t )
+
+} // namespace map
--- /dev/null
+set(MAP_INSDELFIND_HP stress-sequential-map-insdelfind-hp)
+set(MAP_INSDELFIND_RCU stress-sequential-map-insdelfind-rcu)
+
+set(CDSSTRESS_MAP_INSDELFIND_HP_SOURCES
+ ../../../main.cpp
+ map_insdelfind.cpp
+ map_insdelfind_cuckoo.cpp
+ map_insdelfind_ellentree_hp.cpp
+ map_insdelfind_feldman_hashset_hp.cpp
+ map_insdelfind_michael_hp.cpp
+ map_insdelfind_skip_hp.cpp
+ map_insdelfind_split_hp.cpp
+ map_insdelfind_std.cpp
+ map_insdelfind_striped.cpp
+)
+
+set(CDSSTRESS_MAP_INSDELFIND_RCU_SOURCES
+ ../../../main.cpp
+ map_insdelfind.cpp
+ map_insdelfind_bronsonavltree.cpp
+ map_insdelfind_ellentree_rcu.cpp
+ map_insdelfind_feldman_hashset_rcu.cpp
+ map_insdelfind_michael_rcu.cpp
+ map_insdelfind_skip_rcu.cpp
+ map_insdelfind_split_rcu.cpp
+)
+
+include_directories(
+ ${CMAKE_CURRENT_SOURCE_DIR}
+ ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${MAP_INSDELFIND_HP} ${CDSSTRESS_MAP_INSDELFIND_HP_SOURCES})
+target_link_libraries(${MAP_INSDELFIND_HP} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+add_test(NAME ${MAP_INSDELFIND_HP} COMMAND ${MAP_INSDELFIND_HP} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
+
+add_executable(${MAP_INSDELFIND_RCU} ${CDSSTRESS_MAP_INSDELFIND_RCU_SOURCES})
+target_link_libraries(${MAP_INSDELFIND_RCU} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+add_test(NAME ${MAP_INSDELFIND_RCU} COMMAND ${MAP_INSDELFIND_RCU} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
+
+add_custom_target( stress-sequential-map-insdelfind
+ DEPENDS
+ stress-sequential-map-insdelfind-hp
+ stress-sequential-map-insdelfind-rcu
+)
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+
+namespace map {
+
+ size_t Map_InsDelFind::s_nMapSize = 500000;
+ size_t Map_InsDelFind::s_nThreadCount = 8;
+ size_t Map_InsDelFind::s_nMaxLoadFactor = 8;
+ unsigned int Map_InsDelFind::s_nInsertPercentage = 5;
+ unsigned int Map_InsDelFind::s_nDeletePercentage = 5;
+ unsigned int Map_InsDelFind::s_nDuration = 30;
+
+
+ size_t Map_InsDelFind::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+ size_t Map_InsDelFind::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+ size_t Map_InsDelFind::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+ size_t Map_InsDelFind::s_nFeldmanMap_HeadBits = 10;
+ size_t Map_InsDelFind::s_nFeldmanMap_ArrayBits = 4;
+
+ size_t Map_InsDelFind::s_nLoadFactor = 1;
+ Map_InsDelFind::actions Map_InsDelFind::s_arrShuffle[Map_InsDelFind::c_nShuffleSize];
+
+ void Map_InsDelFind::SetUpTestCase()
+ {
+ cds_test::config const& cfg = get_config( "map_insdelfind" );
+
+ s_nMapSize = cfg.get_size_t( "InitialMapSize", s_nMapSize );
+ if ( s_nMapSize < 1000 )
+ s_nMapSize = 1000;
+
+ s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+ if ( s_nThreadCount == 0 )
+ s_nThreadCount = std::min( 16u, std::thread::hardware_concurrency() * 2 );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ s_nInsertPercentage = cfg.get_uint( "InsertPercentage", s_nInsertPercentage );
+ if ( s_nInsertPercentage >= 100 )
+ s_nInsertPercentage = 99;
+
+ s_nDeletePercentage = cfg.get_uint( "DeletePercentage", s_nDeletePercentage );
+ if ( s_nDeletePercentage >= 100 )
+ s_nDeletePercentage = 99;
+
+ if ( s_nInsertPercentage + s_nDeletePercentage > 100 ) {
+ unsigned int total = s_nInsertPercentage + s_nDeletePercentage;
+ s_nInsertPercentage = s_nInsertPercentage * 100 / total;
+ s_nDeletePercentage = s_nDeletePercentage * 100 / total;
+ }
+
+ s_nDuration = cfg.get_uint( "Duration", s_nDuration );
+ if ( s_nDuration < 5 )
+ s_nDuration = 5;
+
+ s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+ if ( s_nCuckooInitialSize < 256 )
+ s_nCuckooInitialSize = 256;
+
+ s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+ if ( s_nCuckooProbesetSize < 8 )
+ s_nCuckooProbesetSize = 8;
+
+ s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+ s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+ if ( s_nFeldmanMap_HeadBits == 0 )
+ s_nFeldmanMap_HeadBits = 2;
+
+ s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+ if ( s_nFeldmanMap_ArrayBits == 0 )
+ s_nFeldmanMap_ArrayBits = 2;
+
+ actions * pFirst = s_arrShuffle;
+ actions * pLast = s_arrShuffle + s_nInsertPercentage;
+ std::fill( pFirst, pLast, do_insert );
+ pFirst = pLast;
+ pLast += s_nDeletePercentage;
+ std::fill( pFirst, pLast, do_delete );
+ pFirst = pLast;
+ pLast = s_arrShuffle + sizeof( s_arrShuffle ) / sizeof( s_arrShuffle[0] );
+ if ( pFirst < pLast )
+ std::fill( pFirst, pLast, do_find );
+ shuffle( s_arrShuffle, pLast );
+ }
+
+ std::vector<size_t> Map_InsDelFind_LF::get_load_factors()
+ {
+ cds_test::config const& cfg = get_config( "map_insdelfind" );
+
+ s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+ if ( s_nMaxLoadFactor == 0 )
+ s_nMaxLoadFactor = 1;
+
+ std::vector<size_t> lf;
+ for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+ lf.push_back( n );
+
+ return lf;
+ }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+ static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+ {
+ return std::to_string( p.param );
+ }
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDelFind_LF, ::testing::ValuesIn( Map_InsDelFind_LF::get_load_factors()), get_test_parameter_name );
+#else
+ INSTANTIATE_TEST_CASE_P( a, Map_InsDelFind_LF, ::testing::ValuesIn( Map_InsDelFind_LF::get_load_factors()));
+#endif
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_type.h"
+
+namespace map {
+
+
+ class Map_InsDelFind: public cds_test::stress_fixture
+ {
+ public:
+ static size_t s_nMapSize; // initial map size
+ static size_t s_nThreadCount; // thread count
+ static size_t s_nMaxLoadFactor; // maximum load factor
+ static unsigned int s_nInsertPercentage;
+ static unsigned int s_nDeletePercentage;
+ static unsigned int s_nDuration; // test duration, seconds
+
+ static size_t s_nCuckooInitialSize; // initial size for CuckooMap
+ static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
+ static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (o - use default)
+
+ static size_t s_nFeldmanMap_HeadBits;
+ static size_t s_nFeldmanMap_ArrayBits;
+
+ static size_t s_nLoadFactor; // current load factor
+
+ static void SetUpTestCase();
+ //static void TearDownTestCase();
+
+ public:
+ enum actions
+ {
+ do_find,
+ do_insert,
+ do_delete
+ };
+ static const unsigned int c_nShuffleSize = 100;
+ static actions s_arrShuffle[c_nShuffleSize];
+
+ protected:
+ typedef size_t key_type;
+ typedef size_t value_type;
+
+ template <class Map>
+ class Worker: public cds_test::thread
+ {
+ typedef cds_test::thread base_class;
+ Map& m_Map;
+
+ public:
+ size_t m_nInsertSuccess = 0;
+ size_t m_nInsertFailed = 0;
+ size_t m_nDeleteSuccess = 0;
+ size_t m_nDeleteFailed = 0;
+ size_t m_nFindSuccess = 0;
+ size_t m_nFindFailed = 0;
+
+ public:
+ Worker( cds_test::thread_pool& pool, Map& map )
+ : base_class( pool )
+ , m_Map( map )
+ {}
+
+ Worker( Worker& src )
+ : base_class( src )
+ , m_Map( src.m_Map )
+ {}
+
+ virtual thread * clone()
+ {
+ return new Worker( *this );
+ }
+
+ typedef std::pair< key_type const, value_type > map_value_type;
+
+ struct update_functor {
+ template <typename Q>
+ void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ ) const
+ {}
+
+ // FeldmanHashMap
+ void operator()( map_value_type& /*cur*/, map_value_type* /*old*/) const
+ {}
+
+ // MichaelMap
+ void operator()( bool /*bNew*/, map_value_type& /*cur*/ ) const
+ {}
+
+ // BronsonAVLTreeMap
+ void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ ) const
+ {}
+ };
+
+ virtual void test()
+ {
+ Map& rMap = m_Map;
+
+ unsigned int i = 0;
+ size_t const nNormalize = size_t(-1) / ( s_nMapSize * 2 );
+
+ size_t nRand = 0;
+ while ( !time_elapsed()) {
+ nRand = cds::bitop::RandXorShift( nRand );
+ size_t n = nRand / nNormalize;
+ switch ( s_arrShuffle[i] ) {
+ case do_find:
+ if ( rMap.contains( n ))
+ ++m_nFindSuccess;
+ else
+ ++m_nFindFailed;
+ break;
+ case do_insert:
+ if ( n % 2 ) {
+ if ( rMap.insert( n, n ))
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ else {
+ if ( rMap.update( n, update_functor(), true ).first )
+ ++m_nInsertSuccess;
+ else
+ ++m_nInsertFailed;
+ }
+ break;
+ case do_delete:
+ if ( rMap.erase( n ))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ break;
+ }
+
+ if ( ++i >= c_nShuffleSize )
+ i = 0;
+ }
+ }
+ };
+
+ protected:
+ template <class Map>
+ void do_test( Map& testMap )
+ {
+ typedef Worker<Map> worker;
+
+ // fill map - only odd number
+ {
+ std::vector<size_t> arr;
+ arr.reserve( s_nMapSize );
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ arr.push_back( i * 2 + 1);
+ shuffle( arr.begin(), arr.end());
+ for ( size_t i = 0; i < s_nMapSize; ++i )
+ testMap.insert( arr[i], arr[i] );
+ }
+
+ cds_test::thread_pool& pool = get_pool();
+ pool.add( new worker( pool, testMap ), s_nThreadCount );
+
+ propout() << std::make_pair( "thread_count", s_nThreadCount )
+ << std::make_pair( "insert_percentage", s_nInsertPercentage )
+ << std::make_pair( "delete_percentage", s_nDeletePercentage )
+ << std::make_pair( "map_size", s_nMapSize );
+
+ std::chrono::milliseconds duration = pool.run( std::chrono::seconds( s_nDuration ));
+
+ propout() << std::make_pair( "duration", duration );
+
+ size_t nInsertSuccess = 0;
+ size_t nInsertFailed = 0;
+ size_t nDeleteSuccess = 0;
+ size_t nDeleteFailed = 0;
+ size_t nFindSuccess = 0;
+ size_t nFindFailed = 0;
+ for ( size_t i = 0; i < pool.size(); ++i ) {
+ worker& thr = static_cast<worker&>( pool.get( i ));
+
+ nInsertSuccess += thr.m_nInsertSuccess;
+ nInsertFailed += thr.m_nInsertFailed;
+ nDeleteSuccess += thr.m_nDeleteSuccess;
+ nDeleteFailed += thr.m_nDeleteFailed;
+ nFindSuccess += thr.m_nFindSuccess;
+ nFindFailed += thr.m_nFindFailed;
+ }
+
+ propout()
+ << std::make_pair( "insert_success", nInsertSuccess )
+ << std::make_pair( "insert_failed", nInsertFailed )
+ << std::make_pair( "delete_success", nDeleteSuccess )
+ << std::make_pair( "delete_failed", nDeleteFailed )
+ << std::make_pair( "find_success", nFindSuccess )
+ << std::make_pair( "find_failed", nFindFailed )
+ << std::make_pair( "finish_map_size", testMap.size());
+
+ {
+ ASSERT_TRUE( std::chrono::duration_cast<std::chrono::seconds>(duration).count() > 0 );
+ size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
+ propout() << std::make_pair( "avg_speed", nTotalOps / std::chrono::duration_cast<std::chrono::seconds>( duration ).count());
+ }
+
+ check_before_cleanup( testMap );
+
+ testMap.clear();
+ EXPECT_TRUE( testMap.empty());
+
+ additional_check( testMap );
+ print_stat( propout(), testMap );
+ additional_cleanup( testMap );
+ }
+
+ template <class Map>
+ void run_test()
+ {
+ Map testMap( *this );
+ do_test( testMap );
+ }
+ };
+
+ class Map_InsDelFind_LF: public Map_InsDelFind
+ , public ::testing::WithParamInterface<size_t>
+ {
+ public:
+ template <class Map>
+ void run_test()
+ {
+ s_nLoadFactor = GetParam();
+ propout() << std::make_pair( "load_factor", s_nLoadFactor );
+ Map_InsDelFind::run_test<Map>();
+ }
+
+ static std::vector<size_t> get_load_factors();
+ };
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+ CDSSTRESS_BronsonAVLTreeMap( Map_InsDelFind, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_cuckoo.h"
+
+namespace map {
+
+// CDSSTRESS_CuckooMap( Map_InsDelFind, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap_HP( Map_InsDelFind, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+ CDSSTRESS_EllenBinTreeMap_RCU( Map_InsDelFind, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ CDSSTRESS_FeldmanHashMap_fixed_HP( Map_InsDelFind, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_feldman_hashmap.h"
+
+namespace map {
+
+ CDSSTRESS_FeldmanHashMap_fixed_RCU( Map_InsDelFind, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
+
+#include "map_insdelfind.h"
+#include "map_type_michael.h"
+
+namespace map {
+
+ CDSSTRESS_MichaelMap_HP( Map_InsDelFind_LF, run_test, size_t, size_t )
+
+} // namespace map
--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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/
+
projects / libcds.git / commitdiff