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