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