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