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: hashes.cpp 36216 2005-11-20 21:55:35Z DS $ 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 38struct Foo 39{ 40 Foo(int n_) { n = n_; count++; } 41 ~Foo() { count--; } 42 43 int n; 44 45 static size_t count; 46}; 47 48size_t Foo::count = 0; 49 50struct 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 60size_t FooObject::count = 0; 61 62// -------------------------------------------------------------------------- 63// test class 64// -------------------------------------------------------------------------- 65 66class HashesTestCase : public CppUnit::TestCase 67{ 68public: 69 HashesTestCase() { } 70 71private: 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 112CPPUNIT_TEST_SUITE_REGISTRATION( HashesTestCase ); 113 114// also include in it's own registry so that these tests can be run alone 115CPPUNIT_TEST_SUITE_NAMED_REGISTRATION( HashesTestCase, "HashesTestCase" ); 116 117void 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 231void 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 268WX_DECLARE_LIST(Foo, wxListFoos); 269#endif 270 271WX_DECLARE_HASH(Foo, wxListFoos, wxHashFoos); 272 273#if WXWIN_COMPATIBILITY_2_4 274#include "wx/listimpl.cpp" 275WX_DEFINE_LIST(wxListFoos) 276#endif 277 278void 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 327WX_DECLARE_HASH_MAP( int*, int*, wxPointerHash, wxPointerEqual, myPtrHashMap ); 328WX_DECLARE_HASH_MAP( long, long, wxIntegerHash, wxIntegerEqual, myLongHashMap ); 329WX_DECLARE_HASH_MAP( unsigned long, unsigned, wxIntegerHash, wxIntegerEqual, 330 myUnsignedHashMap ); 331WX_DECLARE_HASH_MAP( unsigned int, unsigned, wxIntegerHash, wxIntegerEqual, 332 myTestHashMap1 ); 333WX_DECLARE_HASH_MAP( int, unsigned, wxIntegerHash, wxIntegerEqual, 334 myTestHashMap2 ); 335WX_DECLARE_HASH_MAP( short, unsigned, wxIntegerHash, wxIntegerEqual, 336 myTestHashMap3 ); 337WX_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 ); 343WX_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' 353void 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 362template <class IntT, class KeyT> 363IntT 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 373template <class KeyT, class ValueT> 374void 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 381template <class T, class ValueT> 382void 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 389template <class HashMapT> 390void 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 471void HashesTestCase::StringHashMapTest() { HashMapTest<myStringHashMap>(); } 472void HashesTestCase::PtrHashMapTest() { HashMapTest<myPtrHashMap>(); } 473void HashesTestCase::LongHashMapTest() { HashMapTest<myLongHashMap>(); } 474void HashesTestCase::ULongHashMapTest() { HashMapTest<myUnsignedHashMap>(); } 475void HashesTestCase::UIntHashMapTest() { HashMapTest<myTestHashMap1>(); } 476void HashesTestCase::IntHashMapTest() { HashMapTest<myTestHashMap2>(); } 477void HashesTestCase::ShortHashMapTest() { HashMapTest<myTestHashMap3>(); } 478void HashesTestCase::UShortHashMapTest() { HashMapTest<myTestHashMap4>(); } 479 480#ifdef TEST_LONGLONG 481void HashesTestCase::LLongHashMapTest() { HashMapTest<myLLongHashMap>(); } 482void HashesTestCase::ULLongHashMapTest() { HashMapTest<myULLongHashMap>(); } 483#endif 484 485// test compilation of basic set types 486WX_DECLARE_HASH_SET( int*, wxPointerHash, wxPointerEqual, myPtrHashSet ); 487WX_DECLARE_HASH_SET( long, wxIntegerHash, wxIntegerEqual, myLongHashSet ); 488WX_DECLARE_HASH_SET( unsigned long, wxIntegerHash, wxIntegerEqual, 489 myUnsignedHashSet ); 490WX_DECLARE_HASH_SET( unsigned int, wxIntegerHash, wxIntegerEqual, 491 myTestHashSet1 ); 492WX_DECLARE_HASH_SET( int, wxIntegerHash, wxIntegerEqual, 493 myTestHashSet2 ); 494WX_DECLARE_HASH_SET( short, wxIntegerHash, wxIntegerEqual, 495 myTestHashSet3 ); 496WX_DECLARE_HASH_SET( unsigned short, wxIntegerHash, wxIntegerEqual, 497 myTestHashSet4 ); 498WX_DECLARE_HASH_SET( wxString, wxStringHash, wxStringEqual, 499 myTestHashSet5 ); 500 501struct MyStruct 502{ 503 int* ptr; 504 wxString str; 505}; 506 507class MyHash 508{ 509public: 510 unsigned long operator()(const MyStruct& s) const 511 { return m_dummy(s.ptr); } 512 MyHash& operator=(const MyHash&) { return *this; } 513private: 514 wxPointerHash m_dummy; 515}; 516 517class MyEqual 518{ 519public: 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 525WX_DECLARE_HASH_SET( MyStruct, MyHash, MyEqual, mySet ); 526 527typedef myTestHashSet5 wxStringHashSet; 528 529void 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} 565