xercesc/util/ValueHashTableOf.c

0001 /*
0002  * Licensed to the Apache Software Foundation (ASF) under one or more
0003  * contributor license agreements.  See the NOTICE file distributed with
0004  * this work for additional information regarding copyright ownership.
0005  * The ASF licenses this file to You under the Apache License, Version 2.0
0006  * (the "License"); you may not use this file except in compliance with
0007  * the License.  You may obtain a copy of the License at
0008  *
0009  *      http://www.apache.org/licenses/LICENSE-2.0
0010  *
0011  * Unless required by applicable law or agreed to in writing, software
0012  * distributed under the License is distributed on an "AS IS" BASIS,
0013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014  * See the License for the specific language governing permissions and
0015  * limitations under the License.
0016  */
0017
0018 /*
0019  * $Id$
0020  */
0021
0022
0023 // ---------------------------------------------------------------------------
0024 //  Include
0025 // ---------------------------------------------------------------------------
0026 #if defined(XERCES_TMPLSINC)
0027 #include <xercesc/util/ValueHashTableOf.hpp>
0028 #endif
0029
0030 #include <xercesc/util/NullPointerException.hpp>
0031 #include <xercesc/util/Janitor.hpp>
0032 #include <assert.h>
0033 #include <new>
0034
0035 XERCES_CPP_NAMESPACE_BEGIN
0036
0037 // ---------------------------------------------------------------------------
0038 //  ValueHashTableOf: Constructors and Destructor
0039 // ---------------------------------------------------------------------------
0040 template <class TVal, class THasher>
0041 ValueHashTableOf<TVal, THasher>::ValueHashTableOf( const XMLSize_t modulus
0042                                                    , const THasher& hasher
0043                                                    , MemoryManager* const manager)
0044     : fMemoryManager(manager)
0045     , fBucketList(0)
0046     , fHashModulus(modulus)
0047     , fInitialModulus(modulus)
0048     , fCount(0)
0049     , fHasher(hasher)
0050 {
0051     initialize(modulus);
0052 }
0053
0054 template <class TVal, class THasher>
0055 ValueHashTableOf<TVal, THasher>::ValueHashTableOf( const XMLSize_t modulus
0056                                                    , MemoryManager* const manager)
0057     : fMemoryManager(manager)
0058     , fBucketList(0)
0059     , fHashModulus(modulus)
0060     , fInitialModulus(modulus)
0061     , fCount(0)
0062     , fHasher()
0063 {
0064     initialize(modulus);
0065 }
0066
0067 template <class TVal, class THasher>
0068 void ValueHashTableOf<TVal, THasher>::initialize(const XMLSize_t modulus)
0069 {
0070     if (modulus == 0)
0071         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
0072
0073     // Allocate the bucket list and zero them
0074     fBucketList = (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate
0075     (
0076         fHashModulus * sizeof(ValueHashTableBucketElem<TVal>*)
0077     ); //new ValueHashTableBucketElem<TVal>*[fHashModulus];
0078     memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
0079 }
0080
0081 template <class TVal, class THasher>
0082 ValueHashTableOf<TVal, THasher>::~ValueHashTableOf()
0083 {
0084     removeAll();
0085
0086     // Then delete the bucket list & hasher
0087     fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
0088 }
0089
0090
0091 // ---------------------------------------------------------------------------
0092 //  ValueHashTableOf: Element management
0093 // ---------------------------------------------------------------------------
0094 template <class TVal, class THasher>
0095 bool ValueHashTableOf<TVal, THasher>::isEmpty() const
0096 {
0097     return fCount==0;
0098 }
0099
0100 template <class TVal, class THasher>
0101 bool ValueHashTableOf<TVal, THasher>::
0102 containsKey(const void* const key) const
0103 {
0104     XMLSize_t hashVal;
0105     const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
0106     return (findIt != 0);
0107 }
0108
0109 template <class TVal, class THasher>
0110 void ValueHashTableOf<TVal, THasher>::
0111 removeKey(const void* const key)
0112 {
0113     XMLSize_t hashVal;
0114     removeBucketElem(key, hashVal);
0115 }
0116
0117 template <class TVal, class THasher>
0118 void ValueHashTableOf<TVal, THasher>::removeAll()
0119 {
0120     if(isEmpty())
0121         return;
0122
0123     // Clean up the buckets first
0124     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0125     {
0126         // Get the bucket list head for this entry
0127         ValueHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
0128         ValueHashTableBucketElem<TVal>* nextElem;
0129         while (curElem)
0130         {
0131             // Save the next element before we hose this one
0132             nextElem = curElem->fNext;
0133
0134             // delete the current element and move forward
0135             // destructor is empty...
0136             // curElem->~ValueHashTableBucketElem();
0137             fMemoryManager->deallocate(curElem);
0138             curElem = nextElem;
0139         }
0140
0141         // Clean out this entry
0142         fBucketList[buckInd] = 0;
0143     }
0144     fCount = 0;
0145 }
0146
0147
0148 // ---------------------------------------------------------------------------
0149 //  ValueHashTableOf: Getters
0150 // ---------------------------------------------------------------------------
0151 template <class TVal, class THasher>
0152 TVal& ValueHashTableOf<TVal, THasher>::get(const void* const key, MemoryManager* const manager)
0153 {
0154     XMLSize_t hashVal;
0155     ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
0156     if (!findIt)
0157         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, manager);
0158
0159     return findIt->fData;
0160 }
0161
0162 template <class TVal, class THasher>
0163 const TVal& ValueHashTableOf<TVal, THasher>::
0164 get(const void* const key) const
0165 {
0166     XMLSize_t hashVal;
0167     const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
0168     if (!findIt)
0169         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
0170
0171     return findIt->fData;
0172 }
0173
0174
0175 // ---------------------------------------------------------------------------
0176 //  ValueHashTableOf: Putters
0177 // ---------------------------------------------------------------------------
0178 template <class TVal, class THasher>
0179 void ValueHashTableOf<TVal, THasher>::put(void* key, const TVal& valueToAdopt)
0180 {
0181     // Apply 0.75 load factor to find threshold.
0182     XMLSize_t threshold = fHashModulus * 3 / 4;
0183
0184     // If we've grown too big, expand the table and rehash.
0185     if (fCount >= threshold)
0186         rehash();
0187
0188     // First see if the key exists already
0189     XMLSize_t hashVal;
0190     ValueHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
0191
0192     //
0193     //  If so,then update its value. If not, then we need to add it to
0194     //  the right bucket
0195     //
0196     if (newBucket)
0197     {
0198         newBucket->fData = valueToAdopt;
0199         newBucket->fKey = key;
0200     }
0201      else
0202     {
0203         newBucket =
0204             new (fMemoryManager->allocate(sizeof(ValueHashTableBucketElem<TVal>)))
0205             ValueHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
0206         fBucketList[hashVal] = newBucket;
0207         fCount++;
0208     }
0209 }
0210
0211
0212
0213 // ---------------------------------------------------------------------------
0214 //  ValueHashTableOf: Private methods
0215 // ---------------------------------------------------------------------------
0216 template <class TVal, class THasher>
0217 void ValueHashTableOf<TVal, THasher>::rehash()
0218 {
0219     const XMLSize_t newMod = (fHashModulus * 2) + 1;
0220
0221     ValueHashTableBucketElem<TVal>** newBucketList =
0222         (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate
0223     (
0224         newMod * sizeof(ValueHashTableBucketElem<TVal>*)
0225     );//new RefHashTableBucketElem<TVal>*[newMod];
0226
0227     // Make sure the new bucket list is destroyed if an
0228     // exception is thrown.
0229     ArrayJanitor<ValueHashTableBucketElem<TVal>*>  guard(newBucketList, fMemoryManager);
0230
0231     memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
0232
0233
0234     // Rehash all existing entries.
0235     for (XMLSize_t index = 0; index < fHashModulus; index++)
0236     {
0237         // Get the bucket list head for this entry
0238         ValueHashTableBucketElem<TVal>* curElem = fBucketList[index];
0239
0240         while (curElem)
0241         {
0242             // Save the next element before we detach this one
0243             ValueHashTableBucketElem<TVal>* const nextElem = curElem->fNext;
0244
0245             const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey, newMod);
0246             assert(hashVal < newMod);
0247
0248             ValueHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal];
0249
0250             // Insert at the start of this bucket's list.
0251             curElem->fNext = newHeadElem;
0252             newBucketList[hashVal] = curElem;
0253
0254             curElem = nextElem;
0255         }
0256     }
0257
0258     ValueHashTableBucketElem<TVal>** const oldBucketList = fBucketList;
0259
0260     // Everything is OK at this point, so update the
0261     // member variables.
0262     fBucketList = guard.release();
0263     fHashModulus = newMod;
0264
0265     // Delete the old bucket list.
0266     fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
0267
0268 }
0269
0270 template <class TVal, class THasher>
0271 inline ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal, THasher>::
0272 findBucketElem(const void* const key, XMLSize_t& hashVal)
0273 {
0274     // Hash the key
0275     hashVal = fHasher.getHashVal(key, fHashModulus);
0276     assert(hashVal < fHashModulus);
0277
0278     // Search that bucket for the key
0279     ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0280     while (curElem)
0281     {
0282         if (fHasher.equals(key, curElem->fKey))
0283             return curElem;
0284
0285         curElem = curElem->fNext;
0286     }
0287     return 0;
0288 }
0289
0290 template <class TVal, class THasher>
0291 inline const ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal, THasher>::
0292 findBucketElem(const void* const key, XMLSize_t& hashVal) const
0293 {
0294     // Hash the key
0295     hashVal = fHasher.getHashVal(key, fHashModulus);
0296     assert(hashVal < fHashModulus);
0297
0298     // Search that bucket for the key
0299     const ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0300     while (curElem)
0301     {
0302         if (fHasher.equals(key, curElem->fKey))
0303             return curElem;
0304
0305         curElem = curElem->fNext;
0306     }
0307     return 0;
0308 }
0309
0310
0311 template <class TVal, class THasher>
0312 void ValueHashTableOf<TVal, THasher>::
0313 removeBucketElem(const void* const key, XMLSize_t& hashVal)
0314 {
0315     // Hash the key
0316     hashVal = fHasher.getHashVal(key, fHashModulus);
0317     assert(hashVal < fHashModulus);
0318
0319     //
0320     //  Search the given bucket for this key. Keep up with the previous
0321     //  element so we can patch around it.
0322     //
0323     ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0324     ValueHashTableBucketElem<TVal>* lastElem = 0;
0325
0326     while (curElem)
0327     {
0328         if (fHasher.equals(key, curElem->fKey))
0329         {
0330             if (!lastElem)
0331             {
0332                 // It was the first in the bucket
0333                 fBucketList[hashVal] = curElem->fNext;
0334             }
0335              else
0336             {
0337                 // Patch around the current element
0338                 lastElem->fNext = curElem->fNext;
0339             }
0340
0341             // Delete the current element
0342             // delete curElem;
0343             // destructor is empty...
0344             // curElem->~ValueHashTableBucketElem();
0345             fMemoryManager->deallocate(curElem);
0346
0347             fCount--;
0348
0349             return;
0350         }
0351
0352         // Move both pointers upwards
0353         lastElem = curElem;
0354         curElem = curElem->fNext;
0355     }
0356
0357     // We never found that key
0358     ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
0359 }
0360
0361
0362
0363
0364 // ---------------------------------------------------------------------------
0365 //  ValueHashTableOfEnumerator: Constructors and Destructor
0366 // ---------------------------------------------------------------------------
0367 template <class TVal, class THasher>
0368 ValueHashTableOfEnumerator<TVal, THasher>::
0369 ValueHashTableOfEnumerator(ValueHashTableOf<TVal, THasher>* const toEnum
0370                            , const bool adopt
0371                            , MemoryManager* const manager)
0372     : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum), fMemoryManager(manager)
0373 {
0374     if (!toEnum)
0375         ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, manager);
0376
0377     //
0378     //  Find the next available bucket element in the hash table. If it
0379     //  comes back zero, that just means the table is empty.
0380     //
0381     //  Note that the -1 in the current hash tells it to start from the
0382     //  beginning.
0383     //
0384     findNext();
0385 }
0386
0387 template <class TVal, class THasher>
0388 ValueHashTableOfEnumerator<TVal, THasher>::~ValueHashTableOfEnumerator()
0389 {
0390     if (fAdopted)
0391         delete fToEnum;
0392 }
0393
0394
0395 // ---------------------------------------------------------------------------
0396 //  ValueHashTableOfEnumerator: Enum interface
0397 // ---------------------------------------------------------------------------
0398 template <class TVal, class THasher>
0399 bool ValueHashTableOfEnumerator<TVal, THasher>::hasMoreElements() const
0400 {
0401     //
0402     //  If our current has is at the max and there are no more elements
0403     //  in the current bucket, then no more elements.
0404     //
0405     if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
0406         return false;
0407     return true;
0408 }
0409
0410 template <class TVal, class THasher>
0411 TVal& ValueHashTableOfEnumerator<TVal, THasher>::nextElement()
0412 {
0413     // Make sure we have an element to return
0414     if (!hasMoreElements())
0415         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
0416
0417     //
0418     //  Save the current element, then move up to the next one for the
0419     //  next time around.
0420     //
0421     ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
0422     findNext();
0423
0424     return saveElem->fData;
0425 }
0426
0427 template <class TVal, class THasher>
0428 void* ValueHashTableOfEnumerator<TVal, THasher>::nextElementKey()
0429 {
0430     // Make sure we have an element to return
0431     if (!hasMoreElements())
0432         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
0433
0434     //
0435     //  Save the current element, then move up to the next one for the
0436     //  next time around.
0437     //
0438     ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
0439     findNext();
0440
0441     return saveElem->fKey;
0442 }
0443
0444
0445 template <class TVal, class THasher>
0446 void ValueHashTableOfEnumerator<TVal, THasher>::Reset()
0447 {
0448     fCurHash = (XMLSize_t)-1;
0449     fCurElem = 0;
0450     findNext();
0451 }
0452
0453
0454
0455 // ---------------------------------------------------------------------------
0456 //  ValueHashTableOfEnumerator: Private helper methods
0457 // ---------------------------------------------------------------------------
0458 template <class TVal, class THasher>
0459 void ValueHashTableOfEnumerator<TVal, THasher>::findNext()
0460 {
0461     //
0462     //  If there is a current element, move to its next element. If this
0463     //  hits the end of the bucket, the next block will handle the rest.
0464     //
0465     if (fCurElem)
0466         fCurElem = fCurElem->fNext;
0467
0468     //
0469     //  If the current element is null, then we have to move up to the
0470     //  next hash value. If that is the hash modulus, then we cannot
0471     //  go further.
0472     //
0473     if (!fCurElem)
0474     {
0475         if (++fCurHash == fToEnum->fHashModulus)
0476             return;
0477
0478         // Else find the next non-empty bucket
0479         while (fToEnum->fBucketList[fCurHash]==0)
0480         {
0481             // Bump to the next hash value. If we max out return
0482             if (++fCurHash == fToEnum->fHashModulus)
0483                 return;
0484         }
0485         fCurElem = fToEnum->fBucketList[fCurHash];
0486     }
0487 }
0488
0489 XERCES_CPP_NAMESPACE_END