source: NonGTP/Xerces/xercesc/util/RefHash3KeysIdPool.c @ 188

Revision 188, 21.1 KB checked in by mattausch, 19 years ago (diff)

added xercesc to support

Line 
1/*
2 * The Apache Software License, Version 1.1
3 *
4 * Copyright (c) 2001 The Apache Software Foundation.  All rights
5 * reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in
16 *    the documentation and/or other materials provided with the
17 *    distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 *    if any, must include the following acknowledgment:
21 *       "This product includes software developed by the
22 *        Apache Software Foundation (http://www.apache.org/)."
23 *    Alternately, this acknowledgment may appear in the software itself,
24 *    if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "Xerces" and "Apache Software Foundation" must
27 *    not be used to endorse or promote products derived from this
28 *    software without prior written permission. For written
29 *    permission, please contact apache\@apache.org.
30 *
31 * 5. Products derived from this software may not be called "Apache",
32 *    nor may "Apache" appear in their name, without prior written
33 *    permission of the Apache Software Foundation.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46 * SUCH DAMAGE.
47 * ====================================================================
48 *
49 * This software consists of voluntary contributions made by many
50 * individuals on behalf of the Apache Software Foundation, and was
51 * originally based on software copyright (c) 2001, International
52 * Business Machines, Inc., http://www.ibm.com .  For more information
53 * on the Apache Software Foundation, please see
54 * <http://www.apache.org/>.
55 */
56
57/**
58 * $Log: RefHash3KeysIdPool.c,v $
59 * Revision 1.10  2004/01/29 11:48:46  cargilld
60 * Code cleanup changes to get rid of various compiler diagnostic messages.
61 *
62 * Revision 1.9  2003/12/17 00:18:35  cargilld
63 * Update to memory management so that the static memory manager (one used to call Initialize) is only for static data.
64 *
65 * Revision 1.8  2003/11/03 22:00:31  peiyongz
66 * RefHashTable-like enumeration accessing added
67 *
68 * Revision 1.7  2003/10/29 16:18:05  peiyongz
69 * size() added and Reset() bug fixed
70 *
71 * Revision 1.6  2003/06/02 15:18:08  neilg
72 * fix for bug #20092; thanks to Berin Lautenbach
73 *
74 * Revision 1.5  2003/05/21 21:08:04  knoaman
75 * gcc 2.95.x is generating an internal error for some template definitions, so
76 * we use the default memory manger in such cases.
77 *
78 * Revision 1.4  2003/05/16 06:01:52  knoaman
79 * Partial implementation of the configurable memory manager.
80 *
81 * Revision 1.3  2003/05/15 19:04:35  knoaman
82 * Partial implementation of the configurable memory manager.
83 *
84 * Revision 1.2  2002/11/04 15:22:04  tng
85 * C++ Namespace Support.
86 *
87 * Revision 1.1.1.1  2002/02/01 22:22:12  peiyongz
88 * sane_include
89 *
90 * Revision 1.4  2001/07/19 18:43:18  peiyongz
91 * fix: detect null poiniter in enumerator's ctor.
92 *
93 * Revision 1.3  2001/06/04 13:45:04  tng
94 * The "hash" argument clashes with STL hash.  Fixed by Pei Yong Zhang.
95 *
96 * Revision 1.2  2001/05/11 13:26:29  tng
97 * Copyright update.
98 *
99 * Revision 1.1  2001/03/21 21:56:12  tng
100 * Schema: Add Schema Grammar, Schema Validator, and split the DTDValidator into DTDValidator, DTDScanner, and DTDGrammar.
101 *
102 */
103
104
105// ---------------------------------------------------------------------------
106//  Include
107// ---------------------------------------------------------------------------
108#if defined(XERCES_TMPLSINC)
109#include <xercesc/util/RefHash3KeysIdPool.hpp>
110#endif
111
112#include <xercesc/util/NullPointerException.hpp>
113
114XERCES_CPP_NAMESPACE_BEGIN
115
116// ---------------------------------------------------------------------------
117//  RefHash3KeysIdPool: Constructors and Destructor
118// ---------------------------------------------------------------------------
119template <class TVal>
120RefHash3KeysIdPool<TVal>::RefHash3KeysIdPool( const unsigned int modulus
121                                            , const bool         adoptElems
122                                            , const unsigned int initSize
123                                            , MemoryManager* const manager) :
124    fMemoryManager(manager)
125    , fAdoptedElems(adoptElems)
126    , fBucketList(0)
127    , fHashModulus(modulus)
128    , fHash(0)
129    , fIdPtrs(0)
130    , fIdPtrsCount(initSize)
131    , fIdCounter(0)
132{
133    initialize(modulus);
134
135    // create default hasher
136#if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
137                 fHash = new HashXMLCh();
138#else
139    fHash = new (fMemoryManager) HashXMLCh();
140#endif
141
142    //
143    //  Allocate the initial id pointers array. We don't have to zero them
144    //  out since the fIdCounter value tells us which ones are valid. The
145    //  zeroth element is never used (and represents an invalid pool id.)
146    //
147    if (!fIdPtrsCount)
148        fIdPtrsCount = 256;
149    fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
150    fIdPtrs[0] = 0;
151}
152
153template <class TVal>
154RefHash3KeysIdPool<TVal>::RefHash3KeysIdPool( const unsigned int modulus
155                                            , const bool         adoptElems
156                                            , HashBase*          hashBase
157                                            , const unsigned int initSize
158                                            , MemoryManager* const manager) :
159        fMemoryManager(manager)
160    , fAdoptedElems(adoptElems)
161    , fBucketList(0)
162    , fHashModulus(modulus)
163    , fHash(0)
164    , fIdPtrs(0)
165    , fIdPtrsCount(initSize)
166    , fIdCounter(0)
167{
168    initialize(modulus);
169    // set hasher
170    fHash = hashBase;
171
172    //
173    //  Allocate the initial id pointers array. We don't have to zero them
174    //  out since the fIdCounter value tells us which ones are valid. The
175    //  zeroth element is never used (and represents an invalid pool id.)
176    //
177    if (!fIdPtrsCount)
178        fIdPtrsCount = 256;
179    fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
180    fIdPtrs[0] = 0;
181}
182
183template <class TVal>
184RefHash3KeysIdPool<TVal>::RefHash3KeysIdPool( const unsigned int modulus
185                                            , const unsigned int initSize
186                                            , MemoryManager* const manager) :
187        fMemoryManager(manager)
188    , fAdoptedElems(true)
189    , fBucketList(0)
190    , fHashModulus(modulus)
191    , fHash(0)
192    , fIdPtrs(0)
193    , fIdPtrsCount(initSize)
194    , fIdCounter(0)
195{
196    initialize(modulus);
197
198    // create default hasher
199
200    fHash = new (fMemoryManager) HashXMLCh();
201
202    //
203    //  Allocate the initial id pointers array. We don't have to zero them
204    //  out since the fIdCounter value tells us which ones are valid. The
205    //  zeroth element is never used (and represents an invalid pool id.)
206    //
207    if (!fIdPtrsCount)
208        fIdPtrsCount = 256;
209    fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
210    fIdPtrs[0] = 0;
211}
212
213template <class TVal> void RefHash3KeysIdPool<TVal>::initialize(const unsigned int modulus)
214{
215        if (modulus == 0)
216        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
217
218    // Allocate the bucket list and zero them
219    fBucketList = (RefHash3KeysTableBucketElem<TVal>**) fMemoryManager->allocate
220    (
221        fHashModulus * sizeof(RefHash3KeysTableBucketElem<TVal>*)
222    ); //new RefHash3KeysTableBucketElem<TVal>*[fHashModulus];
223    for (unsigned int index = 0; index < fHashModulus; index++)
224        fBucketList[index] = 0;
225}
226
227template <class TVal> RefHash3KeysIdPool<TVal>::~RefHash3KeysIdPool()
228{
229    removeAll();
230
231    // Then delete the bucket list & hasher & id pointers list
232    fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
233    fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
234    delete fHash;
235}
236
237
238// ---------------------------------------------------------------------------
239//  RefHash3KeysIdPool: Element management
240// ---------------------------------------------------------------------------
241template <class TVal> bool RefHash3KeysIdPool<TVal>::isEmpty() const
242{
243    // Just check the bucket list for non-empty elements
244    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
245    {
246        if (fBucketList[buckInd] != 0)
247            return false;
248    }
249    return true;
250}
251
252template <class TVal> bool RefHash3KeysIdPool<TVal>::
253containsKey(const void* const key1, const int key2, const int key3) const
254{
255    unsigned int hashVal;
256    const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
257    return (findIt != 0);
258}
259
260template <class TVal> void RefHash3KeysIdPool<TVal>::removeAll()
261{
262    // Clean up the buckets first
263    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
264    {
265        // Get the bucket list head for this entry
266        RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[buckInd];
267        RefHash3KeysTableBucketElem<TVal>* nextElem;
268        while (curElem)
269        {
270            // Save the next element before we hose this one
271            nextElem = curElem->fNext;
272
273            // If we adopted the data, then delete it too
274            //    (Note:  the userdata hash table instance has data type of void *.
275            //    This will generate compiler warnings here on some platforms, but they
276            //    can be ignored since fAdoptedElements is false.
277            if (fAdoptedElems)
278                delete curElem->fData;
279
280            // Then delete the current element and move forward
281            delete curElem;
282            curElem = nextElem;
283        }
284
285        // Clean out this entry
286        fBucketList[buckInd] = 0;
287    }
288
289    // Reset the id counter
290    fIdCounter = 0;
291}
292
293
294// ---------------------------------------------------------------------------
295//  RefHash3KeysIdPool: Getters
296// ---------------------------------------------------------------------------
297template <class TVal> TVal*
298RefHash3KeysIdPool<TVal>::getByKey(const void* const key1, const int key2, const int key3)
299{
300    unsigned int hashVal;
301    RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
302    if (!findIt)
303        return 0;
304    return findIt->fData;
305}
306
307template <class TVal> const TVal*
308RefHash3KeysIdPool<TVal>::getByKey(const void* const key1, const int key2, const int key3) const
309{
310    unsigned int hashVal;
311    const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
312    if (!findIt)
313        return 0;
314    return findIt->fData;
315}
316
317template <class TVal> TVal*
318RefHash3KeysIdPool<TVal>::getById(const unsigned int elemId)
319{
320    // If its either zero or beyond our current id, its an error
321    if (!elemId || (elemId > fIdCounter))
322        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
323
324    return fIdPtrs[elemId];
325}
326
327template <class TVal> const TVal*
328RefHash3KeysIdPool<TVal>::getById(const unsigned int elemId) const
329{
330    // If its either zero or beyond our current id, its an error
331    if (!elemId || (elemId > fIdCounter))
332        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
333
334    return fIdPtrs[elemId];
335}
336
337template <class TVal>
338MemoryManager* RefHash3KeysIdPool<TVal>::getMemoryManager() const
339{
340    return fMemoryManager;
341}
342// ---------------------------------------------------------------------------
343//  RefHash3KeysIdPool: Putters
344// ---------------------------------------------------------------------------
345template <class TVal> unsigned int
346RefHash3KeysIdPool<TVal>::put(void* key1, int key2, int key3, TVal* const valueToAdopt)
347{
348    // First see if the key exists already
349    unsigned int hashVal;
350    RefHash3KeysTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, key3, hashVal);
351
352    //
353    //  If so,then update its value. If not, then we need to add it to
354    //  the right bucket
355    //
356    if (newBucket)
357    {
358        if (fAdoptedElems)
359            delete newBucket->fData;
360        newBucket->fData = valueToAdopt;
361        newBucket->fKey1 = key1;
362        newBucket->fKey2 = key2;
363        newBucket->fKey3 = key3;
364    }
365     else
366    {
367    // Revisit: the gcc compiler 2.95.x is generating an
368    // internal compiler error message. So we use the default
369    // memory manager for now.
370#if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
371        newBucket = new RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
372#else
373        newBucket = new (fMemoryManager) RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
374#endif
375        fBucketList[hashVal] = newBucket;
376    }
377
378    //
379    //  Give this new one the next available id and add to the pointer list.
380    //  Expand the list if that is now required.
381    //
382    if (fIdCounter + 1 == fIdPtrsCount)
383    {
384        // Create a new count 1.5 times larger and allocate a new array
385        unsigned int newCount = (unsigned int)(fIdPtrsCount * 1.5);
386        TVal** newArray = (TVal**) fMemoryManager->allocate
387        (
388            newCount * sizeof(TVal*)
389        ); //new TVal*[newCount];
390
391        // Copy over the old contents to the new array
392        memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TVal*));
393
394        // Ok, toss the old array and store the new data
395        fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
396        fIdPtrs = newArray;
397        fIdPtrsCount = newCount;
398    }
399    const unsigned int retId = ++fIdCounter;
400    fIdPtrs[retId] = valueToAdopt;
401
402    // Set the id on the passed element
403    valueToAdopt->setId(retId);
404
405    // Return the id that we gave to this element
406    return retId;
407}
408
409// ---------------------------------------------------------------------------
410//  RefHash3KeysIdPool: Private methods
411// ---------------------------------------------------------------------------
412template <class TVal> RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal>::
413findBucketElem(const void* const key1, const int key2, const int key3, unsigned int& hashVal)
414{
415    // Hash the key
416    hashVal = fHash->getHashVal(key1, fHashModulus, fMemoryManager);
417    if (hashVal > fHashModulus)
418        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
419
420    // Search that bucket for the key
421    RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
422    while (curElem)
423    {
424                if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2) && (key3==curElem->fKey3))
425            return curElem;
426
427        curElem = curElem->fNext;
428    }
429    return 0;
430}
431
432template <class TVal> const RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal>::
433findBucketElem(const void* const key1, const int key2, const int key3, unsigned int& hashVal) const
434{
435    // Hash the key
436    hashVal = fHash->getHashVal(key1, fHashModulus);
437    if (hashVal > fHashModulus)
438        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::HshTbl_BadHashFromKey, fMemoryManager);
439
440    // Search that bucket for the key
441    const RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
442    while (curElem)
443    {
444        if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2) && (key3==curElem->fKey3))
445            return curElem;
446
447        curElem = curElem->fNext;
448    }
449    return 0;
450}
451
452
453// ---------------------------------------------------------------------------
454//  RefHash3KeysIdPoolEnumerator: Constructors and Destructor
455// ---------------------------------------------------------------------------
456template <class TVal> RefHash3KeysIdPoolEnumerator<TVal>::
457RefHash3KeysIdPoolEnumerator(RefHash3KeysIdPool<TVal>* const toEnum
458                             , const bool adopt
459                             , MemoryManager* const manager)
460        : fAdoptedElems(adopt), fCurIndex(0), fToEnum(toEnum), fMemoryManager(manager)
461{
462    if (!toEnum)
463        ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
464
465    Reset();
466    resetKey();
467}
468
469template <class TVal> RefHash3KeysIdPoolEnumerator<TVal>::~RefHash3KeysIdPoolEnumerator()
470{
471    if (fAdoptedElems)
472        delete fToEnum;
473}
474
475template <class TVal> RefHash3KeysIdPoolEnumerator<TVal>::
476RefHash3KeysIdPoolEnumerator(const RefHash3KeysIdPoolEnumerator<TVal>& toCopy) :
477    fAdoptedElems(toCopy.fAdoptedElems)
478    , fCurIndex(toCopy.fCurIndex)
479    , fToEnum(toCopy.fToEnum)
480    , fCurElem(toCopy.fCurElem)
481    , fCurHash(toCopy.fCurHash)   
482    , fMemoryManager(toCopy.fMemoryManager)
483{
484}
485
486// ---------------------------------------------------------------------------
487//  RefHash3KeysIdPoolEnumerator: Enum interface
488// ---------------------------------------------------------------------------
489template <class TVal> bool RefHash3KeysIdPoolEnumerator<TVal>::hasMoreElements() const
490{
491    // If our index is zero or past the end, then we are done
492    if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
493        return false;
494    return true;
495}
496
497template <class TVal> TVal& RefHash3KeysIdPoolEnumerator<TVal>::nextElement()
498{
499    // If our index is zero or past the end, then we are done
500    if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
501        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
502
503    // Return the current element and bump the index
504    return *fToEnum->fIdPtrs[fCurIndex++];
505}
506
507template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::Reset()
508{
509    //
510    //  Find the next available bucket element in the pool. We use the id
511    //  array since its very easy to enumerator through by just maintaining
512    //  an index. If the id counter is zero, then its empty and we leave the
513    //  current index to zero.
514    //
515    fCurIndex = fToEnum->fIdCounter ? 1:0;
516
517}
518
519template <class TVal> int RefHash3KeysIdPoolEnumerator<TVal>::size() const
520{
521    return fToEnum->fIdCounter;
522}
523
524template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::resetKey()
525{
526    fCurHash = (unsigned int)-1;
527    fCurElem = 0;
528    findNext();
529}
530
531template <class TVal> bool RefHash3KeysIdPoolEnumerator<TVal>::hasMoreKeys() const
532{
533    //
534    //  If our current has is at the max and there are no more elements
535    //  in the current bucket, then no more elements.
536    //
537    if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
538        return false;
539
540    return true;
541}
542
543template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::nextElementKey(void*& retKey1, int& retKey2, int& retKey3)
544{
545    // Make sure we have an element to return
546    if (!hasMoreKeys())
547        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
548
549    //
550    //  Save the current element, then move up to the next one for the
551    //  next time around.
552    //
553    RefHash3KeysTableBucketElem<TVal>* saveElem = fCurElem;
554    findNext();
555
556    retKey1 = saveElem->fKey1;
557    retKey2 = saveElem->fKey2;
558    retKey3 = saveElem->fKey3;
559
560    return;
561}
562
563template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::findNext()
564{
565    //
566    //  If there is a current element, move to its next element. If this
567    //  hits the end of the bucket, the next block will handle the rest.
568    //
569    if (fCurElem)
570        fCurElem = fCurElem->fNext;
571
572    //
573    //  If the current element is null, then we have to move up to the
574    //  next hash value. If that is the hash modulus, then we cannot
575    //  go further.
576    //
577    if (!fCurElem)
578    {
579        fCurHash++;
580        if (fCurHash == fToEnum->fHashModulus)
581            return;
582
583        // Else find the next non-empty bucket
584        while (true)
585        {
586            if (fToEnum->fBucketList[fCurHash])
587                break;
588
589            // Bump to the next hash value. If we max out return
590            fCurHash++;
591            if (fCurHash == fToEnum->fHashModulus)
592                return;
593        }
594        fCurElem = fToEnum->fBucketList[fCurHash];
595    }
596}
597
598XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.