xercesc/util/RefHashTableOf.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_REFHASHTABLEOF_HPP)
0023 #define XERCESC_INCLUDE_GUARD_REFHASHTABLEOF_HPP
0024
0025 #include <xercesc/util/Hashers.hpp>
0026 #include <xercesc/util/IllegalArgumentException.hpp>
0027 #include <xercesc/util/NoSuchElementException.hpp>
0028 #include <xercesc/util/RuntimeException.hpp>
0029 #include <xercesc/util/PlatformUtils.hpp>
0030 #include <xercesc/framework/MemoryManager.hpp>
0031
0032 XERCES_CPP_NAMESPACE_BEGIN
0033
0034 //  Forward declare the enumerator so it can be our friend.
0035 //
0036 template <class TVal, class THasher = StringHasher>
0037 class RefHashTableOfEnumerator;
0038
0039 //
0040 //  This should really be a nested class, but some of the compilers we
0041 //  have to support cannot deal with that!
0042 //
0043 template <class TVal>
0044 struct RefHashTableBucketElem
0045 {
0046   RefHashTableBucketElem(void* key, TVal* const value, RefHashTableBucketElem<TVal>* next)
0047       : fData(value), fNext(next), fKey(key)
0048   {
0049   }
0050
0051   RefHashTableBucketElem(){};
0052   ~RefHashTableBucketElem(){};
0053
0054   TVal*                           fData;
0055   RefHashTableBucketElem<TVal>*   fNext;
0056   void*                           fKey;
0057
0058 private:
0059     // -----------------------------------------------------------------------
0060     //  Unimplemented constructors and operators
0061     // -----------------------------------------------------------------------
0062   RefHashTableBucketElem(const RefHashTableBucketElem<TVal>&);
0063   RefHashTableBucketElem<TVal>& operator=(const RefHashTableBucketElem<TVal>&);
0064 };
0065
0066
0067 template <class TVal, class THasher = StringHasher>
0068 class RefHashTableOf : public XMemory
0069 {
0070 public:
0071     // -----------------------------------------------------------------------
0072     //  Constructors and Destructor
0073     // -----------------------------------------------------------------------
0074     RefHashTableOf(
0075       const XMLSize_t modulus,
0076       MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0077
0078     RefHashTableOf(
0079       const XMLSize_t modulus,
0080       const THasher& hasher,
0081       MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0082
0083     RefHashTableOf(
0084       const XMLSize_t modulus,
0085       const bool adoptElems,
0086       MemoryManager* const manager =  XMLPlatformUtils::fgMemoryManager);
0087
0088     RefHashTableOf(
0089       const XMLSize_t modulus,
0090       const bool adoptElems,
0091       const THasher& hasher,
0092       MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0093
0094     ~RefHashTableOf();
0095
0096
0097     // -----------------------------------------------------------------------
0098     //  Element management
0099     // -----------------------------------------------------------------------
0100     bool isEmpty() const;
0101     bool containsKey(const void* const key) const;
0102     void removeKey(const void* const key);
0103     void removeAll();
0104     void cleanup();
0105     void reinitialize(const THasher& hasher);
0106     void transferElement(const void* const key1, void* key2);
0107     TVal* orphanKey(const void* const key);
0108
0109     // -----------------------------------------------------------------------
0110     //  Getters
0111     // -----------------------------------------------------------------------
0112     TVal* get(const void* const key);
0113     const TVal* get(const void* const key) const;
0114     MemoryManager* getMemoryManager() const;
0115     XMLSize_t      getHashModulus()   const;
0116     XMLSize_t      getCount() const;
0117
0118     // -----------------------------------------------------------------------
0119     //  Setters
0120     // -----------------------------------------------------------------------
0121     void setAdoptElements(const bool aValue);
0122
0123
0124     // -----------------------------------------------------------------------
0125     //  Putters
0126     // -----------------------------------------------------------------------
0127     void put(void* key, TVal* const valueToAdopt);
0128
0129
0130 private :
0131     // -----------------------------------------------------------------------
0132     //  Declare our friends
0133     // -----------------------------------------------------------------------
0134     friend class RefHashTableOfEnumerator<TVal, THasher>;
0135
0136 private:
0137     // -----------------------------------------------------------------------
0138     //  Unimplemented constructors and operators
0139     // -----------------------------------------------------------------------
0140     RefHashTableOf(const RefHashTableOf<TVal, THasher>&);
0141     RefHashTableOf<TVal, THasher>& operator=(const RefHashTableOf<TVal, THasher>&);
0142
0143     // -----------------------------------------------------------------------
0144     //  Private methods
0145     // -----------------------------------------------------------------------
0146     RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, XMLSize_t& hashVal);
0147     const RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, XMLSize_t& hashVal) const;
0148     void initialize(const XMLSize_t modulus);
0149     void rehash();
0150
0151
0152     // -----------------------------------------------------------------------
0153     //  Data members
0154     //
0155     //  fAdoptedElems
0156     //      Indicates whether the values added are adopted or just referenced.
0157     //      If adopted, then they are deleted when they are removed from the
0158     //      hash table.
0159     //
0160     //  fBucketList
0161     //      This is the array that contains the heads of all of the list
0162     //      buckets, one for each possible hash value.
0163     //
0164     //  fHashModulus
0165     //      The modulus used for this hash table, to hash the keys. This is
0166     //      also the number of elements in the bucket list.
0167     //
0168     //  fHash
0169     //      The hasher for the key data type.
0170     // -----------------------------------------------------------------------
0171     MemoryManager*                 fMemoryManager;
0172     bool                           fAdoptedElems;
0173     RefHashTableBucketElem<TVal>** fBucketList;
0174     XMLSize_t                      fHashModulus;
0175     XMLSize_t                      fInitialModulus;
0176     XMLSize_t                      fCount;
0177     THasher                        fHasher;
0178 };
0179
0180
0181
0182 //
0183 //  An enumerator for a value array. It derives from the basic enumerator
0184 //  class, so that value vectors can be generically enumerated.
0185 //
0186 template <class TVal, class THasher>
0187 class RefHashTableOfEnumerator : public XMLEnumerator<TVal>, public XMemory
0188 {
0189 public :
0190     // -----------------------------------------------------------------------
0191     //  Constructors and Destructor
0192     // -----------------------------------------------------------------------
0193     RefHashTableOfEnumerator(RefHashTableOf<TVal, THasher>* const toEnum
0194         , const bool adopt = false
0195         , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager);
0196     virtual ~RefHashTableOfEnumerator();
0197
0198     RefHashTableOfEnumerator(const RefHashTableOfEnumerator<TVal, THasher>&);
0199     // -----------------------------------------------------------------------
0200     //  Enum interface
0201     // -----------------------------------------------------------------------
0202     bool hasMoreElements() const;
0203     TVal& nextElement();
0204     void Reset();
0205
0206     // -----------------------------------------------------------------------
0207     //  New interface specific for key used in RefHashable
0208     // -----------------------------------------------------------------------
0209     void* nextElementKey();
0210
0211 private :
0212     // -----------------------------------------------------------------------
0213     //  Unimplemented constructors and operators
0214     // -----------------------------------------------------------------------
0215     RefHashTableOfEnumerator<TVal, THasher>&
0216     operator=(const RefHashTableOfEnumerator<TVal, THasher>&);
0217
0218     // -----------------------------------------------------------------------
0219     //  Private methods
0220     // -----------------------------------------------------------------------
0221     void findNext();
0222
0223
0224     // -----------------------------------------------------------------------
0225     //  Data Members
0226     //
0227     //  fAdopted
0228     //      Indicates whether we have adopted the passed vector. If so then
0229     //      we delete the vector when we are destroyed.
0230     //
0231     //  fCurElem
0232     //      This is the current bucket bucket element that we are on.
0233     //
0234     //  fCurHash
0235     //      The current hash buck that we are working on. Once we hit the
0236     //      end of the bucket that fCurElem is in, then we have to start
0237     //      working this one up to the next non-empty bucket.
0238     //
0239     //  fToEnum
0240     //      The value array being enumerated.
0241     // -----------------------------------------------------------------------
0242     bool                                  fAdopted;
0243     RefHashTableBucketElem<TVal>*         fCurElem;
0244     XMLSize_t                             fCurHash;
0245     RefHashTableOf<TVal, THasher>*        fToEnum;
0246     MemoryManager* const                  fMemoryManager;
0247 };
0248
0249 XERCES_CPP_NAMESPACE_END
0250
0251 #if !defined(XERCES_TMPLSINC)
0252 #include <xercesc/util/RefHashTableOf.c>
0253 #endif
0254
0255 #endif