GME
13
|
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