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 and Markus Holzem
   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 // ----------------------------------------------------------------------------
 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, _T(""), _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 _T("");
 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 // ----------------------------------------------------------------------------
 338 // old not type safe wxHashTable
 339 // ----------------------------------------------------------------------------
 340
 341 wxHashTable::wxHashTable (int the_key_type, int size)
 342 {
 343   n = 0;
 344   hash_table = (wxList**) NULL;
 345   Create(the_key_type, size);
 346   m_count = 0;
 347   m_deleteContents = FALSE;
 348 /*
 349   n = size;
 350   current_position = -1;
 351   current_node = (wxNode *) NULL;
 352
 353   key_type = the_key_type;
 354   hash_table = new wxList *[size];
 355   int i;
 356   for (i = 0; i < size; i++)
 357     hash_table[i] = (wxList *) NULL;
 358 */
 359 }
 360
 361 wxHashTable::~wxHashTable ()
 362 {
 363   Destroy();
 364 }
 365
 366 void wxHashTable::Destroy()
 367 {
 368   if (!hash_table) return;
 369   int i;
 370   for (i = 0; i < n; i++)
 371     if (hash_table[i])
 372       delete hash_table[i];
 373   delete[] hash_table;
 374   hash_table = NULL;
 375 }
 376
 377 bool wxHashTable::Create(int the_key_type, int size)
 378 {
 379   Destroy();
 380
 381   n = size;
 382   current_position = -1;
 383   current_node = (wxNode *) NULL;
 384
 385   key_type = the_key_type;
 386   hash_table = new wxList *[size];
 387   int i;
 388   for (i = 0; i < size; i++)
 389     hash_table[i] = (wxList *) NULL;
 390   return TRUE;
 391 }
 392
 393
 394 void wxHashTable::DoCopy(const wxHashTable& table)
 395 {
 396   n = table.n;
 397   m_count = table.m_count;
 398   current_position = table.current_position;
 399   current_node = NULL; // doesn't matter - Next() will reconstruct it
 400   key_type = table.key_type;
 401
 402   hash_table = new wxList *[n];
 403   for (int i = 0; i < n; i++) {
 404     if (table.hash_table[i] == NULL)
 405       hash_table[i] = NULL;
 406     else {
 407       hash_table[i] = new wxList(key_type);
 408       *(hash_table[i]) = *(table.hash_table[i]);
 409     }
 410   }
 411 }
 412
 413 void wxHashTable::Put (long key, long value, wxObject * object)
 414 {
 415   // Should NEVER be
 416   long k = (long) key;
 417
 418   int position = (int) (k % n);
 419   if (position < 0) position = -position;
 420
 421   if (!hash_table[position])
 422   {
 423     hash_table[position] = new wxList (wxKEY_INTEGER);
 424     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 425   }
 426
 427   hash_table[position]->Append (value, object);
 428   m_count++;
 429 }
 430
 431 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 432 {
 433   // Should NEVER be
 434   long k = (long) key;
 435
 436   int position = (int) (k % n);
 437   if (position < 0) position = -position;
 438
 439   if (!hash_table[position])
 440   {
 441     hash_table[position] = new wxList (wxKEY_STRING);
 442     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 443   }
 444
 445   hash_table[position]->Append (value, object);
 446   m_count++;
 447 }
 448
 449 void wxHashTable::Put (long key, wxObject * object)
 450 {
 451   // Should NEVER be
 452   long k = (long) key;
 453
 454   int position = (int) (k % n);
 455   if (position < 0) position = -position;
 456
 457   if (!hash_table[position])
 458   {
 459     hash_table[position] = new wxList (wxKEY_INTEGER);
 460     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 461   }
 462
 463   hash_table[position]->Append (k, object);
 464   m_count++;
 465 }
 466
 467 void wxHashTable::Put (const wxChar *key, wxObject * object)
 468 {
 469   int position = (int) (MakeKey (key) % n);
 470   if (position < 0) position = -position;
 471
 472   if (!hash_table[position])
 473   {
 474     hash_table[position] = new wxList (wxKEY_STRING);
 475     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 476   }
 477
 478   hash_table[position]->Append (key, object);
 479   m_count++;
 480 }
 481
 482 wxObject *wxHashTable::Get (long key, long value) const
 483 {
 484   // Should NEVER be
 485   long k = (long) key;
 486
 487   int position = (int) (k % n);
 488   if (position < 0) position = -position;
 489
 490   if (!hash_table[position])
 491     return (wxObject *) NULL;
 492   else
 493     {
 494       wxNode *node = hash_table[position]->Find (value);
 495       if (node)
 496         return node->GetData ();
 497       else
 498         return (wxObject *) NULL;
 499     }
 500 }
 501
 502 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 503 {
 504   // Should NEVER be
 505   long k = (long) key;
 506
 507   int position = (int) (k % n);
 508   if (position < 0) position = -position;
 509
 510   if (!hash_table[position])
 511     return (wxObject *) NULL;
 512   else
 513     {
 514       wxNode *node = hash_table[position]->Find (value);
 515       if (node)
 516         return node->GetData ();
 517       else
 518         return (wxObject *) NULL;
 519     }
 520 }
 521
 522 wxObject *wxHashTable::Get (long key) const
 523 {
 524   // Should NEVER be
 525   long k = (long) key;
 526
 527   int position = (int) (k % n);
 528   if (position < 0) position = -position;
 529
 530   if (!hash_table[position])
 531     return (wxObject *) NULL;
 532   else
 533     {
 534       wxNode *node = hash_table[position]->Find (k);
 535       return node ? node->GetData () : (wxObject*)NULL;
 536     }
 537 }
 538
 539 wxObject *wxHashTable::Get (const wxChar *key) const
 540 {
 541   int position = (int) (MakeKey (key) % n);
 542   if (position < 0) position = -position;
 543
 544   if (!hash_table[position])
 545     return (wxObject *) NULL;
 546   else
 547     {
 548       wxNode *node = hash_table[position]->Find (key);
 549       return node ? node->GetData () : (wxObject*)NULL;
 550     }
 551 }
 552
 553 wxObject *wxHashTable::Delete (long key)
 554 {
 555   // Should NEVER be
 556   long k = (long) key;
 557
 558   int position = (int) (k % n);
 559   if (position < 0) position = -position;
 560
 561   if (!hash_table[position])
 562     return (wxObject *) NULL;
 563   else
 564     {
 565       wxNode *node = hash_table[position]->Find (k);
 566       if (node)
 567         {
 568           wxObject *data = node->GetData ();
 569           delete node;
 570           m_count--;
 571           return data;
 572         }
 573       else
 574         return (wxObject *) NULL;
 575     }
 576 }
 577
 578 wxObject *wxHashTable::Delete (const wxChar *key)
 579 {
 580   int position = (int) (MakeKey (key) % n);
 581   if (position < 0) position = -position;
 582
 583   if (!hash_table[position])
 584     return (wxObject *) NULL;
 585   else
 586     {
 587       wxNode *node = hash_table[position]->Find (key);
 588       if (node)
 589         {
 590           wxObject *data = node->GetData ();
 591           delete node;
 592           m_count--;
 593           return data;
 594         }
 595       else
 596         return (wxObject *) NULL;
 597     }
 598 }
 599
 600 wxObject *wxHashTable::Delete (long key, int value)
 601 {
 602   // Should NEVER be
 603   long k = (long) key;
 604
 605   int position = (int) (k % n);
 606   if (position < 0) position = -position;
 607
 608   if (!hash_table[position])
 609     return (wxObject *) NULL;
 610   else
 611     {
 612       wxNode *node = hash_table[position]->Find (value);
 613       if (node)
 614         {
 615           wxObject *data = node->GetData ();
 616           delete node;
 617           m_count--;
 618           return data;
 619         }
 620       else
 621         return (wxObject *) NULL;
 622     }
 623 }
 624
 625 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 626 {
 627   int position = (int) (key % n);
 628   if (position < 0) position = -position;
 629
 630   if (!hash_table[position])
 631     return (wxObject *) NULL;
 632   else
 633     {
 634       wxNode *node = hash_table[position]->Find (value);
 635       if (node)
 636         {
 637           wxObject *data = node->GetData ();
 638           delete node;
 639           m_count--;
 640           return data;
 641         }
 642       else
 643         return (wxObject *) NULL;
 644     }
 645 }
 646
 647 long wxHashTable::MakeKey (const wxChar *string) const
 648 {
 649   long int_key = 0;
 650
 651   while (*string)
 652     int_key += (wxUChar) *string++;
 653
 654   return int_key;
 655 }
 656
 657 void wxHashTable::BeginFind ()
 658 {
 659   current_position = -1;
 660   current_node = (wxNode *) NULL;
 661 }
 662
 663 wxNode *wxHashTable::Next ()
 664 {
 665   wxNode *found = (wxNode *) NULL;
 666   bool end = FALSE;
 667   while (!end && !found)
 668     {
 669       if (!current_node)
 670         {
 671           current_position++;
 672           if (current_position >= n)
 673             {
 674               current_position = -1;
 675               current_node = (wxNode *) NULL;
 676               end = TRUE;
 677             }
 678           else
 679             {
 680               if (hash_table[current_position])
 681                 {
 682                   current_node = hash_table[current_position]->GetFirst ();
 683                   found = current_node;
 684                 }
 685             }
 686         }
 687       else
 688         {
 689           current_node = current_node->GetNext ();
 690           found = current_node;
 691         }
 692     }
 693   return found;
 694 }
 695
 696 void wxHashTable::DeleteContents (bool flag)
 697 {
 698   int i;
 699   m_deleteContents = flag;
 700   for (i = 0; i < n; i++)
 701     {
 702       if (hash_table[i])
 703         hash_table[i]->DeleteContents (flag);
 704     }
 705 }
 706
 707 void wxHashTable::Clear ()
 708 {
 709     int i;
 710     if (hash_table)
 711     {
 712         for (i = 0; i < n; i++)
 713         {
 714             if (hash_table[i])
 715                 hash_table[i]->Clear ();
 716         }
 717     }
 718   m_count = 0;
 719 }
 720