X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/a95e38c03464c854af73b960b17db12624bd8f8c..0093fe11c5f581abbc37447b191903e871112f46:/include/wx/hash.h?ds=sidebyside diff --git a/include/wx/hash.h b/include/wx/hash.h index cf10d040c8..3720dd0c1f 100644 --- a/include/wx/hash.h +++ b/include/wx/hash.h @@ -12,12 +12,20 @@ #ifndef _WX_HASH_H__ #define _WX_HASH_H__ -#ifdef __GNUG__ +#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) #pragma interface "hash.h" #endif -#include "wx/list.h" -#include "wx/dynarray.h" +#include "wx/defs.h" + +#if !wxUSE_STL + #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) @@ -34,7 +42,9 @@ // pointers to objects // ---------------------------------------------------------------------------- -class WXDLLEXPORT wxHashTableBase : public wxObject +#if !wxUSE_STL + +class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject { public: wxHashTableBase(); @@ -69,17 +79,209 @@ protected: private: // no copy ctor/assignment operator (yet) - DECLARE_NO_COPY_CLASS(wxHashTableBase); + DECLARE_NO_COPY_CLASS(wxHashTableBase) +}; + +#else + +#include "wx/hashmap.h" + +#if !defined(wxENUM_KEY_TYPE_DEFINED) +#define wxENUM_KEY_TYPE_DEFINED + +enum wxKeyType +{ + wxKEY_NONE, + wxKEY_INTEGER, + wxKEY_STRING +}; + +#endif + +union wxHashKeyValue +{ + long integer; + wxChar *string; +}; + +struct WXDLLIMPEXP_BASE wxHashTableHash +{ + wxHashTableHash() { } + wxHashTableHash( wxKeyType keyType ) : m_keyType( keyType ) { } + + wxKeyType m_keyType; + + unsigned long operator ()( const wxHashKeyValue& k ) const + { + if( m_keyType == wxKEY_STRING ) + return wxStringHash::wxCharStringHash( k.string ); + else + return (unsigned long)k.integer; + } +}; + +struct WXDLLIMPEXP_BASE wxHashTableEqual +{ + wxHashTableEqual() { } + wxHashTableEqual( wxKeyType keyType ) : m_keyType( keyType ) { } + + wxKeyType m_keyType; + + 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; + } +}; + +WX_DECLARE_EXPORTED_HASH_MAP( wxHashKeyValue, + void*, + wxHashTableHash, + wxHashTableEqual, + wxHashTableBaseBaseBase ); + +// hack: we should really have HASH_MULTI(MAP|SET), but this requires +// less work + +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)); + } +}; + +class WXDLLIMPEXP_BASE wxHashTableBase +{ +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); + } + + void DoPut( const wxChar* key, void* data ) + { + wxASSERT( m_keyType == wxKEY_STRING ); + + wxHashKeyValue k; + k.string = wxStrcpy(new wxChar[wxStrlen(key) + 1], key); + m_map.multi_insert(k, data); + } + + void* DoGet( long key ) const + { + wxASSERT( m_keyType == wxKEY_INTEGER ); + + wxHashKeyValue k; k.integer = key; + wxHashTableBaseBase::const_iterator it = m_map.find( k ); + + return it != m_map.end() ? it->second : NULL; + } + + void* DoGet( const wxChar* key ) const + { + wxASSERT( m_keyType == wxKEY_STRING ); + + wxHashKeyValue k; k.string = (wxChar*)key; + wxHashTableBaseBase::const_iterator it = m_map.find( k ); + + return it != m_map.end() ? it->second : NULL; + } + + void* DoDelete( long key ) + { + wxASSERT( m_keyType == wxKEY_INTEGER ); + + wxHashKeyValue k; k.integer = key; + wxHashTableBaseBase::iterator it = m_map.find( k ); + + if( it != m_map.end() ) + { + void* data = it->second; + + m_map.erase( it ); + return data; + } + + return NULL; + } + + void* DoDelete( const wxChar* key ) + { + wxASSERT( m_keyType == wxKEY_STRING ); + + 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; + + m_map.erase( it ); + delete[] k; + return data; + } + + return NULL; + } + + wxHashTableBaseBase m_map; + wxKeyType m_keyType; }; +#endif // !wxUSE_STL + +#if !wxUSE_STL + +#if WXWIN_COMPATIBILITY_2_4 + // ---------------------------------------------------------------------------- // a hash table which stores longs // ---------------------------------------------------------------------------- -class WXDLLEXPORT wxHashTableLong : public wxObject +class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject { public: - wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT) { Init(size); } + wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT) + { Init(size); } virtual ~wxHashTableLong(); void Create(size_t size = wxHASH_SIZE_DEFAULT); @@ -106,14 +308,143 @@ private: size_t m_count; // not implemented yet - DECLARE_NO_COPY_CLASS(wxHashTableLong); + DECLARE_NO_COPY_CLASS(wxHashTableLong) +}; + +// ---------------------------------------------------------------------------- +// wxStringHashTable: a hash table which indexes strings with longs +// ---------------------------------------------------------------------------- + +class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject +{ +public: + wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT); + virtual ~wxStringHashTable(); + + // add a string associated with this key to the table + 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 + wxString Get(long key, bool *wasFound = NULL) const; + + // remove the item, returning TRUE if the item was found and deleted + bool Delete(long key) const; + + // clean up + void Destroy(); + +private: + wxArrayLong **m_keys; + wxArrayString **m_values; + + // the size of array above + size_t m_hashSize; + + DECLARE_NO_COPY_CLASS(wxStringHashTable) }; +#endif // WXWIN_COMPATIBILITY_2_4 + +#endif // !wxUSE_STL + // ---------------------------------------------------------------------------- // for compatibility only // ---------------------------------------------------------------------------- -class WXDLLEXPORT wxHashTable : public wxObject +#if wxUSE_STL + +class WXDLLIMPEXP_BASE wxHashTable : protected wxHashTableBase +{ + typedef wxHashTableBaseBase 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 ); + } + void SetData( wxObject* e ) + { + citer* i = (citer*)this; + i->m_iter->second = e; + } + private: + dummy(); + }; +public: + wxHashTable( wxKeyType keyType = wxKEY_INTEGER, + size_t size = wxHASH_SIZE_DEFAULT ) + : wxHashTableBase( keyType, size ) { } + + 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 ); } + + // 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 ); } + + // Deletes entry and returns data if found + wxObject *Delete(long key) { return (wxObject*)DoDelete( key ); } + wxObject *Delete(const wxChar *key) { return (wxObject*)DoDelete( key ); } + +#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 + // 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 Clear() { wxHashTableBase::Clear(); } + + size_t GetCount() const { return wxHashTableBase::GetCount(); } +private: + compatibility_iterator m_iter; +}; + +#else // if !wxUSE_STL + +class WXDLLIMPEXP_BASE wxHashTable : public wxObject { public: int n; @@ -128,7 +459,8 @@ public: ~wxHashTable(); // copy ctor and assignment operator - wxHashTable(const wxHashTable& table) { DoCopy(table); } + wxHashTable(const wxHashTable& table) : wxObject() + { DoCopy(table); } wxHashTable& operator=(const wxHashTable& table) { Clear(); DoCopy(table); return *this; } @@ -191,6 +523,7 @@ 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; @@ -198,10 +531,32 @@ private: DECLARE_DYNAMIC_CLASS(wxHashTable) }; +#endif + +#if wxUSE_STL + // defines a new type safe hash table which stores the elements of type eltype // in lists of class listclass -#define WX_DECLARE_HASH(eltype, listclass, hashclass) \ - class WXDLLEXPORT hashclass : public wxHashTableBase \ +#define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp) \ + classexp hashclass : public wxHashTableBase \ + { \ + public: \ + hashclass(wxKeyType keyType = wxKEY_INTEGER, \ + size_t size = wxHASH_SIZE_DEFAULT) \ + : wxHashTableBase(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); } \ + } + +#else // if !wxUSE_STL + +#define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \ + classexp hashclass : public wxHashTableBase \ { \ public: \ hashclass(wxKeyType keyType = wxKEY_INTEGER, \ @@ -244,7 +599,7 @@ private: protected: \ void DoPut(long key, long value, eltype *data) \ { \ - size_t slot = (size_t)abs(key % m_hashSize); \ + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \ \ if ( !m_hashTable[slot] ) \ { \ @@ -256,6 +611,40 @@ private: ((listclass *)m_hashTable[slot])->Append(value, data); \ m_count++; \ } \ + \ + DECLARE_NO_COPY_CLASS(hashclass) \ + } + +#endif + +// this macro is to be used in the user code +#define WX_DECLARE_HASH(el, list, hash) \ + _WX_DECLARE_HASH(el, list, hash, class) + +// and this one does exactly the same thing but should be used inside the +// library +#define WX_DECLARE_EXPORTED_HASH(el, list, hash) \ + _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT) + +#define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \ + _WX_DECLARE_HASH(el, list, hash, class usergoo) + +// delete all hash elements +// +// NB: the class declaration of the hash elements must be visible from the +// place where you use this macro, otherwise the proper destructor may not +// be called (a decent compiler should give a warning about it, but don't +// count on it)! +#define WX_CLEAR_HASH_TABLE(hash) \ + { \ + (hash).BeginFind(); \ + wxHashTable::compatibility_iterator it = (hash).Next(); \ + while( it ) \ + { \ + delete it->GetData(); \ + it = (hash).Next(); \ + } \ + (hash).Clear(); \ } #endif