dom/impl/DOMDeepNodeListPool.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 #include <xercesc/util/XercesDefs.hpp>
0027 #if defined(XERCES_TMPLSINC)
0028 #include <xercesc/dom/impl/DOMDeepNodeListPool.hpp>
0029 #endif
0030
0031 #include <assert.h>
0032
0033 XERCES_CPP_NAMESPACE_BEGIN
0034
0035
0036
0037 // ---------------------------------------------------------------------------
0038 //  DOMDeepNodeListPool: Constructors and Destructor
0039 // ---------------------------------------------------------------------------
0040 template <class TVal, class THasher>
0041 DOMDeepNodeListPool<TVal, THasher>::DOMDeepNodeListPool( const XMLSize_t modulus
0042                                               , const bool adoptElems
0043                                               , const XMLSize_t initSize) :
0044     fAdoptedElems(adoptElems)
0045     , fBucketList(0)
0046     , fHashModulus(modulus)
0047     , fIdPtrs(0)
0048     , fIdPtrsCount(initSize)
0049     , fIdCounter(0)
0050     , fMemoryManager(XMLPlatformUtils::fgMemoryManager)
0051 {
0052     initialize(modulus);
0053
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
0062     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*));//new TVal*[fIdPtrsCount];
0063     fIdPtrs[0] = 0;
0064 }
0065
0066 template <class TVal, class THasher>
0067 DOMDeepNodeListPool<TVal, THasher>::DOMDeepNodeListPool( const XMLSize_t modulus
0068                                               , const bool adoptElems
0069                                               , const THasher& hasher
0070                                               , const XMLSize_t initSize) :
0071     fAdoptedElems(adoptElems)
0072     , fBucketList(0)
0073     , fHashModulus(modulus)
0074     , fIdPtrs(0)
0075     , fIdPtrsCount(initSize)
0076     , fIdCounter(0)
0077     , fMemoryManager(XMLPlatformUtils::fgMemoryManager)
0078     , fHasher(hasher)
0079 {
0080     initialize(modulus);
0081
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
0090     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*));//new TVal*[fIdPtrsCount];
0091     fIdPtrs[0] = 0;
0092 }
0093
0094 template <class TVal, class THasher>
0095 DOMDeepNodeListPool<TVal, THasher>::DOMDeepNodeListPool( const XMLSize_t modulus
0096                                               , const XMLSize_t initSize) :
0097     fAdoptedElems(true)
0098     , fBucketList(0)
0099     , fHashModulus(modulus)
0100     , fIdPtrs(0)
0101     , fIdPtrsCount(initSize)
0102     , fIdCounter(0)
0103     , fMemoryManager(XMLPlatformUtils::fgMemoryManager)
0104 {
0105     initialize(modulus);
0106
0107     //
0108     //  Allocate the initial id pointers array. We don't have to zero them
0109     //  out since the fIdCounter value tells us which ones are valid. The
0110     //  zeroth element is never used (and represents an invalid pool id.)
0111     //
0112     if (!fIdPtrsCount)
0113         fIdPtrsCount = 256;
0114
0115     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*));//new TVal*[fIdPtrsCount];
0116     fIdPtrs[0] = 0;
0117 }
0118
0119 template <class TVal, class THasher>
0120 void DOMDeepNodeListPool<TVal, THasher>::initialize(const XMLSize_t modulus)
0121 {
0122     if (modulus == 0)
0123         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
0124
0125     // Allocate the bucket list and zero them
0126     fBucketList = (DOMDeepNodeListPoolTableBucketElem<TVal>**)
0127         fMemoryManager->allocate
0128         (
0129             fHashModulus * sizeof(DOMDeepNodeListPoolTableBucketElem<TVal>*)
0130         );//new DOMDeepNodeListPoolTableBucketElem<TVal>*[fHashModulus];
0131     for (XMLSize_t index = 0; index < fHashModulus; index++)
0132         fBucketList[index] = 0;
0133 }
0134
0135 template <class TVal, class THasher>
0136 DOMDeepNodeListPool<TVal, THasher>::~DOMDeepNodeListPool()
0137 {
0138     removeAll();
0139
0140     // Then delete the bucket list & hasher & id pointers list
0141     fMemoryManager->deallocate(fIdPtrs);//delete [] fIdPtrs;
0142     fMemoryManager->deallocate(fBucketList);//delete [] fBucketList;
0143 }
0144
0145
0146 // ---------------------------------------------------------------------------
0147 //  DOMDeepNodeListPool: Element management
0148 // ---------------------------------------------------------------------------
0149 template <class TVal, class THasher>
0150 bool DOMDeepNodeListPool<TVal, THasher>::isEmpty() const
0151 {
0152     // Just check the bucket list for non-empty elements
0153     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0154     {
0155         if (fBucketList[buckInd] != 0)
0156             return false;
0157     }
0158     return true;
0159 }
0160
0161 template <class TVal, class THasher>
0162 bool DOMDeepNodeListPool<TVal, THasher>::containsKey( const void* const key1
0163                                            , const XMLCh* const key2
0164                                            , const XMLCh* const key3) const
0165 {
0166     XMLSize_t hashVal;
0167     const DOMDeepNodeListPoolTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
0168     return (findIt != 0);
0169 }
0170
0171 template <class TVal, class THasher>
0172 void DOMDeepNodeListPool<TVal, THasher>::removeAll()
0173 {
0174     if (fIdCounter == 0) return;
0175
0176     // Clean up the buckets first
0177     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
0178     {
0179         // Get the bucket list head for this entry
0180         DOMDeepNodeListPoolTableBucketElem<TVal>* curElem = fBucketList[buckInd];
0181         DOMDeepNodeListPoolTableBucketElem<TVal>* nextElem;
0182         while (curElem)
0183         {
0184             // Save the next element before we hose this one
0185             nextElem = curElem->fNext;
0186
0187             // If we adopted the data, then delete it too
0188             //    (Note:  the userdata hash table instance has data type of void *.
0189             //    This will generate compiler warnings here on some platforms, but they
0190             //    can be ignored since fAdoptedElements is false.
0191             if (fAdoptedElems)
0192                 delete curElem->fData;
0193
0194             // Then delete the current element and move forward
0195             fMemoryManager->deallocate(curElem->fKey2);//delete [] curElem->fKey2;
0196             fMemoryManager->deallocate(curElem->fKey3);//delete [] curElem->fKey3;
0197
0198             delete curElem;
0199             curElem = nextElem;
0200         }
0201
0202         // Clean out this entry
0203         fBucketList[buckInd] = 0;
0204     }
0205
0206     // Reset the id counter
0207     fIdCounter = 0;
0208 }
0209
0210 template <class TVal, class THasher>
0211 void DOMDeepNodeListPool<TVal, THasher>::cleanup()
0212 {
0213     removeAll();
0214
0215     // Then delete the bucket list & hasher & id pointers list
0216     fMemoryManager->deallocate(fIdPtrs);//delete [] fIdPtrs;
0217     fMemoryManager->deallocate(fBucketList);//delete [] fBucketList;
0218 }
0219
0220
0221
0222 // ---------------------------------------------------------------------------
0223 //  DOMDeepNodeListPool: Getters
0224 // ---------------------------------------------------------------------------
0225 template <class TVal, class THasher>
0226 TVal*
0227 DOMDeepNodeListPool<TVal, THasher>::getByKey(const void* const key1, const XMLCh* const key2, const XMLCh* const key3)
0228 {
0229     XMLSize_t hashVal;
0230     DOMDeepNodeListPoolTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
0231     if (!findIt)
0232         return 0;
0233     return findIt->fData;
0234 }
0235
0236 template <class TVal, class THasher>
0237 const TVal*
0238 DOMDeepNodeListPool<TVal, THasher>::getByKey(const void* const key1, const XMLCh* const key2, const XMLCh* const key3) const
0239 {
0240     XMLSize_t hashVal;
0241     const DOMDeepNodeListPoolTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
0242     if (!findIt)
0243         return 0;
0244     return findIt->fData;
0245 }
0246
0247 template <class TVal, class THasher>
0248 TVal*
0249 DOMDeepNodeListPool<TVal, THasher>::getById(const XMLSize_t elemId)
0250 {
0251     // If its either zero or beyond our current id, its an error
0252     if (!elemId || (elemId > fIdCounter))
0253         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
0254
0255     return fIdPtrs[elemId];
0256 }
0257
0258 template <class TVal, class THasher>
0259 const TVal*
0260 DOMDeepNodeListPool<TVal, THasher>::getById(const XMLSize_t elemId) const
0261 {
0262     // If its either zero or beyond our current id, its an error
0263     if (!elemId || (elemId > fIdCounter))
0264         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
0265
0266     return fIdPtrs[elemId];
0267 }
0268
0269 // ---------------------------------------------------------------------------
0270 //  DOMDeepNodeListPool: Putters
0271 // ---------------------------------------------------------------------------
0272 template <class TVal, class THasher>
0273 XMLSize_t
0274 DOMDeepNodeListPool<TVal, THasher>::put(void* key1, XMLCh* key2, XMLCh* key3, TVal* const valueToAdopt)
0275 {
0276     // First see if the key exists already
0277     XMLSize_t hashVal;
0278     DOMDeepNodeListPoolTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, key3, hashVal);
0279
0280     //
0281     //  If so,then update its value. If not, then we need to add it to
0282     //  the right bucket
0283     //
0284     if (newBucket)
0285     {
0286         if (fAdoptedElems)
0287             delete newBucket->fData;
0288
0289         fMemoryManager->deallocate(newBucket->fKey2);//delete[] newBucket->fKey2;
0290         fMemoryManager->deallocate(newBucket->fKey3);//delete[] newBucket->fKey3;
0291
0292         newBucket->fData = valueToAdopt;
0293         newBucket->fKey1 = key1;
0294         newBucket->fKey2 = XMLString::replicate(key2, fMemoryManager);
0295         newBucket->fKey3 = XMLString::replicate(key3, fMemoryManager);
0296     }
0297     else
0298     {
0299     // Revisit: the gcc compiler 2.95.x is generating an
0300     // internal compiler error message. So we use the default
0301     // memory manager for now.
0302 #if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
0303         newBucket = new DOMDeepNodeListPoolTableBucketElem<TVal>
0304         (
0305             key1
0306             , key2
0307             , key3
0308             , valueToAdopt
0309             , fBucketList[hashVal]
0310             , fMemoryManager
0311         );
0312 #else
0313         newBucket = new (fMemoryManager) DOMDeepNodeListPoolTableBucketElem<TVal>
0314         (
0315             key1
0316             , key2
0317             , key3
0318             , valueToAdopt
0319             , fBucketList[hashVal]
0320             , fMemoryManager
0321         );
0322 #endif
0323         fBucketList[hashVal] = newBucket;
0324     }
0325
0326     //
0327     //  Give this new one the next available id and add to the pointer list.
0328     //  Expand the list if that is now required.
0329     //
0330     if (fIdCounter + 1 == fIdPtrsCount)
0331     {
0332         // Create a new count 1.5 times larger and allocate a new array
0333         XMLSize_t newCount = (XMLSize_t)(fIdPtrsCount * 1.5);
0334         TVal** newArray = (TVal**) fMemoryManager->allocate
0335         (
0336             newCount * sizeof(TVal*)
0337         );//new TVal*[newCount];
0338
0339         // Copy over the old contents to the new array
0340         memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TVal*));
0341
0342         // Ok, toss the old array and store the new data
0343         fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
0344         fIdPtrs = newArray;
0345         fIdPtrsCount = newCount;
0346     }
0347     const XMLSize_t retId = ++fIdCounter;
0348     fIdPtrs[retId] = valueToAdopt;
0349
0350     // Return the id that we gave to this element
0351     return retId;
0352 }
0353
0354 // ---------------------------------------------------------------------------
0355 //  DOMDeepNodeListPool: Private methods
0356 // ---------------------------------------------------------------------------
0357 template <class TVal, class THasher>
0358 DOMDeepNodeListPoolTableBucketElem<TVal>* DOMDeepNodeListPool<TVal, THasher>::
0359 findBucketElem(const void* const key1, const XMLCh* const key2, const XMLCh* const key3, 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     DOMDeepNodeListPoolTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0367     while (curElem)
0368     {
0369         //key2 and key3 are XMLCh*, compareString takes null pointer vs zero len string the same
0370         //but we need them to be treated as different keys in this case
0371         if (fHasher.equals(key1, curElem->fKey1) && (XMLString::equals(key2, curElem->fKey2)) && (XMLString::equals(key3, curElem->fKey3))) {
0372             if (!key2 || !curElem->fKey2) {
0373                 if (key2 || curElem->fKey2) {
0374                     curElem = curElem->fNext;
0375                     continue;
0376                 }
0377             }
0378             if (!key3 || !curElem->fKey3) {
0379                 if (key3 || curElem->fKey3) {
0380                     curElem = curElem->fNext;
0381                     continue;
0382                 }
0383             }
0384
0385             return curElem;
0386         }
0387
0388         curElem = curElem->fNext;
0389     }
0390     return 0;
0391 }
0392
0393 template <class TVal, class THasher>
0394 const DOMDeepNodeListPoolTableBucketElem<TVal>* DOMDeepNodeListPool<TVal, THasher>::
0395 findBucketElem(const void* const key1, const XMLCh* const key2, const XMLCh* const key3, XMLSize_t& hashVal) const
0396 {
0397     // Hash the key
0398     hashVal = fHasher.getHashVal(key1, fHashModulus);
0399     assert(hashVal < fHashModulus);
0400
0401     // Search that bucket for the key
0402     const DOMDeepNodeListPoolTableBucketElem<TVal>* curElem = fBucketList[hashVal];
0403     while (curElem)
0404     {
0405         //key2 and key3 are XMLCh*, compareString takes null pointer vs zero len string the same
0406         //but we need them to be treated as different keys in this case
0407         if (fHasher.equals(key1, curElem->fKey1) && (XMLString::equals(key2, curElem->fKey2)) && (XMLString::equals(key3, curElem->fKey3))) {
0408             if (!key2 || !curElem->fKey2) {
0409                 if (key2 || curElem->fKey2) {
0410                     curElem = curElem->fNext;
0411                     continue;
0412                 }
0413             }
0414             if (!key3 || !curElem->fKey3) {
0415                 if (key3 || curElem->fKey3) {
0416                     curElem = curElem->fNext;
0417                     continue;
0418                 }
0419             }
0420             return curElem;
0421         }
0422
0423         curElem = curElem->fNext;
0424     }
0425     return 0;
0426 }
0427
0428 XERCES_CPP_NAMESPACE_END