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 #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     delete[] m_table;
 138
 139     m_table = NULL;
 140     m_size = 0;
 141 }
 142
 143 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
 144 {
 145     if( m_table[bucket] == NULL )
 146     {
 147         m_table[bucket] = node->m_next = node;
 148     }
 149     else
 150     {
 151         Node *prev = m_table[bucket];
 152         Node *next = prev->m_next;
 153
 154         prev->m_next = node;
 155         node->m_next = next;
 156         m_table[bucket] = node;
 157     }
 158
 159     ++m_count;
 160 }
 161
 162 void wxHashTableBase::DoPut( long key, long hash, void* data )
 163 {
 164     wxASSERT( m_keyType == wxKEY_INTEGER );
 165
 166     size_t bucket = size_t(hash) % m_size;
 167     Node* node = new wxHashTableBase_Node( key, data, this );
 168
 169     DoInsertNode( bucket, node );
 170 }
 171
 172 void wxHashTableBase::DoPut( const wxString& key, long hash, void* data )
 173 {
 174     wxASSERT( m_keyType == wxKEY_STRING );
 175
 176     size_t bucket = size_t(hash) % m_size;
 177     Node* node = new wxHashTableBase_Node( key, data, this );
 178
 179     DoInsertNode( bucket, node );
 180 }
 181
 182 void* wxHashTableBase::DoGet( long key, long hash ) const
 183 {
 184     wxASSERT( m_keyType == wxKEY_INTEGER );
 185
 186     size_t bucket = size_t(hash) % m_size;
 187
 188     if( m_table[bucket] == NULL )
 189         return NULL;
 190
 191     Node *first = m_table[bucket]->GetNext(),
 192          *curr = first;
 193
 194     do
 195     {
 196         if( curr->m_key.integer == key )
 197             return curr->m_value;
 198
 199         curr = curr->GetNext();
 200     }
 201     while( curr != first );
 202
 203     return NULL;
 204 }
 205
 206 void* wxHashTableBase::DoGet( const wxString& key, long hash ) const
 207 {
 208     wxASSERT( m_keyType == wxKEY_STRING );
 209
 210     size_t bucket = size_t(hash) % m_size;
 211
 212     if( m_table[bucket] == NULL )
 213         return NULL;
 214
 215     Node *first = m_table[bucket]->GetNext(),
 216          *curr = first;
 217
 218     do
 219     {
 220         if( *curr->m_key.string == key )
 221             return curr->m_value;
 222
 223         curr = curr->GetNext();
 224     }
 225     while( curr != first );
 226
 227     return NULL;
 228 }
 229
 230 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
 231                                     wxHashTableBase_Node* prev )
 232 {
 233     if( node == m_table[bucket] )
 234         m_table[bucket] = prev;
 235
 236     if( prev == node && prev == node->GetNext() )
 237         m_table[bucket] = NULL;
 238     else
 239         prev->m_next = node->m_next;
 240
 241     DoDestroyNode( node );
 242     --m_count;
 243 }
 244
 245 void* wxHashTableBase::DoDelete( long key, long hash )
 246 {
 247     wxASSERT( m_keyType == wxKEY_INTEGER );
 248
 249     size_t bucket = size_t(hash) % m_size;
 250
 251     if( m_table[bucket] == NULL )
 252         return NULL;
 253
 254     Node *first = m_table[bucket]->GetNext(),
 255          *curr = first,
 256          *prev = m_table[bucket];
 257
 258     do
 259     {
 260         if( curr->m_key.integer == key )
 261         {
 262             void* retval = curr->m_value;
 263             curr->m_value = NULL;
 264
 265             DoUnlinkNode( bucket, curr, prev );
 266             delete curr;
 267
 268             return retval;
 269         }
 270
 271         prev = curr;
 272         curr = curr->GetNext();
 273     }
 274     while( curr != first );
 275
 276     return NULL;
 277 }
 278
 279 void* wxHashTableBase::DoDelete( const wxString& key, long hash )
 280 {
 281     wxASSERT( m_keyType == wxKEY_STRING );
 282
 283     size_t bucket = size_t(hash) % m_size;
 284
 285     if( m_table[bucket] == NULL )
 286         return NULL;
 287
 288     Node *first = m_table[bucket]->GetNext(),
 289          *curr = first,
 290          *prev = m_table[bucket];
 291
 292     do
 293     {
 294         if( *curr->m_key.string == key )
 295         {
 296             void* retval = curr->m_value;
 297             curr->m_value = NULL;
 298
 299             DoUnlinkNode( bucket, curr, prev );
 300             delete curr;
 301
 302             return retval;
 303         }
 304
 305         prev = curr;
 306         curr = curr->GetNext();
 307     }
 308     while( curr != first );
 309
 310     return NULL;
 311 }
 312
 313 long wxHashTableBase::MakeKey( const wxString& str )
 314 {
 315     long int_key = 0;
 316
 317     const wxStringCharType *p = str.wx_str();
 318     while( *p )
 319         int_key += *p++;
 320
 321     return int_key;
 322 }
 323
 324 // ----------------------------------------------------------------------------
 325 // wxHashTable
 326 // ----------------------------------------------------------------------------
 327
 328 wxHashTable::wxHashTable( const wxHashTable& table )
 329            : wxHashTableBase()
 330 {
 331     DoCopy( table );
 332 }
 333
 334 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
 335 {
 336     Destroy();
 337     DoCopy( table );
 338
 339     return *this;
 340 }
 341
 342 void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
 343 {
 344     Create( m_keyType, m_size );
 345
 346     wxFAIL;
 347 }
 348
 349 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
 350 {
 351     delete ((wxHashTable_Node*)node)->GetData();
 352 }
 353
 354 void wxHashTable::GetNextNode( size_t bucketStart )
 355 {
 356     for( size_t i = bucketStart; i < m_size; ++i )
 357     {
 358         if( m_table[i] != NULL )
 359         {
 360             m_curr = ((Node*)m_table[i])->GetNext();
 361             m_currBucket = i;
 362             return;
 363         }
 364     }
 365
 366     m_curr = NULL;
 367     m_currBucket = 0;
 368 }
 369
 370 wxHashTable::Node* wxHashTable::Next()
 371 {
 372     if( m_curr == NULL )
 373         GetNextNode( 0 );
 374     else
 375     {
 376         m_curr = m_curr->GetNext();
 377
 378         if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
 379             GetNextNode( m_currBucket + 1 );
 380     }
 381
 382     return m_curr;
 383 }
 384