X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/6a5391afa9a22c72e1daaa8ee949febe78ad079d..d5ae99f5e8dca72f160d7002576a3736dccb6f65:/include/wx/hash.h?ds=inline diff --git a/include/wx/hash.h b/include/wx/hash.h index 575216d21c..247a844637 100644 --- a/include/wx/hash.h +++ b/include/wx/hash.h @@ -12,12 +12,29 @@ #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 && 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 // the default size of the hash #define wxHASH_SIZE_DEFAULT (1000) @@ -34,7 +51,9 @@ // pointers to objects // ---------------------------------------------------------------------------- -class WXDLLEXPORT wxHashTableBase : public wxObject +#if wxUSE_OLD_HASH_TABLE + +class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject { public: wxHashTableBase(); @@ -69,17 +88,160 @@ protected: private: // no copy ctor/assignment operator (yet) - DECLARE_NO_COPY_CLASS(wxHashTableBase); + DECLARE_NO_COPY_CLASS(wxHashTableBase) }; +#else // if !wxUSE_OLD_HASH_TABLE + +#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; +}; + +// 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 +{ + 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(); + + long GetKeyInteger() const { return m_key.integer; } + const wxChar* GetKeyString() const { return m_key.string; } + + void* GetData() const { return m_value; } + void SetData( void* data ) { m_value = data; } + +protected: + _Node* GetNext() const { return m_next; } + +protected: + // next node in the chain + wxHashTableBase_Node* m_next; + + // key + wxHashKeyValue m_key; + + // 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: + typedef wxHashTableBase_Node Node; + + wxHashTableBase(); + virtual ~wxHashTableBase() { }; + + void Create( wxKeyType keyType = wxKEY_INTEGER, + size_t size = wxHASH_SIZE_DEFAULT ); + void Clear(); + void Destroy(); + + size_t GetSize() const { return m_size; } + size_t GetCount() const { return m_count; } + + void DeleteContents( bool flag ) { m_deleteContents = flag; } + + static long MakeKey(const wxChar *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 ); + +private: + // Remove the node from the hash, *only called from + // ~wxHashTable*_Node destructor + void DoRemoveNode( wxHashTableBase_Node* node ); + + // 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 ); + + // inserts a node in the table (at the end of the chain) + void DoInsertNode( size_t bucket, wxHashTableBase_Node* node ); + + // 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 ); + + // unconditionally deletes node value (invoking the + // correct destructor) + virtual void DoDeleteContents( wxHashTableBase_Node* node ) = 0; + +protected: + // number of buckets + size_t m_size; + + // number of nodes (key/value pairs) + size_t m_count; + + // table + Node** m_table; + + // key typ (INTEGER/STRING) + wxKeyType m_keyType; + + // delete contents when hash is cleared + bool m_deleteContents; + +private: + DECLARE_NO_COPY_CLASS(wxHashTableBase) +}; + +#endif // wxUSE_OLD_HASH_TABLE + +#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 +268,14 @@ 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 WXDLLEXPORT wxStringHashTable : public wxObject +class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject { public: wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT); @@ -123,9 +285,12 @@ 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 + bool Delete(long key) const; + // clean up void Destroy(); @@ -136,16 +301,126 @@ private: // the size of array above size_t m_hashSize; - DECLARE_NO_COPY_CLASS(wxStringHashTable); + DECLARE_NO_COPY_CLASS(wxStringHashTable) }; +#endif // WXWIN_COMPATIBILITY_2_4 + +#endif // !wxUSE_STL + // ---------------------------------------------------------------------------- // for compatibility only // ---------------------------------------------------------------------------- -class WXDLLEXPORT wxHashTable : public wxObject +#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(); } +}; + +// 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() { Create( keyType, size ); BeginFind(); } + wxHashTable( const wxHashTable& table ); + + virtual ~wxHashTable() { Destroy(); } + + const wxHashTable& operator=( const wxHashTable& ); + + // key and value are the same + 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, 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, 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 ); } + + // 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 + { 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_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: + // current node + Node* m_curr; + + // bucket the current node belongs to + size_t m_currBucket; +}; + +#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; @@ -158,7 +433,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; } @@ -213,7 +489,7 @@ public: // objects maintained separately void BeginFind(); - wxNode *Next(); + Node* Next(); void DeleteContents(bool flag); void Clear(); @@ -228,8 +504,40 @@ private: DECLARE_DYNAMIC_CLASS(wxHashTable) }; +#endif // wxUSE_OLD_HASH_TABLE + +#if !wxUSE_OLD_HASH_TABLE + // defines a new type safe hash table which stores the elements of type eltype // in lists of class listclass +#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() { Create(keyType, size); } \ + \ + virtual ~hashclass() { Destroy(); } \ + \ + 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_OLD_HASH_TABLE + #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \ classexp hashclass : public wxHashTableBase \ { \ @@ -280,14 +588,18 @@ 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); \ m_count++; \ } \ + \ + DECLARE_NO_COPY_CLASS(hashclass) \ } +#endif // wxUSE_OLD_HASH_TABLE + // this macro is to be used in the user code #define WX_DECLARE_HASH(el, list, hash) \ _WX_DECLARE_HASH(el, list, hash, class) @@ -297,5 +609,26 @@ private: #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 // _WX_HASH_H__