source: icXML/icXML-devel/src/icxercesc/util/RefHashTableOf.c

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

Changes to icxercesc files

File size: 19.2 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: RefHashTableOf.c 678409 2008-07-21 13:08:10Z borisk $
20 */
21
22
23// ---------------------------------------------------------------------------
24//  Include
25// ---------------------------------------------------------------------------
26#if defined(XERCES_TMPLSINC)
27#include <icxercesc/util/RefHashTableOf.hpp>
28#endif
29
30#include <xercesc/util/Janitor.hpp>
31#include <icxercesc/util/XMLString.hpp>
32#include <xercesc/util/NullPointerException.hpp>
33#include <new>
34#include <icxmlc/XMLConfig.hpp>
35
36XERCES_CPP_NAMESPACE_BEGIN
37
38// ---------------------------------------------------------------------------
39//  RefHashTableOf: Constructors and Destructor
40// ---------------------------------------------------------------------------
41template <class TVal, class THasher>
42RefHashTableOf<TVal, THasher>::RefHashTableOf(
43  const XMLSize_t modulus,
44  MemoryManager* const manager)
45
46        : fMemoryManager(manager)
47        , fAdoptedElems(true)
48        , fBucketList(0)
49        , fHashModulus(modulus)
50        , fInitialModulus(modulus)
51        , fCount(0)
52{
53        initialize(modulus);
54}
55
56template <class TVal, class THasher>
57RefHashTableOf<TVal, THasher>::RefHashTableOf(
58  const XMLSize_t modulus,
59  const THasher& hasher,
60  MemoryManager* const manager)
61
62        : fMemoryManager(manager)
63        , fAdoptedElems(true)
64        , fBucketList(0)
65        , fHashModulus(modulus)
66        , fInitialModulus(modulus)
67        , fCount(0)
68        , fHasher (hasher)
69{
70        initialize(modulus);
71}
72
73template <class TVal, class THasher>
74RefHashTableOf<TVal, THasher>::RefHashTableOf(
75  const XMLSize_t modulus,
76  const bool adoptElems,
77  MemoryManager* const manager)
78
79        : fMemoryManager(manager)
80        , fAdoptedElems(adoptElems)
81        , fBucketList(0)
82        , fHashModulus(modulus)
83        , fInitialModulus(modulus)
84        , fCount(0)
85
86{
87        initialize(modulus);
88}
89
90template <class TVal, class THasher>
91RefHashTableOf<TVal, THasher>::RefHashTableOf(
92  const XMLSize_t modulus,
93  const bool adoptElems,
94  const THasher& hasher,
95  MemoryManager* const manager)
96
97        : fMemoryManager(manager)
98        , fAdoptedElems(adoptElems)
99        , fBucketList(0)
100        , fHashModulus(modulus)
101        , fInitialModulus(modulus)
102        , fCount(0)
103        , fHasher (hasher)
104{
105        initialize(modulus);
106}
107
108template <class TVal, class THasher>
109void RefHashTableOf<TVal, THasher>::initialize(const XMLSize_t modulus)
110{
111        if (modulus == 0)
112                ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
113
114        // Allocate the bucket list and zero them
115        fBucketList = (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate
116        (
117                fHashModulus * sizeof(RefHashTableBucketElem<TVal>*)
118        );
119        for (XMLSize_t index = 0; index < fHashModulus; index++)
120                fBucketList[index] = 0;
121}
122
123template <class TVal, class THasher>
124RefHashTableOf<TVal, THasher>::~RefHashTableOf()
125{
126        cleanup();
127}
128
129
130// ---------------------------------------------------------------------------
131//  RefHashTableOf: Element management
132// ---------------------------------------------------------------------------
133template <class TVal, class THasher>
134inline bool RefHashTableOf<TVal, THasher>::isEmpty() const
135{
136        return fCount==0;
137}
138
139template <class TVal, class THasher>
140inline bool RefHashTableOf<TVal, THasher>::containsKey(const void* const key) const
141{
142        XMLSize_t hashVal;
143        const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
144        return (findIt != 0);
145}
146
147template <class TVal, class THasher>
148void RefHashTableOf<TVal, THasher>::
149removeKey(const void* const key)
150{
151        // Hash the key
152        XMLSize_t hashVal = fHasher.getHashVal(key, fHashModulus);
153
154        //
155        //  Search the given bucket for this key. Keep up with the previous
156        //  element so we can patch around it.
157        //
158        RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
159        RefHashTableBucketElem<TVal>* lastElem = 0;
160
161        while (curElem)
162        {
163                if (fHasher.equals(key, curElem->fKey))
164                {
165                        if (!lastElem)
166                        {
167                                // It was the first in the bucket
168                                fBucketList[hashVal] = curElem->fNext;
169                        }
170                         else
171                        {
172                                // Patch around the current element
173                                lastElem->fNext = curElem->fNext;
174                        }
175
176                        // If we adopted the data, then delete it too
177                        //    (Note:  the userdata hash table instance has data type of void *.
178                        //    This will generate compiler warnings here on some platforms, but they
179                        //    can be ignored since fAdoptedElements is false.
180                        if (fAdoptedElems)
181                                delete curElem->fData;
182
183                        // Then delete the current element and move forward
184                        // delete curElem;
185                        // destructor doesn't do anything...
186                        fMemoryManager->deallocate(curElem);
187
188                        fCount--;
189
190                        return;
191                }
192
193                // Move both pointers upwards
194                lastElem = curElem;
195                curElem = curElem->fNext;
196        }
197
198        // We never found that key
199        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
200}
201
202template <class TVal, class THasher>
203void RefHashTableOf<TVal, THasher>::removeAll()
204{
205        if(isEmpty())
206                return;
207
208        // Clean up the buckets first
209        for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
210        {
211                // Get the bucket list head for this entry
212                RefHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
213                RefHashTableBucketElem<TVal>* nextElem;
214                while (curElem)
215                {
216                        // Save the next element before we hose this one
217                        nextElem = curElem->fNext;
218
219                        // If we adopted the data, then delete it too
220                        //    (Note:  the userdata hash table instance has data type of void *.
221                        //    This will generate compiler warnings here on some platforms, but they
222                        //    can be ignored since fAdoptedElements is false.
223                        if (fAdoptedElems)
224                                delete curElem->fData;
225
226                        fMemoryManager->deallocate(curElem);
227                        curElem = nextElem;
228                }
229
230                // Clean out this entry
231                fBucketList[buckInd] = 0;
232        }
233
234        fCount = 0;
235}
236
237// This method returns the data associated with a key. The key entry is deleted. The caller
238// now owns the returned data (case of hashtable adopting the data).
239// This function is called by transferElement so that the undeleted data can be transferred
240// to a new key which will own that data.
241template <class TVal, class THasher> TVal* RefHashTableOf<TVal, THasher>::
242orphanKey(const void* const key)
243{
244        // Hash the key
245        TVal* retVal = 0;
246        XMLSize_t hashVal = fHasher.getHashVal(key, fHashModulus);
247
248        //
249        //  Search the given bucket for this key. Keep up with the previous
250        //  element so we can patch around it.
251        //
252        RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
253        RefHashTableBucketElem<TVal>* lastElem = 0;
254
255        while (curElem)
256        {
257                if (fHasher.equals(key, curElem->fKey))
258                {
259                        if (!lastElem)
260                        {
261                                // It was the first in the bucket
262                                fBucketList[hashVal] = curElem->fNext;
263                        }
264                        else
265                        {
266                                // Patch around the current element
267                                lastElem->fNext = curElem->fNext;
268                        }
269
270                        retVal = curElem->fData;
271
272                        // Delete the current element
273                        fMemoryManager->deallocate(curElem);
274                        break;
275                }
276
277                // Move both pointers upwards
278                lastElem = curElem;
279                curElem = curElem->fNext;
280        }
281
282        // We never found that key
283        if (!retVal)
284                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
285
286        return retVal;
287}
288
289//
290// cleanup():
291//   similar to destructor
292//   called to cleanup the memory, in case destructor cannot be called
293//
294template <class TVal, class THasher>
295void RefHashTableOf<TVal, THasher>::cleanup()
296{
297        removeAll();
298
299        // Then delete the bucket list & hasher
300        fMemoryManager->deallocate(fBucketList);
301        fBucketList = 0;
302}
303
304//
305// reinitialize():
306//   similar to constructor
307//   called to re-construct the fElemList from scratch again
308//
309template <class TVal, class THasher>
310void RefHashTableOf<TVal, THasher>::reinitialize(const THasher& hasher)
311{
312        if (fBucketList)
313                cleanup();
314
315        fHasher = hasher;
316
317        fHashModulus = fInitialModulus;
318        initialize(fHashModulus);
319}
320
321
322
323// this function transfer the data from key1 to key2
324// this is equivalent to calling
325//  1.  get(key1) to retrieve the data,
326//  2.  removeKey(key1),
327//  3.  and then put(key2, data)
328// except that the data is not deleted in "removeKey" even it is adopted so that it
329// can be transferred to key2.
330// whatever key2 has originally will be purged (if adopted)
331template <class TVal, class THasher>
332inline void RefHashTableOf<TVal, THasher>::transferElement(const void* const key1, void* key2)
333{
334        put(key2, orphanKey(key1));
335}
336
337
338// ---------------------------------------------------------------------------
339//  RefHashTableOf: Getters
340// ---------------------------------------------------------------------------
341template <class TVal, class THasher>
342TVal* RefHashTableOf<TVal, THasher>::
343get(const void* const key)
344{
345        XMLSize_t hashVal;
346        RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
347        return findIt ? findIt->fData : 0;
348}
349
350template <class TVal, class THasher>
351const TVal* RefHashTableOf<TVal, THasher>::
352get(const void* const key) const
353{
354        XMLSize_t hashVal;
355        const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
356        return findIt ? findIt->fData : 0;
357}
358
359template <class TVal, class THasher>
360TVal* RefHashTableOf<TVal, THasher>::
361get(const void* const key, const unsigned int length)
362{
363        XMLSize_t hashVal;
364        RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, length, hashVal);
365        return findIt ? findIt->fData : 0;
366}
367
368template <class TVal, class THasher>
369const TVal* RefHashTableOf<TVal, THasher>::
370get(const void* const key, const unsigned int length) const
371{
372        XMLSize_t hashVal;
373        const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, length, hashVal);
374        return findIt ? findIt->fData : 0;
375}
376
377template <class TVal, class THasher>
378inline MemoryManager* RefHashTableOf<TVal, THasher>::getMemoryManager() const
379{
380        return fMemoryManager;
381}
382
383template <class TVal, class THasher>
384inline XMLSize_t RefHashTableOf<TVal, THasher>::getHashModulus() const
385{
386        return fHashModulus;
387}
388
389template <class TVal, class THasher>
390inline XMLSize_t RefHashTableOf<TVal, THasher>::getCount() const
391{
392        return fCount;
393}
394
395// ---------------------------------------------------------------------------
396//  RefHashTableOf: Getters
397// ---------------------------------------------------------------------------
398template <class TVal, class THasher>
399inline void RefHashTableOf<TVal, THasher>::setAdoptElements(const bool aValue)
400{
401        fAdoptedElems = aValue;
402}
403
404// ---------------------------------------------------------------------------
405//  RefHashTableOf: Putters
406// ---------------------------------------------------------------------------
407template <class TVal, class THasher>
408void RefHashTableOf<TVal, THasher>::put(void * key, TVal * const valueToAdopt)
409{
410        // Apply 0.75 load factor to find threshold.
411        XMLSize_t threshold = fHashModulus * 3 / 4;
412
413        // If we've grown too big, expand the table and rehash.
414        if (fCount >= threshold)
415                rehash();
416
417        // First see if the key exists already
418        XMLSize_t hashVal;
419        RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);
420
421        //
422        //  If so,then update its value. If not, then we need to add it to
423        //  the right bucket
424        //
425        if (newBucket)
426        {
427                if (fAdoptedElems)
428                        delete newBucket->fData;
429                newBucket->fData = valueToAdopt;
430                newBucket->fKey = key;
431        }
432        else
433        {
434                newBucket =
435                         new (fMemoryManager->allocate(sizeof(RefHashTableBucketElem<TVal>)))
436                         RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
437                fBucketList[hashVal] = newBucket;
438                fCount++;
439        }
440}
441
442
443
444// ---------------------------------------------------------------------------
445//  RefHashTableOf: Private methods
446// ---------------------------------------------------------------------------
447template <class TVal, class THasher>
448void RefHashTableOf<TVal, THasher>::rehash()
449{
450        const XMLSize_t newMod = (fHashModulus * 2) + 1;
451
452        RefHashTableBucketElem<TVal>** newBucketList =
453                (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate
454        (
455                newMod * sizeof(RefHashTableBucketElem<TVal>*)
456        );
457
458        // Make sure the new bucket list is destroyed if an
459        // exception is thrown.
460        ArrayJanitor<RefHashTableBucketElem<TVal>*>  guard(newBucketList, fMemoryManager);
461
462        memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));
463
464
465        // Rehash all existing entries.
466        for (XMLSize_t index = 0; index < fHashModulus; index++)
467        {
468                // Get the bucket list head for this entry
469                RefHashTableBucketElem<TVal>* curElem = fBucketList[index];
470
471                while (curElem)
472                {
473                        // Save the next element before we detach this one
474                        RefHashTableBucketElem<TVal>* const nextElem = curElem->fNext;
475
476                        const XMLSize_t hashVal = fHasher.getHashVal(curElem->fKey, newMod);
477
478                        RefHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal];
479
480                        // Insert at the start of this bucket's list.
481                        curElem->fNext = newHeadElem;
482                        newBucketList[hashVal] = curElem;
483
484                        curElem = nextElem;
485                }
486        }
487
488        RefHashTableBucketElem<TVal>** const oldBucketList = fBucketList;
489
490        // Everything is OK at this point, so update the
491        // member variables.
492        fBucketList = guard.release();
493        fHashModulus = newMod;
494
495        // Delete the old bucket list.
496        fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;
497
498}
499
500template <class TVal, class THasher>
501inline RefHashTableBucketElem<TVal>* RefHashTableOf<TVal, THasher>::
502findBucketElem(const void* const key, XMLSize_t& hashVal)
503{
504        // Hash the key
505        hashVal = fHasher.getHashVal(key, fHashModulus);
506
507        // Search that bucket for the key
508        RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
509        while (curElem)
510        {
511                if (fHasher.equals(key, curElem->fKey))
512                {
513                        return curElem;
514                }
515                curElem = curElem->fNext;
516        }
517        return 0;
518}
519
520template <class TVal, class THasher>
521inline const RefHashTableBucketElem<TVal>* RefHashTableOf<TVal, THasher>::
522findBucketElem(const void* const rawKey, unsigned int length, XMLSize_t & hashVal) const
523{
524        // Hash the key
525        hashVal = fHasher.getHashVal(rawKey, length, fHashModulus);
526
527        // Search that bucket for the key
528        const RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
529        while (curElem)
530        {
531                if (fHasher.equals(rawKey, curElem->fKey))
532                        return curElem;
533
534                curElem = curElem->fNext;
535        }
536        return 0;
537}
538
539template <class TVal, class THasher>
540inline RefHashTableBucketElem<TVal>* RefHashTableOf<TVal, THasher>::
541findBucketElem(const void* const rawKey, unsigned int length, XMLSize_t& hashVal)
542{
543        // Hash the key
544        hashVal = fHasher.getHashVal(rawKey, length, fHashModulus);
545
546        // Search that bucket for the key
547        RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
548        while (curElem)
549        {
550                if (fHasher.equals(rawKey, curElem->fKey))
551                        return curElem;
552
553                curElem = curElem->fNext;
554        }
555        return 0;
556}
557
558template <class TVal, class THasher>
559inline const RefHashTableBucketElem<TVal>* RefHashTableOf<TVal, THasher>::
560findBucketElem(const void* const key, XMLSize_t& hashVal) const
561{
562        // Hash the key
563        hashVal = fHasher.getHashVal(key, fHashModulus);
564
565        // Search that bucket for the key
566        const RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
567        while (curElem)
568        {
569                if (fHasher.equals(key, curElem->fKey))
570                        return curElem;
571
572                curElem = curElem->fNext;
573        }
574        return 0;
575}
576
577
578// ---------------------------------------------------------------------------
579//  RefHashTableOfEnumerator: Constructors and Destructor
580// ---------------------------------------------------------------------------
581template <class TVal, class THasher> RefHashTableOfEnumerator<TVal, THasher>::
582RefHashTableOfEnumerator(RefHashTableOf<TVal, THasher>* const toEnum
583                                                 , const bool adopt
584                                                 , MemoryManager* const manager)
585        : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum)
586        , fMemoryManager(manager)
587{
588        if (!toEnum)
589                ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
590
591        //
592        //  Find the next available bucket element in the hash table. If it
593        //  comes back zero, that just means the table is empty.
594        //
595        //  Note that the -1 in the current hash tells it to start
596        //  from the beginning.
597        //
598        findNext();
599}
600
601template <class TVal, class THasher>
602RefHashTableOfEnumerator<TVal, THasher>::~RefHashTableOfEnumerator()
603{
604        if (fAdopted)
605                delete fToEnum;
606}
607
608
609template <class TVal, class THasher> RefHashTableOfEnumerator<TVal, THasher>::
610RefHashTableOfEnumerator(const RefHashTableOfEnumerator<TVal, THasher>& toCopy) :
611        XMLEnumerator<TVal>(toCopy)
612        , XMemory(toCopy)
613        , fAdopted(toCopy.fAdopted)
614        , fCurElem(toCopy.fCurElem)
615        , fCurHash(toCopy.fCurHash)
616        , fToEnum(toCopy.fToEnum)
617        , fMemoryManager(toCopy.fMemoryManager)
618{
619}
620// ---------------------------------------------------------------------------
621//  RefHashTableOfEnumerator: Enum interface
622// ---------------------------------------------------------------------------
623template <class TVal, class THasher>
624bool RefHashTableOfEnumerator<TVal, THasher>::hasMoreElements() const
625{
626        //
627        //  If our current has is at the max and there are no more elements
628        //  in the current bucket, then no more elements.
629        //
630        if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
631                return false;
632        return true;
633}
634
635template <class TVal, class THasher>
636TVal& RefHashTableOfEnumerator<TVal, THasher>::nextElement()
637{
638        // Make sure we have an element to return
639        if (!hasMoreElements())
640                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
641
642        //
643        //  Save the current element, then move up to the next one for the
644        //  next time around.
645        //
646        RefHashTableBucketElem<TVal>* saveElem = fCurElem;
647        findNext();
648
649        return *saveElem->fData;
650}
651
652template <class TVal, class THasher>
653void* RefHashTableOfEnumerator<TVal, THasher>::nextElementKey()
654{
655        // Make sure we have an element to return
656        if (!hasMoreElements())
657                ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
658
659        //
660        //  Save the current element, then move up to the next one for the
661        //  next time around.
662        //
663        RefHashTableBucketElem<TVal>* saveElem = fCurElem;
664        findNext();
665
666        return saveElem->fKey;
667}
668
669template <class TVal, class THasher>
670void RefHashTableOfEnumerator<TVal, THasher>::Reset()
671{
672        fCurHash = (XMLSize_t)-1;
673        fCurElem = 0;
674        findNext();
675}
676
677
678
679// ---------------------------------------------------------------------------
680//  RefHashTableOfEnumerator: Private helper methods
681// ---------------------------------------------------------------------------
682template <class TVal, class THasher>
683void RefHashTableOfEnumerator<TVal, THasher>::findNext()
684{
685        //
686        //  If there is a current element, move to its next element. If this
687        //  hits the end of the bucket, the next block will handle the rest.
688        //
689        if (fCurElem)
690                fCurElem = fCurElem->fNext;
691
692        //
693        //  If the current element is null, then we have to move up to the
694        //  next hash value. If that is the hash modulus, then we cannot
695        //  go further.
696        //
697        if (!fCurElem)
698        {
699                fCurHash++;
700                if (fCurHash == fToEnum->fHashModulus)
701                        return;
702
703                // Else find the next non-empty bucket
704                while (fToEnum->fBucketList[fCurHash]==0)
705                {
706                        // Bump to the next hash value. If we max out return
707                        fCurHash++;
708                        if (fCurHash == fToEnum->fHashModulus)
709                                return;
710                }
711                fCurElem = fToEnum->fBucketList[fCurHash];
712        }
713}
714
715XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.