X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/c2bb85e9e38ee35758e0076485bb6665f2c229f5..69659fd770f615210efac4b4fa741b3ad6223616:/src/common/hash.cpp?ds=sidebyside diff --git a/src/common/hash.cpp b/src/common/hash.cpp index 1aa13adf84..1e36fec843 100644 --- a/src/common/hash.cpp +++ b/src/common/hash.cpp @@ -1,11 +1,11 @@ ///////////////////////////////////////////////////////////////////////////// -// 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() // Created: 01/02/97 // RCS-ID: $Id$ -// Copyright: (c) Julian Smart and Markus Holzem +// Copyright: (c) Julian Smart // Licence: wxWindows licence ///////////////////////////////////////////////////////////////////////////// @@ -17,587 +17,369 @@ // headers // ---------------------------------------------------------------------------- -#ifdef __GNUG__ -#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" - -#include -#include - -// ---------------------------------------------------------------------------- -// wxWin macros -// ---------------------------------------------------------------------------- +wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) +{ + m_key.integer = key; +} -IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject) +wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) +{ + m_key.string = new wxString(key); +} -// ============================================================================ -// implementation -// ============================================================================ +wxHashTableBase_Node::~wxHashTableBase_Node() +{ + if( m_hashPtr ) m_hashPtr->DoRemoveNode( this ); +} -// ---------------------------------------------------------------------------- -// wxHashTablleBase for working with "void *" data -// ---------------------------------------------------------------------------- +// wxHashTableBase::wxHashTableBase() + : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ), + m_deleteContents( false ) { - 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) +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; - } + m_size = size; + m_table = new wxHashTableBase_Node*[ m_size ]; + + for( size_t i = 0; i < m_size; ++i ) + m_table[i] = NULL; } -void wxHashTableBase::Destroy() +void wxHashTableBase::Clear() { - if ( m_hashTable ) + for( size_t i = 0; i < m_size; ++i ) { - for ( size_t n = 0; n < m_hashSize; n++ ) - { - delete m_hashTable[n]; - } + Node* end = m_table[i]; - delete [] m_hashTable; + if( end == NULL ) + continue; - m_hashTable = (wxListBase **)NULL; + Node *curr, *next = end->GetNext(); - m_count = 0; - } -} - -void wxHashTableBase::DeleteContents(bool flag) -{ - m_deleteContents = flag; - for ( size_t n = 0; n < m_hashSize; n++ ) - { - if ( m_hashTable[n] ) + do { - m_hashTable[n]->DeleteContents(flag); + curr = next; + next = curr->GetNext(); + + DoDestroyNode( curr ); + + delete curr; } + while( curr != end ); + + m_table[i] = NULL; } + + m_count = 0; } -wxNodeBase *wxHashTableBase::GetNode(long key, long value) const +void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) { - size_t slot = (size_t)abs(key % m_hashSize); + size_t bucket = ( m_keyType == wxKEY_INTEGER ? + node->m_key.integer : + MakeKey( *node->m_key.string ) ) % m_size; - wxNodeBase *node; - if ( m_hashTable[slot] ) + if( node->GetNext() == node ) { - node = m_hashTable[slot]->Find(wxListKey(value)); + // single-node chain (common case) + m_table[bucket] = NULL; } else { - node = (wxNodeBase *)NULL; - } + Node *start = m_table[bucket], *curr; + Node* prev = start; - return node; -} + for( curr = prev->GetNext(); curr != node; + prev = curr, curr = curr->GetNext() ) ; -// ---------------------------------------------------------------------------- -// wxHashTableLong -// ---------------------------------------------------------------------------- - -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; + DoUnlinkNode( bucket, node, prev ); } - m_count = 0; + DoDestroyNode( node ); } -void wxHashTableLong::Destroy() +void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node ) { - for ( size_t n = 0; n < m_hashSize; n++ ) - { - delete m_values[n]; - delete m_keys[n]; - } + // if it is called from DoRemoveNode, node has already been + // removed, from other places it does not matter + node->m_hashPtr = NULL; - delete [] m_values; - delete [] m_keys; - m_hashSize = 0; - m_count = 0; + if( m_keyType == wxKEY_STRING ) + delete node->m_key.string; + if( m_deleteContents ) + DoDeleteContents( node ); } -void wxHashTableLong::Put(long key, long value) +void wxHashTableBase::Destroy() { - wxCHECK_RET( m_hashSize, _T("must call Create() first") ); - - size_t slot = (size_t)abs(key % m_hashSize); - - if ( !m_keys[slot] ) - { - m_keys[slot] = new wxArrayLong; - m_values[slot] = new wxArrayLong; - } + Clear(); - m_keys[slot]->Add(key); - m_values[slot]->Add(value); + delete[] m_table; - m_count++; + m_table = NULL; + m_size = 0; } -long wxHashTableLong::Get(long key) const +void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node ) { - wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") ); - - size_t slot = (size_t)abs(key % m_hashSize); - - wxArrayLong *keys = m_keys[slot]; - if ( keys ) + if( m_table[bucket] == NULL ) { - size_t count = keys->GetCount(); - for ( size_t n = 0; n < count; n++ ) - { - if ( keys->Item(n) == key ) - { - return m_values[slot]->Item(n); - } - } + m_table[bucket] = node->m_next = node; } - - 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(key % 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 *prev = m_table[bucket]; + Node *next = prev->m_next; - keys->RemoveAt(n); - m_values[slot]->RemoveAt(n); - - m_count--; - - return val; - } - } + prev->m_next = node; + node->m_next = next; + m_table[bucket] = node; } - return wxNOT_FOUND; + ++m_count; } -// ---------------------------------------------------------------------------- -// old not type safe wxHashTable -// ---------------------------------------------------------------------------- - -wxHashTable::wxHashTable (int the_key_type, int size) +void wxHashTableBase::DoPut( long 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_INTEGER ); -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::DoPut( const wxString& key, long hash, void* data ) { - 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_STRING ); + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); -void wxHashTable::DoCopy(const wxHashTable& table) -{ - n = table.n; - 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]); - } - } + DoInsertNode( bucket, node ); } -void wxHashTable::Put (long key, long value, wxObject * object) +void* wxHashTableBase::DoGet( long key, long hash ) const { - // 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]) - { - hash_table[position] = new wxList (wxKEY_INTEGER); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + if( m_table[bucket] == NULL ) + return NULL; - 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; + 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, 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_INTEGER); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + if( m_table[bucket] == NULL ) + return NULL; - hash_table[position]->Append (k, object); - m_count++; -} + Node *first = m_table[bucket]->GetNext(), + *curr = first; -void wxHashTable::Put (const wxChar *key, wxObject * object) -{ - int position = (int) (MakeKey (key) % 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_STRING); - if (m_deleteContents) hash_table[position]->DeleteContents(TRUE); - } + curr = curr->GetNext(); + } + while( curr != first ); - hash_table[position]->Append (key, object); - m_count++; + return NULL; } -wxObject *wxHashTable::Get (long key, long value) const +void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, + wxHashTableBase_Node* prev ) { - // Should NEVER be - long k = (long) key; + if( node == m_table[bucket] ) + m_table[bucket] = prev; - int position = (int) (k % n); - if (position < 0) position = -position; + if( prev == node && prev == node->GetNext() ) + m_table[bucket] = NULL; + else + prev->m_next = node->m_next; - if (!hash_table[position]) - return (wxObject *) NULL; - else - { - wxNode *node = hash_table[position]->Find (value); - if (node) - return node->Data (); - else - return (wxObject *) NULL; - } + DoDestroyNode( node ); + --m_count; } -wxObject *wxHashTable::Get (long key, const wxChar *value) const +void* wxHashTableBase::DoDelete( long key, long hash ) { - // Should NEVER be - long k = (long) key; + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; - int position = (int) (k % n); - if (position < 0) position = -position; + if( m_table[bucket] == NULL ) + return NULL; - if (!hash_table[position]) - return (wxObject *) NULL; - else + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; + + do { - wxNode *node = hash_table[position]->Find (value); - if (node) - return node->Data (); - 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->Data () : (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->Data () : (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->Data (); - 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->Data (); - 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->Data (); - 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->Data (); - 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) - { - 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 + if( m_table[i] != NULL ) { - current_node = current_node->Next (); - 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; - for (i = 0; i < n; i++) + if( m_curr == NULL ) + GetNextNode( 0 ); + else { - 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; }