tests/test-hdr/set/hdr_intrusive_cuckoo_set.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-2016
   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 #ifndef CDSTEST_HDR_INTRUSIVE_CUCKOO_SET_H
  32 #define CDSTEST_HDR_INTRUSIVE_CUCKOO_SET_H
  33
  34 #include "cppunit/cppunit_proxy.h"
  35 #include <cds/opt/hash.h>
  36
  37 // cds::intrusive namespace forward declaration
  38 namespace cds { namespace intrusive {}}
  39
  40 namespace set {
  41     namespace ci = cds::intrusive;
  42     namespace co = cds::opt;
  43
  44     // MichaelHashSet
  45     class IntrusiveCuckooSetHdrTest: public CppUnitMini::TestCase
  46     {
  47     public:
  48         struct stat
  49         {
  50             unsigned int nDisposeCount  ;   // count of disposer calling
  51             unsigned int nFindCount     ;   // count of find-functor calling
  52             unsigned int nFindArgCount;
  53             unsigned int nInsertCount;
  54             unsigned int nEnsureNewCount;
  55             unsigned int nEnsureCount;
  56             unsigned int nEraseCount;
  57
  58             stat()
  59             {
  60                 memset( this, 0, sizeof(*this));
  61             }
  62
  63             stat& operator=( stat const& s)
  64             {
  65                 memcpy( this, &s, sizeof(*this));
  66                 return *this;
  67             }
  68         };
  69
  70         struct item
  71         {
  72             int nKey;
  73             int nVal;
  74
  75             item()
  76             {}
  77
  78             item(int key, int val)
  79                 : nKey( key )
  80                 , nVal(val)
  81             {}
  82
  83             item(const item& v )
  84                 : nKey( v.nKey )
  85                 , nVal( v.nVal )
  86             {}
  87
  88             int key() const
  89             {
  90                 return nKey;
  91             }
  92
  93             int val() const
  94             {
  95                 return nVal;
  96             }
  97         };
  98
  99         template <typename Hook>
 100         struct base_item
 101             : public item
 102             , public Hook
 103             , public stat
 104
 105         {
 106             base_item()
 107             {}
 108
 109             base_item(int key, int val)
 110                 : item( key, val )
 111             {}
 112
 113             base_item(const base_item& v )
 114                 : item( static_cast<item const&>(v) )
 115                 , stat()
 116             {}
 117         };
 118
 119         template <typename Hook>
 120         struct member_item
 121             : public item
 122             , public stat
 123         {
 124             Hook hMember;
 125
 126             member_item()
 127             {}
 128
 129             member_item(int key, int val)
 130                 : item( key, val )
 131             {}
 132
 133             member_item(const member_item& v )
 134                 : item( static_cast<item const&>(v))
 135                 , stat()
 136             {}
 137         };
 138
 139         struct find_key {
 140             int nKey;
 141
 142             find_key( int key )
 143                 : nKey(key)
 144             {}
 145         };
 146
 147         struct hash_int {
 148             size_t operator()( int i ) const
 149             {
 150                 return co::v::hash<int>()( i );
 151             }
 152             template <typename Item>
 153             size_t operator()( const Item& i ) const
 154             {
 155                 return (*this)( i.key() );
 156             }
 157             size_t operator()( find_key const& i) const
 158             {
 159                 return co::v::hash<int>()( i.nKey );
 160             }
 161         };
 162
 163         template <typename T>
 164         struct less
 165         {
 166             bool operator ()(const T& v1, const T& v2 ) const
 167             {
 168                 return v1.key() < v2.key();
 169             }
 170
 171             template <typename Q>
 172             bool operator ()(const T& v1, const Q& v2 ) const
 173             {
 174                 return v1.key() < v2;
 175             }
 176
 177             template <typename Q>
 178             bool operator ()(const Q& v1, const T& v2 ) const
 179             {
 180                 return v1 < v2.key();
 181             }
 182         };
 183
 184         template <typename T>
 185         struct cmp {
 186             int operator ()(const T& v1, const T& v2 ) const
 187             {
 188                 if ( v1.key() < v2.key() )
 189                     return -1;
 190                 return v1.key() > v2.key() ? 1 : 0;
 191             }
 192
 193             template <typename Q>
 194             int operator ()(const T& v1, const Q& v2 ) const
 195             {
 196                 if ( v1.key() < v2 )
 197                     return -1;
 198                 return v1.key() > v2 ? 1 : 0;
 199             }
 200
 201             template <typename Q>
 202             int operator ()(const Q& v1, const T& v2 ) const
 203             {
 204                 if ( v1 < v2.key() )
 205                     return -1;
 206                 return v1 > v2.key() ? 1 : 0;
 207             }
 208         };
 209
 210         struct faked_disposer
 211         {
 212             template <typename T>
 213             void operator ()( T * p )
 214             {
 215                 ++p->nDisposeCount;
 216             }
 217         };
 218
 219         struct insert_functor {
 220             template <typename Item>
 221             void operator()( Item& e)
 222             {
 223                 ++e.nInsertCount;
 224             }
 225         };
 226
 227         struct update_functor {
 228             template <typename Item>
 229             void operator()( bool bNew, Item& e, Item& arg )
 230             {
 231                 if ( bNew ) {
 232                     ++e.nEnsureNewCount;
 233                     CPPUNIT_ASSERT_CURRENT( &e == &arg );
 234                 }
 235                 else
 236                     ++e.nEnsureCount;
 237             }
 238         };
 239
 240         struct erase_functor {
 241             template< typename Item >
 242             void operator()( Item& e )
 243             {
 244                 ++e.nEraseCount;
 245             }
 246         };
 247
 248         struct find_functor {
 249             template <typename Item, typename What>
 250             void operator()( Item& e, What& )
 251             {
 252                 ++e.nFindCount;
 253             }
 254
 255             template <typename Item>
 256             void operator()( Item& e, Item& w )
 257             {
 258                 ++e.nFindCount;
 259                 ++w.nFindArgCount;
 260             }
 261         };
 262
 263         struct less2 {
 264             template <typename Item>
 265             bool operator()( Item const& e, find_key const& k ) const
 266             {
 267                 return e.key() < k.nKey;
 268             }
 269             template <typename Item>
 270             bool operator()( find_key const& k, Item const& e ) const
 271             {
 272                 return k.nKey < e.key();
 273             }
 274             template <typename Item>
 275             bool operator()( Item const& e, int k ) const
 276             {
 277                 return e.key() < k;
 278             }
 279             template <typename Item>
 280             bool operator()( int k, Item const& e ) const
 281             {
 282                 return k < e.key();
 283             }
 284         };
 285
 286         struct equal_to2 {
 287             template <typename Item>
 288             bool operator()( Item const& e, find_key const& k ) const
 289             {
 290                 return e.key() == k.nKey;
 291             }
 292             template <typename Item>
 293             bool operator()( find_key const& k, Item const& e ) const
 294             {
 295                 return k.nKey == e.key();
 296             }
 297             template <typename Item>
 298             bool operator()( Item const& e, int k ) const
 299             {
 300                 return e.key() == k;
 301             }
 302             template <typename Item>
 303             bool operator()( int k, Item const& e ) const
 304             {
 305                 return k == e.key();
 306             }
 307         };
 308
 309         template <typename T>
 310         struct auto_dispose {
 311             T * m_pArr;
 312             auto_dispose( T * pArr ): m_pArr( pArr ) {}
 313             ~auto_dispose() { delete[] m_pArr; }
 314         };
 315
 316         template <class Set>
 317         void test_with(Set& s)
 318         {
 319             typedef typename Set::value_type    value_type;
 320
 321             int const k1 = 10;
 322             int const k2 = 25;
 323             int const k3 = 51;
 324
 325             int const v1 = 25;
 326             int const v2 = 56;
 327             int const v3 = 23;
 328
 329             value_type e1( k1, v1 );
 330             value_type e2( k2, v2 );
 331             value_type e3( k3, v3);
 332
 333             stat s1 = e1;
 334             stat s2 = e2;
 335             stat s3 = e3;
 336
 337             CPPUNIT_ASSERT( s.empty() );
 338             CPPUNIT_ASSERT( s.size() == 0 );
 339
 340             CPPUNIT_ASSERT( !s.contains(k1));
 341             CPPUNIT_ASSERT( !s.contains(k2, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type() ));
 342             CPPUNIT_ASSERT( !s.contains(k3));
 343
 344             CPPUNIT_ASSERT( s.insert(e1));
 345             CPPUNIT_ASSERT( s.contains(e1));
 346             CPPUNIT_ASSERT( s.contains(k1));
 347             CPPUNIT_ASSERT( s.contains(k1, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type()));
 348             CPPUNIT_ASSERT( !s.contains(e2));
 349             CPPUNIT_ASSERT( !s.contains(e3));
 350
 351             CPPUNIT_ASSERT( e2.nInsertCount == 0 );
 352             CPPUNIT_ASSERT( s.insert(e2, insert_functor() ));
 353             CPPUNIT_ASSERT( e2.nInsertCount == 1 );
 354             CPPUNIT_ASSERT( s.find(e1, find_functor() ));
 355             CPPUNIT_ASSERT( e1.nFindCount == 1 );
 356             CPPUNIT_ASSERT( e1.nFindArgCount == 1 );
 357             CPPUNIT_ASSERT( s.find(k1, find_functor() ));
 358             CPPUNIT_ASSERT( e1.nFindCount == 2 );
 359             CPPUNIT_ASSERT( e1.nFindArgCount == 1 );
 360             CPPUNIT_ASSERT( s.find_with(k2, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type(), find_functor() ));
 361             CPPUNIT_ASSERT( e2.nFindCount == 1 );
 362             CPPUNIT_ASSERT( e2.nFindArgCount == 0 );
 363             CPPUNIT_ASSERT( s.find(e2, find_functor() ));
 364             CPPUNIT_ASSERT( e2.nFindCount == 2 );
 365             CPPUNIT_ASSERT( e2.nFindArgCount == 1 );
 366             CPPUNIT_ASSERT( !s.find(k3, find_functor()));
 367             CPPUNIT_ASSERT( e3.nFindCount == 0 );
 368             CPPUNIT_ASSERT( e3.nFindArgCount == 0 );
 369             CPPUNIT_ASSERT( !s.find(e3, find_functor()));
 370             CPPUNIT_ASSERT( e3.nFindCount == 0 );
 371             CPPUNIT_ASSERT( e3.nFindArgCount == 0 );
 372
 373             s1 = e1 ; s2 = e2 ; s3 = e3;
 374
 375             CPPUNIT_ASSERT( e3.nEnsureNewCount == 0 );
 376             CPPUNIT_ASSERT( e3.nEnsureCount == 0 );
 377             CPPUNIT_ASSERT(s.update(e3, update_functor(), false) == std::make_pair(false, false));
 378             CPPUNIT_ASSERT(e3.nEnsureNewCount == 0);
 379             CPPUNIT_ASSERT(e3.nEnsureCount == 0);
 380             CPPUNIT_ASSERT( s.update( e3, update_functor() ) == std::make_pair(true, true));
 381             CPPUNIT_ASSERT( e3.nEnsureNewCount == 1 );
 382             CPPUNIT_ASSERT( e3.nEnsureCount == 0 );
 383             CPPUNIT_ASSERT( s.find_with(find_key(k1), typename std::conditional<Set::c_isSorted, less2, equal_to2>::type(), find_functor() ));
 384             CPPUNIT_ASSERT( e1.nFindCount == s1.nFindCount + 1 );
 385             CPPUNIT_ASSERT( e1.nFindArgCount == s1.nFindArgCount );
 386             CPPUNIT_ASSERT( s.find_with(k1, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type(), find_functor() ));
 387             CPPUNIT_ASSERT( e1.nFindCount == s1.nFindCount + 2 );
 388             CPPUNIT_ASSERT( e1.nFindArgCount == s1.nFindArgCount );
 389             CPPUNIT_ASSERT( s.find_with(k2, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type(), find_functor() ));
 390             CPPUNIT_ASSERT( e2.nFindCount == s2.nFindCount + 1 );
 391             CPPUNIT_ASSERT( e2.nFindArgCount == s2.nFindArgCount );
 392             CPPUNIT_ASSERT( s.contains(find_key(k2), typename std::conditional<Set::c_isSorted, less2, equal_to2>::type() ));
 393             CPPUNIT_ASSERT( e2.nFindCount == s2.nFindCount + 1 )        ;   // unchanged, no find_functor
 394             CPPUNIT_ASSERT( e2.nFindArgCount == s2.nFindArgCount );
 395             CPPUNIT_ASSERT( s.contains(k3, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type() ));
 396             CPPUNIT_ASSERT( e3.nFindCount == s3.nFindCount )            ;   // unchanged, no find_functor
 397             CPPUNIT_ASSERT( e3.nFindArgCount == s3.nFindArgCount );
 398             CPPUNIT_ASSERT( s.find_with(find_key(k3), typename std::conditional<Set::c_isSorted, less2, equal_to2>::type(), find_functor() ));
 399             CPPUNIT_ASSERT( e3.nFindCount == s3.nFindCount + 1 );
 400             CPPUNIT_ASSERT( e3.nFindArgCount == s3.nFindArgCount );
 401
 402             s1 = e1 ; s2 = e2 ; s3 = e3;
 403
 404             // insert existing elements
 405             {
 406                 value_type eu( k2, 1000 );
 407                 CPPUNIT_ASSERT( !s.insert( eu ));
 408                 CPPUNIT_ASSERT( !s.insert( eu, insert_functor() ));
 409                 CPPUNIT_ASSERT( e2.nInsertCount == s2.nInsertCount );
 410
 411                 CPPUNIT_ASSERT( s.update( eu, update_functor()) == std::make_pair(true, false));
 412                 CPPUNIT_ASSERT( e2.nInsertCount == s2.nInsertCount );
 413                 CPPUNIT_ASSERT( e2.nEnsureCount == s2.nEnsureCount + 1 );
 414                 CPPUNIT_ASSERT( e2.nEnsureNewCount == s2.nEnsureNewCount  );
 415             }
 416
 417             s1 = e1 ; s2 = e2 ; s3 = e3;
 418
 419             // unlink & erase test
 420             {
 421                 value_type eu( k2, 10 );
 422                 CPPUNIT_ASSERT( !s.unlink(eu));
 423             }
 424
 425             CPPUNIT_ASSERT( !s.empty() );
 426             CPPUNIT_ASSERT( s.size() == 3 );
 427
 428             CPPUNIT_ASSERT( s.unlink( e1 ) );
 429             CPPUNIT_ASSERT( s.erase_with( k2, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type() ) == &e2 );
 430             CPPUNIT_ASSERT( s.erase( e2 ) == nullptr );
 431             CPPUNIT_ASSERT( e3.nEraseCount == 0 );
 432             CPPUNIT_ASSERT( s.erase_with( k3, typename std::conditional<Set::c_isSorted, less2, equal_to2>::type(), erase_functor()) == &e3 );
 433             CPPUNIT_ASSERT( e3.nEraseCount == 1 );
 434             CPPUNIT_ASSERT( s.erase( k3, erase_functor() ) == nullptr );
 435             CPPUNIT_ASSERT( e3.nEraseCount == 1 );
 436
 437             CPPUNIT_ASSERT( s.insert( e3 ) );
 438             CPPUNIT_ASSERT( s.erase( e3 ) == &e3 );
 439             CPPUNIT_ASSERT( e3.nEraseCount == 1 );
 440
 441             CPPUNIT_ASSERT( s.empty() );
 442             CPPUNIT_ASSERT( s.size() == 0 );
 443
 444             s1 = e1 ; s2 = e2 ; s3 = e3;
 445
 446             // clear & clear_and_dispose test
 447             CPPUNIT_ASSERT( s.insert(e1));
 448             CPPUNIT_ASSERT( s.insert(e2));
 449             CPPUNIT_ASSERT( s.insert(e3));
 450             CPPUNIT_ASSERT( !s.empty() );
 451             CPPUNIT_ASSERT( s.size() == 3 );
 452             s.clear();
 453             CPPUNIT_ASSERT( s.empty() );
 454             CPPUNIT_ASSERT( s.size() == 0 );
 455
 456             CPPUNIT_ASSERT( s.insert(e1));
 457             CPPUNIT_ASSERT( s.insert(e2));
 458             CPPUNIT_ASSERT( s.insert(e3));
 459             CPPUNIT_ASSERT( !s.empty() );
 460             CPPUNIT_ASSERT( s.size() == 3 );
 461
 462             CPPUNIT_ASSERT( e1.nDisposeCount == 0 );
 463             CPPUNIT_ASSERT( e2.nDisposeCount == 0 );
 464             CPPUNIT_ASSERT( e3.nDisposeCount == 0 );
 465             s.clear_and_dispose( faked_disposer() );
 466             CPPUNIT_ASSERT( e1.nDisposeCount == 1 );
 467             CPPUNIT_ASSERT( e2.nDisposeCount == 1 );
 468             CPPUNIT_ASSERT( e3.nDisposeCount == 1 );
 469             CPPUNIT_ASSERT( s.empty() );
 470             CPPUNIT_ASSERT( s.size() == 0 );
 471
 472             // resize test (up to 64K elements)
 473             size_t const nSize = 64 * 1024;
 474             value_type * arr = new value_type[nSize];
 475             auto_dispose<value_type> ad(arr);
 476             for ( size_t i = 0; i < nSize; ++i ) {
 477                 value_type * p = new (arr + i) value_type( (int) i, (int) i * 2 );
 478                 CPPUNIT_ASSERT_EX( s.insert( *p, insert_functor() ), "i=" << i );
 479                 CPPUNIT_ASSERT_EX( p->nInsertCount == 1, "i=" << i );
 480                 //for ( size_t j = 0; j <= i; ++j ) {
 481                 //    if ( !s.contains((int) j) ) {
 482                 //        CPPUNIT_MSG( "Key " << j << " is not found after inserting key " << i );
 483                 //    }
 484                 //}
 485             }
 486
 487             for ( size_t i = 0; i < nSize; ++i )
 488                 CPPUNIT_ASSERT_EX( s.contains((int) i), "Key " << i << " is not found" );
 489
 490             CPPUNIT_ASSERT( !s.empty() );
 491             CPPUNIT_ASSERT( s.size() == nSize );
 492             s.clear_and_dispose( faked_disposer() );
 493             for ( size_t i = 0; i < nSize; ++i ) {
 494                 CPPUNIT_ASSERT_EX( arr[i].nDisposeCount == 1, "i=" << i );
 495             }
 496         }
 497
 498         template <class Set>
 499         void test()
 500         {
 501             // default ctor
 502             {
 503                 Set s;
 504                 test_with(s);
 505             }
 506
 507             // ctor with explicit initial capacity
 508             {
 509                 Set s(256);
 510                 test_with(s);
 511             }
 512         }
 513
 514         template <class Set>
 515         void test_cuckoo()
 516         {
 517             unsigned int nProbesetSize = Set::node_type::probeset_size ? Set::node_type::probeset_size : 4;
 518             Set s( 256, nProbesetSize, nProbesetSize / 2 );
 519             test_with( s );
 520         }
 521
 522         // ***********************************************************
 523         // Cuckoo hashing (striped)
 524
 525         void Cuckoo_striped_list_basehook_equal();
 526         void Cuckoo_striped_vector_basehook_equal();
 527         void Cuckoo_striped_list_basehook_sort_cmp();
 528         void Cuckoo_striped_vector_basehook_sort_cmp();
 529         void Cuckoo_striped_list_basehook_sort_less();
 530         void Cuckoo_striped_vector_basehook_sort_less();
 531         void Cuckoo_striped_list_basehook_sort_cmpmix();
 532         void Cuckoo_striped_vector_basehook_sort_cmpmix();
 533         void Cuckoo_striped_vector_basehook_sort_cmpmix_stat();
 534
 535         void Cuckoo_striped_list_basehook_equal_storehash();
 536         void Cuckoo_striped_vector_basehook_equal_storehash();
 537         void Cuckoo_striped_list_basehook_sort_cmp_storehash();
 538         void Cuckoo_striped_vector_basehook_sort_cmp_storehash();
 539         void Cuckoo_striped_list_basehook_sort_less_storehash();
 540         void Cuckoo_striped_vector_basehook_sort_less_storehash();
 541         void Cuckoo_striped_list_basehook_sort_cmpmix_storehash();
 542         void Cuckoo_striped_vector_basehook_sort_cmpmix_storehash();
 543
 544         void Cuckoo_striped_list_memberhook_equal();
 545         void Cuckoo_striped_vector_memberhook_equal();
 546         void Cuckoo_striped_list_memberhook_sort_cmp();
 547         void Cuckoo_striped_vector_memberhook_sort_cmp();
 548         void Cuckoo_striped_list_memberhook_sort_less();
 549         void Cuckoo_striped_vector_memberhook_sort_less();
 550         void Cuckoo_striped_list_memberhook_sort_cmpmix();
 551         void Cuckoo_striped_vector_memberhook_sort_cmpmix();
 552
 553         void Cuckoo_striped_list_memberhook_equal_storehash();
 554         void Cuckoo_striped_vector_memberhook_equal_storehash();
 555         void Cuckoo_striped_list_memberhook_sort_cmp_storehash();
 556         void Cuckoo_striped_vector_memberhook_sort_cmp_storehash();
 557         void Cuckoo_striped_list_memberhook_sort_less_storehash();
 558         void Cuckoo_striped_vector_memberhook_sort_less_storehash();
 559         void Cuckoo_striped_list_memberhook_sort_cmpmix_storehash();
 560         void Cuckoo_striped_vector_memberhook_sort_cmpmix_storehash();
 561
 562         // ***********************************************************
 563         // Cuckoo hashing (refinable)
 564
 565         void Cuckoo_refinable_list_basehook_equal();
 566         void Cuckoo_refinable_vector_basehook_equal();
 567         void Cuckoo_refinable_list_basehook_sort_cmp();
 568         void Cuckoo_refinable_vector_basehook_sort_cmp();
 569         void Cuckoo_refinable_list_basehook_sort_less();
 570         void Cuckoo_refinable_vector_basehook_sort_less();
 571         void Cuckoo_refinable_list_basehook_sort_cmpmix();
 572         void Cuckoo_refinable_vector_basehook_sort_cmpmix();
 573         void Cuckoo_refinable_vector_basehook_sort_cmpmix_stat();
 574
 575         void Cuckoo_refinable_list_basehook_equal_storehash();
 576         void Cuckoo_refinable_vector_basehook_equal_storehash();
 577         void Cuckoo_refinable_list_basehook_sort_cmp_storehash();
 578         void Cuckoo_refinable_vector_basehook_sort_cmp_storehash();
 579         void Cuckoo_refinable_list_basehook_sort_less_storehash();
 580         void Cuckoo_refinable_vector_basehook_sort_less_storehash();
 581         void Cuckoo_refinable_list_basehook_sort_cmpmix_storehash();
 582         void Cuckoo_refinable_vector_basehook_sort_cmpmix_storehash();
 583
 584         void Cuckoo_refinable_list_memberhook_equal();
 585         void Cuckoo_refinable_vector_memberhook_equal();
 586         void Cuckoo_refinable_list_memberhook_sort_cmp();
 587         void Cuckoo_refinable_vector_memberhook_sort_cmp();
 588         void Cuckoo_refinable_list_memberhook_sort_less();
 589         void Cuckoo_refinable_vector_memberhook_sort_less();
 590         void Cuckoo_refinable_list_memberhook_sort_cmpmix();
 591         void Cuckoo_refinable_vector_memberhook_sort_cmpmix();
 592
 593         void Cuckoo_refinable_list_memberhook_equal_storehash();
 594         void Cuckoo_refinable_vector_memberhook_equal_storehash();
 595         void Cuckoo_refinable_list_memberhook_sort_cmp_storehash();
 596         void Cuckoo_refinable_vector_memberhook_sort_cmp_storehash();
 597         void Cuckoo_refinable_list_memberhook_sort_less_storehash();
 598         void Cuckoo_refinable_vector_memberhook_sort_less_storehash();
 599         void Cuckoo_refinable_list_memberhook_sort_cmpmix_storehash();
 600         void Cuckoo_refinable_vector_memberhook_sort_cmpmix_storehash();
 601
 602         CPPUNIT_TEST_SUITE(IntrusiveCuckooSetHdrTest)
 603             // ***********************************************************
 604             // Cuckoo hashing (striped)
 605
 606             CPPUNIT_TEST( Cuckoo_striped_list_basehook_equal)
 607             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_equal)
 608             CPPUNIT_TEST( Cuckoo_striped_list_basehook_sort_cmp)
 609             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_cmp)
 610             CPPUNIT_TEST( Cuckoo_striped_list_basehook_sort_less)
 611             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_less)
 612             CPPUNIT_TEST( Cuckoo_striped_list_basehook_sort_cmpmix)
 613             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_cmpmix)
 614             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_cmpmix_stat)
 615
 616             CPPUNIT_TEST( Cuckoo_striped_list_basehook_equal_storehash)
 617             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_equal_storehash)
 618             CPPUNIT_TEST( Cuckoo_striped_list_basehook_sort_cmp_storehash)
 619             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_cmp_storehash)
 620             CPPUNIT_TEST( Cuckoo_striped_list_basehook_sort_less_storehash)
 621             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_less_storehash)
 622             CPPUNIT_TEST( Cuckoo_striped_list_basehook_sort_cmpmix_storehash)
 623             CPPUNIT_TEST( Cuckoo_striped_vector_basehook_sort_cmpmix_storehash)
 624
 625             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_equal)
 626             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_equal)
 627             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_sort_cmp)
 628             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_sort_cmp)
 629             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_sort_less)
 630             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_sort_less)
 631             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_sort_cmpmix)
 632             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_sort_cmpmix)
 633
 634             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_equal_storehash)
 635             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_equal_storehash)
 636             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_sort_cmp_storehash)
 637             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_sort_cmp_storehash)
 638             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_sort_less_storehash)
 639             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_sort_less_storehash)
 640             CPPUNIT_TEST( Cuckoo_striped_list_memberhook_sort_cmpmix_storehash)
 641             CPPUNIT_TEST( Cuckoo_striped_vector_memberhook_sort_cmpmix_storehash)
 642
 643             // ***********************************************************
 644             // Cuckoo hashing (refinable)
 645
 646             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_equal)
 647             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_equal)
 648             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_sort_cmp)
 649             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_cmp)
 650             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_sort_less)
 651             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_less)
 652             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_sort_cmpmix)
 653             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_cmpmix)
 654             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_cmpmix_stat)
 655
 656             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_equal_storehash)
 657             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_equal_storehash)
 658             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_sort_cmp_storehash)
 659             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_cmp_storehash)
 660             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_sort_less_storehash)
 661             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_less_storehash)
 662             CPPUNIT_TEST( Cuckoo_refinable_list_basehook_sort_cmpmix_storehash)
 663             CPPUNIT_TEST( Cuckoo_refinable_vector_basehook_sort_cmpmix_storehash)
 664
 665             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_equal)
 666             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_equal)
 667             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_sort_cmp)
 668             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_sort_cmp)
 669             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_sort_less)
 670             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_sort_less)
 671             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_sort_cmpmix)
 672             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_sort_cmpmix)
 673
 674             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_equal_storehash)
 675             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_equal_storehash)
 676             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_sort_cmp_storehash)
 677             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_sort_cmp_storehash)
 678             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_sort_less_storehash)
 679             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_sort_less_storehash)
 680             CPPUNIT_TEST( Cuckoo_refinable_list_memberhook_sort_cmpmix_storehash)
 681             CPPUNIT_TEST( Cuckoo_refinable_vector_memberhook_sort_cmpmix_storehash)
 682
 683         CPPUNIT_TEST_SUITE_END()
 684     };
 685 } // namespace set
 686
 687 #endif // #ifndef CDSTEST_HDR_INTRUSIVE_CUCKOO_SET_H