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