|
1 /* |
|
2 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 /* |
|
18 * Licensed to the Apache Software Foundation (ASF) under one or more |
|
19 * contributor license agreements. See the NOTICE file distributed with |
|
20 * this work for additional information regarding copyright ownership. |
|
21 * The ASF licenses this file to You under the Apache License, Version 2.0 |
|
22 * (the "License"); you may not use this file except in compliance with |
|
23 * the License. You may obtain a copy of the License at |
|
24 * |
|
25 * http://www.apache.org/licenses/LICENSE-2.0 |
|
26 * |
|
27 * Unless required by applicable law or agreed to in writing, software |
|
28 * distributed under the License is distributed on an "AS IS" BASIS, |
|
29 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
30 * See the License for the specific language governing permissions and |
|
31 * limitations under the License. |
|
32 */ |
|
33 |
|
34 /* |
|
35 * $Id: NameIdPool.hpp 568078 2007-08-21 11:43:25Z amassari $ |
|
36 */ |
|
37 |
|
38 |
|
39 #if !defined(NAMEIDPOOL_HPP) |
|
40 #define NAMEIDPOOL_HPP |
|
41 |
|
42 #include <xercesc/util/XMemory.hpp> |
|
43 #include <xercesc/util/XMLString.hpp> |
|
44 #include <xercesc/util/PlatformUtils.hpp> |
|
45 |
|
46 XERCES_CPP_NAMESPACE_BEGIN |
|
47 |
|
48 // |
|
49 // Forward declare the enumerator so he can be our friend. Can you say |
|
50 // friend? Sure... |
|
51 // |
|
52 template <class TElem> class NameIdPoolEnumerator; |
|
53 |
|
54 |
|
55 // |
|
56 // This class is provided to serve as the basis of many of the pools that |
|
57 // are used by the scanner and validators. They often need to be able to |
|
58 // store objects in such a way that they can be quickly accessed by the |
|
59 // name field of the object, and such that each element added is assigned |
|
60 // a unique id via which it can be accessed almost instantly. |
|
61 // |
|
62 // Object names are enforced as being unique, since that's what all these |
|
63 // pools require. So its effectively a hash table in conjunction with an |
|
64 // array of references into the hash table by id. Ids are assigned such that |
|
65 // id N can be used to get the Nth element from the array of references. |
|
66 // This provides very fast access by id. |
|
67 // |
|
68 // The way these pools are used, elements are never removed except when the |
|
69 // whole thing is flushed. This makes it very easy to maintain the two |
|
70 // access methods in sync. |
|
71 // |
|
72 // For efficiency reasons, the id refererence array is never flushed until |
|
73 // the dtor. This way, it does not have to be regrown every time its reused. |
|
74 // |
|
75 // All elements are assumed to be owned by the pool! |
|
76 // |
|
77 // We have to have a bucket element structure to use to maintain the linked |
|
78 // lists for each bucket. Because some of the compilers we have to support |
|
79 // are totally brain dead, it cannot be a nested class as it should be. |
|
80 // |
|
81 template <class TElem> struct NameIdPoolBucketElem |
|
82 { |
|
83 public : |
|
84 NameIdPoolBucketElem |
|
85 ( |
|
86 TElem* const value |
|
87 , NameIdPoolBucketElem<TElem>* const next |
|
88 ); |
|
89 ~NameIdPoolBucketElem(); |
|
90 |
|
91 TElem* fData; |
|
92 NameIdPoolBucketElem<TElem>* fNext; |
|
93 private: |
|
94 // ----------------------------------------------------------------------- |
|
95 // Unimplemented constructors and operators |
|
96 // ----------------------------------------------------------------------- |
|
97 NameIdPoolBucketElem(const NameIdPoolBucketElem<TElem>&); |
|
98 NameIdPoolBucketElem<TElem>& operator=(const NameIdPoolBucketElem<TElem>&); |
|
99 }; |
|
100 |
|
101 |
|
102 template <class TElem> class NameIdPool : public XMemory |
|
103 { |
|
104 public : |
|
105 // ----------------------------------------------------------------------- |
|
106 // Contructors and Destructor |
|
107 // ----------------------------------------------------------------------- |
|
108 NameIdPool |
|
109 ( |
|
110 const unsigned int hashModulus |
|
111 , const unsigned int initSize = 128 |
|
112 , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager |
|
113 ); |
|
114 |
|
115 ~NameIdPool(); |
|
116 |
|
117 |
|
118 // ----------------------------------------------------------------------- |
|
119 // Element management |
|
120 // ----------------------------------------------------------------------- |
|
121 bool containsKey(const XMLCh* const key) const; |
|
122 void removeAll(); |
|
123 |
|
124 |
|
125 // ----------------------------------------------------------------------- |
|
126 // Getters |
|
127 // ----------------------------------------------------------------------- |
|
128 TElem* getByKey(const XMLCh* const key); |
|
129 const TElem* getByKey(const XMLCh* const key) const; |
|
130 TElem* getById(const unsigned elemId); |
|
131 const TElem* getById(const unsigned elemId) const; |
|
132 |
|
133 MemoryManager* getMemoryManager() const; |
|
134 // ----------------------------------------------------------------------- |
|
135 // Putters |
|
136 // |
|
137 // Dups are not allowed and cause an IllegalArgumentException. The id |
|
138 // of the new element is returned. |
|
139 // ----------------------------------------------------------------------- |
|
140 unsigned int put(TElem* const valueToAdopt); |
|
141 |
|
142 |
|
143 protected : |
|
144 // ----------------------------------------------------------------------- |
|
145 // Declare the enumerator our friend so he can see our members |
|
146 // ----------------------------------------------------------------------- |
|
147 friend class NameIdPoolEnumerator<TElem>; |
|
148 |
|
149 |
|
150 private : |
|
151 // ----------------------------------------------------------------------- |
|
152 // Unused constructors and operators |
|
153 // ----------------------------------------------------------------------- |
|
154 NameIdPool(const NameIdPool<TElem>&); |
|
155 NameIdPool<TElem>& operator=(const NameIdPool<TElem>&); |
|
156 |
|
157 |
|
158 // ----------------------------------------------------------------------- |
|
159 // Private helper methods |
|
160 // ----------------------------------------------------------------------- |
|
161 NameIdPoolBucketElem<TElem>* findBucketElem |
|
162 ( |
|
163 const XMLCh* const key |
|
164 , unsigned int& hashVal |
|
165 ); |
|
166 const NameIdPoolBucketElem<TElem>* findBucketElem |
|
167 ( |
|
168 const XMLCh* const key |
|
169 , unsigned int& hashVal |
|
170 ) const; |
|
171 |
|
172 |
|
173 // ----------------------------------------------------------------------- |
|
174 // Data members |
|
175 // |
|
176 // fBucketList |
|
177 // This is the array that contains the heads of all of the list |
|
178 // buckets, one for each possible hash value. |
|
179 // |
|
180 // fIdPtrs |
|
181 // fIdPtrsCount |
|
182 // This is the array of pointers to the bucket elements in order of |
|
183 // their assigned ids. So taking id N and referencing this array |
|
184 // gives you the element with that id. The count field indicates |
|
185 // the current size of this list. When fIdCounter+1 reaches this |
|
186 // value the list must be expanded. |
|
187 // |
|
188 // fIdCounter |
|
189 // This is used to give out unique ids to added elements. It starts |
|
190 // at zero (which means empty), and is bumped up for each newly added |
|
191 // element. So the first element is 1, the next is 2, etc... This |
|
192 // means that this value is set to the top index of the fIdPtrs array. |
|
193 // |
|
194 // fHashModulus |
|
195 // This is the modulus to use in this pool. The fBucketList array |
|
196 // is of this size. It should be a prime number. |
|
197 // ----------------------------------------------------------------------- |
|
198 MemoryManager* fMemoryManager; |
|
199 NameIdPoolBucketElem<TElem>** fBucketList; |
|
200 TElem** fIdPtrs; |
|
201 unsigned int fIdPtrsCount; |
|
202 unsigned int fIdCounter; |
|
203 unsigned int fHashModulus; |
|
204 }; |
|
205 |
|
206 |
|
207 // |
|
208 // An enumerator for a name id pool. It derives from the basic enumerator |
|
209 // class, so that pools can be generically enumerated. |
|
210 // |
|
211 template <class TElem> class NameIdPoolEnumerator : public XMLEnumerator<TElem>, public XMemory |
|
212 { |
|
213 public : |
|
214 // ----------------------------------------------------------------------- |
|
215 // Constructors and Destructor |
|
216 // ----------------------------------------------------------------------- |
|
217 NameIdPoolEnumerator |
|
218 ( |
|
219 NameIdPool<TElem>* const toEnum |
|
220 , MemoryManager* const manager = XMLPlatformUtils::fgMemoryManager |
|
221 ); |
|
222 |
|
223 NameIdPoolEnumerator |
|
224 ( |
|
225 const NameIdPoolEnumerator<TElem>& toCopy |
|
226 ); |
|
227 |
|
228 virtual ~NameIdPoolEnumerator(); |
|
229 |
|
230 // ----------------------------------------------------------------------- |
|
231 // Public operators |
|
232 // ----------------------------------------------------------------------- |
|
233 NameIdPoolEnumerator<TElem>& operator= |
|
234 ( |
|
235 const NameIdPoolEnumerator<TElem>& toAssign |
|
236 ); |
|
237 |
|
238 // ----------------------------------------------------------------------- |
|
239 // Enum interface |
|
240 // ----------------------------------------------------------------------- |
|
241 bool hasMoreElements() const; |
|
242 TElem& nextElement(); |
|
243 void Reset(); |
|
244 int size() const; |
|
245 |
|
246 private : |
|
247 // ----------------------------------------------------------------------- |
|
248 // Data Members |
|
249 // |
|
250 // fCurIndex |
|
251 // This is the current index into the pool's id mapping array. This |
|
252 // is now we enumerate it. |
|
253 // |
|
254 // fToEnum |
|
255 // The name id pool that is being enumerated. |
|
256 // ----------------------------------------------------------------------- |
|
257 unsigned int fCurIndex; |
|
258 NameIdPool<TElem>* fToEnum; |
|
259 MemoryManager* fMemoryManager; |
|
260 }; |
|
261 |
|
262 XERCES_CPP_NAMESPACE_END |
|
263 |
|
264 #if !defined(XERCES_TMPLSINC) |
|
265 #include <xercesc/util/NameIdPool.c> |
|
266 #endif |
|
267 |
|
268 #endif |