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::Destroy()
 147 {
 148     for ( size_t n = 0; n < m_hashSize; n++ )
 149     {
 150         delete m_values[n];
 151         delete m_keys[n];
 152     }
 153
 154     delete [] m_values;
 155     delete [] m_keys;
 156     m_hashSize = 0;
 157     m_count = 0;
 158 }
 159
 160 void wxHashTableLong::Put(long key, long value)
 161 {
 162     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 163
 164     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 165
 166     if ( !m_keys[slot] )
 167     {
 168         m_keys[slot] = new wxArrayLong;
 169         m_values[slot] = new wxArrayLong;
 170     }
 171
 172     m_keys[slot]->Add(key);
 173     m_values[slot]->Add(value);
 174
 175     m_count++;
 176 }
 177
 178 long wxHashTableLong::Get(long key) const
 179 {
 180     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 181
 182     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 183
 184     wxArrayLong *keys = m_keys[slot];
 185     if ( keys )
 186     {
 187         size_t count = keys->GetCount();
 188         for ( size_t n = 0; n < count; n++ )
 189         {
 190             if ( keys->Item(n) == key )
 191             {
 192                 return m_values[slot]->Item(n);
 193             }
 194         }
 195     }
 196
 197     return wxNOT_FOUND;
 198 }
 199
 200 long wxHashTableLong::Delete(long key)
 201 {
 202     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 203
 204     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 205
 206     wxArrayLong *keys = m_keys[slot];
 207     if ( keys )
 208     {
 209         size_t count = keys->GetCount();
 210         for ( size_t n = 0; n < count; n++ )
 211         {
 212             if ( keys->Item(n) == key )
 213             {
 214                 long val = m_values[slot]->Item(n);
 215
 216                 keys->RemoveAt(n);
 217                 m_values[slot]->RemoveAt(n);
 218
 219                 m_count--;
 220
 221                 return val;
 222             }
 223         }
 224     }
 225
 226     return wxNOT_FOUND;
 227 }
 228
 229 // ----------------------------------------------------------------------------
 230 // wxStringHashTable: more efficient than storing strings in a list
 231 // ----------------------------------------------------------------------------
 232
 233 wxStringHashTable::wxStringHashTable(size_t sizeTable)
 234 {
 235     m_keys = new wxArrayLong *[sizeTable];
 236     m_values = new wxArrayString *[sizeTable];
 237
 238     m_hashSize = sizeTable;
 239     for ( size_t n = 0; n < m_hashSize; n++ )
 240     {
 241         m_values[n] = (wxArrayString *)NULL;
 242         m_keys[n] = (wxArrayLong *)NULL;
 243     }
 244 }
 245
 246 wxStringHashTable::~wxStringHashTable()
 247 {
 248     Destroy();
 249 }
 250
 251 void wxStringHashTable::Destroy()
 252 {
 253     for ( size_t n = 0; n < m_hashSize; n++ )
 254     {
 255         delete m_values[n];
 256         delete m_keys[n];
 257     }
 258
 259     delete [] m_values;
 260     delete [] m_keys;
 261     m_hashSize = 0;
 262 }
 263
 264 void wxStringHashTable::Put(long key, const wxString& value)
 265 {
 266     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 267
 268     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 269
 270     if ( !m_keys[slot] )
 271     {
 272         m_keys[slot] = new wxArrayLong;
 273         m_values[slot] = new wxArrayString;
 274     }
 275
 276     m_keys[slot]->Add(key);
 277     m_values[slot]->Add(value);
 278 }
 279
 280 wxString wxStringHashTable::Get(long key, bool *wasFound) const
 281 {
 282     wxCHECK_MSG( m_hashSize, _T(""), _T("must call Create() first") );
 283
 284     size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
 285
 286     wxArrayLong *keys = m_keys[slot];
 287     if ( keys )
 288     {
 289         size_t count = keys->GetCount();
 290         for ( size_t n = 0; n < count; n++ )
 291         {
 292             if ( keys->Item(n) == key )
 293             {
 294                 if ( wasFound )
 295                     *wasFound = TRUE;
 296
 297                 return m_values[slot]->Item(n);
 298             }
 299         }
 300     }
 301
 302     if ( wasFound )
 303         *wasFound = FALSE;
 304
 305     return _T("");
 306 }
 307
 308 // ----------------------------------------------------------------------------
 309 // old not type safe wxHashTable
 310 // ----------------------------------------------------------------------------
 311
 312 wxHashTable::wxHashTable (int the_key_type, int size)
 313 {
 314   n = 0;
 315   hash_table = (wxList**) NULL;
 316   Create(the_key_type, size);
 317   m_count = 0;
 318   m_deleteContents = FALSE;
 319 /*
 320   n = size;
 321   current_position = -1;
 322   current_node = (wxNode *) NULL;
 323
 324   key_type = the_key_type;
 325   hash_table = new wxList *[size];
 326   int i;
 327   for (i = 0; i < size; i++)
 328     hash_table[i] = (wxList *) NULL;
 329 */
 330 }
 331
 332 wxHashTable::~wxHashTable ()
 333 {
 334   Destroy();
 335 }
 336
 337 void wxHashTable::Destroy()
 338 {
 339   if (!hash_table) return;
 340   int i;
 341   for (i = 0; i < n; i++)
 342     if (hash_table[i])
 343       delete hash_table[i];
 344   delete[] hash_table;
 345   hash_table = NULL;
 346 }
 347
 348 bool wxHashTable::Create(int the_key_type, int size)
 349 {
 350   Destroy();
 351
 352   n = size;
 353   current_position = -1;
 354   current_node = (wxNode *) NULL;
 355
 356   key_type = the_key_type;
 357   hash_table = new wxList *[size];
 358   int i;
 359   for (i = 0; i < size; i++)
 360     hash_table[i] = (wxList *) NULL;
 361   return TRUE;
 362 }
 363
 364
 365 void wxHashTable::DoCopy(const wxHashTable& table)
 366 {
 367   n = table.n;
 368   current_position = table.current_position;
 369   current_node = NULL; // doesn't matter - Next() will reconstruct it
 370   key_type = table.key_type;
 371
 372   hash_table = new wxList *[n];
 373   for (int i = 0; i < n; i++) {
 374     if (table.hash_table[i] == NULL)
 375       hash_table[i] = NULL;
 376     else {
 377       hash_table[i] = new wxList(key_type);
 378       *(hash_table[i]) = *(table.hash_table[i]);
 379     }
 380   }
 381 }
 382
 383 void wxHashTable::Put (long key, long value, wxObject * object)
 384 {
 385   // Should NEVER be
 386   long k = (long) key;
 387
 388   int position = (int) (k % n);
 389   if (position < 0) position = -position;
 390
 391   if (!hash_table[position])
 392   {
 393     hash_table[position] = new wxList (wxKEY_INTEGER);
 394     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 395   }
 396
 397   hash_table[position]->Append (value, object);
 398   m_count++;
 399 }
 400
 401 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 402 {
 403   // Should NEVER be
 404   long k = (long) key;
 405
 406   int position = (int) (k % n);
 407   if (position < 0) position = -position;
 408
 409   if (!hash_table[position])
 410   {
 411     hash_table[position] = new wxList (wxKEY_INTEGER);
 412     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 413   }
 414
 415   hash_table[position]->Append (value, object);
 416   m_count++;
 417 }
 418
 419 void wxHashTable::Put (long key, 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 (k, object);
 434   m_count++;
 435 }
 436
 437 void wxHashTable::Put (const wxChar *key, wxObject * object)
 438 {
 439   int position = (int) (MakeKey (key) % n);
 440   if (position < 0) position = -position;
 441
 442   if (!hash_table[position])
 443   {
 444     hash_table[position] = new wxList (wxKEY_STRING);
 445     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 446   }
 447
 448   hash_table[position]->Append (key, object);
 449   m_count++;
 450 }
 451
 452 wxObject *wxHashTable::Get (long key, long value) const
 453 {
 454   // Should NEVER be
 455   long k = (long) key;
 456
 457   int position = (int) (k % n);
 458   if (position < 0) position = -position;
 459
 460   if (!hash_table[position])
 461     return (wxObject *) NULL;
 462   else
 463     {
 464       wxNode *node = hash_table[position]->Find (value);
 465       if (node)
 466         return node->Data ();
 467       else
 468         return (wxObject *) NULL;
 469     }
 470 }
 471
 472 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 473 {
 474   // Should NEVER be
 475   long k = (long) key;
 476
 477   int position = (int) (k % n);
 478   if (position < 0) position = -position;
 479
 480   if (!hash_table[position])
 481     return (wxObject *) NULL;
 482   else
 483     {
 484       wxNode *node = hash_table[position]->Find (value);
 485       if (node)
 486         return node->Data ();
 487       else
 488         return (wxObject *) NULL;
 489     }
 490 }
 491
 492 wxObject *wxHashTable::Get (long key) const
 493 {
 494   // Should NEVER be
 495   long k = (long) key;
 496
 497   int position = (int) (k % n);
 498   if (position < 0) position = -position;
 499
 500   if (!hash_table[position])
 501     return (wxObject *) NULL;
 502   else
 503     {
 504       wxNode *node = hash_table[position]->Find (k);
 505       return node ? node->Data () : (wxObject*)NULL;
 506     }
 507 }
 508
 509 wxObject *wxHashTable::Get (const wxChar *key) const
 510 {
 511   int position = (int) (MakeKey (key) % 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 (key);
 519       return node ? node->Data () : (wxObject*)NULL;
 520     }
 521 }
 522
 523 wxObject *wxHashTable::Delete (long key)
 524 {
 525   // Should NEVER be
 526   long k = (long) key;
 527
 528   int position = (int) (k % n);
 529   if (position < 0) position = -position;
 530
 531   if (!hash_table[position])
 532     return (wxObject *) NULL;
 533   else
 534     {
 535       wxNode *node = hash_table[position]->Find (k);
 536       if (node)
 537         {
 538           wxObject *data = node->Data ();
 539           delete node;
 540           m_count--;
 541           return data;
 542         }
 543       else
 544         return (wxObject *) NULL;
 545     }
 546 }
 547
 548 wxObject *wxHashTable::Delete (const wxChar *key)
 549 {
 550   int position = (int) (MakeKey (key) % n);
 551   if (position < 0) position = -position;
 552
 553   if (!hash_table[position])
 554     return (wxObject *) NULL;
 555   else
 556     {
 557       wxNode *node = hash_table[position]->Find (key);
 558       if (node)
 559         {
 560           wxObject *data = node->Data ();
 561           delete node;
 562           m_count--;
 563           return data;
 564         }
 565       else
 566         return (wxObject *) NULL;
 567     }
 568 }
 569
 570 wxObject *wxHashTable::Delete (long key, int value)
 571 {
 572   // Should NEVER be
 573   long k = (long) key;
 574
 575   int position = (int) (k % n);
 576   if (position < 0) position = -position;
 577
 578   if (!hash_table[position])
 579     return (wxObject *) NULL;
 580   else
 581     {
 582       wxNode *node = hash_table[position]->Find (value);
 583       if (node)
 584         {
 585           wxObject *data = node->Data ();
 586           delete node;
 587           m_count--;
 588           return data;
 589         }
 590       else
 591         return (wxObject *) NULL;
 592     }
 593 }
 594
 595 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 596 {
 597   int position = (int) (key % n);
 598   if (position < 0) position = -position;
 599
 600   if (!hash_table[position])
 601     return (wxObject *) NULL;
 602   else
 603     {
 604       wxNode *node = hash_table[position]->Find (value);
 605       if (node)
 606         {
 607           wxObject *data = node->Data ();
 608           delete node;
 609           m_count--;
 610           return data;
 611         }
 612       else
 613         return (wxObject *) NULL;
 614     }
 615 }
 616
 617 long wxHashTable::MakeKey (const wxChar *string) const
 618 {
 619   long int_key = 0;
 620
 621   while (*string)
 622     int_key += (wxUChar) *string++;
 623
 624   return int_key;
 625 }
 626
 627 void wxHashTable::BeginFind ()
 628 {
 629   current_position = -1;
 630   current_node = (wxNode *) NULL;
 631 }
 632
 633 wxNode *wxHashTable::Next ()
 634 {
 635   wxNode *found = (wxNode *) NULL;
 636   bool end = FALSE;
 637   while (!end && !found)
 638     {
 639       if (!current_node)
 640         {
 641           current_position++;
 642           if (current_position >= n)
 643             {
 644               current_position = -1;
 645               current_node = (wxNode *) NULL;
 646               end = TRUE;
 647             }
 648           else
 649             {
 650               if (hash_table[current_position])
 651                 {
 652                   current_node = hash_table[current_position]->First ();
 653                   found = current_node;
 654                 }
 655             }
 656         }
 657       else
 658         {
 659           current_node = current_node->Next ();
 660           found = current_node;
 661         }
 662     }
 663   return found;
 664 }
 665
 666 void wxHashTable::DeleteContents (bool flag)
 667 {
 668   int i;
 669   m_deleteContents = flag;
 670   for (i = 0; i < n; i++)
 671     {
 672       if (hash_table[i])
 673         hash_table[i]->DeleteContents (flag);
 674     }
 675 }
 676
 677 void wxHashTable::Clear ()
 678 {
 679   int i;
 680   for (i = 0; i < n; i++)
 681     {
 682       if (hash_table[i])
 683         hash_table[i]->Clear ();
 684     }
 685   m_count = 0;
 686 }
 687