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