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_STL
  38
  39 #include <string.h>
  40 #include <stdarg.h>
  41
  42 // ----------------------------------------------------------------------------
  43 // wxWin macros
  44 // ----------------------------------------------------------------------------
  45
  46 IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
  47
  48 // ============================================================================
  49 // implementation
  50 // ============================================================================
  51
  52 // ----------------------------------------------------------------------------
  53 // wxHashTablleBase for working with "void *" data
  54 // ----------------------------------------------------------------------------
  55
  56 wxHashTableBase::wxHashTableBase()
  57 {
  58     m_deleteContents = FALSE;
  59     m_hashTable = (wxListBase **)NULL;
  60     m_hashSize = 0;
  61     m_count = 0;
  62     m_keyType = wxKEY_NONE;
  63 }
  64
  65 void wxHashTableBase::Create(wxKeyType keyType, size_t size)
  66 {
  67     Destroy();
  68
  69     m_hashSize = size;
  70     m_keyType = keyType;
  71     m_hashTable = new wxListBase *[size];
  72     for ( size_t n = 0; n < m_hashSize; n++ )
  73     {
  74         m_hashTable[n] = (wxListBase *) NULL;
  75     }
  76 }
  77
  78 void wxHashTableBase::Destroy()
  79 {
  80     if ( m_hashTable )
  81     {
  82         for ( size_t n = 0; n < m_hashSize; n++ )
  83         {
  84             delete m_hashTable[n];
  85         }
  86
  87         delete [] m_hashTable;
  88
  89         m_hashTable = (wxListBase **)NULL;
  90
  91         m_count = 0;
  92     }
  93 }
  94
  95 void wxHashTableBase::DeleteContents(bool flag)
  96 {
  97     m_deleteContents = flag;
  98     for ( size_t n = 0; n < m_hashSize; n++ )
  99     {
 100         if ( m_hashTable[n] )
 101         {
 102             m_hashTable[n]->DeleteContents(flag);
 103         }
 104     }
 105 }
 106
 107 wxNodeBase *wxHashTableBase::GetNode(long key, long value) const
 108 {
 109     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 110
 111     wxNodeBase *node;
 112     if ( m_hashTable[slot] )
 113     {
 114         node = m_hashTable[slot]->Find(wxListKey(value));
 115     }
 116     else
 117     {
 118         node = (wxNodeBase *)NULL;
 119     }
 120
 121     return node;
 122 }
 123
 124 #if WXWIN_COMPATIBILITY_2_4
 125
 126 // ----------------------------------------------------------------------------
 127 // wxHashTableLong
 128 // ----------------------------------------------------------------------------
 129
 130 wxHashTableLong::~wxHashTableLong()
 131 {
 132     Destroy();
 133 }
 134
 135 void wxHashTableLong::Init(size_t size)
 136 {
 137     m_hashSize = size;
 138     m_values = new wxArrayLong *[size];
 139     m_keys = new wxArrayLong *[size];
 140
 141     for ( size_t n = 0; n < m_hashSize; n++ )
 142     {
 143         m_values[n] =
 144         m_keys[n] = (wxArrayLong *)NULL;
 145     }
 146
 147     m_count = 0;
 148 }
 149
 150 void wxHashTableLong::Create(size_t size)
 151 {
 152     Init(size);
 153 }
 154
 155 void wxHashTableLong::Destroy()
 156 {
 157     for ( size_t n = 0; n < m_hashSize; n++ )
 158     {
 159         delete m_values[n];
 160         delete m_keys[n];
 161     }
 162
 163     delete [] m_values;
 164     delete [] m_keys;
 165     m_hashSize = 0;
 166     m_count = 0;
 167 }
 168
 169 void wxHashTableLong::Put(long key, long value)
 170 {
 171     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 172
 173     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 174
 175     if ( !m_keys[slot] )
 176     {
 177         m_keys[slot] = new wxArrayLong;
 178         m_values[slot] = new wxArrayLong;
 179     }
 180
 181     m_keys[slot]->Add(key);
 182     m_values[slot]->Add(value);
 183
 184     m_count++;
 185 }
 186
 187 long wxHashTableLong::Get(long key) const
 188 {
 189     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 190
 191     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 192
 193     wxArrayLong *keys = m_keys[slot];
 194     if ( keys )
 195     {
 196         size_t count = keys->GetCount();
 197         for ( size_t n = 0; n < count; n++ )
 198         {
 199             if ( keys->Item(n) == key )
 200             {
 201                 return m_values[slot]->Item(n);
 202             }
 203         }
 204     }
 205
 206     return wxNOT_FOUND;
 207 }
 208
 209 long wxHashTableLong::Delete(long key)
 210 {
 211     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 212
 213     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 214
 215     wxArrayLong *keys = m_keys[slot];
 216     if ( keys )
 217     {
 218         size_t count = keys->GetCount();
 219         for ( size_t n = 0; n < count; n++ )
 220         {
 221             if ( keys->Item(n) == key )
 222             {
 223                 long val = m_values[slot]->Item(n);
 224
 225                 keys->RemoveAt(n);
 226                 m_values[slot]->RemoveAt(n);
 227
 228                 m_count--;
 229
 230                 return val;
 231             }
 232         }
 233     }
 234
 235     return wxNOT_FOUND;
 236 }
 237
 238 // ----------------------------------------------------------------------------
 239 // wxStringHashTable: more efficient than storing strings in a list
 240 // ----------------------------------------------------------------------------
 241
 242 wxStringHashTable::wxStringHashTable(size_t sizeTable)
 243 {
 244     m_keys = new wxArrayLong *[sizeTable];
 245     m_values = new wxArrayString *[sizeTable];
 246
 247     m_hashSize = sizeTable;
 248     for ( size_t n = 0; n < m_hashSize; n++ )
 249     {
 250         m_values[n] = (wxArrayString *)NULL;
 251         m_keys[n] = (wxArrayLong *)NULL;
 252     }
 253 }
 254
 255 wxStringHashTable::~wxStringHashTable()
 256 {
 257     Destroy();
 258 }
 259
 260 void wxStringHashTable::Destroy()
 261 {
 262     for ( size_t n = 0; n < m_hashSize; n++ )
 263     {
 264         delete m_values[n];
 265         delete m_keys[n];
 266     }
 267
 268     delete [] m_values;
 269     delete [] m_keys;
 270     m_hashSize = 0;
 271 }
 272
 273 void wxStringHashTable::Put(long key, const wxString& value)
 274 {
 275     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 276
 277     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 278
 279     if ( !m_keys[slot] )
 280     {
 281         m_keys[slot] = new wxArrayLong;
 282         m_values[slot] = new wxArrayString;
 283     }
 284
 285     m_keys[slot]->Add(key);
 286     m_values[slot]->Add(value);
 287 }
 288
 289 wxString wxStringHashTable::Get(long key, bool *wasFound) const
 290 {
 291     wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );
 292
 293     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 294
 295     wxArrayLong *keys = m_keys[slot];
 296     if ( keys )
 297     {
 298         size_t count = keys->GetCount();
 299         for ( size_t n = 0; n < count; n++ )
 300         {
 301             if ( keys->Item(n) == key )
 302             {
 303                 if ( wasFound )
 304                     *wasFound = TRUE;
 305
 306                 return m_values[slot]->Item(n);
 307             }
 308         }
 309     }
 310
 311     if ( wasFound )
 312         *wasFound = FALSE;
 313
 314     return _T("");
 315 }
 316
 317 bool wxStringHashTable::Delete(long key) const
 318 {
 319     wxCHECK_MSG( m_hashSize, FALSE, _T("must call Create() first") );
 320
 321     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 322
 323     wxArrayLong *keys = m_keys[slot];
 324     if ( keys )
 325     {
 326         size_t count = keys->GetCount();
 327         for ( size_t n = 0; n < count; n++ )
 328         {
 329             if ( keys->Item(n) == key )
 330             {
 331                 keys->RemoveAt(n);
 332                 m_values[slot]->RemoveAt(n);
 333                 return TRUE;
 334             }
 335         }
 336     }
 337
 338     return FALSE;
 339 }
 340
 341 #endif // WXWIN_COMPATIBILITY_2_4
 342
 343 // ----------------------------------------------------------------------------
 344 // old not type safe wxHashTable
 345 // ----------------------------------------------------------------------------
 346
 347 wxHashTable::wxHashTable (int the_key_type, int size)
 348 {
 349   n = 0;
 350   hash_table = (wxList**) NULL;
 351   Create(the_key_type, size);
 352   m_count = 0;
 353   m_deleteContents = FALSE;
 354 /*
 355   n = size;
 356   current_position = -1;
 357   current_node = (wxNode *) NULL;
 358
 359   key_type = the_key_type;
 360   hash_table = new wxList *[size];
 361   int i;
 362   for (i = 0; i < size; i++)
 363     hash_table[i] = (wxList *) NULL;
 364 */
 365 }
 366
 367 wxHashTable::~wxHashTable ()
 368 {
 369   Destroy();
 370 }
 371
 372 void wxHashTable::Destroy()
 373 {
 374   if (!hash_table) return;
 375   int i;
 376   for (i = 0; i < n; i++)
 377     if (hash_table[i])
 378       delete hash_table[i];
 379   delete[] hash_table;
 380   hash_table = NULL;
 381 }
 382
 383 bool wxHashTable::Create(int the_key_type, int size)
 384 {
 385   Destroy();
 386
 387   n = size;
 388   current_position = -1;
 389   current_node = (wxNode *) NULL;
 390
 391   key_type = the_key_type;
 392   hash_table = new wxList *[size];
 393   int i;
 394   for (i = 0; i < size; i++)
 395     hash_table[i] = (wxList *) NULL;
 396   return TRUE;
 397 }
 398
 399
 400 void wxHashTable::DoCopy(const wxHashTable& table)
 401 {
 402   n = table.n;
 403   m_count = table.m_count;
 404   current_position = table.current_position;
 405   current_node = NULL; // doesn't matter - Next() will reconstruct it
 406   key_type = table.key_type;
 407
 408   hash_table = new wxList *[n];
 409   for (int i = 0; i < n; i++) {
 410     if (table.hash_table[i] == NULL)
 411       hash_table[i] = NULL;
 412     else {
 413       hash_table[i] = new wxList(key_type);
 414       *(hash_table[i]) = *(table.hash_table[i]);
 415     }
 416   }
 417 }
 418
 419 void wxHashTable::Put (long key, long value, wxObject * object)
 420 {
 421   // Should NEVER be
 422   long k = (long) key;
 423
 424   int position = (int) (k % n);
 425   if (position < 0) position = -position;
 426
 427   if (!hash_table[position])
 428   {
 429     hash_table[position] = new wxList (wxKEY_INTEGER);
 430     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 431   }
 432
 433   hash_table[position]->Append (value, object);
 434   m_count++;
 435 }
 436
 437 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 438 {
 439   // Should NEVER be
 440   long k = (long) key;
 441
 442   int position = (int) (k % n);
 443   if (position < 0) position = -position;
 444
 445   if (!hash_table[position])
 446   {
 447     hash_table[position] = new wxList (wxKEY_STRING);
 448     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 449   }
 450
 451   hash_table[position]->Append (value, object);
 452   m_count++;
 453 }
 454
 455 void wxHashTable::Put (long key, wxObject * object)
 456 {
 457   // Should NEVER be
 458   long k = (long) key;
 459
 460   int position = (int) (k % n);
 461   if (position < 0) position = -position;
 462
 463   if (!hash_table[position])
 464   {
 465     hash_table[position] = new wxList (wxKEY_INTEGER);
 466     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 467   }
 468
 469   hash_table[position]->Append (k, object);
 470   m_count++;
 471 }
 472
 473 void wxHashTable::Put (const wxChar *key, wxObject * object)
 474 {
 475   int position = (int) (MakeKey (key) % n);
 476   if (position < 0) position = -position;
 477
 478   if (!hash_table[position])
 479   {
 480     hash_table[position] = new wxList (wxKEY_STRING);
 481     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 482   }
 483
 484   hash_table[position]->Append (key, object);
 485   m_count++;
 486 }
 487
 488 wxObject *wxHashTable::Get (long key, long value) const
 489 {
 490   // Should NEVER be
 491   long k = (long) key;
 492
 493   int position = (int) (k % n);
 494   if (position < 0) position = -position;
 495
 496   if (!hash_table[position])
 497     return (wxObject *) NULL;
 498   else
 499     {
 500       wxNode *node = hash_table[position]->Find (value);
 501       if (node)
 502         return node->GetData ();
 503       else
 504         return (wxObject *) NULL;
 505     }
 506 }
 507
 508 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 509 {
 510   // Should NEVER be
 511   long k = (long) key;
 512
 513   int position = (int) (k % n);
 514   if (position < 0) position = -position;
 515
 516   if (!hash_table[position])
 517     return (wxObject *) NULL;
 518   else
 519     {
 520       wxNode *node = hash_table[position]->Find (value);
 521       if (node)
 522         return node->GetData ();
 523       else
 524         return (wxObject *) NULL;
 525     }
 526 }
 527
 528 wxObject *wxHashTable::Get (long key) const
 529 {
 530   // Should NEVER be
 531   long k = (long) key;
 532
 533   int position = (int) (k % n);
 534   if (position < 0) position = -position;
 535
 536   if (!hash_table[position])
 537     return (wxObject *) NULL;
 538   else
 539     {
 540       wxNode *node = hash_table[position]->Find (k);
 541       return node ? node->GetData () : (wxObject*)NULL;
 542     }
 543 }
 544
 545 wxObject *wxHashTable::Get (const wxChar *key) const
 546 {
 547   int position = (int) (MakeKey (key) % n);
 548   if (position < 0) position = -position;
 549
 550   if (!hash_table[position])
 551     return (wxObject *) NULL;
 552   else
 553     {
 554       wxNode *node = hash_table[position]->Find (key);
 555       return node ? node->GetData () : (wxObject*)NULL;
 556     }
 557 }
 558
 559 wxObject *wxHashTable::Delete (long key)
 560 {
 561   // Should NEVER be
 562   long k = (long) key;
 563
 564   int position = (int) (k % n);
 565   if (position < 0) position = -position;
 566
 567   if (!hash_table[position])
 568     return (wxObject *) NULL;
 569   else
 570     {
 571       wxNode *node = hash_table[position]->Find (k);
 572       if (node)
 573         {
 574           wxObject *data = node->GetData ();
 575           delete node;
 576           m_count--;
 577           return data;
 578         }
 579       else
 580         return (wxObject *) NULL;
 581     }
 582 }
 583
 584 wxObject *wxHashTable::Delete (const wxChar *key)
 585 {
 586   int position = (int) (MakeKey (key) % n);
 587   if (position < 0) position = -position;
 588
 589   if (!hash_table[position])
 590     return (wxObject *) NULL;
 591   else
 592     {
 593       wxNode *node = hash_table[position]->Find (key);
 594       if (node)
 595         {
 596           wxObject *data = node->GetData ();
 597           delete node;
 598           m_count--;
 599           return data;
 600         }
 601       else
 602         return (wxObject *) NULL;
 603     }
 604 }
 605
 606 wxObject *wxHashTable::Delete (long key, int value)
 607 {
 608   // Should NEVER be
 609   long k = (long) key;
 610
 611   int position = (int) (k % n);
 612   if (position < 0) position = -position;
 613
 614   if (!hash_table[position])
 615     return (wxObject *) NULL;
 616   else
 617     {
 618       wxNode *node = hash_table[position]->Find (value);
 619       if (node)
 620         {
 621           wxObject *data = node->GetData ();
 622           delete node;
 623           m_count--;
 624           return data;
 625         }
 626       else
 627         return (wxObject *) NULL;
 628     }
 629 }
 630
 631 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 632 {
 633   int position = (int) (key % n);
 634   if (position < 0) position = -position;
 635
 636   if (!hash_table[position])
 637     return (wxObject *) NULL;
 638   else
 639     {
 640       wxNode *node = hash_table[position]->Find (value);
 641       if (node)
 642         {
 643           wxObject *data = node->GetData ();
 644           delete node;
 645           m_count--;
 646           return data;
 647         }
 648       else
 649         return (wxObject *) NULL;
 650     }
 651 }
 652
 653 long wxHashTable::MakeKey (const wxChar *string) const
 654 {
 655   long int_key = 0;
 656
 657   while (*string)
 658     int_key += (wxUChar) *string++;
 659
 660   return int_key;
 661 }
 662
 663 void wxHashTable::BeginFind ()
 664 {
 665   current_position = -1;
 666   current_node = (wxNode *) NULL;
 667 }
 668
 669 wxNode *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 #endif // !wxUSE_STL