src/CHashtable.cpp

   1 /*
   2 Copyright (C) 2005 Parallel Realities
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  12
  13 See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19 */
  20
  21 #include "headers.h"
  22
  23 Hashtable::Hashtable()
  24 {
  25         for (int i = 0 ; i < MAX_BUCKETS ; i++)
  26         {
  27                 bucket[i] = NULL;
  28         }
  29
  30         nullWarning = true;
  31
  32         name = "Unnamed Hashtable";
  33 }
  34
  35 Hashtable::~Hashtable()
  36 {
  37         clear();
  38 }
  39
  40 void Hashtable::put(char *key, void *data)
  41 {
  42         unsigned int hash = 0;
  43         unsigned int entryBucket = 0;
  44
  45         for (unsigned int i = 0 ; i < strlen(key) ; i++)
  46         {
  47                 hash = hash * MULTIPLIER + key[i];
  48         }
  49
  50         entryBucket = hash % MAX_BUCKETS;
  51
  52         Entry *entry;
  53
  54         if (bucket[entryBucket] == NULL)
  55         {
  56                 entry = new Entry();
  57                 entry->hash = hash;
  58                 entry->data = data;
  59                 entry->previous = NULL;
  60                 entry->next = NULL;
  61
  62                 bucket[entryBucket] = entry;
  63
  64                 //printf("Added %s = (Hash = %d : Bucket = %d (1))\n", key, hash, entryBucket);
  65         }
  66         else
  67         {
  68                 Entry *last = bucket[entryBucket];
  69                 int count = 1;
  70
  71                 while (true)
  72                 {
  73                         count++;
  74
  75                         // already added!
  76                         if (last->hash == hash)
  77                         {
  78                                 debug(("WARNING - POSSIBLE HASHCODE COLLISION!! - %s\n", key));
  79                                 return;
  80                         }
  81
  82                         if (last->next != NULL)
  83                         {
  84                                 last = last->next;
  85                         }
  86                         else
  87                         {
  88                                 break;
  89                         }
  90                 }
  91
  92                 entry = new Entry();
  93                 entry->hash = hash;
  94                 entry->data = data;
  95                 entry->previous = last;
  96                 entry->next = NULL;
  97
  98                 last->next = entry;
  99
 100                 //printf("Added %s = (Hash = %d : Bucket = %d (%d))\n", key, hash, entryBucket, count);
 101         }
 102 }
 103
 104 void *Hashtable::get(char *key)
 105 {
 106         unsigned int hash = 0;
 107         unsigned int entryBucket = 0;
 108
 109         for (unsigned int i = 0 ; i < strlen(key) ; i++)
 110         {
 111                 hash = hash * MULTIPLIER + key[i];
 112         }
 113
 114         entryBucket = hash % MAX_BUCKETS;
 115
 116         Entry *entry = bucket[entryBucket];
 117
 118         while (entry != NULL)
 119         {
 120                 if (entry->hash == hash)
 121                 {
 122                         return entry->data;
 123                 }
 124
 125                 entry = entry->next;
 126         }
 127
 128         if (nullWarning)
 129         {
 130                 printf("WARNING - Hashtable::get('%s') - Returning NULL!\n", key);
 131         }
 132
 133         return NULL;
 134 }
 135
 136 void Hashtable::remove(char *key)
 137 {
 138         unsigned int hash = 0;
 139         unsigned int entryBucket = 0;
 140
 141         for (unsigned int i = 0 ; i < strlen(key) ; i++)
 142         {
 143                 hash = hash * MULTIPLIER + key[i];
 144         }
 145
 146         entryBucket = hash % MAX_BUCKETS;
 147
 148         Entry *entry = bucket[entryBucket];
 149
 150         while (entry != NULL)
 151         {
 152                 if (entry->hash == hash)
 153                 {
 154                         if (entry->previous != NULL)
 155                         {
 156                                 entry->previous->next = entry->next;
 157                         }
 158
 159                         if (entry->next != NULL)
 160                         {
 161                                 entry->next->previous = entry->previous;
 162                         }
 163
 164                         free(entry->data);
 165
 166                         delete entry;
 167
 168                         if (entry == bucket[entryBucket])
 169                         {
 170                                 bucket[entryBucket] = NULL;
 171                         }
 172
 173                         return;
 174                 }
 175
 176                 entry = entry->next;
 177         }
 178 }
 179
 180 int Hashtable::getSize()
 181 {
 182         int count = 0;
 183         Entry *entry;
 184
 185         for (int i = 0 ; i < MAX_BUCKETS ; i++)
 186         {
 187                 if (bucket[i] != NULL)
 188                 {
 189                         count++;
 190
 191                         entry = bucket[i]->next;
 192
 193                         while (entry != NULL)
 194                         {
 195                                 count++;
 196
 197                                 entry = entry->next;
 198                         }
 199                 }
 200         }
 201
 202         return count;
 203 }
 204
 205 List *Hashtable::toList()
 206 {
 207         list.clear();
 208
 209         Entry *entry;
 210         Reference *ref;
 211
 212         for (int i = 0 ; i < MAX_BUCKETS ; i++)
 213         {
 214                 if (bucket[i] != NULL)
 215                 {
 216                         ref = new Reference();
 217                         ref->object = (GameObject*)bucket[i]->data;
 218                         list.add(ref);
 219
 220                         entry = bucket[i]->next;
 221
 222                         while (entry != NULL)
 223                         {
 224                                 ref = new Reference();
 225                                 ref->object = (GameObject*)entry->data;
 226                                 list.add(ref);
 227
 228                                 entry = entry->next;
 229                         }
 230                 }
 231         }
 232
 233         return &list;
 234 }
 235
 236 void Hashtable::printTable()
 237 {
 238         int count = 0;
 239         Entry *entry;
 240
 241         for (int i = 0 ; i < MAX_BUCKETS ; i++)
 242         {
 243                 if (bucket[i] != NULL)
 244                 {
 245                         count++;
 246
 247                         printf("%.3d = %d", i, bucket[i]->hash);
 248
 249                         entry = bucket[i]->next;
 250
 251                         while (entry != NULL)
 252                         {
 253                                 count++;
 254
 255                                 printf(", %d", entry->hash);
 256
 257                                 entry = entry->next;
 258                         }
 259
 260                         printf("\n");
 261                 }
 262         }
 263
 264         printf("%d entries in table\n", count);
 265 }
 266
 267 void Hashtable::clear()
 268 {
 269         Entry *entry = NULL;
 270         Entry *entry2 = NULL;
 271
 272         int count = 0;
 273
 274         for (int i = 0 ; i < MAX_BUCKETS ; i++)
 275         {
 276                 for (entry = bucket[i] ; entry != NULL ; entry = entry2)
 277                 {
 278                         entry2 = entry->next;
 279                         free(entry->data);
 280                         delete entry;
 281                         count++;
 282                 }
 283
 284                 bucket[i] = NULL;
 285         }
 286
 287         if ((count > 0) && (nullWarning))
 288         {
 289                 debug(("Removed %d items from %s Hashtable\n", count, name.getText()));
 290         }
 291 }