X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/55d99c7a77789ff4904bf96eddca3715eb5af9b9..254847461268bbc10cb90ca91d5feff411a16bc6:/src/common/hash.cpp diff --git a/src/common/hash.cpp b/src/common/hash.cpp index 9882539bb4..d2a71fa8d3 100644 --- a/src/common/hash.cpp +++ b/src/common/hash.cpp @@ -17,7 +17,7 @@ // headers // ---------------------------------------------------------------------------- -#ifdef __GNUG__ +#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) #pragma implementation "hash.h" #endif @@ -34,6 +34,8 @@ #include "wx/hash.h" +#if !wxUSE_STL + #include #include @@ -119,6 +121,8 @@ wxNodeBase *wxHashTableBase::GetNode(long key, long value) const return node; } +#if WXWIN_COMPATIBILITY_2_4 + // ---------------------------------------------------------------------------- // wxHashTableLong // ---------------------------------------------------------------------------- @@ -334,6 +338,8 @@ bool wxStringHashTable::Delete(long key) const return FALSE; } +#endif // WXWIN_COMPATIBILITY_2_4 + // ---------------------------------------------------------------------------- // old not type safe wxHashTable // ---------------------------------------------------------------------------- @@ -660,7 +666,7 @@ void wxHashTable::BeginFind () current_node = (wxNode *) NULL; } -wxNode *wxHashTable::Next () +wxHashTable::Node* wxHashTable::Next () { wxNode *found = (wxNode *) NULL; bool end = FALSE; @@ -718,3 +724,363 @@ void wxHashTable::Clear () m_count = 0; } +#else // if wxUSE_STL + +#include "wx/object.h" + +wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) +{ + m_key.integer = key; +} + +wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value, + wxHashTableBase* table ) + : m_value( value ), m_hashPtr( table ) +{ + m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key ); +} + +wxHashTableBase_Node::~wxHashTableBase_Node() +{ + if( m_hashPtr ) m_hashPtr->DoRemoveNode( this ); +} + +// + +wxHashTableBase::wxHashTableBase() + : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ), + m_deleteContents( false ) +{ +} + +wxHashTableBase::~wxHashTableBase() +{ + Destroy(); +} + +void wxHashTableBase::Create( wxKeyType keyType, size_t size ) +{ + 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 wxHashTableBase::Clear() +{ + for( size_t i = 0; i < m_size; ++i ) + { + Node* end = m_table[i]; + + if( end == NULL ) + continue; + + Node *curr, *next = end->GetNext(); + + do + { + curr = next; + next = curr->GetNext(); + + DoDestroyNode( curr ); + + delete curr; + } + while( curr != end ); + + m_table[i] = NULL; + } + + m_count = 0; +} + +void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node ) +{ + size_t bucket = ( m_keyType == wxKEY_INTEGER ? + node->m_key.integer : + MakeKey( node->m_key.string ) ) % m_size; + + if( node->GetNext() == node ) + { + // single-node chain (common case) + m_table[bucket] = NULL; + } + else + { + Node *start = m_table[bucket], *curr; + Node* prev = start; + + for( curr = prev->GetNext(); curr != node; + prev = curr, curr = curr->GetNext() ); + + DoUnlinkNode( bucket, node, prev ); + } + + DoDestroyNode( node ); +} + +void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node ) +{ + // if it is called from DoRemoveNode, node has already been + // removed, from other places it does not matter + node->m_hashPtr = NULL; + + if( m_keyType == wxKEY_STRING ) + delete[] node->m_key.string; + if( m_deleteContents ) + DoDeleteContents( node ); +} + +void wxHashTableBase::Destroy() +{ + Clear(); + + delete[] m_table; + + m_table = NULL; + m_size = 0; +} + +void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node ) +{ + if( m_table[bucket] == NULL ) + { + m_table[bucket] = node->m_next = node; + } + else + { + Node *prev = m_table[bucket]; + Node *next = prev->m_next; + + prev->m_next = node; + node->m_next = next; + m_table[bucket] = node; + } + + ++m_count; +} + +void wxHashTableBase::DoPut( long key, long hash, void* data ) +{ + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); + + DoInsertNode( bucket, node ); +} + +void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data ) +{ + wxASSERT( m_keyType == wxKEY_STRING ); + + size_t bucket = size_t(hash) % m_size; + Node* node = new wxHashTableBase_Node( key, data, this ); + + DoInsertNode( bucket, node ); +} + +void* wxHashTableBase::DoGet( long key, long hash ) const +{ + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first; + + do + { + if( curr->m_key.integer == key ) + return curr->m_value; + + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const +{ + wxASSERT( m_keyType == wxKEY_STRING ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first; + + do + { + if( wxStrcmp( curr->m_key.string, key ) == 0 ) + return curr->m_value; + + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, + wxHashTableBase_Node* prev ) +{ + if( node == m_table[bucket] ) + m_table[bucket] = prev; + + if( prev == node && prev == node->GetNext() ) + m_table[bucket] = NULL; + else + prev->m_next = node->m_next; + + DoDestroyNode( node ); + --m_count; +} + +void* wxHashTableBase::DoDelete( long key, long hash ) +{ + wxASSERT( m_keyType == wxKEY_INTEGER ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; + + do + { + if( curr->m_key.integer == key ) + { + void* retval = curr->m_value; + curr->m_value = NULL; + + DoUnlinkNode( bucket, curr, prev ); + delete curr; + + return retval; + } + + prev = curr; + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +void* wxHashTableBase::DoDelete( const wxChar* key, long hash ) +{ + wxASSERT( m_keyType == wxKEY_STRING ); + + size_t bucket = size_t(hash) % m_size; + + if( m_table[bucket] == NULL ) + return NULL; + + Node *first = m_table[bucket]->GetNext(), + *curr = first, + *prev = m_table[bucket]; + + do + { + if( wxStrcmp( curr->m_key.string, key ) == 0 ) + { + void* retval = curr->m_value; + curr->m_value = NULL; + + DoUnlinkNode( bucket, curr, prev ); + delete curr; + + return retval; + } + + prev = curr; + curr = curr->GetNext(); + } + while( curr != first ); + + return NULL; +} + +long wxHashTableBase::MakeKey( const wxChar *str ) +{ + long int_key = 0; + + while( *str ) + int_key += (wxUChar)*str++; + + return int_key; +} + +// + +wxHashTable::wxHashTable( const wxHashTable& table ) +{ + DoCopy( table ); +} + +const wxHashTable& wxHashTable::operator=( const wxHashTable& table ) +{ + Destroy(); + DoCopy( table ); + + return *this; +} + +void wxHashTable::DoCopy( const wxHashTable& table ) +{ + Create( m_keyType, m_size ); + + wxASSERT( false ); +} + +void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node ) +{ + delete ((wxHashTable_Node*)node)->GetData(); +} + +void wxHashTable::GetNextNode( size_t bucketStart ) +{ + for( size_t i = bucketStart; i < m_size; ++i ) + { + if( m_table[i] != NULL ) + { + m_curr = ((Node*)m_table[i])->GetNext(); + m_currBucket = i; + return; + } + } + + m_curr = NULL; + m_currBucket = 0; +} + +wxHashTable::Node* wxHashTable::Next() +{ + if( m_curr == NULL ) + GetNextNode( 0 ); + else + { + m_curr = m_curr->GetNext(); + + if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() ) + GetNextNode( m_currBucket + 1 ); + } + + return m_curr; +} + +#endif // wxUSE_STL