source: icXML/icXML-devel/src/icxercesc/util/ValueHashTableOf.c @ 2721

Last change on this file since 2721 was 2721, checked in by cameron, 6 years ago

Fix imports in icXML modified Xerces files

File size: 13.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: ValueHashTableOf.c 679340 2008-07-24 10:28:29Z borisk $
20 */
21
22
23// ---------------------------------------------------------------------------
24//  Include
25// ---------------------------------------------------------------------------
26#if defined(XERCES_TMPLSINC)
27#include <icxercesc/util/ValueHashTableOf.hpp>
28#endif
29
30#include <xercesc/util/NullPointerException.hpp>
31#include <xercesc/util/Janitor.hpp>
32#include <assert.h>
33#include <new>
34
35XERCES_CPP_NAMESPACE_BEGIN
36
37// ---------------------------------------------------------------------------
38//  ValueHashTableOf: Constructors and Destructor
39// ---------------------------------------------------------------------------
40template <class TVal, class THasher>
41ValueHashTableOf<TVal, THasher>::ValueHashTableOf( const XMLSize_t modulus
42                                                                                                   , const THasher& hasher
43                                                                                                   , MemoryManager* const manager)
44        : fMemoryManager(manager)
45        , fBucketList(0)
46        , fHashModulus(modulus)
47        , fInitialModulus(modulus)
48        , fCount(0)
49        , fHasher(hasher)
50{
51        initialize(modulus);
52}
53
54template <class TVal, class THasher>
55ValueHashTableOf<TVal, THasher>::ValueHashTableOf( const XMLSize_t modulus
56                                                                                                   , MemoryManager* const manager)
57        : fMemoryManager(manager)
58        , fBucketList(0)
59        , fHashModulus(modulus)
60        , fInitialModulus(modulus)
61        , fCount(0)
62        , fHasher()
63{
64        initialize(modulus);
65}
66
67template <class TVal, class THasher>
68void ValueHashTableOf<TVal, THasher>::initialize(const XMLSize_t modulus)
69{
70        if (modulus == 0)
71                ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
72
73        if (likely(fMemoryManager != NULL))
74        {
75                // Allocate the bucket list and zero them
76                fBucketList = (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate
77                (
78                        fHashModulus * sizeof(ValueHashTableBucketElem<TVal>*)
79                ); //new ValueHashTableBucketElem<TVal>*[fHashModulus];
80                memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
81        }
82}
83
84template <class TVal, class THasher>
85ValueHashTableOf<TVal, THasher>::~ValueHashTableOf()
86{
87        removeAll();
88
89        // Then delete the bucket list & hasher
90        fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
91}
92
93
94// ---------------------------------------------------------------------------
95//  ValueHashTableOf: Element management
96// ---------------------------------------------------------------------------
97template <class TVal, class THasher>
98bool ValueHashTableOf<TVal, THasher>::isEmpty() const
99{
100        return fCount==0;
101}
102
103template <class TVal, class THasher>
104bool ValueHashTableOf<TVal, THasher>::
105containsKey(const void* const key) const
106{
107        XMLSize_t hashVal;
108        const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
109        return (findIt != 0);
110}
111
112template <class TVal, class THasher>
113void ValueHashTableOf<TVal, THasher>::
114removeKey(const void* const key)
115{
116        XMLSize_t hashVal;
117        removeBucketElem(key, hashVal);
118}
119
120template <class TVal, class THasher>
121void ValueHashTableOf<TVal, THasher>::removeAll()
122{
123        if(isEmpty())
124                return;
125
126        // Clean up the buckets first
127        for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
128        {
129                // Get the bucket list head for this entry
130                ValueHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
131                ValueHashTableBucketElem<TVal>* nextElem;
132                while (curElem)
133                {
134                        // Save the next element before we hose this one
135                        nextElem = curElem->fNext;
136
137                        // delete the current element and move forward
138                        // destructor is empty...
139                        // curElem->~ValueHashTableBucketElem();
140                        fMemoryManager->deallocate(curElem);
141                        curElem = nextElem;
142                }
143
144                // Clean out this entry
145                fBucketList[buckInd] = 0;
146        }
147        fCount = 0;
148}
149
150
151// ---------------------------------------------------------------------------
152//  ValueHashTableOf: Getters
153// ---------------------------------------------------------------------------
154template <class TVal, class THasher>
155TVal& ValueHashTableOf<TVal, THasher>::get(const void* const key, MemoryManager* const manager)
156{
157        XMLSize_t hashVal;
158        ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
159        if (!findIt)
160                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, manager);
161
162        return findIt->fData;
163}
164
165template <class TVal, class THasher>
166const TVal& ValueHashTableOf<TVal, THasher>::
167get(const void* const key) const
168{
169        XMLSize_t hashVal;
170        const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
171        if (!findIt)
172                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
173
174        return findIt->fData;
175}
176
177
178// ---------------------------------------------------------------------------
179//  ValueHashTableOf: Putters
180// ---------------------------------------------------------------------------
181template <class TVal, class THasher>
182void ValueHashTableOf<TVal, THasher>::put(void* key, const TVal& valueToAdopt)
183{
184        // Apply 0.75 load factor to find threshold.
185        XMLSize_t threshold = fHashModulus * 3 / 4;
186
187        // If we've grown too big, expand the table and rehash.
188        if (fCount >= threshold)
189                rehash();
190
191        // First see if the key exists already
192        XMLSize_t hashVal;
193        ValueHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
194
195        //
196        //  If so,then update its value. If not, then we need to add it to
197        //  the right bucket
198        //
199        if (newBucket)
200        {
201                newBucket->fData = valueToAdopt;
202                newBucket->fKey = key;
203        }
204         else
205        {
206                newBucket =
207                        new (fMemoryManager->allocate(sizeof(ValueHashTableBucketElem<TVal>)))
208                        ValueHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
209                fBucketList[hashVal] = newBucket;
210                fCount++;
211        }
212}
213
214
215
216// ---------------------------------------------------------------------------
217//  ValueHashTableOf: Private methods
218// ---------------------------------------------------------------------------
219template <class TVal, class THasher>
220void ValueHashTableOf<TVal, THasher>::rehash()
221{
222        const XMLSize_t newMod = (fHashModulus * 2) + 1;
223
224        ValueHashTableBucketElem<TVal>** newBucketList =
225                (ValueHashTableBucketElem<TVal>**) fMemoryManager->allocate
226        (
227                newMod * sizeof(ValueHashTableBucketElem<TVal>*)
228        );//new RefHashTableBucketElem<TVal>*[newMod];
229
230        // Make sure the new bucket list is destroyed if an
231        // exception is thrown.
232        ArrayJanitor<ValueHashTableBucketElem<TVal>*>  guard(newBucketList, fMemoryManager);
233
234        memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
235
236
237        // Rehash all existing entries.
238        for (XMLSize_t index = 0; index < fHashModulus; index++)
239        {
240                // Get the bucket list head for this entry
241                ValueHashTableBucketElem<TVal>* curElem = fBucketList[index];
242
243                while (curElem)
244                {
245                        // Save the next element before we detach this one
246                        ValueHashTableBucketElem<TVal>* const nextElem = curElem->fNext;
247
248                        const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey, newMod);
249                        assert(hashVal < newMod);
250
251                        ValueHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal];
252
253                        // Insert at the start of this bucket's list.
254                        curElem->fNext = newHeadElem;
255                        newBucketList[hashVal] = curElem;
256
257                        curElem = nextElem;
258                }
259        }
260
261        ValueHashTableBucketElem<TVal>** const oldBucketList = fBucketList;
262
263        // Everything is OK at this point, so update the
264        // member variables.
265        fBucketList = guard.release();
266        fHashModulus = newMod;
267
268        // Delete the old bucket list.
269        fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
270
271}
272
273template <class TVal, class THasher>
274inline ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal, THasher>::
275findBucketElem(const void* const key, XMLSize_t& hashVal)
276{
277        // Hash the key
278        hashVal = fHasher.getHashVal(key, fHashModulus);
279        assert(hashVal < fHashModulus);
280
281        // Search that bucket for the key
282        ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
283        while (curElem)
284        {
285                if (fHasher.equals(key, curElem->fKey))
286                        return curElem;
287
288                curElem = curElem->fNext;
289        }
290        return 0;
291}
292
293template <class TVal, class THasher>
294inline const ValueHashTableBucketElem<TVal>* ValueHashTableOf<TVal, THasher>::
295findBucketElem(const void* const key, XMLSize_t& hashVal) const
296{
297        // Hash the key
298        hashVal = fHasher.getHashVal(key, fHashModulus);
299        assert(hashVal < fHashModulus);
300
301        // Search that bucket for the key
302        const ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
303        while (curElem)
304        {
305                if (fHasher.equals(key, curElem->fKey))
306                        return curElem;
307
308                curElem = curElem->fNext;
309        }
310        return 0;
311}
312
313
314template <class TVal, class THasher>
315void ValueHashTableOf<TVal, THasher>::
316removeBucketElem(const void* const key, XMLSize_t& hashVal)
317{
318        // Hash the key
319        hashVal = fHasher.getHashVal(key, fHashModulus);
320        assert(hashVal < fHashModulus);
321
322        //
323        //  Search the given bucket for this key. Keep up with the previous
324        //  element so we can patch around it.
325        //
326        ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
327        ValueHashTableBucketElem<TVal>* lastElem = 0;
328
329        while (curElem)
330        {
331                if (fHasher.equals(key, curElem->fKey))
332                {
333                        if (!lastElem)
334                        {
335                                // It was the first in the bucket
336                                fBucketList[hashVal] = curElem->fNext;
337                        }
338                         else
339                        {
340                                // Patch around the current element
341                                lastElem->fNext = curElem->fNext;
342                        }
343
344                        // Delete the current element
345                        // delete curElem;
346                        // destructor is empty...
347                        // curElem->~ValueHashTableBucketElem();
348                        fMemoryManager->deallocate(curElem);
349
350                        fCount--;
351
352                        return;
353                }
354
355                // Move both pointers upwards
356                lastElem = curElem;
357                curElem = curElem->fNext;
358        }
359
360        // We never found that key
361        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
362}
363
364
365
366
367// ---------------------------------------------------------------------------
368//  ValueHashTableOfEnumerator: Constructors and Destructor
369// ---------------------------------------------------------------------------
370template <class TVal, class THasher>
371ValueHashTableOfEnumerator<TVal, THasher>::
372ValueHashTableOfEnumerator(ValueHashTableOf<TVal, THasher>* const toEnum
373                                                   , const bool adopt
374                                                   , MemoryManager* const manager)
375        : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum), fMemoryManager(manager)
376{
377        if (!toEnum)
378                ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, manager);
379
380        //
381        //  Find the next available bucket element in the hash table. If it
382        //  comes back zero, that just means the table is empty.
383        //
384        //  Note that the -1 in the current hash tells it to start from the
385        //  beginning.
386        //
387        findNext();
388}
389
390template <class TVal, class THasher>
391ValueHashTableOfEnumerator<TVal, THasher>::~ValueHashTableOfEnumerator()
392{
393        if (fAdopted)
394                delete fToEnum;
395}
396
397
398// ---------------------------------------------------------------------------
399//  ValueHashTableOfEnumerator: Enum interface
400// ---------------------------------------------------------------------------
401template <class TVal, class THasher>
402bool ValueHashTableOfEnumerator<TVal, THasher>::hasMoreElements() const
403{
404        //
405        //  If our current has is at the max and there are no more elements
406        //  in the current bucket, then no more elements.
407        //
408        if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
409                return false;
410        return true;
411}
412
413template <class TVal, class THasher>
414TVal& ValueHashTableOfEnumerator<TVal, THasher>::nextElement()
415{
416        // Make sure we have an element to return
417        if (!hasMoreElements())
418                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
419
420        //
421        //  Save the current element, then move up to the next one for the
422        //  next time around.
423        //
424        ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
425        findNext();
426
427        return saveElem->fData;
428}
429
430template <class TVal, class THasher>
431void* ValueHashTableOfEnumerator<TVal, THasher>::nextElementKey()
432{
433        // Make sure we have an element to return
434        if (!hasMoreElements())
435                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
436
437        //
438        //  Save the current element, then move up to the next one for the
439        //  next time around.
440        //
441        ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
442        findNext();
443
444        return saveElem->fKey;
445}
446
447
448template <class TVal, class THasher>
449void ValueHashTableOfEnumerator<TVal, THasher>::Reset()
450{
451        fCurHash = (XMLSize_t)-1;
452        fCurElem = 0;
453        findNext();
454}
455
456
457
458// ---------------------------------------------------------------------------
459//  ValueHashTableOfEnumerator: Private helper methods
460// ---------------------------------------------------------------------------
461template <class TVal, class THasher>
462void ValueHashTableOfEnumerator<TVal, THasher>::findNext()
463{
464        //
465        //  If there is a current element, move to its next element. If this
466        //  hits the end of the bucket, the next block will handle the rest.
467        //
468        if (fCurElem)
469                fCurElem = fCurElem->fNext;
470
471        //
472        //  If the current element is null, then we have to move up to the
473        //  next hash value. If that is the hash modulus, then we cannot
474        //  go further.
475        //
476        if (!fCurElem)
477        {
478                if (++fCurHash == fToEnum->fHashModulus)
479                        return;
480
481                // Else find the next non-empty bucket
482                while (fToEnum->fBucketList[fCurHash]==0)
483                {
484                        // Bump to the next hash value. If we max out return
485                        if (++fCurHash == fToEnum->fHashModulus)
486                                return;
487                }
488                fCurElem = fToEnum->fBucketList[fCurHash];
489        }
490}
491
492XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.