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