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 // Created:     2004-05-16
   6 // RCS-ID:      $Id$
   7 // Copyright:   (c) 2004 Vadim Zeitlin, Mattia Barbon
   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 // --------------------------------------------------------------------------
  29 // helper class for typed/untyped wxHashTable
  30 // --------------------------------------------------------------------------
  31
  32 struct Foo
  33 {
  34     Foo(int n_) { n = n_; count++; }
  35     ~Foo() { count--; }
  36
  37     int n;
  38
  39     static size_t count;
  40 };
  41
  42 size_t Foo::count = 0;
  43
  44 struct FooObject : public wxObject
  45 {
  46     FooObject(int n_) { n = n_; count++; }
  47     ~FooObject() { count--; }
  48
  49     int n;
  50
  51     static size_t count;
  52 };
  53
  54 size_t FooObject::count = 0;
  55
  56 // --------------------------------------------------------------------------
  57 // test class
  58 // --------------------------------------------------------------------------
  59
  60 class HashesTestCase : public CppUnit::TestCase
  61 {
  62 public:
  63     HashesTestCase() { }
  64
  65 private:
  66     CPPUNIT_TEST_SUITE( HashesTestCase );
  67         CPPUNIT_TEST( wxHashTableTest );
  68         CPPUNIT_TEST( wxUntypedHashTableDeleteContents );
  69         CPPUNIT_TEST( wxTypedHashTableTest );
  70         CPPUNIT_TEST( wxHashMapTest );
  71         CPPUNIT_TEST( wxHashSetTest );
  72     CPPUNIT_TEST_SUITE_END();
  73
  74     void wxHashTableTest();
  75     void wxUntypedHashTableDeleteContents();
  76     void wxTypedHashTableTest();
  77     void wxHashMapTest();
  78     void wxHashSetTest();
  79
  80     DECLARE_NO_COPY_CLASS(HashesTestCase)
  81 };
  82
  83 // register in the unnamed registry so that these tests are run by default
  84 CPPUNIT_TEST_SUITE_REGISTRATION( HashesTestCase );
  85
  86 // also include in it's own registry so that these tests can be run alone
  87 CPPUNIT_TEST_SUITE_NAMED_REGISTRATION( HashesTestCase, "HashesTestCase" );
  88
  89 void HashesTestCase::wxHashTableTest()
  90 {
  91     const int COUNT = 100;
  92
  93     {
  94         wxHashTable hash(wxKEY_INTEGER, 10), hash2(wxKEY_STRING);
  95         wxObject o;
  96         int i;
  97
  98         for ( i = 0; i < COUNT; ++i )
  99             hash.Put(i, &o + i);
 100
 101         hash.BeginFind();
 102         wxHashTable::compatibility_iterator it = hash.Next();
 103         i = 0;
 104
 105         while (it)
 106         {
 107             ++i;
 108             it = hash.Next();
 109         }
 110
 111         CPPUNIT_ASSERT( i == COUNT );
 112
 113         for ( i = 99; i >= 0; --i )
 114             CPPUNIT_ASSERT( hash.Get(i) == &o + i );
 115
 116         for ( i = 0; i < COUNT; ++i )
 117             hash.Put(i, &o + i + 20);
 118
 119         for ( i = 99; i >= 0; --i )
 120             CPPUNIT_ASSERT( hash.Get(i) == &o + i);
 121
 122         for ( i = 0; i < COUNT/2; ++i )
 123             CPPUNIT_ASSERT( hash.Delete(i) == &o + i);
 124
 125         for ( i = COUNT/2; i < COUNT; ++i )
 126             CPPUNIT_ASSERT( hash.Get(i) == &o + i);
 127
 128         for ( i = 0; i < COUNT/2; ++i )
 129             CPPUNIT_ASSERT( hash.Get(i) == &o + i + 20);
 130
 131         for ( i = 0; i < COUNT/2; ++i )
 132             CPPUNIT_ASSERT( hash.Delete(i) == &o + i + 20);
 133
 134         for ( i = 0; i < COUNT/2; ++i )
 135             CPPUNIT_ASSERT( hash.Get(i) == NULL);
 136
 137         hash2.Put(_T("foo"), &o + 1);
 138         hash2.Put(_T("bar"), &o + 2);
 139         hash2.Put(_T("baz"), &o + 3);
 140
 141         CPPUNIT_ASSERT(hash2.Get(_T("moo")) == NULL);
 142         CPPUNIT_ASSERT(hash2.Get(_T("bar")) == &o + 2);
 143
 144         hash2.Put(_T("bar"), &o + 0);
 145
 146         CPPUNIT_ASSERT(hash2.Get(_T("bar")) == &o + 2);
 147     }
 148
 149     // and now some corner-case testing; 3 and 13 hash to the same bucket
 150     {
 151         wxHashTable hash(wxKEY_INTEGER, 10);
 152         wxObject dummy;
 153
 154         hash.Put(3, &dummy);
 155         hash.Delete(3);
 156
 157         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 158
 159         hash.Put(3, &dummy);
 160         hash.Put(13, &dummy);
 161         hash.Delete(3);
 162
 163         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 164
 165         hash.Delete(13);
 166
 167         CPPUNIT_ASSERT(hash.Get(13) == NULL);
 168
 169         hash.Put(3, &dummy);
 170         hash.Put(13, &dummy);
 171         hash.Delete(13);
 172
 173         CPPUNIT_ASSERT(hash.Get(13) == NULL);
 174
 175         hash.Delete(3);
 176
 177         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 178     }
 179
 180     // test for key + value access (specifically that supplying either
 181     // wrong key or wrong value returns NULL)
 182     {
 183         wxHashTable hash(wxKEY_INTEGER, 10);
 184         wxObject dummy;
 185
 186         hash.Put(3, 7, &dummy + 7);
 187         hash.Put(4, 8, &dummy + 8);
 188
 189         CPPUNIT_ASSERT(hash.Get(7) == NULL);
 190         CPPUNIT_ASSERT(hash.Get(3, 7) == &dummy + 7);
 191         CPPUNIT_ASSERT(hash.Get(4) == NULL);
 192         CPPUNIT_ASSERT(hash.Get(3) == NULL);
 193         CPPUNIT_ASSERT(hash.Get(8) == NULL);
 194         CPPUNIT_ASSERT(hash.Get(8, 4) == NULL);
 195
 196         CPPUNIT_ASSERT(hash.Delete(7) == NULL);
 197         CPPUNIT_ASSERT(hash.Delete(3) == NULL);
 198         CPPUNIT_ASSERT(hash.Delete(3, 7) == &dummy + 7);
 199     }
 200
 201 }
 202
 203 void HashesTestCase::wxUntypedHashTableDeleteContents()
 204 {
 205     // need a nested scope for destruction
 206     {
 207         wxHashTable hash;
 208         hash.DeleteContents(true);
 209
 210         CPPUNIT_ASSERT( hash.GetCount() == 0 );
 211         CPPUNIT_ASSERT( FooObject::count == 0 );
 212
 213         static const int hashTestData[] =
 214         {
 215             0, 1, 17, -2, 2, 4, -4, 345, 3, 3, 2, 1,
 216         };
 217
 218         size_t n;
 219         for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
 220         {
 221             hash.Put(hashTestData[n], n, new FooObject(n));
 222         }
 223
 224         CPPUNIT_ASSERT( hash.GetCount() == WXSIZEOF(hashTestData) );
 225         CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) );
 226
 227         // delete from hash without deleting object
 228         FooObject* foo = (FooObject*)hash.Delete(0l);
 229
 230         CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) );
 231         delete foo;
 232         CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) - 1 );
 233     }
 234
 235     // hash destroyed
 236     CPPUNIT_ASSERT( FooObject::count == 0 );
 237 }
 238
 239 #if WXWIN_COMPATIBILITY_2_4
 240 WX_DECLARE_LIST(Foo, wxListFoos);
 241 #endif
 242
 243 WX_DECLARE_HASH(Foo, wxListFoos, wxHashFoos);
 244
 245 #if WXWIN_COMPATIBILITY_2_4
 246 #include "wx/listimpl.cpp"
 247 WX_DEFINE_LIST(wxListFoos);
 248 #endif
 249
 250 void HashesTestCase::wxTypedHashTableTest()
 251 {
 252     // need a nested scope for destruction
 253     {
 254         wxHashFoos hash;
 255         hash.DeleteContents(true);
 256
 257         CPPUNIT_ASSERT( hash.GetCount() == 0 );
 258         CPPUNIT_ASSERT( Foo::count == 0 );
 259
 260         static const int hashTestData[] =
 261         {
 262             0, 1, 17, -2, 2, 4, -4, 345, 3, 3, 2, 1,
 263         };
 264
 265         size_t n;
 266         for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
 267         {
 268             hash.Put(hashTestData[n], n, new Foo(n));
 269         }
 270
 271         CPPUNIT_ASSERT( hash.GetCount() == WXSIZEOF(hashTestData) );
 272         CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) );
 273
 274         for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
 275         {
 276             Foo *foo = hash.Get(hashTestData[n], n);
 277
 278             CPPUNIT_ASSERT( foo != NULL );
 279             CPPUNIT_ASSERT( foo->n == (int)n );
 280         }
 281
 282         // element not in hash
 283         CPPUNIT_ASSERT( hash.Get(1234) == NULL );
 284         CPPUNIT_ASSERT( hash.Get(1, 0) == NULL );
 285
 286         // delete from hash without deleting object
 287         Foo* foo = hash.Delete(0);
 288
 289         CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) );
 290         delete foo;
 291         CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) - 1 );
 292     }
 293
 294     // hash destroyed
 295     CPPUNIT_ASSERT( Foo::count == 0 );
 296 }
 297
 298 // test compilation of basic map types
 299 WX_DECLARE_HASH_MAP( int*, int*, wxPointerHash, wxPointerEqual, myPtrHashMap );
 300 WX_DECLARE_HASH_MAP( long, long, wxIntegerHash, wxIntegerEqual, myLongHashMap );
 301 WX_DECLARE_HASH_MAP( unsigned long, unsigned, wxIntegerHash, wxIntegerEqual,
 302                      myUnsignedHashMap );
 303 WX_DECLARE_HASH_MAP( unsigned int, unsigned, wxIntegerHash, wxIntegerEqual,
 304                      myTestHashMap1 );
 305 WX_DECLARE_HASH_MAP( int, unsigned, wxIntegerHash, wxIntegerEqual,
 306                      myTestHashMap2 );
 307 WX_DECLARE_HASH_MAP( short, unsigned, wxIntegerHash, wxIntegerEqual,
 308                      myTestHashMap3 );
 309 WX_DECLARE_HASH_MAP( unsigned short, unsigned, wxIntegerHash, wxIntegerEqual,
 310                      myTestHashMap4 );
 311
 312 // same as:
 313 // WX_DECLARE_HASH_MAP( wxString, wxString, wxStringHash, wxStringEqual,
 314 //                      myStringHashMap );
 315 WX_DECLARE_STRING_HASH_MAP(wxString, myStringHashMap);
 316
 317 typedef myStringHashMap::iterator Itor;
 318
 319 void HashesTestCase::wxHashMapTest()
 320 {
 321     myStringHashMap sh(0); // as small as possible
 322     wxString buf;
 323     size_t i;
 324     const size_t count = 10000;
 325
 326     // init with some data
 327     for( i = 0; i < count; ++i )
 328     {
 329         buf.Printf(wxT("%d"), i );
 330         sh[buf] = wxT("A") + buf + wxT("C");
 331     }
 332
 333     // test that insertion worked
 334     CPPUNIT_ASSERT( sh.size() == count );
 335
 336     for( i = 0; i < count; ++i )
 337     {
 338         buf.Printf(wxT("%d"), i );
 339         CPPUNIT_ASSERT( sh[buf] == wxT("A") + buf + wxT("C") );
 340     }
 341
 342     // check that iterators work
 343     Itor it;
 344     for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i )
 345     {
 346         CPPUNIT_ASSERT( i != count );
 347         CPPUNIT_ASSERT( it->second == sh[it->first] );
 348     }
 349
 350     CPPUNIT_ASSERT( sh.size() == i );
 351
 352     // test copy ctor, assignment operator
 353     myStringHashMap h1( sh ), h2( 0 );
 354     h2 = sh;
 355
 356     for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i )
 357     {
 358         CPPUNIT_ASSERT( h1[it->first] == it->second );
 359         CPPUNIT_ASSERT( h2[it->first] == it->second );
 360     }
 361
 362     // other tests
 363     for( i = 0; i < count; ++i )
 364     {
 365         buf.Printf(wxT("%d"), i );
 366         size_t sz = sh.size();
 367
 368         // test find() and erase(it)
 369         if( i < 100 )
 370         {
 371             it = sh.find( buf );
 372             CPPUNIT_ASSERT( it != sh.end() );
 373
 374             sh.erase( it );
 375
 376             CPPUNIT_ASSERT( sh.find( buf ) == sh.end() );
 377         }
 378         else
 379         // test erase(key)
 380         {
 381             size_t c = sh.erase( buf );
 382             CPPUNIT_ASSERT( c == 1 );
 383             CPPUNIT_ASSERT( sh.find( buf ) == sh.end() );
 384         }
 385
 386         // count should decrease
 387         CPPUNIT_ASSERT( sh.size() == sz - 1 );
 388     }
 389 }
 390
 391 // test compilation of basic set types
 392 WX_DECLARE_HASH_SET( int*, wxPointerHash, wxPointerEqual, myPtrHashSet );
 393 WX_DECLARE_HASH_SET( long, wxIntegerHash, wxIntegerEqual, myLongHashSet );
 394 WX_DECLARE_HASH_SET( unsigned long, wxIntegerHash, wxIntegerEqual,
 395                      myUnsignedHashSet );
 396 WX_DECLARE_HASH_SET( unsigned int, wxIntegerHash, wxIntegerEqual,
 397                      myTestHashSet1 );
 398 WX_DECLARE_HASH_SET( int, wxIntegerHash, wxIntegerEqual,
 399                      myTestHashSet2 );
 400 WX_DECLARE_HASH_SET( short, wxIntegerHash, wxIntegerEqual,
 401                      myTestHashSet3 );
 402 WX_DECLARE_HASH_SET( unsigned short, wxIntegerHash, wxIntegerEqual,
 403                      myTestHashSet4 );
 404 WX_DECLARE_HASH_SET( wxString, wxStringHash, wxStringEqual,
 405                      myTestHashSet5 );
 406
 407 struct MyStruct
 408 {
 409     int* ptr;
 410     wxString str;
 411 };
 412
 413 class MyHash
 414 {
 415 public:
 416     unsigned long operator()(const MyStruct& s) const
 417         { return m_dummy(s.ptr); }
 418     MyHash& operator=(const MyHash&) { return *this; }
 419 private:
 420     wxPointerHash m_dummy;
 421 };
 422
 423 class MyEqual
 424 {
 425 public:
 426     bool operator()(const MyStruct& s1, const MyStruct& s2) const
 427         { return s1.ptr == s2.ptr; }
 428     MyEqual& operator=(const MyEqual&) { return *this; }
 429 };
 430
 431 WX_DECLARE_HASH_SET( MyStruct, MyHash, MyEqual, mySet );
 432
 433 typedef myTestHashSet5 wxStringHashSet;
 434
 435 void HashesTestCase::wxHashSetTest()
 436 {
 437     wxStringHashSet set1;
 438
 439     set1.insert( _T("abc") );
 440
 441     CPPUNIT_ASSERT( set1.size() == 1 );
 442
 443     set1.insert( _T("bbc") );
 444     set1.insert( _T("cbc") );
 445
 446     CPPUNIT_ASSERT( set1.size() == 3 );
 447
 448     set1.insert( _T("abc") );
 449
 450     CPPUNIT_ASSERT( set1.size() == 3 );
 451
 452     mySet set2;
 453     int dummy;
 454     MyStruct tmp;
 455
 456     tmp.ptr = &dummy; tmp.str = _T("ABC");
 457     set2.insert( tmp );
 458     tmp.ptr = &dummy + 1;
 459     set2.insert( tmp );
 460     tmp.ptr = &dummy; tmp.str = _T("CDE");
 461     set2.insert( tmp );
 462
 463     CPPUNIT_ASSERT( set2.size() == 2 );
 464
 465     mySet::iterator it = set2.find( tmp );
 466
 467     CPPUNIT_ASSERT( it != set2.end() );
 468     CPPUNIT_ASSERT( it->ptr == &dummy );
 469     CPPUNIT_ASSERT( it->str == _T("ABC") );
 470 }