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 // ----------------------------------------------------------------------------
 120 // old not type safe wxHashTable
 121 // ----------------------------------------------------------------------------
 122
 123 wxHashTable::wxHashTable (int the_key_type, int size)
 124 {
 125   n = 0;
 126   hash_table = (wxList**) NULL;
 127   Create(the_key_type, size);
 128   m_count = 0;
 129   m_deleteContents = false;
 130 /*
 131   n = size;
 132   current_position = -1;
 133   current_node = (wxNode *) NULL;
 134
 135   key_type = the_key_type;
 136   hash_table = new wxList *[size];
 137   int i;
 138   for (i = 0; i < size; i++)
 139     hash_table[i] = (wxList *) NULL;
 140 */
 141 }
 142
 143 wxHashTable::~wxHashTable ()
 144 {
 145   Destroy();
 146 }
 147
 148 void wxHashTable::Destroy()
 149 {
 150   if (!hash_table) return;
 151   int i;
 152   for (i = 0; i < n; i++)
 153     if (hash_table[i])
 154       delete hash_table[i];
 155   delete[] hash_table;
 156   hash_table = NULL;
 157 }
 158
 159 bool wxHashTable::Create(int the_key_type, int size)
 160 {
 161   Destroy();
 162
 163   n = size;
 164   current_position = -1;
 165   current_node = (wxNode *) NULL;
 166
 167   key_type = the_key_type;
 168   hash_table = new wxList *[size];
 169   int i;
 170   for (i = 0; i < size; i++)
 171     hash_table[i] = (wxList *) NULL;
 172   return true;
 173 }
 174
 175
 176 void wxHashTable::DoCopy(const wxHashTable& table)
 177 {
 178   n = table.n;
 179   m_count = table.m_count;
 180   current_position = table.current_position;
 181   current_node = NULL; // doesn't matter - Next() will reconstruct it
 182   key_type = table.key_type;
 183
 184   hash_table = new wxList *[n];
 185   for (int i = 0; i < n; i++) {
 186     if (table.hash_table[i] == NULL)
 187       hash_table[i] = NULL;
 188     else {
 189       hash_table[i] = new wxList(key_type);
 190       *(hash_table[i]) = *(table.hash_table[i]);
 191     }
 192   }
 193 }
 194
 195 void wxHashTable::Put (long key, long value, wxObject * object)
 196 {
 197   // Should NEVER be
 198   long k = (long) key;
 199
 200   int position = (int) (k % n);
 201   if (position < 0) position = -position;
 202
 203   if (!hash_table[position])
 204   {
 205     hash_table[position] = new wxList (wxKEY_INTEGER);
 206     if (m_deleteContents) hash_table[position]->DeleteContents(true);
 207   }
 208
 209   hash_table[position]->Append (value, object);
 210   m_count++;
 211 }
 212
 213 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 214 {
 215   // Should NEVER be
 216   long k = (long) key;
 217
 218   int position = (int) (k % n);
 219   if (position < 0) position = -position;
 220
 221   if (!hash_table[position])
 222   {
 223     hash_table[position] = new wxList (wxKEY_STRING);
 224     if (m_deleteContents) hash_table[position]->DeleteContents(true);
 225   }
 226
 227   hash_table[position]->Append (value, object);
 228   m_count++;
 229 }
 230
 231 void wxHashTable::Put (long key, wxObject * object)
 232 {
 233   // Should NEVER be
 234   long k = (long) key;
 235
 236   int position = (int) (k % n);
 237   if (position < 0) position = -position;
 238
 239   if (!hash_table[position])
 240   {
 241     hash_table[position] = new wxList (wxKEY_INTEGER);
 242     if (m_deleteContents) hash_table[position]->DeleteContents(true);
 243   }
 244
 245   hash_table[position]->Append (k, object);
 246   m_count++;
 247 }
 248
 249 void wxHashTable::Put (const wxChar *key, wxObject * object)
 250 {
 251   int position = (int) (MakeKey (key) % n);
 252   if (position < 0) position = -position;
 253
 254   if (!hash_table[position])
 255   {
 256     hash_table[position] = new wxList (wxKEY_STRING);
 257     if (m_deleteContents) hash_table[position]->DeleteContents(true);
 258   }
 259
 260   hash_table[position]->Append (key, object);
 261   m_count++;
 262 }
 263
 264 wxObject *wxHashTable::Get (long key, long value) const
 265 {
 266   // Should NEVER be
 267   long k = (long) key;
 268
 269   int position = (int) (k % n);
 270   if (position < 0) position = -position;
 271
 272   if (!hash_table[position])
 273     return (wxObject *) NULL;
 274   else
 275     {
 276       wxNode *node = hash_table[position]->Find (value);
 277       if (node)
 278         return node->GetData ();
 279       else
 280         return (wxObject *) NULL;
 281     }
 282 }
 283
 284 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 285 {
 286   // Should NEVER be
 287   long k = (long) key;
 288
 289   int position = (int) (k % n);
 290   if (position < 0) position = -position;
 291
 292   if (!hash_table[position])
 293     return (wxObject *) NULL;
 294   else
 295     {
 296       wxNode *node = hash_table[position]->Find (value);
 297       if (node)
 298         return node->GetData ();
 299       else
 300         return (wxObject *) NULL;
 301     }
 302 }
 303
 304 wxObject *wxHashTable::Get (long key) const
 305 {
 306   // Should NEVER be
 307   long k = (long) key;
 308
 309   int position = (int) (k % n);
 310   if (position < 0) position = -position;
 311
 312   if (!hash_table[position])
 313     return (wxObject *) NULL;
 314   else
 315     {
 316       wxNode *node = hash_table[position]->Find (k);
 317       return node ? node->GetData () : (wxObject*)NULL;
 318     }
 319 }
 320
 321 wxObject *wxHashTable::Get (const wxChar *key) const
 322 {
 323   int position = (int) (MakeKey (key) % n);
 324   if (position < 0) position = -position;
 325
 326   if (!hash_table[position])
 327     return (wxObject *) NULL;
 328   else
 329     {
 330       wxNode *node = hash_table[position]->Find (key);
 331       return node ? node->GetData () : (wxObject*)NULL;
 332     }
 333 }
 334
 335 wxObject *wxHashTable::Delete (long key)
 336 {
 337   // Should NEVER be
 338   long k = (long) key;
 339
 340   int position = (int) (k % n);
 341   if (position < 0) position = -position;
 342
 343   if (!hash_table[position])
 344     return (wxObject *) NULL;
 345   else
 346     {
 347       wxNode *node = hash_table[position]->Find (k);
 348       if (node)
 349         {
 350           wxObject *data = node->GetData ();
 351           delete node;
 352           m_count--;
 353           return data;
 354         }
 355       else
 356         return (wxObject *) NULL;
 357     }
 358 }
 359
 360 wxObject *wxHashTable::Delete (const wxChar *key)
 361 {
 362   int position = (int) (MakeKey (key) % n);
 363   if (position < 0) position = -position;
 364
 365   if (!hash_table[position])
 366     return (wxObject *) NULL;
 367   else
 368     {
 369       wxNode *node = hash_table[position]->Find (key);
 370       if (node)
 371         {
 372           wxObject *data = node->GetData ();
 373           delete node;
 374           m_count--;
 375           return data;
 376         }
 377       else
 378         return (wxObject *) NULL;
 379     }
 380 }
 381
 382 wxObject *wxHashTable::Delete (long key, int value)
 383 {
 384   // Should NEVER be
 385   long k = (long) key;
 386
 387   int position = (int) (k % n);
 388   if (position < 0) position = -position;
 389
 390   if (!hash_table[position])
 391     return (wxObject *) NULL;
 392   else
 393     {
 394       wxNode *node = hash_table[position]->Find (value);
 395       if (node)
 396         {
 397           wxObject *data = node->GetData ();
 398           delete node;
 399           m_count--;
 400           return data;
 401         }
 402       else
 403         return (wxObject *) NULL;
 404     }
 405 }
 406
 407 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 408 {
 409   int position = (int) (key % n);
 410   if (position < 0) position = -position;
 411
 412   if (!hash_table[position])
 413     return (wxObject *) NULL;
 414   else
 415     {
 416       wxNode *node = hash_table[position]->Find (value);
 417       if (node)
 418         {
 419           wxObject *data = node->GetData ();
 420           delete node;
 421           m_count--;
 422           return data;
 423         }
 424       else
 425         return (wxObject *) NULL;
 426     }
 427 }
 428
 429 long wxHashTable::MakeKey (const wxChar *string) const
 430 {
 431   long int_key = 0;
 432
 433   while (*string)
 434     int_key += (wxUChar) *string++;
 435
 436   return int_key;
 437 }
 438
 439 void wxHashTable::BeginFind ()
 440 {
 441   current_position = -1;
 442   current_node = (wxNode *) NULL;
 443 }
 444
 445 wxHashTable::Node* wxHashTable::Next ()
 446 {
 447   wxNode *found = (wxNode *) NULL;
 448   bool end = false;
 449   while (!end && !found)
 450     {
 451       if (!current_node)
 452         {
 453           current_position++;
 454           if (current_position >= n)
 455             {
 456               current_position = -1;
 457               current_node = (wxNode *) NULL;
 458               end = true;
 459             }
 460           else
 461             {
 462               if (hash_table[current_position])
 463                 {
 464                   current_node = hash_table[current_position]->GetFirst ();
 465                   found = current_node;
 466                 }
 467             }
 468         }
 469       else
 470         {
 471           current_node = current_node->GetNext ();
 472           found = current_node;
 473         }
 474     }
 475   return found;
 476 }
 477
 478 void wxHashTable::DeleteContents (bool flag)
 479 {
 480   int i;
 481   m_deleteContents = flag;
 482   for (i = 0; i < n; i++)
 483     {
 484       if (hash_table[i])
 485         hash_table[i]->DeleteContents (flag);
 486     }
 487 }
 488
 489 void wxHashTable::Clear ()
 490 {
 491     int i;
 492     if (hash_table)
 493     {
 494         for (i = 0; i < n; i++)
 495         {
 496             if (hash_table[i])
 497                 hash_table[i]->Clear ();
 498         }
 499     }
 500   m_count = 0;
 501 }
 502
 503 #else // if !wxUSE_OLD_HASH_TABLE
 504
 505 wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
 506                                             wxHashTableBase* table )
 507     : m_value( value ), m_hashPtr( table )
 508 {
 509     m_key.integer = key;
 510 }
 511
 512 wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value,
 513                                             wxHashTableBase* table )
 514     : m_value( value ), m_hashPtr( table )
 515 {
 516     m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key );
 517 }
 518
 519 wxHashTableBase_Node::~wxHashTableBase_Node()
 520 {
 521     if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
 522 }
 523
 524 //
 525
 526 wxHashTableBase::wxHashTableBase()
 527     : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
 528       m_deleteContents( false )
 529 {
 530 }
 531
 532 void wxHashTableBase::Create( wxKeyType keyType, size_t size )
 533 {
 534     m_keyType = keyType;
 535     m_size = size;
 536     m_table = new wxHashTableBase_Node*[ m_size ];
 537
 538     for( size_t i = 0; i < m_size; ++i )
 539         m_table[i] = NULL;
 540 }
 541
 542 void wxHashTableBase::Clear()
 543 {
 544     for( size_t i = 0; i < m_size; ++i )
 545     {
 546         Node* end = m_table[i];
 547
 548         if( end == NULL )
 549             continue;
 550
 551         Node *curr, *next = end->GetNext();
 552
 553         do
 554         {
 555             curr = next;
 556             next = curr->GetNext();
 557
 558             DoDestroyNode( curr );
 559
 560             delete curr;
 561         }
 562         while( curr != end );
 563
 564         m_table[i] = NULL;
 565     }
 566
 567     m_count = 0;
 568 }
 569
 570 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
 571 {
 572     size_t bucket = ( m_keyType == wxKEY_INTEGER ?
 573                       node->m_key.integer        :
 574                       MakeKey( node->m_key.string ) ) % m_size;
 575
 576     if( node->GetNext() == node )
 577     {
 578         // single-node chain (common case)
 579         m_table[bucket] = NULL;
 580     }
 581     else
 582     {
 583         Node *start = m_table[bucket], *curr;
 584         Node* prev = start;
 585
 586         for( curr = prev->GetNext(); curr != node;
 587              prev = curr, curr = curr->GetNext() ) ;
 588
 589         DoUnlinkNode( bucket, node, prev );
 590     }
 591
 592     DoDestroyNode( node );
 593 }
 594
 595 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
 596 {
 597     // if it is called from DoRemoveNode, node has already been
 598     // removed, from other places it does not matter
 599     node->m_hashPtr = NULL;
 600
 601     if( m_keyType == wxKEY_STRING )
 602         delete[] node->m_key.string;
 603     if( m_deleteContents )
 604         DoDeleteContents( node );
 605 }
 606
 607 void wxHashTableBase::Destroy()
 608 {
 609     Clear();
 610
 611     delete[] m_table;
 612
 613     m_table = NULL;
 614     m_size = 0;
 615 }
 616
 617 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
 618 {
 619     if( m_table[bucket] == NULL )
 620     {
 621         m_table[bucket] = node->m_next = node;
 622     }
 623     else
 624     {
 625         Node *prev = m_table[bucket];
 626         Node *next = prev->m_next;
 627
 628         prev->m_next = node;
 629         node->m_next = next;
 630         m_table[bucket] = node;
 631     }
 632
 633     ++m_count;
 634 }
 635
 636 void wxHashTableBase::DoPut( long key, long hash, void* data )
 637 {
 638     wxASSERT( m_keyType == wxKEY_INTEGER );
 639
 640     size_t bucket = size_t(hash) % m_size;
 641     Node* node = new wxHashTableBase_Node( key, data, this );
 642
 643     DoInsertNode( bucket, node );
 644 }
 645
 646 void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data )
 647 {
 648     wxASSERT( m_keyType == wxKEY_STRING );
 649
 650     size_t bucket = size_t(hash) % m_size;
 651     Node* node = new wxHashTableBase_Node( key, data, this );
 652
 653     DoInsertNode( bucket, node );
 654 }
 655
 656 void* wxHashTableBase::DoGet( long key, long hash ) const
 657 {
 658     wxASSERT( m_keyType == wxKEY_INTEGER );
 659
 660     size_t bucket = size_t(hash) % m_size;
 661
 662     if( m_table[bucket] == NULL )
 663         return NULL;
 664
 665     Node *first = m_table[bucket]->GetNext(),
 666          *curr = first;
 667
 668     do
 669     {
 670         if( curr->m_key.integer == key )
 671             return curr->m_value;
 672
 673         curr = curr->GetNext();
 674     }
 675     while( curr != first );
 676
 677     return NULL;
 678 }
 679
 680 void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const
 681 {
 682     wxASSERT( m_keyType == wxKEY_STRING );
 683
 684     size_t bucket = size_t(hash) % m_size;
 685
 686     if( m_table[bucket] == NULL )
 687         return NULL;
 688
 689     Node *first = m_table[bucket]->GetNext(),
 690          *curr = first;
 691
 692     do
 693     {
 694         if( wxStrcmp( curr->m_key.string, key ) == 0 )
 695             return curr->m_value;
 696
 697         curr = curr->GetNext();
 698     }
 699     while( curr != first );
 700
 701     return NULL;
 702 }
 703
 704 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
 705                                     wxHashTableBase_Node* prev )
 706 {
 707     if( node == m_table[bucket] )
 708         m_table[bucket] = prev;
 709
 710     if( prev == node && prev == node->GetNext() )
 711         m_table[bucket] = NULL;
 712     else
 713         prev->m_next = node->m_next;
 714
 715     DoDestroyNode( node );
 716     --m_count;
 717 }
 718
 719 void* wxHashTableBase::DoDelete( long key, long hash )
 720 {
 721     wxASSERT( m_keyType == wxKEY_INTEGER );
 722
 723     size_t bucket = size_t(hash) % m_size;
 724
 725     if( m_table[bucket] == NULL )
 726         return NULL;
 727
 728     Node *first = m_table[bucket]->GetNext(),
 729          *curr = first,
 730          *prev = m_table[bucket];
 731
 732     do
 733     {
 734         if( curr->m_key.integer == key )
 735         {
 736             void* retval = curr->m_value;
 737             curr->m_value = NULL;
 738
 739             DoUnlinkNode( bucket, curr, prev );
 740             delete curr;
 741
 742             return retval;
 743         }
 744
 745         prev = curr;
 746         curr = curr->GetNext();
 747     }
 748     while( curr != first );
 749
 750     return NULL;
 751 }
 752
 753 void* wxHashTableBase::DoDelete( const wxChar* key, long hash )
 754 {
 755     wxASSERT( m_keyType == wxKEY_STRING );
 756
 757     size_t bucket = size_t(hash) % m_size;
 758
 759     if( m_table[bucket] == NULL )
 760         return NULL;
 761
 762     Node *first = m_table[bucket]->GetNext(),
 763          *curr = first,
 764          *prev = m_table[bucket];
 765
 766     do
 767     {
 768         if( wxStrcmp( curr->m_key.string, key ) == 0 )
 769         {
 770             void* retval = curr->m_value;
 771             curr->m_value = NULL;
 772
 773             DoUnlinkNode( bucket, curr, prev );
 774             delete curr;
 775
 776             return retval;
 777         }
 778
 779         prev = curr;
 780         curr = curr->GetNext();
 781     }
 782     while( curr != first );
 783
 784     return NULL;
 785 }
 786
 787 long wxHashTableBase::MakeKey( const wxChar *str )
 788 {
 789     long int_key = 0;
 790
 791     while( *str )
 792         int_key += (wxUChar)*str++;
 793
 794     return int_key;
 795 }
 796
 797 // ----------------------------------------------------------------------------
 798 // wxHashTable
 799 // ----------------------------------------------------------------------------
 800
 801 wxHashTable::wxHashTable( const wxHashTable& table )
 802            : wxHashTableBase()
 803 {
 804     DoCopy( table );
 805 }
 806
 807 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
 808 {
 809     Destroy();
 810     DoCopy( table );
 811
 812     return *this;
 813 }
 814
 815 void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
 816 {
 817     Create( m_keyType, m_size );
 818
 819     wxFAIL;
 820 }
 821
 822 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
 823 {
 824     delete ((wxHashTable_Node*)node)->GetData();
 825 }
 826
 827 void wxHashTable::GetNextNode( size_t bucketStart )
 828 {
 829     for( size_t i = bucketStart; i < m_size; ++i )
 830     {
 831         if( m_table[i] != NULL )
 832         {
 833             m_curr = ((Node*)m_table[i])->GetNext();
 834             m_currBucket = i;
 835             return;
 836         }
 837     }
 838
 839     m_curr = NULL;
 840     m_currBucket = 0;
 841 }
 842
 843 wxHashTable::Node* wxHashTable::Next()
 844 {
 845     if( m_curr == NULL )
 846         GetNextNode( 0 );
 847     else
 848     {
 849         m_curr = m_curr->GetNext();
 850
 851         if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
 852             GetNextNode( m_currBucket + 1 );
 853     }
 854
 855     return m_curr;
 856 }
 857
 858 #endif // !wxUSE_OLD_HASH_TABLE