src/common/hash.cpp

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