Page principale | Liste des namespaces | Hiérarchie des classes | Liste des classes | Répertoires | Liste des fichiers | Membres de namespace | Membres de classe | Membres de fichier

hash.cc

Aller à la documentation de ce fichier.
00001 // hash.cc 
00002 //      Routines to manage a self-expanding hash table of arbitrary things.
00003 //      The hashing function is supplied by the objects being put into
00004 //      the table; we use chaining to resolve hash conflicts.
00005 //
00006 //      The hash table is implemented as an array of sorted lists,
00007 //      and we expand the hash table if the number of elements in the table
00008 //      gets too big.
00009 // 
00010 //      NOTE: Mutual exclusion must be provided by the caller.
00011 //
00012 // Copyright (c) 1992-1996 The Regents of the University of California.
00013 // All rights reserved.  See copyright.h for copyright notice and limitation 
00014 // of liability and disclaimer of warranty provisions.
00015 
00016 const int InitialBuckets = 4;   // how big a hash table do we start with
00017 const int ResizeRatio = 3;      // when do we grow the hash table?
00018 const int IncreaseSizeBy = 4;   // how much do we grow table when needed?
00019 
00020 #include "copyright.h"
00021 
00022 //----------------------------------------------------------------------
00023 // HashTable<Key,T>::HashTable
00024 //      Initialize a hash table, empty to start with.
00025 //      Elements can now be added to the table.
00026 //----------------------------------------------------------------------
00027 
00028 template <class Key, class T>
00029 HashTable<Key,T>::HashTable(Key (*get)(T x), unsigned (*hFunc)(Key x))
00030 { 
00031     numItems = 0;
00032     InitBuckets(InitialBuckets);
00033     getKey = get;
00034     hash = hFunc;
00035 }
00036 
00037 //----------------------------------------------------------------------
00038 // HashTable<Key,T>::InitBuckets
00039 //      Initialize the bucket array for a hash table.
00040 //      Called by the constructor and by ReHash().
00041 //----------------------------------------------------------------------
00042 
00043 template <class Key, class T>
00044 void
00045 HashTable<Key,T>::InitBuckets(int sz)
00046 { 
00047     numBuckets = sz;
00048     buckets = new Bucket[numBuckets];
00049     for (int i = 0; i < sz; i++) {
00050         buckets[i] = new List<T>;
00051     }
00052 }
00053 
00054 //----------------------------------------------------------------------
00055 // HashTable<T>::~HashTable
00056 //      Prepare a hash table for deallocation.  
00057 //----------------------------------------------------------------------
00058 
00059 template <class Key, class T>
00060 HashTable<Key,T>::~HashTable()
00061 { 
00062     ASSERT(IsEmpty());          // make sure table is empty
00063     DeleteBuckets(buckets, numBuckets);
00064 }
00065 
00066 //----------------------------------------------------------------------
00067 // HashTable<Key,T>::DeleteBuckets
00068 //      De-Initialize the bucket array for a hash table.
00069 //      Called by the destructor and by ReHash().
00070 //----------------------------------------------------------------------
00071 
00072 template <class Key, class T>
00073 void
00074 HashTable<Key,T>::DeleteBuckets(List<T> **table, int sz)
00075 { 
00076     for (int i = 0; i < sz; i++) {
00077         delete table[i];
00078     }
00079     delete [] table;
00080 }
00081 
00082 //----------------------------------------------------------------------
00083 // HashTable<Key,T>::HashValue
00084 //      Return hash table bucket that would contain key.
00085 //----------------------------------------------------------------------
00086 
00087 template <class Key, class T>
00088 int
00089 HashTable<Key, T>::HashValue(Key key) const 
00090 {
00091     int result = (*hash)(key) % numBuckets;
00092     ASSERT(result >= 0 && result < numBuckets);
00093     return result;
00094 }
00095 
00096 //----------------------------------------------------------------------
00097 // HashTable<Key,T>::Insert
00098 //      Put an item into the hashtable.
00099 //      
00100 //      Resize the table if the # of elements / # of buckets is too big.
00101 //      Then allocate a HashElement to keep track of the key, item pair,
00102 //      and add it to the right bucket.
00103 //
00104 //      "key" is the key we'll use to find this item.
00105 //      "item" is the thing to put in the table.
00106 //----------------------------------------------------------------------
00107 
00108 template <class Key, class T>
00109 void
00110 HashTable<Key,T>::Insert(T item)
00111 {
00112     Key key = getKey(item);
00113 
00114     ASSERT(!IsInTable(key));
00115 
00116     if ((numItems / numBuckets) >= ResizeRatio) {
00117         ReHash();
00118     }
00119 
00120     buckets[HashValue(key)]->Append(item);
00121     numItems++;
00122 
00123     ASSERT(IsInTable(key));
00124 }
00125 
00126 //----------------------------------------------------------------------
00127 // HashTable<Key,T>::ReHash
00128 //      Increase the size of the hashtable, by 
00129 //        (i) making a new table
00130 //        (ii) moving all the elements into the new table
00131 //        (iii) deleting the old table
00132 //----------------------------------------------------------------------
00133 
00134 template <class Key, class T>
00135 void
00136 HashTable<Key,T>::ReHash()
00137 {
00138     Bucket *oldTable = buckets;
00139     int oldSize = numBuckets;
00140     T item;
00141 
00142     SanityCheck();
00143     InitBuckets(numBuckets * IncreaseSizeBy);
00144 
00145     for (int i = 0; i < oldSize; i++) {
00146         while (!oldTable[i]->IsEmpty()) {
00147             item = oldTable[i]->RemoveFront();
00148             buckets[HashValue(getKey(item))]->Append(item);
00149         }
00150     }
00151     DeleteBuckets(oldTable, oldSize);
00152     SanityCheck();
00153 }
00154 
00155 //----------------------------------------------------------------------
00156 // HashTable<Key,T>::FindInBucket
00157 //      Find an item in a hash table bucket, from it's key
00158 //
00159 //      "bucket" -- the list storing the item, if it's in the table 
00160 //      "key" -- the key uniquely identifying the item
00161 // 
00162 // Returns:
00163 //      Whether item is found, and if found, the item.
00164 //----------------------------------------------------------------------
00165 
00166 template <class Key, class T>
00167 bool
00168 HashTable<Key,T>::FindInBucket(int bucket, 
00169                                 Key key, T *itemPtr) const
00170 {
00171     ListIterator<T> iterator(buckets[bucket]);
00172 
00173     for (; !iterator.IsDone(); iterator.Next()) {
00174         if (key == getKey(iterator.Item())) { // found!
00175             *itemPtr = iterator.Item();
00176             return TRUE;
00177         }
00178     }
00179     *itemPtr = NULL;
00180     return FALSE;
00181 }
00182 
00183 //----------------------------------------------------------------------
00184 // HashTable<Key,T>::Find
00185 //      Find an item from the hash table.
00186 // 
00187 // Returns:
00188 //      The item or NULL if not found. 
00189 //----------------------------------------------------------------------
00190 
00191 template <class Key, class T>
00192 bool
00193 HashTable<Key,T>::Find(Key key, T *itemPtr) const
00194 {
00195     int bucket = HashValue(key);
00196     
00197     return FindInBucket(bucket, key, itemPtr); 
00198 }
00199 
00200 //----------------------------------------------------------------------
00201 // HashTable<Key,T>::Remove
00202 //      Remove an item from the hash table. The item must be in the table.
00203 // 
00204 // Returns:
00205 //      The removed item.
00206 //----------------------------------------------------------------------
00207 
00208 template <class Key, class T>
00209 T
00210 HashTable<Key,T>::Remove(Key key)
00211 {
00212     int bucket = HashValue(key);
00213     T item;
00214     bool found = FindInBucket(bucket, key, &item); 
00215 
00216     ASSERT(found);      // item must be in table
00217 
00218     buckets[bucket]->Remove(item);
00219     numItems--;
00220 
00221     ASSERT(!IsInTable(key));
00222     return item;
00223 }
00224 
00225 
00226 //----------------------------------------------------------------------
00227 // HashTable<Key,T>::Apply
00228 //      Apply function to every item in the hash table.
00229 //
00230 //      "func" -- the function to apply
00231 //----------------------------------------------------------------------
00232 
00233 template <class Key,class T>
00234 void
00235 HashTable<Key,T>::Apply(void (*func)(T)) const
00236 {
00237     for (int bucket = 0; bucket < numBuckets; bucket++) {
00238         buckets[bucket]->Apply(func);
00239     }
00240 }
00241 
00242 //----------------------------------------------------------------------
00243 // HashTable<Key,T>::FindNextFullBucket
00244 //      Find the next bucket in the hash table that has any items in it.
00245 //
00246 //      "bucket" -- where to start looking for full buckets
00247 //----------------------------------------------------------------------
00248 
00249 template <class Key,class T>
00250 int
00251 HashTable<Key,T>::FindNextFullBucket(int bucket) const
00252 { 
00253     for (; bucket < numBuckets; bucket++) {
00254         if (!buckets[bucket]->IsEmpty()) {
00255              break;
00256         }
00257     }
00258     return bucket;
00259 }
00260 
00261 //----------------------------------------------------------------------
00262 // HashTable<Key,T>::SanityCheck
00263 //      Test whether this is still a legal hash table.
00264 //
00265 //      Tests: are all the buckets legal?
00266 //             does the table have the right # of elements?
00267 //             do all the elements hash to where they are stored?
00268 //----------------------------------------------------------------------
00269 
00270 template <class Key, class T>
00271 void 
00272 HashTable<Key,T>::SanityCheck() const
00273 {
00274     int numFound = 0;
00275     ListIterator<T> *iterator;
00276 
00277     for (int i = 0; i < numBuckets; i++) {
00278         buckets[i]->SanityCheck();
00279         numFound += buckets[i]->NumInList();
00280         iterator = new ListIterator<T>(buckets[i]);
00281         for (; !iterator->IsDone(); iterator->Next()) {
00282             ASSERT(i == HashValue(getKey(iterator->Item())));
00283         }
00284         delete iterator;
00285     }
00286     ASSERT(numItems == numFound);
00287 
00288 }
00289 
00290 //----------------------------------------------------------------------
00291 // HashTable<Key,T>::SelfTest
00292 //      Test whether this module is working.
00293 //----------------------------------------------------------------------
00294 
00295 template <class Key, class T>
00296 void 
00297 HashTable<Key,T>::SelfTest(T *p, int numEntries)
00298 {
00299     int i;
00300     HashIterator<Key, T> *iterator = new HashIterator<Key,T>(this);
00301     
00302     SanityCheck();
00303     ASSERT(IsEmpty());  // check that table is empty in various ways
00304     for (; !iterator->IsDone(); iterator->Next()) {
00305         ASSERTNOTREACHED();
00306     }
00307     delete iterator;
00308 
00309     for (i = 0; i < numEntries; i++) {
00310         Insert(p[i]);
00311         ASSERT(IsInTable(getKey(p[i])));
00312         ASSERT(!IsEmpty());
00313     }
00314     
00315     // should be able to get out everything we put in
00316     for (i = 0; i < numEntries; i++) {  
00317         ASSERT(Remove(getKey(p[i])) == p[i]);
00318     }
00319 
00320     ASSERT(IsEmpty());
00321     SanityCheck();
00322 }
00323 
00324 
00325 //----------------------------------------------------------------------
00326 // HashIterator<Key,T>::HashIterator
00327 //      Initialize a data structure to allow us to step through
00328 //      every entry in a has table.
00329 //----------------------------------------------------------------------
00330 
00331 template <class Key, class T>
00332 HashIterator<Key,T>::HashIterator(HashTable<Key,T> *tbl) 
00333 { 
00334     table = tbl;
00335     bucket = table->FindNextFullBucket(0);
00336     bucketIter = NULL;
00337     if (bucket < table->numBuckets) {
00338         bucketIter = new ListIterator<T>(table->buckets[bucket]);
00339     }
00340 }
00341 
00342 //----------------------------------------------------------------------
00343 // HashIterator<Key,T>::Next
00344 //      Update iterator to point to the next item in the table.
00345 //----------------------------------------------------------------------
00346 
00347 template <class Key,class T>
00348 void
00349 HashIterator<Key,T>::Next() 
00350 { 
00351     bucketIter->Next();
00352     if (bucketIter->IsDone()) {
00353         delete bucketIter;
00354         bucketIter = NULL;
00355         bucket = table->FindNextFullBucket(++bucket);
00356         if (bucket < table->numBuckets) {
00357             bucketIter = new ListIterator<T>(table->buckets[bucket]);
00358         }
00359     }
00360 }

Généré le Sun Jan 15 00:45:45 2006 pour Système NachOS : par  doxygen 1.4.4