src/common/hash.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        src/common/hash.cpp
   3 // Purpose:     wxHashTable implementation
   4 // Author:      Julian Smart
   5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
   6 // Created:     01/02/97
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) Julian Smart
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 // ============================================================================
  13 // declarations
  14 // ============================================================================
  15
  16 // ----------------------------------------------------------------------------
  17 // headers
  18 // ----------------------------------------------------------------------------
  19
  20 // For compilers that support precompilation, includes "wx.h".
  21 #include "wx/wxprec.h"
  22
  23 #ifdef __BORLANDC__
  24     #pragma hdrstop
  25 #endif
  26
  27 #ifndef WX_PRECOMP
  28     #include "wx/hash.h"
  29     #include "wx/object.h"
  30 #endif
  31
  32 wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
  33                                             wxHashTableBase* table )
  34     : m_value( value ), m_hashPtr( table )
  35 {
  36     m_key.integer = key;
  37 }
  38
  39 wxHashTableBase_Node::wxHashTableBase_Node( const wxString& key, void* value,
  40                                             wxHashTableBase* table )
  41     : m_value( value ), m_hashPtr( table )
  42 {
  43     m_key.string = new wxString(key);
  44 }
  45
  46 wxHashTableBase_Node::~wxHashTableBase_Node()
  47 {
  48     if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
  49 }
  50
  51 //
  52
  53 wxHashTableBase::wxHashTableBase()
  54     : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
  55       m_deleteContents( false )
  56 {
  57 }
  58
  59 void wxHashTableBase::Create( wxKeyType keyType, size_t size )
  60 {
  61     m_keyType = keyType;
  62     m_size = size;
  63     m_table = new wxHashTableBase_Node*[ m_size ];
  64
  65     for( size_t i = 0; i < m_size; ++i )
  66         m_table[i] = NULL;
  67 }
  68
  69 void wxHashTableBase::Clear()
  70 {
  71     for( size_t i = 0; i < m_size; ++i )
  72     {
  73         Node* end = m_table[i];
  74
  75         if( end == NULL )
  76             continue;
  77
  78         Node *curr, *next = end->GetNext();
  79
  80         do
  81         {
  82             curr = next;
  83             next = curr->GetNext();
  84
  85             DoDestroyNode( curr );
  86
  87             delete curr;
  88         }
  89         while( curr != end );
  90
  91         m_table[i] = NULL;
  92     }
  93
  94     m_count = 0;
  95 }
  96
  97 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
  98 {
  99     size_t bucket = ( m_keyType == wxKEY_INTEGER ?
 100                       node->m_key.integer        :
 101                       MakeKey( *node->m_key.string ) ) % m_size;
 102
 103     if( node->GetNext() == node )
 104     {
 105         // single-node chain (common case)
 106         m_table[bucket] = NULL;
 107     }
 108     else
 109     {
 110         Node *start = m_table[bucket], *curr;
 111         Node* prev = start;
 112
 113         for( curr = prev->GetNext(); curr != node;
 114              prev = curr, curr = curr->GetNext() ) ;
 115
 116         DoUnlinkNode( bucket, node, prev );
 117     }
 118
 119     DoDestroyNode( node );
 120 }
 121
 122 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
 123 {
 124     // if it is called from DoRemoveNode, node has already been
 125     // removed, from other places it does not matter
 126     node->m_hashPtr = NULL;
 127
 128     if( m_keyType == wxKEY_STRING )
 129         delete node->m_key.string;
 130     if( m_deleteContents )
 131         DoDeleteContents( node );
 132 }
 133
 134 void wxHashTableBase::Destroy()
 135 {
 136     Clear();
 137
 138     delete[] m_table;
 139
 140     m_table = NULL;
 141     m_size = 0;
 142 }
 143
 144 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
 145 {
 146     if( m_table[bucket] == NULL )
 147     {
 148         m_table[bucket] = node->m_next = node;
 149     }
 150     else
 151     {
 152         Node *prev = m_table[bucket];
 153         Node *next = prev->m_next;
 154
 155         prev->m_next = node;
 156         node->m_next = next;
 157         m_table[bucket] = node;
 158     }
 159
 160     ++m_count;
 161 }
 162
 163 void wxHashTableBase::DoPut( long key, long hash, void* data )
 164 {
 165     wxASSERT( m_keyType == wxKEY_INTEGER );
 166
 167     size_t bucket = size_t(hash) % m_size;
 168     Node* node = new wxHashTableBase_Node( key, data, this );
 169
 170     DoInsertNode( bucket, node );
 171 }
 172
 173 void wxHashTableBase::DoPut( const wxString& key, long hash, void* data )
 174 {
 175     wxASSERT( m_keyType == wxKEY_STRING );
 176
 177     size_t bucket = size_t(hash) % m_size;
 178     Node* node = new wxHashTableBase_Node( key, data, this );
 179
 180     DoInsertNode( bucket, node );
 181 }
 182
 183 void* wxHashTableBase::DoGet( long key, long hash ) const
 184 {
 185     wxASSERT( m_keyType == wxKEY_INTEGER );
 186
 187     size_t bucket = size_t(hash) % m_size;
 188
 189     if( m_table[bucket] == NULL )
 190         return NULL;
 191
 192     Node *first = m_table[bucket]->GetNext(),
 193          *curr = first;
 194
 195     do
 196     {
 197         if( curr->m_key.integer == key )
 198             return curr->m_value;
 199
 200         curr = curr->GetNext();
 201     }
 202     while( curr != first );
 203
 204     return NULL;
 205 }
 206
 207 void* wxHashTableBase::DoGet( const wxString& key, long hash ) const
 208 {
 209     wxASSERT( m_keyType == wxKEY_STRING );
 210
 211     size_t bucket = size_t(hash) % m_size;
 212
 213     if( m_table[bucket] == NULL )
 214         return NULL;
 215
 216     Node *first = m_table[bucket]->GetNext(),
 217          *curr = first;
 218
 219     do
 220     {
 221         if( *curr->m_key.string == key )
 222             return curr->m_value;
 223
 224         curr = curr->GetNext();
 225     }
 226     while( curr != first );
 227
 228     return NULL;
 229 }
 230
 231 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
 232                                     wxHashTableBase_Node* prev )
 233 {
 234     if( node == m_table[bucket] )
 235         m_table[bucket] = prev;
 236
 237     if( prev == node && prev == node->GetNext() )
 238         m_table[bucket] = NULL;
 239     else
 240         prev->m_next = node->m_next;
 241
 242     DoDestroyNode( node );
 243     --m_count;
 244 }
 245
 246 void* wxHashTableBase::DoDelete( long key, long hash )
 247 {
 248     wxASSERT( m_keyType == wxKEY_INTEGER );
 249
 250     size_t bucket = size_t(hash) % m_size;
 251
 252     if( m_table[bucket] == NULL )
 253         return NULL;
 254
 255     Node *first = m_table[bucket]->GetNext(),
 256          *curr = first,
 257          *prev = m_table[bucket];
 258
 259     do
 260     {
 261         if( curr->m_key.integer == key )
 262         {
 263             void* retval = curr->m_value;
 264             curr->m_value = NULL;
 265
 266             DoUnlinkNode( bucket, curr, prev );
 267             delete curr;
 268
 269             return retval;
 270         }
 271
 272         prev = curr;
 273         curr = curr->GetNext();
 274     }
 275     while( curr != first );
 276
 277     return NULL;
 278 }
 279
 280 void* wxHashTableBase::DoDelete( const wxString& key, long hash )
 281 {
 282     wxASSERT( m_keyType == wxKEY_STRING );
 283
 284     size_t bucket = size_t(hash) % m_size;
 285
 286     if( m_table[bucket] == NULL )
 287         return NULL;
 288
 289     Node *first = m_table[bucket]->GetNext(),
 290          *curr = first,
 291          *prev = m_table[bucket];
 292
 293     do
 294     {
 295         if( *curr->m_key.string == key )
 296         {
 297             void* retval = curr->m_value;
 298             curr->m_value = NULL;
 299
 300             DoUnlinkNode( bucket, curr, prev );
 301             delete curr;
 302
 303             return retval;
 304         }
 305
 306         prev = curr;
 307         curr = curr->GetNext();
 308     }
 309     while( curr != first );
 310
 311     return NULL;
 312 }
 313
 314 long wxHashTableBase::MakeKey( const wxString& str )
 315 {
 316     long int_key = 0;
 317
 318     const wxStringCharType *p = str.wx_str();
 319     while( *p )
 320         int_key += *p++;
 321
 322     return int_key;
 323 }
 324
 325 // ----------------------------------------------------------------------------
 326 // wxHashTable
 327 // ----------------------------------------------------------------------------
 328
 329 wxHashTable::wxHashTable( const wxHashTable& table )
 330            : wxHashTableBase()
 331 {
 332     DoCopy( table );
 333 }
 334
 335 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
 336 {
 337     Destroy();
 338     DoCopy( table );
 339
 340     return *this;
 341 }
 342
 343 void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
 344 {
 345     Create( m_keyType, m_size );
 346
 347     wxFAIL;
 348 }
 349
 350 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
 351 {
 352     delete ((wxHashTable_Node*)node)->GetData();
 353 }
 354
 355 void wxHashTable::GetNextNode( size_t bucketStart )
 356 {
 357     for( size_t i = bucketStart; i < m_size; ++i )
 358     {
 359         if( m_table[i] != NULL )
 360         {
 361             m_curr = ((Node*)m_table[i])->GetNext();
 362             m_currBucket = i;
 363             return;
 364         }
 365     }
 366
 367     m_curr = NULL;
 368     m_currBucket = 0;
 369 }
 370
 371 wxHashTable::Node* wxHashTable::Next()
 372 {
 373     if( m_curr == NULL )
 374         GetNextNode( 0 );
 375     else
 376     {
 377         m_curr = m_curr->GetNext();
 378
 379         if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
 380             GetNextNode( m_currBucket + 1 );
 381     }
 382
 383     return m_curr;
 384 }
 385