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