X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/ffae916f44b271928c3ab7d734a2e9fd89a59e94..8adb5d455797d5b656ef677c74359e5a578b539f:/src/common/hash.cpp diff --git a/src/common/hash.cpp b/src/common/hash.cpp index cfc590327c..9882539bb4 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 +// Copyright: (c) Julian Smart +// Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// +// ============================================================================ +// declarations +// ============================================================================ + +// ---------------------------------------------------------------------------- +// headers +// ---------------------------------------------------------------------------- + #ifdef __GNUG__ #pragma implementation "hash.h" #endif @@ -29,8 +37,307 @@ #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(""); +} + +bool wxStringHashTable::Delete(long key) const +{ + wxCHECK_MSG( m_hashSize, FALSE, _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 ) + { + keys->RemoveAt(n); + m_values[slot]->RemoveAt(n); + return TRUE; + } + } + } + + return FALSE; +} + +// ---------------------------------------------------------------------------- +// old not type safe wxHashTable +// ---------------------------------------------------------------------------- + wxHashTable::wxHashTable (int the_key_type, int size) { n = 0; @@ -51,12 +358,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; @@ -87,6 +394,7 @@ bool wxHashTable::Create(int the_key_type, int size) void wxHashTable::DoCopy(const wxHashTable& table) { n = table.n; + m_count = table.m_count; current_position = table.current_position; current_node = NULL; // doesn't matter - Next() will reconstruct it key_type = table.key_type; @@ -123,14 +431,14 @@ 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); + hash_table[position] = new wxList (wxKEY_STRING); if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); } @@ -142,7 +450,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 +459,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 +493,9 @@ wxObject *wxHashTable::Get (long key, long value) const { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->GetData (); else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -195,7 +503,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 +513,9 @@ wxObject *wxHashTable::Get (long key, const wxChar *value) const { wxNode *node = hash_table[position]->Find (value); if (node) - return node->Data (); + return node->GetData (); else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -224,7 +532,7 @@ wxObject *wxHashTable::Get (long key) const else { wxNode *node = hash_table[position]->Find (k); - return node ? node->Data () : (wxObject*)NULL; + return node ? node->GetData () : (wxObject*)NULL; } } @@ -238,7 +546,7 @@ wxObject *wxHashTable::Get (const wxChar *key) const else { wxNode *node = hash_table[position]->Find (key); - return node ? node->Data () : (wxObject*)NULL; + return node ? node->GetData () : (wxObject*)NULL; } } @@ -256,14 +564,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->GetData (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -278,21 +586,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->GetData (); + 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 +611,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->GetData (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -325,14 +633,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->GetData (); + delete node; + m_count--; + return data; + } else - return (wxObject *) NULL; + return (wxObject *) NULL; } } @@ -346,41 +654,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]->GetFirst (); + found = current_node; + } + } + } else - { - current_node = current_node->Next (); - found = current_node; - } + { + current_node = current_node->GetNext (); + found = current_node; + } } return found; } @@ -392,17 +700,20 @@ 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++) + int i; + if (hash_table) { - if (hash_table[i]) - hash_table[i]->Clear (); + for (i = 0; i < n; i++) + { + if (hash_table[i]) + hash_table[i]->Clear (); + } } m_count = 0; }