2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #include "map_find_string.h"
32 #include <cds_test/hash_func.h>
36 size_t Map_find_string::s_nThreadCount = 8;
37 size_t Map_find_string::s_nMapSize = 10000000;
38 size_t Map_find_string::s_nMaxLoadFactor = 8;
39 size_t Map_find_string::s_nPercentExists = 50;
40 size_t Map_find_string::s_nPassCount = 2;
41 size_t Map_find_string::s_nFeldmanPassCount = 100;
42 size_t Map_find_string::s_nBronsonAVLTreeMapPassCount = 100;
43 size_t Map_find_string::s_nEllenBinTreeMapPassCount = 100;
44 size_t Map_find_string::s_nMichaelMapPassCount = 100;
45 size_t Map_find_string::s_nSkipListMapPassCount = 100;
47 size_t Map_find_string::s_nCuckooInitialSize = 1024;
48 size_t Map_find_string::s_nCuckooProbesetSize = 16;
49 size_t Map_find_string::s_nCuckooProbesetThreshold = 0;
51 size_t Map_find_string::s_nFeldmanMap_HeadBits = 10;
52 size_t Map_find_string::s_nFeldmanMap_ArrayBits = 4;
55 size_t Map_find_string::s_nLoadFactor = 1;
56 Map_find_string::value_vector Map_find_string::s_Data;
57 std::vector<std::string> Map_find_string::s_arrString;
59 void Map_find_string::setup_test_case()
61 cds_test::config const &cfg =
62 get_config("sequential_real_map_find_string");
64 s_nMapSize = cfg.get_size_t("MapSize", s_nMapSize);
65 if (s_nMapSize < 1000)
68 s_nThreadCount = cfg.get_size_t("ThreadCount", s_nThreadCount);
69 if (s_nThreadCount == 0)
72 s_nPassCount = cfg.get_size_t("PassCount", s_nPassCount);
73 if (s_nPassCount == 0)
77 cfg.get_size_t("FeldmanPassCount", s_nFeldmanPassCount);
78 if (s_nFeldmanPassCount == 0)
79 s_nFeldmanPassCount = 500;
81 s_nBronsonAVLTreeMapPassCount = cfg.get_size_t(
82 "BronsonAVLTreeMapPassCount", s_nBronsonAVLTreeMapPassCount);
83 if (s_nBronsonAVLTreeMapPassCount == 0)
84 s_nBronsonAVLTreeMapPassCount = 500;
86 s_nEllenBinTreeMapPassCount = cfg.get_size_t("EllenBinTreeMapPassCount",
87 s_nEllenBinTreeMapPassCount);
88 if (s_nEllenBinTreeMapPassCount == 0)
89 s_nEllenBinTreeMapPassCount = 500;
91 s_nMichaelMapPassCount =
92 cfg.get_size_t("MichaelMapPassCount", s_nMichaelMapPassCount);
93 if (s_nMichaelMapPassCount == 0)
94 s_nMichaelMapPassCount = 500;
96 s_nSkipListMapPassCount =
97 cfg.get_size_t("SkipListMapPassCount", s_nSkipListMapPassCount);
98 if (s_nSkipListMapPassCount == 0)
99 s_nSkipListMapPassCount = 500;
101 s_nPercentExists = cfg.get_size_t("PercentExists", s_nPercentExists);
102 if (s_nPercentExists > 100)
103 s_nPercentExists = 100;
104 else if (s_nPercentExists < 1)
105 s_nPercentExists = 1;
107 s_nMaxLoadFactor = cfg.get_size_t("MaxLoadFactor", s_nMaxLoadFactor);
108 if (s_nMaxLoadFactor == 0)
109 s_nMaxLoadFactor = 1;
111 s_nCuckooInitialSize =
112 cfg.get_size_t("CuckooInitialSize", s_nCuckooInitialSize);
113 if (s_nCuckooInitialSize < 256)
114 s_nCuckooInitialSize = 256;
116 s_nCuckooProbesetSize =
117 cfg.get_size_t("CuckooProbesetSize", s_nCuckooProbesetSize);
118 if (s_nCuckooProbesetSize < 8)
119 s_nCuckooProbesetSize = 8;
121 s_nCuckooProbesetThreshold =
122 cfg.get_size_t("CuckooProbesetThreshold", s_nCuckooProbesetThreshold);
124 s_nFeldmanMap_HeadBits =
125 cfg.get_size_t("FeldmanMapHeadBits", s_nFeldmanMap_HeadBits);
126 if (s_nFeldmanMap_HeadBits == 0)
127 s_nFeldmanMap_HeadBits = 2;
129 s_nFeldmanMap_ArrayBits =
130 cfg.get_size_t("FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits);
131 if (s_nFeldmanMap_ArrayBits == 0)
132 s_nFeldmanMap_ArrayBits = 2;
134 s_arrString = load_dictionary();
137 void Map_find_string::TearDownTestCase()
143 void Map_find_string::SetUpTestCase()
149 size_t nSize = s_arrString.size();
150 if ( nSize > s_nMapSize )
152 s_Data.reserve( nSize );
154 size_t nActualSize = 0;
155 for ( size_t i = 0; i < nSize; ++i ) {
156 bool bExists = rand( 100 ) <= s_nPercentExists;
159 s_Data.push_back( { &s_arrString.at( i ), bExists } );
161 s_nMapSize = nActualSize;
164 template <typename Hash>
165 void Map_find_string::fill_string_array()
168 typedef typename hasher::result_type hash_type;
170 std::map<hash_type, size_t> mapHash;
173 size_t nSize = s_arrString.size();
174 if ( nSize > s_nMapSize )
176 s_Data.reserve( nSize );
178 size_t nActualSize = 0;
179 size_t nDiffHash = 0;
181 for ( size_t i = 0; i < s_arrString.size(); ++i ) {
182 hash_type hash = h( s_arrString.at( i ));
183 if ( mapHash.insert( std::make_pair( hash, i )).second ) {
184 if ( ++nDiffHash >= nSize )
186 bool bExists = rand( 100 ) <= s_nPercentExists;
189 s_Data.push_back( { &s_arrString.at( i ), bExists } );
192 s_nMapSize = nActualSize;
196 void Map_find_string_stdhash::SetUpTestCase()
199 fill_string_array<std::hash<std::string>>();
202 #if CDS_BUILD_BITS == 64
203 void Map_find_string_city32::SetUpTestCase()
206 fill_string_array<cds_test::city32>();
209 void Map_find_string_city64::SetUpTestCase()
212 fill_string_array<cds_test::city64>();
215 void Map_find_string_city128::SetUpTestCase()
218 fill_string_array<cds_test::city128>();
223 std::vector<size_t> Map_find_string::get_load_factors()
225 cds_test::config const& cfg = get_config( "map_find_string" );
227 s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
228 if ( s_nMaxLoadFactor == 0 )
229 s_nMaxLoadFactor = 1;
231 std::vector<size_t> lf;
232 for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
238 #ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
239 static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
241 return std::to_string( p.param );
243 INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()), get_test_parameter_name );
245 INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()));