source: icXML/icXML-devel/src/xercesc/util/RefHash2KeysTableOf.c @ 2732

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

Original Xerces files with import mods for icxercesc

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