GME  13
RefHash3KeysIdPool.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: RefHash3KeysIdPool.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/RefHash3KeysIdPool.hpp>
00028 #endif
00029 
00030 #include <xercesc/util/NullPointerException.hpp>
00031 #include <assert.h>
00032 #include <new>
00033 
00034 XERCES_CPP_NAMESPACE_BEGIN
00035 
00036 // ---------------------------------------------------------------------------
00037 //  RefHash3KeysIdPool: Constructors and Destructor
00038 // ---------------------------------------------------------------------------
00039 template <class TVal, class THasher>
00040 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
00041   const XMLSize_t modulus,
00042   const XMLSize_t initSize,
00043   MemoryManager* const manager)
00044 
00045     : fMemoryManager(manager)
00046     , fAdoptedElems(true)
00047     , fBucketList(0)
00048     , fHashModulus(modulus)
00049     , fIdPtrs(0)
00050     , fIdPtrsCount(initSize)
00051     , fIdCounter(0)
00052 {
00053     initialize(modulus);
00054 
00055     //  Allocate the initial id pointers array. We don't have to zero them
00056     //  out since the fIdCounter value tells us which ones are valid. The
00057     //  zeroth element is never used (and represents an invalid pool id.)
00058     //
00059     if (!fIdPtrsCount)
00060         fIdPtrsCount = 256;
00061     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
00062     fIdPtrs[0] = 0;
00063 }
00064 
00065 template <class TVal, class THasher>
00066 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
00067   const XMLSize_t modulus,
00068   const THasher& hasher,
00069   const XMLSize_t initSize,
00070   MemoryManager* const manager)
00071 
00072     : fMemoryManager(manager)
00073     , fAdoptedElems(true)
00074     , fBucketList(0)
00075     , fHashModulus(modulus)
00076     , fIdPtrs(0)
00077     , fIdPtrsCount(initSize)
00078     , fIdCounter(0)
00079     , fHasher(hasher)
00080 {
00081     initialize(modulus);
00082 
00083     //  Allocate the initial id pointers array. We don't have to zero them
00084     //  out since the fIdCounter value tells us which ones are valid. The
00085     //  zeroth element is never used (and represents an invalid pool id.)
00086     //
00087     if (!fIdPtrsCount)
00088         fIdPtrsCount = 256;
00089     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
00090     fIdPtrs[0] = 0;
00091 }
00092 
00093 template <class TVal, class THasher>
00094 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
00095   const XMLSize_t modulus,
00096   const bool adoptElems,
00097   const XMLSize_t initSize,
00098   MemoryManager* const manager)
00099 
00100     : fMemoryManager(manager)
00101     , fAdoptedElems(adoptElems)
00102     , fBucketList(0)
00103     , fHashModulus(modulus)
00104     , fIdPtrs(0)
00105     , fIdPtrsCount(initSize)
00106     , fIdCounter(0)
00107 
00108 {
00109     initialize(modulus);
00110 
00111     //  Allocate the initial id pointers array. We don't have to zero them
00112     //  out since the fIdCounter value tells us which ones are valid. The
00113     //  zeroth element is never used (and represents an invalid pool id.)
00114     //
00115     if (!fIdPtrsCount)
00116         fIdPtrsCount = 256;
00117     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
00118     fIdPtrs[0] = 0;
00119 }
00120 
00121 template <class TVal, class THasher>
00122 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
00123   const XMLSize_t modulus,
00124   const bool adoptElems,
00125   const THasher& hasher,
00126   const XMLSize_t initSize,
00127   MemoryManager* const manager)
00128 
00129     : fMemoryManager(manager)
00130     , fAdoptedElems(adoptElems)
00131     , fBucketList(0)
00132     , fHashModulus(modulus)
00133     , fIdPtrs(0)
00134     , fIdPtrsCount(initSize)
00135     , fIdCounter(0)
00136     , fHasher(hasher)
00137 {
00138     initialize(modulus);
00139 
00140     //  Allocate the initial id pointers array. We don't have to zero them
00141     //  out since the fIdCounter value tells us which ones are valid. The
00142     //  zeroth element is never used (and represents an invalid pool id.)
00143     //
00144     if (!fIdPtrsCount)
00145         fIdPtrsCount = 256;
00146     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
00147     fIdPtrs[0] = 0;
00148 }
00149 
00150 template <class TVal, class THasher>
00151 void RefHash3KeysIdPool<TVal, THasher>::initialize(const XMLSize_t modulus)
00152 {
00153     if (modulus == 0)
00154         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
00155 
00156     // Allocate the bucket list and zero them
00157     fBucketList = (RefHash3KeysTableBucketElem<TVal>**) fMemoryManager->allocate
00158     (
00159         fHashModulus * sizeof(RefHash3KeysTableBucketElem<TVal>*)
00160     ); //new RefHash3KeysTableBucketElem<TVal>*[fHashModulus];
00161     memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
00162 }
00163 
00164 template <class TVal, class THasher>
00165 RefHash3KeysIdPool<TVal, THasher>::~RefHash3KeysIdPool()
00166 {
00167     removeAll();
00168 
00169     // Then delete the bucket list & hasher & id pointers list
00170     fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
00171     fIdPtrs = 0;
00172     fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
00173     fBucketList = 0;
00174 }
00175 
00176 
00177 // ---------------------------------------------------------------------------
00178 //  RefHash3KeysIdPool: Element management
00179 // ---------------------------------------------------------------------------
00180 template <class TVal, class THasher>
00181 bool RefHash3KeysIdPool<TVal, THasher>::isEmpty() const
00182 {
00183     // Just check the bucket list for non-empty elements
00184     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
00185     {
00186         if (fBucketList[buckInd] != 0)
00187             return false;
00188     }
00189     return true;
00190 }
00191 
00192 template <class TVal, class THasher>
00193 bool RefHash3KeysIdPool<TVal, THasher>::
00194 containsKey(const void* const key1, const int key2, const int key3) const
00195 {
00196     XMLSize_t hashVal;
00197     const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
00198     return (findIt != 0);
00199 }
00200 
00201 template <class TVal, class THasher>
00202 void RefHash3KeysIdPool<TVal, THasher>::removeAll()
00203 {
00204     if (fIdCounter == 0) return;
00205 
00206     // Clean up the buckets first
00207     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
00208     {
00209         // Get the bucket list head for this entry
00210         RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[buckInd];
00211         RefHash3KeysTableBucketElem<TVal>* nextElem;
00212         while (curElem)
00213         {
00214             // Save the next element before we hose this one
00215             nextElem = curElem->fNext;
00216 
00217             // If we adopted the data, then delete it too
00218             //    (Note:  the userdata hash table instance has data type of void *.
00219             //    This will generate compiler warnings here on some platforms, but they
00220             //    can be ignored since fAdoptedElements is false.
00221             if (fAdoptedElems)
00222                 delete curElem->fData;
00223 
00224             // Then delete the current element and move forward
00225             // delete curElem;
00226             // destructor is empty...
00227             // curElem->~RefHash3KeysTableBucketElem();
00228             fMemoryManager->deallocate(curElem);
00229             curElem = nextElem;
00230         }
00231 
00232         // Clean out this entry
00233         fBucketList[buckInd] = 0;
00234     }
00235 
00236     // Reset the id counter
00237     fIdCounter = 0;
00238 }
00239 
00240 
00241 // ---------------------------------------------------------------------------
00242 //  RefHash3KeysIdPool: Getters
00243 // ---------------------------------------------------------------------------
00244 template <class TVal, class THasher>
00245 TVal*
00246 RefHash3KeysIdPool<TVal, THasher>::getByKey(const void* const key1, const int key2, const int key3)
00247 {
00248     XMLSize_t hashVal;
00249     RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
00250     if (!findIt)
00251         return 0;
00252     return findIt->fData;
00253 }
00254 
00255 template <class TVal, class THasher>
00256 const TVal*
00257 RefHash3KeysIdPool<TVal, THasher>::getByKey(const void* const key1, const int key2, const int key3) const
00258 {
00259     XMLSize_t hashVal;
00260     const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
00261     if (!findIt)
00262         return 0;
00263     return findIt->fData;
00264 }
00265 
00266 template <class TVal, class THasher>
00267 TVal*
00268 RefHash3KeysIdPool<TVal, THasher>::getById(const unsigned int elemId)
00269 {
00270     // If its either zero or beyond our current id, its an error
00271     if (!elemId || (elemId > fIdCounter))
00272         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
00273 
00274     return fIdPtrs[elemId];
00275 }
00276 
00277 template <class TVal, class THasher>
00278 const TVal*
00279 RefHash3KeysIdPool<TVal, THasher>::getById(const unsigned int elemId) const
00280 {
00281     // If its either zero or beyond our current id, its an error
00282     if (!elemId || (elemId > fIdCounter))
00283         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
00284 
00285     return fIdPtrs[elemId];
00286 }
00287 
00288 template <class TVal, class THasher>
00289 MemoryManager* RefHash3KeysIdPool<TVal, THasher>::getMemoryManager() const
00290 {
00291     return fMemoryManager;
00292 }
00293 
00294 template <class TVal, class THasher>
00295 XMLSize_t RefHash3KeysIdPool<TVal, THasher>::getHashModulus() const
00296 {
00297     return fHashModulus;
00298 }
00299 
00300 // ---------------------------------------------------------------------------
00301 //  RefHash3KeysIdPool: Putters
00302 // ---------------------------------------------------------------------------
00303 template <class TVal, class THasher>
00304 XMLSize_t
00305 RefHash3KeysIdPool<TVal, THasher>::put(void* key1, int key2, int key3, TVal* const valueToAdopt)
00306 {
00307     // First see if the key exists already
00308     XMLSize_t hashVal;
00309     XMLSize_t retId;
00310     RefHash3KeysTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, key3, hashVal);
00311 
00312     //
00313     //  If so,then update its value. If not, then we need to add it to
00314     //  the right bucket
00315     //
00316     if (newBucket)
00317     {
00318         retId = newBucket->fData->getId();
00319         if (fAdoptedElems)
00320             delete newBucket->fData;
00321         newBucket->fData = valueToAdopt;
00322         newBucket->fKey1 = key1;
00323         newBucket->fKey2 = key2;
00324         newBucket->fKey3 = key3;
00325     }
00326     else
00327     {
00328     // Revisit: the gcc compiler 2.95.x is generating an
00329     // internal compiler error message. So we use the default
00330     // memory manager for now.
00331 #if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
00332         newBucket = new RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
00333 #else
00334         newBucket =
00335             new (fMemoryManager->allocate(sizeof(RefHash3KeysTableBucketElem<TVal>)))
00336             RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
00337 #endif
00338         fBucketList[hashVal] = newBucket;
00339 
00340         //
00341         //  Give this new one the next available id and add to the pointer list.
00342         //  Expand the list if that is now required.
00343         //
00344         if (fIdCounter + 1 == fIdPtrsCount)
00345         {
00346             // Create a new count 1.5 times larger and allocate a new array
00347             XMLSize_t newCount = (XMLSize_t)(fIdPtrsCount * 1.5);
00348             TVal** newArray = (TVal**) fMemoryManager->allocate
00349             (
00350                 newCount * sizeof(TVal*)
00351             ); //new TVal*[newCount];
00352 
00353             // Copy over the old contents to the new array
00354             memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TVal*));
00355 
00356             // Ok, toss the old array and store the new data
00357             fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
00358             fIdPtrs = newArray;
00359             fIdPtrsCount = newCount;
00360         }
00361         retId = ++fIdCounter;
00362     }
00363 
00364     fIdPtrs[retId] = valueToAdopt;
00365 
00366     // Set the id on the passed element
00367     valueToAdopt->setId(retId);
00368 
00369     // Return the id that we gave to this element
00370     return retId;
00371 }
00372 
00373 // ---------------------------------------------------------------------------
00374 //  RefHash3KeysIdPool: Private methods
00375 // ---------------------------------------------------------------------------
00376 template <class TVal, class THasher>
00377 inline RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal, THasher>::
00378 findBucketElem(const void* const key1, const int key2, const int key3, XMLSize_t& hashVal)
00379 {
00380     // Hash the key
00381     hashVal = fHasher.getHashVal(key1, fHashModulus);
00382     assert(hashVal < fHashModulus);
00383 
00384     // Search that bucket for the key
00385     RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00386     while (curElem)
00387     {
00388         if((key2==curElem->fKey2) && (key3==curElem->fKey3) && (fHasher.equals(key1, curElem->fKey1)))
00389             return curElem;
00390 
00391         curElem = curElem->fNext;
00392     }
00393     return 0;
00394 }
00395 
00396 template <class TVal, class THasher>
00397 inline const RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal, THasher>::
00398 findBucketElem(const void* const key1, const int key2, const int key3, XMLSize_t& hashVal) const
00399 {
00400     // Hash the key
00401     hashVal = fHasher.getHashVal(key1, fHashModulus);
00402     assert(hashVal < fHashModulus);
00403 
00404     // Search that bucket for the key
00405     const RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00406     while (curElem)
00407     {
00408         if((key2==curElem->fKey2) && (key3==curElem->fKey3) && (fHasher.equals(key1, curElem->fKey1)))
00409             return curElem;
00410 
00411         curElem = curElem->fNext;
00412     }
00413     return 0;
00414 }
00415 
00416 
00417 // ---------------------------------------------------------------------------
00418 //  RefHash3KeysIdPoolEnumerator: Constructors and Destructor
00419 // ---------------------------------------------------------------------------
00420 template <class TVal, class THasher>
00421 RefHash3KeysIdPoolEnumerator<TVal, THasher>::
00422 RefHash3KeysIdPoolEnumerator(RefHash3KeysIdPool<TVal, THasher>* const toEnum
00423                              , const bool adopt
00424                              , MemoryManager* const manager)
00425     : fAdoptedElems(adopt), fCurIndex(0), fToEnum(toEnum), fMemoryManager(manager)
00426 {
00427     if (!toEnum)
00428         ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
00429 
00430     Reset();
00431     resetKey();
00432 }
00433 
00434 template <class TVal, class THasher>
00435 RefHash3KeysIdPoolEnumerator<TVal, THasher>::~RefHash3KeysIdPoolEnumerator()
00436 {
00437     if (fAdoptedElems)
00438         delete fToEnum;
00439 }
00440 
00441 template <class TVal, class THasher>
00442 RefHash3KeysIdPoolEnumerator<TVal, THasher>::
00443 RefHash3KeysIdPoolEnumerator(const RefHash3KeysIdPoolEnumerator<TVal, THasher>& toCopy) :
00444     XMLEnumerator<TVal>(toCopy)
00445     , XMemory(toCopy)
00446     , fAdoptedElems(toCopy.fAdoptedElems)
00447     , fCurIndex(toCopy.fCurIndex)
00448     , fToEnum(toCopy.fToEnum)
00449     , fCurElem(toCopy.fCurElem)
00450     , fCurHash(toCopy.fCurHash)
00451     , fMemoryManager(toCopy.fMemoryManager)
00452 {
00453 }
00454 
00455 // ---------------------------------------------------------------------------
00456 //  RefHash3KeysIdPoolEnumerator: Enum interface
00457 // ---------------------------------------------------------------------------
00458 template <class TVal, class THasher>
00459 bool RefHash3KeysIdPoolEnumerator<TVal, THasher>::hasMoreElements() const
00460 {
00461     // If our index is zero or past the end, then we are done
00462     if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
00463         return false;
00464     return true;
00465 }
00466 
00467 template <class TVal, class THasher>
00468 TVal& RefHash3KeysIdPoolEnumerator<TVal, THasher>::nextElement()
00469 {
00470     // If our index is zero or past the end, then we are done
00471     if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
00472         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
00473 
00474     // Return the current element and bump the index
00475     return *fToEnum->fIdPtrs[fCurIndex++];
00476 }
00477 
00478 template <class TVal, class THasher>
00479 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::Reset()
00480 {
00481     //
00482     //  Find the next available bucket element in the pool. We use the id
00483     //  array since its very easy to enumerator through by just maintaining
00484     //  an index. If the id counter is zero, then its empty and we leave the
00485     //  current index to zero.
00486     //
00487     fCurIndex = fToEnum->fIdCounter ? 1:0;
00488 
00489 }
00490 
00491 template <class TVal, class THasher>
00492 XMLSize_t RefHash3KeysIdPoolEnumerator<TVal, THasher>::size() const
00493 {
00494     return fToEnum->fIdCounter;
00495 }
00496 
00497 template <class TVal, class THasher>
00498 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::resetKey()
00499 {
00500     fCurHash = (XMLSize_t)-1;
00501     fCurElem = 0;
00502     findNext();
00503 }
00504 
00505 template <class TVal, class THasher>
00506 bool RefHash3KeysIdPoolEnumerator<TVal, THasher>::hasMoreKeys() const
00507 {
00508     //
00509     //  If our current has is at the max and there are no more elements
00510     //  in the current bucket, then no more elements.
00511     //
00512     if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
00513         return false;
00514 
00515     return true;
00516 }
00517 
00518 template <class TVal, class THasher>
00519 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::nextElementKey(void*& retKey1, int& retKey2, int& retKey3)
00520 {
00521     // Make sure we have an element to return
00522     if (!hasMoreKeys())
00523         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
00524 
00525     //
00526     //  Save the current element, then move up to the next one for the
00527     //  next time around.
00528     //
00529     RefHash3KeysTableBucketElem<TVal>* saveElem = fCurElem;
00530     findNext();
00531 
00532     retKey1 = saveElem->fKey1;
00533     retKey2 = saveElem->fKey2;
00534     retKey3 = saveElem->fKey3;
00535 
00536     return;
00537 }
00538 
00539 template <class TVal, class THasher>
00540 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::findNext()
00541 {
00542     //
00543     //  If there is a current element, move to its next element. If this
00544     //  hits the end of the bucket, the next block will handle the rest.
00545     //
00546     if (fCurElem)
00547         fCurElem = fCurElem->fNext;
00548 
00549     //
00550     //  If the current element is null, then we have to move up to the
00551     //  next hash value. If that is the hash modulus, then we cannot
00552     //  go further.
00553     //
00554     if (!fCurElem)
00555     {
00556         fCurHash++;
00557         if (fCurHash == fToEnum->fHashModulus)
00558             return;
00559 
00560         // Else find the next non-empty bucket
00561         while (fToEnum->fBucketList[fCurHash]==0)
00562         {
00563             // Bump to the next hash value. If we max out return
00564             fCurHash++;
00565             if (fCurHash == fToEnum->fHashModulus)
00566                 return;
00567         }
00568         fCurElem = fToEnum->fBucketList[fCurHash];
00569     }
00570 }
00571 
00572 XERCES_CPP_NAMESPACE_END