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