/* * Copyright 2002,2004 The Apache Software Foundation. * * Licensed 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. */ /** * $Log$ * Revision 1.2 2004/09/08 13:57:05 peiyongz * Apache License Version 2.0 * * Revision 1.1 2003/06/03 18:57:32 neilg * following tradition, use a .c extension for the body of a template class. * */ #if defined(XERCES_TMPLSINC) #include "SimpleValueHashTableOf.hpp" #endif // --------------------------------------------------------------------------- // Include // --------------------------------------------------------------------------- #include // This is just an old version of the ValueHashTableOf implementation // from xercesc/util; we need a new one here because this // cannot use the pluggalbe memory management facilities. // forward declarations // --------------------------------------------------------------------------- // ValueHashTableOf: Constructors and Destructor // --------------------------------------------------------------------------- template SimpleValueHashTableOf::SimpleValueHashTableOf(const unsigned int modulus , SimpleHashPtr* hashBase) : fBucketList(0), fHashModulus(modulus) { initialize(modulus); // set hasher fHash = hashBase; } template SimpleValueHashTableOf::SimpleValueHashTableOf(const unsigned int modulus) : fBucketList(0), fHashModulus(modulus) { initialize(modulus); // create default hasher fHash = new HashXMLCh(); } template void SimpleValueHashTableOf::initialize(const unsigned int modulus) { if (modulus == 0) ThrowXML(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus); // Allocate the bucket list and zero them fBucketList = new ValueHashTableBucketElem*[fHashModulus]; for (unsigned int index = 0; index < fHashModulus; index++) fBucketList[index] = 0; } template SimpleValueHashTableOf::~SimpleValueHashTableOf() { removeAll(); // Then delete the bucket list & hasher delete [] fBucketList; delete fHash; } // --------------------------------------------------------------------------- // SimpleValueHashTableOf: Element management // --------------------------------------------------------------------------- template bool SimpleValueHashTableOf::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 SimpleValueHashTableOf:: containsKey(const void* const key) const { unsigned int hashVal; const ValueHashTableBucketElem* findIt = findBucketElem(key, hashVal); return (findIt != 0); } template void SimpleValueHashTableOf:: removeKey(const void* const key) { unsigned int hashVal; removeBucketElem(key, hashVal); } template void SimpleValueHashTableOf::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 delete curElem; curElem = nextElem; } // Clean out this entry fBucketList[buckInd] = 0; } } // --------------------------------------------------------------------------- // SimpleValueHashTableOf: Getters // --------------------------------------------------------------------------- template TVal& SimpleValueHashTableOf::get(const void* const key) { unsigned int hashVal; ValueHashTableBucketElem* findIt = findBucketElem(key, hashVal); if (!findIt) ThrowXML(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists); return findIt->fData; } template const TVal& SimpleValueHashTableOf:: get(const void* const key) const { unsigned int hashVal; const ValueHashTableBucketElem* findIt = findBucketElem(key, hashVal); if (!findIt) ThrowXML(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists); return findIt->fData; } // --------------------------------------------------------------------------- // SimpleValueHashTableOf: Putters // --------------------------------------------------------------------------- template void SimpleValueHashTableOf::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 ValueHashTableBucketElem(key, valueToAdopt, fBucketList[hashVal]); fBucketList[hashVal] = newBucket; } } // --------------------------------------------------------------------------- // SimpleValueHashTableOf: Private methods // --------------------------------------------------------------------------- template ValueHashTableBucketElem* SimpleValueHashTableOf:: findBucketElem(const void* const key, unsigned int& hashVal) { // Hash the key hashVal = fHash->getHashVal(key, fHashModulus); if (hashVal > fHashModulus) ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey); // 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* SimpleValueHashTableOf:: findBucketElem(const void* const key, unsigned int& hashVal) const { // Hash the key hashVal = fHash->getHashVal(key, fHashModulus); if (hashVal > fHashModulus) ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey); // 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 SimpleValueHashTableOf:: removeBucketElem(const void* const key, unsigned int& hashVal) { // Hash the key hashVal = fHash->getHashVal(key, fHashModulus); if (hashVal > fHashModulus) ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey); // // 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; return; } // Move both pointers upwards lastElem = curElem; curElem = curElem->fNext; } // We never found that key ThrowXML(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists); } // --------------------------------------------------------------------------- // ValueHashTableOfEnumerator: Constructors and Destructor // --------------------------------------------------------------------------- template ValueHashTableOfEnumerator:: ValueHashTableOfEnumerator(SimpleValueHashTableOf* const toEnum, const bool adopt) : fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum) { if (!toEnum) ThrowXML(NullPointerException, XMLExcepts::CPtr_PointerIsZero); // // 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()) ThrowXML(NoSuchElementException, XMLExcepts::Enum_NoMoreElements); // // 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::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 (true) { if (fToEnum->fBucketList[fCurHash]) break; // Bump to the next hash value. If we max out return fCurHash++; if (fCurHash == fToEnum->fHashModulus) return; } fCurElem = fToEnum->fBucketList[fCurHash]; } }