source: NonGTP/Xerces/xerces-c_2_8_0/include/xercesc/util/RefHash3KeysIdPool.c @ 2674

Revision 2674, 17.4 KB checked in by mattausch, 16 years ago (diff)
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: RefHash3KeysIdPool.c 568078 2007-08-21 11:43:25Z amassari $
20 */
21
22
23// ---------------------------------------------------------------------------
24//  Include
25// ---------------------------------------------------------------------------
26#if defined(XERCES_TMPLSINC)
27#include <xercesc/util/RefHash3KeysIdPool.hpp>
28#endif
29
30#include <xercesc/util/NullPointerException.hpp>
31#include <assert.h>
32#include <new>
33
34XERCES_CPP_NAMESPACE_BEGIN
35
36// ---------------------------------------------------------------------------
37//  RefHash3KeysIdPool: Constructors and Destructor
38// ---------------------------------------------------------------------------
39template <class TVal>
40RefHash3KeysIdPool<TVal>::RefHash3KeysIdPool( const unsigned int modulus
41                                            , const bool         adoptElems
42                                            , const unsigned int initSize
43                                            , MemoryManager* const manager) :
44    fMemoryManager(manager)
45    , fAdoptedElems(adoptElems)
46    , fBucketList(0)
47    , fHashModulus(modulus)
48    , fHash(0)
49    , fIdPtrs(0)
50    , fIdPtrsCount(initSize)
51    , fIdCounter(0)
52{
53    initialize(modulus);
54
55    // create default hasher
56#if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
57                 fHash = new HashXMLCh();
58#else
59    fHash = new (fMemoryManager) HashXMLCh();
60#endif
61
62    //
63    //  Allocate the initial id pointers array. We don't have to zero them
64    //  out since the fIdCounter value tells us which ones are valid. The
65    //  zeroth element is never used (and represents an invalid pool id.)
66    //
67    if (!fIdPtrsCount)
68        fIdPtrsCount = 256;
69    fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
70    fIdPtrs[0] = 0;
71}
72
73template <class TVal>
74RefHash3KeysIdPool<TVal>::RefHash3KeysIdPool( const unsigned int modulus
75                                            , const bool         adoptElems
76                                            , HashBase*          hashBase
77                                            , const unsigned int initSize
78                                            , MemoryManager* const manager) :
79        fMemoryManager(manager)
80    , fAdoptedElems(adoptElems)
81    , fBucketList(0)
82    , fHashModulus(modulus)
83    , fHash(0)
84    , fIdPtrs(0)
85    , fIdPtrsCount(initSize)
86    , fIdCounter(0)
87{
88    initialize(modulus);
89    // set hasher
90    fHash = hashBase;
91
92    //
93    //  Allocate the initial id pointers array. We don't have to zero them
94    //  out since the fIdCounter value tells us which ones are valid. The
95    //  zeroth element is never used (and represents an invalid pool id.)
96    //
97    if (!fIdPtrsCount)
98        fIdPtrsCount = 256;
99    fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
100    fIdPtrs[0] = 0;
101}
102
103template <class TVal>
104RefHash3KeysIdPool<TVal>::RefHash3KeysIdPool( const unsigned int modulus
105                                            , const unsigned int initSize
106                                            , MemoryManager* const manager) :
107        fMemoryManager(manager)
108    , fAdoptedElems(true)
109    , fBucketList(0)
110    , fHashModulus(modulus)
111    , fHash(0)
112    , fIdPtrs(0)
113    , fIdPtrsCount(initSize)
114    , fIdCounter(0)
115{
116    initialize(modulus);
117
118    // create default hasher
119#if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
120                 fHash = new HashXMLCh();
121#else
122    fHash = new (fMemoryManager) HashXMLCh();
123#endif   
124
125    //
126    //  Allocate the initial id pointers array. We don't have to zero them
127    //  out since the fIdCounter value tells us which ones are valid. The
128    //  zeroth element is never used (and represents an invalid pool id.)
129    //
130    if (!fIdPtrsCount)
131        fIdPtrsCount = 256;
132    fIdPtrs = (TVal**) fMemoryManager->allocate(fIdPtrsCount * sizeof(TVal*)); //new TVal*[fIdPtrsCount];
133    fIdPtrs[0] = 0;
134}
135
136template <class TVal> void RefHash3KeysIdPool<TVal>::initialize(const unsigned int modulus)
137{
138        if (modulus == 0)
139        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);
140
141    // Allocate the bucket list and zero them
142    fBucketList = (RefHash3KeysTableBucketElem<TVal>**) fMemoryManager->allocate
143    (
144        fHashModulus * sizeof(RefHash3KeysTableBucketElem<TVal>*)
145    ); //new RefHash3KeysTableBucketElem<TVal>*[fHashModulus];
146    memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);
147}
148
149template <class TVal> RefHash3KeysIdPool<TVal>::~RefHash3KeysIdPool()
150{
151    removeAll();
152
153    // Then delete the bucket list & hasher & id pointers list
154    fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
155    fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;
156    delete fHash;
157}
158
159
160// ---------------------------------------------------------------------------
161//  RefHash3KeysIdPool: Element management
162// ---------------------------------------------------------------------------
163template <class TVal> bool RefHash3KeysIdPool<TVal>::isEmpty() const
164{
165    // Just check the bucket list for non-empty elements
166    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
167    {
168        if (fBucketList[buckInd] != 0)
169            return false;
170    }
171    return true;
172}
173
174template <class TVal> bool RefHash3KeysIdPool<TVal>::
175containsKey(const void* const key1, const int key2, const int key3) const
176{
177    unsigned int hashVal;
178    const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
179    return (findIt != 0);
180}
181
182template <class TVal> void RefHash3KeysIdPool<TVal>::removeAll()
183{
184    if (fIdCounter == 0) return;
185
186    // Clean up the buckets first
187    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)
188    {
189        // Get the bucket list head for this entry
190        RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[buckInd];
191        RefHash3KeysTableBucketElem<TVal>* nextElem;
192        while (curElem)
193        {
194            // Save the next element before we hose this one
195            nextElem = curElem->fNext;
196
197            // If we adopted the data, then delete it too
198            //    (Note:  the userdata hash table instance has data type of void *.
199            //    This will generate compiler warnings here on some platforms, but they
200            //    can be ignored since fAdoptedElements is false.
201            if (fAdoptedElems)
202                delete curElem->fData;
203
204            // Then delete the current element and move forward
205            // delete curElem;
206            // destructor is empty...
207            // curElem->~RefHash3KeysTableBucketElem();
208            fMemoryManager->deallocate(curElem);
209            curElem = nextElem;
210        }
211
212        // Clean out this entry
213        fBucketList[buckInd] = 0;
214    }
215
216    // Reset the id counter
217    fIdCounter = 0;
218}
219
220
221// ---------------------------------------------------------------------------
222//  RefHash3KeysIdPool: Getters
223// ---------------------------------------------------------------------------
224template <class TVal> TVal*
225RefHash3KeysIdPool<TVal>::getByKey(const void* const key1, const int key2, const int key3)
226{
227    unsigned int hashVal;
228    RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
229    if (!findIt)
230        return 0;
231    return findIt->fData;
232}
233
234template <class TVal> const TVal*
235RefHash3KeysIdPool<TVal>::getByKey(const void* const key1, const int key2, const int key3) const
236{
237    unsigned int hashVal;
238    const RefHash3KeysTableBucketElem<TVal>* findIt = findBucketElem(key1, key2, key3, hashVal);
239    if (!findIt)
240        return 0;
241    return findIt->fData;
242}
243
244template <class TVal> TVal*
245RefHash3KeysIdPool<TVal>::getById(const unsigned int elemId)
246{
247    // If its either zero or beyond our current id, its an error
248    if (!elemId || (elemId > fIdCounter))
249        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
250
251    return fIdPtrs[elemId];
252}
253
254template <class TVal> const TVal*
255RefHash3KeysIdPool<TVal>::getById(const unsigned int elemId) const
256{
257    // If its either zero or beyond our current id, its an error
258    if (!elemId || (elemId > fIdCounter))
259        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::Pool_InvalidId, fMemoryManager);
260
261    return fIdPtrs[elemId];
262}
263
264template <class TVal>
265MemoryManager* RefHash3KeysIdPool<TVal>::getMemoryManager() const
266{
267    return fMemoryManager;
268}
269
270template <class TVal>
271unsigned int RefHash3KeysIdPool<TVal>::getHashModulus() const
272{
273    return fHashModulus;
274}
275
276// ---------------------------------------------------------------------------
277//  RefHash3KeysIdPool: Putters
278// ---------------------------------------------------------------------------
279template <class TVal> unsigned int
280RefHash3KeysIdPool<TVal>::put(void* key1, int key2, int key3, TVal* const valueToAdopt)
281{
282    // First see if the key exists already
283    unsigned int hashVal;
284    RefHash3KeysTableBucketElem<TVal>* newBucket = findBucketElem(key1, key2, key3, hashVal);
285
286    //
287    //  If so,then update its value. If not, then we need to add it to
288    //  the right bucket
289    //
290    if (newBucket)
291    {
292        if (fAdoptedElems)
293            delete newBucket->fData;
294        newBucket->fData = valueToAdopt;
295        newBucket->fKey1 = key1;
296        newBucket->fKey2 = key2;
297        newBucket->fKey3 = key3;
298    }
299     else
300    {
301    // Revisit: the gcc compiler 2.95.x is generating an
302    // internal compiler error message. So we use the default
303    // memory manager for now.
304#if defined (XML_GCC_VERSION) && (XML_GCC_VERSION < 29600)
305        newBucket = new RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
306#else
307        newBucket =
308            new (fMemoryManager->allocate(sizeof(RefHash3KeysTableBucketElem<TVal>)))
309            RefHash3KeysTableBucketElem<TVal>(key1, key2, key3, valueToAdopt, fBucketList[hashVal]);
310#endif
311        fBucketList[hashVal] = newBucket;
312    }
313
314    //
315    //  Give this new one the next available id and add to the pointer list.
316    //  Expand the list if that is now required.
317    //
318    if (fIdCounter + 1 == fIdPtrsCount)
319    {
320        // Create a new count 1.5 times larger and allocate a new array
321        unsigned int newCount = (unsigned int)(fIdPtrsCount * 1.5);
322        TVal** newArray = (TVal**) fMemoryManager->allocate
323        (
324            newCount * sizeof(TVal*)
325        ); //new TVal*[newCount];
326
327        // Copy over the old contents to the new array
328        memcpy(newArray, fIdPtrs, fIdPtrsCount * sizeof(TVal*));
329
330        // Ok, toss the old array and store the new data
331        fMemoryManager->deallocate(fIdPtrs); //delete [] fIdPtrs;
332        fIdPtrs = newArray;
333        fIdPtrsCount = newCount;
334    }
335    const unsigned int retId = ++fIdCounter;
336    fIdPtrs[retId] = valueToAdopt;
337
338    // Set the id on the passed element
339    valueToAdopt->setId(retId);
340
341    // Return the id that we gave to this element
342    return retId;
343}
344
345// ---------------------------------------------------------------------------
346//  RefHash3KeysIdPool: Private methods
347// ---------------------------------------------------------------------------
348template <class TVal> RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal>::
349findBucketElem(const void* const key1, const int key2, const int key3, unsigned int& hashVal)
350{
351    // Hash the key
352    hashVal = fHash->getHashVal(key1, fHashModulus, fMemoryManager);
353    assert(hashVal < fHashModulus);
354
355    // Search that bucket for the key
356    RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
357    while (curElem)
358    {
359                if (key2==curElem->fKey2 && key3==curElem->fKey3 && fHash->equals(key1, curElem->fKey1))
360            return curElem;
361
362        curElem = curElem->fNext;
363    }
364    return 0;
365}
366
367template <class TVal> const RefHash3KeysTableBucketElem<TVal>* RefHash3KeysIdPool<TVal>::
368findBucketElem(const void* const key1, const int key2, const int key3, unsigned int& hashVal) const
369{
370    // Hash the key
371    hashVal = fHash->getHashVal(key1, fHashModulus);
372    assert(hashVal < fHashModulus);
373
374    // Search that bucket for the key
375    const RefHash3KeysTableBucketElem<TVal>* curElem = fBucketList[hashVal];
376    while (curElem)
377    {
378        if (fHash->equals(key1, curElem->fKey1) && (key2==curElem->fKey2) && (key3==curElem->fKey3))
379            return curElem;
380
381        curElem = curElem->fNext;
382    }
383    return 0;
384}
385
386
387// ---------------------------------------------------------------------------
388//  RefHash3KeysIdPoolEnumerator: Constructors and Destructor
389// ---------------------------------------------------------------------------
390template <class TVal> RefHash3KeysIdPoolEnumerator<TVal>::
391RefHash3KeysIdPoolEnumerator(RefHash3KeysIdPool<TVal>* const toEnum
392                             , const bool adopt
393                             , MemoryManager* const manager)
394        : fAdoptedElems(adopt), fCurIndex(0), fToEnum(toEnum), fMemoryManager(manager)
395{
396    if (!toEnum)
397        ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, fMemoryManager);
398
399    Reset();
400    resetKey();
401}
402
403template <class TVal> RefHash3KeysIdPoolEnumerator<TVal>::~RefHash3KeysIdPoolEnumerator()
404{
405    if (fAdoptedElems)
406        delete fToEnum;
407}
408
409template <class TVal> RefHash3KeysIdPoolEnumerator<TVal>::
410RefHash3KeysIdPoolEnumerator(const RefHash3KeysIdPoolEnumerator<TVal>& toCopy) :
411    XMLEnumerator<TVal>(toCopy)
412    , XMemory(toCopy)
413    , fAdoptedElems(toCopy.fAdoptedElems)
414    , fCurIndex(toCopy.fCurIndex)
415    , fToEnum(toCopy.fToEnum)
416    , fCurElem(toCopy.fCurElem)
417    , fCurHash(toCopy.fCurHash)   
418    , fMemoryManager(toCopy.fMemoryManager)
419{
420}
421
422// ---------------------------------------------------------------------------
423//  RefHash3KeysIdPoolEnumerator: Enum interface
424// ---------------------------------------------------------------------------
425template <class TVal> bool RefHash3KeysIdPoolEnumerator<TVal>::hasMoreElements() const
426{
427    // If our index is zero or past the end, then we are done
428    if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
429        return false;
430    return true;
431}
432
433template <class TVal> TVal& RefHash3KeysIdPoolEnumerator<TVal>::nextElement()
434{
435    // If our index is zero or past the end, then we are done
436    if (!fCurIndex || (fCurIndex > fToEnum->fIdCounter))
437        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
438
439    // Return the current element and bump the index
440    return *fToEnum->fIdPtrs[fCurIndex++];
441}
442
443template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::Reset()
444{
445    //
446    //  Find the next available bucket element in the pool. We use the id
447    //  array since its very easy to enumerator through by just maintaining
448    //  an index. If the id counter is zero, then its empty and we leave the
449    //  current index to zero.
450    //
451    fCurIndex = fToEnum->fIdCounter ? 1:0;
452
453}
454
455template <class TVal> int RefHash3KeysIdPoolEnumerator<TVal>::size() const
456{
457    return fToEnum->fIdCounter;
458}
459
460template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::resetKey()
461{
462    fCurHash = (unsigned int)-1;
463    fCurElem = 0;
464    findNext();
465}
466
467template <class TVal> bool RefHash3KeysIdPoolEnumerator<TVal>::hasMoreKeys() const
468{
469    //
470    //  If our current has is at the max and there are no more elements
471    //  in the current bucket, then no more elements.
472    //
473    if (!fCurElem && (fCurHash == fToEnum->fHashModulus))
474        return false;
475
476    return true;
477}
478
479template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::nextElementKey(void*& retKey1, int& retKey2, int& retKey3)
480{
481    // Make sure we have an element to return
482    if (!hasMoreKeys())
483        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::Enum_NoMoreElements, fMemoryManager);
484
485    //
486    //  Save the current element, then move up to the next one for the
487    //  next time around.
488    //
489    RefHash3KeysTableBucketElem<TVal>* saveElem = fCurElem;
490    findNext();
491
492    retKey1 = saveElem->fKey1;
493    retKey2 = saveElem->fKey2;
494    retKey3 = saveElem->fKey3;
495
496    return;
497}
498
499template <class TVal> void RefHash3KeysIdPoolEnumerator<TVal>::findNext()
500{
501    //
502    //  If there is a current element, move to its next element. If this
503    //  hits the end of the bucket, the next block will handle the rest.
504    //
505    if (fCurElem)
506        fCurElem = fCurElem->fNext;
507
508    //
509    //  If the current element is null, then we have to move up to the
510    //  next hash value. If that is the hash modulus, then we cannot
511    //  go further.
512    //
513    if (!fCurElem)
514    {
515        fCurHash++;
516        if (fCurHash == fToEnum->fHashModulus)
517            return;
518
519        // Else find the next non-empty bucket
520        while (fToEnum->fBucketList[fCurHash]==0)
521        {
522            // Bump to the next hash value. If we max out return
523            fCurHash++;
524            if (fCurHash == fToEnum->fHashModulus)
525                return;
526        }
527        fCurElem = fToEnum->fBucketList[fCurHash];
528    }
529}
530
531XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.