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 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(key % 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(key % 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(key % 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 // old not type safe wxHashTable
 231 // ----------------------------------------------------------------------------
 232
 233 wxHashTable::wxHashTable (int the_key_type, int size)
 234 {
 235   n = 0;
 236   hash_table = (wxList**) NULL;
 237   Create(the_key_type, size);
 238   m_count = 0;
 239   m_deleteContents = FALSE;
 240 /*
 241   n = size;
 242   current_position = -1;
 243   current_node = (wxNode *) NULL;
 244
 245   key_type = the_key_type;
 246   hash_table = new wxList *[size];
 247   int i;
 248   for (i = 0; i < size; i++)
 249     hash_table[i] = (wxList *) NULL;
 250 */
 251 }
 252
 253 wxHashTable::~wxHashTable ()
 254 {
 255   Destroy();
 256 }
 257
 258 void wxHashTable::Destroy()
 259 {
 260   if (!hash_table) return;
 261   int i;
 262   for (i = 0; i < n; i++)
 263     if (hash_table[i])
 264       delete hash_table[i];
 265   delete[] hash_table;
 266   hash_table = NULL;
 267 }
 268
 269 bool wxHashTable::Create(int the_key_type, int size)
 270 {
 271   Destroy();
 272
 273   n = size;
 274   current_position = -1;
 275   current_node = (wxNode *) NULL;
 276
 277   key_type = the_key_type;
 278   hash_table = new wxList *[size];
 279   int i;
 280   for (i = 0; i < size; i++)
 281     hash_table[i] = (wxList *) NULL;
 282   return TRUE;
 283 }
 284
 285
 286 void wxHashTable::DoCopy(const wxHashTable& table)
 287 {
 288   n = table.n;
 289   current_position = table.current_position;
 290   current_node = NULL; // doesn't matter - Next() will reconstruct it
 291   key_type = table.key_type;
 292
 293   hash_table = new wxList *[n];
 294   for (int i = 0; i < n; i++) {
 295     if (table.hash_table[i] == NULL)
 296       hash_table[i] = NULL;
 297     else {
 298       hash_table[i] = new wxList(key_type);
 299       *(hash_table[i]) = *(table.hash_table[i]);
 300     }
 301   }
 302 }
 303
 304 void wxHashTable::Put (long key, long value, wxObject * object)
 305 {
 306   // Should NEVER be
 307   long k = (long) key;
 308
 309   int position = (int) (k % n);
 310   if (position < 0) position = -position;
 311
 312   if (!hash_table[position])
 313   {
 314     hash_table[position] = new wxList (wxKEY_INTEGER);
 315     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 316   }
 317
 318   hash_table[position]->Append (value, object);
 319   m_count++;
 320 }
 321
 322 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 323 {
 324   // Should NEVER be
 325   long k = (long) key;
 326
 327   int position = (int) (k % n);
 328   if (position < 0) position = -position;
 329
 330   if (!hash_table[position])
 331   {
 332     hash_table[position] = new wxList (wxKEY_INTEGER);
 333     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 334   }
 335
 336   hash_table[position]->Append (value, object);
 337   m_count++;
 338 }
 339
 340 void wxHashTable::Put (long key, wxObject * object)
 341 {
 342   // Should NEVER be
 343   long k = (long) key;
 344
 345   int position = (int) (k % n);
 346   if (position < 0) position = -position;
 347
 348   if (!hash_table[position])
 349   {
 350     hash_table[position] = new wxList (wxKEY_INTEGER);
 351     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 352   }
 353
 354   hash_table[position]->Append (k, object);
 355   m_count++;
 356 }
 357
 358 void wxHashTable::Put (const wxChar *key, wxObject * object)
 359 {
 360   int position = (int) (MakeKey (key) % n);
 361   if (position < 0) position = -position;
 362
 363   if (!hash_table[position])
 364   {
 365     hash_table[position] = new wxList (wxKEY_STRING);
 366     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 367   }
 368
 369   hash_table[position]->Append (key, object);
 370   m_count++;
 371 }
 372
 373 wxObject *wxHashTable::Get (long key, long value) const
 374 {
 375   // Should NEVER be
 376   long k = (long) key;
 377
 378   int position = (int) (k % n);
 379   if (position < 0) position = -position;
 380
 381   if (!hash_table[position])
 382     return (wxObject *) NULL;
 383   else
 384     {
 385       wxNode *node = hash_table[position]->Find (value);
 386       if (node)
 387         return node->Data ();
 388       else
 389         return (wxObject *) NULL;
 390     }
 391 }
 392
 393 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 394 {
 395   // Should NEVER be
 396   long k = (long) key;
 397
 398   int position = (int) (k % n);
 399   if (position < 0) position = -position;
 400
 401   if (!hash_table[position])
 402     return (wxObject *) NULL;
 403   else
 404     {
 405       wxNode *node = hash_table[position]->Find (value);
 406       if (node)
 407         return node->Data ();
 408       else
 409         return (wxObject *) NULL;
 410     }
 411 }
 412
 413 wxObject *wxHashTable::Get (long key) const
 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     return (wxObject *) NULL;
 423   else
 424     {
 425       wxNode *node = hash_table[position]->Find (k);
 426       return node ? node->Data () : (wxObject*)NULL;
 427     }
 428 }
 429
 430 wxObject *wxHashTable::Get (const wxChar *key) const
 431 {
 432   int position = (int) (MakeKey (key) % n);
 433   if (position < 0) position = -position;
 434
 435   if (!hash_table[position])
 436     return (wxObject *) NULL;
 437   else
 438     {
 439       wxNode *node = hash_table[position]->Find (key);
 440       return node ? node->Data () : (wxObject*)NULL;
 441     }
 442 }
 443
 444 wxObject *wxHashTable::Delete (long key)
 445 {
 446   // Should NEVER be
 447   long k = (long) key;
 448
 449   int position = (int) (k % n);
 450   if (position < 0) position = -position;
 451
 452   if (!hash_table[position])
 453     return (wxObject *) NULL;
 454   else
 455     {
 456       wxNode *node = hash_table[position]->Find (k);
 457       if (node)
 458         {
 459           wxObject *data = node->Data ();
 460           delete node;
 461           m_count--;
 462           return data;
 463         }
 464       else
 465         return (wxObject *) NULL;
 466     }
 467 }
 468
 469 wxObject *wxHashTable::Delete (const wxChar *key)
 470 {
 471   int position = (int) (MakeKey (key) % n);
 472   if (position < 0) position = -position;
 473
 474   if (!hash_table[position])
 475     return (wxObject *) NULL;
 476   else
 477     {
 478       wxNode *node = hash_table[position]->Find (key);
 479       if (node)
 480         {
 481           wxObject *data = node->Data ();
 482           delete node;
 483           m_count--;
 484           return data;
 485         }
 486       else
 487         return (wxObject *) NULL;
 488     }
 489 }
 490
 491 wxObject *wxHashTable::Delete (long key, int value)
 492 {
 493   // Should NEVER be
 494   long k = (long) key;
 495
 496   int position = (int) (k % n);
 497   if (position < 0) position = -position;
 498
 499   if (!hash_table[position])
 500     return (wxObject *) NULL;
 501   else
 502     {
 503       wxNode *node = hash_table[position]->Find (value);
 504       if (node)
 505         {
 506           wxObject *data = node->Data ();
 507           delete node;
 508           m_count--;
 509           return data;
 510         }
 511       else
 512         return (wxObject *) NULL;
 513     }
 514 }
 515
 516 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 517 {
 518   int position = (int) (key % n);
 519   if (position < 0) position = -position;
 520
 521   if (!hash_table[position])
 522     return (wxObject *) NULL;
 523   else
 524     {
 525       wxNode *node = hash_table[position]->Find (value);
 526       if (node)
 527         {
 528           wxObject *data = node->Data ();
 529           delete node;
 530           m_count--;
 531           return data;
 532         }
 533       else
 534         return (wxObject *) NULL;
 535     }
 536 }
 537
 538 long wxHashTable::MakeKey (const wxChar *string) const
 539 {
 540   long int_key = 0;
 541
 542   while (*string)
 543     int_key += (wxUChar) *string++;
 544
 545   return int_key;
 546 }
 547
 548 void wxHashTable::BeginFind ()
 549 {
 550   current_position = -1;
 551   current_node = (wxNode *) NULL;
 552 }
 553
 554 wxNode *wxHashTable::Next ()
 555 {
 556   wxNode *found = (wxNode *) NULL;
 557   bool end = FALSE;
 558   while (!end && !found)
 559     {
 560       if (!current_node)
 561         {
 562           current_position++;
 563           if (current_position >= n)
 564             {
 565               current_position = -1;
 566               current_node = (wxNode *) NULL;
 567               end = TRUE;
 568             }
 569           else
 570             {
 571               if (hash_table[current_position])
 572                 {
 573                   current_node = hash_table[current_position]->First ();
 574                   found = current_node;
 575                 }
 576             }
 577         }
 578       else
 579         {
 580           current_node = current_node->Next ();
 581           found = current_node;
 582         }
 583     }
 584   return found;
 585 }
 586
 587 void wxHashTable::DeleteContents (bool flag)
 588 {
 589   int i;
 590   m_deleteContents = flag;
 591   for (i = 0; i < n; i++)
 592     {
 593       if (hash_table[i])
 594         hash_table[i]->DeleteContents (flag);
 595     }
 596 }
 597
 598 void wxHashTable::Clear ()
 599 {
 600   int i;
 601   for (i = 0; i < n; i++)
 602     {
 603       if (hash_table[i])
 604         hash_table[i]->Clear ();
 605     }
 606   m_count = 0;
 607 }
 608