xercesc/util/RefHash3KeysIdPool.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/RefHash3KeysIdPool.hpp>
0028 #endif
0029
0030 #include <xercesc/util/NullPointerException.hpp>
0031 #include <assert.h>
0032 #include <new>
0033
0034 XERCES_CPP_NAMESPACE_BEGIN
0035
0036 // ---------------------------------------------------------------------------
0037 //  RefHash3KeysIdPool: Constructors and Destructor
0038 // ---------------------------------------------------------------------------
0039 template <class TVal, class THasher>
0040 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
0041   const XMLSize_t modulus,
0042   const XMLSize_t initSize,
0043   MemoryManager* const manager)
0044
0045     : fMemoryManager(manager)
0046     , fAdoptedElems(true)
0047     , fBucketList(0)
0048     , fHashModulus(modulus)
0049     , fIdPtrs(0)
0050     , fIdPtrsCount(initSize)
0051     , fIdCounter(0)
0052 {
0053     initialize(modulus);
0054
0055     //  Allocate the initial id pointers array. We don't have to zero them
0056     //  out since the fIdCounter value tells us which ones are valid. The
0057     //  zeroth element is never used (and represents an invalid pool id.)
0058     //
0059     if (!fIdPtrsCount)
0060         fIdPtrsCount = 256;
0061     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
0062     fIdPtrs[0] = 0;
0063 }
0064
0065 template <class TVal, class THasher>
0066 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
0067   const XMLSize_t modulus,
0068   const THasher& hasher,
0069   const XMLSize_t initSize,
0070   MemoryManager* const manager)
0071
0072     : fMemoryManager(manager)
0073     , fAdoptedElems(true)
0074     , fBucketList(0)
0075     , fHashModulus(modulus)
0076     , fIdPtrs(0)
0077     , fIdPtrsCount(initSize)
0078     , fIdCounter(0)
0079     , fHasher(hasher)
0080 {
0081     initialize(modulus);
0082
0083     //  Allocate the initial id pointers array. We don't have to zero them
0084     //  out since the fIdCounter value tells us which ones are valid. The
0085     //  zeroth element is never used (and represents an invalid pool id.)
0086     //
0087     if (!fIdPtrsCount)
0088         fIdPtrsCount = 256;
0089     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
0090     fIdPtrs[0] = 0;
0091 }
0092
0093 template <class TVal, class THasher>
0094 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
0095   const XMLSize_t modulus,
0096   const bool adoptElems,
0097   const XMLSize_t initSize,
0098   MemoryManager* const manager)
0099
0100     : fMemoryManager(manager)
0101     , fAdoptedElems(adoptElems)
0102     , fBucketList(0)
0103     , fHashModulus(modulus)
0104     , fIdPtrs(0)
0105     , fIdPtrsCount(initSize)
0106     , fIdCounter(0)
0107
0108 {
0109     initialize(modulus);
0110
0111     //  Allocate the initial id pointers array. We don't have to zero them
0112     //  out since the fIdCounter value tells us which ones are valid. The
0113     //  zeroth element is never used (and represents an invalid pool id.)
0114     //
0115     if (!fIdPtrsCount)
0116         fIdPtrsCount = 256;
0117     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
0118     fIdPtrs[0] = 0;
0119 }
0120
0121 template <class TVal, class THasher>
0122 RefHash3KeysIdPool<TVal, THasher>::RefHash3KeysIdPool(
0123   const XMLSize_t modulus,
0124   const bool adoptElems,
0125   const THasher& hasher,
0126   const XMLSize_t initSize,
0127   MemoryManager* const manager)
0128
0129     : fMemoryManager(manager)
0130     , fAdoptedElems(adoptElems)
0131     , fBucketList(0)
0132     , fHashModulus(modulus)
0133     , fIdPtrs(0)
0134     , fIdPtrsCount(initSize)
0135     , fIdCounter(0)
0136     , fHasher(hasher)
0137 {
0138     initialize(modulus);
0139
0140     //  Allocate the initial id pointers array. We don't have to zero them
0141     //  out since the fIdCounter value tells us which ones are valid. The
0142     //  zeroth element is never used (and represents an invalid pool id.)
0143     //
0144     if (!fIdPtrsCount)
0145         fIdPtrsCount = 256;
0146     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
0147     fIdPtrs[0] = 0;
0148 }
0149
0150 template <class TVal, class THasher>
0151 void RefHash3KeysIdPool<TVal, THasher>::initialize(const XMLSize_t modulus)
0152 {
0153     if (modulus == 0)
0154         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
0155
0156     // Allocate the bucket list and zero them
0157     fBucketList = (RefHash3KeysTableBucketElem<TVal>**) fMemoryManager->allocate
0158     (
0159         fHashModulus * sizeof(RefHash3KeysTableBucketElem<TVal>*)
0160     ); //new RefHash3KeysTableBucketElem<TVal>*[fHashModulus];
0161     memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
0162 }
0163
0164 template <class TVal, class THasher>
0165 RefHash3KeysIdPool<TVal, THasher>::~RefHash3KeysIdPool()
0166 {
0167     removeAll();
0168
0169     // Then delete the bucket list & hasher & id pointers list
0170     fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
0171     fIdPtrs = 0;
0172     fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
0173     fBucketList = 0;
0174 }
0175
0176
0177 // ---------------------------------------------------------------------------
0178 //  RefHash3KeysIdPool: Element management
0179 // ---------------------------------------------------------------------------
0180 template <class TVal, class THasher>
0181 bool RefHash3KeysIdPool<TVal, THasher>::isEmpty() const
0182 {
0183     // Just check the bucket list for non-empty elements
0184     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0185     {
0186         if (fBucketList[buckInd] != 0)
0187             return false;
0188     }
0189     return true;
0190 }
0191
0192 template <class TVal, class THasher>
0193 bool RefHash3KeysIdPool<TVal, THasher>::
0194 containsKey(const void* const key1, const int key2, const int key3) const
0195 {
0196     XMLSize_t hashVal;
0197     const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
0198     return (findIt != 0);
0199 }
0200
0201 template <class TVal, class THasher>
0202 void RefHash3KeysIdPool<TVal, THasher>::removeAll()
0203 {
0204     if (fIdCounter == 0) return;
0205
0206     // Clean up the buckets first
0207     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0208     {
0209         // Get the bucket list head for this entry
0210         RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[buckInd];
0211         RefHash3KeysTableBucketElem<TVal>* nextElem;
0212         while (curElem)
0213         {
0214             // Save the next element before we hose this one
0215             nextElem = curElem->fNext;
0216
0217             // If we adopted the data, then delete it too
0218             //    (Note:  the userdata hash table instance has data type of void *.
0219             //    This will generate compiler warnings here on some platforms, but they
0220             //    can be ignored since fAdoptedElements is false.
0221             if (fAdoptedElems)
0222                 delete curElem->fData;
0223
0224             // Then delete the current element and move forward
0225             // delete curElem;
0226             // destructor is empty...
0227             // curElem->~RefHash3KeysTableBucketElem();
0228             fMemoryManager->deallocate(curElem);
0229             curElem = nextElem;
0230         }
0231
0232         // Clean out this entry
0233         fBucketList[buckInd] = 0;
0234     }
0235
0236     // Reset the id counter
0237     fIdCounter = 0;
0238 }
0239
0240
0241 // ---------------------------------------------------------------------------
0242 //  RefHash3KeysIdPool: Getters
0243 // ---------------------------------------------------------------------------
0244 template <class TVal, class THasher>
0245 TVal*
0246 RefHash3KeysIdPool<TVal, THasher>::getByKey(const void* const key1, const int key2, const int key3)
0247 {
0248     XMLSize_t hashVal;
0249     RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
0250     if (!findIt)
0251         return 0;
0252     return findIt->fData;
0253 }
0254
0255 template <class TVal, class THasher>
0256 const TVal*
0257 RefHash3KeysIdPool<TVal, THasher>::getByKey(const void* const key1, const int key2, const int key3) const
0258 {
0259     XMLSize_t hashVal;
0260     const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
0261     if (!findIt)
0262         return 0;
0263     return findIt->fData;
0264 }
0265
0266 template <class TVal, class THasher>
0267 TVal*
0268 RefHash3KeysIdPool<TVal, THasher>::getById(const unsigned int elemId)
0269 {
0270     // If its either zero or beyond our current id, its an error
0271     if (!elemId || (elemId > fIdCounter))
0272         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
0273
0274     return fIdPtrs[elemId];
0275 }
0276
0277 template <class TVal, class THasher>
0278 const TVal*
0279 RefHash3KeysIdPool<TVal, THasher>::getById(const unsigned int elemId) const
0280 {
0281     // If its either zero or beyond our current id, its an error
0282     if (!elemId || (elemId > fIdCounter))
0283         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
0284
0285     return fIdPtrs[elemId];
0286 }
0287
0288 template <class TVal, class THasher>
0289 MemoryManager* RefHash3KeysIdPool<TVal, THasher>::getMemoryManager() const
0290 {
0291     return fMemoryManager;
0292 }
0293
0294 template <class TVal, class THasher>
0295 XMLSize_t RefHash3KeysIdPool<TVal, THasher>::getHashModulus() const
0296 {
0297     return fHashModulus;
0298 }
0299
0300 // ---------------------------------------------------------------------------
0301 //  RefHash3KeysIdPool: Putters
0302 // ---------------------------------------------------------------------------
0303 template <class TVal, class THasher>
0304 XMLSize_t
0305 RefHash3KeysIdPool<TVal, THasher>::put(void* key1, int key2, int key3, TVal* const valueToAdopt)
0306 {
0307     // First see if the key exists already
0308     XMLSize_t hashVal;
0309     XMLSize_t retId;
0310     RefHash3KeysTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, key3, hashVal);
0311
0312     //
0313     //  If so,then update its value. If not, then we need to add it to
0314     //  the right bucket
0315     //
0316     if (newBucket)
0317     {
0318         retId = newBucket->fData->getId();
0319         if (fAdoptedElems)
0320             delete newBucket->fData;
0321         newBucket->fData = valueToAdopt;
0322         newBucket->fKey1 = key1;
0323         newBucket->fKey2 = key2;
0324         newBucket->fKey3 = key3;
0325     }
0326     else
0327     {
0328     // Revisit: the gcc compiler 2.95.x is generating an
0329     // internal compiler error message. So we use the default
0330     // memory manager for now.
0331 #if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
0332         newBucket = new RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
0333 #else
0334         newBucket =
0335             new (fMemoryManager->allocate(sizeof(RefHash3KeysTableBucketElem<TVal>)))
0336             RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
0337 #endif
0338         fBucketList[hashVal] = newBucket;
0339
0340         //
0341         //  Give this new one the next available id and add to the pointer list.
0342         //  Expand the list if that is now required.
0343         //
0344         if (fIdCounter + 1 == fIdPtrsCount)
0345         {
0346             // Create a new count 1.5 times larger and allocate a new array
0347             XMLSize_t newCount = (XMLSize_t)(fIdPtrsCount * 1.5);
0348             TVal** newArray = (TVal**) fMemoryManager->allocate
0349             (
0350                 newCount * sizeof(TVal*)
0351             ); //new TVal*[newCount];
0352
0353             // Copy over the old contents to the new array
0354             memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TVal*));
0355
0356             // Ok, toss the old array and store the new data
0357             fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
0358             fIdPtrs = newArray;
0359             fIdPtrsCount = newCount;
0360         }
0361         retId = ++fIdCounter;
0362     }
0363
0364     fIdPtrs[retId] = valueToAdopt;
0365
0366     // Set the id on the passed element
0367     valueToAdopt->setId(retId);
0368
0369     // Return the id that we gave to this element
0370     return retId;
0371 }
0372
0373 // ---------------------------------------------------------------------------
0374 //  RefHash3KeysIdPool: Private methods
0375 // ---------------------------------------------------------------------------
0376 template <class TVal, class THasher>
0377 inline RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal, THasher>::
0378 findBucketElem(const void* const key1, const int key2, const int key3, XMLSize_t& hashVal)
0379 {
0380     // Hash the key
0381     hashVal = fHasher.getHashVal(key1, fHashModulus);
0382     assert(hashVal < fHashModulus);
0383
0384     // Search that bucket for the key
0385     RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0386     while (curElem)
0387     {
0388         if((key2==curElem->fKey2) && (key3==curElem->fKey3) && (fHasher.equals(key1, curElem->fKey1)))
0389             return curElem;
0390
0391         curElem = curElem->fNext;
0392     }
0393     return 0;
0394 }
0395
0396 template <class TVal, class THasher>
0397 inline const RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal, THasher>::
0398 findBucketElem(const void* const key1, const int key2, const int key3, XMLSize_t& hashVal) const
0399 {
0400     // Hash the key
0401     hashVal = fHasher.getHashVal(key1, fHashModulus);
0402     assert(hashVal < fHashModulus);
0403
0404     // Search that bucket for the key
0405     const RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0406     while (curElem)
0407     {
0408         if((key2==curElem->fKey2) && (key3==curElem->fKey3) && (fHasher.equals(key1, curElem->fKey1)))
0409             return curElem;
0410
0411         curElem = curElem->fNext;
0412     }
0413     return 0;
0414 }
0415
0416
0417 // ---------------------------------------------------------------------------
0418 //  RefHash3KeysIdPoolEnumerator: Constructors and Destructor
0419 // ---------------------------------------------------------------------------
0420 template <class TVal, class THasher>
0421 RefHash3KeysIdPoolEnumerator<TVal, THasher>::
0422 RefHash3KeysIdPoolEnumerator(RefHash3KeysIdPool<TVal, THasher>* const toEnum
0423                              , const bool adopt
0424                              , MemoryManager* const manager)
0425     : fAdoptedElems(adopt), fCurIndex(0), fToEnum(toEnum), fMemoryManager(manager)
0426 {
0427     if (!toEnum)
0428         ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
0429
0430     Reset();
0431     resetKey();
0432 }
0433
0434 template <class TVal, class THasher>
0435 RefHash3KeysIdPoolEnumerator<TVal, THasher>::~RefHash3KeysIdPoolEnumerator()
0436 {
0437     if (fAdoptedElems)
0438         delete fToEnum;
0439 }
0440
0441 template <class TVal, class THasher>
0442 RefHash3KeysIdPoolEnumerator<TVal, THasher>::
0443 RefHash3KeysIdPoolEnumerator(const RefHash3KeysIdPoolEnumerator<TVal, THasher>& toCopy) :
0444     XMLEnumerator<TVal>(toCopy)
0445     , XMemory(toCopy)
0446     , fAdoptedElems(toCopy.fAdoptedElems)
0447     , fCurIndex(toCopy.fCurIndex)
0448     , fToEnum(toCopy.fToEnum)
0449     , fCurElem(toCopy.fCurElem)
0450     , fCurHash(toCopy.fCurHash)
0451     , fMemoryManager(toCopy.fMemoryManager)
0452 {
0453 }
0454
0455 // ---------------------------------------------------------------------------
0456 //  RefHash3KeysIdPoolEnumerator: Enum interface
0457 // ---------------------------------------------------------------------------
0458 template <class TVal, class THasher>
0459 bool RefHash3KeysIdPoolEnumerator<TVal, THasher>::hasMoreElements() const
0460 {
0461     // If our index is zero or past the end, then we are done
0462     if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
0463         return false;
0464     return true;
0465 }
0466
0467 template <class TVal, class THasher>
0468 TVal& RefHash3KeysIdPoolEnumerator<TVal, THasher>::nextElement()
0469 {
0470     // If our index is zero or past the end, then we are done
0471     if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
0472         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
0473
0474     // Return the current element and bump the index
0475     return *fToEnum->fIdPtrs[fCurIndex++];
0476 }
0477
0478 template <class TVal, class THasher>
0479 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::Reset()
0480 {
0481     //
0482     //  Find the next available bucket element in the pool. We use the id
0483     //  array since its very easy to enumerator through by just maintaining
0484     //  an index. If the id counter is zero, then its empty and we leave the
0485     //  current index to zero.
0486     //
0487     fCurIndex = fToEnum->fIdCounter ? 1:0;
0488
0489 }
0490
0491 template <class TVal, class THasher>
0492 XMLSize_t RefHash3KeysIdPoolEnumerator<TVal, THasher>::size() const
0493 {
0494     return fToEnum->fIdCounter;
0495 }
0496
0497 template <class TVal, class THasher>
0498 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::resetKey()
0499 {
0500     fCurHash = (XMLSize_t)-1;
0501     fCurElem = 0;
0502     findNext();
0503 }
0504
0505 template <class TVal, class THasher>
0506 bool RefHash3KeysIdPoolEnumerator<TVal, THasher>::hasMoreKeys() const
0507 {
0508     //
0509     //  If our current has is at the max and there are no more elements
0510     //  in the current bucket, then no more elements.
0511     //
0512     if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
0513         return false;
0514
0515     return true;
0516 }
0517
0518 template <class TVal, class THasher>
0519 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::nextElementKey(void*& retKey1, int& retKey2, int& retKey3)
0520 {
0521     // Make sure we have an element to return
0522     if (!hasMoreKeys())
0523         ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
0524
0525     //
0526     //  Save the current element, then move up to the next one for the
0527     //  next time around.
0528     //
0529     RefHash3KeysTableBucketElem<TVal>* saveElem = fCurElem;
0530     findNext();
0531
0532     retKey1 = saveElem->fKey1;
0533     retKey2 = saveElem->fKey2;
0534     retKey3 = saveElem->fKey3;
0535
0536     return;
0537 }
0538
0539 template <class TVal, class THasher>
0540 void RefHash3KeysIdPoolEnumerator<TVal, THasher>::findNext()
0541 {
0542     //
0543     //  If there is a current element, move to its next element. If this
0544     //  hits the end of the bucket, the next block will handle the rest.
0545     //
0546     if (fCurElem)
0547         fCurElem = fCurElem->fNext;
0548
0549     //
0550     //  If the current element is null, then we have to move up to the
0551     //  next hash value. If that is the hash modulus, then we cannot
0552     //  go further.
0553     //
0554     if (!fCurElem)
0555     {
0556         fCurHash++;
0557         if (fCurHash == fToEnum->fHashModulus)
0558             return;
0559
0560         // Else find the next non-empty bucket
0561         while (fToEnum->fBucketList[fCurHash]==0)
0562         {
0563             // Bump to the next hash value. If we max out return
0564             fCurHash++;
0565             if (fCurHash == fToEnum->fHashModulus)
0566                 return;
0567         }
0568         fCurElem = fToEnum->fBucketList[fCurHash];
0569     }
0570 }
0571
0572 XERCES_CPP_NAMESPACE_END