From bcaa23de098c1276b3f35716c9ea8b73cf3599bd Mon Sep 17 00:00:00 2001 From: Vadim Zeitlin Date: Fri, 25 Feb 2000 19:23:11 +0000 Subject: [PATCH] WX_DECLARE_HASH() macro for type safe hashes git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@6292 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- include/wx/hash.h | 283 ++++++++++++++++++++++++++++------------ include/wx/list.h | 3 +- include/wx/listimpl.cpp | 2 +- src/common/hash.cpp | 228 ++++++++++++++++++++++---------- src/common/list.cpp | 6 +- 5 files changed, 364 insertions(+), 158 deletions(-) diff --git a/include/wx/hash.h b/include/wx/hash.h index e5450054f0..650ffe1eee 100644 --- a/include/wx/hash.h +++ b/include/wx/hash.h @@ -1,24 +1,26 @@ ///////////////////////////////////////////////////////////////////////////// -// Name: hash.h +// Name: wx/hash.h // Purpose: wxHashTable class // Author: Julian Smart -// Modified by: +// Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH() // Created: 01/02/97 // RCS-ID: $Id$ // Copyright: (c) -// Licence: wxWindows licence +// Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// -#ifndef _WX_WXHASHH__ -#define _WX_WXHASHH__ +#ifndef _WX_HASH_H__ +#define _WX_HASH_H__ #ifdef __GNUG__ #pragma interface "hash.h" #endif -#include "wx/object.h" #include "wx/list.h" +// the default size of the hash +#define wxHASH_SIZE_DEFAULT (1000) + /* * A hash table is an array of user-definable size with lists * of data items hanging off the array positions. Usually there'll @@ -26,86 +28,197 @@ * the list to find the desired item. */ -class WXDLLEXPORT wxHashTable: public wxObject +// ---------------------------------------------------------------------------- +// this is the base class for object hashes: hash tables which contain +// pointers to objects +// ---------------------------------------------------------------------------- + +class WXDLLEXPORT wxHashTableBase : public wxObject { - DECLARE_DYNAMIC_CLASS(wxHashTable) - - public: - int n; - int current_position; - wxNode *current_node; - - unsigned int key_type; - wxList **hash_table; - - wxHashTable(int the_key_type = wxKEY_INTEGER, int size = 1000); - ~wxHashTable(void); - - // copy ctor and assignment operator - wxHashTable(const wxHashTable& table) { DoCopy(table); } - wxHashTable& operator=(const wxHashTable& table) { Clear(); DoCopy(table); return *this; } - void DoCopy(const wxHashTable& table); - - void Destroy(void); // Robert Roebling - - bool Create(int the_key_type = wxKEY_INTEGER, int size = 1000); - - // Note that there are 2 forms of Put, Get. - // With a key and a value, the *value* will be checked - // when a collision is detected. Otherwise, if there are - // 2 items with a different value but the same key, - // we'll retrieve the WRONG ONE. So where possible, - // supply the required value along with the key. - // In fact, the value-only versions make a key, and still store - // the value. The use of an explicit key might be required - // e.g. when combining several values into one key. - // When doing that, it's highly likely we'll get a collision, - // e.g. 1 + 2 = 3, 2 + 1 = 3. - - // key and value are NOT necessarily the same - void Put(long key, long value, wxObject *object); - void Put(long key, const wxChar *value, wxObject *object); - - // key and value are the same - void Put(long value, wxObject *object); - void Put(const wxChar *value, wxObject *object); - - // key and value not the same - wxObject *Get(long key, long value) const; - wxObject *Get(long key, const wxChar *value) const; - - // key and value are the same - wxObject *Get(long value) const; - wxObject *Get(const wxChar *value) const; - - // Deletes entry and returns data if found - wxObject *Delete(long key); - wxObject *Delete(const wxChar *key); - - wxObject *Delete(long key, int value); - wxObject *Delete(long key, const wxChar *value); - - // 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; - - // 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(void); - wxNode *Next(void); - - void DeleteContents(bool flag); - void Clear(void); - - // Returns number of nodes - size_t GetCount() const { return m_count; } - - private: - size_t m_count; // number of elements in the hashtable - bool m_deleteContents; +public: + wxHashTableBase(); + + void Create(wxKeyType keyType = wxKEY_INTEGER, + size_t size = wxHASH_SIZE_DEFAULT); + void Destroy(); + + size_t GetSize() const { return m_hashSize; } + size_t GetCount() const { return m_count; } + + void DeleteContents(bool flag); + +protected: + // find the node for (key, value) + wxNodeBase *GetNode(long key, long value) const; + + // the array of lists in which we store the values for given key hash + wxListBase **m_hashTable; + + // the size of m_lists array + size_t m_hashSize; + + // the type of indexing we use + wxKeyType m_keyType; + + // the total number of elements in the hash + size_t m_count; + + // should we delete our data? + bool m_deleteContents; + +private: + // no copy ctor/assignment operator (yet) + DECLARE_NO_COPY_CLASS(wxHashTableBase); }; +// ---------------------------------------------------------------------------- +// for compatibility only +// ---------------------------------------------------------------------------- + +class WXDLLEXPORT wxHashTable : public wxObject +{ +public: + int n; + int current_position; + wxNode *current_node; + + unsigned int key_type; + wxList **hash_table; + + wxHashTable(int the_key_type = wxKEY_INTEGER, + int size = wxHASH_SIZE_DEFAULT); + ~wxHashTable(); + + // copy ctor and assignment operator + wxHashTable(const wxHashTable& table) { DoCopy(table); } + wxHashTable& operator=(const wxHashTable& table) + { Clear(); DoCopy(table); return *this; } + + void DoCopy(const wxHashTable& table); + + void Destroy(); + + bool Create(int the_key_type = wxKEY_INTEGER, + int size = wxHASH_SIZE_DEFAULT); + + // Note that there are 2 forms of Put, Get. + // With a key and a value, the *value* will be checked + // when a collision is detected. Otherwise, if there are + // 2 items with a different value but the same key, + // we'll retrieve the WRONG ONE. So where possible, + // supply the required value along with the key. + // In fact, the value-only versions make a key, and still store + // the value. The use of an explicit key might be required + // e.g. when combining several values into one key. + // When doing that, it's highly likely we'll get a collision, + // e.g. 1 + 2 = 3, 2 + 1 = 3. + + // key and value are NOT necessarily the same + void Put(long key, long value, wxObject *object); + void Put(long key, const wxChar *value, wxObject *object); + + // key and value are the same + void Put(long value, wxObject *object); + void Put(const wxChar *value, wxObject *object); + + // key and value not the same + wxObject *Get(long key, long value) const; + wxObject *Get(long key, const wxChar *value) const; + + // key and value are the same + wxObject *Get(long value) const; + wxObject *Get(const wxChar *value) const; + + // Deletes entry and returns data if found + wxObject *Delete(long key); + wxObject *Delete(const wxChar *key); + + wxObject *Delete(long key, int value); + wxObject *Delete(long key, const wxChar *value); + + // 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; + + // 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(); + wxNode *Next(); + + void DeleteContents(bool flag); + void Clear(); + + // Returns number of nodes + size_t GetCount() const { return m_count; } + +private: + size_t m_count; // number of elements in the hashtable + bool m_deleteContents; + + DECLARE_DYNAMIC_CLASS(wxHashTable) +}; + +// 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 \ + { \ + public: \ + hashclass(wxKeyType keyType = wxKEY_INTEGER, \ + size_t size = wxHASH_SIZE_DEFAULT) \ + { Create(keyType, size); } \ + \ + ~hashclass() { Destroy(); } \ + \ + void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \ + void Put(long key, eltype *data) { DoPut(key, key, data); } \ + \ + eltype *Get(long key, long value) const \ + { \ + wxNodeBase *node = GetNode(key, value); \ + return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \ + } \ + eltype *Get(long key) const { return Get(key, key); } \ + \ + eltype *Delete(long key, long value) \ + { \ + eltype *data; \ + \ + wxNodeBase *node = GetNode(key, value); \ + if ( node ) \ + { \ + data = ((listclass::Node *)node)->GetData(); \ + \ + delete node; \ + m_count--; \ + } \ + else \ + { \ + data = (eltype *)0; \ + } \ + \ + return data; \ + } \ + eltype *Delete(long key) { return Delete(key, key); } \ + \ + protected: \ + void DoPut(long key, long value, eltype *data) \ + { \ + size_t slot = (size_t)abs(key % m_hashSize); \ + \ + if ( !m_hashTable[slot] ) \ + { \ + m_hashTable[slot] = new listclass(m_keyType); \ + if ( m_deleteContents ) \ + m_hashTable[slot]->DeleteContents(TRUE); \ + } \ + \ + ((listclass *)m_hashTable[slot])->Append(value, data); \ + m_count++; \ + } \ + } + #endif - // _WX_WXHASHH__ + // _WX_HASH_H__ diff --git a/include/wx/list.h b/include/wx/list.h index 7cad34a420..f42942f442 100644 --- a/include/wx/list.h +++ b/include/wx/list.h @@ -186,7 +186,8 @@ private: // ----------------------------------------------------------------------------- class WXDLLEXPORT wxListBase : public wxObject { -friend class wxNodeBase; // should be able to call DetachNode() +friend class wxNodeBase; // should be able to call DetachNode() +friend class wxHashTableBase; // should be able to call untyped Find() public: // default ctor & dtor wxListBase(wxKeyType keyType = wxKEY_NONE) { Init(keyType); } diff --git a/include/wx/listimpl.cpp b/include/wx/listimpl.cpp index ccb1e6397c..d7ef44dded 100644 --- a/include/wx/listimpl.cpp +++ b/include/wx/listimpl.cpp @@ -6,7 +6,7 @@ // Created: 16/11/98 // RCS-ID: $Id$ // Copyright: (c) 1998 Vadim Zeitlin -// Licence: wxWindows license +// Licence: wxWindows license ///////////////////////////////////////////////////////////////////////////// #define _DEFINE_LIST(T, name) \ diff --git a/src/common/hash.cpp b/src/common/hash.cpp index cfc590327c..ef635a1be1 100644 --- a/src/common/hash.cpp +++ b/src/common/hash.cpp @@ -2,13 +2,21 @@ // Name: hash.cpp // Purpose: wxHashTable implementation // Author: Julian Smart -// Modified by: +// Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH() // Created: 01/02/97 // RCS-ID: $Id$ // Copyright: (c) Julian Smart and Markus Holzem -// Licence: wxWindows licence +// Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// +// ============================================================================ +// declarations +// ============================================================================ + +// ---------------------------------------------------------------------------- +// headers +// ---------------------------------------------------------------------------- + #ifdef __GNUG__ #pragma implementation "hash.h" #endif @@ -29,8 +37,92 @@ #include #include +// ---------------------------------------------------------------------------- +// wxWin macros +// ---------------------------------------------------------------------------- + IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject) +// ============================================================================ +// implementation +// ============================================================================ + +// ---------------------------------------------------------------------------- +// wxHashTablleBase for working with "void *" data +// ---------------------------------------------------------------------------- + +wxHashTableBase::wxHashTableBase() +{ + m_deleteContents = FALSE; + m_hashTable = (wxListBase **)NULL; + m_hashSize = 0; + m_count = 0; + m_keyType = wxKEY_NONE; +} + +void wxHashTableBase::Create(wxKeyType keyType, size_t size) +{ + Destroy(); + + m_hashSize = size; + m_keyType = keyType; + m_hashTable = new wxListBase *[size]; + for ( size_t n = 0; n < m_hashSize; n++ ) + { + m_hashTable[n] = (wxListBase *) NULL; + } +} + +void wxHashTableBase::Destroy() +{ + if ( m_hashTable ) + { + for ( size_t n = 0; n < m_hashSize; n++ ) + { + delete m_hashTable[n]; + } + + delete [] m_hashTable; + + m_hashTable = (wxListBase **)NULL; + + m_count = 0; + } +} + +void wxHashTableBase::DeleteContents(bool flag) +{ + m_deleteContents = flag; + for ( size_t n = 0; n < m_hashSize; n++ ) + { + if ( m_hashTable[n] ) + { + m_hashTable[n]->DeleteContents(flag); + } + } +} + +wxNodeBase *wxHashTableBase::GetNode(long key, long value) const +{ + size_t slot = (size_t)abs(key % m_hashSize); + + wxNodeBase *node; + if ( m_hashTable[slot] ) + { + node = m_hashTable[slot]->Find(wxListKey(value)); + } + else + { + node = (wxNodeBase *)NULL; + } + + return node; +} + +// ---------------------------------------------------------------------------- +// old not type safe wxHashTable +// ---------------------------------------------------------------------------- + wxHashTable::wxHashTable (int the_key_type, int size) { n = 0; @@ -51,12 +143,12 @@ wxHashTable::wxHashTable (int the_key_type, int size) */ } -wxHashTable::~wxHashTable (void) +wxHashTable::~wxHashTable () { Destroy(); } -void wxHashTable::Destroy(void) +void wxHashTable::Destroy() { if (!hash_table) return; int i; @@ -123,11 +215,11 @@ void wxHashTable::Put (long key, long value, wxObject * object) void wxHashTable::Put (long key, const wxChar *value, wxObject * object) { // Should NEVER be - long k = (long) key; + long k = (long) key; int position = (int) (k % n); if (position < 0) position = -position; - + if (!hash_table[position]) { hash_table[position] = new wxList (wxKEY_INTEGER); @@ -142,7 +234,7 @@ void wxHashTable::Put (long key, wxObject * object) { // Should NEVER be long k = (long) key; - + int position = (int) (k % n); if (position < 0) position = -position; @@ -151,7 +243,7 @@ void wxHashTable::Put (long key, wxObject * object) hash_table[position] = new wxList (wxKEY_INTEGER); if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); } - + hash_table[position]->Append (k, object); m_count++; } @@ -185,9 +277,9 @@ wxObject *wxHashTable::Get (long key, long value) const { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->Data (); else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -195,7 +287,7 @@ wxObject *wxHashTable::Get (long key, const wxChar *value) const { // Should NEVER be long k = (long) key; - + int position = (int) (k % n); if (position < 0) position = -position; @@ -205,9 +297,9 @@ wxObject *wxHashTable::Get (long key, const wxChar *value) const { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->Data (); else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -256,14 +348,14 @@ wxObject *wxHashTable::Delete (long key) { wxNode *node = hash_table[position]->Find (k); if (node) - { - wxObject *data = node->Data (); - delete node; - m_count--; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -278,21 +370,21 @@ wxObject *wxHashTable::Delete (const wxChar *key) { wxNode *node = hash_table[position]->Find (key); if (node) - { - wxObject *data = node->Data (); - delete node; - m_count--; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } wxObject *wxHashTable::Delete (long key, int value) { // Should NEVER be - long k = (long) key; + long k = (long) key; int position = (int) (k % n); if (position < 0) position = -position; @@ -303,14 +395,14 @@ wxObject *wxHashTable::Delete (long key, int value) { wxNode *node = hash_table[position]->Find (value); if (node) - { - wxObject *data = node->Data (); - delete node; - m_count--; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -325,14 +417,14 @@ wxObject *wxHashTable::Delete (long key, const wxChar *value) { wxNode *node = hash_table[position]->Find (value); if (node) - { - wxObject *data = node->Data (); - delete node; - m_count--; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -346,41 +438,41 @@ long wxHashTable::MakeKey (const wxChar *string) const return int_key; } -void wxHashTable::BeginFind (void) +void wxHashTable::BeginFind () { current_position = -1; current_node = (wxNode *) NULL; } -wxNode *wxHashTable::Next (void) +wxNode *wxHashTable::Next () { wxNode *found = (wxNode *) NULL; bool end = FALSE; while (!end && !found) { if (!current_node) - { - current_position++; - if (current_position >= n) - { - current_position = -1; - current_node = (wxNode *) NULL; - end = TRUE; - } - else - { - if (hash_table[current_position]) - { - current_node = hash_table[current_position]->First (); - found = current_node; - } - } - } + { + current_position++; + if (current_position >= n) + { + current_position = -1; + current_node = (wxNode *) NULL; + end = TRUE; + } + else + { + if (hash_table[current_position]) + { + current_node = hash_table[current_position]->First (); + found = current_node; + } + } + } else - { - current_node = current_node->Next (); - found = current_node; - } + { + current_node = current_node->Next (); + found = current_node; + } } return found; } @@ -392,17 +484,17 @@ void wxHashTable::DeleteContents (bool flag) for (i = 0; i < n; i++) { if (hash_table[i]) - hash_table[i]->DeleteContents (flag); + hash_table[i]->DeleteContents (flag); } } -void wxHashTable::Clear (void) +void wxHashTable::Clear () { int i; for (i = 0; i < n; i++) { if (hash_table[i]) - hash_table[i]->Clear (); + hash_table[i]->Clear (); } m_count = 0; } diff --git a/src/common/list.cpp b/src/common/list.cpp index 9d88dea967..b56beb3dec 100644 --- a/src/common/list.cpp +++ b/src/common/list.cpp @@ -172,10 +172,10 @@ void wxListBase::DoCopy(const wxListBase& list) m_nodeLast = (wxNodeBase *) NULL; switch (m_keyType) { - + case wxKEY_INTEGER: { - long key; + long key; for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() ) { key = node->GetKeyInteger(); @@ -186,7 +186,7 @@ void wxListBase::DoCopy(const wxListBase& list) case wxKEY_STRING: { - const wxChar *key; + const wxChar *key; for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() ) { key = node->GetKeyString(); -- 2.45.2