source: icXML/icXML-devel/src/xercesc/dom/impl/DOMNodeIDMap.cpp @ 2777

Last change on this file since 2777 was 2777, checked in by cameron, 7 years ago

Set up to use xercesc/icxercesc root-relative paths for all includes

File size: 6.6 KB
Line 
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements.  See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License.  You may obtain a copy of the License at
8 *
9 *      http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18/*
19 * $Id: DOMNodeIDMap.cpp 678144 2008-07-19 12:08:55Z borisk $
20 */
21
22#include <xercesc/dom/impl/DOMAttrImpl.hpp>
23#include <xercesc/dom/impl/DOMDocumentImpl.hpp>
24#include <xercesc/dom/impl/DOMNodeIDMap.hpp>
25
26#include <icxercesc/util/XMLString.hpp>
27#include <xercesc/util/RuntimeException.hpp>
28#include <stdio.h>
29
30XERCES_CPP_NAMESPACE_BEGIN
31
32
33static const XMLSize_t gPrimes[] = {997, 9973, 99991, 999983, 0 };  // To do - add a few more.
34
35static const float gMaxFill = 0.8f;   // The maximum fraction of the total
36                                    // table entries to consume before exanding.
37
38DOMNodeIDMap::DOMNodeIDMap(XMLSize_t initialSize, DOMDocument *doc)
39: fNumEntries(0)
40, fDoc(doc)
41{
42    for (fSizeIndex = 0; gPrimes[fSizeIndex] < initialSize; fSizeIndex++)
43    {
44        if (gPrimes[fSizeIndex] == 0)
45        {
46            // We need a bigger size than the largest available one.
47            //   Big trouble.
48            fSizeIndex--;
49            ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::NodeIDMap_GrowErr, ((DOMDocumentImpl *)fDoc)->getMemoryManager());
50        }
51    }
52
53    fSize = gPrimes[fSizeIndex];
54    fMaxEntries = (XMLSize_t)(float(fSize) * gMaxFill);
55
56    //fTable = new (fDoc) DOMAttr*[fSize];
57    fTable = (DOMAttr**) ((DOMDocumentImpl *)fDoc)->allocate(sizeof(DOMAttr*) * fSize);
58    XMLSize_t i;
59    for (i=0; i<fSize; i++)
60        fTable[i] = 0;
61}
62
63
64DOMNodeIDMap::~DOMNodeIDMap()
65{
66    // don't delete - the document owns the storage.
67    fTable = 0;
68}
69
70
71
72void DOMNodeIDMap::add(DOMAttr *attr)
73{
74        //
75        //  If the table is getting too full, grow it.  We arbitrarily limit
76        //   the table to 80 full, which should limit the average number of
77        //   rehashes to a reasonable value.
78        //
79        if (fNumEntries >= fMaxEntries)
80                growTable();
81
82        fNumEntries++;
83
84        //
85        // Hash the value string from the ID attribute being added to the table
86        //      0 < Initial hash value < table size.
87        //      An initial hash of zero would cause the rehash to fail.
88        //
89        const XMLCh *id=attr->getValue();
90        XMLSize_t initalHash = XMLString::hash(id, fSize-1);
91        initalHash++;
92        XMLSize_t currentHash = initalHash;
93
94        //
95        // Loop looking for an empty slot for this ID.
96        //   Don't even bother checking to see if the ID is already there -
97        //   the table is only filled by the parser from valid documents, which
98        //   can not have duplicates.  Behavior of invalid docs is not defined.
99        //
100    while (fTable[currentHash]!=0 && fTable[currentHash]!=(DOMAttr *)-1)
101        {
102                currentHash += initalHash;  // rehash
103        if (currentHash >= fSize)
104            currentHash = currentHash % fSize;
105    }
106
107    //
108    // We've found our slot.  Stick the pointer to the attr into it.
109    //
110    fTable[currentHash] = attr;
111
112}
113
114
115void DOMNodeIDMap::remove(DOMAttr *attr)
116{
117    //
118        // Hash the value string from the ID attribute being added to the table
119        //      0 < Initial hash value < table size.
120        //      An initial hash of zero would cause the rehash to fail.
121        //
122        const XMLCh *id=attr->getValue();
123        XMLSize_t initalHash = XMLString::hash(id, fSize-1);
124        initalHash++;
125        XMLSize_t currentHash = initalHash;
126
127        //
128        // Loop looking for a slot pointing to an attr with this id.
129    //
130        DOMAttr *tableSlot;
131    while ((tableSlot= fTable[currentHash])!=0)
132        {
133        if (tableSlot == attr)
134        {
135            //  Found the attribute.  Set the slot to -1 to indicate
136            //   that it was once used, meaning that lookups, while never
137            //   matching here, can not stop either, but must rehash again
138            //   and continue searching.
139            fTable[currentHash] = (DOMAttr *)-1;
140            return;
141        }
142
143        currentHash += initalHash;  // rehash.
144        if (currentHash >= fSize)
145            currentHash = currentHash % fSize;
146    }
147    // There is no matching entry in the table
148}
149
150
151DOMAttr *DOMNodeIDMap::find(const XMLCh *id)
152{
153    //
154    //  Get the hashcode for the supplied string.
155    //
156    XMLSize_t initalHash = XMLString::hash(id, fSize-1);
157        initalHash++;
158        XMLSize_t currentHash = initalHash;
159
160        //
161        // Loop looking for a slot pointing to an attr with this id.
162    //
163        DOMAttr *tableSlot;
164    while ((tableSlot= fTable[currentHash])!=0)
165        {
166        if ((tableSlot != (DOMAttr *)-1) && XMLString::equals(tableSlot->getValue(), id))
167            return tableSlot;
168
169        currentHash += initalHash;  // rehash
170        if (currentHash >= fSize)
171            currentHash = currentHash % fSize;
172    }
173    // There is no matching entry in the table
174    return 0;
175}
176
177
178//
179//  Grow the table to the next larger size.
180//      It has gotten too full for efficient operation.
181//     (We never fill it all the way)
182//
183void DOMNodeIDMap::growTable()
184{
185    DOMAttr     **oldTable = fTable;
186    XMLSize_t oldSize  = fSize;
187
188    //
189    //  Figure the new table size.
190    //
191#if defined(XERCES_DEBUG)
192    fprintf(stderr, "growing...\n");
193#endif
194    fSizeIndex++;
195    fSize = gPrimes[fSizeIndex];
196    if (fSize == 0)
197    {
198        // We need to grow bigger than the largest available size.
199        //   Big trouble.
200        fSizeIndex--;
201        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::NodeIDMap_GrowErr, ((DOMDocumentImpl *)fDoc)->getMemoryManager());
202    }
203
204    //
205    //  Allocate the new table.
206    //
207    //fTable = new (fDoc) DOMAttr *[fSize];
208    fTable = (DOMAttr**) ((DOMDocumentImpl *)fDoc)->allocate(sizeof(DOMAttr*) * fSize);
209    XMLSize_t i;
210    for (i=0; i<fSize; i++)
211        fTable[i] = 0;
212
213    fMaxEntries = (XMLSize_t)(float(fSize) * gMaxFill);
214
215    //
216    // Move entries over from the old table to the new one.
217    //
218    for (i=0; i<oldSize; i++)
219    {
220        if ((oldTable[i] != 0)  &&  (oldTable[i] != (DOMAttr *)-1))
221            add(oldTable[i]);
222    }
223
224    // delete [] oldTable;   (The document owns the storage.  The old table will just
225    //                        need to leak until until the document is discarded.)
226
227}
228
229
230XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.