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