source: icXML/icXML-devel/src/xercesc/util/RefHash3KeysIdPool.c @ 2722

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

Original Xerces files with import mods for icxercesc

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