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

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

Initial check-in of icXML 0.8 source files

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