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