Dictionary.cc

Go to the documentation of this file.
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 }

Generated on Sun Jun 8 10:56:39 2008 for GNUmifluz by  doxygen 1.5.5