src/common/hash.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        hash.cpp
   3 // Purpose:     wxHashTable implementation
   4 // Author:      Julian Smart
   5 // Modified by:
   6 // Created:     01/02/97
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) Julian Smart and Markus Holzem
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 #ifdef __GNUG__
  13 #pragma implementation "hash.h"
  14 #endif
  15
  16 // For compilers that support precompilation, includes "wx.h".
  17 #include "wx/wxprec.h"
  18
  19 #ifdef __BORLANDC__
  20 #pragma hdrstop
  21 #endif
  22
  23 #ifndef WX_PRECOMP
  24 #include "wx/list.h"
  25 #endif
  26
  27 #include "wx/hash.h"
  28
  29 #include <string.h>
  30 #include <stdarg.h>
  31
  32 IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
  33
  34 wxHashTable::wxHashTable (int the_key_type, int size)
  35 {
  36   n = 0;
  37   hash_table = (wxList**) NULL;
  38   Create(the_key_type, size);
  39   m_count = 0;
  40   m_deleteContents = FALSE;
  41 /*
  42   n = size;
  43   current_position = -1;
  44   current_node = (wxNode *) NULL;
  45
  46   key_type = the_key_type;
  47   hash_table = new wxList *[size];
  48   int i;
  49   for (i = 0; i < size; i++)
  50     hash_table[i] = (wxList *) NULL;
  51 */
  52 }
  53
  54 wxHashTable::~wxHashTable (void)
  55 {
  56   Destroy();
  57 }
  58
  59 void wxHashTable::Destroy(void)
  60 {
  61   if (!hash_table) return;
  62   int i;
  63   for (i = 0; i < n; i++)
  64     if (hash_table[i])
  65       delete hash_table[i];
  66   delete[] hash_table;
  67   hash_table = NULL;
  68 }
  69
  70 bool wxHashTable::Create(int the_key_type, int size)
  71 {
  72   Destroy();
  73
  74   n = size;
  75   current_position = -1;
  76   current_node = (wxNode *) NULL;
  77
  78   key_type = the_key_type;
  79   hash_table = new wxList *[size];
  80   int i;
  81   for (i = 0; i < size; i++)
  82     hash_table[i] = (wxList *) NULL;
  83   return TRUE;
  84 }
  85
  86
  87 void wxHashTable::DoCopy(const wxHashTable& table)
  88 {
  89   n = table.n;
  90   current_position = table.current_position;
  91   current_node = NULL; // doesn't matter - Next() will reconstruct it
  92   key_type = table.key_type;
  93
  94   hash_table = new wxList *[n];
  95   for (int i = 0; i < n; i++) {
  96     if (table.hash_table[i] == NULL)
  97       hash_table[i] = NULL;
  98     else {
  99       hash_table[i] = new wxList(key_type);
 100       *(hash_table[i]) = *(table.hash_table[i]);
 101     }
 102   }
 103 }
 104
 105 void wxHashTable::Put (long key, long value, wxObject * object)
 106 {
 107   // Should NEVER be
 108   long k = (long) key;
 109   if (k < 0)
 110     k = -k;
 111
 112   int position = (int) (k % n);
 113   if (!hash_table[position])
 114   {
 115     hash_table[position] = new wxList (wxKEY_INTEGER);
 116     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 117   }
 118
 119   hash_table[position]->Append (value, object);
 120   m_count++;
 121 }
 122
 123 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
 124 {
 125   // Should NEVER be
 126   long k = (long) key;
 127   if (k < 0)
 128     k = -k;
 129
 130   int position = (int) (k % n);
 131   if (!hash_table[position])
 132   {
 133     hash_table[position] = new wxList (wxKEY_INTEGER);
 134     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 135   }
 136
 137   hash_table[position]->Append (value, object);
 138   m_count++;
 139 }
 140
 141 void wxHashTable::Put (long key, wxObject * object)
 142 {
 143   // Should NEVER be
 144   long k = (long) key;
 145   if (k < 0)
 146     k = -k;
 147
 148   int position = (int) (k % n);
 149   if (!hash_table[position])
 150   {
 151     hash_table[position] = new wxList (wxKEY_INTEGER);
 152     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 153   }
 154
 155   hash_table[position]->Append (k, object);
 156   m_count++;
 157 }
 158
 159 void wxHashTable::Put (const wxChar *key, wxObject * object)
 160 {
 161   int position = (int) (MakeKey (key) % n);
 162
 163   if (!hash_table[position])
 164   {
 165     hash_table[position] = new wxList (wxKEY_STRING);
 166     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 167   }
 168
 169   hash_table[position]->Append (key, object);
 170   m_count++;
 171 }
 172
 173 wxObject *wxHashTable::Get (long key, long value) const
 174 {
 175   // Should NEVER be
 176   long k = (long) key;
 177   if (k < 0)
 178     k = -k;
 179
 180   int position = (int) (k % n);
 181   if (!hash_table[position])
 182     return (wxObject *) NULL;
 183   else
 184     {
 185       wxNode *node = hash_table[position]->Find (value);
 186       if (node)
 187         return node->Data ();
 188       else
 189         return (wxObject *) NULL;
 190     }
 191 }
 192
 193 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 194 {
 195   // Should NEVER be
 196   long k = (long) key;
 197   if (k < 0)
 198     k = -k;
 199
 200   int position = (int) (k % n);
 201   if (!hash_table[position])
 202     return (wxObject *) NULL;
 203   else
 204     {
 205       wxNode *node = hash_table[position]->Find (value);
 206       if (node)
 207         return node->Data ();
 208       else
 209         return (wxObject *) NULL;
 210     }
 211 }
 212
 213 wxObject *wxHashTable::Get (long key) const
 214 {
 215   // Should NEVER be
 216   long k = (long) key;
 217   if (k < 0)
 218     k = -k;
 219
 220   int position = (int) (k % n);
 221   if (!hash_table[position])
 222     return (wxObject *) NULL;
 223   else
 224     {
 225       wxNode *node = hash_table[position]->Find (k);
 226       return node ? node->Data () : (wxObject*)NULL;
 227     }
 228 }
 229
 230 wxObject *wxHashTable::Get (const wxChar *key) const
 231 {
 232   int position = (int) (MakeKey (key) % n);
 233
 234   if (!hash_table[position])
 235     return (wxObject *) NULL;
 236   else
 237     {
 238       wxNode *node = hash_table[position]->Find (key);
 239       return node ? node->Data () : (wxObject*)NULL;
 240     }
 241 }
 242
 243 wxObject *wxHashTable::Delete (long key)
 244 {
 245   // Should NEVER be
 246   long k = (long) key;
 247   if (k < 0)
 248     k = -k;
 249
 250   int position = (int) (k % n);
 251   if (!hash_table[position])
 252     return (wxObject *) NULL;
 253   else
 254     {
 255       wxNode *node = hash_table[position]->Find (k);
 256       if (node)
 257         {
 258           wxObject *data = node->Data ();
 259           delete node;
 260           m_count--;
 261           return data;
 262         }
 263       else
 264         return (wxObject *) NULL;
 265     }
 266 }
 267
 268 wxObject *wxHashTable::Delete (const wxChar *key)
 269 {
 270   int position = (int) (MakeKey (key) % n);
 271   if (!hash_table[position])
 272     return (wxObject *) NULL;
 273   else
 274     {
 275       wxNode *node = hash_table[position]->Find (key);
 276       if (node)
 277         {
 278           wxObject *data = node->Data ();
 279           delete node;
 280           m_count--;
 281           return data;
 282         }
 283       else
 284         return (wxObject *) NULL;
 285     }
 286 }
 287
 288 wxObject *wxHashTable::Delete (long key, int value)
 289 {
 290   // Should NEVER be
 291   long k = (long) key;
 292   if (k < 0)
 293     k = -k;
 294
 295   int position = (int) (k % n);
 296   if (!hash_table[position])
 297     return (wxObject *) NULL;
 298   else
 299     {
 300       wxNode *node = hash_table[position]->Find (value);
 301       if (node)
 302         {
 303           wxObject *data = node->Data ();
 304           delete node;
 305           m_count--;
 306           return data;
 307         }
 308       else
 309         return (wxObject *) NULL;
 310     }
 311 }
 312
 313 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 314 {
 315   int position = (int) (key % n);
 316   if (!hash_table[position])
 317     return (wxObject *) NULL;
 318   else
 319     {
 320       wxNode *node = hash_table[position]->Find (value);
 321       if (node)
 322         {
 323           wxObject *data = node->Data ();
 324           delete node;
 325           m_count--;
 326           return data;
 327         }
 328       else
 329         return (wxObject *) NULL;
 330     }
 331 }
 332
 333 long wxHashTable::MakeKey (const wxChar *string) const
 334 {
 335   long int_key = 0;
 336
 337   while (*string)
 338     int_key += (wxUChar) *string++;
 339
 340   return int_key;
 341 }
 342
 343 void wxHashTable::BeginFind (void)
 344 {
 345   current_position = -1;
 346   current_node = (wxNode *) NULL;
 347 }
 348
 349 wxNode *wxHashTable::Next (void)
 350 {
 351   wxNode *found = (wxNode *) NULL;
 352   bool end = FALSE;
 353   while (!end && !found)
 354     {
 355       if (!current_node)
 356         {
 357           current_position++;
 358           if (current_position >= n)
 359             {
 360               current_position = -1;
 361               current_node = (wxNode *) NULL;
 362               end = TRUE;
 363             }
 364           else
 365             {
 366               if (hash_table[current_position])
 367                 {
 368                   current_node = hash_table[current_position]->First ();
 369                   found = current_node;
 370                 }
 371             }
 372         }
 373       else
 374         {
 375           current_node = current_node->Next ();
 376           found = current_node;
 377         }
 378     }
 379   return found;
 380 }
 381
 382 void wxHashTable::DeleteContents (bool flag)
 383 {
 384   int i;
 385   m_deleteContents = flag;
 386   for (i = 0; i < n; i++)
 387     {
 388       if (hash_table[i])
 389         hash_table[i]->DeleteContents (flag);
 390     }
 391 }
 392
 393 void wxHashTable::Clear (void)
 394 {
 395   int i;
 396   for (i = 0; i < n; i++)
 397     {
 398       if (hash_table[i])
 399         hash_table[i]->Clear ();
 400     }
 401   m_count = 0;
 402 }
 403