X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/d8274c928e8a68e6514d07d4dd268aaf8167db17..5687a67ce1e365d010c6282aa57b4f99f7f5ea29:/include/wx/hash.h diff --git a/include/wx/hash.h b/include/wx/hash.h index 280c91e83e..247a844637 100644 --- a/include/wx/hash.h +++ b/include/wx/hash.h @@ -12,21 +12,30 @@ #ifndef _WX_HASH_H__ #define _WX_HASH_H__ -#if defined(__GNUG__) && !defined(__APPLE__) +#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) #pragma interface "hash.h" #endif #include "wx/defs.h" +#if !wxUSE_STL && WXWIN_COMPATIBILITY_2_4 + #define wxUSE_OLD_HASH_TABLE 1 +#else + #define wxUSE_OLD_HASH_TABLE 0 +#endif + #if !wxUSE_STL + #include "wx/object.h" +#else + class WXDLLIMPEXP_BASE wxObject; +#endif +#if wxUSE_OLD_HASH_TABLE #include "wx/list.h" #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) @@ -42,7 +51,7 @@ class WXDLLIMPEXP_BASE wxObject; // pointers to objects // ---------------------------------------------------------------------------- -#if !wxUSE_STL +#if wxUSE_OLD_HASH_TABLE class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject { @@ -82,9 +91,7 @@ private: DECLARE_NO_COPY_CLASS(wxHashTableBase) }; -#else - -#include "wx/hashmap.h" +#else // if !wxUSE_OLD_HASH_TABLE #if !defined(wxENUM_KEY_TYPE_DEFINED) #define wxENUM_KEY_TYPE_DEFINED @@ -104,162 +111,123 @@ union wxHashKeyValue wxChar *string; }; -struct WXDLLIMPEXP_BASE wxHashTableHash +// for some compilers (AIX xlC), defining it as friend inside the class is not +// enough, so provide a real forward declaration +class WXDLLIMPEXP_BASE wxHashTableBase; + +class WXDLLIMPEXP_BASE wxHashTableBase_Node { - wxHashTableHash() { } - wxHashTableHash( wxKeyType keyType ) : m_keyType( 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(); - wxKeyType m_keyType; + long GetKeyInteger() const { return m_key.integer; } + const wxChar* GetKeyString() const { return m_key.string; } - unsigned long operator ()( const wxHashKeyValue& k ) const - { - if( m_keyType == wxKEY_STRING ) - return wxStringHash::wxCharStringHash( k.string ); - else - return (unsigned long)k.integer; - } -}; + void* GetData() const { return m_value; } + void SetData( void* data ) { m_value = data; } -struct WXDLLIMPEXP_BASE wxHashTableEqual -{ - wxHashTableEqual() { } - wxHashTableEqual( wxKeyType keyType ) : m_keyType( keyType ) { } +protected: + _Node* GetNext() const { return m_next; } - wxKeyType m_keyType; +protected: + // next node in the chain + wxHashTableBase_Node* 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; - } -}; + // key + wxHashKeyValue m_key; -WX_DECLARE_EXPORTED_HASH_MAP( wxHashKeyValue, - void*, - wxHashTableHash, - wxHashTableEqual, - wxHashTableBaseBase ); + // value + void* m_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 ); + typedef wxHashTableBase_Node Node; - wxHashKeyValue k; k.integer = key; - m_map[k] = data; - } + wxHashTableBase(); + virtual ~wxHashTableBase() { }; - void DoPut( const wxChar* key, void* data ) - { - wxASSERT( m_keyType == wxKEY_STRING ); - - wxHashKeyValue k; - k.string = (wxChar*)key; - wxHashTableBaseBase::iterator it = m_map.find(k); - - if( it == m_map.end() ) - { - k.string = new wxChar[wxStrlen(key) + 1]; - wxStrcpy(k.string, key); - m_map[k] = data; - } - else - it->second = 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 +#endif // wxUSE_OLD_HASH_TABLE #if !wxUSE_STL @@ -317,10 +285,10 @@ public: void Put(long key, const wxString& value); // get the string from the key: if not found, an empty string is returned - // and the wasFound is set to FALSE if not NULL + // and the wasFound is set to false if not NULL wxString Get(long key, bool *wasFound = NULL) const; - // remove the item, returning TRUE if the item was found and deleted + // remove the item, returning true if the item was found and deleted bool Delete(long key) const; // clean up @@ -338,111 +306,121 @@ private: #endif // WXWIN_COMPATIBILITY_2_4 -#endif // !wxUSE_STL +#endif // !wxUSE_STL // ---------------------------------------------------------------------------- // for compatibility only // ---------------------------------------------------------------------------- -#if wxUSE_STL +#if !wxUSE_OLD_HASH_TABLE + +class WXDLLIMPEXP_BASE wxHashTable_Node : public wxHashTableBase_Node +{ + friend class WXDLLIMPEXP_BASE wxHashTable; +public: + 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(); } +}; -class WXDLLIMPEXP_BASE wxHashTable : protected wxHashTableBase +// should inherit protectedly, but it is public for compatibility in +// order to publicly inherit from wxObject +class WXDLLIMPEXP_BASE wxHashTable : public wxHashTableBase { - typedef wxHashTableBaseBase hash; + typedef wxHashTableBase hash; 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 ); - } - citer GetPrevious() 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(); - }; + 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 ); - void Destroy() { Clear(); } + virtual ~wxHashTable() { Destroy(); } + + const wxHashTable& operator=( const wxHashTable& ); // 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*)DoGet( key ); } - wxObject *Delete(const wxChar *key) { return (wxObject*)DoGet( 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 +#else // if wxUSE_OLD_HASH_TABLE class WXDLLIMPEXP_BASE wxHashTable : public wxObject { public: + typedef wxNode Node; + typedef wxNode* compatibility_iterator; + int n; int current_position; wxNode *current_node; @@ -511,7 +489,7 @@ public: // objects maintained separately void BeginFind(); - wxNode *Next(); + Node* Next(); void DeleteContents(bool flag); void Clear(); @@ -519,7 +497,6 @@ public: // Returns number of nodes size_t GetCount() const { return m_count; } - typedef wxNode* compatibility_iterator; private: size_t m_count; // number of elements in the hashtable bool m_deleteContents; @@ -527,9 +504,9 @@ private: DECLARE_DYNAMIC_CLASS(wxHashTable) }; -#endif +#endif // wxUSE_OLD_HASH_TABLE -#if wxUSE_STL +#if !wxUSE_OLD_HASH_TABLE // defines a new type safe hash table which stores the elements of type eltype // in lists of class listclass @@ -539,17 +516,27 @@ private: public: \ hashclass(wxKeyType keyType = wxKEY_INTEGER, \ size_t size = wxHASH_SIZE_DEFAULT) \ - : wxHashTableBase(keyType, size) { } \ + : wxHashTableBase() { Create(keyType, size); } \ \ - ~hashclass() { Destroy(); } \ + virtual ~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 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 +#else // if wxUSE_OLD_HASH_TABLE #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \ classexp hashclass : public wxHashTableBase \ @@ -601,7 +588,7 @@ private: { \ m_hashTable[slot] = new listclass(m_keyType); \ if ( m_deleteContents ) \ - m_hashTable[slot]->DeleteContents(TRUE); \ + m_hashTable[slot]->DeleteContents(true); \ } \ \ ((listclass *)m_hashTable[slot])->Append(value, data); \ @@ -611,7 +598,7 @@ private: DECLARE_NO_COPY_CLASS(hashclass) \ } -#endif +#endif // wxUSE_OLD_HASH_TABLE // this macro is to be used in the user code #define WX_DECLARE_HASH(el, list, hash) \