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(key % 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 void wxHashTableLong::Init(size_t size)
 127 {
 128     m_hashSize = size;
 129     m_values = new wxArrayLong *[size];
 130     m_keys = new wxArrayLong *[size];
 131
 132     for ( size_t n = 0; n < m_hashSize; n++ )
 133     {
 134         m_values[n] =
 135         m_keys[n] = (wxArrayLong *)NULL;
 136     }
 137
 138     m_count = 0;
 139 }
 140
 141 void wxHashTableLong::Destroy()
 142 {
 143     for ( size_t n = 0; n < m_hashSize; n++ )
 144     {
 145         delete m_values[n];
 146         delete m_keys[n];
 147     }
 148
 149     delete [] m_values;
 150     delete [] m_keys;
 151     m_hashSize = 0;
 152     m_count = 0;
 153 }
 154
 155 void wxHashTableLong::Put(long key, long value)
 156 {
 157     wxCHECK_RET( m_hashSize, _T("must call Create() first") );
 158
 159     size_t slot = (size_t)abs(key % m_hashSize);
 160
 161     if ( !m_keys[slot] )
 162     {
 163         m_keys[slot] = new wxArrayLong;
 164         m_values[slot] = new wxArrayLong;
 165     }
 166
 167     m_keys[slot]->Add(key);
 168     m_values[slot]->Add(value);
 169
 170     m_count++;
 171 }
 172
 173 long wxHashTableLong::Get(long key) const
 174 {
 175     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 176
 177     size_t slot = (size_t)abs(key % m_hashSize);
 178
 179     wxArrayLong *keys = m_keys[slot];
 180     if ( keys )
 181     {
 182         size_t count = keys->GetCount();
 183         for ( size_t n = 0; n < count; n++ )
 184         {
 185             if ( keys->Item(n) == key )
 186             {
 187                 return m_values[slot]->Item(n);
 188             }
 189         }
 190     }
 191
 192     return wxNOT_FOUND;
 193 }
 194
 195 long wxHashTableLong::Delete(long key)
 196 {
 197     wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
 198
 199     size_t slot = (size_t)abs(key % m_hashSize);
 200
 201     wxArrayLong *keys = m_keys[slot];
 202     if ( keys )
 203     {
 204         size_t count = keys->GetCount();
 205         for ( size_t n = 0; n < count; n++ )
 206         {
 207             if ( keys->Item(n) == key )
 208             {
 209                 long val = m_values[slot]->Item(n);
 210
 211                 keys->RemoveAt(n);
 212                 m_values[slot]->RemoveAt(n);
 213
 214                 m_count--;
 215
 216                 return val;
 217             }
 218         }
 219     }
 220
 221     return wxNOT_FOUND;
 222 }
 223
 224 // ----------------------------------------------------------------------------
 225 // old not type safe wxHashTable
 226 // ----------------------------------------------------------------------------
 227
 228 wxHashTable::wxHashTable (int the_key_type, int size)
 229 {
 230   n = 0;
 231   hash_table = (wxList**) NULL;
 232   Create(the_key_type, size);
 233   m_count = 0;
 234   m_deleteContents = FALSE;
 235 /*
 236   n = size;
 237   current_position = -1;
 238   current_node = (wxNode *) NULL;
 239
 240   key_type = the_key_type;
 241   hash_table = new wxList *[size];
 242   int i;
 243   for (i = 0; i < size; i++)
 244     hash_table[i] = (wxList *) NULL;
 245 */
 246 }
 247
 248 wxHashTable::~wxHashTable ()
 249 {
 250   Destroy();
 251 }
 252
 253 void wxHashTable::Destroy()
 254 {
 255   if (!hash_table) return;
 256   int i;
 257   for (i = 0; i < n; i++)
 258     if (hash_table[i])
 259       delete hash_table[i];
 260   delete[] hash_table;
 261   hash_table = NULL;
 262 }
 263
 264 bool wxHashTable::Create(int the_key_type, int size)
 265 {
 266   Destroy();
 267
 268   n = size;
 269   current_position = -1;
 270   current_node = (wxNode *) NULL;
 271
 272   key_type = the_key_type;
 273   hash_table = new wxList *[size];
 274   int i;
 275   for (i = 0; i < size; i++)
 276     hash_table[i] = (wxList *) NULL;
 277   return TRUE;
 278 }
 279
 280
 281 void wxHashTable::DoCopy(const wxHashTable& table)
 282 {
 283   n = table.n;
 284   current_position = table.current_position;
 285   current_node = NULL; // doesn't matter - Next() will reconstruct it
 286   key_type = table.key_type;
 287
 288   hash_table = new wxList *[n];
 289   for (int i = 0; i < n; i++) {
 290     if (table.hash_table[i] == NULL)
 291       hash_table[i] = NULL;
 292     else {
 293       hash_table[i] = new wxList(key_type);
 294       *(hash_table[i]) = *(table.hash_table[i]);
 295     }
 296   }
 297 }
 298
 299 void wxHashTable::Put (long key, long value, wxObject * object)
 300 {
 301   // Should NEVER be
 302   long k = (long) key;
 303
 304   int position = (int) (k % n);
 305   if (position < 0) position = -position;
 306
 307   if (!hash_table[position])
 308   {
 309     hash_table[position] = new wxList (wxKEY_INTEGER);
 310     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 311   }
 312
 313   hash_table[position]->Append (value, object);
 314   m_count++;
 315 }
 316
 317 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 318 {
 319   // Should NEVER be
 320   long k = (long) key;
 321
 322   int position = (int) (k % n);
 323   if (position < 0) position = -position;
 324
 325   if (!hash_table[position])
 326   {
 327     hash_table[position] = new wxList (wxKEY_INTEGER);
 328     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 329   }
 330
 331   hash_table[position]->Append (value, object);
 332   m_count++;
 333 }
 334
 335 void wxHashTable::Put (long key, wxObject * object)
 336 {
 337   // Should NEVER be
 338   long k = (long) key;
 339
 340   int position = (int) (k % n);
 341   if (position < 0) position = -position;
 342
 343   if (!hash_table[position])
 344   {
 345     hash_table[position] = new wxList (wxKEY_INTEGER);
 346     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 347   }
 348
 349   hash_table[position]->Append (k, object);
 350   m_count++;
 351 }
 352
 353 void wxHashTable::Put (const wxChar *key, wxObject * object)
 354 {
 355   int position = (int) (MakeKey (key) % n);
 356   if (position < 0) position = -position;
 357
 358   if (!hash_table[position])
 359   {
 360     hash_table[position] = new wxList (wxKEY_STRING);
 361     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 362   }
 363
 364   hash_table[position]->Append (key, object);
 365   m_count++;
 366 }
 367
 368 wxObject *wxHashTable::Get (long key, long value) const
 369 {
 370   // Should NEVER be
 371   long k = (long) key;
 372
 373   int position = (int) (k % n);
 374   if (position < 0) position = -position;
 375
 376   if (!hash_table[position])
 377     return (wxObject *) NULL;
 378   else
 379     {
 380       wxNode *node = hash_table[position]->Find (value);
 381       if (node)
 382         return node->Data ();
 383       else
 384         return (wxObject *) NULL;
 385     }
 386 }
 387
 388 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 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     return (wxObject *) NULL;
 398   else
 399     {
 400       wxNode *node = hash_table[position]->Find (value);
 401       if (node)
 402         return node->Data ();
 403       else
 404         return (wxObject *) NULL;
 405     }
 406 }
 407
 408 wxObject *wxHashTable::Get (long key) const
 409 {
 410   // Should NEVER be
 411   long k = (long) key;
 412
 413   int position = (int) (k % n);
 414   if (position < 0) position = -position;
 415
 416   if (!hash_table[position])
 417     return (wxObject *) NULL;
 418   else
 419     {
 420       wxNode *node = hash_table[position]->Find (k);
 421       return node ? node->Data () : (wxObject*)NULL;
 422     }
 423 }
 424
 425 wxObject *wxHashTable::Get (const wxChar *key) const
 426 {
 427   int position = (int) (MakeKey (key) % n);
 428   if (position < 0) position = -position;
 429
 430   if (!hash_table[position])
 431     return (wxObject *) NULL;
 432   else
 433     {
 434       wxNode *node = hash_table[position]->Find (key);
 435       return node ? node->Data () : (wxObject*)NULL;
 436     }
 437 }
 438
 439 wxObject *wxHashTable::Delete (long key)
 440 {
 441   // Should NEVER be
 442   long k = (long) key;
 443
 444   int position = (int) (k % n);
 445   if (position < 0) position = -position;
 446
 447   if (!hash_table[position])
 448     return (wxObject *) NULL;
 449   else
 450     {
 451       wxNode *node = hash_table[position]->Find (k);
 452       if (node)
 453         {
 454           wxObject *data = node->Data ();
 455           delete node;
 456           m_count--;
 457           return data;
 458         }
 459       else
 460         return (wxObject *) NULL;
 461     }
 462 }
 463
 464 wxObject *wxHashTable::Delete (const wxChar *key)
 465 {
 466   int position = (int) (MakeKey (key) % n);
 467   if (position < 0) position = -position;
 468
 469   if (!hash_table[position])
 470     return (wxObject *) NULL;
 471   else
 472     {
 473       wxNode *node = hash_table[position]->Find (key);
 474       if (node)
 475         {
 476           wxObject *data = node->Data ();
 477           delete node;
 478           m_count--;
 479           return data;
 480         }
 481       else
 482         return (wxObject *) NULL;
 483     }
 484 }
 485
 486 wxObject *wxHashTable::Delete (long key, int value)
 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         {
 501           wxObject *data = node->Data ();
 502           delete node;
 503           m_count--;
 504           return data;
 505         }
 506       else
 507         return (wxObject *) NULL;
 508     }
 509 }
 510
 511 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 512 {
 513   int position = (int) (key % n);
 514   if (position < 0) position = -position;
 515
 516   if (!hash_table[position])
 517     return (wxObject *) NULL;
 518   else
 519     {
 520       wxNode *node = hash_table[position]->Find (value);
 521       if (node)
 522         {
 523           wxObject *data = node->Data ();
 524           delete node;
 525           m_count--;
 526           return data;
 527         }
 528       else
 529         return (wxObject *) NULL;
 530     }
 531 }
 532
 533 long wxHashTable::MakeKey (const wxChar *string) const
 534 {
 535   long int_key = 0;
 536
 537   while (*string)
 538     int_key += (wxUChar) *string++;
 539
 540   return int_key;
 541 }
 542
 543 void wxHashTable::BeginFind ()
 544 {
 545   current_position = -1;
 546   current_node = (wxNode *) NULL;
 547 }
 548
 549 wxNode *wxHashTable::Next ()
 550 {
 551   wxNode *found = (wxNode *) NULL;
 552   bool end = FALSE;
 553   while (!end && !found)
 554     {
 555       if (!current_node)
 556         {
 557           current_position++;
 558           if (current_position >= n)
 559             {
 560               current_position = -1;
 561               current_node = (wxNode *) NULL;
 562               end = TRUE;
 563             }
 564           else
 565             {
 566               if (hash_table[current_position])
 567                 {
 568                   current_node = hash_table[current_position]->First ();
 569                   found = current_node;
 570                 }
 571             }
 572         }
 573       else
 574         {
 575           current_node = current_node->Next ();
 576           found = current_node;
 577         }
 578     }
 579   return found;
 580 }
 581
 582 void wxHashTable::DeleteContents (bool flag)
 583 {
 584   int i;
 585   m_deleteContents = flag;
 586   for (i = 0; i < n; i++)
 587     {
 588       if (hash_table[i])
 589         hash_table[i]->DeleteContents (flag);
 590     }
 591 }
 592
 593 void wxHashTable::Clear ()
 594 {
 595   int i;
 596   for (i = 0; i < n; i++)
 597     {
 598       if (hash_table[i])
 599         hash_table[i]->Clear ();
 600     }
 601   m_count = 0;
 602 }
 603