[wxWidgets.git] / tests / hashes / hashes.cpp

///////////////////////////////////////////////////////////////////////////////
// Name:        tests/hashes/hashes.cpp
// Purpose:     wxHashTable, wxHashMap, wxHashSet unit test
// Author:      Vadim Zeitlin, Mattia Barbon
// Modified:    Mike Wetherell
// Created:     2004-05-16
// Copyright:   (c) 2004 Vadim Zeitlin, Mattia Barbon, 2005 M. Wetherell
///////////////////////////////////////////////////////////////////////////////

// ----------------------------------------------------------------------------
// headers
// ----------------------------------------------------------------------------

#include "testprec.h"

#ifdef __BORLANDC__
    #pragma hdrstop
#endif

#ifndef WX_PRECOMP
    #include "wx/wx.h"
#endif // WX_PRECOMP

#include "wx/hash.h"
#include "wx/hashmap.h"
#include "wx/hashset.h"

#if defined wxLongLong_t && !defined wxLongLongIsLong && \
        (!defined __VISUALC__ || __VISUALC__ > 1100)    // doesn't work on VC5
    #define TEST_LONGLONG
#endif

// --------------------------------------------------------------------------
// helper class for typed/untyped wxHashTable
// --------------------------------------------------------------------------

struct Foo
{
    Foo(int n_) { n = n_; count++; }
    ~Foo() { count--; }

    int n;

    static size_t count;
};

size_t Foo::count = 0;

struct FooObject : public wxObject
{
    FooObject(int n_) { n = n_; count++; }
    ~FooObject() { count--; }

    int n;

    static size_t count;
};

size_t FooObject::count = 0;

// --------------------------------------------------------------------------
// test class
// --------------------------------------------------------------------------

class HashesTestCase : public CppUnit::TestCase
{
public:
    HashesTestCase() { }

private:
    CPPUNIT_TEST_SUITE( HashesTestCase );
        CPPUNIT_TEST( wxHashTableTest );
        CPPUNIT_TEST( wxUntypedHashTableDeleteContents );
        CPPUNIT_TEST( wxTypedHashTableTest );
        CPPUNIT_TEST( StringHashMapTest );
        CPPUNIT_TEST( PtrHashMapTest );
        CPPUNIT_TEST( LongHashMapTest );
        CPPUNIT_TEST( ULongHashMapTest );
        CPPUNIT_TEST( UIntHashMapTest );
        CPPUNIT_TEST( IntHashMapTest );
        CPPUNIT_TEST( ShortHashMapTest );
        CPPUNIT_TEST( UShortHashMapTest );
#ifdef TEST_LONGLONG
        CPPUNIT_TEST( LLongHashMapTest );
        CPPUNIT_TEST( ULLongHashMapTest );
#endif
        CPPUNIT_TEST( wxHashSetTest );
    CPPUNIT_TEST_SUITE_END();

    void wxHashTableTest();
    void wxUntypedHashTableDeleteContents();
    void wxTypedHashTableTest();
    void StringHashMapTest();
    void PtrHashMapTest();
    void LongHashMapTest();
    void ULongHashMapTest();
    void UIntHashMapTest();
    void IntHashMapTest();
    void ShortHashMapTest();
    void UShortHashMapTest();
#ifdef TEST_LONGLONG
    void LLongHashMapTest();
    void ULLongHashMapTest();
#endif
    void wxHashSetTest();

    DECLARE_NO_COPY_CLASS(HashesTestCase)
};

// register in the unnamed registry so that these tests are run by default
CPPUNIT_TEST_SUITE_REGISTRATION( HashesTestCase );

// also include in its own registry so that these tests can be run alone
CPPUNIT_TEST_SUITE_NAMED_REGISTRATION( HashesTestCase, "HashesTestCase" );

void HashesTestCase::wxHashTableTest()
{
    const int COUNT = 100;

    {
        wxHashTable hash(wxKEY_INTEGER, 10), hash2(wxKEY_STRING);
        wxObject o;
        int i;

        for ( i = 0; i < COUNT; ++i )
            hash.Put(i, &o + i);

        hash.BeginFind();
        wxHashTable::compatibility_iterator it = hash.Next();
        i = 0;

        while (it)
        {
            ++i;
            it = hash.Next();
        }

        CPPUNIT_ASSERT( i == COUNT );

        for ( i = 99; i >= 0; --i )
            CPPUNIT_ASSERT( hash.Get(i) == &o + i );

        for ( i = 0; i < COUNT; ++i )
            hash.Put(i, &o + i + 20);

        for ( i = 99; i >= 0; --i )
            CPPUNIT_ASSERT( hash.Get(i) == &o + i);

        for ( i = 0; i < COUNT/2; ++i )
            CPPUNIT_ASSERT( hash.Delete(i) == &o + i);

        for ( i = COUNT/2; i < COUNT; ++i )
            CPPUNIT_ASSERT( hash.Get(i) == &o + i);

        for ( i = 0; i < COUNT/2; ++i )
            CPPUNIT_ASSERT( hash.Get(i) == &o + i + 20);

        for ( i = 0; i < COUNT/2; ++i )
            CPPUNIT_ASSERT( hash.Delete(i) == &o + i + 20);

        for ( i = 0; i < COUNT/2; ++i )
            CPPUNIT_ASSERT( hash.Get(i) == NULL);

        hash2.Put(wxT("foo"), &o + 1);
        hash2.Put(wxT("bar"), &o + 2);
        hash2.Put(wxT("baz"), &o + 3);

        CPPUNIT_ASSERT(hash2.Get(wxT("moo")) == NULL);
        CPPUNIT_ASSERT(hash2.Get(wxT("bar")) == &o + 2);

        hash2.Put(wxT("bar"), &o + 0);

        CPPUNIT_ASSERT(hash2.Get(wxT("bar")) == &o + 2);
    }

    // and now some corner-case testing; 3 and 13 hash to the same bucket
    {
        wxHashTable hash(wxKEY_INTEGER, 10);
        wxObject dummy;

        hash.Put(3, &dummy);
        hash.Delete(3);

        CPPUNIT_ASSERT(hash.Get(3) == NULL);

        hash.Put(3, &dummy);
        hash.Put(13, &dummy);
        hash.Delete(3);

        CPPUNIT_ASSERT(hash.Get(3) == NULL);

        hash.Delete(13);

        CPPUNIT_ASSERT(hash.Get(13) == NULL);

        hash.Put(3, &dummy);
        hash.Put(13, &dummy);
        hash.Delete(13);

        CPPUNIT_ASSERT(hash.Get(13) == NULL);

        hash.Delete(3);

        CPPUNIT_ASSERT(hash.Get(3) == NULL);
    }

    // test for key + value access (specifically that supplying either
    // wrong key or wrong value returns NULL)
    {
        wxHashTable hash(wxKEY_INTEGER, 10);
        wxObject dummy;

        hash.Put(3, 7, &dummy + 7);
        hash.Put(4, 8, &dummy + 8);

        CPPUNIT_ASSERT(hash.Get(7) == NULL);
        CPPUNIT_ASSERT(hash.Get(3, 7) == &dummy + 7);
        CPPUNIT_ASSERT(hash.Get(4) == NULL);
        CPPUNIT_ASSERT(hash.Get(3) == NULL);
        CPPUNIT_ASSERT(hash.Get(8) == NULL);
        CPPUNIT_ASSERT(hash.Get(8, 4) == NULL);

        CPPUNIT_ASSERT(hash.Delete(7) == NULL);
        CPPUNIT_ASSERT(hash.Delete(3) == NULL);
        CPPUNIT_ASSERT(hash.Delete(3, 7) == &dummy + 7);
    }

}

void HashesTestCase::wxUntypedHashTableDeleteContents()
{
    // need a nested scope for destruction
    {
        wxHashTable hash;
        hash.DeleteContents(true);

        CPPUNIT_ASSERT( hash.GetCount() == 0 );
        CPPUNIT_ASSERT( FooObject::count == 0 );

        static const int hashTestData[] =
        {
            0, 1, 17, -2, 2, 4, -4, 345, 3, 3, 2, 1,
        };

        size_t n;
        for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
        {
            hash.Put(hashTestData[n], n, new FooObject(n));
        }

        CPPUNIT_ASSERT( hash.GetCount() == WXSIZEOF(hashTestData) );
        CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) );

        // delete from hash without deleting object
        FooObject* foo = (FooObject*)hash.Delete(0l);

        CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) );
        delete foo;
        CPPUNIT_ASSERT( FooObject::count == WXSIZEOF(hashTestData) - 1 );
    }

    // hash destroyed
    CPPUNIT_ASSERT( FooObject::count == 0 );
}

WX_DECLARE_HASH(Foo, wxListFoos, wxHashFoos);

void HashesTestCase::wxTypedHashTableTest()
{
    // need a nested scope for destruction
    {
        wxHashFoos hash;
        hash.DeleteContents(true);

        CPPUNIT_ASSERT( hash.GetCount() == 0 );
        CPPUNIT_ASSERT( Foo::count == 0 );

        static const int hashTestData[] =
        {
            0, 1, 17, -2, 2, 4, -4, 345, 3, 3, 2, 1,
        };

        size_t n;
        for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
        {
            hash.Put(hashTestData[n], n, new Foo(n));
        }

        CPPUNIT_ASSERT( hash.GetCount() == WXSIZEOF(hashTestData) );
        CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) );

        for ( n = 0; n < WXSIZEOF(hashTestData); n++ )
        {
            Foo *foo = hash.Get(hashTestData[n], n);

            CPPUNIT_ASSERT( foo != NULL );
            CPPUNIT_ASSERT( foo->n == (int)n );
        }

        // element not in hash
        CPPUNIT_ASSERT( hash.Get(1234) == NULL );
        CPPUNIT_ASSERT( hash.Get(1, 0) == NULL );

        // delete from hash without deleting object
        Foo* foo = hash.Delete(0);

        CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) );
        delete foo;
        CPPUNIT_ASSERT( Foo::count == WXSIZEOF(hashTestData) - 1 );
    }

    // hash destroyed
    CPPUNIT_ASSERT( Foo::count == 0 );
}

// test compilation of basic map types
WX_DECLARE_HASH_MAP( int*, int*, wxPointerHash, wxPointerEqual, myPtrHashMap );
WX_DECLARE_HASH_MAP( long, long, wxIntegerHash, wxIntegerEqual, myLongHashMap );
WX_DECLARE_HASH_MAP( unsigned long, unsigned, wxIntegerHash, wxIntegerEqual,
                     myUnsignedHashMap );
WX_DECLARE_HASH_MAP( unsigned int, unsigned, wxIntegerHash, wxIntegerEqual,
                     myTestHashMap1 );
WX_DECLARE_HASH_MAP( int, unsigned, wxIntegerHash, wxIntegerEqual,
                     myTestHashMap2 );
WX_DECLARE_HASH_MAP( short, unsigned, wxIntegerHash, wxIntegerEqual,
                     myTestHashMap3 );
WX_DECLARE_HASH_MAP( unsigned short, unsigned, wxIntegerHash, wxIntegerEqual,
                     myTestHashMap4 );

// same as:
// WX_DECLARE_HASH_MAP( wxString, wxString, wxStringHash, wxStringEqual,
//                      myStringHashMap );
WX_DECLARE_STRING_HASH_MAP(wxString, myStringHashMap);

#ifdef TEST_LONGLONG
    WX_DECLARE_HASH_MAP( wxLongLong_t, wxLongLong_t,
                         wxIntegerHash, wxIntegerEqual, myLLongHashMap );
    WX_DECLARE_HASH_MAP( wxULongLong_t, wxULongLong_t,
                         wxIntegerHash, wxIntegerEqual, myULLongHashMap );
#endif

// Helpers to generate a key value pair for item 'i', out of a total of 'count'
void MakeKeyValuePair(size_t i, size_t /*count*/, wxString& key, wxString& val)
{
    key.clear();
    key << i;
    val = wxT("A") + key + wxT("C");
}

// for integral keys generate a range of keys that will use all the bits of
// the key type
template <class IntT, class KeyT>
IntT MakeKey(size_t i, size_t count)
{
    IntT max = 1;
    max <<= sizeof(KeyT) * 8 - 2;
    max -= count / 4 + 1;

    return max / count * 4 * i + i / 3;
}

// make key/value pairs for integer types
template <class KeyT, class ValueT>
void MakeKeyValuePair(size_t i, size_t count, KeyT& key, ValueT& value)
{
    key = MakeKey<KeyT, KeyT>(i, count);
    value = wx_truncate_cast(ValueT, key);
}

// make key/values paris for pointer types
template <class T, class ValueT>
void MakeKeyValuePair(size_t i, size_t count, T*& key, ValueT& value)
{
    key = (T*)wxUIntToPtr(MakeKey<wxUIntPtr, T*>(i, count));
    value = wx_truncate_cast(ValueT, key);
}

// the test
template <class HashMapT>
void HashMapTest()
{
    typedef typename HashMapT::value_type::second_type value_type;
    typedef typename HashMapT::key_type key_type;
    typedef typename HashMapT::iterator Itor;

    HashMapT sh(0); // as small as possible
    key_type buf;
    value_type value;
    size_t i;
    const size_t count = 10000;

    // init with some data
    for( i = 0; i < count; ++i )
    {
        MakeKeyValuePair(i, count, buf, value);
        sh[buf] = value;
    }

    // test that insertion worked
    CPPUNIT_ASSERT( sh.size() == count );

    for( i = 0; i < count; ++i )
    {
        MakeKeyValuePair(i, count, buf, value);
        CPPUNIT_ASSERT( sh[buf] == value );
    }

    // check that iterators work
    Itor it;
    for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i )
    {
        CPPUNIT_ASSERT( i != count );
        CPPUNIT_ASSERT( it->second == sh[it->first] );
    }

    CPPUNIT_ASSERT( sh.size() == i );

    // test copy ctor, assignment operator
    HashMapT h1( sh ), h2( 0 );
    h2 = sh;

    for( i = 0, it = sh.begin(); it != sh.end(); ++it, ++i )
    {
        CPPUNIT_ASSERT( h1[it->first] == it->second );
        CPPUNIT_ASSERT( h2[it->first] == it->second );
    }

    // other tests
    for( i = 0; i < count; ++i )
    {
        MakeKeyValuePair(i, count, buf, value);
        size_t sz = sh.size();

        // test find() and erase(it)
        if( i < 100 )
        {
            it = sh.find( buf );
            CPPUNIT_ASSERT( it != sh.end() );

            sh.erase( it );

            CPPUNIT_ASSERT( sh.find( buf ) == sh.end() );
        }
        else
        // test erase(key)
        {
            size_t c = sh.erase( buf );
            CPPUNIT_ASSERT( c == 1 );
            CPPUNIT_ASSERT( sh.find( buf ) == sh.end() );
        }

        // count should decrease
        CPPUNIT_ASSERT( sh.size() == sz - 1 );
    }
}

void HashesTestCase::StringHashMapTest() { HashMapTest<myStringHashMap>();   }
void HashesTestCase::PtrHashMapTest()    { HashMapTest<myPtrHashMap>();      }
void HashesTestCase::LongHashMapTest()   { HashMapTest<myLongHashMap>();     }
void HashesTestCase::ULongHashMapTest()  { HashMapTest<myUnsignedHashMap>(); }
void HashesTestCase::UIntHashMapTest()   { HashMapTest<myTestHashMap1>();    }
void HashesTestCase::IntHashMapTest()    { HashMapTest<myTestHashMap2>();    }
void HashesTestCase::ShortHashMapTest()  { HashMapTest<myTestHashMap3>();    }
void HashesTestCase::UShortHashMapTest() { HashMapTest<myTestHashMap4>();    }

#ifdef TEST_LONGLONG
void HashesTestCase::LLongHashMapTest()  { HashMapTest<myLLongHashMap>();    }
void HashesTestCase::ULLongHashMapTest() { HashMapTest<myULLongHashMap>();   }
#endif

#ifdef __VISUALC__
    #if __VISUALC__ <= 1200
        #pragma warning(disable:4284) // operator->() returns a non-UDT
    #endif
#endif // __VISUALC__

// test compilation of basic set types
WX_DECLARE_HASH_SET( int*, wxPointerHash, wxPointerEqual, myPtrHashSet );
WX_DECLARE_HASH_SET( long, wxIntegerHash, wxIntegerEqual, myLongHashSet );
WX_DECLARE_HASH_SET( unsigned long, wxIntegerHash, wxIntegerEqual,
                     myUnsignedHashSet );
WX_DECLARE_HASH_SET( unsigned int, wxIntegerHash, wxIntegerEqual,
                     myTestHashSet1 );
WX_DECLARE_HASH_SET( int, wxIntegerHash, wxIntegerEqual,
                     myTestHashSet2 );
WX_DECLARE_HASH_SET( short, wxIntegerHash, wxIntegerEqual,
                     myTestHashSet3 );
WX_DECLARE_HASH_SET( unsigned short, wxIntegerHash, wxIntegerEqual,
                     myTestHashSet4 );
WX_DECLARE_HASH_SET( wxString, wxStringHash, wxStringEqual,
                     myTestHashSet5 );

struct MyStruct
{
    int* ptr;
    wxString str;
};

class MyHash
{
public:
    unsigned long operator()(const MyStruct& s) const
        { return m_dummy(s.ptr); }
    MyHash& operator=(const MyHash&) { return *this; }
private:
    wxPointerHash m_dummy;
};

class MyEqual
{
public:
    bool operator()(const MyStruct& s1, const MyStruct& s2) const
        { return s1.ptr == s2.ptr; }
    MyEqual& operator=(const MyEqual&) { return *this; }
};

WX_DECLARE_HASH_SET( MyStruct, MyHash, MyEqual, mySet );

typedef myTestHashSet5 wxStringHashSet;

void HashesTestCase::wxHashSetTest()
{
    wxStringHashSet set1;

    set1.insert( wxT("abc") );

    CPPUNIT_ASSERT( set1.size() == 1 );

    set1.insert( wxT("bbc") );
    set1.insert( wxT("cbc") );

    CPPUNIT_ASSERT( set1.size() == 3 );

    set1.insert( wxT("abc") );

    CPPUNIT_ASSERT( set1.size() == 3 );

    mySet set2;
    int dummy;
    MyStruct tmp;

    tmp.ptr = &dummy; tmp.str = wxT("ABC");
    set2.insert( tmp );
    tmp.ptr = &dummy + 1;
    set2.insert( tmp );
    tmp.ptr = &dummy; tmp.str = wxT("CDE");
    set2.insert( tmp );

    CPPUNIT_ASSERT( set2.size() == 2 );

    mySet::iterator it = set2.find( tmp );

    CPPUNIT_ASSERT( it != set2.end() );
    CPPUNIT_ASSERT( it->ptr == &dummy );
    CPPUNIT_ASSERT( it->str == wxT("ABC") );
}
Commit	Line	Data
cbca1e08 MB	1	///////////////////////////////////////////////////////////////////////////////
cbca1e08 MB	2	// Name: tests/hashes/hashes.cpp
7d9cfc54	3	// Purpose: wxHashTable, wxHashMap, wxHashSet unit test
cbca1e08	4	// Author: Vadim Zeitlin, Mattia Barbon
d8b6309b	5	// Modified: Mike Wetherell
cbca1e08	6	// Created: 2004-05-16
d8b6309b	7	// Copyright: (c) 2004 Vadim Zeitlin, Mattia Barbon, 2005 M. Wetherell
cbca1e08 MB	8	///////////////////////////////////////////////////////////////////////////////
	9
	10	// ----------------------------------------------------------------------------
	11	// headers
	12	// ----------------------------------------------------------------------------
	13
8899b155	14	#include "testprec.h"
cbca1e08 MB	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
d8b6309b MW	28	#if defined wxLongLong_t && !defined wxLongLongIsLong && \
	29	(!defined __VISUALC__ \|\| __VISUALC__ > 1100) // doesn't work on VC5
	30	#define TEST_LONGLONG
	31	#endif
	32
cbca1e08 MB	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 );
d8b6309b MW	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
cbca1e08 MB	87	CPPUNIT_TEST( wxHashSetTest );
	88	CPPUNIT_TEST_SUITE_END();
	89
	90	void wxHashTableTest();
	91	void wxUntypedHashTableDeleteContents();
	92	void wxTypedHashTableTest();
d8b6309b MW	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
cbca1e08 MB	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
e3778b4d	113	// also include in its own registry so that these tests can be run alone
cbca1e08 MB	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
9a83f860 VZ	164	hash2.Put(wxT("foo"), &o + 1);
	165	hash2.Put(wxT("bar"), &o + 2);
	166	hash2.Put(wxT("baz"), &o + 3);
cbca1e08	167
9a83f860 VZ	168	CPPUNIT_ASSERT(hash2.Get(wxT("moo")) == NULL);
9a83f860 VZ	169	CPPUNIT_ASSERT(hash2.Get(wxT("bar")) == &o + 2);
cbca1e08	170
9a83f860	171	hash2.Put(wxT("bar"), &o + 0);
cbca1e08	172
9a83f860	173	CPPUNIT_ASSERT(hash2.Get(wxT("bar")) == &o + 2);
cbca1e08 MB	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
cbca1e08 MB	266	WX_DECLARE_HASH(Foo, wxListFoos, wxHashFoos);
cbca1e08 MB	267
cbca1e08 MB	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
7d9cfc54 MB	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
d8b6309b MW	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;
d7ad5a02	358
d8b6309b MW	359	return max / count * 4 * i + i / 3;
d8b6309b MW	360	}
7d9cfc54	361
d8b6309b MW	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)
cbca1e08	365	{
d8b6309b MW	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	{
d8b6309b	382	typedef typename HashMapT::value_type::second_type value_type;
d8b6309b MW	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;
7d9cfc54 MB	389	size_t i;
	390	const size_t count = 10000;
	391
	392	// init with some data
	393	for( i = 0; i < count; ++i )
	394	{
d8b6309b MW	395	MakeKeyValuePair(i, count, buf, value);
d8b6309b MW	396	sh[buf] = value;
7d9cfc54 MB	397	}
	398
	399	// test that insertion worked
	400	CPPUNIT_ASSERT( sh.size() == count );
	401
	402	for( i = 0; i < count; ++i )
	403	{
d8b6309b MW	404	MakeKeyValuePair(i, count, buf, value);
d8b6309b MW	405	CPPUNIT_ASSERT( sh[buf] == value );
7d9cfc54 MB	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
d8b6309b	419	HashMapT h1( sh ), h2( 0 );
7d9cfc54 MB	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	{
d8b6309b	431	MakeKeyValuePair(i, count, buf, value);
7d9cfc54 MB	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	}
cbca1e08 MB	455	}
cbca1e08 MB	456
d8b6309b MW	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
5098c258 VZ	471	#ifdef __VISUALC__
	472	#if __VISUALC__ <= 1200
	473	#pragma warning(disable:4284) // operator->() returns a non-UDT
	474	#endif
	475	#endif // __VISUALC__
	476
7d9cfc54 MB	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
cbca1e08 MB	521	void HashesTestCase::wxHashSetTest()
cbca1e08 MB	522	{
7d9cfc54 MB	523	wxStringHashSet set1;
7d9cfc54 MB	524
9a83f860	525	set1.insert( wxT("abc") );
7d9cfc54 MB	526
	527	CPPUNIT_ASSERT( set1.size() == 1 );
	528
9a83f860 VZ	529	set1.insert( wxT("bbc") );
9a83f860 VZ	530	set1.insert( wxT("cbc") );
7d9cfc54 MB	531
	532	CPPUNIT_ASSERT( set1.size() == 3 );
	533
9a83f860	534	set1.insert( wxT("abc") );
7d9cfc54 MB	535
	536	CPPUNIT_ASSERT( set1.size() == 3 );
	537
	538	mySet set2;
	539	int dummy;
	540	MyStruct tmp;
	541
9a83f860	542	tmp.ptr = &dummy; tmp.str = wxT("ABC");
7d9cfc54 MB	543	set2.insert( tmp );
	544	tmp.ptr = &dummy + 1;
	545	set2.insert( tmp );
9a83f860	546	tmp.ptr = &dummy; tmp.str = wxT("CDE");
7d9cfc54 MB	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 );
9a83f860	555	CPPUNIT_ASSERT( it->str == wxT("ABC") );
cbca1e08	556	}