X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/c801d85f158c4cba50b588807daabdcbd0ed3853..03e11df5470fd64d9d9a669d0b50b84c2d714736:/src/common/hash.cpp diff --git a/src/common/hash.cpp b/src/common/hash.cpp index 1aba64563c..09e9b42d13 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,150 +37,468 @@ #include #include -#if !USE_SHARED_LIBRARY +// ---------------------------------------------------------------------------- +// wxWin macros +// ---------------------------------------------------------------------------- + IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject) -#endif -wxHashTable::wxHashTable (const int the_key_type, const int size) +// ============================================================================ +// 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((int)(key % (long)m_hashSize)); + + wxNodeBase *node; + if ( m_hashTable[slot] ) + { + node = m_hashTable[slot]->Find(wxListKey(value)); + } + else + { + node = (wxNodeBase *)NULL; + } + + return node; +} + +// ---------------------------------------------------------------------------- +// wxHashTableLong +// ---------------------------------------------------------------------------- + +wxHashTableLong::~wxHashTableLong() +{ + Destroy(); +} + +void wxHashTableLong::Init(size_t size) +{ + m_hashSize = size; + m_values = new wxArrayLong *[size]; + m_keys = new wxArrayLong *[size]; + + for ( size_t n = 0; n < m_hashSize; n++ ) + { + m_values[n] = + m_keys[n] = (wxArrayLong *)NULL; + } + + m_count = 0; +} + +void wxHashTableLong::Destroy() +{ + for ( size_t n = 0; n < m_hashSize; n++ ) + { + delete m_values[n]; + delete m_keys[n]; + } + + delete [] m_values; + delete [] m_keys; + m_hashSize = 0; + m_count = 0; +} + +void wxHashTableLong::Put(long key, long value) { + wxCHECK_RET( m_hashSize, _T("must call Create() first") ); + + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); + + if ( !m_keys[slot] ) + { + m_keys[slot] = new wxArrayLong; + m_values[slot] = new wxArrayLong; + } + + m_keys[slot]->Add(key); + m_values[slot]->Add(value); + + m_count++; +} + +long wxHashTableLong::Get(long key) const +{ + wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); + + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); + + wxArrayLong *keys = m_keys[slot]; + if ( keys ) + { + size_t count = keys->GetCount(); + for ( size_t n = 0; n < count; n++ ) + { + if ( keys->Item(n) == key ) + { + return m_values[slot]->Item(n); + } + } + } + + return wxNOT_FOUND; +} + +long wxHashTableLong::Delete(long key) +{ + wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); + + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); + + wxArrayLong *keys = m_keys[slot]; + if ( keys ) + { + size_t count = keys->GetCount(); + for ( size_t n = 0; n < count; n++ ) + { + if ( keys->Item(n) == key ) + { + long val = m_values[slot]->Item(n); + + keys->RemoveAt(n); + m_values[slot]->RemoveAt(n); + + m_count--; + + return val; + } + } + } + + return wxNOT_FOUND; +} + +// ---------------------------------------------------------------------------- +// wxStringHashTable: more efficient than storing strings in a list +// ---------------------------------------------------------------------------- + +wxStringHashTable::wxStringHashTable(size_t sizeTable) +{ + m_keys = new wxArrayLong *[sizeTable]; + m_values = new wxArrayString *[sizeTable]; + + m_hashSize = sizeTable; + for ( size_t n = 0; n < m_hashSize; n++ ) + { + m_values[n] = (wxArrayString *)NULL; + m_keys[n] = (wxArrayLong *)NULL; + } +} + +wxStringHashTable::~wxStringHashTable() +{ + Destroy(); +} + +void wxStringHashTable::Destroy() +{ + for ( size_t n = 0; n < m_hashSize; n++ ) + { + delete m_values[n]; + delete m_keys[n]; + } + + delete [] m_values; + delete [] m_keys; + m_hashSize = 0; +} + +void wxStringHashTable::Put(long key, const wxString& value) +{ + wxCHECK_RET( m_hashSize, _T("must call Create() first") ); + + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); + + if ( !m_keys[slot] ) + { + m_keys[slot] = new wxArrayLong; + m_values[slot] = new wxArrayString; + } + + m_keys[slot]->Add(key); + m_values[slot]->Add(value); +} + +wxString wxStringHashTable::Get(long key, bool *wasFound) const +{ + wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") ); + + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); + + wxArrayLong *keys = m_keys[slot]; + if ( keys ) + { + size_t count = keys->GetCount(); + for ( size_t n = 0; n < count; n++ ) + { + if ( keys->Item(n) == key ) + { + if ( wasFound ) + *wasFound = TRUE; + + return m_values[slot]->Item(n); + } + } + } + + if ( wasFound ) + *wasFound = FALSE; + + return _T(""); +} + +// ---------------------------------------------------------------------------- +// old not type safe wxHashTable +// ---------------------------------------------------------------------------- + +wxHashTable::wxHashTable (int the_key_type, int size) +{ + n = 0; + hash_table = (wxList**) NULL; + Create(the_key_type, size); + m_count = 0; + m_deleteContents = FALSE; +/* n = size; current_position = -1; - current_node = NULL; + current_node = (wxNode *) NULL; key_type = the_key_type; hash_table = new wxList *[size]; int i; for (i = 0; i < size; i++) - hash_table[i] = NULL; + hash_table[i] = (wxList *) NULL; +*/ +} + +wxHashTable::~wxHashTable () +{ + Destroy(); } -wxHashTable::~wxHashTable (void) +void wxHashTable::Destroy() { + if (!hash_table) return; int i; for (i = 0; i < n; i++) if (hash_table[i]) delete hash_table[i]; delete[] hash_table; + hash_table = NULL; } -bool wxHashTable::Create(const int the_key_type, const int size) +bool wxHashTable::Create(int the_key_type, int size) { + Destroy(); + n = size; current_position = -1; - current_node = NULL; + current_node = (wxNode *) NULL; key_type = the_key_type; - if (hash_table) - delete[] hash_table; hash_table = new wxList *[size]; int i; for (i = 0; i < size; i++) - hash_table[i] = NULL; + hash_table[i] = (wxList *) NULL; return TRUE; } -void wxHashTable::Put (const long key, const long value, wxObject * object) + +void wxHashTable::DoCopy(const wxHashTable& table) +{ + n = table.n; + current_position = table.current_position; + current_node = NULL; // doesn't matter - Next() will reconstruct it + key_type = table.key_type; + + hash_table = new wxList *[n]; + for (int i = 0; i < n; i++) { + if (table.hash_table[i] == NULL) + hash_table[i] = NULL; + else { + hash_table[i] = new wxList(key_type); + *(hash_table[i]) = *(table.hash_table[i]); + } + } +} + +void wxHashTable::Put (long key, long value, wxObject * object) { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) + { hash_table[position] = new wxList (wxKEY_INTEGER); + if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); + } hash_table[position]->Append (value, object); + m_count++; } -void wxHashTable::Put (const long key, const char *value, wxObject * object) +void wxHashTable::Put (long key, const wxChar *value, wxObject * object) { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) + { hash_table[position] = new wxList (wxKEY_INTEGER); + if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); + } hash_table[position]->Append (value, object); + m_count++; } -void wxHashTable::Put (const long key, wxObject * object) +void wxHashTable::Put (long key, wxObject * object) { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) + { hash_table[position] = new wxList (wxKEY_INTEGER); + if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); + } hash_table[position]->Append (k, object); + m_count++; } -void wxHashTable::Put (const char *key, wxObject * object) +void wxHashTable::Put (const wxChar *key, wxObject * object) { int position = (int) (MakeKey (key) % n); + if (position < 0) position = -position; if (!hash_table[position]) + { hash_table[position] = new wxList (wxKEY_STRING); + if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); + } hash_table[position]->Append (key, object); + m_count++; } -wxObject *wxHashTable::Get (const long key, const long value) const +wxObject *wxHashTable::Get (long key, long value) const { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->Data (); else - return NULL; + return (wxObject *) NULL; } } -wxObject *wxHashTable::Get (const long key, const char *value) const +wxObject *wxHashTable::Get (long key, const wxChar *value) const { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->Data (); else - return NULL; + return (wxObject *) NULL; } } -wxObject *wxHashTable::Get (const long key) const +wxObject *wxHashTable::Get (long key) const { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (k); @@ -180,12 +506,13 @@ wxObject *wxHashTable::Get (const long key) const } } -wxObject *wxHashTable::Get (const char *key) const +wxObject *wxHashTable::Get (const wxChar *key) const { int position = (int) (MakeKey (key) % n); + if (position < 0) position = -position; if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (key); @@ -193,158 +520,168 @@ wxObject *wxHashTable::Get (const char *key) const } } -wxObject *wxHashTable::Delete (const long key) +wxObject *wxHashTable::Delete (long key) { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (k); if (node) - { - wxObject *data = node->Data (); - delete node; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return NULL; + return (wxObject *) NULL; } } -wxObject *wxHashTable::Delete (const char *key) +wxObject *wxHashTable::Delete (const wxChar *key) { int position = (int) (MakeKey (key) % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (key); if (node) - { - wxObject *data = node->Data (); - delete node; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return NULL; + return (wxObject *) NULL; } } -wxObject *wxHashTable::Delete (const long key, const int value) +wxObject *wxHashTable::Delete (long key, int value) { // Should NEVER be long k = (long) key; - if (k < 0) - k = -k; int position = (int) (k % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (value); if (node) - { - wxObject *data = node->Data (); - delete node; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return NULL; + return (wxObject *) NULL; } } -wxObject *wxHashTable::Delete (const long key, const char *value) +wxObject *wxHashTable::Delete (long key, const wxChar *value) { int position = (int) (key % n); + if (position < 0) position = -position; + if (!hash_table[position]) - return NULL; + return (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (value); if (node) - { - wxObject *data = node->Data (); - delete node; - return data; - } + { + wxObject *data = node->Data (); + delete node; + m_count--; + return data; + } else - return NULL; + return (wxObject *) NULL; } } -long wxHashTable::MakeKey (const char *string) const +long wxHashTable::MakeKey (const wxChar *string) const { long int_key = 0; while (*string) - int_key += (unsigned char) *string++; + int_key += (wxUChar) *string++; return int_key; } -void wxHashTable::BeginFind (void) +void wxHashTable::BeginFind () { current_position = -1; - current_node = NULL; + current_node = (wxNode *) NULL; } -wxNode *wxHashTable::Next (void) +wxNode *wxHashTable::Next () { - wxNode *found = NULL; + wxNode *found = (wxNode *) NULL; bool end = FALSE; while (!end && !found) { if (!current_node) - { - current_position++; - if (current_position >= n) - { - current_position = -1; - current_node = 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; } -void wxHashTable::DeleteContents (const bool flag) +void wxHashTable::DeleteContents (bool flag) { int i; + m_deleteContents = 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; }