xercesc/util/Hash2KeysSetOf.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/Hash2KeysSetOf.hpp>
0028 #endif
0029
0030 #include <xercesc/util/Janitor.hpp>
0031 #include <xercesc/util/NullPointerException.hpp>
0032 #include <assert.h>
0033 #include <new>
0034
0035 XERCES_CPP_NAMESPACE_BEGIN
0036
0037 // ---------------------------------------------------------------------------
0038 //  Hash2KeysSetOf: Constructors and Destructor
0039 // ---------------------------------------------------------------------------
0040
0041 template <class THasher>
0042 Hash2KeysSetOf<THasher>::Hash2KeysSetOf(
0043   const XMLSize_t modulus,
0044   MemoryManager* const manager)
0045
0046     : fMemoryManager(manager)
0047     , fBucketList(0)
0048     , fHashModulus(modulus)
0049     , fCount(0)
0050     , fAvailable(0)
0051 {
0052     initialize(modulus);
0053 }
0054
0055 template <class THasher>
0056 Hash2KeysSetOf<THasher>::Hash2KeysSetOf(
0057   const XMLSize_t modulus,
0058   const THasher& hasher,
0059   MemoryManager* const manager)
0060
0061     : fMemoryManager(manager)
0062     , fBucketList(0)
0063     , fHashModulus(modulus)
0064     , fCount(0)
0065     , fAvailable(0)
0066     , fHasher (hasher)
0067 {
0068     initialize(modulus);
0069 }
0070
0071 template <class THasher>
0072 void Hash2KeysSetOf<THasher>::initialize(const XMLSize_t modulus)
0073 {
0074     if (modulus == 0)
0075         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
0076
0077     // Allocate the bucket list and zero them
0078     fBucketList = (Hash2KeysSetBucketElem**) fMemoryManager->allocate
0079     (
0080         fHashModulus * sizeof(Hash2KeysSetBucketElem*)
0081     ); //new Hash2KeysSetBucketElem*[fHashModulus];
0082     memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
0083 }
0084
0085 template <class THasher>
0086 Hash2KeysSetOf<THasher>::~Hash2KeysSetOf()
0087 {
0088     Hash2KeysSetBucketElem* nextElem;
0089     if(!isEmpty())
0090     {
0091         // Clean up the buckets first
0092         for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0093         {
0094             // Get the bucket list head for this entry
0095             Hash2KeysSetBucketElem* curElem = fBucketList[buckInd];
0096             while (curElem)
0097             {
0098                 // Save the next element before we hose this one
0099                 nextElem = curElem->fNext;
0100                 fMemoryManager->deallocate(curElem);
0101                 curElem = nextElem;
0102             }
0103
0104             // Clean out this entry
0105             fBucketList[buckInd] = 0;
0106         }
0107     }
0108     // Then delete the list of available blocks
0109     Hash2KeysSetBucketElem* curElem = fAvailable;
0110     while (curElem)
0111     {
0112         // Save the next element before we hose this one
0113         nextElem = curElem->fNext;
0114         fMemoryManager->deallocate(curElem);
0115         curElem = nextElem;
0116     }
0117     fAvailable = 0;
0118
0119     // Then delete the bucket list & hasher
0120     fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
0121     fBucketList = 0;
0122 }
0123
0124
0125 // ---------------------------------------------------------------------------
0126 //  Hash2KeysSetOf: Element management
0127 // ---------------------------------------------------------------------------
0128 template <class THasher>
0129 bool Hash2KeysSetOf<THasher>::isEmpty() const
0130 {
0131     return (fCount==0);
0132 }
0133
0134 template <class THasher>
0135 bool Hash2KeysSetOf<THasher>::containsKey(const void* const key1, const int key2) const
0136 {
0137     XMLSize_t hashVal;
0138     const Hash2KeysSetBucketElem* findIt = findBucketElem(key1, key2, hashVal);
0139     return (findIt != 0);
0140 }
0141
0142 template <class THasher>
0143 void Hash2KeysSetOf<THasher>::removeKey(const void* const key1, const int key2)
0144 {
0145     // Hash the key
0146     XMLSize_t hashVal = fHasher.getHashVal(key1, fHashModulus);
0147     assert(hashVal < fHashModulus);
0148
0149     //
0150     //  Search the given bucket for this key. Keep up with the previous
0151     //  element so we can patch around it.
0152     //
0153     Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
0154     Hash2KeysSetBucketElem* lastElem = 0;
0155
0156     while (curElem)
0157     {
0158         if((key2==curElem->fKey2) && (fHasher.equals(key1, curElem->fKey1)))
0159         {
0160             if (!lastElem)
0161             {
0162                 // It was the first in the bucket
0163                 fBucketList[hashVal] = curElem->fNext;
0164             }
0165             else
0166             {
0167                 // Patch around the current element
0168                 lastElem->fNext = curElem->fNext;
0169             }
0170
0171             // Move the current element to the list of available blocks
0172             curElem->fNext=fAvailable;
0173             fAvailable=curElem;
0174
0175             fCount--;
0176             return;
0177         }
0178
0179         // Move both pointers upwards
0180         lastElem = curElem;
0181         curElem = curElem->fNext;
0182     }
0183
0184     // We never found that key
0185     ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
0186 }
0187
0188 template <class THasher>
0189 void Hash2KeysSetOf<THasher>::
0190 removeKey(const void* const key1)
0191 {
0192     // Hash the key
0193     XMLSize_t hashVal = fHasher.getHashVal(key1, fHashModulus);
0194     assert(hashVal < fHashModulus);
0195
0196     //
0197     //  Search the given bucket for this key. Keep up with the previous
0198     //  element so we can patch around it.
0199     //
0200     Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
0201     Hash2KeysSetBucketElem* lastElem = 0;
0202
0203     while (curElem)
0204     {
0205         if(fHasher.equals(key1, curElem->fKey1))
0206         {
0207             if (!lastElem)
0208             {
0209                 // It was the first in the bucket
0210                 fBucketList[hashVal] = curElem->fNext;
0211             }
0212             else
0213             {
0214                 // Patch around the current element
0215                 lastElem->fNext = curElem->fNext;
0216             }
0217
0218             Hash2KeysSetBucketElem* toBeDeleted=curElem;
0219             curElem = curElem->fNext;
0220
0221             // Move the current element to the list of available blocks
0222             toBeDeleted->fNext=fAvailable;
0223             fAvailable=toBeDeleted;
0224
0225             fCount--;
0226         }
0227         else
0228         {
0229             // Move both pointers upwards
0230             lastElem = curElem;
0231             curElem = curElem->fNext;
0232         }
0233     }
0234 }
0235
0236 template <class THasher>
0237 void Hash2KeysSetOf<THasher>::removeAll()
0238 {
0239     if(isEmpty())
0240         return;
0241
0242     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0243     {
0244         if(fBucketList[buckInd]!=0)
0245         {
0246             // Advance to the end of the chain, and connect it to the list of
0247             // available blocks
0248             Hash2KeysSetBucketElem* curElem = fBucketList[buckInd];
0249             while (curElem->fNext)
0250                 curElem = curElem->fNext;
0251             curElem->fNext=fAvailable;
0252             fAvailable=fBucketList[buckInd];
0253             fBucketList[buckInd] = 0;
0254         }
0255     }
0256     fCount=0;
0257 }
0258
0259 // ---------------------------------------------------------------------------
0260 //  Hash2KeysSetOf: Getters
0261 // ---------------------------------------------------------------------------
0262 template <class THasher>
0263 MemoryManager* Hash2KeysSetOf<THasher>::getMemoryManager() const
0264 {
0265     return fMemoryManager;
0266 }
0267
0268 template <class THasher>
0269 XMLSize_t Hash2KeysSetOf<THasher>::getHashModulus() const
0270 {
0271     return fHashModulus;
0272 }
0273
0274 // ---------------------------------------------------------------------------
0275 //  Hash2KeysSetOf: Putters
0276 // ---------------------------------------------------------------------------
0277 template <class THasher>
0278 void Hash2KeysSetOf<THasher>::put(const void* key1, int key2)
0279 {
0280     // Apply 4 load factor to find threshold.
0281     XMLSize_t threshold = fHashModulus * 4;
0282
0283     // If we've grown too big, expand the table and rehash.
0284     if (fCount >= threshold)
0285         rehash();
0286
0287     // First see if the key exists already
0288     XMLSize_t hashVal;
0289     Hash2KeysSetBucketElem* newBucket = findBucketElem(key1, key2, hashVal);
0290
0291     //
0292     //  If so,then update its value. If not, then we need to add it to
0293     //  the right bucket
0294     //
0295     if (newBucket)
0296     {
0297         newBucket->fKey1 = key1;
0298         newBucket->fKey2 = key2;
0299     }
0300      else
0301     {
0302         if(fAvailable==0)
0303             newBucket = (Hash2KeysSetBucketElem*)fMemoryManager->allocate(sizeof(Hash2KeysSetBucketElem));
0304         else
0305         {
0306             newBucket = fAvailable;
0307             fAvailable = fAvailable->fNext;
0308         }
0309         newBucket->fKey1 = key1;
0310         newBucket->fKey2 = key2;
0311         newBucket->fNext = fBucketList[hashVal];
0312         fBucketList[hashVal] = newBucket;
0313         fCount++;
0314     }
0315 }
0316
0317 template <class THasher>
0318 bool Hash2KeysSetOf<THasher>::putIfNotPresent(const void* key1, int key2)
0319 {
0320     // First see if the key exists already
0321     XMLSize_t hashVal;
0322     Hash2KeysSetBucketElem* newBucket = findBucketElem(key1, key2, hashVal);
0323
0324     //
0325     //  If so,then update its value. If not, then we need to add it to
0326     //  the right bucket
0327     //
0328     if (newBucket)
0329         return false;
0330
0331     // Apply 4 load factor to find threshold.
0332     XMLSize_t threshold = fHashModulus * 4;
0333
0334     // If we've grown too big, expand the table and rehash.
0335     if (fCount >= threshold)
0336         rehash();
0337
0338     if(fAvailable==0)
0339         newBucket = (Hash2KeysSetBucketElem*)fMemoryManager->allocate(sizeof(Hash2KeysSetBucketElem));
0340     else
0341     {
0342         newBucket = fAvailable;
0343         fAvailable = fAvailable->fNext;
0344     }
0345     newBucket->fKey1 = key1;
0346     newBucket->fKey2 = key2;
0347     newBucket->fNext = fBucketList[hashVal];
0348     fBucketList[hashVal] = newBucket;
0349     fCount++;
0350     return true;
0351 }
0352
0353
0354 // ---------------------------------------------------------------------------
0355 //  Hash2KeysSetOf: Private methods
0356 // ---------------------------------------------------------------------------
0357 template <class THasher>
0358 inline Hash2KeysSetBucketElem* Hash2KeysSetOf<THasher>::
0359 findBucketElem(const void* const key1, const int key2, XMLSize_t& hashVal)
0360 {
0361     // Hash the key
0362     hashVal = fHasher.getHashVal(key1, fHashModulus);
0363     assert(hashVal < fHashModulus);
0364
0365     // Search that bucket for the key
0366     Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
0367     while (curElem)
0368     {
0369         if((key2==curElem->fKey2) && (fHasher.equals(key1, curElem->fKey1)))
0370             return curElem;
0371
0372         curElem = curElem->fNext;
0373     }
0374     return 0;
0375 }
0376
0377 template <class THasher>
0378 inline const Hash2KeysSetBucketElem* Hash2KeysSetOf<THasher>::
0379 findBucketElem(const void* const key1, const int key2, XMLSize_t& hashVal) const
0380 {
0381     // Hash the key
0382     hashVal = fHasher.getHashVal(key1, fHashModulus);
0383     assert(hashVal < fHashModulus);
0384
0385     // Search that bucket for the key
0386     const Hash2KeysSetBucketElem* curElem = fBucketList[hashVal];
0387     while (curElem)
0388     {
0389         if((key2==curElem->fKey2) && (fHasher.equals(key1, curElem->fKey1)))
0390             return curElem;
0391
0392         curElem = curElem->fNext;
0393     }
0394     return 0;
0395 }
0396
0397
0398 template <class THasher>
0399 void Hash2KeysSetOf<THasher>::
0400 rehash()
0401 {
0402     const XMLSize_t newMod = (fHashModulus * 8)+1;
0403
0404     Hash2KeysSetBucketElem** newBucketList =
0405         (Hash2KeysSetBucketElem**) fMemoryManager->allocate
0406     (
0407         newMod * sizeof(Hash2KeysSetBucketElem*)
0408     );//new Hash2KeysSetBucketElem*[fHashModulus];
0409
0410     // Make sure the new bucket list is destroyed if an
0411     // exception is thrown.
0412     ArrayJanitor<Hash2KeysSetBucketElem*>  guard(newBucketList, fMemoryManager);
0413
0414     memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
0415
0416     // Rehash all existing entries.
0417     for (XMLSize_t index = 0; index < fHashModulus; index++)
0418     {
0419         // Get the bucket list head for this entry
0420         Hash2KeysSetBucketElem* curElem = fBucketList[index];
0421         while (curElem)
0422         {
0423             // Save the next element before we detach this one
0424             Hash2KeysSetBucketElem* nextElem = curElem->fNext;
0425
0426             const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey1, newMod);
0427             assert(hashVal < newMod);
0428
0429             Hash2KeysSetBucketElem* newHeadElem = newBucketList[hashVal];
0430
0431             // Insert at the start of this bucket's list.
0432             curElem->fNext = newHeadElem;
0433             newBucketList[hashVal] = curElem;
0434
0435             curElem = nextElem;
0436         }
0437     }
0438
0439     Hash2KeysSetBucketElem** const oldBucketList = fBucketList;
0440
0441     // Everything is OK at this point, so update the
0442     // member variables.
0443     fBucketList = guard.release();
0444     fHashModulus = newMod;
0445
0446     // Delete the old bucket list.
0447     fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
0448
0449 }
0450
0451
0452
0453 // ---------------------------------------------------------------------------
0454 //  Hash2KeysSetOfEnumerator: Constructors and Destructor
0455 // ---------------------------------------------------------------------------
0456 template <class THasher>
0457 Hash2KeysSetOfEnumerator<THasher>::
0458 Hash2KeysSetOfEnumerator(Hash2KeysSetOf<THasher>* const toEnum
0459                               , const bool adopt
0460                               , MemoryManager* const manager)
0461     : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum)
0462     , fMemoryManager(manager)
0463     , fLockPrimaryKey(0)
0464 {
0465     if (!toEnum)
0466         ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
0467
0468     //
0469     //  Find the next available bucket element in the hash table. If it
0470     //  comes back zero, that just means the table is empty.
0471     //
0472     //  Note that the -1 in the current hash tells it to start
0473     //  from the beginning.
0474     //
0475     findNext();
0476 }
0477
0478 template <class THasher>
0479 Hash2KeysSetOfEnumerator<THasher>::~Hash2KeysSetOfEnumerator()
0480 {
0481     if (fAdopted)
0482         delete fToEnum;
0483 }
0484
0485
0486 // ---------------------------------------------------------------------------
0487 //  Hash2KeysSetOfEnumerator: Enum interface
0488 // ---------------------------------------------------------------------------
0489 template <class THasher>
0490 bool Hash2KeysSetOfEnumerator<THasher>::hasMoreElements() const
0491 {
0492     //
0493     //  If our current has is at the max and there are no more elements
0494     //  in the current bucket, then no more elements.
0495     //
0496     if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
0497         return false;
0498     return true;
0499 }
0500
0501 template <class THasher>
0502 void Hash2KeysSetOfEnumerator<THasher>::nextElementKey(const void*& retKey1, int& retKey2)
0503 {
0504     // Make sure we have an element to return
0505     if (!hasMoreElements())
0506         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
0507
0508     //
0509     //  Save the current element, then move up to the next one for the
0510     //  next time around.
0511     //
0512     Hash2KeysSetBucketElem* saveElem = fCurElem;
0513     findNext();
0514
0515     retKey1 = saveElem->fKey1;
0516     retKey2 = saveElem->fKey2;
0517
0518     return;
0519 }
0520
0521 template <class THasher>
0522 void Hash2KeysSetOfEnumerator<THasher>::Reset()
0523 {
0524     if(fLockPrimaryKey)
0525         fCurHash=fToEnum->fHasher.getHashVal(fLockPrimaryKey, fToEnum->fHashModulus);
0526     else
0527         fCurHash = (XMLSize_t)-1;
0528
0529     fCurElem = 0;
0530     findNext();
0531 }
0532
0533
0534 template <class THasher>
0535 void Hash2KeysSetOfEnumerator<THasher>::setPrimaryKey(const void* key)
0536 {
0537     fLockPrimaryKey=key;
0538     Reset();
0539 }
0540
0541 // ---------------------------------------------------------------------------
0542 //  Hash2KeysSetOfEnumerator: Private helper methods
0543 // ---------------------------------------------------------------------------
0544 template <class THasher>
0545 void Hash2KeysSetOfEnumerator<THasher>::findNext()
0546 {
0547     //  Code to execute if we have to return only values with the primary key
0548     if(fLockPrimaryKey)
0549     {
0550         if(!fCurElem)
0551             fCurElem = fToEnum->fBucketList[fCurHash];
0552         else
0553             fCurElem = fCurElem->fNext;
0554         while (fCurElem && (!fToEnum->fHasher.equals(fLockPrimaryKey, fCurElem->fKey1)))
0555             fCurElem = fCurElem->fNext;
0556         // if we didn't found it, make so hasMoreElements() returns false
0557         if(!fCurElem)
0558             fCurHash = fToEnum->fHashModulus;
0559         return;
0560     }
0561     //
0562     //  If there is a current element, move to its next element. If this
0563     //  hits the end of the bucket, the next block will handle the rest.
0564     //
0565     if (fCurElem)
0566         fCurElem = fCurElem->fNext;
0567
0568     //
0569     //  If the current element is null, then we have to move up to the
0570     //  next hash value. If that is the hash modulus, then we cannot
0571     //  go further.
0572     //
0573     if (!fCurElem)
0574     {
0575         fCurHash++;
0576         if (fCurHash == fToEnum->fHashModulus)
0577             return;
0578
0579         // Else find the next non-empty bucket
0580         while (fToEnum->fBucketList[fCurHash]==0)
0581         {
0582             // Bump to the next hash value. If we max out return
0583             fCurHash++;
0584             if (fCurHash == fToEnum->fHashModulus)
0585                 return;
0586         }
0587         fCurElem = fToEnum->fBucketList[fCurHash];
0588     }
0589 }
0590
0591 XERCES_CPP_NAMESPACE_END