2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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 #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_ITERABLE_SET_H
32 #define CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_ITERABLE_SET_H
34 #include <cds_test/check_size.h>
35 #include <cds_test/fixture.h>
37 #include <cds/opt/hash.h>
38 #include <functional> // ref
40 // forward declaration
41 namespace cds { namespace intrusive {}}
45 namespace ci = cds::intrusive;
46 namespace co = cds::opt;
48 class intrusive_split_iterable_set: public fixture
51 static size_t const kSize = 100;
55 unsigned int nDisposeCount ; // count of disposer calling
56 unsigned int nFindCount ; // count of find-functor calling
57 unsigned int nUpdateNewCount;
58 unsigned int nUpdateCount;
59 mutable unsigned int nEraseCount;
68 memset( this, 0, sizeof( *this ));
72 template <typename Base>
73 struct item_type: public stat, public Base
90 size_t operator()( int i ) const
92 return co::v::hash<int>()( i );
95 size_t operator()( Q const& i ) const
97 return (*this)( i.key());
101 struct simple_item_counter {
104 simple_item_counter()
123 operator size_t() const
131 template <typename T>
134 bool operator ()(const T& v1, const T& v2 ) const
136 return v1.key() < v2.key();
139 template <typename Q>
140 bool operator ()(const T& v1, const Q& v2 ) const
142 return v1.key() < v2;
145 template <typename Q>
146 bool operator ()(const Q& v1, const T& v2 ) const
148 return v1 < v2.key();
152 template <typename T>
154 int operator ()(const T& v1, const T& v2 ) const
156 if ( v1.key() < v2.key())
158 return v1.key() > v2.key() ? 1 : 0;
161 template <typename Q>
162 int operator ()(const T& v1, const Q& v2 ) const
166 return v1.key() > v2 ? 1 : 0;
169 template <typename Q>
170 int operator ()(const Q& v1, const T& v2 ) const
174 return v1 > v2.key() ? 1 : 0;
181 explicit other_item( int k )
192 template <typename Q, typename T>
193 bool operator()( Q const& lhs, T const& rhs ) const
195 return lhs.key() < rhs.key();
201 template <typename T>
202 void operator ()( T * p )
212 // Precondition: set is empty
213 // Postcondition: set is empty
215 ASSERT_TRUE( s.empty());
216 ASSERT_CONTAINER_SIZE( s, 0 );
217 size_t const nSetSize = kSize;
219 typedef typename Set::value_type value_type;
221 std::vector< value_type > data;
222 std::vector< size_t> indices;
223 data.reserve( kSize );
224 indices.reserve( kSize );
225 for ( size_t key = 0; key < kSize; ++key ) {
226 data.push_back( value_type( static_cast<int>( key )));
227 indices.push_back( key );
229 shuffle( indices.begin(), indices.end());
232 for ( auto idx : indices ) {
233 auto& i = data[ idx ];
235 ASSERT_FALSE( s.contains( i.nKey ));
236 ASSERT_FALSE( s.contains( i ));
237 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
238 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
239 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
240 ASSERT_TRUE( s.find( i.nKey ) == s.end());
241 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) == s.end());
243 std::pair<bool, bool> updResult;
245 updResult = s.update( i, []( value_type&, value_type* )
247 ASSERT_TRUE( false );
249 EXPECT_FALSE( updResult.first );
250 EXPECT_FALSE( updResult.second );
252 updResult = s.upsert( i, false );
253 EXPECT_FALSE( updResult.first );
254 EXPECT_FALSE( updResult.second );
256 switch ( i.key() % 4 ) {
258 ASSERT_TRUE( s.insert( i ));
259 ASSERT_FALSE( s.insert( i ));
260 updResult = s.update( i, []( value_type& val, value_type* arg)
262 ASSERT_TRUE( arg != nullptr );
263 EXPECT_EQ( val.key(), arg->key());
265 EXPECT_TRUE( updResult.first );
266 EXPECT_FALSE( updResult.second );
269 EXPECT_EQ( i.nUpdateNewCount, 0u );
270 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
271 EXPECT_EQ( i.nUpdateNewCount, 1u );
272 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
273 EXPECT_EQ( i.nUpdateNewCount, 1u );
274 i.nUpdateNewCount = 0;
277 updResult = s.update( i, []( value_type& /*val*/, value_type* arg )
279 EXPECT_TRUE( arg == nullptr );
281 EXPECT_TRUE( updResult.first );
282 EXPECT_TRUE( updResult.second );
285 updResult = s.upsert( i );
286 EXPECT_TRUE( updResult.first );
287 EXPECT_TRUE( updResult.second );
291 ASSERT_TRUE( s.contains( i.nKey ));
292 ASSERT_TRUE( s.contains( i ));
293 ASSERT_TRUE( s.contains( other_item( i.key()), other_less()));
294 EXPECT_EQ( i.nFindCount, 0u );
295 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
296 EXPECT_EQ( i.nFindCount, 1u );
297 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
298 EXPECT_EQ( i.nFindCount, 2u );
299 ASSERT_TRUE( s.find( i.nKey ) != s.end());
300 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) != s.end());
301 EXPECT_EQ( s.find( i.nKey )->nKey, i.key());
302 EXPECT_EQ( s.find_with( other_item( i.key()), other_less())->nKey, i.key());
304 ASSERT_FALSE( s.empty());
305 ASSERT_CONTAINER_SIZE( s, nSetSize );
307 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
310 shuffle( indices.begin(), indices.end());
311 for ( auto idx : indices ) {
312 auto& i = data[ idx ];
314 ASSERT_TRUE( s.contains( i.nKey ));
315 ASSERT_TRUE( s.contains( i ));
316 ASSERT_TRUE( s.contains( other_item( i.key()), other_less()));
317 EXPECT_EQ( i.nFindCount, 0u );
318 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
319 EXPECT_EQ( i.nFindCount, 1u );
320 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
321 EXPECT_EQ( i.nFindCount, 2u );
322 ASSERT_TRUE( s.find( i.nKey ) != s.end());
323 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) != s.end());
324 EXPECT_EQ( s.find( i.nKey )->nKey, i.key());
325 EXPECT_EQ( s.find_with( other_item( i.key()), other_less())->nKey, i.key());
329 switch ( i.key() % 6 ) {
331 ASSERT_FALSE( s.unlink( v ));
332 ASSERT_TRUE( s.unlink( i ));
333 ASSERT_FALSE( s.unlink( i ));
336 ASSERT_TRUE( s.erase( i.key()));
337 ASSERT_FALSE( s.erase( i.key()));
340 ASSERT_TRUE( s.erase( v ));
341 ASSERT_FALSE( s.erase( v ));
344 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
345 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less()));
348 EXPECT_EQ( i.nEraseCount, 0u );
349 ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
350 EXPECT_EQ( i.nEraseCount, 1u );
351 ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
352 EXPECT_EQ( i.nEraseCount, 1u );
355 EXPECT_EQ( i.nEraseCount, 0u );
356 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
357 EXPECT_EQ( i.nEraseCount, 1u );
358 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
359 EXPECT_EQ( i.nEraseCount, 1u );
363 ASSERT_FALSE( s.contains( i.nKey ));
364 ASSERT_FALSE( s.contains( i ));
365 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
366 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
367 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
368 ASSERT_TRUE( s.find( i.nKey ) == s.end());
369 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) == s.end());
371 ASSERT_TRUE( s.empty());
372 ASSERT_CONTAINER_SIZE( s, 0u );
374 // Force retiring cycle
375 Set::gc::force_dispose();
376 for ( auto& i : data ) {
377 EXPECT_EQ( i.nDisposeCount, 1u );
381 for ( auto& i : data ) {
383 ASSERT_TRUE( s.insert( i ));
385 ASSERT_FALSE( s.empty());
386 ASSERT_CONTAINER_SIZE( s, nSetSize );
389 for ( auto it = s.begin(); it != s.end(); ++it ) {
392 for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
393 EXPECT_EQ( it->nFindCount, 1u );
395 for ( auto& i : data ) {
396 EXPECT_EQ( i.nFindCount, 1u );
402 ASSERT_TRUE( s.empty());
403 ASSERT_CONTAINER_SIZE( s, 0u );
404 ASSERT_TRUE( s.begin() == s.end());
405 ASSERT_TRUE( s.cbegin() == s.cend());
407 // Force retiring cycle
408 Set::gc::force_dispose();
409 for ( auto& i : data ) {
410 EXPECT_EQ( i.nDisposeCount, 1u );
416 } // namespace cds_test
418 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SPLIT_ITERABLE_SET_H