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