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