xercesc/util/RefHash3KeysIdPool.hpp

0001 /*
0002  * Licensed to the Apache Software Foundation (ASF) under one or more
0003  * contributor license agreements.  See the NOTICE file distributed with
0004  * this work for additional information regarding copyright ownership.
0005  * The ASF licenses this file to You under the Apache License, Version 2.0
0006  * (the "License"); you may not use this file except in compliance with
0007  * the License.  You may obtain a copy of the License at
0008  *
0009  *      http://www.apache.org/licenses/LICENSE-2.0
0010  *
0011  * Unless required by applicable law or agreed to in writing, software
0012  * distributed under the License is distributed on an "AS IS" BASIS,
0013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014  * See the License for the specific language governing permissions and
0015  * limitations under the License.
0016  */
0017
0018 /*
0019  * $Id$
0020  */
0021
0022 #if !defined(XERCESC_INCLUDE_GUARD_REFHASH3KEYSIDPOOL_HPP)
0023 #define XERCESC_INCLUDE_GUARD_REFHASH3KEYSIDPOOL_HPP
0024
0025
0026 #include <xercesc/util/Hashers.hpp>
0027 #include <xercesc/util/IllegalArgumentException.hpp>
0028 #include <xercesc/util/NoSuchElementException.hpp>
0029 #include <xercesc/util/RuntimeException.hpp>
0030 #include <xercesc/util/PlatformUtils.hpp>
0031
0032 XERCES_CPP_NAMESPACE_BEGIN
0033
0034 // This hash table is a combination of RefHash2KeyTableOf (with an additional integer as key3)
0035 // and NameIdPool with an id as index
0036
0037 //  Forward declare the enumerator so it can be our friend.
0038 //
0039 template <class TVal, class THasher = StringHasher>
0040 class RefHash3KeysIdPoolEnumerator;
0041
0042
0043 //
0044 //  This should really be a nested class, but some of the compilers we
0045 //  have to support cannot deal with that!
0046 //
0047 template <class TVal>
0048 struct RefHash3KeysTableBucketElem
0049 {
0050     RefHash3KeysTableBucketElem(
0051               void* key1
0052               , int key2
0053               , int key3
0054               , TVal* const value
0055               , RefHash3KeysTableBucketElem<TVal>* next) :
0056         fData(value)
0057     , fNext(next)
0058     , fKey1(key1)
0059     , fKey2(key2)
0060     , fKey3(key3)
0061     {
0062     }
0063
0064     RefHash3KeysTableBucketElem() {};
0065     ~RefHash3KeysTableBucketElem() {};
0066
0067     TVal*  fData;
0068     RefHash3KeysTableBucketElem<TVal>*   fNext;
0069     void*  fKey1;
0070     int    fKey2;
0071     int    fKey3;
0072
0073 private:
0074     // -----------------------------------------------------------------------
0075     //  Unimplemented constructors and operators
0076     // -----------------------------------------------------------------------
0077     RefHash3KeysTableBucketElem(const RefHash3KeysTableBucketElem<TVal>&);
0078     RefHash3KeysTableBucketElem<TVal>& operator=(const RefHash3KeysTableBucketElem<TVal>&);
0079 };
0080
0081
0082 template <class TVal, class THasher = StringHasher>
0083 class RefHash3KeysIdPool : public XMemory
0084 {
0085 public:
0086     // -----------------------------------------------------------------------
0087     //  Constructors and Destructor
0088     // -----------------------------------------------------------------------
0089     RefHash3KeysIdPool(
0090       const XMLSize_t modulus,
0091       const XMLSize_t initSize = 128,
0092       MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0093
0094     RefHash3KeysIdPool(
0095       const XMLSize_t modulus,
0096       const THasher& hasher,
0097       const XMLSize_t initSize = 128,
0098       MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0099
0100     RefHash3KeysIdPool(
0101       const XMLSize_t modulus,
0102       const bool adoptElems,
0103       const XMLSize_t initSize = 128,
0104       MemoryManager* const manager =  XMLPlatformUtils::fgMemoryManager);
0105
0106     RefHash3KeysIdPool(
0107       const XMLSize_t modulus,
0108       const bool adoptElems,
0109       const THasher& hasher,
0110       const XMLSize_t initSize = 128,
0111       MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0112
0113     ~RefHash3KeysIdPool();
0114
0115     // -----------------------------------------------------------------------
0116     //  Element management
0117     // -----------------------------------------------------------------------
0118     bool isEmpty() const;
0119     bool containsKey(const void* const key1, const int key2, const int key3) const;
0120     void removeAll();
0121
0122
0123     // -----------------------------------------------------------------------
0124     //  Getters
0125     // -----------------------------------------------------------------------
0126     TVal* getByKey(const void* const key1, const int key2, const int key3);
0127     const TVal* getByKey(const void* const key1, const int key2, const int key3) const;
0128
0129     TVal* getById(const unsigned int elemId);
0130     const TVal* getById(const unsigned int elemId) const;
0131
0132     MemoryManager* getMemoryManager() const;
0133     XMLSize_t      getHashModulus()   const;
0134
0135     // -----------------------------------------------------------------------
0136     //  Putters
0137     // -----------------------------------------------------------------------
0138     XMLSize_t put(void* key1, int key2, int key3, TVal* const valueToAdopt);
0139
0140
0141 private :
0142     // -----------------------------------------------------------------------
0143     //  Declare our friends
0144     // -----------------------------------------------------------------------
0145     friend class RefHash3KeysIdPoolEnumerator<TVal, THasher>;
0146
0147 private:
0148     // -----------------------------------------------------------------------
0149     //  Unimplemented constructors and operators
0150     // -----------------------------------------------------------------------
0151     RefHash3KeysIdPool(const RefHash3KeysIdPool<TVal, THasher>&);
0152     RefHash3KeysIdPool<TVal, THasher>& operator=(const RefHash3KeysIdPool<TVal, THasher>&);
0153
0154     // -----------------------------------------------------------------------
0155     //  Private methods
0156     // -----------------------------------------------------------------------
0157     RefHash3KeysTableBucketElem<TVal>* findBucketElem(const void* const key1, const int key2, const int key3, XMLSize_t& hashVal);
0158     const RefHash3KeysTableBucketElem<TVal>* findBucketElem(const void* const key1, const int key2, const int key3, XMLSize_t& hashVal) const;
0159     void initialize(const XMLSize_t modulus);
0160
0161
0162     // -----------------------------------------------------------------------
0163     //  Data members
0164     //
0165     //  fAdoptedElems
0166     //      Indicates whether the values added are adopted or just referenced.
0167     //      If adopted, then they are deleted when they are removed from the
0168     //      hash table.
0169     //
0170     //  fBucketList
0171     //      This is the array that contains the heads of all of the list
0172     //      buckets, one for each possible hash value.
0173     //
0174     //  fHashModulus
0175     //      The modulus used for this hash table, to hash the keys. This is
0176     //      also the number of elements in the bucket list.
0177     //
0178     //  fHash
0179     //      The hasher for the key1 data type.
0180     //
0181     //  fIdPtrs
0182     //  fIdPtrsCount
0183     //      This is the array of pointers to the bucket elements in order of
0184     //      their assigned ids. So taking id N and referencing this array
0185     //      gives you the element with that id. The count field indicates
0186     //      the current size of this list. When fIdCounter+1 reaches this
0187     //      value the list must be expanded.
0188     //
0189     //  fIdCounter
0190     //      This is used to give out unique ids to added elements. It starts
0191     //      at zero (which means empty), and is bumped up for each newly added
0192     //      element. So the first element is 1, the next is 2, etc... This
0193     //      means that this value is set to the top index of the fIdPtrs array.
0194     // -----------------------------------------------------------------------
0195     MemoryManager*                      fMemoryManager;
0196     bool                                fAdoptedElems;
0197     RefHash3KeysTableBucketElem<TVal>** fBucketList;
0198     XMLSize_t                           fHashModulus;
0199     TVal**                              fIdPtrs;
0200     XMLSize_t                           fIdPtrsCount;
0201     XMLSize_t                           fIdCounter;
0202     THasher                             fHasher;
0203 };
0204
0205
0206
0207 //
0208 //  An enumerator for a value array. It derives from the basic enumerator
0209 //  class, so that value vectors can be generically enumerated.
0210 //
0211 template <class TVal, class THasher>
0212 class RefHash3KeysIdPoolEnumerator : public XMLEnumerator<TVal>, public XMemory
0213 {
0214 public :
0215     // -----------------------------------------------------------------------
0216     //  Constructors and Destructor
0217     // -----------------------------------------------------------------------
0218     RefHash3KeysIdPoolEnumerator(RefHash3KeysIdPool<TVal, THasher>* const toEnum
0219         , const bool adopt = false
0220         , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0221     virtual ~RefHash3KeysIdPoolEnumerator();
0222
0223     RefHash3KeysIdPoolEnumerator(const RefHash3KeysIdPoolEnumerator<TVal, THasher>&);
0224     // -----------------------------------------------------------------------
0225     //  Enum interface
0226     // -----------------------------------------------------------------------
0227     bool hasMoreElements() const;
0228     TVal& nextElement();
0229     void Reset();
0230     XMLSize_t size() const;
0231
0232     // -----------------------------------------------------------------------
0233     //  New interface
0234     // -----------------------------------------------------------------------
0235     void resetKey();
0236     void nextElementKey(void*&, int&, int&);
0237     bool hasMoreKeys()   const;
0238
0239 private :
0240     // -----------------------------------------------------------------------
0241     //  Unimplemented constructors and operators
0242     // -----------------------------------------------------------------------
0243     RefHash3KeysIdPoolEnumerator<TVal, THasher>&
0244     operator=(const RefHash3KeysIdPoolEnumerator<TVal, THasher>&);
0245
0246     // -----------------------------------------------------------------------
0247     //  Private methods
0248     // -----------------------------------------------------------------------
0249     void findNext();
0250
0251     // -----------------------------------------------------------------------
0252     //  Data Members
0253     //  fAdoptedElems
0254     //      Indicates whether the values added are adopted or just referenced.
0255     //      If adopted, then they are deleted when they are removed from the
0256     //      hash table
0257     //
0258     //  fCurIndex
0259     //      This is the current index into the pool's id mapping array. This
0260     //      is now we enumerate it.
0261     //
0262     //  fToEnum
0263     //      The name id pool that is being enumerated.
0264     // -----------------------------------------------------------------------
0265     bool                                fAdoptedElems;
0266     XMLSize_t                           fCurIndex;
0267     RefHash3KeysIdPool<TVal, THasher>*  fToEnum;
0268     RefHash3KeysTableBucketElem<TVal>*  fCurElem;
0269     XMLSize_t                           fCurHash;
0270     MemoryManager* const                fMemoryManager;
0271 };
0272
0273 XERCES_CPP_NAMESPACE_END
0274
0275 #if !defined(XERCES_TMPLSINC)
0276 #include <xercesc/util/RefHash3KeysIdPool.c>
0277 #endif
0278
0279 #endif