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;
42 size_t Map_find_string::s_nCuckooInitialSize = 1024;
43 size_t Map_find_string::s_nCuckooProbesetSize = 16;
44 size_t Map_find_string::s_nCuckooProbesetThreshold = 0;
46 size_t Map_find_string::s_nFeldmanMap_HeadBits = 10;
47 size_t Map_find_string::s_nFeldmanMap_ArrayBits = 4;
50 size_t Map_find_string::s_nLoadFactor = 1;
51 Map_find_string::value_vector Map_find_string::s_Data;
52 std::vector<std::string> Map_find_string::s_arrString;
54 void Map_find_string::setup_test_case()
56 cds_test::config const& cfg = get_config( "map_find_string" );
58 s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
59 if ( s_nMapSize < 1000 )
62 s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
63 if ( s_nThreadCount == 0 )
66 s_nPercentExists = cfg.get_size_t( "PercentExists", s_nPercentExists );
67 if ( s_nPercentExists > 100 )
68 s_nPercentExists = 100;
69 else if ( s_nPercentExists < 1 )
72 s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
73 if ( s_nMaxLoadFactor == 0 )
76 s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
77 if ( s_nCuckooInitialSize < 256 )
78 s_nCuckooInitialSize = 256;
80 s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
81 if ( s_nCuckooProbesetSize < 8 )
82 s_nCuckooProbesetSize = 8;
84 s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
86 s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
87 if ( s_nFeldmanMap_HeadBits == 0 )
88 s_nFeldmanMap_HeadBits = 2;
90 s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
91 if ( s_nFeldmanMap_ArrayBits == 0 )
92 s_nFeldmanMap_ArrayBits = 2;
94 s_arrString = load_dictionary();
97 void Map_find_string::TearDownTestCase()
103 void Map_find_string::SetUpTestCase()
109 size_t nSize = s_arrString.size();
110 if ( nSize > s_nMapSize )
112 s_Data.reserve( nSize );
114 size_t nActualSize = 0;
115 for ( size_t i = 0; i < nSize; ++i ) {
116 bool bExists = rand( 100 ) <= s_nPercentExists;
119 s_Data.push_back( { &s_arrString.at( i ), bExists } );
121 s_nMapSize = nActualSize;
124 template <typename Hash>
125 void Map_find_string::fill_string_array()
128 typedef typename hasher::result_type hash_type;
130 std::map<hash_type, size_t> mapHash;
133 size_t nSize = s_arrString.size();
134 if ( nSize > s_nMapSize )
136 s_Data.reserve( nSize );
138 size_t nActualSize = 0;
139 size_t nDiffHash = 0;
141 for ( size_t i = 0; i < s_arrString.size(); ++i ) {
142 hash_type hash = h( s_arrString.at( i ));
143 if ( mapHash.insert( std::make_pair( hash, i )).second ) {
144 if ( ++nDiffHash >= nSize )
146 bool bExists = rand( 100 ) <= s_nPercentExists;
149 s_Data.push_back( { &s_arrString.at( i ), bExists } );
152 s_nMapSize = nActualSize;
156 void Map_find_string_stdhash::SetUpTestCase()
159 fill_string_array<std::hash<std::string>>();
162 #if CDS_BUILD_BITS == 64
163 void Map_find_string_city32::SetUpTestCase()
166 fill_string_array<cds_test::city32>();
169 void Map_find_string_city64::SetUpTestCase()
172 fill_string_array<cds_test::city64>();
175 void Map_find_string_city128::SetUpTestCase()
178 fill_string_array<cds_test::city128>();
183 std::vector<size_t> Map_find_string::get_load_factors()
185 cds_test::config const& cfg = get_config( "map_find_string" );
187 s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
188 if ( s_nMaxLoadFactor == 0 )
189 s_nMaxLoadFactor = 1;
191 std::vector<size_t> lf;
192 for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
198 #ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
199 static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
201 return std::to_string( p.param );
203 INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()), get_test_parameter_name );
205 INSTANTIATE_TEST_CASE_P( a, Map_find_string_LF, ::testing::ValuesIn( Map_find_string::get_load_factors()));