X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/c2bb85e9e38ee35758e0076485bb6665f2c229f5..878711c01c1b9ad5b97d35f379a048b8ce1bfb49:/src/common/hash.cpp diff --git a/src/common/hash.cpp b/src/common/hash.cpp index 1aa13adf84..9882539bb4 100644 --- a/src/common/hash.cpp +++ b/src/common/hash.cpp @@ -5,7 +5,7 @@ // 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 +// Copyright: (c) Julian Smart // Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// @@ -104,7 +104,7 @@ void wxHashTableBase::DeleteContents(bool flag) wxNodeBase *wxHashTableBase::GetNode(long key, long value) const { - size_t slot = (size_t)abs(key % m_hashSize); + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); wxNodeBase *node; if ( m_hashTable[slot] ) @@ -123,6 +123,11 @@ wxNodeBase *wxHashTableBase::GetNode(long key, long value) const // wxHashTableLong // ---------------------------------------------------------------------------- +wxHashTableLong::~wxHashTableLong() +{ + Destroy(); +} + void wxHashTableLong::Init(size_t size) { m_hashSize = size; @@ -138,6 +143,11 @@ void wxHashTableLong::Init(size_t size) m_count = 0; } +void wxHashTableLong::Create(size_t size) +{ + Init(size); +} + void wxHashTableLong::Destroy() { for ( size_t n = 0; n < m_hashSize; n++ ) @@ -156,7 +166,7 @@ void wxHashTableLong::Put(long key, long value) { wxCHECK_RET( m_hashSize, _T("must call Create() first") ); - size_t slot = (size_t)abs(key % m_hashSize); + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); if ( !m_keys[slot] ) { @@ -174,7 +184,7 @@ long wxHashTableLong::Get(long key) const { wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); - size_t slot = (size_t)abs(key % m_hashSize); + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); wxArrayLong *keys = m_keys[slot]; if ( keys ) @@ -196,7 +206,7 @@ long wxHashTableLong::Delete(long key) { wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); - size_t slot = (size_t)abs(key % m_hashSize); + size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); wxArrayLong *keys = m_keys[slot]; if ( keys ) @@ -221,6 +231,109 @@ long wxHashTableLong::Delete(long key) 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 // ---------------------------------------------------------------------------- @@ -281,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; @@ -324,7 +438,7 @@ void wxHashTable::Put (long key, const wxChar *value, wxObject * object) 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); } @@ -379,7 +493,7 @@ 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; } @@ -399,7 +513,7 @@ 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; } @@ -418,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; } } @@ -432,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; } } @@ -451,7 +565,7 @@ wxObject *wxHashTable::Delete (long key) wxNode *node = hash_table[position]->Find (k); if (node) { - wxObject *data = node->Data (); + wxObject *data = node->GetData (); delete node; m_count--; return data; @@ -473,7 +587,7 @@ wxObject *wxHashTable::Delete (const wxChar *key) wxNode *node = hash_table[position]->Find (key); if (node) { - wxObject *data = node->Data (); + wxObject *data = node->GetData (); delete node; m_count--; return data; @@ -498,7 +612,7 @@ wxObject *wxHashTable::Delete (long key, int value) wxNode *node = hash_table[position]->Find (value); if (node) { - wxObject *data = node->Data (); + wxObject *data = node->GetData (); delete node; m_count--; return data; @@ -520,7 +634,7 @@ wxObject *wxHashTable::Delete (long key, const wxChar *value) wxNode *node = hash_table[position]->Find (value); if (node) { - wxObject *data = node->Data (); + wxObject *data = node->GetData (); delete node; m_count--; return data; @@ -565,14 +679,14 @@ wxNode *wxHashTable::Next () { if (hash_table[current_position]) { - current_node = hash_table[current_position]->First (); + current_node = hash_table[current_position]->GetFirst (); found = current_node; } } } else { - current_node = current_node->Next (); + current_node = current_node->GetNext (); found = current_node; } } @@ -592,11 +706,14 @@ void wxHashTable::DeleteContents (bool flag) 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; }