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