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