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