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