/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /* * $Id: RefHashTableOf.c 568078 2007-08-21 11:43:25Z amassari $ */ // --------------------------------------------------------------------------- // Include // --------------------------------------------------------------------------- #if defined(XERCES_TMPLSINC) #include #endif #include #include #include #include XERCES_CPP_NAMESPACE_BEGIN // --------------------------------------------------------------------------- // RefHashTableOf: Constructors and Destructor // --------------------------------------------------------------------------- template RefHashTableOf::RefHashTableOf( const unsigned int modulus , const bool adoptElems , MemoryManager* const manager) : fMemoryManager(manager) , fAdoptedElems(adoptElems) , fBucketList(0) , fHashModulus(modulus) , fInitialModulus(modulus) , fCount(0) , fHash(0) { initialize(modulus); // create default hasher fHash = new (fMemoryManager) HashXMLCh(); } template RefHashTableOf::RefHashTableOf( const unsigned int modulus , const bool adoptElems , HashBase* hashBase , MemoryManager* const manager) : fMemoryManager(manager) , fAdoptedElems(adoptElems) , fBucketList(0) , fHashModulus(modulus) , fInitialModulus(modulus) , fCount(0) , fHash(0) { initialize(modulus); // set hasher fHash = hashBase; } template RefHashTableOf::RefHashTableOf(const unsigned int modulus , MemoryManager* const manager) : fMemoryManager(manager) , fAdoptedElems(true) , fBucketList(0) , fHashModulus(modulus) , fInitialModulus(modulus) , fCount(0) , fHash(0) { initialize(modulus); // create default hasher fHash = new (fMemoryManager) HashXMLCh(); } template void RefHashTableOf::initialize(const unsigned int modulus) { if (modulus == 0) ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager); // Allocate the bucket list and zero them fBucketList = (RefHashTableBucketElem**) fMemoryManager->allocate ( fHashModulus * sizeof(RefHashTableBucketElem*) ); //new RefHashTableBucketElem*[fHashModulus]; for (unsigned int index = 0; index < fHashModulus; index++) fBucketList[index] = 0; } template RefHashTableOf::~RefHashTableOf() { cleanup(); } // --------------------------------------------------------------------------- // RefHashTableOf: Element management // --------------------------------------------------------------------------- template bool RefHashTableOf::isEmpty() const { return fCount==0; } template bool RefHashTableOf:: containsKey(const void* const key) const { unsigned int hashVal; const RefHashTableBucketElem* findIt = findBucketElem(key, hashVal); return (findIt != 0); } template void RefHashTableOf:: removeKey(const void* const key) { // Hash the key unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); assert(hashVal < fHashModulus); // // Search the given bucket for this key. Keep up with the previous // element so we can patch around it. // RefHashTableBucketElem* curElem = fBucketList[hashVal]; RefHashTableBucketElem* lastElem = 0; while (curElem) { if (fHash->equals(key, curElem->fKey)) { if (!lastElem) { // It was the first in the bucket fBucketList[hashVal] = curElem->fNext; } else { // Patch around the current element lastElem->fNext = curElem->fNext; } // If we adopted the data, then delete it too // (Note: the userdata hash table instance has data type of void *. // This will generate compiler warnings here on some platforms, but they // can be ignored since fAdoptedElements is false. if (fAdoptedElems) delete curElem->fData; // Then delete the current element and move forward // delete curElem; // destructor doesn't do anything... // curElem->~RefHashTableBucketElem(); fMemoryManager->deallocate(curElem); fCount--; return; } // Move both pointers upwards lastElem = curElem; curElem = curElem->fNext; } // We never found that key ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); } template void RefHashTableOf::removeAll() { if(isEmpty()) return; // Clean up the buckets first for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) { // Get the bucket list head for this entry RefHashTableBucketElem* curElem = fBucketList[buckInd]; RefHashTableBucketElem* nextElem; while (curElem) { // Save the next element before we hose this one nextElem = curElem->fNext; // If we adopted the data, then delete it too // (Note: the userdata hash table instance has data type of void *. // This will generate compiler warnings here on some platforms, but they // can be ignored since fAdoptedElements is false. if (fAdoptedElems) delete curElem->fData; // Then delete the current element and move forward // delete curElem; // destructor doesn't do anything... // curElem->~RefHashTableBucketElem(); fMemoryManager->deallocate(curElem); curElem = nextElem; } // Clean out this entry fBucketList[buckInd] = 0; } fCount = 0; } // This method returns the data associated with a key. The key entry is deleted. The caller // now owns the returned data (case of hashtable adopting the data). // This function is called by transferElement so that the undeleted data can be transferred // to a new key which will own that data. template TVal* RefHashTableOf:: orphanKey(const void* const key) { // Hash the key TVal* retVal = 0; unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); assert(hashVal < fHashModulus); // // Search the given bucket for this key. Keep up with the previous // element so we can patch around it. // RefHashTableBucketElem* curElem = fBucketList[hashVal]; RefHashTableBucketElem* lastElem = 0; while (curElem) { if (fHash->equals(key, curElem->fKey)) { if (!lastElem) { // It was the first in the bucket fBucketList[hashVal] = curElem->fNext; } else { // Patch around the current element lastElem->fNext = curElem->fNext; } retVal = curElem->fData; // Delete the current element // delete curElem; // destructor doesn't do anything... // curElem->~RefHashTableBucketElem(); fMemoryManager->deallocate(curElem); break; } // Move both pointers upwards lastElem = curElem; curElem = curElem->fNext; } // We never found that key if (!retVal) ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); return retVal; } // // cleanup(): // similar to destructor // called to cleanup the memory, in case destructor cannot be called // template void RefHashTableOf::cleanup() { removeAll(); // Then delete the bucket list & hasher fMemoryManager->deallocate(fBucketList); //delete [] fBucketList; fBucketList = 0; delete fHash; } // // reinitialize(): // similar to constructor // called to re-construct the fElemList from scratch again // template void RefHashTableOf::reinitialize(HashBase* hashBase) { if (fBucketList || fHash) cleanup(); fHashModulus = fInitialModulus; initialize(fHashModulus); if (hashBase) fHash = hashBase; else fHash = new (fMemoryManager) HashXMLCh(); // create default hasher } // this function transfer the data from key1 to key2 // this is equivalent to calling // 1. get(key1) to retrieve the data, // 2. removeKey(key1), // 3. and then put(key2, data) // except that the data is not deleted in "removeKey" even it is adopted so that it // can be transferred to key2. // whatever key2 has originally will be purged (if adopted) template void RefHashTableOf::transferElement(const void* const key1, void* key2) { put(key2, orphanKey(key1)); } // --------------------------------------------------------------------------- // RefHashTableOf: Getters // --------------------------------------------------------------------------- template TVal* RefHashTableOf::get(const void* const key) { unsigned int hashVal; RefHashTableBucketElem* findIt = findBucketElem(key, hashVal); if (!findIt) return 0; return findIt->fData; } template const TVal* RefHashTableOf:: get(const void* const key) const { unsigned int hashVal; const RefHashTableBucketElem* findIt = findBucketElem(key, hashVal); if (!findIt) return 0; return findIt->fData; } template MemoryManager* RefHashTableOf::getMemoryManager() const { return fMemoryManager; } template unsigned int RefHashTableOf::getHashModulus() const { return fHashModulus; } template unsigned int RefHashTableOf::getCount() const { return fCount; } // --------------------------------------------------------------------------- // RefHashTableOf: Getters // --------------------------------------------------------------------------- template void RefHashTableOf::setAdoptElements(const bool aValue) { fAdoptedElems = aValue; } // --------------------------------------------------------------------------- // RefHashTableOf: Putters // --------------------------------------------------------------------------- template void RefHashTableOf::put(void* key, TVal* const valueToAdopt) { // Apply 0.75 load factor to find threshold. unsigned int threshold = fHashModulus * 3 / 4; // If we've grown too big, expand the table and rehash. if (fCount >= threshold) rehash(); // First see if the key exists already unsigned int hashVal; RefHashTableBucketElem* newBucket = findBucketElem(key, hashVal); // // If so,then update its value. If not, then we need to add it to // the right bucket // if (newBucket) { if (fAdoptedElems) delete newBucket->fData; newBucket->fData = valueToAdopt; newBucket->fKey = key; } else { //newBucket = new (fMemoryManager) RefHashTableBucketElem(key, valueToAdopt, fBucketList[hashVal]); newBucket = new (fMemoryManager->allocate(sizeof(RefHashTableBucketElem))) RefHashTableBucketElem(key, valueToAdopt, fBucketList[hashVal]); fBucketList[hashVal] = newBucket; fCount++; } } // --------------------------------------------------------------------------- // RefHashTableOf: Private methods // --------------------------------------------------------------------------- template void RefHashTableOf::rehash() { const unsigned int newMod = fHashModulus * 2; RefHashTableBucketElem** newBucketList = (RefHashTableBucketElem**) fMemoryManager->allocate ( newMod * sizeof(RefHashTableBucketElem*) );//new RefHashTableBucketElem*[newMod]; // Make sure the new bucket list is destroyed if an // exception is thrown. ArrayJanitor*> guard(newBucketList, fMemoryManager); memset(newBucketList, 0, newMod * sizeof(newBucketList[0])); // Rehash all existing entries. for (unsigned int index = 0; index < fHashModulus; index++) { // Get the bucket list head for this entry RefHashTableBucketElem* curElem = fBucketList[index]; while (curElem) { // Save the next element before we detach this one RefHashTableBucketElem* const nextElem = curElem->fNext; const unsigned int hashVal = fHash->getHashVal(curElem->fKey, newMod, fMemoryManager); assert(hashVal < newMod); RefHashTableBucketElem* const newHeadElem = newBucketList[hashVal]; // Insert at the start of this bucket's list. curElem->fNext = newHeadElem; newBucketList[hashVal] = curElem; curElem = nextElem; } } RefHashTableBucketElem** const oldBucketList = fBucketList; // Everything is OK at this point, so update the // member variables. fBucketList = guard.release(); fHashModulus = newMod; // Delete the old bucket list. fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList; } template RefHashTableBucketElem* RefHashTableOf:: findBucketElem(const void* const key, unsigned int& hashVal) { // Hash the key hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); assert(hashVal < fHashModulus); // Search that bucket for the key RefHashTableBucketElem* curElem = fBucketList[hashVal]; while (curElem) { if (fHash->equals(key, curElem->fKey)) return curElem; curElem = curElem->fNext; } return 0; } template const RefHashTableBucketElem* RefHashTableOf:: findBucketElem(const void* const key, unsigned int& hashVal) const { // Hash the key hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager); assert(hashVal < fHashModulus); // Search that bucket for the key const RefHashTableBucketElem* curElem = fBucketList[hashVal]; while (curElem) { if (fHash->equals(key, curElem->fKey)) return curElem; curElem = curElem->fNext; } return 0; } // --------------------------------------------------------------------------- // RefHashTableOfEnumerator: Constructors and Destructor // --------------------------------------------------------------------------- template RefHashTableOfEnumerator:: RefHashTableOfEnumerator(RefHashTableOf* const toEnum , const bool adopt , MemoryManager* const manager) : fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum) , fMemoryManager(manager) { if (!toEnum) ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager); // // Find the next available bucket element in the hash table. If it // comes back zero, that just means the table is empty. // // Note that the -1 in the current hash tells it to start from the // beginning. // findNext(); } template RefHashTableOfEnumerator::~RefHashTableOfEnumerator() { if (fAdopted) delete fToEnum; } template RefHashTableOfEnumerator:: RefHashTableOfEnumerator(const RefHashTableOfEnumerator& toCopy) : XMLEnumerator(toCopy) , XMemory(toCopy) , fAdopted(toCopy.fAdopted) , fCurElem(toCopy.fCurElem) , fCurHash(toCopy.fCurHash) , fToEnum(toCopy.fToEnum) , fMemoryManager(toCopy.fMemoryManager) { } // --------------------------------------------------------------------------- // RefHashTableOfEnumerator: Enum interface // --------------------------------------------------------------------------- template bool RefHashTableOfEnumerator::hasMoreElements() const { // // If our current has is at the max and there are no more elements // in the current bucket, then no more elements. // if (!fCurElem && (fCurHash == fToEnum->fHashModulus)) return false; return true; } template TVal& RefHashTableOfEnumerator::nextElement() { // Make sure we have an element to return if (!hasMoreElements()) ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); // // Save the current element, then move up to the next one for the // next time around. // RefHashTableBucketElem* saveElem = fCurElem; findNext(); return *saveElem->fData; } template void* RefHashTableOfEnumerator::nextElementKey() { // Make sure we have an element to return if (!hasMoreElements()) ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager); // // Save the current element, then move up to the next one for the // next time around. // RefHashTableBucketElem* saveElem = fCurElem; findNext(); return saveElem->fKey; } template void RefHashTableOfEnumerator::Reset() { fCurHash = (unsigned int)-1; fCurElem = 0; findNext(); } // --------------------------------------------------------------------------- // RefHashTableOfEnumerator: Private helper methods // --------------------------------------------------------------------------- template void RefHashTableOfEnumerator::findNext() { // // If there is a current element, move to its next element. If this // hits the end of the bucket, the next block will handle the rest. // if (fCurElem) fCurElem = fCurElem->fNext; // // If the current element is null, then we have to move up to the // next hash value. If that is the hash modulus, then we cannot // go further. // if (!fCurElem) { fCurHash++; if (fCurHash == fToEnum->fHashModulus) return; // Else find the next non-empty bucket while (fToEnum->fBucketList[fCurHash]==0) { // Bump to the next hash value. If we max out return fCurHash++; if (fCurHash == fToEnum->fHashModulus) return; } fCurElem = fToEnum->fBucketList[fCurHash]; } } XERCES_CPP_NAMESPACE_END