GME  13
ValueHashTableOf.c
Go to the documentation of this file.
00001 /*
00002  * Licensed to the Apache Software Foundation (ASF) under one or more
00003  * contributor license agreements.  See the NOTICE file distributed with
00004  * this work for additional information regarding copyright ownership.
00005  * The ASF licenses this file to You under the Apache License, Version 2.0
00006  * (the "License"); you may not use this file except in compliance with
00007  * the License.  You may obtain a copy of the License at
00008  *
00009  *      http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 
00018 /*
00019  * $Id: ValueHashTableOf.c 679340 2008-07-24 10:28:29Z borisk $
00020  */
00021 
00022 
00023 // ---------------------------------------------------------------------------
00024 //  Include
00025 // ---------------------------------------------------------------------------
00026 #if defined(XERCES_TMPLSINC)
00027 #include <xercesc/util/ValueHashTableOf.hpp>
00028 #endif
00029 
00030 #include <xercesc/util/NullPointerException.hpp>
00031 #include <xercesc/util/Janitor.hpp>
00032 #include <assert.h>
00033 #include <new>
00034 
00035 XERCES_CPP_NAMESPACE_BEGIN
00036 
00037 // ---------------------------------------------------------------------------
00038 //  ValueHashTableOf: Constructors and Destructor
00039 // ---------------------------------------------------------------------------
00040 template <class TVal, class THasher>
00041 ValueHashTableOf<TVal, THasher>::ValueHashTableOf( const XMLSize_t modulus
00042                                                    , const THasher& hasher
00043                                                    , MemoryManager* const manager)
00044     : fMemoryManager(manager)
00045     , fBucketList(0)
00046     , fHashModulus(modulus)
00047     , fInitialModulus(modulus)
00048     , fCount(0)
00049     , fHasher(hasher)
00050 {
00051     initialize(modulus);
00052 }
00053 
00054 template <class TVal, class THasher>
00055 ValueHashTableOf<TVal, THasher>::ValueHashTableOf( const XMLSize_t modulus
00056                                                    , MemoryManager* const manager)
00057     : fMemoryManager(manager)
00058     , fBucketList(0)
00059     , fHashModulus(modulus)
00060     , fInitialModulus(modulus)
00061     , fCount(0)
00062     , fHasher()
00063 {
00064     initialize(modulus);
00065 }
00066 
00067 template <class TVal, class THasher>
00068 void ValueHashTableOf<TVal, THasher>::initialize(const XMLSize_t modulus)
00069 {
00070     if (modulus == 0)
00071         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
00072 
00073     // Allocate the bucket list and zero them
00074     fBucketList = (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate
00075     (
00076         fHashModulus * sizeof(ValueHashTableBucketElem<TVal>*)
00077     ); //new ValueHashTableBucketElem<TVal>*[fHashModulus];
00078     memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
00079 }
00080 
00081 template <class TVal, class THasher>
00082 ValueHashTableOf<TVal, THasher>::~ValueHashTableOf()
00083 {
00084     removeAll();
00085 
00086     // Then delete the bucket list & hasher
00087     fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
00088 }
00089 
00090 
00091 // ---------------------------------------------------------------------------
00092 //  ValueHashTableOf: Element management
00093 // ---------------------------------------------------------------------------
00094 template <class TVal, class THasher>
00095 bool ValueHashTableOf<TVal, THasher>::isEmpty() const
00096 {
00097     return fCount==0;
00098 }
00099 
00100 template <class TVal, class THasher>
00101 bool ValueHashTableOf<TVal, THasher>::
00102 containsKey(const void* const key) const
00103 {
00104     XMLSize_t hashVal;
00105     const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
00106     return (findIt != 0);
00107 }
00108 
00109 template <class TVal, class THasher>
00110 void ValueHashTableOf<TVal, THasher>::
00111 removeKey(const void* const key)
00112 {
00113     XMLSize_t hashVal;
00114     removeBucketElem(key, hashVal);
00115 }
00116 
00117 template <class TVal, class THasher>
00118 void ValueHashTableOf<TVal, THasher>::removeAll()
00119 {
00120     if(isEmpty())
00121         return;
00122 
00123     // Clean up the buckets first
00124     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
00125     {
00126         // Get the bucket list head for this entry
00127         ValueHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
00128         ValueHashTableBucketElem<TVal>* nextElem;
00129         while (curElem)
00130         {
00131             // Save the next element before we hose this one
00132             nextElem = curElem->fNext;
00133 
00134             // delete the current element and move forward
00135             // destructor is empty...
00136             // curElem->~ValueHashTableBucketElem();
00137             fMemoryManager->deallocate(curElem);
00138             curElem = nextElem;
00139         }
00140 
00141         // Clean out this entry
00142         fBucketList[buckInd] = 0;
00143     }
00144     fCount = 0;
00145 }
00146 
00147 
00148 // ---------------------------------------------------------------------------
00149 //  ValueHashTableOf: Getters
00150 // ---------------------------------------------------------------------------
00151 template <class TVal, class THasher>
00152 TVal& ValueHashTableOf<TVal, THasher>::get(const void* const key, MemoryManager* const manager)
00153 {
00154     XMLSize_t hashVal;
00155     ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
00156     if (!findIt)
00157         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, manager);
00158 
00159     return findIt->fData;
00160 }
00161 
00162 template <class TVal, class THasher>
00163 const TVal& ValueHashTableOf<TVal, THasher>::
00164 get(const void* const key) const
00165 {
00166     XMLSize_t hashVal;
00167     const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
00168     if (!findIt)
00169         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
00170 
00171     return findIt->fData;
00172 }
00173 
00174 
00175 // ---------------------------------------------------------------------------
00176 //  ValueHashTableOf: Putters
00177 // ---------------------------------------------------------------------------
00178 template <class TVal, class THasher>
00179 void ValueHashTableOf<TVal, THasher>::put(void* key, const TVal& valueToAdopt)
00180 {
00181     // Apply 0.75 load factor to find threshold.
00182     XMLSize_t threshold = fHashModulus * 3 / 4;
00183 
00184     // If we've grown too big, expand the table and rehash.
00185     if (fCount >= threshold)
00186         rehash();
00187 
00188     // First see if the key exists already
00189     XMLSize_t hashVal;
00190     ValueHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
00191 
00192     //
00193     //  If so,then update its value. If not, then we need to add it to
00194     //  the right bucket
00195     //
00196     if (newBucket)
00197     {
00198         newBucket->fData = valueToAdopt;
00199         newBucket->fKey = key;
00200     }
00201      else
00202     {
00203         newBucket =
00204             new (fMemoryManager->allocate(sizeof(ValueHashTableBucketElem<TVal>)))
00205             ValueHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
00206         fBucketList[hashVal] = newBucket;
00207         fCount++;
00208     }
00209 }
00210 
00211 
00212 
00213 // ---------------------------------------------------------------------------
00214 //  ValueHashTableOf: Private methods
00215 // ---------------------------------------------------------------------------
00216 template <class TVal, class THasher>
00217 void ValueHashTableOf<TVal, THasher>::rehash()
00218 {
00219     const XMLSize_t newMod = (fHashModulus * 2) + 1;
00220 
00221     ValueHashTableBucketElem<TVal>** newBucketList =
00222         (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate
00223     (
00224         newMod * sizeof(ValueHashTableBucketElem<TVal>*)
00225     );//new RefHashTableBucketElem<TVal>*[newMod];
00226 
00227     // Make sure the new bucket list is destroyed if an
00228     // exception is thrown.
00229     ArrayJanitor<ValueHashTableBucketElem<TVal>*>  guard(newBucketList, fMemoryManager);
00230 
00231     memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
00232 
00233 
00234     // Rehash all existing entries.
00235     for (XMLSize_t index = 0; index < fHashModulus; index++)
00236     {
00237         // Get the bucket list head for this entry
00238         ValueHashTableBucketElem<TVal>* curElem = fBucketList[index];
00239 
00240         while (curElem)
00241         {
00242             // Save the next element before we detach this one
00243             ValueHashTableBucketElem<TVal>* const nextElem = curElem->fNext;
00244 
00245             const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey, newMod);
00246             assert(hashVal < newMod);
00247 
00248             ValueHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal];
00249 
00250             // Insert at the start of this bucket's list.
00251             curElem->fNext = newHeadElem;
00252             newBucketList[hashVal] = curElem;
00253 
00254             curElem = nextElem;
00255         }
00256     }
00257 
00258     ValueHashTableBucketElem<TVal>** const oldBucketList = fBucketList;
00259 
00260     // Everything is OK at this point, so update the
00261     // member variables.
00262     fBucketList = guard.release();
00263     fHashModulus = newMod;
00264 
00265     // Delete the old bucket list.
00266     fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
00267 
00268 }
00269 
00270 template <class TVal, class THasher>
00271 inline ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal, THasher>::
00272 findBucketElem(const void* const key, XMLSize_t& hashVal)
00273 {
00274     // Hash the key
00275     hashVal = fHasher.getHashVal(key, fHashModulus);
00276     assert(hashVal < fHashModulus);
00277 
00278     // Search that bucket for the key
00279     ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00280     while (curElem)
00281     {
00282         if (fHasher.equals(key, curElem->fKey))
00283             return curElem;
00284 
00285         curElem = curElem->fNext;
00286     }
00287     return 0;
00288 }
00289 
00290 template <class TVal, class THasher>
00291 inline const ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal, THasher>::
00292 findBucketElem(const void* const key, XMLSize_t& hashVal) const
00293 {
00294     // Hash the key
00295     hashVal = fHasher.getHashVal(key, fHashModulus);
00296     assert(hashVal < fHashModulus);
00297 
00298     // Search that bucket for the key
00299     const ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00300     while (curElem)
00301     {
00302         if (fHasher.equals(key, curElem->fKey))
00303             return curElem;
00304 
00305         curElem = curElem->fNext;
00306     }
00307     return 0;
00308 }
00309 
00310 
00311 template <class TVal, class THasher>
00312 void ValueHashTableOf<TVal, THasher>::
00313 removeBucketElem(const void* const key, XMLSize_t& hashVal)
00314 {
00315     // Hash the key
00316     hashVal = fHasher.getHashVal(key, fHashModulus);
00317     assert(hashVal < fHashModulus);
00318 
00319     //
00320     //  Search the given bucket for this key. Keep up with the previous
00321     //  element so we can patch around it.
00322     //
00323     ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00324     ValueHashTableBucketElem<TVal>* lastElem = 0;
00325 
00326     while (curElem)
00327     {
00328         if (fHasher.equals(key, curElem->fKey))
00329         {
00330             if (!lastElem)
00331             {
00332                 // It was the first in the bucket
00333                 fBucketList[hashVal] = curElem->fNext;
00334             }
00335              else
00336             {
00337                 // Patch around the current element
00338                 lastElem->fNext = curElem->fNext;
00339             }
00340 
00341             // Delete the current element
00342             // delete curElem;
00343             // destructor is empty...
00344             // curElem->~ValueHashTableBucketElem();
00345             fMemoryManager->deallocate(curElem);
00346 
00347             fCount--;
00348 
00349             return;
00350         }
00351 
00352         // Move both pointers upwards
00353         lastElem = curElem;
00354         curElem = curElem->fNext;
00355     }
00356 
00357     // We never found that key
00358     ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
00359 }
00360 
00361 
00362 
00363 
00364 // ---------------------------------------------------------------------------
00365 //  ValueHashTableOfEnumerator: Constructors and Destructor
00366 // ---------------------------------------------------------------------------
00367 template <class TVal, class THasher>
00368 ValueHashTableOfEnumerator<TVal, THasher>::
00369 ValueHashTableOfEnumerator(ValueHashTableOf<TVal, THasher>* const toEnum
00370                            , const bool adopt
00371                            , MemoryManager* const manager)
00372     : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum), fMemoryManager(manager)
00373 {
00374     if (!toEnum)
00375         ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, manager);
00376 
00377     //
00378     //  Find the next available bucket element in the hash table. If it
00379     //  comes back zero, that just means the table is empty.
00380     //
00381     //  Note that the -1 in the current hash tells it to start from the
00382     //  beginning.
00383     //
00384     findNext();
00385 }
00386 
00387 template <class TVal, class THasher>
00388 ValueHashTableOfEnumerator<TVal, THasher>::~ValueHashTableOfEnumerator()
00389 {
00390     if (fAdopted)
00391         delete fToEnum;
00392 }
00393 
00394 
00395 // ---------------------------------------------------------------------------
00396 //  ValueHashTableOfEnumerator: Enum interface
00397 // ---------------------------------------------------------------------------
00398 template <class TVal, class THasher>
00399 bool ValueHashTableOfEnumerator<TVal, THasher>::hasMoreElements() const
00400 {
00401     //
00402     //  If our current has is at the max and there are no more elements
00403     //  in the current bucket, then no more elements.
00404     //
00405     if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
00406         return false;
00407     return true;
00408 }
00409 
00410 template <class TVal, class THasher>
00411 TVal& ValueHashTableOfEnumerator<TVal, THasher>::nextElement()
00412 {
00413     // Make sure we have an element to return
00414     if (!hasMoreElements())
00415         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
00416 
00417     //
00418     //  Save the current element, then move up to the next one for the
00419     //  next time around.
00420     //
00421     ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
00422     findNext();
00423 
00424     return saveElem->fData;
00425 }
00426 
00427 template <class TVal, class THasher>
00428 void* ValueHashTableOfEnumerator<TVal, THasher>::nextElementKey()
00429 {
00430     // Make sure we have an element to return
00431     if (!hasMoreElements())
00432         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
00433 
00434     //
00435     //  Save the current element, then move up to the next one for the
00436     //  next time around.
00437     //
00438     ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
00439     findNext();
00440 
00441     return saveElem->fKey;
00442 }
00443 
00444 
00445 template <class TVal, class THasher>
00446 void ValueHashTableOfEnumerator<TVal, THasher>::Reset()
00447 {
00448     fCurHash = (XMLSize_t)-1;
00449     fCurElem = 0;
00450     findNext();
00451 }
00452 
00453 
00454 
00455 // ---------------------------------------------------------------------------
00456 //  ValueHashTableOfEnumerator: Private helper methods
00457 // ---------------------------------------------------------------------------
00458 template <class TVal, class THasher>
00459 void ValueHashTableOfEnumerator<TVal, THasher>::findNext()
00460 {
00461     //
00462     //  If there is a current element, move to its next element. If this
00463     //  hits the end of the bucket, the next block will handle the rest.
00464     //
00465     if (fCurElem)
00466         fCurElem = fCurElem->fNext;
00467 
00468     //
00469     //  If the current element is null, then we have to move up to the
00470     //  next hash value. If that is the hash modulus, then we cannot
00471     //  go further.
00472     //
00473     if (!fCurElem)
00474     {
00475         if (++fCurHash == fToEnum->fHashModulus)
00476             return;
00477 
00478         // Else find the next non-empty bucket
00479         while (fToEnum->fBucketList[fCurHash]==0)
00480         {
00481             // Bump to the next hash value. If we max out return
00482             if (++fCurHash == fToEnum->fHashModulus)
00483                 return;
00484         }
00485         fCurElem = fToEnum->fBucketList[fCurHash];
00486     }
00487 }
00488 
00489 XERCES_CPP_NAMESPACE_END