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_OLD_HASH_TABLE
  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_OLD_HASH_TABLE
 728
 729 wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
 730                                             wxHashTableBase* table )
 731     : m_value( value ), m_hashPtr( table )
 732 {
 733     m_key.integer = key;
 734 }
 735
 736 wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value,
 737                                             wxHashTableBase* table )
 738     : m_value( value ), m_hashPtr( table )
 739 {
 740     m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key );
 741 }
 742
 743 wxHashTableBase_Node::~wxHashTableBase_Node()
 744 {
 745     if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
 746 }
 747
 748 //
 749
 750 wxHashTableBase::wxHashTableBase()
 751     : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
 752       m_deleteContents( false )
 753 {
 754 }
 755
 756 wxHashTableBase::~wxHashTableBase()
 757 {
 758     Destroy();
 759 }
 760
 761 void wxHashTableBase::Create( wxKeyType keyType, size_t size )
 762 {
 763     m_keyType = keyType;
 764     m_size = size;
 765     m_table = new wxHashTableBase_Node*[ m_size ];
 766
 767     for( size_t i = 0; i < m_size; ++i )
 768         m_table[i] = NULL;
 769 }
 770
 771 void wxHashTableBase::Clear()
 772 {
 773     for( size_t i = 0; i < m_size; ++i )
 774     {
 775         Node* end = m_table[i];
 776
 777         if( end == NULL )
 778             continue;
 779
 780         Node *curr, *next = end->GetNext();
 781
 782         do
 783         {
 784             curr = next;
 785             next = curr->GetNext();
 786
 787             DoDestroyNode( curr );
 788
 789             delete curr;
 790         }
 791         while( curr != end );
 792
 793         m_table[i] = NULL;
 794     }
 795
 796     m_count = 0;
 797 }
 798
 799 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
 800 {
 801     size_t bucket = ( m_keyType == wxKEY_INTEGER ?
 802                       node->m_key.integer        :
 803                       MakeKey( node->m_key.string ) ) % m_size;
 804
 805     if( node->GetNext() == node )
 806     {
 807         // single-node chain (common case)
 808         m_table[bucket] = NULL;
 809     }
 810     else
 811     {
 812         Node *start = m_table[bucket], *curr;
 813         Node* prev = start;
 814
 815         for( curr = prev->GetNext(); curr != node;
 816              prev = curr, curr = curr->GetNext() );
 817
 818         DoUnlinkNode( bucket, node, prev );
 819     }
 820
 821     DoDestroyNode( node );
 822 }
 823
 824 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
 825 {
 826     // if it is called from DoRemoveNode, node has already been
 827     // removed, from other places it does not matter
 828     node->m_hashPtr = NULL;
 829
 830     if( m_keyType == wxKEY_STRING )
 831         delete[] node->m_key.string;
 832     if( m_deleteContents )
 833         DoDeleteContents( node );
 834 }
 835
 836 void wxHashTableBase::Destroy()
 837 {
 838     Clear();
 839
 840     delete[] m_table;
 841
 842     m_table = NULL;
 843     m_size = 0;
 844 }
 845
 846 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
 847 {
 848     if( m_table[bucket] == NULL )
 849     {
 850         m_table[bucket] = node->m_next = node;
 851     }
 852     else
 853     {
 854         Node *prev = m_table[bucket];
 855         Node *next = prev->m_next;
 856
 857         prev->m_next = node;
 858         node->m_next = next;
 859         m_table[bucket] = node;
 860     }
 861
 862     ++m_count;
 863 }
 864
 865 void wxHashTableBase::DoPut( long key, long hash, void* data )
 866 {
 867     wxASSERT( m_keyType == wxKEY_INTEGER );
 868
 869     size_t bucket = size_t(hash) % m_size;
 870     Node* node = new wxHashTableBase_Node( key, data, this );
 871
 872     DoInsertNode( bucket, node );
 873 }
 874
 875 void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data )
 876 {
 877     wxASSERT( m_keyType == wxKEY_STRING );
 878
 879     size_t bucket = size_t(hash) % m_size;
 880     Node* node = new wxHashTableBase_Node( key, data, this );
 881
 882     DoInsertNode( bucket, node );
 883 }
 884
 885 void* wxHashTableBase::DoGet( long key, long hash ) const
 886 {
 887     wxASSERT( m_keyType == wxKEY_INTEGER );
 888
 889     size_t bucket = size_t(hash) % m_size;
 890
 891     if( m_table[bucket] == NULL )
 892         return NULL;
 893
 894     Node *first = m_table[bucket]->GetNext(),
 895          *curr = first;
 896
 897     do
 898     {
 899         if( curr->m_key.integer == key )
 900             return curr->m_value;
 901
 902         curr = curr->GetNext();
 903     }
 904     while( curr != first );
 905
 906     return NULL;
 907 }
 908
 909 void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const
 910 {
 911     wxASSERT( m_keyType == wxKEY_STRING );
 912
 913     size_t bucket = size_t(hash) % m_size;
 914
 915     if( m_table[bucket] == NULL )
 916         return NULL;
 917
 918     Node *first = m_table[bucket]->GetNext(),
 919          *curr = first;
 920
 921     do
 922     {
 923         if( wxStrcmp( curr->m_key.string, key ) == 0 )
 924             return curr->m_value;
 925
 926         curr = curr->GetNext();
 927     }
 928     while( curr != first );
 929
 930     return NULL;
 931 }
 932
 933 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
 934                                     wxHashTableBase_Node* prev )
 935 {
 936     if( node == m_table[bucket] )
 937         m_table[bucket] = prev;
 938
 939     if( prev == node && prev == node->GetNext() )
 940         m_table[bucket] = NULL;
 941     else
 942         prev->m_next = node->m_next;
 943
 944     DoDestroyNode( node );
 945     --m_count;
 946 }
 947
 948 void* wxHashTableBase::DoDelete( long key, long hash )
 949 {
 950     wxASSERT( m_keyType == wxKEY_INTEGER );
 951
 952     size_t bucket = size_t(hash) % m_size;
 953
 954     if( m_table[bucket] == NULL )
 955         return NULL;
 956
 957     Node *first = m_table[bucket]->GetNext(),
 958          *curr = first,
 959          *prev = m_table[bucket];
 960
 961     do
 962     {
 963         if( curr->m_key.integer == key )
 964         {
 965             void* retval = curr->m_value;
 966             curr->m_value = NULL;
 967
 968             DoUnlinkNode( bucket, curr, prev );
 969             delete curr;
 970
 971             return retval;
 972         }
 973
 974         prev = curr;
 975         curr = curr->GetNext();
 976     }
 977     while( curr != first );
 978
 979     return NULL;
 980 }
 981
 982 void* wxHashTableBase::DoDelete( const wxChar* key, long hash )
 983 {
 984     wxASSERT( m_keyType == wxKEY_STRING );
 985
 986     size_t bucket = size_t(hash) % m_size;
 987
 988     if( m_table[bucket] == NULL )
 989         return NULL;
 990
 991     Node *first = m_table[bucket]->GetNext(),
 992          *curr = first,
 993          *prev = m_table[bucket];
 994
 995     do
 996     {
 997         if( wxStrcmp( curr->m_key.string, key ) == 0 )
 998         {
 999             void* retval = curr->m_value;
1000             curr->m_value = NULL;
1001
1002             DoUnlinkNode( bucket, curr, prev );
1003             delete curr;
1004
1005             return retval;
1006         }
1007
1008         prev = curr;
1009         curr = curr->GetNext();
1010     }
1011     while( curr != first );
1012
1013     return NULL;
1014 }
1015
1016 long wxHashTableBase::MakeKey( const wxChar *str )
1017 {
1018     long int_key = 0;
1019
1020     while( *str )
1021         int_key += (wxUChar)*str++;
1022
1023     return int_key;
1024 }
1025
1026 //
1027
1028 wxHashTable::wxHashTable( const wxHashTable& table )
1029 {
1030     DoCopy( table );
1031 }
1032
1033 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
1034 {
1035     Destroy();
1036     DoCopy( table );
1037
1038     return *this;
1039 }
1040
1041 void wxHashTable::DoCopy( const wxHashTable& table )
1042 {
1043     Create( m_keyType, m_size );
1044
1045     wxASSERT( false );
1046 }
1047
1048 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
1049 {
1050     delete ((wxHashTable_Node*)node)->GetData();
1051 }
1052
1053 void wxHashTable::GetNextNode( size_t bucketStart )
1054 {
1055     for( size_t i = bucketStart; i < m_size; ++i )
1056     {
1057         if( m_table[i] != NULL )
1058         {
1059             m_curr = ((Node*)m_table[i])->GetNext();
1060             m_currBucket = i;
1061             return;
1062         }
1063     }
1064
1065     m_curr = NULL;
1066     m_currBucket = 0;
1067 }
1068
1069 wxHashTable::Node* wxHashTable::Next()
1070 {
1071     if( m_curr == NULL )
1072         GetNextNode( 0 );
1073     else
1074     {
1075         m_curr = m_curr->GetNext();
1076
1077         if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
1078             GetNextNode( m_currBucket + 1 );
1079     }
1080
1081     return m_curr;
1082 }
1083
1084 #endif // !wxUSE_OLD_HASH_TABLE