e4f24bb1b80fc10c253a117301be00cd96ff7215
[libcds.git] / test / stress / map / del3 / map_del3.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.
29 */
30
31 #include "map_type.h"
32 #include "../../misc/common.h"
33 #include <cds/os/topology.h>
34
35 namespace map {
36
37     namespace {
38         struct key_thread
39         {
40             uint32_t  nKey;
41             uint16_t  nThread;
42
43             key_thread( size_t key, size_t threadNo )
44                 : nKey( static_cast<uint32_t>(key))
45                 , nThread( static_cast<uint16_t>(threadNo))
46             {}
47
48             key_thread()
49                 : nKey()
50                 , nThread()
51             {}
52         };
53
54         static_assert(sizeof( key_thread ) % 8 == 0, "Key size mismatch!!!");
55     } // namespace
56
57     template <>
58     struct cmp<key_thread> {
59         int operator ()(key_thread const& k1, key_thread const& k2) const
60         {
61             if ( k1.nKey < k2.nKey )
62                 return -1;
63             if ( k1.nKey > k2.nKey )
64                 return 1;
65             if ( k1.nThread < k2.nThread )
66                 return -1;
67             if ( k1.nThread > k2.nThread )
68                 return 1;
69             return 0;
70         }
71         int operator ()(key_thread const& k1, size_t k2) const
72         {
73             if ( k1.nKey < k2 )
74                 return -1;
75             if ( k1.nKey > k2 )
76                 return 1;
77             return 0;
78         }
79         int operator ()(size_t k1, key_thread const& k2) const
80         {
81             if ( k1 < k2.nKey )
82                 return -1;
83             if ( k1 > k2.nKey )
84                 return 1;
85             return 0;
86         }
87     };
88
89     template <>
90     struct less<key_thread>
91     {
92         bool operator()( key_thread const& k1, key_thread const& k2 ) const
93         {
94             if ( k1.nKey <= k2.nKey )
95                 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
96             return false;
97         }
98     };
99
100     template <>
101     struct hash<key_thread>
102     {
103         typedef size_t             result_type;
104         typedef key_thread    argument_type;
105
106         size_t operator()( key_thread const& k ) const
107         {
108             return std::hash<size_t>()(k.nKey);
109         }
110         size_t operator()( size_t k ) const
111         {
112             return std::hash<size_t>()(k);
113         }
114     };
115
116     class Map_Del3: public cds_test::stress_fixture
117     {
118     public:
119         static size_t s_nInsThreadCount;      // insert thread count
120         static size_t s_nDelThreadCount;      // delete thread count
121         static size_t s_nExtractThreadCount;  // extract thread count
122         static size_t s_nMapSize;             // max map size
123         static size_t s_nMaxLoadFactor;       // maximum load factor
124         static size_t s_nInsertPassCount;
125         static size_t s_nFindThreadCount;     // find thread count
126
127         static size_t s_nCuckooInitialSize;       // initial size for CuckooMap
128         static size_t s_nCuckooProbesetSize;      // CuckooMap probeset size (only for list-based probeset)
129         static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
130
131         static size_t s_nFeldmanMap_HeadBits;
132         static size_t s_nFeldmanMap_ArrayBits;
133
134         static size_t  s_nLoadFactor;  // current load factor
135
136         static std::vector<size_t> m_arrElements;
137
138         static void SetUpTestCase();
139         static void TearDownTestCase();
140
141         template <typename Pred>
142         static void prepare_array( std::vector<size_t>& arr, Pred pred )
143         {
144             arr.reserve( m_arrElements.size());
145             for ( auto el : m_arrElements ) {
146                 if ( pred( el ))
147                     arr.push_back( el );
148             }
149             arr.resize( arr.size());
150             shuffle( arr.begin(), arr.end());
151         }
152
153     protected:
154         typedef key_thread  key_type;
155         typedef size_t      value_type;
156         typedef std::pair<key_type const, value_type> pair_type;
157
158         atomics::atomic<size_t> m_nInsThreadCount;
159
160         enum {
161             inserter_thread,
162             deleter_thread,
163             extractor_thread,
164             find_thread,
165         };
166
167         // Inserts keys from [0..N)
168         template <class Map>
169         class Inserter: public cds_test::thread
170         {
171             typedef cds_test::thread base_class;
172             Map&     m_Map;
173
174             struct update_func
175             {
176                 template <typename Q>
177                 void operator()( bool /*bNew*/, Q const& ) const
178                 {}
179
180                 template <typename Q, typename V>
181                 void operator()( bool /*bNew*/, Q const&, V& ) const
182                 {}
183
184                 // FeldmanHashMap
185                 template <typename Q>
186                 void operator()( Q&, Q*) const
187                 {}
188             };
189
190             void init_data()
191             {
192                 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
193                 for ( size_t i = 0; i < m_arr.size(); ++i ) {
194                     if ( m_Map.insert( key_type( m_arr[i], id())))
195                         ++m_nInsertInitSuccess;
196                     else
197                         ++m_nInsertInitFailed;
198                 }
199             }
200
201         public:
202             size_t m_nInsertSuccess = 0;
203             size_t m_nInsertFailed = 0;
204             size_t m_nInsertInitSuccess = 0;
205             size_t m_nInsertInitFailed = 0;
206
207             std::vector<size_t> m_arr;
208
209         public:
210             Inserter( cds_test::thread_pool& pool, Map& map )
211                 : base_class( pool, inserter_thread )
212                 , m_Map( map )
213             {
214                 init_data();
215             }
216
217             Inserter( Inserter& src )
218                 : base_class( src )
219                 , m_Map( src.m_Map )
220             {
221                 init_data();
222             }
223
224             virtual thread * clone()
225             {
226                 return new Inserter( *this );
227             }
228
229             virtual void test()
230             {
231                 Map& rMap = m_Map;
232                 Map_Del3& fixture = pool().template fixture<Map_Del3>();
233
234                 update_func f;
235
236                 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
237                     if ( nPass & 1 ) {
238                         // insert pass
239                         for ( auto el : m_arr ) {
240                             if ( el & 3 ) {
241                                 if ( rMap.insert( key_type( el, id())))
242                                     ++m_nInsertSuccess;
243                                 else
244                                     ++m_nInsertFailed;
245                             }
246                         }
247                     }
248                     else {
249                         // update pass
250                         for ( auto el : m_arr ) {
251                             if ( el & 3 ) {
252                                 bool success;
253                                 bool inserted;
254                                 std::tie( success, inserted ) = rMap.update( key_type( el, id()), f );
255                                 if ( success && inserted )
256                                     ++m_nInsertSuccess;
257                                 else
258                                     ++m_nInsertFailed;
259                             }
260                         }
261                     }
262                 }
263
264                 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
265                 m_arr.resize( 0 );
266             }
267         };
268
269         struct key_equal {
270             bool operator()( key_type const& k1, key_type const& k2 ) const
271             {
272                 return k1.nKey == k2.nKey;
273             }
274             bool operator()( size_t k1, key_type const& k2 ) const
275             {
276                 return k1 == k2.nKey;
277             }
278             bool operator()( key_type const& k1, size_t k2 ) const
279             {
280                 return k1.nKey == k2;
281             }
282         };
283
284         struct key_less {
285             bool operator()( key_type const& k1, key_type const& k2 ) const
286             {
287                 return k1.nKey < k2.nKey;
288             }
289             bool operator()( size_t k1, key_type const& k2 ) const
290             {
291                 return k1 < k2.nKey;
292             }
293             bool operator()( key_type const& k1, size_t k2 ) const
294             {
295                 return k1.nKey < k2;
296             }
297
298             typedef key_equal equal_to;
299         };
300
301         // Deletes odd keys from [0..N)
302         template <class Map>
303         class Deleter: public cds_test::thread
304         {
305             typedef cds_test::thread base_class;
306             Map&     m_Map;
307
308             void init_data()
309             {
310                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
311             }
312
313         public:
314             size_t  m_nDeleteSuccess = 0;
315             size_t  m_nDeleteFailed = 0;
316
317             std::vector<size_t> m_arr;
318
319         public:
320             Deleter( cds_test::thread_pool& pool, Map& map )
321                 : base_class( pool, deleter_thread )
322                 , m_Map( map )
323             {
324                 init_data();
325             }
326
327             Deleter( Deleter& src )
328                 : base_class( src )
329                 , m_Map( src.m_Map )
330             {
331                 init_data();
332             }
333
334             virtual thread * clone()
335             {
336                 return new Deleter( *this );
337             }
338
339             virtual void test()
340             {
341                 Map& rMap = m_Map;
342
343                 Map_Del3& fixture = pool().template fixture<Map_Del3>();
344                 size_t const nInsThreadCount = s_nInsThreadCount;
345
346                 do {
347                     if ( id() & 1 ) {
348                         for ( auto el: m_arr ) {
349                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
350                                 if ( rMap.erase( key_type( el, k )))
351                                     ++m_nDeleteSuccess;
352                                 else
353                                     ++m_nDeleteFailed;
354                             }
355                         }
356                     }
357                     else {
358                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
359                             for ( auto el: m_arr ) {
360                                 if ( rMap.erase( key_type( el, k )))
361                                     ++m_nDeleteSuccess;
362                                 else
363                                     ++m_nDeleteFailed;
364                             }
365                         }
366                     }
367                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
368
369                 m_arr.resize( 0 );
370             }
371         };
372
373         // Deletes odd keys from [0..N)
374         template <class GC, class Map >
375         class Extractor: public cds_test::thread
376         {
377             typedef cds_test::thread base_class;
378             Map&     m_Map;
379
380             void init_data()
381             {
382                 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
383             }
384
385         public:
386             size_t  m_nDeleteSuccess = 0;
387             size_t  m_nDeleteFailed = 0;
388
389             std::vector<size_t> m_arr;
390
391         public:
392             Extractor( cds_test::thread_pool& pool, Map& map )
393                 : base_class( pool, extractor_thread )
394                 , m_Map( map )
395             {
396                 init_data();
397             }
398
399             Extractor( Extractor& src )
400                 : base_class( src )
401                 , m_Map( src.m_Map )
402             {
403                 init_data();
404             }
405
406             virtual thread * clone()
407             {
408                 return new Extractor( *this );
409             }
410
411             virtual void test()
412             {
413                 Map& rMap = m_Map;
414
415                 typename Map::guarded_ptr gp;
416                 Map_Del3& fixture = pool().template fixture<Map_Del3>();
417                 size_t const nInsThreadCount = s_nInsThreadCount;
418
419                 do {
420                     if ( id() & 1 ) {
421                         for ( auto el : m_arr ) {
422                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
423                                 gp = rMap.extract( key_type( el, k ));
424                                 if ( gp )
425                                     ++m_nDeleteSuccess;
426                                 else
427                                     ++m_nDeleteFailed;
428                                 gp.release();
429                             }
430                         }
431                     }
432                     else {
433                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
434                             for ( auto el: m_arr ) {
435                                 gp = rMap.extract( key_type( el, k ));
436                                 if ( gp )
437                                     ++m_nDeleteSuccess;
438                                 else
439                                     ++m_nDeleteFailed;
440                                 gp.release();
441                             }
442                         }
443                     }
444                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
445
446                 m_arr.resize( 0 );
447             }
448         };
449
450         template <class RCU, class Map >
451         class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
452         {
453             typedef cds_test::thread base_class;
454             Map&     m_Map;
455
456             void init_data()
457             {
458                 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
459             }
460
461         public:
462             size_t  m_nDeleteSuccess = 0;
463             size_t  m_nDeleteFailed = 0;
464
465             std::vector<size_t> m_arr;
466
467         public:
468             Extractor( cds_test::thread_pool& pool, Map& map )
469                 : base_class( pool, extractor_thread )
470                 , m_Map( map )
471             {
472                 init_data();
473             }
474
475             Extractor( Extractor& src )
476                 : base_class( src )
477                 , m_Map( src.m_Map )
478             {
479                 init_data();
480             }
481
482             virtual thread * clone()
483             {
484                 return new Extractor( *this );
485             }
486
487             virtual void test()
488             {
489                 Map& rMap = m_Map;
490                 Map_Del3& fixture = pool().template fixture<Map_Del3>();
491
492                 typename Map::exempt_ptr xp;
493                 size_t const nInsThreadCount = s_nInsThreadCount;
494
495                 do {
496                     if ( id() & 1 ) {
497                         for ( size_t k = 0; k < nInsThreadCount; ++k ) {
498                             for ( auto el: m_arr ) {
499                                 if ( Map::c_bExtractLockExternal ) {
500                                     typename Map::rcu_lock l;
501                                     xp = rMap.extract( key_type( el, k ));
502                                     if ( xp )
503                                         ++m_nDeleteSuccess;
504                                     else
505                                         ++m_nDeleteFailed;
506                                 }
507                                 else {
508                                     xp = rMap.extract( key_type( el, k ));
509                                     if ( xp )
510                                         ++m_nDeleteSuccess;
511                                     else
512                                         ++m_nDeleteFailed;
513                                 }
514                                 xp.release();
515                             }
516                         }
517                     }
518                     else {
519                         for ( auto el : m_arr ) {
520                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
521                                 if ( Map::c_bExtractLockExternal ) {
522                                     typename Map::rcu_lock l;
523                                     xp = rMap.extract( key_type( el, k ));
524                                     if ( xp )
525                                         ++m_nDeleteSuccess;
526                                     else
527                                         ++m_nDeleteFailed;
528                                 }
529                                 else {
530                                     xp = rMap.extract( key_type( el, k ));
531                                     if ( xp )
532                                         ++m_nDeleteSuccess;
533                                     else
534                                         ++m_nDeleteFailed;
535                                 }
536                                 xp.release();
537                             }
538                         }
539                     }
540                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
541
542                 m_arr.resize( 0 );
543             }
544         };
545
546         // Finds keys
547         template <class Map>
548         class Observer: public cds_test::thread
549         {
550             typedef cds_test::thread base_class;
551             Map&                m_Map;
552
553         public:
554             size_t m_nFindEvenSuccess = 0;
555             size_t m_nFindEvenFailed  = 0;
556             size_t m_nFindOddSuccess  = 0;
557             size_t m_nFindOddFailed   = 0;
558
559         public:
560             Observer( cds_test::thread_pool& pool, Map& map )
561                 : base_class( pool, find_thread )
562                 , m_Map( map )
563             {}
564
565             Observer( Observer& src )
566                 : base_class( src )
567                 , m_Map( src.m_Map )
568             {}
569
570             virtual thread * clone()
571             {
572                 return new Observer( *this );
573             }
574
575             virtual void test()
576             {
577                 Map& map = m_Map;
578                 Map_Del3& fixture = pool().template fixture<Map_Del3>();
579                 std::vector<size_t> const& arr = m_arrElements;
580                 size_t const nInsThreadCount = s_nInsThreadCount;
581
582                 do {
583                     for ( size_t key : arr ) {
584                         if ( key & 3 ) {
585                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
586                                 if ( map.contains( key_thread( key, k )))
587                                     ++m_nFindOddSuccess;
588                                 else
589                                     ++m_nFindOddFailed;
590                             }
591                         }
592                         else {
593                             // even keys MUST be in the map
594                             for ( size_t k = 0; k < nInsThreadCount; ++k ) {
595                                 if ( map.contains( key_thread( key, k )))
596                                     ++m_nFindEvenSuccess;
597                                 else
598                                     ++m_nFindEvenFailed;
599                             }
600                         }
601                     }
602                 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
603             }
604         };
605
606     protected:
607         template <class Map>
608         void do_test( Map& testMap )
609         {
610             typedef Inserter<Map> insert_thread;
611             typedef Deleter<Map>  delete_thread;
612             typedef Observer<Map> observer_thread;
613
614             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
615
616             cds_test::thread_pool& pool = get_pool();
617             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
618             pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
619             if ( s_nFindThreadCount )
620                 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
621
622             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
623                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
624                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
625                 << std::make_pair( "map_size", s_nMapSize )
626                 << std::make_pair( "pass_count", s_nInsertPassCount );
627
628             std::chrono::milliseconds duration = pool.run();
629
630             propout() << std::make_pair( "duration", duration );
631
632             size_t nInsertInitFailed = 0;
633             size_t nInsertInitSuccess = 0;
634             size_t nInsertSuccess = 0;
635             size_t nInsertFailed = 0;
636             size_t nDeleteSuccess = 0;
637             size_t nDeleteFailed = 0;
638
639             size_t nFindEvenSuccess = 0;
640             size_t nFindEvenFailed = 0;
641             size_t nFindOddSuccess = 0;
642             size_t nFindOddFailed = 0;
643
644             for ( size_t i = 0; i < pool.size(); ++i ) {
645                 cds_test::thread& thr = pool.get( i );
646                 switch ( thr.type()) {
647                 case inserter_thread:
648                     {
649                         insert_thread& inserter = static_cast<insert_thread&>( thr );
650                         nInsertSuccess += inserter.m_nInsertSuccess;
651                         nInsertFailed += inserter.m_nInsertFailed;
652                         nInsertInitSuccess += inserter.m_nInsertInitSuccess;
653                         nInsertInitFailed += inserter.m_nInsertInitFailed;
654                     }
655                     break;
656                 case deleter_thread:
657                     {
658                         delete_thread& deleter = static_cast<delete_thread&>( thr );
659                         nDeleteSuccess += deleter.m_nDeleteSuccess;
660                         nDeleteFailed += deleter.m_nDeleteFailed;
661                     }
662                     break;
663                 case find_thread:
664                     {
665                         observer_thread& observer = static_cast<observer_thread&>( thr );
666                         nFindEvenSuccess = observer.m_nFindEvenSuccess;
667                         nFindEvenFailed = observer.m_nFindEvenFailed;
668                         nFindOddSuccess = observer.m_nFindOddSuccess;
669                         nFindOddFailed = observer.m_nFindOddFailed;
670                     }
671                     break;
672                 }
673             }
674
675             size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
676
677             EXPECT_EQ( nInsertInitFailed, 0u );
678             EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
679             EXPECT_EQ( nFindEvenFailed, 0u );
680             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
681             EXPECT_LE( nInsertSuccess, nDeleteSuccess );
682
683             propout()
684                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
685                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
686                 << std::make_pair( "insert_success", nInsertSuccess )
687                 << std::make_pair( "insert_failed", nInsertFailed )
688                 << std::make_pair( "delete_success", nDeleteSuccess )
689                 << std::make_pair( "delete_failed", nDeleteFailed )
690                 << std::make_pair( "find_even_success", nFindEvenSuccess )
691                 << std::make_pair( "find_even_failed", nFindEvenFailed )
692                 << std::make_pair( "find_odd_success", nFindOddSuccess )
693                 << std::make_pair( "find_odd_failed", nFindOddFailed );
694
695             DEBUG(analyze( testMap ));
696         }
697
698         template <class Map>
699         void do_test_extract( Map& testMap )
700         {
701             typedef Inserter<Map> insert_thread;
702             typedef Deleter<Map> delete_thread;
703             typedef Extractor< typename Map::gc, Map > extract_thread;
704             typedef Observer<Map> observer_thread;
705
706             m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
707
708             cds_test::thread_pool& pool = get_pool();
709             pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
710             if ( s_nDelThreadCount )
711                 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
712             if ( s_nExtractThreadCount )
713                 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
714             if ( s_nFindThreadCount )
715                 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
716
717             propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
718                 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
719                 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
720                 << std::make_pair( "find_thread_count", s_nFindThreadCount )
721                 << std::make_pair( "map_size", s_nMapSize )
722                 << std::make_pair( "pass_count", s_nInsertPassCount );
723
724             std::chrono::milliseconds duration = pool.run();
725
726             propout() << std::make_pair( "duration", duration );
727
728             size_t nInsertInitFailed = 0;
729             size_t nInsertInitSuccess = 0;
730             size_t nInsertSuccess = 0;
731             size_t nInsertFailed = 0;
732             size_t nDeleteSuccess = 0;
733             size_t nDeleteFailed = 0;
734             size_t nExtractSuccess = 0;
735             size_t nExtractFailed = 0;
736
737             size_t nFindEvenSuccess = 0;
738             size_t nFindEvenFailed = 0;
739             size_t nFindOddSuccess = 0;
740             size_t nFindOddFailed = 0;
741
742             for ( size_t i = 0; i < pool.size(); ++i ) {
743                 cds_test::thread& thr = pool.get( i );
744                 switch ( thr.type()) {
745                 case inserter_thread:
746                 {
747                     insert_thread& inserter = static_cast<insert_thread&>(thr);
748                     nInsertSuccess += inserter.m_nInsertSuccess;
749                     nInsertFailed += inserter.m_nInsertFailed;
750                     nInsertInitSuccess += inserter.m_nInsertInitSuccess;
751                     nInsertInitFailed += inserter.m_nInsertInitFailed;
752                 }
753                 break;
754                 case deleter_thread:
755                 {
756                     delete_thread& deleter = static_cast<delete_thread&>(thr);
757                     nDeleteSuccess += deleter.m_nDeleteSuccess;
758                     nDeleteFailed += deleter.m_nDeleteFailed;
759                 }
760                 break;
761                 case extractor_thread:
762                 {
763                     extract_thread& extractor = static_cast<extract_thread&>(thr);
764                     nExtractSuccess += extractor.m_nDeleteSuccess;
765                     nExtractFailed += extractor.m_nDeleteFailed;
766                 }
767                 break;
768                 case find_thread:
769                 {
770                     observer_thread& observer = static_cast<observer_thread&>( thr );
771                     nFindEvenSuccess = observer.m_nFindEvenSuccess;
772                     nFindEvenFailed = observer.m_nFindEvenFailed;
773                     nFindOddSuccess = observer.m_nFindOddSuccess;
774                     nFindOddFailed = observer.m_nFindOddFailed;
775                 }
776                 break;
777                 default:
778                     assert( false );
779                 }
780             }
781
782             size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
783
784             EXPECT_EQ( nInsertInitFailed, 0u );
785             EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
786             EXPECT_EQ( nFindEvenFailed, 0u );
787             EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
788             EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
789
790             propout()
791                 << std::make_pair( "insert_init_success", nInsertInitSuccess )
792                 << std::make_pair( "insert_init_failed", nInsertInitFailed )
793                 << std::make_pair( "insert_success", nInsertSuccess )
794                 << std::make_pair( "insert_failed", nInsertFailed )
795                 << std::make_pair( "delete_success", nDeleteSuccess )
796                 << std::make_pair( "delete_failed", nDeleteFailed )
797                 << std::make_pair( "extract_success", nExtractSuccess )
798                 << std::make_pair( "extract_failed", nExtractFailed )
799                 << std::make_pair( "find_even_success", nFindEvenSuccess )
800                 << std::make_pair( "find_even_failed", nFindEvenFailed )
801                 << std::make_pair( "find_odd_success", nFindOddSuccess )
802                 << std::make_pair( "find_odd_failed", nFindOddFailed );
803
804             DEBUG(analyze( testMap ));
805         }
806
807         template <class Map>
808         void analyze( Map& testMap )
809         {
810             // All even keys must be in the map
811             {
812                 for ( size_t n = 0; n < s_nMapSize; n +=4 ) {
813                     for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
814                         EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
815                     }
816                 }
817             }
818
819             print_stat( propout(), testMap );
820
821             check_before_cleanup( testMap );
822             testMap.clear();
823             EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
824
825             additional_check( testMap );
826             additional_cleanup( testMap );
827         }
828
829         template <class Map>
830         void run_test_extract()
831         {
832             static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
833
834             size_t nMapSize = s_nMapSize;
835             s_nMapSize *= s_nInsThreadCount;
836
837             Map testMap( *this );
838
839             s_nMapSize = nMapSize;
840             do_test_extract( testMap );
841         }
842
843         template <class Map>
844         void run_test()
845         {
846             size_t nMapSize = s_nMapSize;
847             s_nMapSize *= s_nInsThreadCount;
848
849             Map testMap( *this );
850
851             s_nMapSize = nMapSize;
852             do_test( testMap );
853         }
854
855         template <class Map>
856         void run_feldman();
857     };
858
859     class Map_Del3_LF: public Map_Del3
860         , public ::testing::WithParamInterface<size_t>
861     {
862     public:
863         template <class Map>
864         void run_test()
865         {
866             s_nLoadFactor = GetParam();
867             propout() << std::make_pair( "load_factor", s_nLoadFactor );
868             Map_Del3::run_test<Map>();
869         }
870
871         template <class Map>
872         void run_test_extract()
873         {
874             s_nLoadFactor = GetParam();
875             propout() << std::make_pair( "load_factor", s_nLoadFactor );
876             Map_Del3::run_test_extract<Map>();
877         }
878
879         static std::vector<size_t> get_load_factors();
880     };
881
882 } // namespace map