tests/hashes/hashes.cpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Name:        tests/hashes/hashes.cpp
   3 // Purpose:     wxHashTable, wxHashMap, wxHashSet unit test
   4 // Author:      Vadim Zeitlin, Mattia Barbon
   5 // Modified:    Mike Wetherell
   6 // Created:     2004-05-16
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 2004 Vadim Zeitlin, Mattia Barbon, 2005 M. Wetherell
   9 ///////////////////////////////////////////////////////////////////////////////
  10
  11 // ----------------------------------------------------------------------------
  12 // headers
  13 // ----------------------------------------------------------------------------
  14
  15 #include "testprec.h"
  16
  17 #ifdef __BORLANDC__
  18     #pragma hdrstop
  19 #endif
  20
  21 #ifndef WX_PRECOMP
  22     #include "wx/wx.h"
  23 #endif // WX_PRECOMP
  24
  25 #include "wx/hash.h"
  26 #include "wx/hashmap.h"
  27 #include "wx/hashset.h"
  28
  29 #if defined wxLongLong_t && !defined wxLongLongIsLong && \
  30         (!defined __VISUALC__ || __VISUALC__ > 1100)    // doesn't work on VC5
  31     #define TEST_LONGLONG
  32 #endif
  33
  34 // --------------------------------------------------------------------------
  35 // helper class for typed/untyped wxHashTable
  36 // --------------------------------------------------------------------------
  37
  38 struct Foo
  39 {
  40     Foo(int n_) { n = n_; count++; }
  41     ~Foo() { count--; }
  42
  43     int n;
  44
  45     static size_t count;
  46 };
  47
  48 size_t Foo::count = 0;
  49
  50 struct FooObject : public wxObject
  51 {
  52     FooObject(int n_) { n = n_; count++; }
  53     ~FooObject() { count--; }
  54
  55     int n;
  56
  57     static size_t count;
  58 };
  59
  60 size_t FooObject::count = 0;
  61
  62 // --------------------------------------------------------------------------
  63 // test class
  64 // --------------------------------------------------------------------------
  65
  66 class HashesTestCase : public CppUnit::TestCase
  67 {
  68 public:
  69     HashesTestCase() { }
  70
  71 private:
  72     CPPUNIT_TEST_SUITE( HashesTestCase );
  73         CPPUNIT_TEST( wxHashTableTest );
  74         CPPUNIT_TEST( wxUntypedHashTableDeleteContents );
  75         CPPUNIT_TEST( wxTypedHashTableTest );
  76         CPPUNIT_TEST( StringHashMapTest );
  77         CPPUNIT_TEST( PtrHashMapTest );
  78         CPPUNIT_TEST( LongHashMapTest );
  79         CPPUNIT_TEST( ULongHashMapTest );
  80         CPPUNIT_TEST( UIntHashMapTest );
  81         CPPUNIT_TEST( IntHashMapTest );
  82         CPPUNIT_TEST( ShortHashMapTest );
  83         CPPUNIT_TEST( UShortHashMapTest );
  84 #ifdef TEST_LONGLONG
  85         CPPUNIT_TEST( LLongHashMapTest );
  86         CPPUNIT_TEST( ULLongHashMapTest );
  87 #endif
  88         CPPUNIT_TEST( wxHashSetTest );
  89     CPPUNIT_TEST_SUITE_END();
  90
  91     void wxHashTableTest();
  92     void wxUntypedHashTableDeleteContents();
  93     void wxTypedHashTableTest();
  94     void StringHashMapTest();
  95     void PtrHashMapTest();
  96     void LongHashMapTest();
  97     void ULongHashMapTest();
  98     void UIntHashMapTest();
  99     void IntHashMapTest();
 100     void ShortHashMapTest();
 101     void UShortHashMapTest();
 102 #ifdef TEST_LONGLONG
 103     void LLongHashMapTest();
 104     void ULLongHashMapTest();
 105 #endif
 106     void wxHashSetTest();
 107
 108     DECLARE_NO_COPY_CLASS(HashesTestCase)
 109 };
 110
 111 // register in the unnamed registry so that these tests are run by default
 112 CPPUNIT_TEST_SUITE_REGISTRATION( HashesTestCase );
 113
 114 // also include in it's own registry so that these tests can be run alone
 115 CPPUNIT_TEST_SUITE_NAMED_REGISTRATION( HashesTestCase, "HashesTestCase" );
 116
 117 void HashesTestCase::wxHashTableTest()
 118 {
 119     const int COUNT = 100;
 120
 121     {
 122         wxHashTable hash(wxKEY_INTEGER, 10), hash2(wxKEY_STRING);
 123         wxObject o;
 124         int i;
 125
 126         for ( i = 0; i < COUNT; ++i )
 127             hash.Put(i, &o + i);
 128
 129         hash.BeginFind();
 130         wxHashTable::compatibility_iterator it = hash.Next();
 131         i = 0;
 132
 133         while (it)
 134         {
 135             ++i;
 136             it = hash.Next();
 137         }
 138
 139         CPPUNIT_ASSERT( i == COUNT );
 140
 141         for ( i = 99; i >= 0; --i )
 142             CPPUNIT_ASSERT( hash.Get(i) == &o + i );
 143
 144         for ( i = 0; i < COUNT; ++i )
 145             hash.Put(i, &o + i + 20);
 146
 147         for ( i = 99; i >= 0; --i )
 148             CPPUNIT_ASSERT( hash.Get(i) == &o + i);
 149
 150         for ( i = 0; i < COUNT/2; ++i )
 151             CPPUNIT_ASSERT( hash.Delete(i) == &o + i);
 152
 153         for ( i = COUNT/2; i < COUNT; ++i )
 154             CPPUNIT_ASSERT( hash.Get(i) == &o + i);
 155
 156         for ( i = 0; i < COUNT/2; ++i )
 157             CPPUNIT_ASSERT( hash.Get(i) == &o + i + 20);
 158
 159         for ( i = 0; i < COUNT/2; ++i )
 160             CPPUNIT_ASSERT( hash.Delete(i) == &o + i + 20);
 161
 162         for ( i = 0; i < COUNT/2; ++i )
 163             CPPUNIT_ASSERT( hash.Get(i) == NULL);
 164
 165         hash2.Put(_T("foo"), &o + 1);
 166         hash2.Put(_T("bar"), &o + 2);
 167         hash2.Put(_T("baz"), &o + 3);
 168
 169         CPPUNIT_ASSERT(hash2.Get(_T("moo")) == NULL);
 170         CPPUNIT_ASSERT(hash2.Get(_T("bar")) == &o + 2);
 171
 172         hash2.Put(_T("bar"), &o + 0);
 173
 174         CPPUNIT_ASSERT(hash2.Get(_T("bar")) == &o + 2);
 175     }
 176
 177     // and now some corner-case testing; 3 and 13 hash to the same bucket
 178     {
 179         wxHashTable hash(wxKEY_INTEGER, 10);
 180         wxObject dummy;
 181
 182         hash.Put(3, &dummy);
 183         hash.Delete(3);
 184
 185         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 186
 187         hash.Put(3, &dummy);
 188         hash.Put(13, &dummy);
 189         hash.Delete(3);
 190
 191         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 192
 193         hash.Delete(13);
 194
 195         CPPUNIT_ASSERT(hash.Get(13) == NULL);
 196
 197         hash.Put(3, &dummy);
 198         hash.Put(13, &dummy);
 199         hash.Delete(13);
 200
 201         CPPUNIT_ASSERT(hash.Get(13) == NULL);
 202
 203         hash.Delete(3);
 204
 205         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 206     }
 207
 208     // test for key + value access (specifically that supplying either
 209     // wrong key or wrong value returns NULL)
 210     {
 211         wxHashTable hash(wxKEY_INTEGER, 10);
 212         wxObject dummy;
 213
 214         hash.Put(3, 7, &dummy + 7);
 215         hash.Put(4, 8, &dummy + 8);
 216
 217         CPPUNIT_ASSERT(hash.Get(7) == NULL);
 218         CPPUNIT_ASSERT(hash.Get(3, 7) == &dummy + 7);
 219         CPPUNIT_ASSERT(hash.Get(4) == NULL);
 220         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 221         CPPUNIT_ASSERT(hash.Get(8) == NULL);
 222         CPPUNIT_ASSERT(hash.Get(8, 4) == NULL);
 223
 224         CPPUNIT_ASSERT(hash.Delete(7) == NULL);
 225         CPPUNIT_ASSERT(hash.Delete(3) == NULL);
 226         CPPUNIT_ASSERT(hash.Delete(3, 7) == &dummy + 7);
 227     }
 228
 229 }
 230
 231 void HashesTestCase::wxUntypedHashTableDeleteContents()
 232 {
 233     // need a nested scope for destruction
 234     {
 235         wxHashTable hash;
 236         hash.DeleteContents(true);
 237
 238         CPPUNIT_ASSERT( hash.GetCount() == 0 );
 239         CPPUNIT_ASSERT( FooObject::count == 0 );
 240
 241         static const int hashTestData[] =
 242         {
 243             0, 1, 17, -2, 2, 4, -4, 345, 3, 3, 2, 1,
 244         };
 245
 246         size_t n;
 247         for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
 248         {
 249             hash.Put(hashTestData[n], n, new FooObject(n));
 250         }
 251
 252         CPPUNIT_ASSERT( hash.GetCount() == WXSIZEOF(hashTestData) );
 253         CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) );
 254
 255         // delete from hash without deleting object
 256         FooObject* foo = (FooObject*)hash.Delete(0l);
 257
 258         CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) );
 259         delete foo;
 260         CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) - 1 );
 261     }
 262
 263     // hash destroyed
 264     CPPUNIT_ASSERT( FooObject::count == 0 );
 265 }
 266
 267 #if WXWIN_COMPATIBILITY_2_4
 268 WX_DECLARE_LIST(Foo, wxListFoos);
 269 #endif
 270
 271 WX_DECLARE_HASH(Foo, wxListFoos, wxHashFoos);
 272
 273 #if WXWIN_COMPATIBILITY_2_4
 274 #include "wx/listimpl.cpp"
 275 WX_DEFINE_LIST(wxListFoos)
 276 #endif
 277
 278 void HashesTestCase::wxTypedHashTableTest()
 279 {
 280     // need a nested scope for destruction
 281     {
 282         wxHashFoos hash;
 283         hash.DeleteContents(true);
 284
 285         CPPUNIT_ASSERT( hash.GetCount() == 0 );
 286         CPPUNIT_ASSERT( Foo::count == 0 );
 287
 288         static const int hashTestData[] =
 289         {
 290             0, 1, 17, -2, 2, 4, -4, 345, 3, 3, 2, 1,
 291         };
 292
 293         size_t n;
 294         for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
 295         {
 296             hash.Put(hashTestData[n], n, new Foo(n));
 297         }
 298
 299         CPPUNIT_ASSERT( hash.GetCount() == WXSIZEOF(hashTestData) );
 300         CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) );
 301
 302         for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
 303         {
 304             Foo *foo = hash.Get(hashTestData[n], n);
 305
 306             CPPUNIT_ASSERT( foo != NULL );
 307             CPPUNIT_ASSERT( foo->n == (int)n );
 308         }
 309
 310         // element not in hash
 311         CPPUNIT_ASSERT( hash.Get(1234) == NULL );
 312         CPPUNIT_ASSERT( hash.Get(1, 0) == NULL );
 313
 314         // delete from hash without deleting object
 315         Foo* foo = hash.Delete(0);
 316
 317         CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) );
 318         delete foo;
 319         CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) - 1 );
 320     }
 321
 322     // hash destroyed
 323     CPPUNIT_ASSERT( Foo::count == 0 );
 324 }
 325
 326 // test compilation of basic map types
 327 WX_DECLARE_HASH_MAP( int*, int*, wxPointerHash, wxPointerEqual, myPtrHashMap );
 328 WX_DECLARE_HASH_MAP( long, long, wxIntegerHash, wxIntegerEqual, myLongHashMap );
 329 WX_DECLARE_HASH_MAP( unsigned long, unsigned, wxIntegerHash, wxIntegerEqual,
 330                      myUnsignedHashMap );
 331 WX_DECLARE_HASH_MAP( unsigned int, unsigned, wxIntegerHash, wxIntegerEqual,
 332                      myTestHashMap1 );
 333 WX_DECLARE_HASH_MAP( int, unsigned, wxIntegerHash, wxIntegerEqual,
 334                      myTestHashMap2 );
 335 WX_DECLARE_HASH_MAP( short, unsigned, wxIntegerHash, wxIntegerEqual,
 336                      myTestHashMap3 );
 337 WX_DECLARE_HASH_MAP( unsigned short, unsigned, wxIntegerHash, wxIntegerEqual,
 338                      myTestHashMap4 );
 339
 340 // same as:
 341 // WX_DECLARE_HASH_MAP( wxString, wxString, wxStringHash, wxStringEqual,
 342 //                      myStringHashMap );
 343 WX_DECLARE_STRING_HASH_MAP(wxString, myStringHashMap);
 344
 345 #ifdef TEST_LONGLONG
 346     WX_DECLARE_HASH_MAP( wxLongLong_t, wxLongLong_t,
 347                          wxIntegerHash, wxIntegerEqual, myLLongHashMap );
 348     WX_DECLARE_HASH_MAP( wxULongLong_t, wxULongLong_t,
 349                          wxIntegerHash, wxIntegerEqual, myULLongHashMap );
 350 #endif
 351
 352 // Helpers to generate a key value pair for item 'i', out of a total of 'count'
 353 void MakeKeyValuePair(size_t i, size_t /*count*/, wxString& key, wxString& val)
 354 {
 355     key.clear();
 356     key << i;
 357     val = wxT("A") + key + wxT("C");
 358 }
 359
 360 // for integral keys generate a range of keys that will use all the bits of
 361 // the key type
 362 template <class IntT, class KeyT>
 363 IntT MakeKey(size_t i, size_t count)
 364 {
 365     IntT max = 1;
 366     max <<= sizeof(KeyT) * 8 - 2;
 367     max -= count / 4 + 1;
 368
 369     return max / count * 4 * i + i / 3;
 370 }
 371
 372 // make key/value pairs for integer types
 373 template <class KeyT, class ValueT>
 374 void MakeKeyValuePair(size_t i, size_t count, KeyT& key, ValueT& value)
 375 {
 376     key = MakeKey<KeyT, KeyT>(i, count);
 377     value = wx_truncate_cast(ValueT, key);
 378 }
 379
 380 // make key/values paris for pointer types
 381 template <class T, class ValueT>
 382 void MakeKeyValuePair(size_t i, size_t count, T*& key, ValueT& value)
 383 {
 384     key = (T*)wxUIntToPtr(MakeKey<wxUIntPtr, T*>(i, count));
 385     value = wx_truncate_cast(ValueT, key);
 386 }
 387
 388 // the test
 389 template <class HashMapT>
 390 void HashMapTest()
 391 {
 392 #if wxUSE_STL && defined HAVE_STL_HASH_MAP
 393     typedef typename HashMapT::value_type::second_type value_type;
 394 #else
 395     typedef typename HashMapT::value_type::t2 value_type;
 396 #endif
 397     typedef typename HashMapT::key_type key_type;
 398     typedef typename HashMapT::iterator Itor;
 399
 400     HashMapT sh(0); // as small as possible
 401     key_type buf;
 402     value_type value;
 403     size_t i;
 404     const size_t count = 10000;
 405
 406     // init with some data
 407     for( i = 0; i < count; ++i )
 408     {
 409         MakeKeyValuePair(i, count, buf, value);
 410         sh[buf] = value;
 411     }
 412
 413     // test that insertion worked
 414     CPPUNIT_ASSERT( sh.size() == count );
 415
 416     for( i = 0; i < count; ++i )
 417     {
 418         MakeKeyValuePair(i, count, buf, value);
 419         CPPUNIT_ASSERT( sh[buf] == value );
 420     }
 421
 422     // check that iterators work
 423     Itor it;
 424     for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i )
 425     {
 426         CPPUNIT_ASSERT( i != count );
 427         CPPUNIT_ASSERT( it->second == sh[it->first] );
 428     }
 429
 430     CPPUNIT_ASSERT( sh.size() == i );
 431
 432     // test copy ctor, assignment operator
 433     HashMapT h1( sh ), h2( 0 );
 434     h2 = sh;
 435
 436     for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i )
 437     {
 438         CPPUNIT_ASSERT( h1[it->first] == it->second );
 439         CPPUNIT_ASSERT( h2[it->first] == it->second );
 440     }
 441
 442     // other tests
 443     for( i = 0; i < count; ++i )
 444     {
 445         MakeKeyValuePair(i, count, buf, value);
 446         size_t sz = sh.size();
 447
 448         // test find() and erase(it)
 449         if( i < 100 )
 450         {
 451             it = sh.find( buf );
 452             CPPUNIT_ASSERT( it != sh.end() );
 453
 454             sh.erase( it );
 455
 456             CPPUNIT_ASSERT( sh.find( buf ) == sh.end() );
 457         }
 458         else
 459         // test erase(key)
 460         {
 461             size_t c = sh.erase( buf );
 462             CPPUNIT_ASSERT( c == 1 );
 463             CPPUNIT_ASSERT( sh.find( buf ) == sh.end() );
 464         }
 465
 466         // count should decrease
 467         CPPUNIT_ASSERT( sh.size() == sz - 1 );
 468     }
 469 }
 470
 471 void HashesTestCase::StringHashMapTest() { HashMapTest<myStringHashMap>();   }
 472 void HashesTestCase::PtrHashMapTest()    { HashMapTest<myPtrHashMap>();      }
 473 void HashesTestCase::LongHashMapTest()   { HashMapTest<myLongHashMap>();     }
 474 void HashesTestCase::ULongHashMapTest()  { HashMapTest<myUnsignedHashMap>(); }
 475 void HashesTestCase::UIntHashMapTest()   { HashMapTest<myTestHashMap1>();    }
 476 void HashesTestCase::IntHashMapTest()    { HashMapTest<myTestHashMap2>();    }
 477 void HashesTestCase::ShortHashMapTest()  { HashMapTest<myTestHashMap3>();    }
 478 void HashesTestCase::UShortHashMapTest() { HashMapTest<myTestHashMap4>();    }
 479
 480 #ifdef TEST_LONGLONG
 481 void HashesTestCase::LLongHashMapTest()  { HashMapTest<myLLongHashMap>();    }
 482 void HashesTestCase::ULLongHashMapTest() { HashMapTest<myULLongHashMap>();   }
 483 #endif
 484
 485 // test compilation of basic set types
 486 WX_DECLARE_HASH_SET( int*, wxPointerHash, wxPointerEqual, myPtrHashSet );
 487 WX_DECLARE_HASH_SET( long, wxIntegerHash, wxIntegerEqual, myLongHashSet );
 488 WX_DECLARE_HASH_SET( unsigned long, wxIntegerHash, wxIntegerEqual,
 489                      myUnsignedHashSet );
 490 WX_DECLARE_HASH_SET( unsigned int, wxIntegerHash, wxIntegerEqual,
 491                      myTestHashSet1 );
 492 WX_DECLARE_HASH_SET( int, wxIntegerHash, wxIntegerEqual,
 493                      myTestHashSet2 );
 494 WX_DECLARE_HASH_SET( short, wxIntegerHash, wxIntegerEqual,
 495                      myTestHashSet3 );
 496 WX_DECLARE_HASH_SET( unsigned short, wxIntegerHash, wxIntegerEqual,
 497                      myTestHashSet4 );
 498 WX_DECLARE_HASH_SET( wxString, wxStringHash, wxStringEqual,
 499                      myTestHashSet5 );
 500
 501 struct MyStruct
 502 {
 503     int* ptr;
 504     wxString str;
 505 };
 506
 507 class MyHash
 508 {
 509 public:
 510     unsigned long operator()(const MyStruct& s) const
 511         { return m_dummy(s.ptr); }
 512     MyHash& operator=(const MyHash&) { return *this; }
 513 private:
 514     wxPointerHash m_dummy;
 515 };
 516
 517 class MyEqual
 518 {
 519 public:
 520     bool operator()(const MyStruct& s1, const MyStruct& s2) const
 521         { return s1.ptr == s2.ptr; }
 522     MyEqual& operator=(const MyEqual&) { return *this; }
 523 };
 524
 525 WX_DECLARE_HASH_SET( MyStruct, MyHash, MyEqual, mySet );
 526
 527 typedef myTestHashSet5 wxStringHashSet;
 528
 529 void HashesTestCase::wxHashSetTest()
 530 {
 531     wxStringHashSet set1;
 532
 533     set1.insert( _T("abc") );
 534
 535     CPPUNIT_ASSERT( set1.size() == 1 );
 536
 537     set1.insert( _T("bbc") );
 538     set1.insert( _T("cbc") );
 539
 540     CPPUNIT_ASSERT( set1.size() == 3 );
 541
 542     set1.insert( _T("abc") );
 543
 544     CPPUNIT_ASSERT( set1.size() == 3 );
 545
 546     mySet set2;
 547     int dummy;
 548     MyStruct tmp;
 549
 550     tmp.ptr = &dummy; tmp.str = _T("ABC");
 551     set2.insert( tmp );
 552     tmp.ptr = &dummy + 1;
 553     set2.insert( tmp );
 554     tmp.ptr = &dummy; tmp.str = _T("CDE");
 555     set2.insert( tmp );
 556
 557     CPPUNIT_ASSERT( set2.size() == 2 );
 558
 559     mySet::iterator it = set2.find( tmp );
 560
 561     CPPUNIT_ASSERT( it != set2.end() );
 562     CPPUNIT_ASSERT( it->ptr == &dummy );
 563     CPPUNIT_ASSERT( it->str == _T("ABC") );
 564 }