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
 110   int position = (int) (k % n);
 111   if (position < 0) position = -position;
 112
 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
 128   int position = (int) (k % n);
 129   if (position < 0) position = -position;
 130
 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
 146   int position = (int) (k % n);
 147   if (position < 0) position = -position;
 148
 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   if (position < 0) position = -position;
 163
 164   if (!hash_table[position])
 165   {
 166     hash_table[position] = new wxList (wxKEY_STRING);
 167     if (m_deleteContents) hash_table[position]->DeleteContents(TRUE);
 168   }
 169
 170   hash_table[position]->Append (key, object);
 171   m_count++;
 172 }
 173
 174 wxObject *wxHashTable::Get (long key, long value) const
 175 {
 176   // Should NEVER be
 177   long k = (long) key;
 178
 179   int position = (int) (k % n);
 180   if (position < 0) position = -position;
 181
 182   if (!hash_table[position])
 183     return (wxObject *) NULL;
 184   else
 185     {
 186       wxNode *node = hash_table[position]->Find (value);
 187       if (node)
 188         return node->Data ();
 189       else
 190         return (wxObject *) NULL;
 191     }
 192 }
 193
 194 wxObject *wxHashTable::Get (long key, const wxChar *value) const
 195 {
 196   // Should NEVER be
 197   long k = (long) key;
 198
 199   int position = (int) (k % n);
 200   if (position < 0) position = -position;
 201
 202   if (!hash_table[position])
 203     return (wxObject *) NULL;
 204   else
 205     {
 206       wxNode *node = hash_table[position]->Find (value);
 207       if (node)
 208         return node->Data ();
 209       else
 210         return (wxObject *) NULL;
 211     }
 212 }
 213
 214 wxObject *wxHashTable::Get (long key) const
 215 {
 216   // Should NEVER be
 217   long k = (long) key;
 218
 219   int position = (int) (k % n);
 220   if (position < 0) position = -position;
 221
 222   if (!hash_table[position])
 223     return (wxObject *) NULL;
 224   else
 225     {
 226       wxNode *node = hash_table[position]->Find (k);
 227       return node ? node->Data () : (wxObject*)NULL;
 228     }
 229 }
 230
 231 wxObject *wxHashTable::Get (const wxChar *key) const
 232 {
 233   int position = (int) (MakeKey (key) % n);
 234   if (position < 0) position = -position;
 235
 236   if (!hash_table[position])
 237     return (wxObject *) NULL;
 238   else
 239     {
 240       wxNode *node = hash_table[position]->Find (key);
 241       return node ? node->Data () : (wxObject*)NULL;
 242     }
 243 }
 244
 245 wxObject *wxHashTable::Delete (long key)
 246 {
 247   // Should NEVER be
 248   long k = (long) key;
 249
 250   int position = (int) (k % n);
 251   if (position < 0) position = -position;
 252
 253   if (!hash_table[position])
 254     return (wxObject *) NULL;
 255   else
 256     {
 257       wxNode *node = hash_table[position]->Find (k);
 258       if (node)
 259         {
 260           wxObject *data = node->Data ();
 261           delete node;
 262           m_count--;
 263           return data;
 264         }
 265       else
 266         return (wxObject *) NULL;
 267     }
 268 }
 269
 270 wxObject *wxHashTable::Delete (const wxChar *key)
 271 {
 272   int position = (int) (MakeKey (key) % n);
 273   if (position < 0) position = -position;
 274
 275   if (!hash_table[position])
 276     return (wxObject *) NULL;
 277   else
 278     {
 279       wxNode *node = hash_table[position]->Find (key);
 280       if (node)
 281         {
 282           wxObject *data = node->Data ();
 283           delete node;
 284           m_count--;
 285           return data;
 286         }
 287       else
 288         return (wxObject *) NULL;
 289     }
 290 }
 291
 292 wxObject *wxHashTable::Delete (long key, int value)
 293 {
 294   // Should NEVER be
 295   long k = (long) key;
 296
 297   int position = (int) (k % n);
 298   if (position < 0) position = -position;
 299
 300   if (!hash_table[position])
 301     return (wxObject *) NULL;
 302   else
 303     {
 304       wxNode *node = hash_table[position]->Find (value);
 305       if (node)
 306         {
 307           wxObject *data = node->Data ();
 308           delete node;
 309           m_count--;
 310           return data;
 311         }
 312       else
 313         return (wxObject *) NULL;
 314     }
 315 }
 316
 317 wxObject *wxHashTable::Delete (long key, const wxChar *value)
 318 {
 319   int position = (int) (key % n);
 320   if (position < 0) position = -position;
 321
 322   if (!hash_table[position])
 323     return (wxObject *) NULL;
 324   else
 325     {
 326       wxNode *node = hash_table[position]->Find (value);
 327       if (node)
 328         {
 329           wxObject *data = node->Data ();
 330           delete node;
 331           m_count--;
 332           return data;
 333         }
 334       else
 335         return (wxObject *) NULL;
 336     }
 337 }
 338
 339 long wxHashTable::MakeKey (const wxChar *string) const
 340 {
 341   long int_key = 0;
 342
 343   while (*string)
 344     int_key += (wxUChar) *string++;
 345
 346   return int_key;
 347 }
 348
 349 void wxHashTable::BeginFind (void)
 350 {
 351   current_position = -1;
 352   current_node = (wxNode *) NULL;
 353 }
 354
 355 wxNode *wxHashTable::Next (void)
 356 {
 357   wxNode *found = (wxNode *) NULL;
 358   bool end = FALSE;
 359   while (!end && !found)
 360     {
 361       if (!current_node)
 362         {
 363           current_position++;
 364           if (current_position >= n)
 365             {
 366               current_position = -1;
 367               current_node = (wxNode *) NULL;
 368               end = TRUE;
 369             }
 370           else
 371             {
 372               if (hash_table[current_position])
 373                 {
 374                   current_node = hash_table[current_position]->First ();
 375                   found = current_node;
 376                 }
 377             }
 378         }
 379       else
 380         {
 381           current_node = current_node->Next ();
 382           found = current_node;
 383         }
 384     }
 385   return found;
 386 }
 387
 388 void wxHashTable::DeleteContents (bool flag)
 389 {
 390   int i;
 391   m_deleteContents = flag;
 392   for (i = 0; i < n; i++)
 393     {
 394       if (hash_table[i])
 395         hash_table[i]->DeleteContents (flag);
 396     }
 397 }
 398
 399 void wxHashTable::Clear (void)
 400 {
 401   int i;
 402   for (i = 0; i < n; i++)
 403     {
 404       if (hash_table[i])
 405         hash_table[i]->Clear ();
 406     }
 407   m_count = 0;
 408 }
 409