source: NonGTP/Xerces/xercesc/util/NameIdPool.hpp @ 188

Revision 188, 12.9 KB checked in by mattausch, 19 years ago (diff)

added xercesc to support

Line 
1/*
2 * The Apache Software License, Version 1.1
3 *
4 * Copyright (c) 1999-2000 The Apache Software Foundation.  All rights
5 * reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in
16 *    the documentation and/or other materials provided with the
17 *    distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 *    if any, must include the following acknowledgment:
21 *       "This product includes software developed by the
22 *        Apache Software Foundation (http://www.apache.org/)."
23 *    Alternately, this acknowledgment may appear in the software itself,
24 *    if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "Xerces" and "Apache Software Foundation" must
27 *    not be used to endorse or promote products derived from this
28 *    software without prior written permission. For written
29 *    permission, please contact apache\@apache.org.
30 *
31 * 5. Products derived from this software may not be called "Apache",
32 *    nor may "Apache" appear in their name, without prior written
33 *    permission of the Apache Software Foundation.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46 * SUCH DAMAGE.
47 * ====================================================================
48 *
49 * This software consists of voluntary contributions made by many
50 * individuals on behalf of the Apache Software Foundation, and was
51 * originally based on software copyright (c) 1999, International
52 * Business Machines, Inc., http://www.ibm.com .  For more information
53 * on the Apache Software Foundation, please see
54 * <http://www.apache.org/>.
55 */
56
57/*
58 * $Log: NameIdPool.hpp,v $
59 * Revision 1.9  2004/01/29 11:48:46  cargilld
60 * Code cleanup changes to get rid of various compiler diagnostic messages.
61 *
62 * Revision 1.8  2003/12/17 00:18:35  cargilld
63 * Update to memory management so that the static memory manager (one used to call Initialize) is only for static data.
64 *
65 * Revision 1.7  2003/10/29 16:17:48  peiyongz
66 * size() added
67 *
68 * Revision 1.6  2003/05/16 06:01:52  knoaman
69 * Partial implementation of the configurable memory manager.
70 *
71 * Revision 1.5  2003/05/15 19:04:35  knoaman
72 * Partial implementation of the configurable memory manager.
73 *
74 * Revision 1.4  2003/03/07 18:11:54  tng
75 * Return a reference instead of void for operator=
76 *
77 * Revision 1.3  2002/12/04 02:32:43  knoaman
78 * #include cleanup.
79 *
80 * Revision 1.2  2002/11/04 15:22:04  tng
81 * C++ Namespace Support.
82 *
83 * Revision 1.1.1.1  2002/02/01 22:22:11  peiyongz
84 * sane_include
85 *
86 * Revision 1.6  2000/09/09 00:11:48  andyh
87 * Virtual Destructor Patch, submitted by Kirk Wylie
88 *
89 * Revision 1.5  2000/07/19 18:47:26  andyh
90 * More Macintosh port tweaks, submitted by James Berry.
91 *
92 * Revision 1.4  2000/03/02 19:54:42  roddey
93 * This checkin includes many changes done while waiting for the
94 * 1.1.0 code to be finished. I can't list them all here, but a list is
95 * available elsewhere.
96 *
97 * Revision 1.3  2000/02/24 20:05:24  abagchi
98 * Swat for removing Log from API docs
99 *
100 * Revision 1.2  2000/02/06 07:48:02  rahulj
101 * Year 2K copyright swat.
102 *
103 * Revision 1.1.1.1  1999/11/09 01:04:48  twl
104 * Initial checkin
105 *
106 * Revision 1.3  1999/11/08 20:45:10  rahul
107 * Swat for adding in Product name and CVS comment log variable.
108 *
109 */
110
111
112#if !defined(NAMEIDPOOL_HPP)
113#define NAMEIDPOOL_HPP
114
115#include <xercesc/util/XMemory.hpp>
116#include <xercesc/util/XMLString.hpp>
117#include <xercesc/util/PlatformUtils.hpp>
118
119XERCES_CPP_NAMESPACE_BEGIN
120
121//
122//  Forward declare the enumerator so he can be our friend. Can you say
123//  friend? Sure...
124//
125template <class TElem> class NameIdPoolEnumerator;
126
127
128//
129//  This class is provided to serve as the basis of many of the pools that
130//  are used by the scanner and validators. They often need to be able to
131//  store objects in such a way that they can be quickly accessed by the
132//  name field of the object, and such that each element added is assigned
133//  a unique id via which it can be accessed almost instantly.
134//
135//  Object names are enforced as being unique, since that's what all these
136//  pools require. So its effectively a hash table in conjunction with an
137//  array of references into the hash table by id. Ids are assigned such that
138//  id N can be used to get the Nth element from the array of references.
139//  This provides very fast access by id.
140//
141//  The way these pools are used, elements are never removed except when the
142//  whole thing is flushed. This makes it very easy to maintain the two
143//  access methods in sync.
144//
145//  For efficiency reasons, the id refererence array is never flushed until
146//  the dtor. This way, it does not have to be regrown every time its reused.
147//
148//  All elements are assumed to be owned by the pool!
149//
150//  We have to have a bucket element structure to use to maintain the linked
151//  lists for each bucket. Because some of the compilers we have to support
152//  are totally brain dead, it cannot be a nested class as it should be.
153//
154template <class TElem> struct NameIdPoolBucketElem : public XMemory
155{
156public :
157    NameIdPoolBucketElem
158    (
159        TElem* const                            value
160        , NameIdPoolBucketElem<TElem>* const    next
161    );
162    ~NameIdPoolBucketElem();
163
164    TElem*                          fData;
165    NameIdPoolBucketElem<TElem>*    fNext;
166private:
167    // -----------------------------------------------------------------------
168    //  Unimplemented constructors and operators
169    // -----------------------------------------------------------------------
170    NameIdPoolBucketElem(const NameIdPoolBucketElem<TElem>&);
171    NameIdPoolBucketElem<TElem>& operator=(const NameIdPoolBucketElem<TElem>&);
172};
173
174
175template <class TElem> class NameIdPool : public XMemory
176{
177public :
178    // -----------------------------------------------------------------------
179    //  Contructors and Destructor
180    // -----------------------------------------------------------------------
181    NameIdPool
182    (
183        const   unsigned int    hashModulus
184        , const unsigned int    initSize = 128
185        , MemoryManager* const  manager = XMLPlatformUtils::fgMemoryManager
186    );
187
188    ~NameIdPool();
189
190
191    // -----------------------------------------------------------------------
192    //  Element management
193    // -----------------------------------------------------------------------
194    bool containsKey(const XMLCh* const key) const;
195    void removeAll();
196
197
198    // -----------------------------------------------------------------------
199    //  Getters
200    // -----------------------------------------------------------------------
201    TElem* getByKey(const XMLCh* const key);
202    const TElem* getByKey(const XMLCh* const key) const;
203    TElem* getById(const unsigned elemId);
204    const TElem* getById(const unsigned elemId) const;
205
206    MemoryManager* getMemoryManager() const;
207    // -----------------------------------------------------------------------
208    //  Putters
209    //
210    //  Dups are not allowed and cause an IllegalArgumentException. The id
211    //  of the new element is returned.
212    // -----------------------------------------------------------------------
213    unsigned int put(TElem* const valueToAdopt);
214
215
216protected :
217    // -----------------------------------------------------------------------
218    //  Declare the enumerator our friend so he can see our members
219    // -----------------------------------------------------------------------
220    friend class NameIdPoolEnumerator<TElem>;
221
222
223private :
224    // -----------------------------------------------------------------------
225    //  Unused constructors and operators
226    // -----------------------------------------------------------------------
227    NameIdPool(const NameIdPool<TElem>&);
228    NameIdPool<TElem>& operator=(const NameIdPool<TElem>&);
229
230
231    // -----------------------------------------------------------------------
232    //  Private helper methods
233    // -----------------------------------------------------------------------
234    NameIdPoolBucketElem<TElem>* findBucketElem
235    (
236        const XMLCh* const      key
237        ,     unsigned int&     hashVal
238    );
239    const NameIdPoolBucketElem<TElem>* findBucketElem
240    (
241        const   XMLCh* const    key
242        ,       unsigned int&   hashVal
243    )   const;
244
245
246    // -----------------------------------------------------------------------
247    //  Data members
248    //
249    //  fBucketList
250    //      This is the array that contains the heads of all of the list
251    //      buckets, one for each possible hash value.
252    //
253    //  fIdPtrs
254    //  fIdPtrsCount
255    //      This is the array of pointers to the bucket elements in order of
256    //      their assigned ids. So taking id N and referencing this array
257    //      gives you the element with that id. The count field indicates
258    //      the current size of this list. When fIdCounter+1 reaches this
259    //      value the list must be expanded.
260    //
261    //  fIdCounter
262    //      This is used to give out unique ids to added elements. It starts
263    //      at zero (which means empty), and is bumped up for each newly added
264    //      element. So the first element is 1, the next is 2, etc... This
265    //      means that this value is set to the top index of the fIdPtrs array.
266    //
267    //  fHashModulus
268    //      This is the modulus to use in this pool. The fBucketList array
269    //      is of this size. It should be a prime number.
270    // -----------------------------------------------------------------------
271    MemoryManager*                  fMemoryManager;
272    NameIdPoolBucketElem<TElem>**   fBucketList;
273    TElem**                         fIdPtrs;
274    unsigned int                    fIdPtrsCount;
275    unsigned int                    fIdCounter;
276    unsigned int                    fHashModulus;
277};
278
279
280//
281//  An enumerator for a name id pool. It derives from the basic enumerator
282//  class, so that pools can be generically enumerated.
283//
284template <class TElem> class NameIdPoolEnumerator : public XMLEnumerator<TElem>, public XMemory
285{
286public :
287    // -----------------------------------------------------------------------
288    //  Constructors and Destructor
289    // -----------------------------------------------------------------------
290    NameIdPoolEnumerator
291    (
292                NameIdPool<TElem>* const    toEnum
293                , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager
294    );
295
296    NameIdPoolEnumerator
297    (
298        const   NameIdPoolEnumerator<TElem>& toCopy
299    );
300
301    virtual ~NameIdPoolEnumerator();
302
303    // -----------------------------------------------------------------------
304    //  Public operators
305    // -----------------------------------------------------------------------
306    NameIdPoolEnumerator<TElem>& operator=
307    (
308        const   NameIdPoolEnumerator<TElem>& toAssign
309    );
310   
311    // -----------------------------------------------------------------------
312    //  Enum interface
313    // -----------------------------------------------------------------------
314    bool hasMoreElements() const;
315    TElem& nextElement();
316    void Reset();
317    int  size()  const;
318
319private :
320    // -----------------------------------------------------------------------
321    //  Data Members
322    //
323    //  fCurIndex
324    //      This is the current index into the pool's id mapping array. This
325    //      is now we enumerate it.
326    //
327    //  fToEnum
328    //      The name id pool that is being enumerated.
329    // -----------------------------------------------------------------------
330    unsigned int            fCurIndex;
331    NameIdPool<TElem>*      fToEnum;
332    MemoryManager* const    fMemoryManager;
333};
334
335XERCES_CPP_NAMESPACE_END
336
337#if !defined(XERCES_TMPLSINC)
338#include <xercesc/util/NameIdPool.c>
339#endif
340
341#endif
Note: See TracBrowser for help on using the repository browser.