GME
13
|
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