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