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