00001 /* 00002 * The Apache Software License, Version 1.1 00003 * 00004 * Copyright (c) 1999-2000 The Apache Software Foundation. All rights 00005 * reserved. 00006 * 00007 * Redistribution and use in source and binary forms, with or without 00008 * modification, are permitted provided that the following conditions 00009 * are met: 00010 * 00011 * 1. Redistributions of source code must retain the above copyright 00012 * notice, this list of conditions and the following disclaimer. 00013 * 00014 * 2. Redistributions in binary form must reproduce the above copyright 00015 * notice, this list of conditions and the following disclaimer in 00016 * the documentation and/or other materials provided with the 00017 * distribution. 00018 * 00019 * 3. The end-user documentation included with the redistribution, 00020 * if any, must include the following acknowledgment: 00021 * "This product includes software developed by the 00022 * Apache Software Foundation (http://www.apache.org/)." 00023 * Alternately, this acknowledgment may appear in the software itself, 00024 * if and wherever such third-party acknowledgments normally appear. 00025 * 00026 * 4. The names "Xerces" and "Apache Software Foundation" must 00027 * not be used to endorse or promote products derived from this 00028 * software without prior written permission. For written 00029 * permission, please contact apache\@apache.org. 00030 * 00031 * 5. Products derived from this software may not be called "Apache", 00032 * nor may "Apache" appear in their name, without prior written 00033 * permission of the Apache Software Foundation. 00034 * 00035 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 00036 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00037 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 00038 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR 00039 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00040 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00041 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 00042 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 00043 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 00044 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 00045 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00046 * SUCH DAMAGE. 00047 * ==================================================================== 00048 * 00049 * This software consists of voluntary contributions made by many 00050 * individuals on behalf of the Apache Software Foundation, and was 00051 * originally based on software copyright (c) 1999, International 00052 * Business Machines, Inc., http://www.ibm.com . For more information 00053 * on the Apache Software Foundation, please see 00054 * <http://www.apache.org/>. 00055 */ 00056 00057 /* 00058 * $Log: RefHashTableOf.hpp,v $ 00059 * Revision 1.1 2002/05/11 21:09:17 bhavani 00060 * CR#CR062582# adding xercesc 1.7 file 00061 * 00062 * Revision 1.1.1.1 2002/02/01 22:22:12 peiyongz 00063 * sane_include 00064 * 00065 * Revision 1.9 2001/06/04 13:45:04 tng 00066 * The "hash" argument clashes with STL hash. Fixed by Pei Yong Zhang. 00067 * 00068 * Revision 1.8 2000/07/07 22:16:51 jpolast 00069 * remove old put(value) function. use put(key,value) instead. 00070 * 00071 * Revision 1.7 2000/06/29 18:27:09 jpolast 00072 * bug fix for passing hasher class references to constructor 00073 * 00074 * Revision 1.6 2000/06/27 22:11:12 jpolast 00075 * added more general functionality to hashtables. 00076 * able to specify which hasher to use. 00077 * default: HashXMLCh [hashes XMLCh* strings] 00078 * 00079 * future todo: make hasher class references static so only 00080 * one instance of a hasher is ever created. 00081 * 00082 * Revision 1.5 2000/03/02 19:54:44 roddey 00083 * This checkin includes many changes done while waiting for the 00084 * 1.1.0 code to be finished. I can't list them all here, but a list is 00085 * available elsewhere. 00086 * 00087 * Revision 1.4 2000/02/24 20:05:25 abagchi 00088 * Swat for removing Log from API docs 00089 * 00090 * Revision 1.3 2000/02/06 07:48:03 rahulj 00091 * Year 2K copyright swat. 00092 * 00093 * Revision 1.2 1999/12/18 00:18:10 roddey 00094 * More changes to support the new, completely orthagonal support for 00095 * intrinsic encodings. 00096 * 00097 * Revision 1.1.1.1 1999/11/09 01:05:01 twl 00098 * Initial checkin 00099 * 00100 * Revision 1.2 1999/11/08 20:45:12 rahul 00101 * Swat for adding in Product name and CVS comment log variable. 00102 * 00103 */ 00104 00105 00106 #if !defined(REFHASHTABLEOF_HPP) 00107 #define REFHASHTABLEOF_HPP 00108 00109 00110 #include <xercesc/util/XercesDefs.hpp> 00111 #include <xercesc/util/KeyValuePair.hpp> 00112 #include <xercesc/util/HashBase.hpp> 00113 #include <xercesc/util/IllegalArgumentException.hpp> 00114 #include <xercesc/util/NoSuchElementException.hpp> 00115 #include <xercesc/util/RuntimeException.hpp> 00116 #include <xercesc/util/XMLExceptMsgs.hpp> 00117 #include <xercesc/util/XMLEnumerator.hpp> 00118 #include <xercesc/util/XMLString.hpp> 00119 #include <xercesc/util/HashBase.hpp> 00120 #include <xercesc/util/HashXMLCh.hpp> 00121 00122 00123 // 00124 // Forward declare the enumerator so he can be our friend. Can you say 00125 // friend? Sure... 00126 // 00127 template <class TVal> class RefHashTableOfEnumerator; 00128 template <class TVal> struct RefHashTableBucketElem; 00129 00130 00131 // 00132 // This should really be a nested class, but some of the compilers we 00133 // have to support cannot deal with that! 00134 // 00135 template <class TVal> struct RefHashTableBucketElem 00136 { 00137 RefHashTableBucketElem(void* key, TVal* const value, RefHashTableBucketElem<TVal>* next) 00138 : fData(value), fNext(next), fKey(key) 00139 { 00140 } 00141 00142 TVal* fData; 00143 RefHashTableBucketElem<TVal>* fNext; 00144 void* fKey; 00145 }; 00146 00147 00148 template <class TVal> class RefHashTableOf 00149 { 00150 public: 00151 // ----------------------------------------------------------------------- 00152 // Constructors and Destructor 00153 // ----------------------------------------------------------------------- 00154 // backwards compatability - default hasher is HashXMLCh 00155 RefHashTableOf(const unsigned int modulus); 00156 // backwards compatability - default hasher is HashXMLCh 00157 RefHashTableOf(const unsigned int modulus, const bool adoptElems); 00158 // if a hash function is passed in, it will be deleted when the hashtable is deleted. 00159 // use a new instance of the hasher class for each hashtable, otherwise one hashtable 00160 // may delete the hasher of a different hashtable if both use the same hasher. 00161 RefHashTableOf(const unsigned int modulus, const bool adoptElems, HashBase* hashBase); 00162 ~RefHashTableOf(); 00163 00164 00165 // ----------------------------------------------------------------------- 00166 // Element management 00167 // ----------------------------------------------------------------------- 00168 bool isEmpty() const; 00169 bool containsKey(const void* const key) const; 00170 void removeKey(const void* const key); 00171 void removeAll(); 00172 00173 00174 // ----------------------------------------------------------------------- 00175 // Getters 00176 // ----------------------------------------------------------------------- 00177 TVal* get(const void* const key); 00178 const TVal* get(const void* const key) const; 00179 00180 00181 // ----------------------------------------------------------------------- 00182 // Putters 00183 // ----------------------------------------------------------------------- 00184 void put(void* key, TVal* const valueToAdopt); 00185 00186 00187 private : 00188 // ----------------------------------------------------------------------- 00189 // Declare our friends 00190 // ----------------------------------------------------------------------- 00191 friend class RefHashTableOfEnumerator<TVal>; 00192 00193 private: 00194 00195 // ----------------------------------------------------------------------- 00196 // Private methods 00197 // ----------------------------------------------------------------------- 00198 RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal); 00199 const RefHashTableBucketElem<TVal>* findBucketElem(const void* const key, unsigned int& hashVal) const; 00200 void removeBucketElem(const void* const key, unsigned int& hashVal); 00201 void initialize(const unsigned int modulus); 00202 00203 00204 // ----------------------------------------------------------------------- 00205 // Data members 00206 // 00207 // fAdoptedElems 00208 // Indicates whether the values added are adopted or just referenced. 00209 // If adopted, then they are deleted when they are removed from the 00210 // hash table. 00211 // 00212 // fBucketList 00213 // This is the array that contains the heads of all of the list 00214 // buckets, one for each possible hash value. 00215 // 00216 // fHashModulus 00217 // The modulus used for this hash table, to hash the keys. This is 00218 // also the number of elements in the bucket list. 00219 // 00220 // fHash 00221 // The hasher for the key data type. 00222 // ----------------------------------------------------------------------- 00223 bool fAdoptedElems; 00224 RefHashTableBucketElem<TVal>** fBucketList; 00225 unsigned int fHashModulus; 00226 HashBase* fHash; 00227 }; 00228 00229 00230 00231 // 00232 // An enumerator for a value array. It derives from the basic enumerator 00233 // class, so that value vectors can be generically enumerated. 00234 // 00235 template <class TVal> class RefHashTableOfEnumerator : public XMLEnumerator<TVal> 00236 { 00237 public : 00238 // ----------------------------------------------------------------------- 00239 // Constructors and Destructor 00240 // ----------------------------------------------------------------------- 00241 RefHashTableOfEnumerator(RefHashTableOf<TVal>* const toEnum, const bool adopt = false); 00242 ~RefHashTableOfEnumerator(); 00243 00244 00245 // ----------------------------------------------------------------------- 00246 // Enum interface 00247 // ----------------------------------------------------------------------- 00248 bool hasMoreElements() const; 00249 TVal& nextElement(); 00250 void Reset(); 00251 00252 00253 private : 00254 // ----------------------------------------------------------------------- 00255 // Private methods 00256 // ----------------------------------------------------------------------- 00257 void findNext(); 00258 00259 00260 // ----------------------------------------------------------------------- 00261 // Data Members 00262 // 00263 // fAdopted 00264 // Indicates whether we have adopted the passed vector. If so then 00265 // we delete the vector when we are destroyed. 00266 // 00267 // fCurElem 00268 // This is the current bucket bucket element that we are on. 00269 // 00270 // fCurHash 00271 // The is the current hash buck that we are working on. Once we hit 00272 // the end of the bucket that fCurElem is in, then we have to start 00273 // working this one up to the next non-empty bucket. 00274 // 00275 // fToEnum 00276 // The value array being enumerated. 00277 // ----------------------------------------------------------------------- 00278 bool fAdopted; 00279 RefHashTableBucketElem<TVal>* fCurElem; 00280 unsigned int fCurHash; 00281 RefHashTableOf<TVal>* fToEnum; 00282 }; 00283 00284 #if !defined(XERCES_TMPLSINC) 00285 #include <xercesc/util/RefHashTableOf.c> 00286 #endif 00287 00288 #endif