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_MICHAEL_ITERABLE_H
32 #define CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_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_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 struct item_type: public stat
89 size_t operator()( int i ) const
91 return co::v::hash<int>()( i );
94 size_t operator()( Q const& i ) const
96 return (*this)( i.key());
100 struct simple_item_counter {
103 simple_item_counter()
122 operator size_t() const
130 template <typename T>
133 bool operator ()(const T& v1, const T& v2 ) const
135 return v1.key() < v2.key();
138 template <typename Q>
139 bool operator ()(const T& v1, const Q& v2 ) const
141 return v1.key() < v2;
144 template <typename Q>
145 bool operator ()(const Q& v1, const T& v2 ) const
147 return v1 < v2.key();
151 template <typename T>
153 int operator ()(const T& v1, const T& v2 ) const
155 if ( v1.key() < v2.key())
157 return v1.key() > v2.key() ? 1 : 0;
160 template <typename Q>
161 int operator ()(const T& v1, const Q& v2 ) const
165 return v1.key() > v2 ? 1 : 0;
168 template <typename Q>
169 int operator ()(const Q& v1, const T& v2 ) const
173 return v1 > v2.key() ? 1 : 0;
180 explicit other_item( int k )
191 template <typename Q, typename T>
192 bool operator()( Q const& lhs, T const& rhs ) const
194 return lhs.key() < rhs.key();
200 template <typename T>
201 void operator ()( T * p )
211 // Precondition: set is empty
212 // Postcondition: set is empty
214 ASSERT_TRUE( s.empty());
215 ASSERT_CONTAINER_SIZE( s, 0 );
216 size_t const nSetSize = kSize;
218 typedef typename Set::value_type value_type;
220 std::vector< value_type > data;
221 std::vector< size_t> indices;
222 data.reserve( kSize );
223 indices.reserve( kSize );
224 for ( size_t key = 0; key < kSize; ++key ) {
225 data.push_back( value_type( static_cast<int>( key )));
226 indices.push_back( key );
228 shuffle( indices.begin(), indices.end());
231 for ( auto idx : indices ) {
232 auto& i = data[ idx ];
234 ASSERT_FALSE( s.contains( i.nKey ));
235 ASSERT_FALSE( s.contains( i ));
236 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
237 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
238 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
239 ASSERT_TRUE( s.find( i.nKey ) == s.end());
240 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) == s.end());
242 std::pair<bool, bool> updResult;
244 updResult = s.update( i, []( value_type&, value_type* )
246 ASSERT_TRUE( false );
248 EXPECT_FALSE( updResult.first );
249 EXPECT_FALSE( updResult.second );
251 updResult = s.upsert( i, false );
252 EXPECT_FALSE( updResult.first );
253 EXPECT_FALSE( updResult.second );
255 switch ( i.key() % 4 ) {
257 ASSERT_TRUE( s.insert( i ));
258 ASSERT_FALSE( s.insert( i ));
259 updResult = s.update( i, []( value_type& val, value_type* arg)
261 ASSERT_TRUE( arg != nullptr );
262 EXPECT_EQ( val.key(), arg->key());
264 EXPECT_TRUE( updResult.first );
265 EXPECT_FALSE( updResult.second );
268 EXPECT_EQ( i.nUpdateNewCount, 0u );
269 ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
270 EXPECT_EQ( i.nUpdateNewCount, 1u );
271 ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
272 EXPECT_EQ( i.nUpdateNewCount, 1u );
273 i.nUpdateNewCount = 0;
276 updResult = s.update( i, []( value_type& /*val*/, value_type* arg )
278 EXPECT_TRUE( arg == nullptr );
280 EXPECT_TRUE( updResult.first );
281 EXPECT_TRUE( updResult.second );
284 updResult = s.upsert( i );
285 EXPECT_TRUE( updResult.first );
286 EXPECT_TRUE( updResult.second );
290 ASSERT_TRUE( s.contains( i.nKey ));
291 ASSERT_TRUE( s.contains( i ));
292 ASSERT_TRUE( s.contains( other_item( i.key()), other_less()));
293 EXPECT_EQ( i.nFindCount, 0u );
294 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
295 EXPECT_EQ( i.nFindCount, 1u );
296 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
297 EXPECT_EQ( i.nFindCount, 2u );
298 ASSERT_TRUE( s.find( i.nKey ) != s.end());
299 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) != s.end());
300 EXPECT_EQ( s.find( i.nKey )->nKey, i.key());
301 EXPECT_EQ( s.find_with( other_item( i.key()), other_less())->nKey, i.key());
303 ASSERT_FALSE( s.empty());
304 ASSERT_CONTAINER_SIZE( s, nSetSize );
306 std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
309 shuffle( indices.begin(), indices.end());
310 for ( auto idx : indices ) {
311 auto& i = data[ idx ];
313 ASSERT_TRUE( s.contains( i.nKey ));
314 ASSERT_TRUE( s.contains( i ));
315 ASSERT_TRUE( s.contains( other_item( i.key()), other_less()) );
316 EXPECT_EQ( i.nFindCount, 0u );
317 ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
318 EXPECT_EQ( i.nFindCount, 1u );
319 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
320 EXPECT_EQ( i.nFindCount, 2u );
321 ASSERT_TRUE( s.find( i.nKey ) != s.end());
322 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) != s.end());
323 EXPECT_EQ( s.find( i.nKey )->nKey, i.key());
324 EXPECT_EQ( s.find_with( other_item( i.key()), other_less())->nKey, i.key());
328 switch ( i.key() % 6 ) {
330 ASSERT_FALSE( s.unlink( v ));
331 ASSERT_TRUE( s.unlink( i ));
332 ASSERT_FALSE( s.unlink( i ));
335 ASSERT_TRUE( s.erase( i.key()));
336 ASSERT_FALSE( s.erase( i.key()) );
339 ASSERT_TRUE( s.erase( v ));
340 ASSERT_FALSE( s.erase( v ));
343 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
344 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less()) );
347 EXPECT_EQ( i.nEraseCount, 0u );
348 ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
349 EXPECT_EQ( i.nEraseCount, 1u );
350 ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
351 EXPECT_EQ( i.nEraseCount, 1u );
354 EXPECT_EQ( i.nEraseCount, 0u );
355 ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
356 EXPECT_EQ( i.nEraseCount, 1u );
357 ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
358 EXPECT_EQ( i.nEraseCount, 1u );
362 ASSERT_FALSE( s.contains( i.nKey ));
363 ASSERT_FALSE( s.contains( i ));
364 ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
365 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
366 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
367 ASSERT_TRUE( s.find( i.nKey ) == s.end());
368 ASSERT_TRUE( s.find_with( other_item( i.key()), other_less()) == s.end());
370 ASSERT_TRUE( s.empty());
371 ASSERT_CONTAINER_SIZE( s, 0u );
373 // Force retiring cycle
374 Set::gc::force_dispose();
375 for ( auto& i : data ) {
376 EXPECT_EQ( i.nDisposeCount, 1u );
380 for ( auto& i : data ) {
382 ASSERT_TRUE( s.insert( i ));
384 ASSERT_FALSE( s.empty());
385 ASSERT_CONTAINER_SIZE( s, nSetSize );
388 for ( auto it = s.begin(); it != s.end(); ++it ) {
391 for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
392 EXPECT_EQ( it->nFindCount, 1u );
394 for ( auto& i : data ) {
395 EXPECT_EQ( i.nFindCount, 1u );
401 ASSERT_TRUE( s.empty());
402 ASSERT_CONTAINER_SIZE( s, 0u );
403 ASSERT_TRUE( s.begin() == s.end());
404 ASSERT_TRUE( s.cbegin() == s.cend());
406 // Force retiring cycle
407 Set::gc::force_dispose();
408 for ( auto& i : data ) {
409 EXPECT_EQ( i.nDisposeCount, 1u );
415 } // namespace cds_test
417 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_H