X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/5692876f3b45c8f141ea961f0a206b0c2248bc6d..4a45223c970eabf6ba66347129627775935c90b3:/src/common/hash.cpp?ds=sidebyside diff --git a/src/common/hash.cpp b/src/common/hash.cpp index 4c6ad97c6d..d8079dce9e 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,14 +37,290 @@ #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((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::Create(size_t size) +{ + Init(size); +} + +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; @@ -50,12 +334,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; @@ -105,12 +389,15 @@ 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++; @@ -120,12 +407,15 @@ 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++; @@ -135,12 +425,15 @@ 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++; @@ -149,9 +442,13 @@ void wxHashTable::Put (long 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++; @@ -161,19 +458,19 @@ 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 (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->Data (); else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -181,19 +478,19 @@ 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 (wxObject *) NULL; else { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->Data (); else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -201,10 +498,10 @@ 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 (wxObject *) NULL; else @@ -217,6 +514,7 @@ wxObject *wxHashTable::Get (long 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 (wxObject *) NULL; @@ -231,44 +529,46 @@ 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 (wxObject *) NULL; else { 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; } } wxObject *wxHashTable::Delete (const wxChar *key) { int position = (int) (MakeKey (key) % n); + if (position < 0) position = -position; + if (!hash_table[position]) return (wxObject *) NULL; else { 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; } } @@ -276,44 +576,46 @@ 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 (wxObject *) NULL; else { 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; } } wxObject *wxHashTable::Delete (long key, const wxChar *value) { int position = (int) (key % n); + if (position < 0) position = -position; + if (!hash_table[position]) return (wxObject *) NULL; else { 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; } } @@ -327,41 +629,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; } @@ -369,20 +671,21 @@ wxNode *wxHashTable::Next (void) 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; }