source: icXML/icXML-devel/tests/src/MemHandlerTest/SimpleValueHashTableOf.hpp @ 2726

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

Add original Xerces tests and samples directories

File size: 17.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: SimpleValueHashTableOf.hpp 679340 2008-07-24 10:28:29Z borisk $
20 */
21
22//
23// This is just a version of the ValueHashTableOf implementation from
24// xercesc/util; we need a new one here because this cannot use the
25// pluggable memory management facilities.
26//
27
28#include <xercesc/util/XercesDefs.hpp>
29#include <xercesc/util/IllegalArgumentException.hpp>
30#include <xercesc/util/NoSuchElementException.hpp>
31#include <xercesc/util/NullPointerException.hpp>
32#include <xercesc/util/RuntimeException.hpp>
33#include <xercesc/util/XMLExceptMsgs.hpp>
34#include <xercesc/util/XMLEnumerator.hpp>
35#include <xercesc/util/Hashers.hpp>
36
37XERCES_CPP_NAMESPACE_USE
38
39//  Forward declare the enumerator so it can be our friend.
40//
41template <class TVal, class THasher = PtrHasher>
42class ValueHashTableOfEnumerator;
43
44
45//
46//  This should really be a nested class, but some of the compilers we
47//  have to support cannot deal with that!
48//
49template <class TVal>
50struct ValueHashTableBucketElem
51{
52    ValueHashTableBucketElem(void* key, const TVal& value, ValueHashTableBucketElem<TVal>* next)
53                : fData(value), fNext(next), fKey(key)
54        {
55        }
56
57    TVal                            fData;
58    ValueHashTableBucketElem<TVal>* fNext;
59    void*                           fKey;
60};
61
62
63template <class TVal, class THasher = PtrHasher>
64class SimpleValueHashTableOf
65{
66public:
67    // -----------------------------------------------------------------------
68    //  Constructors and Destructor
69    // -----------------------------------------------------------------------
70    SimpleValueHashTableOf(const XMLSize_t modulus);
71    SimpleValueHashTableOf(const XMLSize_t modulus, const THasher& hasher);
72    ~SimpleValueHashTableOf();
73
74
75    // -----------------------------------------------------------------------
76    //  Element management
77    // -----------------------------------------------------------------------
78    bool isEmpty() const;
79    bool containsKey(const void* const key) const;
80    void removeKey(const void* const key);
81    void removeAll();
82
83
84    // -----------------------------------------------------------------------
85    //  Getters
86    // -----------------------------------------------------------------------
87    TVal& get(const void* const key);
88    const TVal& get(const void* const key) const;
89
90
91    // -----------------------------------------------------------------------
92    //  Putters
93    // -----------------------------------------------------------------------
94    void put(void* key, const TVal& valueToAdopt);
95
96
97private :
98    // -----------------------------------------------------------------------
99    //  Declare our friends
100    // -----------------------------------------------------------------------
101    friend class ValueHashTableOfEnumerator<TVal, THasher>;
102
103private:
104
105    // -----------------------------------------------------------------------
106    //  Private methods
107    // -----------------------------------------------------------------------
108    ValueHashTableBucketElem<TVal>* findBucketElem(const void* const key, XMLSize_t& hashVal);
109    const ValueHashTableBucketElem<TVal>* findBucketElem(const void* const key, XMLSize_t& hashVal) const;
110    void removeBucketElem(const void* const key, XMLSize_t& hashVal);
111    void initialize(const XMLSize_t modulus);
112
113
114    // -----------------------------------------------------------------------
115    //  Data members
116    //
117    //  fBucketList
118    //      This is the array that contains the heads of all of the list
119    //      buckets, one for each possible hash value.
120    //
121    //  fHashModulus
122    //      The modulus used for this hash table, to hash the keys. This is
123    //      also the number of elements in the bucket list.
124        //
125        //  fHash
126        //      The hasher for the key data type.
127    // -----------------------------------------------------------------------
128    ValueHashTableBucketElem<TVal>** fBucketList;
129    XMLSize_t                        fHashModulus;
130    THasher                          fHasher;
131};
132
133
134
135//
136//  An enumerator for a value array. It derives from the basic enumerator
137//  class, so that value vectors can be generically enumerated.
138//
139template <class TVal, class THasher>
140class ValueHashTableOfEnumerator : public XMLEnumerator<TVal>
141{
142public :
143    // -----------------------------------------------------------------------
144    //  Constructors and Destructor
145    // -----------------------------------------------------------------------
146    ValueHashTableOfEnumerator(SimpleValueHashTableOf<TVal, THasher>* const toEnum, const bool adopt = false);
147    virtual ~ValueHashTableOfEnumerator();
148
149
150    // -----------------------------------------------------------------------
151    //  Enum interface
152    // -----------------------------------------------------------------------
153    bool hasMoreElements() const;
154    TVal& nextElement();
155    void Reset();
156
157
158private :
159    // -----------------------------------------------------------------------
160    //  Private methods
161    // -----------------------------------------------------------------------
162    void findNext();
163
164
165    // -----------------------------------------------------------------------
166    //  Data Members
167    //
168    //  fAdopted
169    //      Indicates whether we have adopted the passed vector. If so then
170    //      we delete the vector when we are destroyed.
171    //
172    //  fCurElem
173    //      This is the current bucket bucket element that we are on.
174    //
175    //  fCurHash
176    //      The is the current hash buck that we are working on. Once we hit
177    //      the end of the bucket that fCurElem is in, then we have to start
178    //      working this one up to the next non-empty bucket.
179    //
180    //  fToEnum
181    //      The value array being enumerated.
182    // -----------------------------------------------------------------------
183    bool                            fAdopted;
184    ValueHashTableBucketElem<TVal>* fCurElem;
185    XMLSize_t                       fCurHash;
186    SimpleValueHashTableOf<TVal, THasher>* fToEnum;
187
188};
189
190// ---------------------------------------------------------------------------
191//  ValueHashTableOf: Constructors and Destructor
192// ---------------------------------------------------------------------------
193template <class TVal, class THasher>
194SimpleValueHashTableOf<TVal, THasher>::SimpleValueHashTableOf(const XMLSize_t modulus
195                                                     , const THasher& hasher)
196    : fBucketList(0), fHashModulus(modulus), fHasher (hasher)
197{
198  initialize(modulus);
199}
200
201template <class TVal, class THasher>
202SimpleValueHashTableOf<TVal, THasher>::SimpleValueHashTableOf(const XMLSize_t modulus)
203        : fBucketList(0), fHashModulus(modulus)
204{
205  initialize(modulus);
206}
207
208template <class TVal, class THasher>
209void SimpleValueHashTableOf<TVal, THasher>::initialize(const XMLSize_t modulus)
210{
211        if (modulus == 0)
212        ThrowXML(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus);
213
214    // Allocate the bucket list and zero them
215    fBucketList = new ValueHashTableBucketElem<TVal>*[fHashModulus];
216    for (XMLSize_t index = 0; index < fHashModulus; index++)
217        fBucketList[index] = 0;
218}
219
220template <class TVal, class THasher>
221SimpleValueHashTableOf<TVal, THasher>::~SimpleValueHashTableOf()
222{
223    removeAll();
224
225    // Then delete the bucket list & hasher
226    delete [] fBucketList;
227}
228
229
230// ---------------------------------------------------------------------------
231//  SimpleValueHashTableOf: Element management
232// ---------------------------------------------------------------------------
233template <class TVal, class THasher>
234bool SimpleValueHashTableOf<TVal, THasher>::isEmpty() const
235{
236    // Just check the bucket list for non-empty elements
237    for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
238    {
239        if (fBucketList[buckInd] != 0)
240            return false;
241    }
242    return true;
243}
244
245template <class TVal, class THasher>
246bool SimpleValueHashTableOf<TVal, THasher>::
247containsKey(const void* const key) const
248{
249    XMLSize_t hashVal;
250    const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
251    return (findIt != 0);
252}
253
254template <class TVal, class THasher>
255void SimpleValueHashTableOf<TVal, THasher>::
256removeKey(const void* const key)
257{
258    XMLSize_t hashVal;
259    removeBucketElem(key, hashVal);
260}
261
262template <class TVal, class THasher>
263void SimpleValueHashTableOf<TVal, THasher>::removeAll()
264{
265    // Clean up the buckets first
266    for (XMLSize_t buckInd = 0; buckInd < fHashModulus; buckInd++)
267    {
268        // Get the bucket list head for this entry
269        ValueHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];
270        ValueHashTableBucketElem<TVal>* nextElem;
271        while (curElem)
272        {
273            // Save the next element before we hose this one
274            nextElem = curElem->fNext;
275
276            // delete the current element and move forward
277            delete curElem;
278            curElem = nextElem;
279        }
280
281        // Clean out this entry
282        fBucketList[buckInd] = 0;
283    }
284}
285
286
287// ---------------------------------------------------------------------------
288//  SimpleValueHashTableOf: Getters
289// ---------------------------------------------------------------------------
290template <class TVal, class THasher>
291TVal& SimpleValueHashTableOf<TVal, THasher>::get(const void* const key)
292{
293    XMLSize_t hashVal;
294    ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
295    if (!findIt)
296        ThrowXML(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists);
297
298    return findIt->fData;
299}
300
301template <class TVal, class THasher>
302const TVal& SimpleValueHashTableOf<TVal, THasher>::
303get(const void* const key) const
304{
305    XMLSize_t hashVal;
306    const ValueHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);
307    if (!findIt)
308        ThrowXML(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists);
309
310    return findIt->fData;
311}
312
313
314// ---------------------------------------------------------------------------
315//  SimpleValueHashTableOf: Putters
316// ---------------------------------------------------------------------------
317template <class TVal, class THasher>
318void SimpleValueHashTableOf<TVal, THasher>::put(void* key, const TVal& valueToAdopt)
319{
320    // First see if the key exists already
321    XMLSize_t hashVal;
322    ValueHashTableBucketElem<TVal>* newBucket = findBucketElem(key, 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    {
330        newBucket->fData = valueToAdopt;
331                newBucket->fKey = key;
332    }
333     else
334    {
335        newBucket = new ValueHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);
336        fBucketList[hashVal] = newBucket;
337    }
338}
339
340
341
342// ---------------------------------------------------------------------------
343//  SimpleValueHashTableOf: Private methods
344// ---------------------------------------------------------------------------
345template <class TVal, class THasher>
346ValueHashTableBucketElem<TVal>* SimpleValueHashTableOf<TVal, THasher>::
347findBucketElem(const void* const key, XMLSize_t& hashVal)
348{
349    // Hash the key
350    hashVal = fHasher.getHashVal(key, fHashModulus);
351    if (hashVal > fHashModulus)
352        ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey);
353
354    // Search that bucket for the key
355    ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
356    while (curElem)
357    {
358                if (fHasher.equals(key, curElem->fKey))
359            return curElem;
360
361        curElem = curElem->fNext;
362    }
363    return 0;
364}
365
366template <class TVal, class THasher>
367const ValueHashTableBucketElem<TVal>* SimpleValueHashTableOf<TVal, THasher>::
368findBucketElem(const void* const key, XMLSize_t& hashVal) const
369{
370    // Hash the key
371    hashVal = fHasher.getHashVal(key, fHashModulus);
372    if (hashVal > fHashModulus)
373        ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey);
374
375    // Search that bucket for the key
376    const ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
377    while (curElem)
378    {
379        if (fHasher.equals(key, curElem->fKey))
380            return curElem;
381
382        curElem = curElem->fNext;
383    }
384    return 0;
385}
386
387
388template <class TVal, class THasher>
389void SimpleValueHashTableOf<TVal, THasher>::
390removeBucketElem(const void* const key, XMLSize_t& hashVal)
391{
392    // Hash the key
393    hashVal = fHasher.getHashVal(key, fHashModulus);
394    if (hashVal > fHashModulus)
395        ThrowXML(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey);
396
397    //
398    //  Search the given bucket for this key. Keep up with the previous
399    //  element so we can patch around it.
400    //
401    ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];
402    ValueHashTableBucketElem<TVal>* lastElem = 0;
403
404    while (curElem)
405    {
406        if (fHasher.equals(key, curElem->fKey))
407        {
408            if (!lastElem)
409            {
410                // It was the first in the bucket
411                fBucketList[hashVal] = curElem->fNext;
412            }
413             else
414            {
415                // Patch around the current element
416                lastElem->fNext = curElem->fNext;
417            }
418
419            // Delete the current element
420            delete curElem;
421
422            return;
423        }
424
425        // Move both pointers upwards
426        lastElem = curElem;
427        curElem = curElem->fNext;
428    }
429
430    // We never found that key
431    ThrowXML(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists);
432}
433
434
435// ---------------------------------------------------------------------------
436//  ValueHashTableOfEnumerator: Constructors and Destructor
437// ---------------------------------------------------------------------------
438template <class TVal, class THasher>
439ValueHashTableOfEnumerator<TVal, THasher>::
440ValueHashTableOfEnumerator(SimpleValueHashTableOf<TVal, THasher>* const toEnum, const bool adopt)
441        : fAdopted(adopt), fCurElem(0), fCurHash((XMLSize_t)-1), fToEnum(toEnum)
442{
443    if (!toEnum)
444        ThrowXML(NullPointerException, XMLExcepts::CPtr_PointerIsZero);
445
446    //
447    //  Find the next available bucket element in the hash table. If it
448    //  comes back zero, that just means the table is empty.
449    //
450    //  Note that the -1 in the current hash tells it to start from the
451    //  beginning.
452    //
453    findNext();
454}
455
456template <class TVal, class THasher>
457ValueHashTableOfEnumerator<TVal, THasher>::~ValueHashTableOfEnumerator()
458{
459    if (fAdopted)
460        delete fToEnum;
461}
462
463
464// ---------------------------------------------------------------------------
465//  ValueHashTableOfEnumerator: Enum interface
466// ---------------------------------------------------------------------------
467template <class TVal, class THasher>
468bool ValueHashTableOfEnumerator<TVal, THasher>::hasMoreElements() const
469{
470    //
471    //  If our current has is at the max and there are no more elements
472    //  in the current bucket, then no more elements.
473    //
474    if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
475        return false;
476    return true;
477}
478
479template <class TVal, class THasher>
480TVal& ValueHashTableOfEnumerator<TVal, THasher>::nextElement()
481{
482    // Make sure we have an element to return
483    if (!hasMoreElements())
484        ThrowXML(NoSuchElementException, XMLExcepts::Enum_NoMoreElements);
485
486    //
487    //  Save the current element, then move up to the next one for the
488    //  next time around.
489    //
490    ValueHashTableBucketElem<TVal>* saveElem = fCurElem;
491    findNext();
492
493    return saveElem->fData;
494}
495
496
497template <class TVal, class THasher>
498void ValueHashTableOfEnumerator<TVal, THasher>::Reset()
499{
500    fCurHash = (XMLSize_t)-1;
501    fCurElem = 0;
502    findNext();
503}
504
505
506
507// ---------------------------------------------------------------------------
508//  ValueHashTableOfEnumerator: Private helper methods
509// ---------------------------------------------------------------------------
510template <class TVal, class THasher>
511void ValueHashTableOfEnumerator<TVal, THasher>::findNext()
512{
513    //
514    //  If there is a current element, move to its next element. If this
515    //  hits the end of the bucket, the next block will handle the rest.
516    //
517    if (fCurElem)
518        fCurElem = fCurElem->fNext;
519
520    //
521    //  If the current element is null, then we have to move up to the
522    //  next hash value. If that is the hash modulus, then we cannot
523    //  go further.
524    //
525    if (!fCurElem)
526    {
527        fCurHash++;
528        if (fCurHash == fToEnum->fHashModulus)
529            return;
530
531        // Else find the next non-empty bucket
532        while (true)
533        {
534            if (fToEnum->fBucketList[fCurHash])
535                break;
536
537            // Bump to the next hash value. If we max out return
538            fCurHash++;
539            if (fCurHash == fToEnum->fHashModulus)
540                return;
541        }
542        fCurElem = fToEnum->fBucketList[fCurHash];
543    }
544}
Note: See TracBrowser for help on using the repository browser.