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 // old not type safe wxHashTable
 124 // ----------------------------------------------------------------------------
 125
 126 wxHashTable::wxHashTable (int the_key_type, int size)
 127 {
 128   n = 0;
 129   hash_table = (wxList**) NULL;
 130   Create(the_key_type, size);
 131   m_count = 0;
 132   m_deleteContents = FALSE;
 133 /*
 134   n = size;
 135   current_position = -1;
 136   current_node = (wxNode *) NULL;
 137
 138   key_type = the_key_type;
 139   hash_table = new wxList *[size];
 140   int i;
 141   for (i = 0; i < size; i++)
 142     hash_table[i] = (wxList *) NULL;
 143 */
 144 }
 145
 146 wxHashTable::~wxHashTable ()
 147 {
 148   Destroy();
 149 }
 150
 151 void wxHashTable::Destroy()
 152 {
 153   if (!hash_table) return;
 154   int i;
 155   for (i = 0; i < n; i++)
 156     if (hash_table[i])
 157       delete hash_table[i];
 158   delete[] hash_table;
 159   hash_table = NULL;
 160 }
 161
 162 bool wxHashTable::Create(int the_key_type, int size)
 163 {
 164   Destroy();
 165
 166   n = size;
 167   current_position = -1;
 168   current_node = (wxNode *) NULL;
 169
 170   key_type = the_key_type;
 171   hash_table = new wxList *[size];
 172   int i;
 173   for (i = 0; i < size; i++)
 174     hash_table[i] = (wxList *) NULL;
 175   return TRUE;
 176 }
 177
 178
 179 void wxHashTable::DoCopy(const wxHashTable& table)
 180 {
 181   n = table.n;
 182   current_position = table.current_position;
 183   current_node = NULL; // doesn't matter - Next() will reconstruct it
 184   key_type = table.key_type;
 185
 186   hash_table = new wxList *[n];
 187   for (int i = 0; i < n; i++) {
 188     if (table.hash_table[i] == NULL)
 189       hash_table[i] = NULL;
 190     else {
 191       hash_table[i] = new wxList(key_type);
 192       *(hash_table[i]) = *(table.hash_table[i]);
 193     }
 194   }
 195 }
 196
 197 void wxHashTable::Put (long key, long value, wxObject * object)
 198 {
 199   // Should NEVER be
 200   long k = (long) key;
 201
 202   int position = (int) (k % n);
 203   if (position < 0) position = -position;
 204
 205   if (!hash_table[position])
 206   {
 207     hash_table[position] = new wxList (wxKEY_INTEGER);
 208     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 209   }
 210
 211   hash_table[position]->Append (value, object);
 212   m_count++;
 213 }
 214
 215 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 216 {
 217   // Should NEVER be
 218   long k = (long) key;
 219
 220   int position = (int) (k % n);
 221   if (position < 0) position = -position;
 222
 223   if (!hash_table[position])
 224   {
 225     hash_table[position] = new wxList (wxKEY_INTEGER);
 226     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 227   }
 228
 229   hash_table[position]->Append (value, object);
 230   m_count++;
 231 }
 232
 233 void wxHashTable::Put (long key, wxObject * object)
 234 {
 235   // Should NEVER be
 236   long k = (long) key;
 237
 238   int position = (int) (k % n);
 239   if (position < 0) position = -position;
 240
 241   if (!hash_table[position])
 242   {
 243     hash_table[position] = new wxList (wxKEY_INTEGER);
 244     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 245   }
 246
 247   hash_table[position]->Append (k, object);
 248   m_count++;
 249 }
 250
 251 void wxHashTable::Put (const wxChar *key, wxObject * object)
 252 {
 253   int position = (int) (MakeKey (key) % n);
 254   if (position < 0) position = -position;
 255
 256   if (!hash_table[position])
 257   {
 258     hash_table[position] = new wxList (wxKEY_STRING);
 259     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 260   }
 261
 262   hash_table[position]->Append (key, object);
 263   m_count++;
 264 }
 265
 266 wxObject *wxHashTable::Get (long key, long value) const
 267 {
 268   // Should NEVER be
 269   long k = (long) key;
 270
 271   int position = (int) (k % n);
 272   if (position < 0) position = -position;
 273
 274   if (!hash_table[position])
 275     return (wxObject *) NULL;
 276   else
 277     {
 278       wxNode *node = hash_table[position]->Find (value);
 279       if (node)
 280         return node->Data ();
 281       else
 282         return (wxObject *) NULL;
 283     }
 284 }
 285
 286 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 287 {
 288   // Should NEVER be
 289   long k = (long) key;
 290
 291   int position = (int) (k % n);
 292   if (position < 0) position = -position;
 293
 294   if (!hash_table[position])
 295     return (wxObject *) NULL;
 296   else
 297     {
 298       wxNode *node = hash_table[position]->Find (value);
 299       if (node)
 300         return node->Data ();
 301       else
 302         return (wxObject *) NULL;
 303     }
 304 }
 305
 306 wxObject *wxHashTable::Get (long key) const
 307 {
 308   // Should NEVER be
 309   long k = (long) key;
 310
 311   int position = (int) (k % n);
 312   if (position < 0) position = -position;
 313
 314   if (!hash_table[position])
 315     return (wxObject *) NULL;
 316   else
 317     {
 318       wxNode *node = hash_table[position]->Find (k);
 319       return node ? node->Data () : (wxObject*)NULL;
 320     }
 321 }
 322
 323 wxObject *wxHashTable::Get (const wxChar *key) const
 324 {
 325   int position = (int) (MakeKey (key) % n);
 326   if (position < 0) position = -position;
 327
 328   if (!hash_table[position])
 329     return (wxObject *) NULL;
 330   else
 331     {
 332       wxNode *node = hash_table[position]->Find (key);
 333       return node ? node->Data () : (wxObject*)NULL;
 334     }
 335 }
 336
 337 wxObject *wxHashTable::Delete (long key)
 338 {
 339   // Should NEVER be
 340   long k = (long) key;
 341
 342   int position = (int) (k % n);
 343   if (position < 0) position = -position;
 344
 345   if (!hash_table[position])
 346     return (wxObject *) NULL;
 347   else
 348     {
 349       wxNode *node = hash_table[position]->Find (k);
 350       if (node)
 351         {
 352           wxObject *data = node->Data ();
 353           delete node;
 354           m_count--;
 355           return data;
 356         }
 357       else
 358         return (wxObject *) NULL;
 359     }
 360 }
 361
 362 wxObject *wxHashTable::Delete (const wxChar *key)
 363 {
 364   int position = (int) (MakeKey (key) % n);
 365   if (position < 0) position = -position;
 366
 367   if (!hash_table[position])
 368     return (wxObject *) NULL;
 369   else
 370     {
 371       wxNode *node = hash_table[position]->Find (key);
 372       if (node)
 373         {
 374           wxObject *data = node->Data ();
 375           delete node;
 376           m_count--;
 377           return data;
 378         }
 379       else
 380         return (wxObject *) NULL;
 381     }
 382 }
 383
 384 wxObject *wxHashTable::Delete (long key, int value)
 385 {
 386   // Should NEVER be
 387   long k = (long) key;
 388
 389   int position = (int) (k % n);
 390   if (position < 0) position = -position;
 391
 392   if (!hash_table[position])
 393     return (wxObject *) NULL;
 394   else
 395     {
 396       wxNode *node = hash_table[position]->Find (value);
 397       if (node)
 398         {
 399           wxObject *data = node->Data ();
 400           delete node;
 401           m_count--;
 402           return data;
 403         }
 404       else
 405         return (wxObject *) NULL;
 406     }
 407 }
 408
 409 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 410 {
 411   int position = (int) (key % n);
 412   if (position < 0) position = -position;
 413
 414   if (!hash_table[position])
 415     return (wxObject *) NULL;
 416   else
 417     {
 418       wxNode *node = hash_table[position]->Find (value);
 419       if (node)
 420         {
 421           wxObject *data = node->Data ();
 422           delete node;
 423           m_count--;
 424           return data;
 425         }
 426       else
 427         return (wxObject *) NULL;
 428     }
 429 }
 430
 431 long wxHashTable::MakeKey (const wxChar *string) const
 432 {
 433   long int_key = 0;
 434
 435   while (*string)
 436     int_key += (wxUChar) *string++;
 437
 438   return int_key;
 439 }
 440
 441 void wxHashTable::BeginFind ()
 442 {
 443   current_position = -1;
 444   current_node = (wxNode *) NULL;
 445 }
 446
 447 wxNode *wxHashTable::Next ()
 448 {
 449   wxNode *found = (wxNode *) NULL;
 450   bool end = FALSE;
 451   while (!end && !found)
 452     {
 453       if (!current_node)
 454         {
 455           current_position++;
 456           if (current_position >= n)
 457             {
 458               current_position = -1;
 459               current_node = (wxNode *) NULL;
 460               end = TRUE;
 461             }
 462           else
 463             {
 464               if (hash_table[current_position])
 465                 {
 466                   current_node = hash_table[current_position]->First ();
 467                   found = current_node;
 468                 }
 469             }
 470         }
 471       else
 472         {
 473           current_node = current_node->Next ();
 474           found = current_node;
 475         }
 476     }
 477   return found;
 478 }
 479
 480 void wxHashTable::DeleteContents (bool flag)
 481 {
 482   int i;
 483   m_deleteContents = flag;
 484   for (i = 0; i < n; i++)
 485     {
 486       if (hash_table[i])
 487         hash_table[i]->DeleteContents (flag);
 488     }
 489 }
 490
 491 void wxHashTable::Clear ()
 492 {
 493   int i;
 494   for (i = 0; i < n; i++)
 495     {
 496       if (hash_table[i])
 497         hash_table[i]->Clear ();
 498     }
 499   m_count = 0;
 500 }
 501