/* * 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: ValueHashTableOf.c 568078 2007-08-21 11:43:25Z amassari $ */ // --------------------------------------------------------------------------- // Include // --------------------------------------------------------------------------- #if defined(XERCES_TMPLSINC) #include #endif #include #include #include XERCES_CPP_NAMESPACE_BEGIN // --------------------------------------------------------------------------- // ValueHashTableOf: Constructors and Destructor // --------------------------------------------------------------------------- template ValueHashTableOf::ValueHashTableOf( const unsigned int modulus , HashBase* hashBase , MemoryManager* const manager) : fMemoryManager(manager) , fBucketList(0) , fHashModulus(modulus) , fHash(0) { initialize(modulus); // set hasher fHash = hashBase; } template ValueHashTableOf::ValueHashTableOf( const unsigned int modulus , MemoryManager* const manager) : fMemoryManager(manager) , fBucketList(0) , fHashModulus(modulus) , fHash(0) { initialize(modulus); // create default hasher fHash = new (fMemoryManager) HashXMLCh(); } template void ValueHashTableOf::initialize(const unsigned int modulus) { if (modulus == 0) ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager); // Allocate the bucket list and zero them fBucketList = (ValueHashTableBucketElem**) fMemoryManager->allocate ( fHashModulus * sizeof(ValueHashTableBucketElem*) ); //new ValueHashTableBucketElem*[fHashModulus]; memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus); } template ValueHashTableOf::~ValueHashTableOf() { removeAll(); // Then delete the bucket list & hasher fMemoryManager->deallocate(fBucketList); //delete [] fBucketList; delete fHash; } // --------------------------------------------------------------------------- // ValueHashTableOf: Element management // --------------------------------------------------------------------------- template bool ValueHashTableOf::isEmpty() const { // Just check the bucket list for non-empty elements for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) { if (fBucketList[buckInd] != 0) return false; } return true; } template bool ValueHashTableOf:: containsKey(const void* const key) const { unsigned int hashVal; const ValueHashTableBucketElem* findIt = findBucketElem(key, hashVal); return (findIt != 0); } template void ValueHashTableOf:: removeKey(const void* const key) { unsigned int hashVal; removeBucketElem(key, hashVal); } template void ValueHashTableOf::removeAll() { // Clean up the buckets first for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++) { // Get the bucket list head for this entry ValueHashTableBucketElem* curElem = fBucketList[buckInd]; ValueHashTableBucketElem* nextElem; while (curElem) { // Save the next element before we hose this one nextElem = curElem->fNext; // delete the current element and move forward // destructor is empty... // curElem->~ValueHashTableBucketElem(); fMemoryManager->deallocate(curElem); curElem = nextElem; } // Clean out this entry fBucketList[buckInd] = 0; } } // --------------------------------------------------------------------------- // ValueHashTableOf: Getters // --------------------------------------------------------------------------- template TVal& ValueHashTableOf::get(const void* const key, MemoryManager* const manager) { unsigned int hashVal; ValueHashTableBucketElem* findIt = findBucketElem(key, hashVal); if (!findIt) ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, manager); return findIt->fData; } template const TVal& ValueHashTableOf:: get(const void* const key) const { unsigned int hashVal; const ValueHashTableBucketElem* findIt = findBucketElem(key, hashVal); if (!findIt) ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); return findIt->fData; } // --------------------------------------------------------------------------- // ValueHashTableOf: Putters // --------------------------------------------------------------------------- template void ValueHashTableOf::put(void* key, const TVal& valueToAdopt) { // First see if the key exists already unsigned int hashVal; ValueHashTableBucketElem* newBucket = findBucketElem(key, hashVal); // // If so,then update its value. If not, then we need to add it to // the right bucket // if (newBucket) { newBucket->fData = valueToAdopt; newBucket->fKey = key; } else { newBucket = new (fMemoryManager->allocate(sizeof(ValueHashTableBucketElem))) ValueHashTableBucketElem(key, valueToAdopt, fBucketList[hashVal]); fBucketList[hashVal] = newBucket; } } // --------------------------------------------------------------------------- // ValueHashTableOf: Private methods // --------------------------------------------------------------------------- template ValueHashTableBucketElem* ValueHashTableOf:: 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 ValueHashTableBucketElem* curElem = fBucketList[hashVal]; while (curElem) { if (fHash->equals(key, curElem->fKey)) return curElem; curElem = curElem->fNext; } return 0; } template const ValueHashTableBucketElem* ValueHashTableOf:: 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 ValueHashTableBucketElem* curElem = fBucketList[hashVal]; while (curElem) { if (fHash->equals(key, curElem->fKey)) return curElem; curElem = curElem->fNext; } return 0; } template void ValueHashTableOf:: removeBucketElem(const void* const key, unsigned int& hashVal) { // Hash the key hashVal = fHash->getHashVal(key, fHashModulus); assert(hashVal < fHashModulus); // // Search the given bucket for this key. Keep up with the previous // element so we can patch around it. // ValueHashTableBucketElem* curElem = fBucketList[hashVal]; ValueHashTableBucketElem* 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; } // Delete the current element // delete curElem; // destructor is empty... // curElem->~ValueHashTableBucketElem(); fMemoryManager->deallocate(curElem); return; } // Move both pointers upwards lastElem = curElem; curElem = curElem->fNext; } // We never found that key ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager); } // --------------------------------------------------------------------------- // ValueHashTableOfEnumerator: Constructors and Destructor // --------------------------------------------------------------------------- template ValueHashTableOfEnumerator:: ValueHashTableOfEnumerator(ValueHashTableOf* 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, manager); // // 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 ValueHashTableOfEnumerator::~ValueHashTableOfEnumerator() { if (fAdopted) delete fToEnum; } // --------------------------------------------------------------------------- // ValueHashTableOfEnumerator: Enum interface // --------------------------------------------------------------------------- template bool ValueHashTableOfEnumerator::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& ValueHashTableOfEnumerator::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. // ValueHashTableBucketElem* saveElem = fCurElem; findNext(); return saveElem->fData; } template void* ValueHashTableOfEnumerator::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. // ValueHashTableBucketElem* saveElem = fCurElem; findNext(); return saveElem->fKey; } template void ValueHashTableOfEnumerator::Reset() { fCurHash = (unsigned int)-1; fCurElem = 0; findNext(); } // --------------------------------------------------------------------------- // ValueHashTableOfEnumerator: Private helper methods // --------------------------------------------------------------------------- template void ValueHashTableOfEnumerator::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