GME  13
DOMDeepNodeListPool.c
Go to the documentation of this file.
00001 /*
00002  * Licensed to the Apache Software Foundation (ASF) under one or more
00003  * contributor license agreements.  See the NOTICE file distributed with
00004  * this work for additional information regarding copyright ownership.
00005  * The ASF licenses this file to You under the Apache License, Version 2.0
00006  * (the "License"); you may not use this file except in compliance with
00007  * the License.  You may obtain a copy of the License at
00008  *
00009  *      http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 
00023 // ---------------------------------------------------------------------------
00024 //  Include
00025 // ---------------------------------------------------------------------------
00026 #include <xercesc/util/XercesDefs.hpp>
00027 #if defined(XERCES_TMPLSINC)
00028 #include <xercesc/dom/impl/DOMDeepNodeListPool.hpp>
00029 #endif
00030 
00031 #include <assert.h>
00032 
00033 XERCES_CPP_NAMESPACE_BEGIN
00034 
00035 
00036 
00037 // ---------------------------------------------------------------------------
00038 //  DOMDeepNodeListPool: Constructors and Destructor
00039 // ---------------------------------------------------------------------------
00040 template <class TVal, class THasher>
00041 DOMDeepNodeListPool<TVal, THasher>::DOMDeepNodeListPool( const XMLSize_t modulus
00042                                               , const bool adoptElems
00043                                               , const XMLSize_t initSize) :
00044     fAdoptedElems(adoptElems)
00045     , fBucketList(0)
00046     , fHashModulus(modulus)
00047     , fIdPtrs(0)
00048     , fIdPtrsCount(initSize)
00049     , fIdCounter(0)
00050     , fMemoryManager(XMLPlatformUtils::fgMemoryManager)
00051 {
00052     initialize(modulus);
00053 
00054     //
00055     //  Allocate the initial id pointers array. We don't have to zero them
00056     //  out since the fIdCounter value tells us which ones are valid. The
00057     //  zeroth element is never used (and represents an invalid pool id.)
00058     //
00059     if (!fIdPtrsCount)
00060         fIdPtrsCount = 256;
00061 
00062     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*));//new TVal*[fIdPtrsCount];
00063     fIdPtrs[0] = 0;
00064 }
00065 
00066 template <class TVal, class THasher>
00067 DOMDeepNodeListPool<TVal, THasher>::DOMDeepNodeListPool( const XMLSize_t modulus
00068                                               , const bool adoptElems
00069                                               , const THasher& hasher
00070                                               , const XMLSize_t initSize) :
00071     fAdoptedElems(adoptElems)
00072     , fBucketList(0)
00073     , fHashModulus(modulus)
00074     , fIdPtrs(0)
00075     , fIdPtrsCount(initSize)
00076     , fIdCounter(0)
00077     , fMemoryManager(XMLPlatformUtils::fgMemoryManager)
00078     , fHasher(hasher)
00079 {
00080     initialize(modulus);
00081 
00082     //
00083     //  Allocate the initial id pointers array. We don't have to zero them
00084     //  out since the fIdCounter value tells us which ones are valid. The
00085     //  zeroth element is never used (and represents an invalid pool id.)
00086     //
00087     if (!fIdPtrsCount)
00088         fIdPtrsCount = 256;
00089 
00090     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*));//new TVal*[fIdPtrsCount];
00091     fIdPtrs[0] = 0;
00092 }
00093 
00094 template <class TVal, class THasher>
00095 DOMDeepNodeListPool<TVal, THasher>::DOMDeepNodeListPool( const XMLSize_t modulus
00096                                               , const XMLSize_t initSize) :
00097     fAdoptedElems(true)
00098     , fBucketList(0)
00099     , fHashModulus(modulus)
00100     , fIdPtrs(0)
00101     , fIdPtrsCount(initSize)
00102     , fIdCounter(0)
00103     , fMemoryManager(XMLPlatformUtils::fgMemoryManager)
00104 {
00105     initialize(modulus);
00106 
00107     //
00108     //  Allocate the initial id pointers array. We don't have to zero them
00109     //  out since the fIdCounter value tells us which ones are valid. The
00110     //  zeroth element is never used (and represents an invalid pool id.)
00111     //
00112     if (!fIdPtrsCount)
00113         fIdPtrsCount = 256;
00114 
00115     fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*));//new TVal*[fIdPtrsCount];
00116     fIdPtrs[0] = 0;
00117 }
00118 
00119 template <class TVal, class THasher>
00120 void DOMDeepNodeListPool<TVal, THasher>::initialize(const XMLSize_t modulus)
00121 {
00122         if (modulus == 0)
00123         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
00124 
00125     // Allocate the bucket list and zero them
00126     fBucketList = (DOMDeepNodeListPoolTableBucketElem<TVal>**)
00127         fMemoryManager->allocate
00128         (
00129             fHashModulus * sizeof(DOMDeepNodeListPoolTableBucketElem<TVal>*)
00130         );//new DOMDeepNodeListPoolTableBucketElem<TVal>*[fHashModulus];
00131     for (XMLSize_t index = 0; index < fHashModulus; index++)
00132         fBucketList[index] = 0;
00133 }
00134 
00135 template <class TVal, class THasher>
00136 DOMDeepNodeListPool<TVal, THasher>::~DOMDeepNodeListPool()
00137 {
00138     removeAll();
00139 
00140     // Then delete the bucket list & hasher & id pointers list
00141     fMemoryManager->deallocate(fIdPtrs);//delete [] fIdPtrs;
00142     fMemoryManager->deallocate(fBucketList);//delete [] fBucketList;
00143 }
00144 
00145 
00146 // ---------------------------------------------------------------------------
00147 //  DOMDeepNodeListPool: Element management
00148 // ---------------------------------------------------------------------------
00149 template <class TVal, class THasher>
00150 bool DOMDeepNodeListPool<TVal, THasher>::isEmpty() const
00151 {
00152     // Just check the bucket list for non-empty elements
00153     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
00154     {
00155         if (fBucketList[buckInd] != 0)
00156             return false;
00157     }
00158     return true;
00159 }
00160 
00161 template <class TVal, class THasher>
00162 bool DOMDeepNodeListPool<TVal, THasher>::containsKey( const void* const key1
00163                                            , const XMLCh* const key2
00164                                            , const XMLCh* const key3) const
00165 {
00166     XMLSize_t hashVal;
00167     const DOMDeepNodeListPoolTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
00168     return (findIt != 0);
00169 }
00170 
00171 template <class TVal, class THasher>
00172 void DOMDeepNodeListPool<TVal, THasher>::removeAll()
00173 {
00174     if (fIdCounter == 0) return;
00175 
00176     // Clean up the buckets first
00177     for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
00178     {
00179         // Get the bucket list head for this entry
00180         DOMDeepNodeListPoolTableBucketElem<TVal>* curElem = fBucketList[buckInd];
00181         DOMDeepNodeListPoolTableBucketElem<TVal>* nextElem;
00182         while (curElem)
00183         {
00184             // Save the next element before we hose this one
00185             nextElem = curElem->fNext;
00186 
00187             // If we adopted the data, then delete it too
00188             //    (Note:  the userdata hash table instance has data type of void *.
00189             //    This will generate compiler warnings here on some platforms, but they
00190             //    can be ignored since fAdoptedElements is false.
00191             if (fAdoptedElems)
00192                 delete curElem->fData;
00193 
00194             // Then delete the current element and move forward
00195             fMemoryManager->deallocate(curElem->fKey2);//delete [] curElem->fKey2;
00196             fMemoryManager->deallocate(curElem->fKey3);//delete [] curElem->fKey3;
00197 
00198             delete curElem;
00199             curElem = nextElem;
00200         }
00201 
00202         // Clean out this entry
00203         fBucketList[buckInd] = 0;
00204     }
00205 
00206     // Reset the id counter
00207     fIdCounter = 0;
00208 }
00209 
00210 template <class TVal, class THasher>
00211 void DOMDeepNodeListPool<TVal, THasher>::cleanup()
00212 {
00213     removeAll();
00214 
00215     // Then delete the bucket list & hasher & id pointers list
00216     fMemoryManager->deallocate(fIdPtrs);//delete [] fIdPtrs;
00217     fMemoryManager->deallocate(fBucketList);//delete [] fBucketList;
00218 }
00219 
00220 
00221 
00222 // ---------------------------------------------------------------------------
00223 //  DOMDeepNodeListPool: Getters
00224 // ---------------------------------------------------------------------------
00225 template <class TVal, class THasher>
00226 TVal*
00227 DOMDeepNodeListPool<TVal, THasher>::getByKey(const void* const key1, const XMLCh* const key2, const XMLCh* const key3)
00228 {
00229     XMLSize_t hashVal;
00230     DOMDeepNodeListPoolTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
00231     if (!findIt)
00232         return 0;
00233     return findIt->fData;
00234 }
00235 
00236 template <class TVal, class THasher>
00237 const TVal*
00238 DOMDeepNodeListPool<TVal, THasher>::getByKey(const void* const key1, const XMLCh* const key2, const XMLCh* const key3) const
00239 {
00240     XMLSize_t hashVal;
00241     const DOMDeepNodeListPoolTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
00242     if (!findIt)
00243         return 0;
00244     return findIt->fData;
00245 }
00246 
00247 template <class TVal, class THasher>
00248 TVal*
00249 DOMDeepNodeListPool<TVal, THasher>::getById(const XMLSize_t elemId)
00250 {
00251     // If its either zero or beyond our current id, its an error
00252     if (!elemId || (elemId > fIdCounter))
00253         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
00254 
00255     return fIdPtrs[elemId];
00256 }
00257 
00258 template <class TVal, class THasher>
00259 const TVal*
00260 DOMDeepNodeListPool<TVal, THasher>::getById(const XMLSize_t elemId) const
00261 {
00262     // If its either zero or beyond our current id, its an error
00263     if (!elemId || (elemId > fIdCounter))
00264         ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
00265 
00266     return fIdPtrs[elemId];
00267 }
00268 
00269 // ---------------------------------------------------------------------------
00270 //  DOMDeepNodeListPool: Putters
00271 // ---------------------------------------------------------------------------
00272 template <class TVal, class THasher>
00273 XMLSize_t
00274 DOMDeepNodeListPool<TVal, THasher>::put(void* key1, XMLCh* key2, XMLCh* key3, TVal* const valueToAdopt)
00275 {
00276     // First see if the key exists already
00277     XMLSize_t hashVal;
00278     DOMDeepNodeListPoolTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, key3, hashVal);
00279 
00280     //
00281     //  If so,then update its value. If not, then we need to add it to
00282     //  the right bucket
00283     //
00284     if (newBucket)
00285     {
00286         if (fAdoptedElems)
00287             delete newBucket->fData;
00288 
00289         fMemoryManager->deallocate(newBucket->fKey2);//delete[] newBucket->fKey2;
00290         fMemoryManager->deallocate(newBucket->fKey3);//delete[] newBucket->fKey3;
00291 
00292         newBucket->fData = valueToAdopt;
00293         newBucket->fKey1 = key1;
00294         newBucket->fKey2 = XMLString::replicate(key2, fMemoryManager);
00295         newBucket->fKey3 = XMLString::replicate(key3, fMemoryManager);
00296     }
00297     else
00298     {
00299     // Revisit: the gcc compiler 2.95.x is generating an
00300     // internal compiler error message. So we use the default
00301     // memory manager for now.
00302 #if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
00303         newBucket = new DOMDeepNodeListPoolTableBucketElem<TVal>
00304         (
00305             key1
00306             , key2
00307             , key3
00308             , valueToAdopt
00309             , fBucketList[hashVal]
00310             , fMemoryManager
00311         );
00312 #else
00313         newBucket = new (fMemoryManager) DOMDeepNodeListPoolTableBucketElem<TVal>
00314         (
00315             key1
00316             , key2
00317             , key3
00318             , valueToAdopt
00319             , fBucketList[hashVal]
00320             , fMemoryManager
00321         );
00322 #endif
00323         fBucketList[hashVal] = newBucket;
00324     }
00325 
00326     //
00327     //  Give this new one the next available id and add to the pointer list.
00328     //  Expand the list if that is now required.
00329     //
00330     if (fIdCounter + 1 == fIdPtrsCount)
00331     {
00332         // Create a new count 1.5 times larger and allocate a new array
00333         XMLSize_t newCount = (XMLSize_t)(fIdPtrsCount * 1.5);
00334         TVal** newArray = (TVal**) fMemoryManager->allocate
00335         (
00336             newCount * sizeof(TVal*)
00337         );//new TVal*[newCount];
00338 
00339         // Copy over the old contents to the new array
00340         memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TVal*));
00341 
00342         // Ok, toss the old array and store the new data
00343         fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
00344         fIdPtrs = newArray;
00345         fIdPtrsCount = newCount;
00346     }
00347     const XMLSize_t retId = ++fIdCounter;
00348     fIdPtrs[retId] = valueToAdopt;
00349 
00350     // Return the id that we gave to this element
00351     return retId;
00352 }
00353 
00354 // ---------------------------------------------------------------------------
00355 //  DOMDeepNodeListPool: Private methods
00356 // ---------------------------------------------------------------------------
00357 template <class TVal, class THasher>
00358 DOMDeepNodeListPoolTableBucketElem<TVal>* DOMDeepNodeListPool<TVal, THasher>::
00359 findBucketElem(const void* const key1, const XMLCh* const key2, const XMLCh* const key3, XMLSize_t& hashVal)
00360 {
00361     // Hash the key
00362     hashVal = fHasher.getHashVal(key1, fHashModulus);
00363     assert(hashVal < fHashModulus);
00364 
00365     // Search that bucket for the key
00366     DOMDeepNodeListPoolTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00367     while (curElem)
00368     {
00369         //key2 and key3 are XMLCh*, compareString takes null pointer vs zero len string the same
00370         //but we need them to be treated as different keys in this case
00371         if (fHasher.equals(key1, curElem->fKey1) && (XMLString::equals(key2, curElem->fKey2)) && (XMLString::equals(key3, curElem->fKey3))) {
00372             if (!key2 || !curElem->fKey2) {
00373                 if (key2 || curElem->fKey2) {
00374                     curElem = curElem->fNext;
00375                     continue;
00376                 }
00377             }
00378             if (!key3 || !curElem->fKey3) {
00379                 if (key3 || curElem->fKey3) {
00380                     curElem = curElem->fNext;
00381                     continue;
00382                 }
00383             }
00384 
00385             return curElem;
00386         }
00387 
00388         curElem = curElem->fNext;
00389     }
00390     return 0;
00391 }
00392 
00393 template <class TVal, class THasher>
00394 const DOMDeepNodeListPoolTableBucketElem<TVal>* DOMDeepNodeListPool<TVal, THasher>::
00395 findBucketElem(const void* const key1, const XMLCh* const key2, const XMLCh* const key3, XMLSize_t& hashVal) const
00396 {
00397     // Hash the key
00398     hashVal = fHasher.getHashVal(key1, fHashModulus);
00399     assert(hashVal < fHashModulus);
00400 
00401     // Search that bucket for the key
00402     const DOMDeepNodeListPoolTableBucketElem<TVal>* curElem = fBucketList[hashVal];
00403     while (curElem)
00404     {
00405         //key2 and key3 are XMLCh*, compareString takes null pointer vs zero len string the same
00406         //but we need them to be treated as different keys in this case
00407         if (fHasher.equals(key1, curElem->fKey1) && (XMLString::equals(key2, curElem->fKey2)) && (XMLString::equals(key3, curElem->fKey3))) {
00408             if (!key2 || !curElem->fKey2) {
00409                 if (key2 || curElem->fKey2) {
00410                     curElem = curElem->fNext;
00411                     continue;
00412                 }
00413             }
00414             if (!key3 || !curElem->fKey3) {
00415                 if (key3 || curElem->fKey3) {
00416                     curElem = curElem->fNext;
00417                     continue;
00418                 }
00419             }
00420             return curElem;
00421         }
00422 
00423         curElem = curElem->fNext;
00424     }
00425     return 0;
00426 }
00427 
00428 XERCES_CPP_NAMESPACE_END