src/common/hash.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        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 #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
  21 #pragma implementation "hash.h"
  22 #endif
  23
  24 // For compilers that support precompilation, includes "wx.h".
  25 #include "wx/wxprec.h"
  26
  27 #ifdef __BORLANDC__
  28 #pragma hdrstop
  29 #endif
  30
  31 #ifndef WX_PRECOMP
  32 #include "wx/list.h"
  33 #endif
  34
  35 #include "wx/hash.h"
  36
  37 #if !wxUSE_STL
  38
  39 #include <string.h>
  40 #include <stdarg.h>
  41
  42 // ----------------------------------------------------------------------------
  43 // wxWin macros
  44 // ----------------------------------------------------------------------------
  45
  46 IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
  47
  48 // ============================================================================
  49 // implementation
  50 // ============================================================================
  51
  52 // ----------------------------------------------------------------------------
  53 // wxHashTablleBase for working with "void *" data
  54 // ----------------------------------------------------------------------------
  55
  56 wxHashTableBase::wxHashTableBase()
  57 {
  58     m_deleteContents = FALSE;
  59     m_hashTable = (wxListBase **)NULL;
  60     m_hashSize = 0;
  61     m_count = 0;
  62     m_keyType = wxKEY_NONE;
  63 }
  64
  65 void wxHashTableBase::Create(wxKeyType keyType, size_t size)
  66 {
  67     Destroy();
  68
  69     m_hashSize = size;
  70     m_keyType = keyType;
  71     m_hashTable = new wxListBase *[size];
  72     for ( size_t n = 0; n < m_hashSize; n++ )
  73     {
  74         m_hashTable[n] = (wxListBase *) NULL;
  75     }
  76 }
  77
  78 void wxHashTableBase::Destroy()
  79 {
  80     if ( m_hashTable )
  81     {
  82         for ( size_t n = 0; n < m_hashSize; n++ )
  83         {
  84             delete m_hashTable[n];
  85         }
  86
  87         delete [] m_hashTable;
  88
  89         m_hashTable = (wxListBase **)NULL;
  90
  91         m_count = 0;
  92     }
  93 }
  94
  95 void wxHashTableBase::DeleteContents(bool flag)
  96 {
  97     m_deleteContents = flag;
  98     for ( size_t n = 0; n < m_hashSize; n++ )
  99     {
 100         if ( m_hashTable[n] )
 101         {
 102             m_hashTable[n]->DeleteContents(flag);
 103         }
 104     }
 105 }
 106
 107 wxNodeBase *wxHashTableBase::GetNode(long key, long value) const
 108 {
 109     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 110
 111     wxNodeBase *node;
 112     if ( m_hashTable[slot] )
 113     {
 114         node = m_hashTable[slot]->Find(wxListKey(value));
 115     }
 116     else
 117     {
 118         node = (wxNodeBase *)NULL;
 119     }
 120
 121     return node;
 122 }
 123
 124 #if WXWIN_COMPATIBILITY_2_4
 125
 126 // ----------------------------------------------------------------------------
 127 // wxHashTableLong
 128 // ----------------------------------------------------------------------------
 129
 130 wxHashTableLong::~wxHashTableLong()
 131 {
 132     Destroy();
 133 }
 134
 135 void wxHashTableLong::Init(size_t size)
 136 {
 137     m_hashSize = size;
 138     m_values = new wxArrayLong *[size];
 139     m_keys = new wxArrayLong *[size];
 140
 141     for ( size_t n = 0; n < m_hashSize; n++ )
 142     {
 143         m_values[n] =
 144         m_keys[n] = (wxArrayLong *)NULL;
 145     }
 146
 147     m_count = 0;
 148 }
 149
 150 void wxHashTableLong::Create(size_t size)
 151 {
 152     Init(size);
 153 }
 154
 155 void wxHashTableLong::Destroy()
 156 {
 157     for ( size_t n = 0; n < m_hashSize; n++ )
 158     {
 159         delete m_values[n];
 160         delete m_keys[n];
 161     }
 162
 163     delete [] m_values;
 164     delete [] m_keys;
 165     m_hashSize = 0;
 166     m_count = 0;
 167 }
 168
 169 void wxHashTableLong::Put(long key, long value)
 170 {
 171     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 172
 173     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 174
 175     if ( !m_keys[slot] )
 176     {
 177         m_keys[slot] = new wxArrayLong;
 178         m_values[slot] = new wxArrayLong;
 179     }
 180
 181     m_keys[slot]->Add(key);
 182     m_values[slot]->Add(value);
 183
 184     m_count++;
 185 }
 186
 187 long wxHashTableLong::Get(long key) const
 188 {
 189     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 190
 191     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 192
 193     wxArrayLong *keys = m_keys[slot];
 194     if ( keys )
 195     {
 196         size_t count = keys->GetCount();
 197         for ( size_t n = 0; n < count; n++ )
 198         {
 199             if ( keys->Item(n) == key )
 200             {
 201                 return m_values[slot]->Item(n);
 202             }
 203         }
 204     }
 205
 206     return wxNOT_FOUND;
 207 }
 208
 209 long wxHashTableLong::Delete(long key)
 210 {
 211     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 212
 213     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 214
 215     wxArrayLong *keys = m_keys[slot];
 216     if ( keys )
 217     {
 218         size_t count = keys->GetCount();
 219         for ( size_t n = 0; n < count; n++ )
 220         {
 221             if ( keys->Item(n) == key )
 222             {
 223                 long val = m_values[slot]->Item(n);
 224
 225                 keys->RemoveAt(n);
 226                 m_values[slot]->RemoveAt(n);
 227
 228                 m_count--;
 229
 230                 return val;
 231             }
 232         }
 233     }
 234
 235     return wxNOT_FOUND;
 236 }
 237
 238 // ----------------------------------------------------------------------------
 239 // wxStringHashTable: more efficient than storing strings in a list
 240 // ----------------------------------------------------------------------------
 241
 242 wxStringHashTable::wxStringHashTable(size_t sizeTable)
 243 {
 244     m_keys = new wxArrayLong *[sizeTable];
 245     m_values = new wxArrayString *[sizeTable];
 246
 247     m_hashSize = sizeTable;
 248     for ( size_t n = 0; n < m_hashSize; n++ )
 249     {
 250         m_values[n] = (wxArrayString *)NULL;
 251         m_keys[n] = (wxArrayLong *)NULL;
 252     }
 253 }
 254
 255 wxStringHashTable::~wxStringHashTable()
 256 {
 257     Destroy();
 258 }
 259
 260 void wxStringHashTable::Destroy()
 261 {
 262     for ( size_t n = 0; n < m_hashSize; n++ )
 263     {
 264         delete m_values[n];
 265         delete m_keys[n];
 266     }
 267
 268     delete [] m_values;
 269     delete [] m_keys;
 270     m_hashSize = 0;
 271 }
 272
 273 void wxStringHashTable::Put(long key, const wxString& value)
 274 {
 275     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 276
 277     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 278
 279     if ( !m_keys[slot] )
 280     {
 281         m_keys[slot] = new wxArrayLong;
 282         m_values[slot] = new wxArrayString;
 283     }
 284
 285     m_keys[slot]->Add(key);
 286     m_values[slot]->Add(value);
 287 }
 288
 289 wxString wxStringHashTable::Get(long key, bool *wasFound) const
 290 {
 291     wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );
 292
 293     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 294
 295     wxArrayLong *keys = m_keys[slot];
 296     if ( keys )
 297     {
 298         size_t count = keys->GetCount();
 299         for ( size_t n = 0; n < count; n++ )
 300         {
 301             if ( keys->Item(n) == key )
 302             {
 303                 if ( wasFound )
 304                     *wasFound = TRUE;
 305
 306                 return m_values[slot]->Item(n);
 307             }
 308         }
 309     }
 310
 311     if ( wasFound )
 312         *wasFound = FALSE;
 313
 314     return _T("");
 315 }
 316
 317 bool wxStringHashTable::Delete(long key) const
 318 {
 319     wxCHECK_MSG( m_hashSize, FALSE, _T("must call Create() first") );
 320
 321     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 322
 323     wxArrayLong *keys = m_keys[slot];
 324     if ( keys )
 325     {
 326         size_t count = keys->GetCount();
 327         for ( size_t n = 0; n < count; n++ )
 328         {
 329             if ( keys->Item(n) == key )
 330             {
 331                 keys->RemoveAt(n);
 332                 m_values[slot]->RemoveAt(n);
 333                 return TRUE;
 334             }
 335         }
 336     }
 337
 338     return FALSE;
 339 }
 340
 341 #endif // WXWIN_COMPATIBILITY_2_4
 342
 343 // ----------------------------------------------------------------------------
 344 // old not type safe wxHashTable
 345 // ----------------------------------------------------------------------------
 346
 347 wxHashTable::wxHashTable (int the_key_type, int size)
 348 {
 349   n = 0;
 350   hash_table = (wxList**) NULL;
 351   Create(the_key_type, size);
 352   m_count = 0;
 353   m_deleteContents = FALSE;
 354 /*
 355   n = size;
 356   current_position = -1;
 357   current_node = (wxNode *) NULL;
 358
 359   key_type = the_key_type;
 360   hash_table = new wxList *[size];
 361   int i;
 362   for (i = 0; i < size; i++)
 363     hash_table[i] = (wxList *) NULL;
 364 */
 365 }
 366
 367 wxHashTable::~wxHashTable ()
 368 {
 369   Destroy();
 370 }
 371
 372 void wxHashTable::Destroy()
 373 {
 374   if (!hash_table) return;
 375   int i;
 376   for (i = 0; i < n; i++)
 377     if (hash_table[i])
 378       delete hash_table[i];
 379   delete[] hash_table;
 380   hash_table = NULL;
 381 }
 382
 383 bool wxHashTable::Create(int the_key_type, int size)
 384 {
 385   Destroy();
 386
 387   n = size;
 388   current_position = -1;
 389   current_node = (wxNode *) NULL;
 390
 391   key_type = the_key_type;
 392   hash_table = new wxList *[size];
 393   int i;
 394   for (i = 0; i < size; i++)
 395     hash_table[i] = (wxList *) NULL;
 396   return TRUE;
 397 }
 398
 399
 400 void wxHashTable::DoCopy(const wxHashTable& table)
 401 {
 402   n = table.n;
 403   m_count = table.m_count;
 404   current_position = table.current_position;
 405   current_node = NULL; // doesn't matter - Next() will reconstruct it
 406   key_type = table.key_type;
 407
 408   hash_table = new wxList *[n];
 409   for (int i = 0; i < n; i++) {
 410     if (table.hash_table[i] == NULL)
 411       hash_table[i] = NULL;
 412     else {
 413       hash_table[i] = new wxList(key_type);
 414       *(hash_table[i]) = *(table.hash_table[i]);
 415     }
 416   }
 417 }
 418
 419 void wxHashTable::Put (long key, long value, wxObject * object)
 420 {
 421   // Should NEVER be
 422   long k = (long) key;
 423
 424   int position = (int) (k % n);
 425   if (position < 0) position = -position;
 426
 427   if (!hash_table[position])
 428   {
 429     hash_table[position] = new wxList (wxKEY_INTEGER);
 430     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 431   }
 432
 433   hash_table[position]->Append (value, object);
 434   m_count++;
 435 }
 436
 437 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 438 {
 439   // Should NEVER be
 440   long k = (long) key;
 441
 442   int position = (int) (k % n);
 443   if (position < 0) position = -position;
 444
 445   if (!hash_table[position])
 446   {
 447     hash_table[position] = new wxList (wxKEY_STRING);
 448     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 449   }
 450
 451   hash_table[position]->Append (value, object);
 452   m_count++;
 453 }
 454
 455 void wxHashTable::Put (long key, wxObject * object)
 456 {
 457   // Should NEVER be
 458   long k = (long) key;
 459
 460   int position = (int) (k % n);
 461   if (position < 0) position = -position;
 462
 463   if (!hash_table[position])
 464   {
 465     hash_table[position] = new wxList (wxKEY_INTEGER);
 466     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 467   }
 468
 469   hash_table[position]->Append (k, object);
 470   m_count++;
 471 }
 472
 473 void wxHashTable::Put (const wxChar *key, wxObject * object)
 474 {
 475   int position = (int) (MakeKey (key) % n);
 476   if (position < 0) position = -position;
 477
 478   if (!hash_table[position])
 479   {
 480     hash_table[position] = new wxList (wxKEY_STRING);
 481     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 482   }
 483
 484   hash_table[position]->Append (key, object);
 485   m_count++;
 486 }
 487
 488 wxObject *wxHashTable::Get (long key, long value) const
 489 {
 490   // Should NEVER be
 491   long k = (long) key;
 492
 493   int position = (int) (k % n);
 494   if (position < 0) position = -position;
 495
 496   if (!hash_table[position])
 497     return (wxObject *) NULL;
 498   else
 499     {
 500       wxNode *node = hash_table[position]->Find (value);
 501       if (node)
 502         return node->GetData ();
 503       else
 504         return (wxObject *) NULL;
 505     }
 506 }
 507
 508 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 509 {
 510   // Should NEVER be
 511   long k = (long) key;
 512
 513   int position = (int) (k % n);
 514   if (position < 0) position = -position;
 515
 516   if (!hash_table[position])
 517     return (wxObject *) NULL;
 518   else
 519     {
 520       wxNode *node = hash_table[position]->Find (value);
 521       if (node)
 522         return node->GetData ();
 523       else
 524         return (wxObject *) NULL;
 525     }
 526 }
 527
 528 wxObject *wxHashTable::Get (long key) const
 529 {
 530   // Should NEVER be
 531   long k = (long) key;
 532
 533   int position = (int) (k % n);
 534   if (position < 0) position = -position;
 535
 536   if (!hash_table[position])
 537     return (wxObject *) NULL;
 538   else
 539     {
 540       wxNode *node = hash_table[position]->Find (k);
 541       return node ? node->GetData () : (wxObject*)NULL;
 542     }
 543 }
 544
 545 wxObject *wxHashTable::Get (const wxChar *key) const
 546 {
 547   int position = (int) (MakeKey (key) % n);
 548   if (position < 0) position = -position;
 549
 550   if (!hash_table[position])
 551     return (wxObject *) NULL;
 552   else
 553     {
 554       wxNode *node = hash_table[position]->Find (key);
 555       return node ? node->GetData () : (wxObject*)NULL;
 556     }
 557 }
 558
 559 wxObject *wxHashTable::Delete (long key)
 560 {
 561   // Should NEVER be
 562   long k = (long) key;
 563
 564   int position = (int) (k % n);
 565   if (position < 0) position = -position;
 566
 567   if (!hash_table[position])
 568     return (wxObject *) NULL;
 569   else
 570     {
 571       wxNode *node = hash_table[position]->Find (k);
 572       if (node)
 573         {
 574           wxObject *data = node->GetData ();
 575           delete node;
 576           m_count--;
 577           return data;
 578         }
 579       else
 580         return (wxObject *) NULL;
 581     }
 582 }
 583
 584 wxObject *wxHashTable::Delete (const wxChar *key)
 585 {
 586   int position = (int) (MakeKey (key) % n);
 587   if (position < 0) position = -position;
 588
 589   if (!hash_table[position])
 590     return (wxObject *) NULL;
 591   else
 592     {
 593       wxNode *node = hash_table[position]->Find (key);
 594       if (node)
 595         {
 596           wxObject *data = node->GetData ();
 597           delete node;
 598           m_count--;
 599           return data;
 600         }
 601       else
 602         return (wxObject *) NULL;
 603     }
 604 }
 605
 606 wxObject *wxHashTable::Delete (long key, int value)
 607 {
 608   // Should NEVER be
 609   long k = (long) key;
 610
 611   int position = (int) (k % n);
 612   if (position < 0) position = -position;
 613
 614   if (!hash_table[position])
 615     return (wxObject *) NULL;
 616   else
 617     {
 618       wxNode *node = hash_table[position]->Find (value);
 619       if (node)
 620         {
 621           wxObject *data = node->GetData ();
 622           delete node;
 623           m_count--;
 624           return data;
 625         }
 626       else
 627         return (wxObject *) NULL;
 628     }
 629 }
 630
 631 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 632 {
 633   int position = (int) (key % n);
 634   if (position < 0) position = -position;
 635
 636   if (!hash_table[position])
 637     return (wxObject *) NULL;
 638   else
 639     {
 640       wxNode *node = hash_table[position]->Find (value);
 641       if (node)
 642         {
 643           wxObject *data = node->GetData ();
 644           delete node;
 645           m_count--;
 646           return data;
 647         }
 648       else
 649         return (wxObject *) NULL;
 650     }
 651 }
 652
 653 long wxHashTable::MakeKey (const wxChar *string) const
 654 {
 655   long int_key = 0;
 656
 657   while (*string)
 658     int_key += (wxUChar) *string++;
 659
 660   return int_key;
 661 }
 662
 663 void wxHashTable::BeginFind ()
 664 {
 665   current_position = -1;
 666   current_node = (wxNode *) NULL;
 667 }
 668
 669 wxHashTable::Node* wxHashTable::Next ()
 670 {
 671   wxNode *found = (wxNode *) NULL;
 672   bool end = FALSE;
 673   while (!end && !found)
 674     {
 675       if (!current_node)
 676         {
 677           current_position++;
 678           if (current_position >= n)
 679             {
 680               current_position = -1;
 681               current_node = (wxNode *) NULL;
 682               end = TRUE;
 683             }
 684           else
 685             {
 686               if (hash_table[current_position])
 687                 {
 688                   current_node = hash_table[current_position]->GetFirst ();
 689                   found = current_node;
 690                 }
 691             }
 692         }
 693       else
 694         {
 695           current_node = current_node->GetNext ();
 696           found = current_node;
 697         }
 698     }
 699   return found;
 700 }
 701
 702 void wxHashTable::DeleteContents (bool flag)
 703 {
 704   int i;
 705   m_deleteContents = flag;
 706   for (i = 0; i < n; i++)
 707     {
 708       if (hash_table[i])
 709         hash_table[i]->DeleteContents (flag);
 710     }
 711 }
 712
 713 void wxHashTable::Clear ()
 714 {
 715     int i;
 716     if (hash_table)
 717     {
 718         for (i = 0; i < n; i++)
 719         {
 720             if (hash_table[i])
 721                 hash_table[i]->Clear ();
 722         }
 723     }
 724   m_count = 0;
 725 }
 726
 727 #else // if wxUSE_STL
 728
 729 #include "wx/object.h"
 730
 731 wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
 732                                             wxHashTableBase* table )
 733     : m_value( value ), m_hashPtr( table )
 734 {
 735     m_key.integer = key;
 736 }
 737
 738 wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value,
 739                                             wxHashTableBase* table )
 740     : m_value( value ), m_hashPtr( table )
 741 {
 742     m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key );
 743 }
 744
 745 wxHashTableBase_Node::~wxHashTableBase_Node()
 746 {
 747     if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
 748 }
 749
 750 //
 751
 752 wxHashTableBase::wxHashTableBase()
 753     : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
 754       m_deleteContents( false )
 755 {
 756 }
 757
 758 wxHashTableBase::~wxHashTableBase()
 759 {
 760     Destroy();
 761 }
 762
 763 void wxHashTableBase::Create( wxKeyType keyType, size_t size )
 764 {
 765     m_keyType = keyType;
 766     m_size = size;
 767     m_table = new wxHashTableBase_Node*[ m_size ];
 768
 769     for( size_t i = 0; i < m_size; ++i )
 770         m_table[i] = NULL;
 771 }
 772
 773 void wxHashTableBase::Clear()
 774 {
 775     for( size_t i = 0; i < m_size; ++i )
 776     {
 777         Node* end = m_table[i];
 778
 779         if( end == NULL )
 780             continue;
 781
 782         Node *curr, *next = end->GetNext();
 783
 784         do
 785         {
 786             curr = next;
 787             next = curr->GetNext();
 788
 789             DoDestroyNode( curr );
 790
 791             delete curr;
 792         }
 793         while( curr != end );
 794
 795         m_table[i] = NULL;
 796     }
 797
 798     m_count = 0;
 799 }
 800
 801 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
 802 {
 803     size_t bucket = ( m_keyType == wxKEY_INTEGER ?
 804                       node->m_key.integer        :
 805                       MakeKey( node->m_key.string ) ) % m_size;
 806
 807     if( node->GetNext() == node )
 808     {
 809         // single-node chain (common case)
 810         m_table[bucket] = NULL;
 811     }
 812     else
 813     {
 814         Node *start = m_table[bucket], *curr;
 815         Node* prev = start;
 816
 817         for( curr = prev->GetNext(); curr != node;
 818              prev = curr, curr = curr->GetNext() );
 819
 820         DoUnlinkNode( bucket, node, prev );
 821     }
 822
 823     DoDestroyNode( node );
 824 }
 825
 826 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
 827 {
 828     // if it is called from DoRemoveNode, node has already been
 829     // removed, from other places it does not matter
 830     node->m_hashPtr = NULL;
 831
 832     if( m_keyType == wxKEY_STRING )
 833         delete[] node->m_key.string;
 834     if( m_deleteContents )
 835         DoDeleteContents( node );
 836 }
 837
 838 void wxHashTableBase::Destroy()
 839 {
 840     Clear();
 841
 842     delete[] m_table;
 843
 844     m_table = NULL;
 845     m_size = 0;
 846 }
 847
 848 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
 849 {
 850     if( m_table[bucket] == NULL )
 851     {
 852         m_table[bucket] = node->m_next = node;
 853     }
 854     else
 855     {
 856         Node *prev = m_table[bucket];
 857         Node *next = prev->m_next;
 858
 859         prev->m_next = node;
 860         node->m_next = next;
 861         m_table[bucket] = node;
 862     }
 863
 864     ++m_count;
 865 }
 866
 867 void wxHashTableBase::DoPut( long key, long hash, void* data )
 868 {
 869     wxASSERT( m_keyType == wxKEY_INTEGER );
 870
 871     size_t bucket = size_t(hash) % m_size;
 872     Node* node = new wxHashTableBase_Node( key, data, this );
 873
 874     DoInsertNode( bucket, node );
 875 }
 876
 877 void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data )
 878 {
 879     wxASSERT( m_keyType == wxKEY_STRING );
 880
 881     size_t bucket = size_t(hash) % m_size;
 882     Node* node = new wxHashTableBase_Node( key, data, this );
 883
 884     DoInsertNode( bucket, node );
 885 }
 886
 887 void* wxHashTableBase::DoGet( long key, long hash ) const
 888 {
 889     wxASSERT( m_keyType == wxKEY_INTEGER );
 890
 891     size_t bucket = size_t(hash) % m_size;
 892
 893     if( m_table[bucket] == NULL )
 894         return NULL;
 895
 896     Node *first = m_table[bucket]->GetNext(),
 897          *curr = first;
 898
 899     do
 900     {
 901         if( curr->m_key.integer == key )
 902             return curr->m_value;
 903
 904         curr = curr->GetNext();
 905     }
 906     while( curr != first );
 907
 908     return NULL;
 909 }
 910
 911 void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const
 912 {
 913     wxASSERT( m_keyType == wxKEY_STRING );
 914
 915     size_t bucket = size_t(hash) % m_size;
 916
 917     if( m_table[bucket] == NULL )
 918         return NULL;
 919
 920     Node *first = m_table[bucket]->GetNext(),
 921          *curr = first;
 922
 923     do
 924     {
 925         if( wxStrcmp( curr->m_key.string, key ) == 0 )
 926             return curr->m_value;
 927
 928         curr = curr->GetNext();
 929     }
 930     while( curr != first );
 931
 932     return NULL;
 933 }
 934
 935 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
 936                                     wxHashTableBase_Node* prev )
 937 {
 938     if( node == m_table[bucket] )
 939         m_table[bucket] = prev;
 940
 941     if( prev == node && prev == node->GetNext() )
 942         m_table[bucket] = NULL;
 943     else
 944         prev->m_next = node->m_next;
 945
 946     DoDestroyNode( node );
 947     --m_count;
 948 }
 949
 950 void* wxHashTableBase::DoDelete( long key, long hash )
 951 {
 952     wxASSERT( m_keyType == wxKEY_INTEGER );
 953
 954     size_t bucket = size_t(hash) % m_size;
 955
 956     if( m_table[bucket] == NULL )
 957         return NULL;
 958
 959     Node *first = m_table[bucket]->GetNext(),
 960          *curr = first,
 961          *prev = m_table[bucket];
 962
 963     do
 964     {
 965         if( curr->m_key.integer == key )
 966         {
 967             void* retval = curr->m_value;
 968             curr->m_value = NULL;
 969
 970             DoUnlinkNode( bucket, curr, prev );
 971             delete curr;
 972
 973             return retval;
 974         }
 975
 976         prev = curr;
 977         curr = curr->GetNext();
 978     }
 979     while( curr != first );
 980
 981     return NULL;
 982 }
 983
 984 void* wxHashTableBase::DoDelete( const wxChar* key, long hash )
 985 {
 986     wxASSERT( m_keyType == wxKEY_STRING );
 987
 988     size_t bucket = size_t(hash) % m_size;
 989
 990     if( m_table[bucket] == NULL )
 991         return NULL;
 992
 993     Node *first = m_table[bucket]->GetNext(),
 994          *curr = first,
 995          *prev = m_table[bucket];
 996
 997     do
 998     {
 999         if( wxStrcmp( curr->m_key.string, key ) == 0 )
1000         {
1001             void* retval = curr->m_value;
1002             curr->m_value = NULL;
1003
1004             DoUnlinkNode( bucket, curr, prev );
1005             delete curr;
1006
1007             return retval;
1008         }
1009
1010         prev = curr;
1011         curr = curr->GetNext();
1012     }
1013     while( curr != first );
1014
1015     return NULL;
1016 }
1017
1018 long wxHashTableBase::MakeKey( const wxChar *str )
1019 {
1020     long int_key = 0;
1021
1022     while( *str )
1023         int_key += (wxUChar)*str++;
1024
1025     return int_key;
1026 }
1027
1028 //
1029
1030 wxHashTable::wxHashTable( const wxHashTable& table )
1031 {
1032     DoCopy( table );
1033 }
1034
1035 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
1036 {
1037     Destroy();
1038     DoCopy( table );
1039
1040     return *this;
1041 }
1042
1043 void wxHashTable::DoCopy( const wxHashTable& table )
1044 {
1045     Create( m_keyType, m_size );
1046
1047     wxASSERT( false );
1048 }
1049
1050 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
1051 {
1052     delete ((wxHashTable_Node*)node)->GetData();
1053 }
1054
1055 void wxHashTable::GetNextNode( size_t bucketStart )
1056 {
1057     for( size_t i = bucketStart; i < m_size; ++i )
1058     {
1059         if( m_table[i] != NULL )
1060         {
1061             m_curr = ((Node*)m_table[i])->GetNext();
1062             m_currBucket = i;
1063             return;
1064         }
1065     }
1066
1067     m_curr = NULL;
1068     m_currBucket = 0;
1069 }
1070
1071 wxHashTable::Node* wxHashTable::Next()
1072 {
1073     if( m_curr == NULL )
1074         GetNextNode( 0 );
1075     else
1076     {
1077         m_curr = m_curr->GetNext();
1078
1079         if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
1080             GetNextNode( m_currBucket + 1 );
1081     }
1082
1083     return m_curr;
1084 }
1085
1086 #endif // wxUSE_STL