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