source: NonGTP/Xerces/xerces/include/xercesc/util/RefHash2KeysTableOf.c @ 358

Revision 358, 18.6 KB checked in by bittner, 19 years ago (diff)

xerces added

Line 
1/*
2 * Copyright 2001,2004 The Apache Software Foundation.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/**
18 * $Log: RefHash2KeysTableOf.c,v $
19 * Revision 1.11  2004/09/22 11:14:22  amassari
20 * Reorder initialization of variables in constructor
21 *
22 * Revision 1.10  2004/09/08 13:56:22  peiyongz
23 * Apache License Version 2.0
24 *
25 * Revision 1.9  2004/08/30 18:56:20  amassari
26 * Change the order of testing to save some CPU cycles
27 *
28 * Revision 1.8  2004/08/30 15:18:35  amassari
29 * - Added transferElement API
30 * - The iterator class now can iterate over the items having the same primary key
31 *
32 * Revision 1.7  2004/03/01 15:03:08  peiyongz
33 * new getter: getHashModulus
34 *
35 * Revision 1.6  2003/12/17 00:18:35  cargilld
36 * Update to memory management so that the static memory manager (one used to call Initialize) is only for static data.
37 *
38 * Revision 1.5  2003/10/17 21:10:40  peiyongz
39 * nextElementKey() added
40 *
41 * Revision 1.4  2003/05/18 14:02:05  knoaman
42 * Memory manager implementation: pass per instance manager.
43 *
44 * Revision 1.3  2003/05/15 19:04:35  knoaman
45 * Partial implementation of the configurable memory manager.
46 *
47 * Revision 1.2  2002/11/04 15:22:04  tng
48 * C++ Namespace Support.
49 *
50 * Revision 1.1.1.1  2002/02/01 22:22:12  peiyongz
51 * sane_include
52 *
53 * Revision 1.5  2001/07/19 18:43:18  peiyongz
54 * fix: detect null poiniter in enumerator's ctor.
55 *
56 * Revision 1.4  2001/06/04 13:45:03  tng
57 * The "hash" argument clashes with STL hash.  Fixed by Pei Yong Zhang.
58 *
59 * Revision 1.3  2001/05/11 13:26:28  tng
60 * Copyright update.
61 *
62 * Revision 1.2  2001/03/14 13:18:21  tng
63 * typo: should use fKey1
64 *
65 * Revision 1.1  2001/02/27 18:24:00  tng
66 * Schema: Add utility RefHash2KeysTableOf.
67 *
68 */
69
70
71// ---------------------------------------------------------------------------
72//  Include
73// ---------------------------------------------------------------------------
74#if defined(XERCES_TMPLSINC)
75#include <xercesc/util/RefHash2KeysTableOf.hpp>
76#endif
77
78#include <xercesc/util/NullPointerException.hpp>
79
80XERCES_CPP_NAMESPACE_BEGIN
81
82// ---------------------------------------------------------------------------
83//  RefHash2KeysTableOf: Constructors and Destructor
84// ---------------------------------------------------------------------------
85template <class TVal>
86RefHash2KeysTableOf<TVal>::RefHash2KeysTableOf( const unsigned int   modulus
87                                              , const bool           adoptElems
88                                              , MemoryManager* const manager)
89    : fMemoryManager(manager)
90        , fAdoptedElems(adoptElems)
91    , fBucketList(0)
92    , fHashModulus(modulus)
93    , fHash(0)
94{
95    initialize(modulus);
96       
97        // create default hasher
98        fHash = new (fMemoryManager) HashXMLCh();
99}
100
101template <class TVal>
102RefHash2KeysTableOf<TVal>::RefHash2KeysTableOf( const unsigned int   modulus
103                                              , const bool           adoptElems
104                                              , HashBase*            hashBase
105                                              , MemoryManager* const manager)
106        : fMemoryManager(manager)
107    , fAdoptedElems(adoptElems)
108    , fBucketList(0)
109    , fHashModulus(modulus)
110    , fHash(0)
111{
112        initialize(modulus);
113        // set hasher
114        fHash = hashBase;
115}
116
117template <class TVal>
118RefHash2KeysTableOf<TVal>::RefHash2KeysTableOf(const unsigned int modulus,
119                                               MemoryManager* const manager)
120        : fMemoryManager(manager)
121    , fAdoptedElems(true)
122    , fBucketList(0)
123    , fHashModulus(modulus)
124    , fHash(0)
125{
126        initialize(modulus);
127
128        // create default hasher
129        fHash = new (fMemoryManager) HashXMLCh();
130}
131
132template <class TVal>
133void RefHash2KeysTableOf<TVal>::initialize(const unsigned int modulus)
134{
135        if (modulus == 0)
136        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
137
138    // Allocate the bucket list and zero them
139    fBucketList = (RefHash2KeysTableBucketElem<TVal>**) fMemoryManager->allocate
140    (
141        fHashModulus * sizeof(RefHash2KeysTableBucketElem<TVal>*)
142    ); //new RefHash2KeysTableBucketElem<TVal>*[fHashModulus];
143    for (unsigned int index = 0; index < fHashModulus; index++)
144        fBucketList[index] = 0;
145}
146
147template <class TVal> RefHash2KeysTableOf<TVal>::~RefHash2KeysTableOf()
148{
149    removeAll();
150
151    // Then delete the bucket list & hasher
152    fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
153        delete fHash;
154}
155
156
157// ---------------------------------------------------------------------------
158//  RefHash2KeysTableOf: Element management
159// ---------------------------------------------------------------------------
160template <class TVal> bool RefHash2KeysTableOf<TVal>::isEmpty() const
161{
162    // Just check the bucket list for non-empty elements
163    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
164    {
165        if (fBucketList[buckInd] != 0)
166            return false;
167    }
168    return true;
169}
170
171template <class TVal> bool RefHash2KeysTableOf<TVal>::
172containsKey(const void* const key1, const int key2) const
173{
174    unsigned int hashVal;
175    const RefHash2KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, hashVal);
176    return (findIt != 0);
177}
178
179template <class TVal> void RefHash2KeysTableOf<TVal>::
180removeKey(const void* const key1, const int key2)
181{
182    unsigned int hashVal;
183    removeBucketElem(key1, key2, hashVal);
184}
185
186template <class TVal> void RefHash2KeysTableOf<TVal>::removeAll()
187{
188    // Clean up the buckets first
189    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
190    {
191        // Get the bucket list head for this entry
192        RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[buckInd];
193        RefHash2KeysTableBucketElem<TVal>* nextElem;
194        while (curElem)
195        {
196            // Save the next element before we hose this one
197            nextElem = curElem->fNext;
198
199            // If we adopted the data, then delete it too
200            //    (Note:  the userdata hash table instance has data type of void *.
201            //    This will generate compiler warnings here on some platforms, but they
202            //    can be ignored since fAdoptedElements is false.
203            if (fAdoptedElems)
204                delete curElem->fData;
205
206            // Then delete the current element and move forward
207            delete curElem;
208            curElem = nextElem;
209        }
210
211        // Clean out this entry
212        fBucketList[buckInd] = 0;
213    }
214}
215
216// this function transfer the data from key1 to key2
217template <class TVal> void RefHash2KeysTableOf<TVal>::transferElement(const void* const key1, void* key2)
218{
219    // Hash the key
220    unsigned int hashVal = fHash->getHashVal(key1, fHashModulus);
221    if (hashVal > fHashModulus)
222        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
223
224    //
225    //  Search the given bucket for this key. Keep up with the previous
226    //  element so we can patch around it.
227    //
228    RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
229    RefHash2KeysTableBucketElem<TVal>* lastElem = 0;
230
231    while (curElem)
232    {
233        // if this element has the same primary key, remove it and add it using the new primary key
234        if (fHash->equals(key1, curElem->fKey1))
235        {
236            if (!lastElem)
237            {
238                // It was the first in the bucket
239                fBucketList[hashVal] = curElem->fNext;
240            }
241            else
242            {
243                // Patch around the current element
244                lastElem->fNext = curElem->fNext;
245            }
246
247            put(key2, curElem->fKey2, curElem->fData);
248
249            RefHash2KeysTableBucketElem<TVal>* elemToDelete = curElem;
250           
251            // Update just curElem; lastElem must stay the same
252            curElem = curElem->fNext;
253
254            // Delete the current element
255            delete elemToDelete;
256        }
257        else
258        {
259            // Move both pointers upwards
260            lastElem = curElem;
261            curElem = curElem->fNext;
262        }
263    }
264}
265
266
267
268// ---------------------------------------------------------------------------
269//  RefHash2KeysTableOf: Getters
270// ---------------------------------------------------------------------------
271template <class TVal> TVal* RefHash2KeysTableOf<TVal>::get(const void* const key1, const int key2)
272{
273    unsigned int hashVal;
274    RefHash2KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, hashVal);
275    if (!findIt)
276        return 0;
277    return findIt->fData;
278}
279
280template <class TVal> const TVal* RefHash2KeysTableOf<TVal>::
281get(const void* const key1, const int key2) const
282{
283    unsigned int hashVal;
284    const RefHash2KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, hashVal);
285    if (!findIt)
286        return 0;
287    return findIt->fData;
288}
289
290template <class TVal>
291MemoryManager* RefHash2KeysTableOf<TVal>::getMemoryManager() const
292{
293    return fMemoryManager;
294}
295
296template <class TVal>
297unsigned int RefHash2KeysTableOf<TVal>::getHashModulus() const
298{
299    return fHashModulus;
300}
301
302// ---------------------------------------------------------------------------
303//  RefHash2KeysTableOf: Putters
304// ---------------------------------------------------------------------------
305template <class TVal> void RefHash2KeysTableOf<TVal>::put(void* key1, int key2, TVal* const valueToAdopt)
306{
307    // First see if the key exists already
308    unsigned int hashVal;
309    RefHash2KeysTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, hashVal);
310
311    //
312    //  If so,then update its value. If not, then we need to add it to
313    //  the right bucket
314    //
315    if (newBucket)
316    {
317        if (fAdoptedElems)
318            delete newBucket->fData;
319        newBucket->fData = valueToAdopt;
320                newBucket->fKey1 = key1;
321                newBucket->fKey2 = key2;
322    }
323     else
324    {
325        newBucket = new (fMemoryManager) RefHash2KeysTableBucketElem<TVal>(key1, key2, valueToAdopt, fBucketList[hashVal]);
326        fBucketList[hashVal] = newBucket;
327    }
328}
329
330
331
332// ---------------------------------------------------------------------------
333//  RefHash2KeysTableOf: Private methods
334// ---------------------------------------------------------------------------
335template <class TVal> RefHash2KeysTableBucketElem<TVal>* RefHash2KeysTableOf<TVal>::
336findBucketElem(const void* const key1, const int key2, unsigned int& hashVal)
337{
338    // Hash the key
339    hashVal = fHash->getHashVal(key1, fHashModulus, fMemoryManager);
340    if (hashVal > fHashModulus)
341        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
342
343    // Search that bucket for the key
344    RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
345    while (curElem)
346    {
347                if (key2==curElem->fKey2 && fHash->equals(key1, curElem->fKey1))
348            return curElem;
349
350        curElem = curElem->fNext;
351    }
352    return 0;
353}
354
355template <class TVal> const RefHash2KeysTableBucketElem<TVal>* RefHash2KeysTableOf<TVal>::
356findBucketElem(const void* const key1, const int key2, unsigned int& hashVal) const
357{
358    // Hash the key
359    hashVal = fHash->getHashVal(key1, fHashModulus, fMemoryManager);
360    if (hashVal > fHashModulus)
361        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
362
363    // Search that bucket for the key
364    const RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
365    while (curElem)
366    {
367        if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2))
368            return curElem;
369
370        curElem = curElem->fNext;
371    }
372    return 0;
373}
374
375
376template <class TVal> void RefHash2KeysTableOf<TVal>::
377removeBucketElem(const void* const key1, const int key2, unsigned int& hashVal)
378{
379    // Hash the key
380    hashVal = fHash->getHashVal(key1, fHashModulus);
381    if (hashVal > fHashModulus)
382        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
383
384    //
385    //  Search the given bucket for this key. Keep up with the previous
386    //  element so we can patch around it.
387    //
388    RefHash2KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
389    RefHash2KeysTableBucketElem<TVal>* lastElem = 0;
390
391    while (curElem)
392    {
393        if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2))
394        {
395            if (!lastElem)
396            {
397                // It was the first in the bucket
398                fBucketList[hashVal] = curElem->fNext;
399            }
400             else
401            {
402                // Patch around the current element
403                lastElem->fNext = curElem->fNext;
404            }
405
406            // If we adopted the elements, then delete the data
407            if (fAdoptedElems)
408                delete curElem->fData;
409
410            // Delete the current element
411            delete curElem;
412
413            return;
414        }
415
416        // Move both pointers upwards
417        lastElem = curElem;
418        curElem = curElem->fNext;
419    }
420
421    // We never found that key
422    ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);
423}
424
425
426
427
428// ---------------------------------------------------------------------------
429//  RefHash2KeysTableOfEnumerator: Constructors and Destructor
430// ---------------------------------------------------------------------------
431template <class TVal> RefHash2KeysTableOfEnumerator<TVal>::
432RefHash2KeysTableOfEnumerator(RefHash2KeysTableOf<TVal>* const toEnum
433                              , const bool adopt
434                              , MemoryManager* const manager)
435        : fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum)
436    , fMemoryManager(manager)
437    , fLockPrimaryKey(0)
438{
439    if (!toEnum)
440        ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
441
442    //
443    //  Find the next available bucket element in the hash table. If it
444    //  comes back zero, that just means the table is empty.
445    //
446    //  Note that the -1 in the current hash tells it to start from the
447    //  beginning.
448    //
449    findNext();
450}
451
452template <class TVal> RefHash2KeysTableOfEnumerator<TVal>::~RefHash2KeysTableOfEnumerator()
453{
454    if (fAdopted)
455        delete fToEnum;
456}
457
458
459// ---------------------------------------------------------------------------
460//  RefHash2KeysTableOfEnumerator: Enum interface
461// ---------------------------------------------------------------------------
462template <class TVal> bool RefHash2KeysTableOfEnumerator<TVal>::hasMoreElements() const
463{
464    //
465    //  If our current has is at the max and there are no more elements
466    //  in the current bucket, then no more elements.
467    //
468    if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
469        return false;
470    return true;
471}
472
473template <class TVal> TVal& RefHash2KeysTableOfEnumerator<TVal>::nextElement()
474{
475    // Make sure we have an element to return
476    if (!hasMoreElements())
477        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
478
479    //
480    //  Save the current element, then move up to the next one for the
481    //  next time around.
482    //
483    RefHash2KeysTableBucketElem<TVal>* saveElem = fCurElem;
484    findNext();
485
486    return *saveElem->fData;
487}
488
489template <class TVal> void RefHash2KeysTableOfEnumerator<TVal>::nextElementKey(void*& retKey1, int& retKey2)
490{
491    // Make sure we have an element to return
492    if (!hasMoreElements())
493        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
494
495    //
496    //  Save the current element, then move up to the next one for the
497    //  next time around.
498    //
499    RefHash2KeysTableBucketElem<TVal>* saveElem = fCurElem;
500    findNext();
501
502    retKey1 = saveElem->fKey1;
503    retKey2 = saveElem->fKey2;
504
505    return;
506}
507
508template <class TVal> void RefHash2KeysTableOfEnumerator<TVal>::Reset()
509{
510    if(fLockPrimaryKey)
511        fCurHash=fToEnum->fHash->getHashVal(fLockPrimaryKey, fToEnum->fHashModulus, fMemoryManager);
512    else
513        fCurHash = (unsigned int)-1;
514    fCurElem = 0;
515    findNext();
516}
517
518
519template <class TVal> void RefHash2KeysTableOfEnumerator<TVal>::setPrimaryKey(const void* key)
520{
521    fLockPrimaryKey=key;
522    Reset();
523}
524
525// ---------------------------------------------------------------------------
526//  RefHash2KeysTableOfEnumerator: Private helper methods
527// ---------------------------------------------------------------------------
528template <class TVal> void RefHash2KeysTableOfEnumerator<TVal>::findNext()
529{
530    //  Code to execute if we have to return only values with the primary key
531    if(fLockPrimaryKey)
532    {
533        if(!fCurElem)
534            fCurElem = fToEnum->fBucketList[fCurHash];
535        else
536            fCurElem = fCurElem->fNext;
537        while (fCurElem && !fToEnum->fHash->equals(fLockPrimaryKey, fCurElem->fKey1) )
538            fCurElem = fCurElem->fNext;
539        // if we didn't found it, make so hasMoreElements() returns false
540        if(!fCurElem)
541            fCurHash = fToEnum->fHashModulus;
542        return;
543    }
544    //
545    //  If there is a current element, move to its next element. If this
546    //  hits the end of the bucket, the next block will handle the rest.
547    //
548    if (fCurElem)
549        fCurElem = fCurElem->fNext;
550
551    //
552    //  If the current element is null, then we have to move up to the
553    //  next hash value. If that is the hash modulus, then we cannot
554    //  go further.
555    //
556    if (!fCurElem)
557    {
558        fCurHash++;
559        if (fCurHash == fToEnum->fHashModulus)
560            return;
561
562        // Else find the next non-empty bucket
563        while (true)
564        {
565            if (fToEnum->fBucketList[fCurHash])
566                break;
567
568            // Bump to the next hash value. If we max out return
569            fCurHash++;
570            if (fCurHash == fToEnum->fHashModulus)
571                return;
572        }
573        fCurElem = fToEnum->fBucketList[fCurHash];
574    }
575}
576
577XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.