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: NameIdPool.hpp,v $ 00059 * Revision 1.1 2002/05/11 20:55:39 bhavani 00060 * CR#CR062582# adding xercesc 1.7 file 00061 * 00062 * Revision 1.1.1.1 2002/02/01 22:22:11 peiyongz 00063 * sane_include 00064 * 00065 * Revision 1.6 2000/09/09 00:11:48 andyh 00066 * Virtual Destructor Patch, submitted by Kirk Wylie 00067 * 00068 * Revision 1.5 2000/07/19 18:47:26 andyh 00069 * More Macintosh port tweaks, submitted by James Berry. 00070 * 00071 * Revision 1.4 2000/03/02 19:54:42 roddey 00072 * This checkin includes many changes done while waiting for the 00073 * 1.1.0 code to be finished. I can't list them all here, but a list is 00074 * available elsewhere. 00075 * 00076 * Revision 1.3 2000/02/24 20:05:24 abagchi 00077 * Swat for removing Log from API docs 00078 * 00079 * Revision 1.2 2000/02/06 07:48:02 rahulj 00080 * Year 2K copyright swat. 00081 * 00082 * Revision 1.1.1.1 1999/11/09 01:04:48 twl 00083 * Initial checkin 00084 * 00085 * Revision 1.3 1999/11/08 20:45:10 rahul 00086 * Swat for adding in Product name and CVS comment log variable. 00087 * 00088 */ 00089 00090 00091 #if !defined(NAMEIDPOOL_HPP) 00092 #define NAMEIDPOOL_HPP 00093 00094 #include <xercesc/util/XercesDefs.hpp> 00095 #include <string.h> 00096 #include <xercesc/util/XMLEnumerator.hpp> 00097 #include <xercesc/util/XMLString.hpp> 00098 00099 00100 // 00101 // Forward declare the enumerator so he can be our friend. Can you say 00102 // friend? Sure... 00103 // 00104 template <class TElem> class NameIdPoolEnumerator; 00105 00106 00107 // 00108 // This class is provided to serve as the basis of many of the pools that 00109 // are used by the scanner and validators. They often need to be able to 00110 // store objects in such a way that they can be quickly accessed by the 00111 // name field of the object, and such that each element added is assigned 00112 // a unique id via which it can be accessed almost instantly. 00113 // 00114 // Object names are enforced as being unique, since that's what all these 00115 // pools require. So its effectively a hash table in conjunction with an 00116 // array of references into the hash table by id. Ids are assigned such that 00117 // id N can be used to get the Nth element from the array of references. 00118 // This provides very fast access by id. 00119 // 00120 // The way these pools are used, elements are never removed except when the 00121 // whole thing is flushed. This makes it very easy to maintain the two 00122 // access methods in sync. 00123 // 00124 // For efficiency reasons, the id refererence array is never flushed until 00125 // the dtor. This way, it does not have to be regrown every time its reused. 00126 // 00127 // All elements are assumed to be owned by the pool! 00128 // 00129 // We have to have a bucket element structure to use to maintain the linked 00130 // lists for each bucket. Because some of the compilers we have to support 00131 // are totally brain dead, it cannot be a nested class as it should be. 00132 // 00133 template <class TElem> struct NameIdPoolBucketElem 00134 { 00135 public : 00136 NameIdPoolBucketElem 00137 ( 00138 TElem* const value 00139 , NameIdPoolBucketElem<TElem>* const next 00140 ); 00141 ~NameIdPoolBucketElem(); 00142 00143 TElem* fData; 00144 NameIdPoolBucketElem<TElem>* fNext; 00145 }; 00146 00147 00148 template <class TElem> class NameIdPool 00149 { 00150 public : 00151 // ----------------------------------------------------------------------- 00152 // Contructors and Destructor 00153 // ----------------------------------------------------------------------- 00154 NameIdPool 00155 ( 00156 const unsigned int hashModulus 00157 , const unsigned int initSize = 128 00158 ); 00159 00160 ~NameIdPool(); 00161 00162 00163 // ----------------------------------------------------------------------- 00164 // Element management 00165 // ----------------------------------------------------------------------- 00166 bool containsKey(const XMLCh* const key) const; 00167 void removeAll(); 00168 00169 00170 // ----------------------------------------------------------------------- 00171 // Getters 00172 // ----------------------------------------------------------------------- 00173 TElem* getByKey(const XMLCh* const key); 00174 const TElem* getByKey(const XMLCh* const key) const; 00175 TElem* getById(const unsigned elemId); 00176 const TElem* getById(const unsigned elemId) const; 00177 00178 00179 // ----------------------------------------------------------------------- 00180 // Putters 00181 // 00182 // Dups are not allowed and cause an IllegalArgumentException. The id 00183 // of the new element is returned. 00184 // ----------------------------------------------------------------------- 00185 unsigned int put(TElem* const valueToAdopt); 00186 00187 00188 protected : 00189 // ----------------------------------------------------------------------- 00190 // Declare the enumerator our friend so he can see our members 00191 // ----------------------------------------------------------------------- 00192 friend class NameIdPoolEnumerator<TElem>; 00193 00194 00195 private : 00196 // ----------------------------------------------------------------------- 00197 // Unused constructors and operators 00198 // ----------------------------------------------------------------------- 00199 NameIdPool(const NameIdPool<TElem>&); 00200 void operator=(const NameIdPool<TElem>&); 00201 00202 00203 // ----------------------------------------------------------------------- 00204 // Private helper methods 00205 // ----------------------------------------------------------------------- 00206 NameIdPoolBucketElem<TElem>* findBucketElem 00207 ( 00208 const XMLCh* const key 00209 , unsigned int& hashVal 00210 ); 00211 const NameIdPoolBucketElem<TElem>* findBucketElem 00212 ( 00213 const XMLCh* const key 00214 , unsigned int& hashVal 00215 ) const; 00216 00217 00218 // ----------------------------------------------------------------------- 00219 // Data members 00220 // 00221 // fBucketList 00222 // This is the array that contains the heads of all of the list 00223 // buckets, one for each possible hash value. 00224 // 00225 // fIdPtrs 00226 // fIdPtrsCount 00227 // This is the array of pointers to the bucket elements in order of 00228 // their assigned ids. So taking id N and referencing this array 00229 // gives you the element with that id. The count field indicates 00230 // the current size of this list. When fIdCounter+1 reaches this 00231 // value the list must be expanded. 00232 // 00233 // fIdCounter 00234 // This is used to give out unique ids to added elements. It starts 00235 // at zero (which means empty), and is bumped up for each newly added 00236 // element. So the first element is 1, the next is 2, etc... This 00237 // means that this value is set to the top index of the fIdPtrs array. 00238 // 00239 // fHashModulus 00240 // This is the modulus to use in this pool. The fBucketList array 00241 // is of this size. It should be a prime number. 00242 // ----------------------------------------------------------------------- 00243 NameIdPoolBucketElem<TElem>** fBucketList; 00244 TElem** fIdPtrs; 00245 unsigned int fIdPtrsCount; 00246 unsigned int fIdCounter; 00247 unsigned int fHashModulus; 00248 }; 00249 00250 00251 // 00252 // An enumerator for a name id pool. It derives from the basic enumerator 00253 // class, so that pools can be generically enumerated. 00254 // 00255 template <class TElem> class NameIdPoolEnumerator : public XMLEnumerator<TElem> 00256 { 00257 public : 00258 // ----------------------------------------------------------------------- 00259 // Constructors and Destructor 00260 // ----------------------------------------------------------------------- 00261 NameIdPoolEnumerator 00262 ( 00263 NameIdPool<TElem>* const toEnum 00264 ); 00265 00266 NameIdPoolEnumerator 00267 ( 00268 const NameIdPoolEnumerator<TElem>& toCopy 00269 ); 00270 00271 virtual ~NameIdPoolEnumerator(); 00272 00273 // ----------------------------------------------------------------------- 00274 // Public operators 00275 // ----------------------------------------------------------------------- 00276 NameIdPoolEnumerator<TElem>& operator= 00277 ( 00278 const NameIdPoolEnumerator<TElem>& toAssign 00279 ); 00280 00281 00282 // ----------------------------------------------------------------------- 00283 // Enum interface 00284 // ----------------------------------------------------------------------- 00285 bool hasMoreElements() const; 00286 TElem& nextElement(); 00287 void Reset(); 00288 00289 00290 private : 00291 // ----------------------------------------------------------------------- 00292 // Data Members 00293 // 00294 // fCurIndex 00295 // This is the current index into the pool's id mapping array. This 00296 // is now we enumerate it. 00297 // 00298 // fToEnum 00299 // The name id pool that is being enumerated. 00300 // ----------------------------------------------------------------------- 00301 unsigned int fCurIndex; 00302 NameIdPool<TElem>* fToEnum; 00303 }; 00304 00305 00306 #if !defined(XERCES_TMPLSINC) 00307 #include <xercesc/util/NameIdPool.c> 00308 #endif 00309 00310 #endif