GME  13
RefHashTableOf.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: RefHashTableOf.c 678409 2008-07-21 13:08:10Z borisk $
00020  */
00021 
00022 
00023 // ---------------------------------------------------------------------------
00024 //  Include
00025 // ---------------------------------------------------------------------------
00026 #if defined(XERCES_TMPLSINC)
00027 #include <xercesc/util/RefHashTableOf.hpp>
00028 #endif
00029 
00030 #include <xercesc/util/Janitor.hpp>
00031 #include <xercesc/util/XMLString.hpp>
00032 #include <xercesc/util/NullPointerException.hpp>
00033 #include <new>
00034 
00035 XERCES_CPP_NAMESPACE_BEGIN
00036 
00037 // ---------------------------------------------------------------------------
00038 //  RefHashTableOf: Constructors and Destructor
00039 // ---------------------------------------------------------------------------
00040 template <class TVal, class THasher>
00041 RefHashTableOf<TVal, THasher>::RefHashTableOf(
00042   const XMLSize_t modulus,
00043   MemoryManager* const manager)
00044 
00045     : fMemoryManager(manager)
00046     , fAdoptedElems(true)
00047     , fBucketList(0)
00048     , fHashModulus(modulus)
00049     , fInitialModulus(modulus)
00050     , fCount(0)
00051 {
00052     initialize(modulus);
00053 }
00054 
00055 template <class TVal, class THasher>
00056 RefHashTableOf<TVal, THasher>::RefHashTableOf(
00057   const XMLSize_t modulus,
00058   const THasher& hasher,
00059   MemoryManager* const manager)
00060 
00061     : fMemoryManager(manager)
00062     , fAdoptedElems(true)
00063     , fBucketList(0)
00064     , fHashModulus(modulus)
00065     , fInitialModulus(modulus)
00066     , fCount(0)
00067     , fHasher (hasher)
00068 {
00069     initialize(modulus);
00070 }
00071 
00072 template <class TVal, class THasher>
00073 RefHashTableOf<TVal, THasher>::RefHashTableOf(
00074   const XMLSize_t modulus,
00075   const bool adoptElems,
00076   MemoryManager* const manager)
00077 
00078     : fMemoryManager(manager)
00079     , fAdoptedElems(adoptElems)
00080     , fBucketList(0)
00081     , fHashModulus(modulus)
00082     , fInitialModulus(modulus)
00083     , fCount(0)
00084 
00085 {
00086     initialize(modulus);
00087 }
00088 
00089 template <class TVal, class THasher>
00090 RefHashTableOf<TVal, THasher>::RefHashTableOf(
00091   const XMLSize_t modulus,
00092   const bool adoptElems,
00093   const THasher& hasher,
00094   MemoryManager* const manager)
00095 
00096     : fMemoryManager(manager)
00097     , fAdoptedElems(adoptElems)
00098     , fBucketList(0)
00099     , fHashModulus(modulus)
00100     , fInitialModulus(modulus)
00101     , fCount(0)
00102     , fHasher (hasher)
00103 {
00104     initialize(modulus);
00105 }
00106 
00107 template <class TVal, class THasher>
00108 void RefHashTableOf<TVal, THasher>::initialize(const XMLSize_t modulus)
00109 {
00110     if (modulus == 0)
00111         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
00112 
00113     // Allocate the bucket list and zero them
00114     fBucketList = (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate
00115     (
00116         fHashModulus * sizeof(RefHashTableBucketElem<TVal>*)
00117     );
00118     for (XMLSize_t index = 0; index < fHashModulus; index++)
00119         fBucketList[index] = 0;
00120 }
00121 
00122 template <class TVal, class THasher>
00123 RefHashTableOf<TVal, THasher>::~RefHashTableOf()
00124 {
00125     cleanup();
00126 }
00127 
00128 
00129 // ---------------------------------------------------------------------------
00130 //  RefHashTableOf: Element management
00131 // ---------------------------------------------------------------------------
00132 template <class TVal, class THasher>
00133 inline bool RefHashTableOf<TVal, THasher>::isEmpty() const
00134 {
00135     return fCount==0;
00136 }
00137 
00138 template <class TVal, class THasher>
00139 inline bool RefHashTableOf<TVal, THasher>::containsKey(const void* const key) const
00140 {
00141     XMLSize_t hashVal;
00142     const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
00143     return (findIt != 0);
00144 }
00145 
00146 template <class TVal, class THasher>
00147 void RefHashTableOf<TVal, THasher>::
00148 removeKey(const void* const key)
00149 {
00150     // Hash the key
00151     XMLSize_t hashVal = fHasher.getHashVal(key, fHashModulus);
00152 
00153     //
00154     //  Search the given bucket for this key. Keep up with the previous
00155     //  element so we can patch around it.
00156     //
00157     RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00158     RefHashTableBucketElem<TVal>* lastElem = 0;
00159 
00160     while (curElem)
00161     {
00162         if (fHasher.equals(key, curElem->fKey))
00163         {
00164             if (!lastElem)
00165             {
00166                 // It was the first in the bucket
00167                 fBucketList[hashVal] = curElem->fNext;
00168             }
00169              else
00170             {
00171                 // Patch around the current element
00172                 lastElem->fNext = curElem->fNext;
00173             }
00174 
00175             // If we adopted the data, then delete it too
00176             //    (Note:  the userdata hash table instance has data type of void *.
00177             //    This will generate compiler warnings here on some platforms, but they
00178             //    can be ignored since fAdoptedElements is false.
00179             if (fAdoptedElems)
00180                 delete curElem->fData;
00181 
00182             // Then delete the current element and move forward
00183             // delete curElem;
00184             // destructor doesn't do anything...
00185             fMemoryManager->deallocate(curElem);
00186 
00187             fCount--;
00188 
00189             return;
00190         }
00191 
00192         // Move both pointers upwards
00193         lastElem = curElem;
00194         curElem = curElem->fNext;
00195     }
00196 
00197     // We never found that key
00198     ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
00199 }
00200 
00201 template <class TVal, class THasher>
00202 void RefHashTableOf<TVal, THasher>::removeAll()
00203 {
00204     if(isEmpty())
00205         return;
00206 
00207     // Clean up the buckets first
00208     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
00209     {
00210         // Get the bucket list head for this entry
00211         RefHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
00212         RefHashTableBucketElem<TVal>* nextElem;
00213         while (curElem)
00214         {
00215             // Save the next element before we hose this one
00216             nextElem = curElem->fNext;
00217 
00218             // If we adopted the data, then delete it too
00219             //    (Note:  the userdata hash table instance has data type of void *.
00220             //    This will generate compiler warnings here on some platforms, but they
00221             //    can be ignored since fAdoptedElements is false.
00222             if (fAdoptedElems)
00223                 delete curElem->fData;
00224 
00225             // Then delete the current element and move forward
00226              // delete curElem;
00227             // destructor doesn't do anything...
00228             // curElem->~RefHashTableBucketElem();
00229             fMemoryManager->deallocate(curElem);
00230             curElem = nextElem;
00231         }
00232 
00233         // Clean out this entry
00234         fBucketList[buckInd] = 0;
00235     }
00236 
00237     fCount = 0;
00238 }
00239 
00240 // This method returns the data associated with a key. The key entry is deleted. The caller
00241 // now owns the returned data (case of hashtable adopting the data).
00242 // This function is called by transferElement so that the undeleted data can be transferred
00243 // to a new key which will own that data.
00244 template <class TVal, class THasher> TVal* RefHashTableOf<TVal, THasher>::
00245 orphanKey(const void* const key)
00246 {
00247     // Hash the key
00248     TVal* retVal = 0;
00249     XMLSize_t hashVal = fHasher.getHashVal(key, fHashModulus);
00250 
00251     //
00252     //  Search the given bucket for this key. Keep up with the previous
00253     //  element so we can patch around it.
00254     //
00255     RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00256     RefHashTableBucketElem<TVal>* lastElem = 0;
00257 
00258     while (curElem)
00259     {
00260         if (fHasher.equals(key, curElem->fKey))
00261         {
00262             if (!lastElem)
00263             {
00264                 // It was the first in the bucket
00265                 fBucketList[hashVal] = curElem->fNext;
00266             }
00267             else
00268             {
00269                 // Patch around the current element
00270                 lastElem->fNext = curElem->fNext;
00271             }
00272 
00273             retVal = curElem->fData;
00274 
00275             // Delete the current element
00276             // delete curElem;
00277             // destructor doesn't do anything...
00278             // curElem->~RefHashTableBucketElem();
00279             fMemoryManager->deallocate(curElem);
00280             break;
00281         }
00282 
00283         // Move both pointers upwards
00284         lastElem = curElem;
00285         curElem = curElem->fNext;
00286     }
00287 
00288     // We never found that key
00289     if (!retVal)
00290         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
00291 
00292     return retVal;
00293 }
00294 
00295 //
00296 // cleanup():
00297 //   similar to destructor
00298 //   called to cleanup the memory, in case destructor cannot be called
00299 //
00300 template <class TVal, class THasher>
00301 void RefHashTableOf<TVal, THasher>::cleanup()
00302 {
00303     removeAll();
00304 
00305     // Then delete the bucket list & hasher
00306     fMemoryManager->deallocate(fBucketList);
00307     fBucketList = 0;
00308 }
00309 
00310 //
00311 // reinitialize():
00312 //   similar to constructor
00313 //   called to re-construct the fElemList from scratch again
00314 //
00315 template <class TVal, class THasher>
00316 void RefHashTableOf<TVal, THasher>::reinitialize(const THasher& hasher)
00317 {
00318     if (fBucketList)
00319         cleanup();
00320 
00321     fHasher = hasher;
00322 
00323     fHashModulus = fInitialModulus;
00324     initialize(fHashModulus);
00325 }
00326 
00327 
00328 
00329 // this function transfer the data from key1 to key2
00330 // this is equivalent to calling
00331 //  1.  get(key1) to retrieve the data,
00332 //  2.  removeKey(key1),
00333 //  3.  and then put(key2, data)
00334 // except that the data is not deleted in "removeKey" even it is adopted so that it
00335 // can be transferred to key2.
00336 // whatever key2 has originally will be purged (if adopted)
00337 template <class TVal, class THasher>
00338 inline void RefHashTableOf<TVal, THasher>::transferElement(const void* const key1, void* key2)
00339 {
00340     put(key2, orphanKey(key1));
00341 }
00342 
00343 
00344 // ---------------------------------------------------------------------------
00345 //  RefHashTableOf: Getters
00346 // ---------------------------------------------------------------------------
00347 template <class TVal, class THasher>
00348 inline TVal* RefHashTableOf<TVal, THasher>::get(const void* const key)
00349 {
00350     XMLSize_t hashVal;
00351     RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
00352     return findIt ? findIt->fData : 0;
00353 }
00354 
00355 template <class TVal, class THasher>
00356 inline const TVal* RefHashTableOf<TVal, THasher>::
00357 get(const void* const key) const
00358 {
00359     XMLSize_t hashVal;
00360     const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
00361     return findIt ? findIt->fData : 0;
00362 }
00363 
00364 template <class TVal, class THasher>
00365 inline MemoryManager* RefHashTableOf<TVal, THasher>::getMemoryManager() const
00366 {
00367     return fMemoryManager;
00368 }
00369 
00370 template <class TVal, class THasher>
00371 inline XMLSize_t RefHashTableOf<TVal, THasher>::getHashModulus() const
00372 {
00373     return fHashModulus;
00374 }
00375 
00376 template <class TVal, class THasher>
00377 inline XMLSize_t RefHashTableOf<TVal, THasher>::getCount() const
00378 {
00379     return fCount;
00380 }
00381 
00382 // ---------------------------------------------------------------------------
00383 //  RefHashTableOf: Getters
00384 // ---------------------------------------------------------------------------
00385 template <class TVal, class THasher>
00386 inline void RefHashTableOf<TVal, THasher>::setAdoptElements(const bool aValue)
00387 {
00388     fAdoptedElems = aValue;
00389 }
00390 
00391 // ---------------------------------------------------------------------------
00392 //  RefHashTableOf: Putters
00393 // ---------------------------------------------------------------------------
00394 template <class TVal, class THasher>
00395 void RefHashTableOf<TVal, THasher>::put(void* key, TVal* const valueToAdopt)
00396 {
00397     // Apply 0.75 load factor to find threshold.
00398     XMLSize_t threshold = fHashModulus * 3 / 4;
00399 
00400     // If we've grown too big, expand the table and rehash.
00401     if (fCount >= threshold)
00402         rehash();
00403 
00404     // First see if the key exists already
00405     XMLSize_t hashVal;
00406     RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
00407 
00408     //
00409     //  If so,then update its value. If not, then we need to add it to
00410     //  the right bucket
00411     //
00412     if (newBucket)
00413     {
00414         if (fAdoptedElems)
00415             delete newBucket->fData;
00416         newBucket->fData = valueToAdopt;
00417         newBucket->fKey = key;
00418     }
00419     else
00420     {
00421         newBucket =
00422              new (fMemoryManager->allocate(sizeof(RefHashTableBucketElem<TVal>)))
00423              RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
00424         fBucketList[hashVal] = newBucket;
00425         fCount++;
00426     }
00427 }
00428 
00429 
00430 
00431 // ---------------------------------------------------------------------------
00432 //  RefHashTableOf: Private methods
00433 // ---------------------------------------------------------------------------
00434 template <class TVal, class THasher>
00435 void RefHashTableOf<TVal, THasher>::rehash()
00436 {
00437     const XMLSize_t newMod = (fHashModulus * 2) + 1;
00438 
00439     RefHashTableBucketElem<TVal>** newBucketList =
00440         (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate
00441     (
00442         newMod * sizeof(RefHashTableBucketElem<TVal>*)
00443     );
00444 
00445     // Make sure the new bucket list is destroyed if an
00446     // exception is thrown.
00447     ArrayJanitor<RefHashTableBucketElem<TVal>*>  guard(newBucketList, fMemoryManager);
00448 
00449     memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
00450 
00451 
00452     // Rehash all existing entries.
00453     for (XMLSize_t index = 0; index < fHashModulus; index++)
00454     {
00455         // Get the bucket list head for this entry
00456         RefHashTableBucketElem<TVal>* curElem = fBucketList[index];
00457 
00458         while (curElem)
00459         {
00460             // Save the next element before we detach this one
00461             RefHashTableBucketElem<TVal>* const nextElem = curElem->fNext;
00462 
00463             const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey, newMod);
00464 
00465             RefHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal];
00466 
00467             // Insert at the start of this bucket's list.
00468             curElem->fNext = newHeadElem;
00469             newBucketList[hashVal] = curElem;
00470 
00471             curElem = nextElem;
00472         }
00473     }
00474 
00475     RefHashTableBucketElem<TVal>** const oldBucketList = fBucketList;
00476 
00477     // Everything is OK at this point, so update the
00478     // member variables.
00479     fBucketList = guard.release();
00480     fHashModulus = newMod;
00481 
00482     // Delete the old bucket list.
00483     fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
00484 
00485 }
00486 
00487 template <class TVal, class THasher>
00488 inline RefHashTableBucketElem<TVal>* RefHashTableOf<TVal, THasher>::
00489 findBucketElem(const void* const key, XMLSize_t& hashVal)
00490 {
00491     // Hash the key
00492     hashVal = fHasher.getHashVal(key, fHashModulus);
00493 
00494     // Search that bucket for the key
00495     RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00496     while (curElem)
00497     {
00498         if (fHasher.equals(key, curElem->fKey))
00499             return curElem;
00500 
00501         curElem = curElem->fNext;
00502     }
00503     return 0;
00504 }
00505 
00506 template <class TVal, class THasher>
00507 inline const RefHashTableBucketElem<TVal>* RefHashTableOf<TVal, THasher>::
00508 findBucketElem(const void* const key, XMLSize_t& hashVal) const
00509 {
00510     // Hash the key
00511     hashVal = fHasher.getHashVal(key, fHashModulus);
00512 
00513     // Search that bucket for the key
00514     const RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00515     while (curElem)
00516     {
00517         if (fHasher.equals(key, curElem->fKey))
00518             return curElem;
00519 
00520         curElem = curElem->fNext;
00521     }
00522     return 0;
00523 }
00524 
00525 
00526 // ---------------------------------------------------------------------------
00527 //  RefHashTableOfEnumerator: Constructors and Destructor
00528 // ---------------------------------------------------------------------------
00529 template <class TVal, class THasher> RefHashTableOfEnumerator<TVal, THasher>::
00530 RefHashTableOfEnumerator(RefHashTableOf<TVal, THasher>* const toEnum
00531                          , const bool adopt
00532                          , MemoryManager* const manager)
00533     : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum)
00534     , fMemoryManager(manager)
00535 {
00536     if (!toEnum)
00537         ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
00538 
00539     //
00540     //  Find the next available bucket element in the hash table. If it
00541     //  comes back zero, that just means the table is empty.
00542     //
00543     //  Note that the -1 in the current hash tells it to start
00544     //  from the beginning.
00545     //
00546     findNext();
00547 }
00548 
00549 template <class TVal, class THasher>
00550 RefHashTableOfEnumerator<TVal, THasher>::~RefHashTableOfEnumerator()
00551 {
00552     if (fAdopted)
00553         delete fToEnum;
00554 }
00555 
00556 
00557 template <class TVal, class THasher> RefHashTableOfEnumerator<TVal, THasher>::
00558 RefHashTableOfEnumerator(const RefHashTableOfEnumerator<TVal, THasher>& toCopy) :
00559     XMLEnumerator<TVal>(toCopy)
00560     , XMemory(toCopy)
00561     , fAdopted(toCopy.fAdopted)
00562     , fCurElem(toCopy.fCurElem)
00563     , fCurHash(toCopy.fCurHash)
00564     , fToEnum(toCopy.fToEnum)
00565     , fMemoryManager(toCopy.fMemoryManager)
00566 {
00567 }
00568 // ---------------------------------------------------------------------------
00569 //  RefHashTableOfEnumerator: Enum interface
00570 // ---------------------------------------------------------------------------
00571 template <class TVal, class THasher>
00572 bool RefHashTableOfEnumerator<TVal, THasher>::hasMoreElements() const
00573 {
00574     //
00575     //  If our current has is at the max and there are no more elements
00576     //  in the current bucket, then no more elements.
00577     //
00578     if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
00579         return false;
00580     return true;
00581 }
00582 
00583 template <class TVal, class THasher>
00584 TVal& RefHashTableOfEnumerator<TVal, THasher>::nextElement()
00585 {
00586     // Make sure we have an element to return
00587     if (!hasMoreElements())
00588         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
00589 
00590     //
00591     //  Save the current element, then move up to the next one for the
00592     //  next time around.
00593     //
00594     RefHashTableBucketElem<TVal>* saveElem = fCurElem;
00595     findNext();
00596 
00597     return *saveElem->fData;
00598 }
00599 
00600 template <class TVal, class THasher>
00601 void* RefHashTableOfEnumerator<TVal, THasher>::nextElementKey()
00602 {
00603     // Make sure we have an element to return
00604     if (!hasMoreElements())
00605         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
00606 
00607     //
00608     //  Save the current element, then move up to the next one for the
00609     //  next time around.
00610     //
00611     RefHashTableBucketElem<TVal>* saveElem = fCurElem;
00612     findNext();
00613 
00614     return saveElem->fKey;
00615 }
00616 
00617 template <class TVal, class THasher>
00618 void RefHashTableOfEnumerator<TVal, THasher>::Reset()
00619 {
00620     fCurHash = (XMLSize_t)-1;
00621     fCurElem = 0;
00622     findNext();
00623 }
00624 
00625 
00626 
00627 // ---------------------------------------------------------------------------
00628 //  RefHashTableOfEnumerator: Private helper methods
00629 // ---------------------------------------------------------------------------
00630 template <class TVal, class THasher>
00631 void RefHashTableOfEnumerator<TVal, THasher>::findNext()
00632 {
00633     //
00634     //  If there is a current element, move to its next element. If this
00635     //  hits the end of the bucket, the next block will handle the rest.
00636     //
00637     if (fCurElem)
00638         fCurElem = fCurElem->fNext;
00639 
00640     //
00641     //  If the current element is null, then we have to move up to the
00642     //  next hash value. If that is the hash modulus, then we cannot
00643     //  go further.
00644     //
00645     if (!fCurElem)
00646     {
00647         fCurHash++;
00648         if (fCurHash == fToEnum->fHashModulus)
00649             return;
00650 
00651         // Else find the next non-empty bucket
00652         while (fToEnum->fBucketList[fCurHash]==0)
00653         {
00654             // Bump to the next hash value. If we max out return
00655             fCurHash++;
00656             if (fCurHash == fToEnum->fHashModulus)
00657                 return;
00658         }
00659         fCurElem = fToEnum->fBucketList[fCurHash];
00660     }
00661 }
00662 
00663 XERCES_CPP_NAMESPACE_END