From 1a6d9c7680c19f25613380ab5b151806da6decb0 Mon Sep 17 00:00:00 2001 From: Mattia Barbon Date: Sun, 23 Nov 2003 08:12:34 +0000 Subject: [PATCH] New wxHashTable implementation when wxUSE_STL == 1. Replaces the old implementation based upon wxHashMap. Removed support for wxHashTable in wxHashMap. Rationale: using wxHashMap for wxHashTable implementation required special support in wxHashMap. This precluded using STL-provided hash_map to implement wxHashMap. This new implementation does not use keyed wxList interface and should be almost totally compatible with the old non-STL wxHashTable. git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@24638 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- docs/changes.txt | 2 + include/wx/hash.h | 378 +++++++++++++++++------------------- include/wx/hashmap.h | 18 +- samples/console/console.cpp | 95 +++++++-- src/common/hash.cpp | 363 +++++++++++++++++++++++++++++++++- src/common/hashmap.cpp | 33 +--- 6 files changed, 626 insertions(+), 263 deletions(-) diff --git a/docs/changes.txt b/docs/changes.txt index 1088cede39..8bf520f4c2 100644 --- a/docs/changes.txt +++ b/docs/changes.txt @@ -82,6 +82,8 @@ All: - wxFileName::Normalize(wxPATH_NORM_ALL) doesn't lower filename case any more - wxFileName::Normalize(wxPATH_NORM_ENV_VARS) now works - check if file exists in wxFileConfig::DeleteFile() (Christian Sturmlechner) +- when wxUSE_STL == 1 wxHashTable will not be implemented using wxHashMap + (as in 2.5.0). All (GUI): diff --git a/include/wx/hash.h b/include/wx/hash.h index 4fb1436c21..4196d68308 100644 --- a/include/wx/hash.h +++ b/include/wx/hash.h @@ -19,14 +19,15 @@ #include "wx/defs.h" #if !wxUSE_STL + #include "wx/object.h" #include "wx/list.h" +#else + class WXDLLIMPEXP_BASE wxObject; #endif #if WXWIN_COMPATIBILITY_2_4 #include "wx/dynarray.h" #endif -class WXDLLIMPEXP_BASE wxObject; - // the default size of the hash #define wxHASH_SIZE_DEFAULT (1000) @@ -82,9 +83,7 @@ private: DECLARE_NO_COPY_CLASS(wxHashTableBase) }; -#else - -#include "wx/hashmap.h" +#else // if wxUSE_STL #if !defined(wxENUM_KEY_TYPE_DEFINED) #define wxENUM_KEY_TYPE_DEFINED @@ -104,167 +103,116 @@ union wxHashKeyValue wxChar *string; }; -struct WXDLLIMPEXP_BASE wxHashTableHash +class WXDLLIMPEXP_BASE wxHashTableBase_Node { - wxHashTableHash() { } - wxHashTableHash( wxKeyType keyType ) : m_keyType( keyType ) { } - - wxKeyType m_keyType; + friend class WXDLLIMPEXP_BASE wxHashTableBase; + typedef class WXDLLIMPEXP_BASE wxHashTableBase_Node _Node; +public: + wxHashTableBase_Node( long key, void* value, + wxHashTableBase* table ); + wxHashTableBase_Node( const wxChar* key, void* value, + wxHashTableBase* table ); + ~wxHashTableBase_Node(); - unsigned long operator ()( const wxHashKeyValue& k ) const - { - if( m_keyType == wxKEY_STRING ) - return wxStringHash::wxCharStringHash( k.string ); - else - return (unsigned long)k.integer; - } -}; + long GetKeyInteger() const { return m_key.integer; } + const wxChar* GetKeyString() const { return m_key.string; } -struct WXDLLIMPEXP_BASE wxHashTableEqual -{ - wxHashTableEqual() { } - wxHashTableEqual( wxKeyType keyType ) : m_keyType( keyType ) { } + void* GetData() const { return m_value; } + void SetData( void* data ) { m_value = data; } - wxKeyType m_keyType; +protected: + _Node* GetNext() const { return m_next; } - bool operator ()( const wxHashKeyValue& k1, const wxHashKeyValue& k2 ) const - { - if( m_keyType == wxKEY_STRING ) - return wxStrcmp( k1.string, k2.string ) == 0; - else - return k1.integer == k2.integer; - } -}; +protected: + // next node in the chain + wxHashTableBase_Node* m_next; -WX_DECLARE_EXPORTED_HASH_MAP( wxHashKeyValue, - void*, - wxHashTableHash, - wxHashTableEqual, - wxHashTableBaseBaseBase ); + // key + wxHashKeyValue m_key; -// hack: we should really have HASH_MULTI(MAP|SET), but this requires -// less work + // value + void* m_value; -class WXDLLIMPEXP_BASE wxHashTableBaseBase : public wxHashTableBaseBaseBase -{ -public: - wxHashTableBaseBase(size_t size, const wxHashTableHash& hash, - const wxHashTableEqual& equal) - : wxHashTableBaseBaseBase(size, hash, equal) - { } - - void multi_insert(const wxHashKeyValue& key, void* value) - { - CreateNodeLast(value_type(key, value)); - } + // pointer to the hash containing the node, used to remove the + // node from the hash when the user deletes the node iterating + // through it + // TODO: move it to wxHashTable_Node (only wxHashTable supports + // iteration) + wxHashTableBase* m_hashPtr; }; class WXDLLIMPEXP_BASE wxHashTableBase +#if !wxUSE_STL + : public wxObject +#endif { + friend class WXDLLIMPEXP_BASE wxHashTableBase_Node; public: - wxHashTableBase( wxKeyType keyType = wxKEY_INTEGER, - size_t size = wxHASH_SIZE_DEFAULT ) - : m_map( size, wxHashTableHash( keyType ), - wxHashTableEqual( keyType ) ), - m_keyType( keyType ) { } - - ~wxHashTableBase() { Clear(); } - - size_t GetCount() const { return m_map.size(); } - - void Clear() - { - if( m_keyType == wxKEY_STRING ) - { - for( wxHashTableBaseBase::iterator it = m_map.begin(), - en = m_map.end(); - it != en; ) - { - wxChar* tmp = it->first.string; - ++it; - delete[] tmp; // used in operator++ - } - } - m_map.clear(); - } -protected: - void DoPut( long key, void* data ) - { - wxASSERT( m_keyType == wxKEY_INTEGER ); - - wxHashKeyValue k; k.integer = key; - m_map.multi_insert(k, data); - } + typedef wxHashTableBase_Node Node; - void DoPut( const wxChar* key, void* data ) - { - wxASSERT( m_keyType == wxKEY_STRING ); + wxHashTableBase(); + virtual ~wxHashTableBase(); - wxHashKeyValue k; - k.string = wxStrcpy(new wxChar[wxStrlen(key) + 1], key); - m_map.multi_insert(k, data); - } + void Create( wxKeyType keyType = wxKEY_INTEGER, + size_t size = wxHASH_SIZE_DEFAULT ); + void Clear(); + void Destroy(); - void* DoGet( long key ) const - { - wxASSERT( m_keyType == wxKEY_INTEGER ); + size_t GetSize() const { return m_size; } + size_t GetCount() const { return m_count; } - wxHashKeyValue k; k.integer = key; - wxHashTableBaseBase::const_iterator it = m_map.find( k ); + void DeleteContents( bool flag ) { m_deleteContents = flag; } - return it != m_map.end() ? it->second : NULL; - } + static long MakeKey(const wxChar *string); - void* DoGet( const wxChar* key ) const - { - wxASSERT( m_keyType == wxKEY_STRING ); +protected: + void DoPut( long key, long hash, void* data ); + void DoPut( const wxChar* key, long hash, void* data ); + void* DoGet( long key, long hash ) const; + void* DoGet( const wxChar* key, long hash ) const; + void* DoDelete( long key, long hash ); + void* DoDelete( const wxChar* key, long hash ); - wxHashKeyValue k; k.string = (wxChar*)key; - wxHashTableBaseBase::const_iterator it = m_map.find( k ); +private: + // Remove the node from the hash, *only called from + // ~wxHashTable*_Node destructor + void DoRemoveNode( wxHashTableBase_Node* node ); - return it != m_map.end() ? it->second : NULL; - } + // destroys data contained in the node if appropriate: + // deletes the key if it is a string and destrys + // the value if m_deleteContents is true + void DoDestroyNode( wxHashTableBase_Node* node ); - void* DoDelete( long key ) - { - wxASSERT( m_keyType == wxKEY_INTEGER ); + // inserts a node in the table (at the end of the chain) + void DoInsertNode( size_t bucket, wxHashTableBase_Node* node ); - wxHashKeyValue k; k.integer = key; - wxHashTableBaseBase::iterator it = m_map.find( k ); - - if( it != m_map.end() ) - { - void* data = it->second; + // removes a node from the table (fiven a pointer to the previous + // but does not delete it (only deletes its contents) + void DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, + wxHashTableBase_Node* prev ); - m_map.erase( it ); - return data; - } + // unconditionally deletes node value (invoking the + // correct destructor) + virtual void DoDeleteContents( wxHashTableBase_Node* node ) = 0; - return NULL; - } +protected: + // number of buckets + size_t m_size; - void* DoDelete( const wxChar* key ) - { - wxASSERT( m_keyType == wxKEY_STRING ); + // number of nodes (key/value pairs) + size_t m_count; - wxHashKeyValue k; k.string = (wxChar*)key; - wxHashTableBaseBase::iterator it = m_map.find( k ); - - if( it != m_map.end() ) - { - void* data = it->second; - wxChar* k = it->first.string; + // table + Node** m_table; - m_map.erase( it ); - delete[] k; - return data; - } + // key typ (INTEGER/STRING) + wxKeyType m_keyType; - return NULL; - } + // delete contents when hash is cleared + bool m_deleteContents; - wxHashTableBaseBase m_map; - wxKeyType m_keyType; +private: + DECLARE_NO_COPY_CLASS(wxHashTableBase) }; #endif // !wxUSE_STL @@ -354,92 +302,103 @@ private: #if wxUSE_STL -class WXDLLIMPEXP_BASE wxHashTable : protected wxHashTableBase +class WXDLLIMPEXP_BASE wxHashTable_Node : public wxHashTableBase_Node { - typedef wxHashTableBaseBase hash; + friend class WXDLLIMPEXP_BASE wxHashTable; public: - class dummy; - - struct compatibility_iterator - { - hash::iterator m_iter; - hash* m_hash; - - operator bool() const { return m_iter != m_hash->end(); } - bool operator !() const { return m_iter == m_hash->end(); } - compatibility_iterator( hash* li, hash::iterator it ) - : m_iter( it ), m_hash( li ) {} - compatibility_iterator() { } - - dummy* operator->() { return (dummy*)this; } - }; - typedef compatibility_iterator citer; - - class dummy - { - typedef hash::iterator it; - typedef compatibility_iterator citer; - public: - wxObject* GetData() const - { - citer* i = (citer*)this; - return (wxObject*)i->m_iter->second; - } - citer GetNext() const - { - citer* i = (citer*)this; - it lit = i->m_iter; - return citer( i->m_hash, ++lit ); - } - void SetData( wxObject* e ) - { - citer* i = (citer*)this; - i->m_iter->second = e; - } - private: - dummy(); - }; + wxHashTable_Node( long key, void* value, + wxHashTableBase* table ) + : wxHashTableBase_Node( key, value, table ) { } + wxHashTable_Node( const wxChar* key, void* value, + wxHashTableBase* table ) + : wxHashTableBase_Node( key, value, table ) { } + + wxObject* GetData() const + { return (wxObject*)wxHashTableBase_Node::GetData(); } + void SetData( wxObject* data ) + { wxHashTableBase_Node::SetData( data ); } + + wxHashTable_Node* GetNext() const + { return (wxHashTable_Node*)wxHashTableBase_Node::GetNext(); } +}; + +// should inherit protectedly, but it is public for compatibility in +// order to publicly inherit from wxObject +class WXDLLIMPEXP_BASE wxHashTable : public wxHashTableBase +{ + typedef wxHashTableBase hash; +public: + typedef wxHashTable_Node Node; + typedef wxHashTable_Node* compatibility_iterator; public: wxHashTable( wxKeyType keyType = wxKEY_INTEGER, size_t size = wxHASH_SIZE_DEFAULT ) - : wxHashTableBase( keyType, size ) { } + : wxHashTableBase() { Create( keyType, size ); BeginFind(); } + wxHashTable( const wxHashTable& table ); + + const wxHashTable& operator=( const wxHashTable& ); void Destroy() { Clear(); } // key and value are the same - void Put(long value, wxObject *object) { DoPut( value, object ); } - void Put(const wxChar *value, wxObject *object) { DoPut( value, object ); } + void Put(long value, wxObject *object) + { DoPut( value, value, object ); } + void Put(long hash, long value, wxObject *object) + { DoPut( value, hash, object ); } + void Put(const wxChar *value, wxObject *object) + { DoPut( value, MakeKey( value ), object ); } + void Put(long hash, const wxChar *value, wxObject *object) + { DoPut( value, hash, object ); } // key and value are the same - wxObject *Get(long value) const { return (wxObject*)DoGet( value ); } - wxObject *Get(const wxChar *value) const { return (wxObject*)DoGet( value ); } + wxObject *Get(long value) const + { return (wxObject*)DoGet( value, value ); } + wxObject *Get(long hash, long value) const + { return (wxObject*)DoGet( value, hash ); } + wxObject *Get(const wxChar *value) const + { return (wxObject*)DoGet( value, MakeKey( value ) ); } + wxObject *Get(long hash, const wxChar *value) const + { return (wxObject*)DoGet( value, hash ); } // Deletes entry and returns data if found - wxObject *Delete(long key) { return (wxObject*)DoDelete( key ); } - wxObject *Delete(const wxChar *key) { return (wxObject*)DoDelete( key ); } + wxObject *Delete(long key) + { return (wxObject*)DoDelete( key, key ); } + wxObject *Delete(long hash, long key) + { return (wxObject*)DoDelete( key, hash ); } + wxObject *Delete(const wxChar *key) + { return (wxObject*)DoDelete( key, MakeKey( key ) ); } + wxObject *Delete(long hash, const wxChar *key) + { return (wxObject*)DoDelete( key, hash ); } -#if 0 // Construct your own integer key from a string, e.g. in case // you need to combine it with something - long MakeKey(const wxChar *string) const; -#endif + long MakeKey(const wxChar *string) const + { return wxHashTableBase::MakeKey(string); } + // Way of iterating through whole hash table (e.g. to delete everything) // Not necessary, of course, if you're only storing pointers to // objects maintained separately - void BeginFind() { m_iter = citer( &this->m_map, this->m_map.begin() ); } - compatibility_iterator Next() - { - compatibility_iterator it = m_iter; - if( m_iter ) - m_iter = m_iter->GetNext(); - return it; - } + void BeginFind() { m_curr = NULL; m_currBucket = 0; } + Node* Next(); void Clear() { wxHashTableBase::Clear(); } size_t GetCount() const { return wxHashTableBase::GetCount(); } +protected: + virtual void DoDeleteContents( wxHashTableBase_Node* node ); + + // copy helper + void DoCopy( const wxHashTable& copy ); + + // searches the next node starting from bucket bucketStart and sets + // m_curr to it and m_currBucket to its bucket + void GetNextNode( size_t bucketStart ); private: - compatibility_iterator m_iter; + // current node + Node* m_curr; + + // bucket the current node belongs to + size_t m_currBucket; }; #else // if !wxUSE_STL @@ -518,7 +477,7 @@ public: // objects maintained separately void BeginFind(); - wxNode *Next(); + Node* Next(); void DeleteContents(bool flag); void Clear(); @@ -545,14 +504,25 @@ private: public: \ hashclass(wxKeyType keyType = wxKEY_INTEGER, \ size_t size = wxHASH_SIZE_DEFAULT) \ - : wxHashTableBase(keyType, size) { } \ + : wxHashTableBase() { Create(keyType, size); } \ \ ~hashclass() { Destroy(); } \ \ - void Destroy() { m_map.clear(); } \ - void Put(long key, eltype *data) { DoPut(key, (void*)data); } \ - eltype *Get(long key) const { return (eltype*)DoGet(key); } \ - eltype *Delete(long key) { return (eltype*)DoDelete(key); } \ + void Destroy() { Clear(); } \ + void Put(long key, eltype *data) { DoPut(key, key, (void*)data); } \ + void Put(long hash, long key, eltype *data) \ + { DoPut(key, hash, (void*)data); } \ + eltype *Get(long key) const { return (eltype*)DoGet(key, key); } \ + eltype *Get(long hash, long key) const \ + { return (eltype*)DoGet(key, hash); } \ + eltype *Delete(long key) { return (eltype*)DoDelete(key, key); } \ + eltype *Delete(long hash, long key) \ + { return (eltype*)DoDelete(key, hash); } \ + protected: \ + virtual void DoDeleteContents( wxHashTableBase_Node* node ) \ + { delete (eltype*)node->GetData(); } \ + \ + DECLARE_NO_COPY_CLASS(hashclass) \ } #else // if !wxUSE_STL diff --git a/include/wx/hashmap.h b/include/wx/hashmap.h index 3f2e008976..6b20a0e79f 100644 --- a/include/wx/hashmap.h +++ b/include/wx/hashmap.h @@ -70,7 +70,6 @@ protected: static void CopyHashTable( _wxHashTable_NodeBase** srcTable, size_t srcBuckets, _wxHashTableBase2* dst, _wxHashTable_NodeBase** dstTable, - size_t dstBuckets, BucketFromNode func, ProcessNode proc ); static void** AllocTable( size_t sz ) @@ -298,19 +297,6 @@ protected: \ \ return node; \ } \ - void CreateNodeLast( const value_type& value ) \ - { \ - size_t bucket = m_hasher( m_getKey(value) ) % m_tableBuckets; \ - Node* curr = m_table[bucket], \ - * next = m_table[bucket]; \ - while( next ) { curr = next; next = next->m_next(); } \ - Node** ptr = curr ? (Node**)&curr->m_nxt : &m_table[bucket]; \ - *ptr = new Node( value ); \ - /* must be after the node is inserted */ \ - ++m_items; \ - if( SHOULD_GROW( m_tableBuckets, m_items ) ) \ - ResizeTable( m_tableBuckets ); \ - } \ void CreateNode( const value_type& value ) \ {\ CreateNode(value, m_hasher( m_getKey(value) ) % m_tableBuckets ); \ @@ -358,7 +344,7 @@ protected: \ m_tableBuckets = newSize; \ \ CopyHashTable( (_wxHashTable_NodeBase**)srcTable, srcBuckets, \ - this, (_wxHashTable_NodeBase**)m_table, newSize, \ + this, (_wxHashTable_NodeBase**)m_table, \ (BucketFromNode)GetBucketForNode,\ (ProcessNode)&DummyProcessNode ); \ free(srcTable); \ @@ -370,7 +356,7 @@ protected: \ ResizeTable( ht.size() ); \ CopyHashTable( (_wxHashTable_NodeBase**)ht.m_table, ht.m_tableBuckets,\ (_wxHashTableBase2*)this, \ - (_wxHashTable_NodeBase**)m_table, m_tableBuckets, \ + (_wxHashTable_NodeBase**)m_table, \ (BucketFromNode)GetBucketForNode, \ (ProcessNode)CopyNode ); \ } \ diff --git a/samples/console/console.cpp b/samples/console/console.cpp index f6027477ca..12fe283cf4 100644 --- a/samples/console/console.cpp +++ b/samples/console/console.cpp @@ -93,7 +93,9 @@ #undef TEST_ALL static const bool TEST_ALL = true; #else - #define TEST_UNICODE + #define TEST_HASH + #define TEST_HASHMAP + #define TEST_HASHSET static const bool TEST_ALL = false; #endif @@ -1144,16 +1146,23 @@ WX_DECLARE_HASH(Foo, wxListFoos, wxHashFoos); WX_DEFINE_LIST(wxListFoos); +#include "wx/timer.h" + static void TestHash() { wxPuts(_T("*** Testing wxHashTable ***\n")); + const int COUNT = 100; + + wxStopWatch sw; + + sw.Start(); { wxHashTable hash(wxKEY_INTEGER, 10), hash2(wxKEY_STRING); wxObject o; int i; - for ( i = 0; i < 100; ++i ) + for ( i = 0; i < COUNT; ++i ) hash.Put(i, &o + i); hash.BeginFind(); @@ -1166,37 +1175,37 @@ static void TestHash() it = hash.Next(); } - if (i != 100) + if (i != COUNT) wxPuts(_T("Error in wxHashTable::compatibility_iterator\n")); for ( i = 99; i >= 0; --i ) if( hash.Get(i) != &o + i ) wxPuts(_T("Error in wxHashTable::Get/Put\n")); - for ( i = 0; i < 100; ++i ) + for ( i = 0; i < COUNT; ++i ) hash.Put(i, &o + i + 20); for ( i = 99; i >= 0; --i ) if( hash.Get(i) != &o + i) wxPuts(_T("Error (2) in wxHashTable::Get/Put\n")); - for ( i = 0; i < 50; ++i ) + for ( i = 0; i < COUNT/2; ++i ) if( hash.Delete(i) != &o + i) wxPuts(_T("Error in wxHashTable::Delete\n")); - for ( i = 50; i < 100; ++i ) + for ( i = COUNT/2; i < COUNT; ++i ) if( hash.Get(i) != &o + i) wxPuts(_T("Error (3) in wxHashTable::Get/Put\n")); - for ( i = 0; i < 50; ++i ) + for ( i = 0; i < COUNT/2; ++i ) if( hash.Get(i) != &o + i + 20) wxPuts(_T("Error (4) in wxHashTable::Put/Delete\n")); - for ( i = 0; i < 50; ++i ) + for ( i = 0; i < COUNT/2; ++i ) if( hash.Delete(i) != &o + i + 20) wxPuts(_T("Error (2) in wxHashTable::Delete\n")); - for ( i = 0; i < 50; ++i ) + for ( i = 0; i < COUNT/2; ++i ) if( hash.Get(i) != NULL) wxPuts(_T("Error (5) in wxHashTable::Put/Delete\n")); @@ -1215,7 +1224,62 @@ static void TestHash() if (hash2.Get(_T("bar")) != &o + 2) wxPuts(_T("Error (2) in wxHashTable::Get/Put\n")); } -#if !wxUSE_STL + + // 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); + + if (hash.Get(3) != NULL) + wxPuts(_T("Corner case 1 failure\n")); + + hash.Put(3, &dummy); + hash.Put(13, &dummy); + hash.Delete(3); + + if (hash.Get(3) != NULL) + wxPuts(_T("Corner case 2 failure\n")); + + hash.Delete(13); + + if (hash.Get(13) != NULL) + wxPuts(_T("Corner case 3 failure\n")); + + hash.Put(3, &dummy); + hash.Put(13, &dummy); + hash.Delete(13); + + if (hash.Get(13) != NULL) + wxPuts(_T("Corner case 4 failure\n")); + + hash.Delete(3); + + if (hash.Get(3) != NULL) + wxPuts(_T("Corner case 5 failure\n")); + } + + { + wxHashTable hash(wxKEY_INTEGER, 10); + wxObject dummy; + + hash.Put(3, 7, &dummy + 7); + hash.Put(4, 8, &dummy + 8); + + if (hash.Get(7) != NULL) wxPuts(_T("Key/Hash 1 failure\n")); + if (hash.Get(3, 7) != &dummy + 7) wxPuts(_T("Key/Hash 2 failure\n")); + if (hash.Get(4) != NULL) wxPuts(_T("Key/Hash 3 failure\n")); + if (hash.Get(3) != NULL) wxPuts(_T("Key/Hash 4 failure\n")); + if (hash.Get(8) != NULL) wxPuts(_T("Key/Hash 5 failure\n")); + if (hash.Get(8, 4) != NULL) wxPuts(_T("Key/Hash 6 failure\n")); + + if (hash.Delete(7) != NULL) wxPuts(_T("Key/Hash 7 failure\n")); + if (hash.Delete(3) != NULL) wxPuts(_T("Key/Hash 8 failure\n")); + if (hash.Delete(3, 7) != &dummy + 7) wxPuts(_T("Key/Hash 8 failure\n")); + } + { wxHashFoos hash; hash.DeleteContents(true); @@ -1264,11 +1328,20 @@ static void TestHash() { wxPuts(_T("ok (not found)")); } + + Foo* foo = hash.Delete(0); + + wxPrintf(_T("Removed 1 foo: %u foos still there\n"), Foo::count); + + delete foo; + + wxPrintf(_T("Foo deleted: %u foos left\n"), Foo::count); } -#endif wxPrintf(_T("Hash destroyed: %u foos left\n"), Foo::count); wxPuts(_T("*** Testing wxHashTable finished ***\n")); + + wxPrintf(_T("Time: %ld\n"), sw.Time()); } #endif // TEST_HASH diff --git a/src/common/hash.cpp b/src/common/hash.cpp index db33f96e28..d2a71fa8d3 100644 --- a/src/common/hash.cpp +++ b/src/common/hash.cpp @@ -666,7 +666,7 @@ void wxHashTable::BeginFind () current_node = (wxNode *) NULL; } -wxNode *wxHashTable::Next () +wxHashTable::Node* wxHashTable::Next () { wxNode *found = (wxNode *) NULL; bool end = FALSE; @@ -724,4 +724,363 @@ void wxHashTable::Clear () m_count = 0; } -#endif // !wxUSE_STL +#else // if wxUSE_STL + +#include "wx/object.h" + +wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) +{ + m_key.integer = key; +} + +wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) +{ + m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key ); +} + +wxHashTableBase_Node::~wxHashTableBase_Node() +{ + if( m_hashPtr ) m_hashPtr->DoRemoveNode( this ); +} + +// + +wxHashTableBase::wxHashTableBase() + : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ), + m_deleteContents( false ) +{ +} + +wxHashTableBase::~wxHashTableBase() +{ + Destroy(); +} + +void wxHashTableBase::Create( wxKeyType keyType, size_t size ) +{ + m_keyType = keyType; + m_size = size; + m_table = new wxHashTableBase_Node*[ m_size ]; + + for( size_t i = 0; i < m_size; ++i ) + m_table[i] = NULL; +} + +void wxHashTableBase::Clear() +{ + for( size_t i = 0; i < m_size; ++i ) + { + Node* end = m_table[i]; + + if( end == NULL ) + continue; + + Node *curr, *next = end->GetNext(); + + do + { + curr = next; + next = curr->GetNext(); + + DoDestroyNode( curr ); + + delete curr; + } + while( curr != end ); + + m_table[i] = NULL; + } + + m_count = 0; +} + +void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) +{ + size_t bucket = ( m_keyType == wxKEY_INTEGER ? + node->m_key.integer : + MakeKey( node->m_key.string ) ) % m_size; + + if( node->GetNext() == node ) + { + // single-node chain (common case) + m_table[bucket] = NULL; + } + else + { + Node *start = m_table[bucket], *curr; + Node* prev = start; + + for( curr = prev->GetNext(); curr != node; + prev = curr, curr = curr->GetNext() ); + + DoUnlinkNode( bucket, node, prev ); + } + + DoDestroyNode( node ); +} + +void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node ) +{ + // if it is called from DoRemoveNode, node has already been + // removed, from other places it does not matter + node->m_hashPtr = NULL; + + if( m_keyType == wxKEY_STRING ) + delete[] node->m_key.string; + if( m_deleteContents ) + DoDeleteContents( node ); +} + +void wxHashTableBase::Destroy() +{ + Clear(); + + delete[] m_table; + + m_table = NULL; + m_size = 0; +} + +void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node ) +{ + if( m_table[bucket] == NULL ) + { + m_table[bucket] = node->m_next = node; + } + else + { + Node *prev = m_table[bucket]; + Node *next = prev->m_next; + + prev->m_next = node; + node->m_next = next; + m_table[bucket] = node; + } + + ++m_count; +} + +void wxHashTableBase::DoPut( long key, long hash, void* data ) +{ + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); + + DoInsertNode( bucket, node ); +} + +void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data ) +{ + wxASSERT( m_keyType == wxKEY_STRING ); + + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); + + DoInsertNode( bucket, node ); +} + +void* wxHashTableBase::DoGet( long key, long hash ) const +{ + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first; + + do + { + if( curr->m_key.integer == key ) + return curr->m_value; + + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const +{ + wxASSERT( m_keyType == wxKEY_STRING ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first; + + do + { + if( wxStrcmp( curr->m_key.string, key ) == 0 ) + return curr->m_value; + + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, + wxHashTableBase_Node* prev ) +{ + if( node == m_table[bucket] ) + m_table[bucket] = prev; + + if( prev == node && prev == node->GetNext() ) + m_table[bucket] = NULL; + else + prev->m_next = node->m_next; + + DoDestroyNode( node ); + --m_count; +} + +void* wxHashTableBase::DoDelete( long key, long hash ) +{ + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; + + do + { + if( curr->m_key.integer == key ) + { + void* retval = curr->m_value; + curr->m_value = NULL; + + DoUnlinkNode( bucket, curr, prev ); + delete curr; + + return retval; + } + + prev = curr; + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +void* wxHashTableBase::DoDelete( const wxChar* key, long hash ) +{ + wxASSERT( m_keyType == wxKEY_STRING ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; + + do + { + if( wxStrcmp( curr->m_key.string, key ) == 0 ) + { + void* retval = curr->m_value; + curr->m_value = NULL; + + DoUnlinkNode( bucket, curr, prev ); + delete curr; + + return retval; + } + + prev = curr; + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +long wxHashTableBase::MakeKey( const wxChar *str ) +{ + long int_key = 0; + + while( *str ) + int_key += (wxUChar)*str++; + + return int_key; +} + +// + +wxHashTable::wxHashTable( const wxHashTable& table ) +{ + DoCopy( table ); +} + +const wxHashTable& wxHashTable::operator=( const wxHashTable& table ) +{ + Destroy(); + DoCopy( table ); + + return *this; +} + +void wxHashTable::DoCopy( const wxHashTable& table ) +{ + Create( m_keyType, m_size ); + + wxASSERT( false ); +} + +void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node ) +{ + delete ((wxHashTable_Node*)node)->GetData(); +} + +void wxHashTable::GetNextNode( size_t bucketStart ) +{ + for( size_t i = bucketStart; i < m_size; ++i ) + { + if( m_table[i] != NULL ) + { + m_curr = ((Node*)m_table[i])->GetNext(); + m_currBucket = i; + return; + } + } + + m_curr = NULL; + m_currBucket = 0; +} + +wxHashTable::Node* wxHashTable::Next() +{ + if( m_curr == NULL ) + GetNextNode( 0 ); + else + { + m_curr = m_curr->GetNext(); + + if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() ) + GetNextNode( m_currBucket + 1 ); + } + + return m_curr; +} + +#endif // wxUSE_STL diff --git a/src/common/hashmap.cpp b/src/common/hashmap.cpp index 098d789ac7..f86e192644 100644 --- a/src/common/hashmap.cpp +++ b/src/common/hashmap.cpp @@ -128,20 +128,9 @@ void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable, size_t srcBuckets, _wxHashTableBase2* dst, _wxHashTable_NodeBase** dstTable, - size_t dstBuckets, BucketFromNode func, ProcessNode proc ) { - // for compatibility with wxHashTable (to avoid reimplementig it - // from scratch), we need to preserve the order of nodes in a - // source bucket when copying the table, hence, to avoid - // allocating an auxiliary table we use a circular list for each - // bucket, and we keep the *tail* of each list in dstTable[i], to - // be able to append nodes in O(1) time. Wen we're done copying, - // we adjust dstTable[i] to point at the head of the list and we - // break the circular list into a linear one. - size_t i; - - for( i = 0; i < srcBuckets; ++i ) + for( size_t i = 0; i < srcBuckets; ++i ) { _wxHashTable_NodeBase* nextnode; @@ -151,24 +140,8 @@ void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable, nextnode = node->m_nxt; _wxHashTable_NodeBase* newnode = proc( node ); - if( dstTable[bucket] ) - { - newnode->m_nxt = dstTable[bucket]->m_nxt; // head of the list - dstTable[bucket]->m_nxt = newnode; - dstTable[bucket] = newnode; - } - else - dstTable[bucket] = newnode->m_nxt = newnode; - } - } - - for( i = 0; i < dstBuckets; ++i ) - { - if( dstTable[i] ) - { - _wxHashTable_NodeBase* tmp = dstTable[i]; - dstTable[i] = dstTable[i]->m_nxt; - tmp->m_nxt = NULL; + newnode->m_nxt = dstTable[bucket]; + dstTable[bucket] = newnode; } } } -- 2.45.2