X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/6aa33060cd9132116fa3431b4889342e2f655853..95912bdddeb21afe1cabc0401c0f8b8475a5e5c6:/src/common/hash.cpp diff --git a/src/common/hash.cpp b/src/common/hash.cpp index 28ba8276da..8c7049b6b4 100644 --- a/src/common/hash.cpp +++ b/src/common/hash.cpp @@ -1,5 +1,5 @@ ///////////////////////////////////////////////////////////////////////////// -// Name: hash.cpp +// Name: src/common/hash.cpp // Purpose: wxHashTable implementation // Author: Julian Smart // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH() @@ -17,715 +17,18 @@ // headers // ---------------------------------------------------------------------------- -#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) -#pragma implementation "hash.h" -#endif - // For compilers that support precompilation, includes "wx.h". #include "wx/wxprec.h" #ifdef __BORLANDC__ -#pragma hdrstop + #pragma hdrstop #endif #ifndef WX_PRECOMP -#include "wx/list.h" + #include "wx/hash.h" + #include "wx/object.h" #endif -#include "wx/hash.h" - -#if wxUSE_OLD_HASH_TABLE - -#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; -} - -#if WXWIN_COMPATIBILITY_2_4 - -// ---------------------------------------------------------------------------- -// 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; -} - -#endif // WXWIN_COMPATIBILITY_2_4 - -// ---------------------------------------------------------------------------- -// 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 = (wxNode *) NULL; - - key_type = the_key_type; - hash_table = new wxList *[size]; - int i; - for (i = 0; i < size; i++) - hash_table[i] = (wxList *) NULL; -*/ -} - -wxHashTable::~wxHashTable () -{ - Destroy(); -} - -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(int the_key_type, int size) -{ - Destroy(); - - n = size; - current_position = -1; - 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] = (wxList *) NULL; - return TRUE; -} - - -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; - - 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; - - 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 (long key, const wxChar *value, wxObject * object) -{ - // Should NEVER be - long k = (long) key; - - int position = (int) (k % 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 (value, object); - m_count++; -} - -void wxHashTable::Put (long key, wxObject * object) -{ - // Should NEVER be - 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); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } - - hash_table[position]->Append (k, object); - m_count++; -} - -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 (long key, long value) const -{ - // Should NEVER be - long k = (long) key; - - 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->GetData (); - else - return (wxObject *) NULL; - } -} - -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; - - if (!hash_table[position]) - return (wxObject *) NULL; - else - { - wxNode *node = hash_table[position]->Find (value); - if (node) - return node->GetData (); - else - return (wxObject *) NULL; - } -} - -wxObject *wxHashTable::Get (long key) const -{ - // Should NEVER be - long k = (long) key; - - 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); - return node ? node->GetData () : (wxObject*)NULL; - } -} - -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; - else - { - wxNode *node = hash_table[position]->Find (key); - return node ? node->GetData () : (wxObject*)NULL; - } -} - -wxObject *wxHashTable::Delete (long key) -{ - // Should NEVER be - long k = (long) key; - - 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->GetData (); - delete node; - m_count--; - return data; - } - else - 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->GetData (); - delete node; - m_count--; - return data; - } - else - return (wxObject *) NULL; - } -} - -wxObject *wxHashTable::Delete (long key, int value) -{ - // Should NEVER be - long k = (long) key; - - 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->GetData (); - delete node; - m_count--; - return data; - } - else - 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->GetData (); - delete node; - m_count--; - return data; - } - else - return (wxObject *) NULL; - } -} - -long wxHashTable::MakeKey (const wxChar *string) const -{ - long int_key = 0; - - while (*string) - int_key += (wxUChar) *string++; - - return int_key; -} - -void wxHashTable::BeginFind () -{ - current_position = -1; - current_node = (wxNode *) NULL; -} - -wxHashTable::Node* 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]->GetFirst (); - found = current_node; - } - } - } - else - { - current_node = current_node->GetNext (); - found = current_node; - } - } - return found; -} - -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); - } -} - -void wxHashTable::Clear () -{ - int i; - if (hash_table) - { - for (i = 0; i < n; i++) - { - if (hash_table[i]) - hash_table[i]->Clear (); - } - } - m_count = 0; -} - -#else // if !wxUSE_OLD_HASH_TABLE - wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, wxHashTableBase* table ) : m_value( value ), m_hashPtr( table ) @@ -733,11 +36,11 @@ wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, m_key.integer = key; } -wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value, +wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value, wxHashTableBase* table ) : m_value( value ), m_hashPtr( table ) { - m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key ); + m_key.string = new wxString(key); } wxHashTableBase_Node::~wxHashTableBase_Node() @@ -795,7 +98,7 @@ void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) { size_t bucket = ( m_keyType == wxKEY_INTEGER ? node->m_key.integer : - MakeKey( node->m_key.string ) ) % m_size; + MakeKey( *node->m_key.string ) ) % m_size; if( node->GetNext() == node ) { @@ -808,7 +111,7 @@ void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) Node* prev = start; for( curr = prev->GetNext(); curr != node; - prev = curr, curr = curr->GetNext() ); + prev = curr, curr = curr->GetNext() ) ; DoUnlinkNode( bucket, node, prev ); } @@ -823,7 +126,7 @@ void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node ) node->m_hashPtr = NULL; if( m_keyType == wxKEY_STRING ) - delete[] node->m_key.string; + delete node->m_key.string; if( m_deleteContents ) DoDeleteContents( node ); } @@ -832,9 +135,7 @@ void wxHashTableBase::Destroy() { Clear(); - delete[] m_table; - - m_table = NULL; + wxDELETEA(m_table); m_size = 0; } @@ -867,7 +168,7 @@ void wxHashTableBase::DoPut( long key, long hash, void* data ) DoInsertNode( bucket, node ); } -void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data ) +void wxHashTableBase::DoPut( const wxString& key, long hash, void* data ) { wxASSERT( m_keyType == wxKEY_STRING ); @@ -901,7 +202,7 @@ void* wxHashTableBase::DoGet( long key, long hash ) const return NULL; } -void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const +void* wxHashTableBase::DoGet( const wxString& key, long hash ) const { wxASSERT( m_keyType == wxKEY_STRING ); @@ -915,7 +216,7 @@ void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const do { - if( wxStrcmp( curr->m_key.string, key ) == 0 ) + if( *curr->m_key.string == key ) return curr->m_value; curr = curr->GetNext(); @@ -974,7 +275,7 @@ void* wxHashTableBase::DoDelete( long key, long hash ) return NULL; } -void* wxHashTableBase::DoDelete( const wxChar* key, long hash ) +void* wxHashTableBase::DoDelete( const wxString& key, long hash ) { wxASSERT( m_keyType == wxKEY_STRING ); @@ -989,7 +290,7 @@ void* wxHashTableBase::DoDelete( const wxChar* key, long hash ) do { - if( wxStrcmp( curr->m_key.string, key ) == 0 ) + if( *curr->m_key.string == key ) { void* retval = curr->m_value; curr->m_value = NULL; @@ -1008,19 +309,23 @@ void* wxHashTableBase::DoDelete( const wxChar* key, long hash ) return NULL; } -long wxHashTableBase::MakeKey( const wxChar *str ) +long wxHashTableBase::MakeKey( const wxString& str ) { long int_key = 0; - while( *str ) - int_key += (wxUChar)*str++; + const wxStringCharType *p = str.wx_str(); + while( *p ) + int_key += *p++; return int_key; } -// +// ---------------------------------------------------------------------------- +// wxHashTable +// ---------------------------------------------------------------------------- wxHashTable::wxHashTable( const wxHashTable& table ) + : wxHashTableBase() { DoCopy( table ); } @@ -1037,7 +342,7 @@ void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) ) { Create( m_keyType, m_size ); - wxASSERT( false ); + wxFAIL; } void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node ) @@ -1076,4 +381,3 @@ wxHashTable::Node* wxHashTable::Next() return m_curr; } -#endif // !wxUSE_OLD_HASH_TABLE