GME  13
DOMNodeIDMap.cpp
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 
00018 /*
00019  * $Id: DOMNodeIDMap.cpp 678144 2008-07-19 12:08:55Z borisk $
00020  */
00021 
00022 #include "DOMAttrImpl.hpp"
00023 #include "DOMDocumentImpl.hpp"
00024 #include "DOMNodeIDMap.hpp"
00025 
00026 #include <xercesc/util/XMLString.hpp>
00027 #include <xercesc/util/RuntimeException.hpp>
00028 #include <stdio.h>
00029 
00030 XERCES_CPP_NAMESPACE_BEGIN
00031 
00032 
00033 static const XMLSize_t gPrimes[] = {997, 9973, 99991, 999983, 0 };  // To do - add a few more.
00034 
00035 static const float gMaxFill = 0.8f;   // The maximum fraction of the total
00036                                     // table entries to consume before exanding.
00037 
00038 DOMNodeIDMap::DOMNodeIDMap(XMLSize_t initialSize, DOMDocument *doc)
00039 : fNumEntries(0)
00040 , fDoc(doc)
00041 {
00042     for (fSizeIndex = 0; gPrimes[fSizeIndex] < initialSize; fSizeIndex++)
00043     {
00044         if (gPrimes[fSizeIndex] == 0)
00045         {
00046             // We need a bigger size than the largest available one.
00047             //   Big trouble.
00048             fSizeIndex--;
00049             ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::NodeIDMap_GrowErr, ((DOMDocumentImpl *)fDoc)->getMemoryManager());
00050         }
00051     }
00052 
00053     fSize = gPrimes[fSizeIndex];
00054     fMaxEntries = (XMLSize_t)(float(fSize) * gMaxFill);
00055 
00056     //fTable = new (fDoc) DOMAttr*[fSize];
00057     fTable = (DOMAttr**) ((DOMDocumentImpl *)fDoc)->allocate(sizeof(DOMAttr*) * fSize);
00058     XMLSize_t i;
00059     for (i=0; i<fSize; i++)
00060         fTable[i] = 0;
00061 }
00062 
00063 
00064 DOMNodeIDMap::~DOMNodeIDMap()
00065 {
00066     // don't delete - the document owns the storage.
00067     fTable = 0;
00068 }
00069 
00070 
00071 
00072 void DOMNodeIDMap::add(DOMAttr *attr)
00073 {
00074         //
00075         //  If the table is getting too full, grow it.  We arbitrarily limit
00076         //   the table to 80 full, which should limit the average number of
00077         //   rehashes to a reasonable value.
00078         //
00079         if (fNumEntries >= fMaxEntries)
00080                 growTable();
00081 
00082         fNumEntries++;
00083 
00084         //
00085         // Hash the value string from the ID attribute being added to the table
00086         //      0 < Initial hash value < table size.
00087         //      An initial hash of zero would cause the rehash to fail.
00088         //
00089         const XMLCh *id=attr->getValue();
00090         XMLSize_t initalHash = XMLString::hash(id, fSize-1);
00091         initalHash++;
00092         XMLSize_t currentHash = initalHash;
00093 
00094         //
00095         // Loop looking for an empty slot for this ID.
00096         //   Don't even bother checking to see if the ID is already there -
00097         //   the table is only filled by the parser from valid documents, which
00098         //   can not have duplicates.  Behavior of invalid docs is not defined.
00099         //
00100     while (fTable[currentHash]!=0 && fTable[currentHash]!=(DOMAttr *)-1)
00101         {
00102                 currentHash += initalHash;  // rehash
00103         if (currentHash >= fSize)
00104             currentHash = currentHash % fSize;
00105     }
00106 
00107     //
00108     // We've found our slot.  Stick the pointer to the attr into it.
00109     //
00110     fTable[currentHash] = attr;
00111 
00112 }
00113 
00114 
00115 void DOMNodeIDMap::remove(DOMAttr *attr)
00116 {
00117     //
00118         // Hash the value string from the ID attribute being added to the table
00119         //      0 < Initial hash value < table size.
00120         //      An initial hash of zero would cause the rehash to fail.
00121         //
00122         const XMLCh *id=attr->getValue();
00123         XMLSize_t initalHash = XMLString::hash(id, fSize-1);
00124         initalHash++;
00125         XMLSize_t currentHash = initalHash;
00126 
00127         //
00128         // Loop looking for a slot pointing to an attr with this id.
00129     //
00130         DOMAttr *tableSlot;
00131     while ((tableSlot= fTable[currentHash])!=0)
00132         {
00133         if (tableSlot == attr)
00134         {
00135             //  Found the attribute.  Set the slot to -1 to indicate
00136             //   that it was once used, meaning that lookups, while never
00137             //   matching here, can not stop either, but must rehash again
00138             //   and continue searching.
00139             fTable[currentHash] = (DOMAttr *)-1;
00140             return;
00141         }
00142 
00143         currentHash += initalHash;  // rehash.
00144         if (currentHash >= fSize)
00145             currentHash = currentHash % fSize;
00146     }
00147     // There is no matching entry in the table
00148 }
00149 
00150 
00151 DOMAttr *DOMNodeIDMap::find(const XMLCh *id)
00152 {
00153     //
00154     //  Get the hashcode for the supplied string.
00155     //
00156     XMLSize_t initalHash = XMLString::hash(id, fSize-1);
00157         initalHash++;
00158         XMLSize_t currentHash = initalHash;
00159 
00160         //
00161         // Loop looking for a slot pointing to an attr with this id.
00162     //
00163         DOMAttr *tableSlot;
00164     while ((tableSlot= fTable[currentHash])!=0)
00165         {
00166         if ((tableSlot != (DOMAttr *)-1) && XMLString::equals(tableSlot->getValue(), id))
00167             return tableSlot;
00168 
00169         currentHash += initalHash;  // rehash
00170         if (currentHash >= fSize)
00171             currentHash = currentHash % fSize;
00172     }
00173     // There is no matching entry in the table
00174     return 0;
00175 }
00176 
00177 
00178 //
00179 //  Grow the table to the next larger size.
00180 //      It has gotten too full for efficient operation.
00181 //     (We never fill it all the way)
00182 //
00183 void DOMNodeIDMap::growTable()
00184 {
00185     DOMAttr     **oldTable = fTable;
00186     XMLSize_t oldSize  = fSize;
00187 
00188     //
00189     //  Figure the new table size.
00190     //
00191 #if defined(XERCES_DEBUG)
00192     fprintf(stderr, "growing...\n");
00193 #endif
00194     fSizeIndex++;
00195     fSize = gPrimes[fSizeIndex];
00196     if (fSize == 0)
00197     {
00198         // We need to grow bigger than the largest available size.
00199         //   Big trouble.
00200         fSizeIndex--;
00201         ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::NodeIDMap_GrowErr, ((DOMDocumentImpl *)fDoc)->getMemoryManager());
00202     }
00203 
00204     //
00205     //  Allocate the new table.
00206     //
00207     //fTable = new (fDoc) DOMAttr *[fSize];
00208     fTable = (DOMAttr**) ((DOMDocumentImpl *)fDoc)->allocate(sizeof(DOMAttr*) * fSize);
00209     XMLSize_t i;
00210     for (i=0; i<fSize; i++)
00211         fTable[i] = 0;
00212 
00213     fMaxEntries = (XMLSize_t)(float(fSize) * gMaxFill);
00214 
00215     //
00216     // Move entries over from the old table to the new one.
00217     //
00218     for (i=0; i<oldSize; i++)
00219     {
00220         if ((oldTable[i] != 0)  &&  (oldTable[i] != (DOMAttr *)-1))
00221             add(oldTable[i]);
00222     }
00223 
00224     // delete [] oldTable;   (The document owns the storage.  The old table will just
00225     //                        need to leak until until the document is discarded.)
00226 
00227 }
00228 
00229 
00230 XERCES_CPP_NAMESPACE_END