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: 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