Dictionary.cc

00001 //
00002 // Dictionary.cc
00003 //
00004 // Dictionary: This class provides an object lookup table. 
00005 // Each object in the dictionary is indexed with a string. 
00006 // The objects can be returned by mentioning their
00007 // string index.
00008 //
00009 // Part of the ht://Dig package <http://www.htdig.org/>
00010 // Copyright (c) 1999, 2000, 2001 The ht://Dig Group
00011 // For copyright details, see the file COPYING in your distribution
00012 // or the GNU General Public License version 2 or later 
00013 // <http://www.gnu.org/copyleft/gpl.html>
00014 //
00015 // $Id: Dictionary_8cc-source.html,v 1.1 2008年06月08日 10:12:53 sebdiaz Exp $
00016 //
00017 
00018 #ifdef HAVE_CONFIG_H
00019 #include "config.h"
00020 #endif /* HAVE_CONFIG_H */
00021 
00022 #include "Dictionary.h"
00023 
00024 #include <stdlib.h>
00025 
00026 class DictionaryEntry
00027 {
00028 public:
00029 unsigned int hash;
00030 char *key;
00031 Object *value;
00032 DictionaryEntry *next;
00033 
00034 ~DictionaryEntry();
00035 void release();
00036 };
00037 
00038 DictionaryEntry::~DictionaryEntry()
00039 {
00040 free(key);
00041 delete value;
00042 }
00043 
00044 void
00045 DictionaryEntry::release()
00046 {
00047 value = NULL; // Prevent the value from being deleted
00048 }
00049 
00050 
00051 //*********************************************************************
00052 //
00053 Dictionary::Dictionary()
00054 {
00055 init(101, 10.0f);
00056 }
00057 
00058 Dictionary::Dictionary(int initialCapacity, float loadFactor)
00059 {
00060 init(initialCapacity, loadFactor);
00061 }
00062 
00063 Dictionary::Dictionary(int initialCapacity)
00064 {
00065 init(initialCapacity, 0.75f);
00066 }
00067 
00068 Dictionary::Dictionary(const Dictionary& other) : Object()
00069 {
00070 init(other.initialCapacity, other.loadFactor);
00071 
00072 DictionaryCursor cursor;
00073 const char* key;
00074 for(other.Start_Get(cursor); (key = other.Get_Next(cursor));) {
00075 Add(key, other[key]);
00076 }
00077 }
00078 
00079 //*********************************************************************
00080 //
00081 Dictionary::~Dictionary()
00082 {
00083 Destroy();
00084 
00085 delete [] table;
00086 }
00087 
00088 
00089 //*********************************************************************
00090 //
00091 void
00092 Dictionary::Destroy()
00093 {
00094 DictionaryEntry *t, *n;
00095 
00096 for (int i = 0; i < tableLength; i++)
00097 {
00098 if (table[i] != NULL)
00099 { 
00100 t = table[i];
00101 do { // clear out hash chain
00102 n = t->next;
00103 delete t;
00104 t = n;
00105 } while (n);
00106 table[i] = NULL;
00107 }
00108 }
00109 count = 0;
00110 }
00111 
00112 //*********************************************************************
00113 //
00114 void
00115 Dictionary::Release()
00116 {
00117 DictionaryEntry *t, *n;
00118 
00119 for (int i = 0; i < tableLength; i++)
00120 {
00121 if (table[i] != NULL)
00122 {
00123 t = table[i];
00124 do { // clear out hash chain
00125 n = t->next;
00126 t->release();
00127 delete t;
00128 t = n;
00129 } while (n);
00130 table[i] = NULL;
00131 }
00132 }
00133 count = 0;
00134 }
00135 
00136 
00137 //*********************************************************************
00138 //
00139 void
00140 Dictionary::init(int initialCapacity, float loadFactor)
00141 {
00142 if (initialCapacity <= 0)
00143 initialCapacity = 101;
00144 if (loadFactor <= 0.0)
00145 loadFactor = 0.75f;
00146 Dictionary::loadFactor = loadFactor;
00147 table = new DictionaryEntry*[initialCapacity];
00148 for (int i = 0; i < initialCapacity; i++)
00149 {
00150 table[i] = NULL;
00151 }
00152 threshold = (int)(initialCapacity * loadFactor);
00153 tableLength = initialCapacity;
00154 count = 0;
00155 }
00156 
00157 //*********************************************************************
00158 //
00159 unsigned int
00160 Dictionary::hashCode(const char *key) const
00161 {
00162 char *test;
00163 long conv_key = strtol(key, &test, 10);
00164 if (key && *key && !*test) // Conversion succeeded
00165 return conv_key;
00166 unsigned int h = 0;
00167 int length = strlen(key);
00168 
00169 if (length < 16)
00170 {
00171 for (int i = length; i > 0; i--)
00172 {
00173 h = (h * 37) + *key++;
00174 }
00175 }
00176 else
00177 {
00178 int skip = length / 8;
00179 for (int i = length; i > 0; i -= skip, key += skip)
00180 {
00181 h = (h * 39) + *key;
00182 }
00183 }
00184 return h;
00185 }
00186 
00187 //*********************************************************************
00188 // Add an entry to the hash table. This will *not* delete the
00189 // data associated with an already existing key. Use the Replace
00190 // method for that function.
00191 //
00192 void
00193 Dictionary::Add(const String& name, Object *obj)
00194 {
00195 unsigned int hash = hashCode(name);
00196 int index = hash % tableLength;
00197 DictionaryEntry *e;
00198 
00199 for (e = table[index]; e != NULL; e = e->next)
00200 {
00201 if (e->hash == hash && strcmp(e->key, name) == 0)
00202 {
00203 delete e->value;
00204 e->value = obj;
00205 return;
00206 }
00207 }
00208 
00209 if (count >= threshold)
00210 {
00211 rehash();
00212 Add(name, obj);
00213 return;
00214 }
00215 
00216 e = new DictionaryEntry();
00217 e->hash = hash;
00218 e->key = strdup(name);
00219 e->value = obj;
00220 e->next = table[index];
00221 table[index] = e;
00222 count++;
00223 }
00224 
00225 
00226 //*********************************************************************
00227 // Remove an entry from the hash table.
00228 //
00229 int
00230 Dictionary::Remove(const String& name)
00231 {
00232 if (!count)
00233 return 0;
00234 
00235 unsigned int hash = hashCode(name);
00236 int index = hash % tableLength;
00237 DictionaryEntry *e, *prev;
00238 
00239 for (e = table[index], prev = NULL; e != NULL; prev = e, e = e->next)
00240 {
00241 if (hash == e->hash && strcmp(e->key, name) == 0)
00242 {
00243 if (prev != NULL)
00244 {
00245 prev->next = e->next;
00246 }
00247 else
00248 {
00249 table[index] = e->next;
00250 }
00251 count--;
00252 delete e;
00253 return 1;
00254 }
00255 }
00256 return 0;
00257 }
00258 
00259 
00260 //*********************************************************************
00261 //
00262 Object *Dictionary::Find(const String& name) const
00263 {
00264 if (!count)
00265 return NULL;
00266 
00267 unsigned int hash = hashCode(name);
00268 int index = hash % tableLength;
00269 DictionaryEntry *e;
00270 
00271 for (e = table[index]; e != NULL; e = e->next)
00272 {
00273 if (e->hash == hash && strcmp(e->key, name) == 0)
00274 {
00275 return e->value;
00276 }
00277 }
00278 return NULL;
00279 }
00280 
00281 
00282 //*********************************************************************
00283 //
00284 Object *Dictionary::operator[](const String& name) const
00285 {
00286 return Find(name);
00287 }
00288 
00289 
00290 //*********************************************************************
00291 //
00292 int Dictionary::Exists(const String& name) const
00293 {
00294 if (!count)
00295 return 0;
00296 
00297 unsigned int hash = hashCode(name);
00298 int index = hash % tableLength;
00299 DictionaryEntry *e;
00300 
00301 for (e = table[index]; e != NULL; e = e->next)
00302 {
00303 if (e->hash == hash && strcmp(e->key, name) == 0)
00304 {
00305 return 1;
00306 }
00307 }
00308 return 0;
00309 }
00310 
00311 
00312 //*********************************************************************
00313 //
00314 void
00315 Dictionary::rehash()
00316 {
00317 DictionaryEntry **oldTable = table;
00318 int oldCapacity = tableLength;
00319 
00320 int newCapacity;
00321 DictionaryEntry *e;
00322 int i, index;
00323 
00324 newCapacity = count > oldCapacity ? count * 2 + 1 : oldCapacity * 2 + 1;
00325 
00326 DictionaryEntry **newTable = new DictionaryEntry*[newCapacity];
00327 
00328 for (i = 0; i < newCapacity; i++)
00329 {
00330 newTable[i] = NULL;
00331 }
00332 
00333 threshold = (int) (newCapacity * loadFactor);
00334 table = newTable;
00335 tableLength = newCapacity;
00336 
00337 for (i = oldCapacity; i-- > 0;)
00338 {
00339 for (DictionaryEntry *old = oldTable[i]; old != NULL;)
00340 {
00341 e = old;
00342 old = old->next;
00343 index = e->hash % newCapacity;
00344 e->next = newTable[index];
00345 newTable[index] = e;
00346 }
00347 }
00348 delete [] oldTable;
00349 }
00350 
00351 
00352 //*********************************************************************
00353 //
00354 void
00355 Dictionary::Start_Get(DictionaryCursor& cursor) const
00356 {
00357 cursor.currentTableIndex = -1;
00358 cursor.currentDictionaryEntry = NULL;
00359 }
00360 
00361 
00362 //*********************************************************************
00363 //
00364 char *
00365 Dictionary::Get_Next(DictionaryCursor& cursor) const
00366 {
00367 while (cursor.currentDictionaryEntry == NULL ||
00368 cursor.currentDictionaryEntry->next == NULL)
00369 {
00370 cursor.currentTableIndex++;
00371 
00372 if (cursor.currentTableIndex >= tableLength)
00373 {
00374 cursor.currentTableIndex--;
00375 return NULL;
00376 }
00377 
00378 cursor.currentDictionaryEntry = table[cursor.currentTableIndex];
00379 
00380 if (cursor.currentDictionaryEntry != NULL)
00381 {
00382 return cursor.currentDictionaryEntry->key;
00383 }
00384 }
00385 
00386 cursor.currentDictionaryEntry = cursor.currentDictionaryEntry->next;
00387 return cursor.currentDictionaryEntry->key;
00388 }
00389 
00390 //*********************************************************************
00391 //
00392 Object *
00393 Dictionary::Get_NextElement(DictionaryCursor& cursor) const
00394 {
00395 while (cursor.currentDictionaryEntry == NULL ||
00396 cursor.currentDictionaryEntry->next == NULL)
00397 {
00398 cursor.currentTableIndex++;
00399 
00400 if (cursor.currentTableIndex >= tableLength)
00401 {
00402 cursor.currentTableIndex--;
00403 return NULL;
00404 }
00405 
00406 cursor.currentDictionaryEntry = table[cursor.currentTableIndex];
00407 
00408 if (cursor.currentDictionaryEntry != NULL)
00409 {
00410 return cursor.currentDictionaryEntry->value;
00411 }
00412 }
00413 
00414 cursor.currentDictionaryEntry = cursor.currentDictionaryEntry->next;
00415 return cursor.currentDictionaryEntry->value;
00416 }