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