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
38 struct Foo
39 {
FooFoo40 Foo(int n_) { n = n_; count++; }
~FooFoo41 ~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 {
FooObjectFooObject52 FooObject(int n_) { n = n_; count++; }
~FooObjectFooObject53 ~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:
HashesTestCase()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
wxHashTableTest()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
wxUntypedHashTableDeleteContents()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"
WX_DEFINE_LIST(wxListFoos)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'
MakeKeyValuePair(size_t i,size_t,wxString & key,wxString & val)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>
MakeKeyValuePair(size_t i,size_t count,KeyT & key,ValueT & value)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>
MakeKeyValuePair(size_t i,size_t count,T * & key,ValueT & value)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>
HashMapTest()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
StringHashMapTest()471 void HashesTestCase::StringHashMapTest() { HashMapTest<myStringHashMap>(); }
PtrHashMapTest()472 void HashesTestCase::PtrHashMapTest() { HashMapTest<myPtrHashMap>(); }
LongHashMapTest()473 void HashesTestCase::LongHashMapTest() { HashMapTest<myLongHashMap>(); }
ULongHashMapTest()474 void HashesTestCase::ULongHashMapTest() { HashMapTest<myUnsignedHashMap>(); }
UIntHashMapTest()475 void HashesTestCase::UIntHashMapTest() { HashMapTest<myTestHashMap1>(); }
IntHashMapTest()476 void HashesTestCase::IntHashMapTest() { HashMapTest<myTestHashMap2>(); }
ShortHashMapTest()477 void HashesTestCase::ShortHashMapTest() { HashMapTest<myTestHashMap3>(); }
UShortHashMapTest()478 void HashesTestCase::UShortHashMapTest() { HashMapTest<myTestHashMap4>(); }
479
480 #ifdef TEST_LONGLONG
LLongHashMapTest()481 void HashesTestCase::LLongHashMapTest() { HashMapTest<myLLongHashMap>(); }
ULLongHashMapTest()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:
operator ()(const MyStruct & s) const510 unsigned long operator()(const MyStruct& s) const
511 { return m_dummy(s.ptr); }
operator =(const MyHash &)512 MyHash& operator=(const MyHash&) { return *this; }
513 private:
514 wxPointerHash m_dummy;
515 };
516
517 class MyEqual
518 {
519 public:
operator ()(const MyStruct & s1,const MyStruct & s2) const520 bool operator()(const MyStruct& s1, const MyStruct& s2) const
521 { return s1.ptr == s2.ptr; }
operator =(const MyEqual &)522 MyEqual& operator=(const MyEqual&) { return *this; }
523 };
524
525 WX_DECLARE_HASH_SET( MyStruct, MyHash, MyEqual, mySet );
526
527 typedef myTestHashSet5 wxStringHashSet;
528
wxHashSetTest()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 }
565