X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/14f355c2b5c71fc7c3d680aea366582d2ac60f7b..69659fd770f615210efac4b4fa741b3ad6223616:/src/common/hash.cpp?ds=sidebyside diff --git a/src/common/hash.cpp b/src/common/hash.cpp index db33f96e28..1e36fec843 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,711 +17,369 @@ // 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_STL - -#include -#include - -// ---------------------------------------------------------------------------- -// wxWin macros -// ---------------------------------------------------------------------------- - -IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject) - -// ============================================================================ -// implementation -// ============================================================================ - -// ---------------------------------------------------------------------------- -// wxHashTablleBase for working with "void *" data -// ---------------------------------------------------------------------------- - -wxHashTableBase::wxHashTableBase() +wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) { - m_deleteContents = FALSE; - m_hashTable = (wxListBase **)NULL; - m_hashSize = 0; - m_count = 0; - m_keyType = wxKEY_NONE; + m_key.integer = key; } -void wxHashTableBase::Create(wxKeyType keyType, size_t size) +wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) { - 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; - } + m_key.string = new wxString(key); } -void wxHashTableBase::Destroy() +wxHashTableBase_Node::~wxHashTableBase_Node() { - 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; - } + if( m_hashPtr ) m_hashPtr->DoRemoveNode( this ); } -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 +wxHashTableBase::wxHashTableBase() + : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ), + m_deleteContents( false ) { - 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() +void wxHashTableBase::Create( wxKeyType keyType, size_t size ) { - Destroy(); + m_keyType = keyType; + m_size = size; + m_table = new wxHashTableBase_Node*[ m_size ]; + + for( size_t i = 0; i < m_size; ++i ) + m_table[i] = NULL; } -void wxHashTableLong::Init(size_t size) +void wxHashTableBase::Clear() { - m_hashSize = size; - m_values = new wxArrayLong *[size]; - m_keys = new wxArrayLong *[size]; - - for ( size_t n = 0; n < m_hashSize; n++ ) + for( size_t i = 0; i < m_size; ++i ) { - m_values[n] = - m_keys[n] = (wxArrayLong *)NULL; - } + Node* end = m_table[i]; - m_count = 0; -} + if( end == NULL ) + continue; -void wxHashTableLong::Create(size_t size) -{ - Init(size); -} + Node *curr, *next = end->GetNext(); -void wxHashTableLong::Destroy() -{ - for ( size_t n = 0; n < m_hashSize; n++ ) - { - delete m_values[n]; - delete m_keys[n]; - } + do + { + curr = next; + next = curr->GetNext(); - delete [] m_values; - delete [] m_keys; - m_hashSize = 0; - m_count = 0; -} + DoDestroyNode( curr ); -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)); + delete curr; + } + while( curr != end ); - if ( !m_keys[slot] ) - { - m_keys[slot] = new wxArrayLong; - m_values[slot] = new wxArrayLong; + m_table[i] = NULL; } - m_keys[slot]->Add(key); - m_values[slot]->Add(value); - - m_count++; + m_count = 0; } -long wxHashTableLong::Get(long key) const +void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) { - wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); + size_t bucket = ( m_keyType == wxKEY_INTEGER ? + node->m_key.integer : + MakeKey( *node->m_key.string ) ) % m_size; - size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); - - wxArrayLong *keys = m_keys[slot]; - if ( keys ) + if( node->GetNext() == node ) { - size_t count = keys->GetCount(); - for ( size_t n = 0; n < count; n++ ) - { - if ( keys->Item(n) == key ) - { - return m_values[slot]->Item(n); - } - } + // single-node chain (common case) + m_table[bucket] = NULL; } - - 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 ) + else { - 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); + Node *start = m_table[bucket], *curr; + Node* prev = start; - keys->RemoveAt(n); - m_values[slot]->RemoveAt(n); + for( curr = prev->GetNext(); curr != node; + prev = curr, curr = curr->GetNext() ) ; - m_count--; - - return val; - } - } + DoUnlinkNode( bucket, node, prev ); } - return wxNOT_FOUND; + DoDestroyNode( node ); } -// ---------------------------------------------------------------------------- -// wxStringHashTable: more efficient than storing strings in a list -// ---------------------------------------------------------------------------- - -wxStringHashTable::wxStringHashTable(size_t sizeTable) +void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node ) { - m_keys = new wxArrayLong *[sizeTable]; - m_values = new wxArrayString *[sizeTable]; + // if it is called from DoRemoveNode, node has already been + // removed, from other places it does not matter + node->m_hashPtr = NULL; - m_hashSize = sizeTable; - for ( size_t n = 0; n < m_hashSize; n++ ) - { - m_values[n] = (wxArrayString *)NULL; - m_keys[n] = (wxArrayLong *)NULL; - } + if( m_keyType == wxKEY_STRING ) + delete node->m_key.string; + if( m_deleteContents ) + DoDeleteContents( node ); } -wxStringHashTable::~wxStringHashTable() +void wxHashTableBase::Destroy() { - Destroy(); -} + Clear(); -void wxStringHashTable::Destroy() -{ - for ( size_t n = 0; n < m_hashSize; n++ ) - { - delete m_values[n]; - delete m_keys[n]; - } + delete[] m_table; - delete [] m_values; - delete [] m_keys; - m_hashSize = 0; + m_table = NULL; + m_size = 0; } -void wxStringHashTable::Put(long key, const wxString& value) +void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node ) { - wxCHECK_RET( m_hashSize, _T("must call Create() first") ); - - size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); - - if ( !m_keys[slot] ) + if( m_table[bucket] == NULL ) { - m_keys[slot] = new wxArrayLong; - m_values[slot] = new wxArrayString; + m_table[bucket] = node->m_next = node; } - - 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 ) + else { - size_t count = keys->GetCount(); - for ( size_t n = 0; n < count; n++ ) - { - if ( keys->Item(n) == key ) - { - if ( wasFound ) - *wasFound = TRUE; + Node *prev = m_table[bucket]; + Node *next = prev->m_next; - return m_values[slot]->Item(n); - } - } + prev->m_next = node; + node->m_next = next; + m_table[bucket] = node; } - if ( wasFound ) - *wasFound = FALSE; - - return _T(""); + ++m_count; } -bool wxStringHashTable::Delete(long key) const +void wxHashTableBase::DoPut( long key, long hash, void* data ) { - wxCHECK_MSG( m_hashSize, FALSE, _T("must call Create() first") ); + wxASSERT( m_keyType == wxKEY_INTEGER ); - size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); - 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; + DoInsertNode( bucket, node ); } -#endif // WXWIN_COMPATIBILITY_2_4 - -// ---------------------------------------------------------------------------- -// old not type safe wxHashTable -// ---------------------------------------------------------------------------- - -wxHashTable::wxHashTable (int the_key_type, int size) +void wxHashTableBase::DoPut( const wxString& key, long hash, void* data ) { - 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; -*/ -} + wxASSERT( m_keyType == wxKEY_STRING ); -wxHashTable::~wxHashTable () -{ - Destroy(); -} + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); -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; + DoInsertNode( bucket, node ); } -bool wxHashTable::Create(int the_key_type, int size) +void* wxHashTableBase::DoGet( long key, long hash ) const { - 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; -} + wxASSERT( m_keyType == wxKEY_INTEGER ); + size_t bucket = size_t(hash) % m_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; - - 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]); - } - } -} + if( m_table[bucket] == NULL ) + return NULL; -void wxHashTable::Put (long key, long value, wxObject * object) -{ - // Should NEVER be - long k = (long) key; + Node *first = m_table[bucket]->GetNext(), + *curr = first; - int position = (int) (k % n); - if (position < 0) position = -position; + do + { + if( curr->m_key.integer == key ) + return curr->m_value; - if (!hash_table[position]) - { - hash_table[position] = new wxList (wxKEY_INTEGER); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + curr = curr->GetNext(); + } + while( curr != first ); - hash_table[position]->Append (value, object); - m_count++; + return NULL; } -void wxHashTable::Put (long key, const wxChar *value, wxObject * object) +void* wxHashTableBase::DoGet( const wxString& key, long hash ) const { - // Should NEVER be - long k = (long) key; + wxASSERT( m_keyType == wxKEY_STRING ); - int position = (int) (k % n); - if (position < 0) position = -position; + size_t bucket = size_t(hash) % m_size; - if (!hash_table[position]) - { - hash_table[position] = new wxList (wxKEY_STRING); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + if( m_table[bucket] == NULL ) + return NULL; - hash_table[position]->Append (value, object); - m_count++; -} + Node *first = m_table[bucket]->GetNext(), + *curr = first; -void wxHashTable::Put (long key, wxObject * object) -{ - // Should NEVER be - long k = (long) key; - - int position = (int) (k % n); - if (position < 0) position = -position; + do + { + if( *curr->m_key.string == key ) + return curr->m_value; - if (!hash_table[position]) - { - hash_table[position] = new wxList (wxKEY_INTEGER); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + curr = curr->GetNext(); + } + while( curr != first ); - hash_table[position]->Append (k, object); - m_count++; + return NULL; } -void wxHashTable::Put (const wxChar *key, wxObject * object) +void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, + wxHashTableBase_Node* prev ) { - int position = (int) (MakeKey (key) % n); - if (position < 0) position = -position; + if( node == m_table[bucket] ) + m_table[bucket] = prev; - if (!hash_table[position]) - { - hash_table[position] = new wxList (wxKEY_STRING); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + if( prev == node && prev == node->GetNext() ) + m_table[bucket] = NULL; + else + prev->m_next = node->m_next; - hash_table[position]->Append (key, object); - m_count++; + DoDestroyNode( node ); + --m_count; } -wxObject *wxHashTable::Get (long key, long value) const +void* wxHashTableBase::DoDelete( long key, long hash ) { - // Should NEVER be - long k = (long) key; + wxASSERT( m_keyType == wxKEY_INTEGER ); - int position = (int) (k % n); - if (position < 0) position = -position; + size_t bucket = size_t(hash) % m_size; - if (!hash_table[position]) - return (wxObject *) NULL; - else - { - wxNode *node = hash_table[position]->Find (value); - if (node) - return node->GetData (); - else - return (wxObject *) NULL; - } -} + if( m_table[bucket] == NULL ) + return NULL; -wxObject *wxHashTable::Get (long key, const wxChar *value) const -{ - // Should NEVER be - long k = (long) key; + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; - int position = (int) (k % n); - if (position < 0) position = -position; - - if (!hash_table[position]) - return (wxObject *) NULL; - else + do { - wxNode *node = hash_table[position]->Find (value); - if (node) - return node->GetData (); - else - return (wxObject *) NULL; - } -} + if( curr->m_key.integer == key ) + { + void* retval = curr->m_value; + curr->m_value = NULL; -wxObject *wxHashTable::Get (long key) const -{ - // Should NEVER be - long k = (long) key; + DoUnlinkNode( bucket, curr, prev ); + delete curr; - int position = (int) (k % n); - if (position < 0) position = -position; + return retval; + } - if (!hash_table[position]) - return (wxObject *) NULL; - else - { - wxNode *node = hash_table[position]->Find (k); - return node ? node->GetData () : (wxObject*)NULL; + prev = curr; + curr = curr->GetNext(); } + while( curr != first ); + + return NULL; } -wxObject *wxHashTable::Get (const wxChar *key) const +void* wxHashTableBase::DoDelete( const wxString& key, long hash ) { - int position = (int) (MakeKey (key) % n); - if (position < 0) position = -position; + wxASSERT( m_keyType == wxKEY_STRING ); - if (!hash_table[position]) - return (wxObject *) NULL; - else - { - wxNode *node = hash_table[position]->Find (key); - return node ? node->GetData () : (wxObject*)NULL; - } -} + size_t bucket = size_t(hash) % m_size; -wxObject *wxHashTable::Delete (long key) -{ - // Should NEVER be - long k = (long) key; + if( m_table[bucket] == NULL ) + return NULL; - int position = (int) (k % n); - if (position < 0) position = -position; + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; - if (!hash_table[position]) - return (wxObject *) NULL; - else + do { - wxNode *node = hash_table[position]->Find (k); - if (node) + if( *curr->m_key.string == key ) { - wxObject *data = node->GetData (); - delete node; - m_count--; - return data; - } - else - return (wxObject *) NULL; - } -} + void* retval = curr->m_value; + curr->m_value = NULL; -wxObject *wxHashTable::Delete (const wxChar *key) -{ - int position = (int) (MakeKey (key) % n); - if (position < 0) position = -position; + DoUnlinkNode( bucket, curr, prev ); + delete curr; - 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; + return retval; } - else - return (wxObject *) NULL; + + prev = curr; + curr = curr->GetNext(); } + while( curr != first ); + + return NULL; } -wxObject *wxHashTable::Delete (long key, int value) +long wxHashTableBase::MakeKey( const wxString& str ) { - // Should NEVER be - long k = (long) key; + long int_key = 0; - int position = (int) (k % n); - if (position < 0) position = -position; + const wxStringCharType *p = str.wx_str(); + while( *p ) + int_key += *p++; - 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; - } + return int_key; } -wxObject *wxHashTable::Delete (long key, const wxChar *value) -{ - int position = (int) (key % n); - if (position < 0) position = -position; +// ---------------------------------------------------------------------------- +// wxHashTable +// ---------------------------------------------------------------------------- - 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; - } +wxHashTable::wxHashTable( const wxHashTable& table ) + : wxHashTableBase() +{ + DoCopy( table ); } -long wxHashTable::MakeKey (const wxChar *string) const +const wxHashTable& wxHashTable::operator=( const wxHashTable& table ) { - long int_key = 0; + Destroy(); + DoCopy( table ); - while (*string) - int_key += (wxUChar) *string++; + return *this; +} + +void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) ) +{ + Create( m_keyType, m_size ); - return int_key; + wxFAIL; } -void wxHashTable::BeginFind () +void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node ) { - current_position = -1; - current_node = (wxNode *) NULL; + delete ((wxHashTable_Node*)node)->GetData(); } -wxNode *wxHashTable::Next () +void wxHashTable::GetNextNode( size_t bucketStart ) { - wxNode *found = (wxNode *) NULL; - bool end = FALSE; - while (!end && !found) + for( size_t i = bucketStart; i < m_size; ++i ) { - if (!current_node) + if( m_table[i] != NULL ) { - 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; + m_curr = ((Node*)m_table[i])->GetNext(); + m_currBucket = i; + return; } } - 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); - } + m_curr = NULL; + m_currBucket = 0; } -void wxHashTable::Clear () +wxHashTable::Node* wxHashTable::Next() { - int i; - if (hash_table) + if( m_curr == NULL ) + GetNextNode( 0 ); + else { - for (i = 0; i < n; i++) - { - if (hash_table[i]) - hash_table[i]->Clear (); - } + m_curr = m_curr->GetNext(); + + if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() ) + GetNextNode( m_currBucket + 1 ); } - m_count = 0; + + return m_curr; } -#endif // !wxUSE_STL