|
0
|
1 |
// Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies).
|
|
|
2 |
// All rights reserved.
|
|
|
3 |
// This component and the accompanying materials are made available
|
|
|
4 |
// under the terms of the License "Eclipse Public License v1.0"
|
|
|
5 |
// which accompanies this distribution, and is available
|
|
|
6 |
// at the URL "http://www.eclipse.org/legal/epl-v10.html".
|
|
|
7 |
//
|
|
|
8 |
// Initial Contributors:
|
|
|
9 |
// Nokia Corporation - initial contribution.
|
|
|
10 |
//
|
|
|
11 |
// Contributors:
|
|
|
12 |
//
|
|
|
13 |
// Description:
|
|
|
14 |
// e32/include/e32hashtab.h
|
|
|
15 |
//
|
|
|
16 |
//
|
|
|
17 |
|
|
|
18 |
#ifndef __E32HASHTAB_H__
|
|
|
19 |
#define __E32HASHTAB_H__
|
|
|
20 |
#include <e32cmn.h>
|
|
|
21 |
|
|
|
22 |
/**
|
|
|
23 |
@publishedAll
|
|
|
24 |
@released
|
|
|
25 |
|
|
|
26 |
Defines a function type used by a THashFunction32 object.
|
|
|
27 |
|
|
|
28 |
A function of this type implements an algorithm for producing a 32 bit hash
|
|
|
29 |
value from a key.
|
|
|
30 |
|
|
|
31 |
@see THashFunction32
|
|
|
32 |
*/
|
|
|
33 |
typedef TUint32 (*TGeneralHashFunction32)(const TAny*);
|
|
|
34 |
|
|
|
35 |
|
|
|
36 |
/**
|
|
|
37 |
@publishedAll
|
|
|
38 |
@released
|
|
|
39 |
|
|
|
40 |
A templated class which packages a function that calculates a 32 bit hash
|
|
|
41 |
value from a key of templated type.
|
|
|
42 |
|
|
|
43 |
A THashFunction32<T> object is constructed and passed as a parameter to
|
|
|
44 |
member functions of the hash table classes RHashSet<T>, RPtrHashSet<T>,
|
|
|
45 |
RHashMap<T,V> and RPtrHashMap<T,V>.
|
|
|
46 |
|
|
|
47 |
@see RHashSet
|
|
|
48 |
@see RPtrHashSet
|
|
|
49 |
@see RHashMap
|
|
|
50 |
@see RPtrHashMap
|
|
|
51 |
*/
|
|
|
52 |
template <class T>
|
|
|
53 |
class THashFunction32
|
|
|
54 |
{
|
|
|
55 |
public:
|
|
|
56 |
inline THashFunction32( TUint32 (*aHashFunc)(const T&) )
|
|
|
57 |
{ iHashFunction = (TGeneralHashFunction32)aHashFunc; }
|
|
|
58 |
inline operator TGeneralHashFunction32() const
|
|
|
59 |
{ return iHashFunction; }
|
|
|
60 |
inline TUint32 Hash(const T& aKey) const
|
|
|
61 |
{ return (*iHashFunction)(&aKey); }
|
|
|
62 |
private:
|
|
|
63 |
TGeneralHashFunction32 iHashFunction;
|
|
|
64 |
};
|
|
|
65 |
|
|
|
66 |
|
|
|
67 |
/**
|
|
|
68 |
@publishedAll
|
|
|
69 |
@released
|
|
|
70 |
|
|
|
71 |
A set of common hashing functions for frequently occurring types.
|
|
|
72 |
|
|
|
73 |
@see RHashSet
|
|
|
74 |
@see RPtrHashSet
|
|
|
75 |
@see RHashMap
|
|
|
76 |
@see RPtrHashMap
|
|
|
77 |
*/
|
|
|
78 |
class DefaultHash
|
|
|
79 |
{
|
|
|
80 |
public:
|
|
|
81 |
IMPORT_C static TUint32 Integer(const TInt&);
|
|
|
82 |
IMPORT_C static TUint32 Des8(const TDesC8&);
|
|
|
83 |
IMPORT_C static TUint32 Des16(const TDesC16&);
|
|
|
84 |
IMPORT_C static TUint32 IntegerPtr(TInt* const &);
|
|
|
85 |
IMPORT_C static TUint32 Des8Ptr(TDesC8* const &);
|
|
|
86 |
IMPORT_C static TUint32 Des16Ptr(TDesC16* const &);
|
|
|
87 |
};
|
|
|
88 |
|
|
|
89 |
|
|
|
90 |
|
|
|
91 |
class THashTableIterBase;
|
|
|
92 |
|
|
|
93 |
/**
|
|
|
94 |
@internalComponent
|
|
|
95 |
|
|
|
96 |
Base class used in the derivation of RHashSet<T>, RPtrHashSet<T>,
|
|
|
97 |
RHashMap<K,V> and RPtrHashMap<K,V>.
|
|
|
98 |
|
|
|
99 |
This class provides a general hash table implementation using probe sequences
|
|
|
100 |
generated by pseudo-double hashing.
|
|
|
101 |
The class is internal and is not intended for use.
|
|
|
102 |
*/
|
|
|
103 |
class RHashTableBase
|
|
|
104 |
{
|
|
|
105 |
public:
|
|
|
106 |
enum TDefaultSpecifier
|
|
|
107 |
{
|
|
|
108 |
EDefaultSpecifier_Normal,
|
|
|
109 |
};
|
|
|
110 |
|
|
|
111 |
protected:
|
|
|
112 |
template<class K, TDefaultSpecifier S>
|
|
|
113 |
class Defaults
|
|
|
114 |
{
|
|
|
115 |
public:
|
|
|
116 |
inline static TGeneralHashFunction32 Hash();
|
|
|
117 |
inline static TGeneralIdentityRelation Id();
|
|
|
118 |
};
|
|
|
119 |
|
|
|
120 |
protected:
|
|
|
121 |
enum TElementState
|
|
|
122 |
{
|
|
|
123 |
EEmpty=0, // entry is vacant
|
|
|
124 |
EDeleted=1, // entry has been deleted
|
|
|
125 |
EGen0=2, // entry is occupied, generation number 0
|
|
|
126 |
EGen1=3, // entry is occupied, generation number 1
|
|
|
127 |
EStateMask=3,
|
|
|
128 |
EOccupiedMask=2,
|
|
|
129 |
};
|
|
|
130 |
|
|
|
131 |
struct SElement
|
|
|
132 |
{
|
|
|
133 |
inline void SetEmpty() {iHash=EEmpty;}
|
|
|
134 |
inline void SetDeleted() {iHash=EDeleted;}
|
|
|
135 |
inline TBool IsEmpty() const {return (iHash&EStateMask)==EEmpty;}
|
|
|
136 |
inline TBool IsDeleted() const {return (iHash&EStateMask)==EDeleted;}
|
|
|
137 |
inline TBool IsEmptyOrDeleted() const {return !(iHash&EOccupiedMask);}
|
|
|
138 |
|
|
|
139 |
TUint32 iHash; // bits 2-31 = 30 bit hash value, bits 0,1 = state
|
|
|
140 |
};
|
|
|
141 |
|
|
|
142 |
protected:
|
|
|
143 |
IMPORT_C RHashTableBase(TGeneralHashFunction32, TGeneralIdentityRelation, TInt aElementSize, TInt aKeyOffset);
|
|
|
144 |
IMPORT_C void Close();
|
|
|
145 |
IMPORT_C TAny* Find(const TAny* aKey, TInt aOffset=0) const;
|
|
|
146 |
IMPORT_C TAny* FindL(const TAny* aKey, TInt aOffset=0) const;
|
|
|
147 |
TInt Insert(const TAny* aKey, TAny*& aElement);
|
|
|
148 |
IMPORT_C TInt PtrInsert(const TAny* aKey, const TAny* aValue);
|
|
|
149 |
IMPORT_C void PtrInsertL(const TAny* aKey, const TAny* aValue);
|
|
|
150 |
IMPORT_C TInt ValueInsert(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize);
|
|
|
151 |
IMPORT_C void ValueInsertL(const TAny* aKey, TInt aKeySize, const TAny* aValue, TInt aValueOffset, TInt aValueSize);
|
|
|
152 |
IMPORT_C TInt Remove(const TAny* aKey);
|
|
|
153 |
IMPORT_C TInt Count() const;
|
|
|
154 |
IMPORT_C TInt Reserve(TInt aCount);
|
|
|
155 |
IMPORT_C void ReserveL(TInt aCount);
|
|
|
156 |
IMPORT_C void ConsistencyCheck(TUint32* aDeleted=0, TUint32* aComparisons=0, TUint32 aChainLimit=0, TUint32* aChainInfo=0);
|
|
|
157 |
private:
|
|
|
158 |
void SetThresholds();
|
|
|
159 |
TInt ExpandTable(TInt aNewIndexBits);
|
|
|
160 |
void ShrinkTable();
|
|
|
161 |
void ReformTable(TUint aNewIndexBits);
|
|
|
162 |
void VerifyReform();
|
|
|
163 |
private:
|
|
|
164 |
inline SElement* Element(TInt aIndex)
|
|
|
165 |
{return (SElement*)(((TUint8*)iElements) + aIndex*iElementSize);}
|
|
|
166 |
inline const SElement* ElementC(TInt aIndex) const
|
|
|
167 |
{return (const SElement*)(((TUint8*)iElements) + aIndex*iElementSize);}
|
|
|
168 |
inline TAny* GetKey(const SElement* aElement) const
|
|
|
169 |
{return iKeyOffset ? ((TUint8*)aElement + iKeyOffset) : (TAny*)((TUint32*)aElement)[1];}
|
|
|
170 |
private:
|
|
|
171 |
TGeneralHashFunction32 iHashFunc; // generates the hash from a given key
|
|
|
172 |
TGeneralIdentityRelation iIdFunc; // compare two keys for equality
|
|
|
173 |
TUint8 iIndexBits; // number of bits used to index the table
|
|
|
174 |
TUint8 iGeneration; // 2 or 3, generation number used when traversing entire table
|
|
|
175 |
TUint8 iKeyOffset; // offset to key
|
|
|
176 |
TUint8 iPad0;
|
|
|
177 |
TAny* iElements;
|
|
|
178 |
TUint32 iCount; // number of valid entries
|
|
|
179 |
TUint32 iEmptyCount; // number of empty entries
|
|
|
180 |
TUint32 iLowerThreshold; // shrink if count drops below this
|
|
|
181 |
TUint32 iUpperThreshold; // expand if count rises above this
|
|
|
182 |
TUint32 iCleanThreshold; // clean table if count of empty entries falls below this
|
|
|
183 |
TInt iElementSize;
|
|
|
184 |
TInt iPad1; // expansion room
|
|
|
185 |
TInt iPad2;
|
|
|
186 |
|
|
|
187 |
friend struct RHashTableBase::SElement;
|
|
|
188 |
friend class THashTableIterBase;
|
|
|
189 |
friend class HashTest;
|
|
|
190 |
};
|
|
|
191 |
|
|
|
192 |
|
|
|
193 |
/**
|
|
|
194 |
@internalComponent
|
|
|
195 |
*/
|
|
|
196 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt*, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
197 |
{
|
|
|
198 |
public:
|
|
|
199 |
inline static TGeneralHashFunction32 Hash();
|
|
|
200 |
inline static TGeneralIdentityRelation Id();
|
|
|
201 |
};
|
|
|
202 |
|
|
|
203 |
/**
|
|
|
204 |
@internalComponent
|
|
|
205 |
*/
|
|
|
206 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
207 |
{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}
|
|
|
208 |
|
|
|
209 |
/**
|
|
|
210 |
@internalComponent
|
|
|
211 |
*/
|
|
|
212 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt*, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
213 |
{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}
|
|
|
214 |
|
|
|
215 |
/**
|
|
|
216 |
@internalComponent
|
|
|
217 |
*/
|
|
|
218 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt32*, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
219 |
{
|
|
|
220 |
public:
|
|
|
221 |
inline static TGeneralHashFunction32 Hash();
|
|
|
222 |
inline static TGeneralIdentityRelation Id();
|
|
|
223 |
};
|
|
|
224 |
|
|
|
225 |
/**
|
|
|
226 |
@internalComponent
|
|
|
227 |
*/
|
|
|
228 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt32*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
229 |
{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}
|
|
|
230 |
|
|
|
231 |
/**
|
|
|
232 |
@internalComponent
|
|
|
233 |
*/
|
|
|
234 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt32*, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
235 |
{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}
|
|
|
236 |
|
|
|
237 |
/**
|
|
|
238 |
@internalComponent
|
|
|
239 |
*/
|
|
|
240 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint*, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
241 |
{
|
|
|
242 |
public:
|
|
|
243 |
inline static TGeneralHashFunction32 Hash();
|
|
|
244 |
inline static TGeneralIdentityRelation Id();
|
|
|
245 |
};
|
|
|
246 |
/**
|
|
|
247 |
@internalComponent
|
|
|
248 |
*/
|
|
|
249 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
250 |
{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}
|
|
|
251 |
|
|
|
252 |
/**
|
|
|
253 |
@internalComponent
|
|
|
254 |
*/
|
|
|
255 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint*, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
256 |
{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}
|
|
|
257 |
|
|
|
258 |
|
|
|
259 |
/**
|
|
|
260 |
@internalComponent
|
|
|
261 |
*/
|
|
|
262 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint32*, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
263 |
{
|
|
|
264 |
public:
|
|
|
265 |
inline static TGeneralHashFunction32 Hash();
|
|
|
266 |
inline static TGeneralIdentityRelation Id();
|
|
|
267 |
};
|
|
|
268 |
/**
|
|
|
269 |
@internalComponent
|
|
|
270 |
*/
|
|
|
271 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint32*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
272 |
{return (TGeneralHashFunction32)&DefaultHash::IntegerPtr;}
|
|
|
273 |
|
|
|
274 |
/**
|
|
|
275 |
@internalComponent
|
|
|
276 |
*/
|
|
|
277 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint32*, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
278 |
{return (TGeneralIdentityRelation)&DefaultIdentity::IntegerPtr;}
|
|
|
279 |
|
|
|
280 |
/**
|
|
|
281 |
@internalComponent
|
|
|
282 |
*/
|
|
|
283 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC8*, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
284 |
{
|
|
|
285 |
public:
|
|
|
286 |
inline static TGeneralHashFunction32 Hash();
|
|
|
287 |
inline static TGeneralIdentityRelation Id();
|
|
|
288 |
};
|
|
|
289 |
/**
|
|
|
290 |
@internalComponent
|
|
|
291 |
*/
|
|
|
292 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC8*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
293 |
{return (TGeneralHashFunction32)&DefaultHash::Des8Ptr;}
|
|
|
294 |
|
|
|
295 |
/**
|
|
|
296 |
@internalComponent
|
|
|
297 |
*/
|
|
|
298 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC8*, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
299 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Des8Ptr;}
|
|
|
300 |
|
|
|
301 |
/**
|
|
|
302 |
@internalComponent
|
|
|
303 |
*/
|
|
|
304 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC16*, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
305 |
{
|
|
|
306 |
public:
|
|
|
307 |
inline static TGeneralHashFunction32 Hash();
|
|
|
308 |
inline static TGeneralIdentityRelation Id();
|
|
|
309 |
};
|
|
|
310 |
/**
|
|
|
311 |
@internalComponent
|
|
|
312 |
*/
|
|
|
313 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC16*, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
314 |
{return (TGeneralHashFunction32)&DefaultHash::Des16Ptr;}
|
|
|
315 |
|
|
|
316 |
/**
|
|
|
317 |
@internalComponent
|
|
|
318 |
*/
|
|
|
319 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC16*, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
320 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Des16Ptr;}
|
|
|
321 |
|
|
|
322 |
/**
|
|
|
323 |
@internalComponent
|
|
|
324 |
*/
|
|
|
325 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
326 |
{
|
|
|
327 |
public:
|
|
|
328 |
inline static TGeneralHashFunction32 Hash();
|
|
|
329 |
inline static TGeneralIdentityRelation Id();
|
|
|
330 |
};
|
|
|
331 |
|
|
|
332 |
/**
|
|
|
333 |
@internalComponent
|
|
|
334 |
*/
|
|
|
335 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
336 |
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
|
|
|
337 |
|
|
|
338 |
/**
|
|
|
339 |
@internalComponent
|
|
|
340 |
*/
|
|
|
341 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
342 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
|
|
|
343 |
|
|
|
344 |
/**
|
|
|
345 |
@internalComponent
|
|
|
346 |
*/
|
|
|
347 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
348 |
{
|
|
|
349 |
public:
|
|
|
350 |
inline static TGeneralHashFunction32 Hash();
|
|
|
351 |
inline static TGeneralIdentityRelation Id();
|
|
|
352 |
};
|
|
|
353 |
|
|
|
354 |
/**
|
|
|
355 |
@internalComponent
|
|
|
356 |
*/
|
|
|
357 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
358 |
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
|
|
|
359 |
|
|
|
360 |
/**
|
|
|
361 |
@internalComponent
|
|
|
362 |
*/
|
|
|
363 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TInt32, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
364 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
|
|
|
365 |
|
|
|
366 |
/**
|
|
|
367 |
@internalComponent
|
|
|
368 |
*/
|
|
|
369 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
370 |
{
|
|
|
371 |
public:
|
|
|
372 |
inline static TGeneralHashFunction32 Hash();
|
|
|
373 |
inline static TGeneralIdentityRelation Id();
|
|
|
374 |
};
|
|
|
375 |
|
|
|
376 |
/**
|
|
|
377 |
@internalComponent
|
|
|
378 |
*/
|
|
|
379 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
380 |
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
|
|
|
381 |
|
|
|
382 |
/**
|
|
|
383 |
@internalComponent
|
|
|
384 |
*/
|
|
|
385 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
386 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
|
|
|
387 |
|
|
|
388 |
|
|
|
389 |
/**
|
|
|
390 |
@internalComponent
|
|
|
391 |
*/
|
|
|
392 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
393 |
{
|
|
|
394 |
public:
|
|
|
395 |
inline static TGeneralHashFunction32 Hash();
|
|
|
396 |
inline static TGeneralIdentityRelation Id();
|
|
|
397 |
};
|
|
|
398 |
|
|
|
399 |
/**
|
|
|
400 |
@internalComponent
|
|
|
401 |
*/
|
|
|
402 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
403 |
{return (TGeneralHashFunction32)&DefaultHash::Integer;}
|
|
|
404 |
|
|
|
405 |
/**
|
|
|
406 |
@internalComponent
|
|
|
407 |
*/
|
|
|
408 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TUint32, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
409 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Integer;}
|
|
|
410 |
|
|
|
411 |
|
|
|
412 |
/**
|
|
|
413 |
@internalComponent
|
|
|
414 |
*/
|
|
|
415 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
416 |
{
|
|
|
417 |
public:
|
|
|
418 |
inline static TGeneralHashFunction32 Hash();
|
|
|
419 |
inline static TGeneralIdentityRelation Id();
|
|
|
420 |
};
|
|
|
421 |
|
|
|
422 |
/**
|
|
|
423 |
@internalComponent
|
|
|
424 |
*/
|
|
|
425 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
426 |
{return (TGeneralHashFunction32)&DefaultHash::Des8;}
|
|
|
427 |
|
|
|
428 |
/**
|
|
|
429 |
@internalComponent
|
|
|
430 |
*/
|
|
|
431 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC8, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
432 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Des8;}
|
|
|
433 |
|
|
|
434 |
|
|
|
435 |
/**
|
|
|
436 |
@internalComponent
|
|
|
437 |
*/
|
|
|
438 |
TEMPLATE_SPECIALIZATION class RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>
|
|
|
439 |
{
|
|
|
440 |
public:
|
|
|
441 |
inline static TGeneralHashFunction32 Hash();
|
|
|
442 |
inline static TGeneralIdentityRelation Id();
|
|
|
443 |
};
|
|
|
444 |
|
|
|
445 |
/**
|
|
|
446 |
@internalComponent
|
|
|
447 |
*/
|
|
|
448 |
inline TGeneralHashFunction32 RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>::Hash()
|
|
|
449 |
{return (TGeneralHashFunction32)&DefaultHash::Des16;}
|
|
|
450 |
|
|
|
451 |
/**
|
|
|
452 |
@internalComponent
|
|
|
453 |
*/
|
|
|
454 |
inline TGeneralIdentityRelation RHashTableBase::Defaults<TDesC16, RHashTableBase::EDefaultSpecifier_Normal>::Id()
|
|
|
455 |
{return (TGeneralIdentityRelation)&DefaultIdentity::Des16;}
|
|
|
456 |
|
|
|
457 |
|
|
|
458 |
|
|
|
459 |
|
|
|
460 |
/**
|
|
|
461 |
@internalComponent
|
|
|
462 |
|
|
|
463 |
Base class used in the derivation of THashSetIter<T>, TPtrHashSetIter<T>,
|
|
|
464 |
THashMapIter<K,V> and TPtrHashMapIter<K,V>.
|
|
|
465 |
|
|
|
466 |
This class provides iteration capability for the hash table classes derived
|
|
|
467 |
from RHashTableBase.
|
|
|
468 |
The class is internal and is not intended for use.
|
|
|
469 |
*/
|
|
|
470 |
class THashTableIterBase
|
|
|
471 |
{
|
|
|
472 |
protected:
|
|
|
473 |
IMPORT_C THashTableIterBase(const RHashTableBase& aTable);
|
|
|
474 |
IMPORT_C void Reset();
|
|
|
475 |
IMPORT_C const TAny* Next(TInt aOffset=0);
|
|
|
476 |
IMPORT_C const TAny* Current(TInt aOffset=0) const;
|
|
|
477 |
IMPORT_C void RemoveCurrent();
|
|
|
478 |
private:
|
|
|
479 |
const RHashTableBase& iTbl;
|
|
|
480 |
TInt iIndex;
|
|
|
481 |
TInt iPad1; // expansion room
|
|
|
482 |
TInt iPad2;
|
|
|
483 |
};
|
|
|
484 |
|
|
|
485 |
|
|
|
486 |
|
|
|
487 |
template <class T> class THashSetIter;
|
|
|
488 |
|
|
|
489 |
/**
|
|
|
490 |
@publishedAll
|
|
|
491 |
@released
|
|
|
492 |
|
|
|
493 |
A templated class which implements an unordered extensional set of objects of
|
|
|
494 |
type T using a probe-sequence hash table. The objects are copied into the set
|
|
|
495 |
when they are added. A bitwise binary copy is used here, so the type T must
|
|
|
496 |
not implement a nontrivial copy constructor.
|
|
|
497 |
|
|
|
498 |
*/
|
|
|
499 |
template <class T>
|
|
|
500 |
class RHashSet : public RHashTableBase
|
|
|
501 |
{
|
|
|
502 |
private:
|
|
|
503 |
friend class THashSetIter<T>;
|
|
|
504 |
|
|
|
505 |
struct SFullElement
|
|
|
506 |
{
|
|
|
507 |
TUint32 iHash;
|
|
|
508 |
T iT;
|
|
|
509 |
};
|
|
|
510 |
|
|
|
511 |
public:
|
|
|
512 |
|
|
|
513 |
/**
|
|
|
514 |
A class which allows iteration over the elements of a RHashSet<T> class.
|
|
|
515 |
|
|
|
516 |
The set being iterated over may not be modified while an iteration is in progress
|
|
|
517 |
or the iteration operations may malfunction or panic.
|
|
|
518 |
|
|
|
519 |
@see THashSetIter<T>
|
|
|
520 |
*/
|
|
|
521 |
typedef THashSetIter<T> TIter;
|
|
|
522 |
|
|
|
523 |
/**
|
|
|
524 |
Construct a set of objects of type T using a specified hash function and identity relation.
|
|
|
525 |
The set is initially empty.
|
|
|
526 |
|
|
|
527 |
@param aHash The hash function used to hash the objects of type T.
|
|
|
528 |
@param aIdentity The identity relation used to determine if two objects of type T
|
|
|
529 |
should be considered identical.
|
|
|
530 |
*/
|
|
|
531 |
inline RHashSet(const THashFunction32<T>& aHash, const TIdentityRelation<T>& aIdentity)
|
|
|
532 |
: RHashTableBase(aHash, aIdentity, sizeof(SFullElement), _FOFF(SFullElement,iT))
|
|
|
533 |
{}
|
|
|
534 |
|
|
|
535 |
|
|
|
536 |
/**
|
|
|
537 |
Construct a set of objects of type T using a default hash function and identity relation.
|
|
|
538 |
The set is initially empty.
|
|
|
539 |
*/
|
|
|
540 |
inline RHashSet()
|
|
|
541 |
: RHashTableBase(Defaults<T,EDefaultSpecifier_Normal>::Hash(), Defaults<T,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), _FOFF(SFullElement,iT))
|
|
|
542 |
{}
|
|
|
543 |
|
|
|
544 |
|
|
|
545 |
/**
|
|
|
546 |
Free all memory used by this set.
|
|
|
547 |
Returns the set to the same state it had following construction.
|
|
|
548 |
*/
|
|
|
549 |
inline void Close()
|
|
|
550 |
{ RHashTableBase::Close(); }
|
|
|
551 |
|
|
|
552 |
|
|
|
553 |
/**
|
|
|
554 |
Locate a specified element in the set.
|
|
|
555 |
|
|
|
556 |
@param aKey The object of type T to search for.
|
|
|
557 |
@return A pointer to the copy of the specified object in the set, if it
|
|
|
558 |
exists. The object may not be modified via this pointer.
|
|
|
559 |
NULL if the specified object is not a member of this set.
|
|
|
560 |
*/
|
|
|
561 |
inline const T* Find(const T& aKey) const
|
|
|
562 |
{ return (const T*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iT)); }
|
|
|
563 |
|
|
|
564 |
|
|
|
565 |
/**
|
|
|
566 |
Locate a specified element in the set.
|
|
|
567 |
|
|
|
568 |
@param aKey The object of type T to search for.
|
|
|
569 |
@return A reference to the copy of the specified object in the set, if it
|
|
|
570 |
exists. The object may not be modified via this reference.
|
|
|
571 |
@leave KErrNotFound if the specified object is not a member of this set.
|
|
|
572 |
*/
|
|
|
573 |
inline const T& FindL(const T& aKey) const
|
|
|
574 |
{ return *(const T*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iT)); }
|
|
|
575 |
|
|
|
576 |
|
|
|
577 |
/**
|
|
|
578 |
Locate a specified element in the set.
|
|
|
579 |
|
|
|
580 |
@param aKey The object of type T to search for.
|
|
|
581 |
@return A pointer to the copy of the specified object in the set, if it
|
|
|
582 |
exists. The object may be modified via this pointer. Care should
|
|
|
583 |
be taken not to modify any parts of the object which are used by
|
|
|
584 |
either the hash function or the identity relation for this set.
|
|
|
585 |
If this is done the set may become inconsistent, resulting in
|
|
|
586 |
malfunctions and/or panics at a later time.
|
|
|
587 |
NULL if the specified object is not a member of this set.
|
|
|
588 |
*/
|
|
|
589 |
inline T* Find(const T& aKey)
|
|
|
590 |
{ return (T*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iT)); }
|
|
|
591 |
|
|
|
592 |
|
|
|
593 |
/**
|
|
|
594 |
Locate a specified element in the set.
|
|
|
595 |
|
|
|
596 |
@param aKey The object of type T to search for.
|
|
|
597 |
@return A reference to the copy of the specified object in the set, if it
|
|
|
598 |
exists. The object may be modified via this reference. Care should
|
|
|
599 |
be taken not to modify any parts of the object which are used by
|
|
|
600 |
either the hash function or the identity relation for this set.
|
|
|
601 |
If this is done the set may become inconsistent, resulting in
|
|
|
602 |
malfunctions and/or panics at a later time.
|
|
|
603 |
@leave KErrNotFound if the specified object is not a member of this set.
|
|
|
604 |
*/
|
|
|
605 |
inline T& FindL(const T& aKey)
|
|
|
606 |
{ return *(T*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iT)); }
|
|
|
607 |
|
|
|
608 |
|
|
|
609 |
/**
|
|
|
610 |
Insert an element into the set.
|
|
|
611 |
|
|
|
612 |
If the specified object is not currently a member of the set, a copy of the
|
|
|
613 |
object is added to the set and KErrNone is returned.
|
|
|
614 |
If the specified object is currently a member of the set, the existing copy
|
|
|
615 |
of the object is replaced by the provided object and KErrNone is
|
|
|
616 |
returned.
|
|
|
617 |
In both cases the object is copied bitwise into the set.
|
|
|
618 |
|
|
|
619 |
@param aKey The object of type T to add to the set.
|
|
|
620 |
@return KErrNone if the object was added successfully.
|
|
|
621 |
KErrNoMemory if memory could not be allocated to store
|
|
|
622 |
the copy of aKey.
|
|
|
623 |
*/
|
|
|
624 |
inline TInt Insert(const T& aKey)
|
|
|
625 |
{ return RHashTableBase::ValueInsert(&aKey, sizeof(T), 0, 0, 0); }
|
|
|
626 |
|
|
|
627 |
|
|
|
628 |
/**
|
|
|
629 |
Insert an element into the set.
|
|
|
630 |
|
|
|
631 |
If the specified object is not currently a member of the set, a copy of the
|
|
|
632 |
object is added to the set and KErrNone is returned.
|
|
|
633 |
If the specified object is currently a member of the set, the existing copy
|
|
|
634 |
of the object is replaced by the provided object and KErrNone is
|
|
|
635 |
returned.
|
|
|
636 |
In both cases the object is copied bitwise into the set.
|
|
|
637 |
|
|
|
638 |
@param aKey The object of type T to add to the set.
|
|
|
639 |
@leave KErrNoMemory if memory could not be allocated to store
|
|
|
640 |
the copy of aKey.
|
|
|
641 |
*/
|
|
|
642 |
inline void InsertL(const T& aKey)
|
|
|
643 |
{ RHashTableBase::ValueInsertL(&aKey, sizeof(T), 0, 0, 0); }
|
|
|
644 |
|
|
|
645 |
|
|
|
646 |
/**
|
|
|
647 |
Remove an element from the set.
|
|
|
648 |
|
|
|
649 |
@param aKey The object to be removed.
|
|
|
650 |
@return KErrNone if the object was removed successfully.
|
|
|
651 |
KErrNotFound if the object was not present in the set.
|
|
|
652 |
*/
|
|
|
653 |
inline TInt Remove(const T& aKey)
|
|
|
654 |
{ return RHashTableBase::Remove(&aKey); }
|
|
|
655 |
|
|
|
656 |
|
|
|
657 |
/**
|
|
|
658 |
Query the number of elements in the set.
|
|
|
659 |
|
|
|
660 |
@return The number of elements currently in the set.
|
|
|
661 |
*/
|
|
|
662 |
inline TInt Count() const
|
|
|
663 |
{ return RHashTableBase::Count(); }
|
|
|
664 |
|
|
|
665 |
|
|
|
666 |
/**
|
|
|
667 |
Expand the set to accommodate a specified number of elements.
|
|
|
668 |
If the set already has enough space for the specified number of elements, no
|
|
|
669 |
action is taken. Any elements already in the set are retained.
|
|
|
670 |
|
|
|
671 |
@param aCount The number of elements for which space should be allocated.
|
|
|
672 |
@return KErrNone if the operation completed successfully.
|
|
|
673 |
@return KErrNoMemory if sufficient memory could not be allocated.
|
|
|
674 |
*/
|
|
|
675 |
inline TInt Reserve(TInt aCount)
|
|
|
676 |
{ return RHashTableBase::Reserve(aCount); }
|
|
|
677 |
|
|
|
678 |
|
|
|
679 |
/**
|
|
|
680 |
Expand the set to accommodate a specified number of elements.
|
|
|
681 |
If the set already has enough space for the specified number of elements, no
|
|
|
682 |
action is taken. Any elements already in the set are retained.
|
|
|
683 |
|
|
|
684 |
@param aCount The number of elements for which space should be allocated.
|
|
|
685 |
@leave KErrNoMemory if sufficient memory could not be allocated.
|
|
|
686 |
*/
|
|
|
687 |
inline void ReserveL(TInt aCount)
|
|
|
688 |
{ RHashTableBase::ReserveL(aCount); }
|
|
|
689 |
|
|
|
690 |
};
|
|
|
691 |
|
|
|
692 |
|
|
|
693 |
/**
|
|
|
694 |
@publishedAll
|
|
|
695 |
@released
|
|
|
696 |
|
|
|
697 |
A templated class which allows iteration over the elements of a RHashSet<T>
|
|
|
698 |
class.
|
|
|
699 |
|
|
|
700 |
The set being iterated over may not be modified while an iteration is in progress
|
|
|
701 |
or the iteration operations may malfunction or panic.
|
|
|
702 |
|
|
|
703 |
@see RHashSet<T>
|
|
|
704 |
*/
|
|
|
705 |
template <class T>
|
|
|
706 |
class THashSetIter : public THashTableIterBase
|
|
|
707 |
{
|
|
|
708 |
private:
|
|
|
709 |
|
|
|
710 |
struct SFullElement
|
|
|
711 |
{
|
|
|
712 |
TUint32 iHash;
|
|
|
713 |
T iT;
|
|
|
714 |
};
|
|
|
715 |
|
|
|
716 |
public:
|
|
|
717 |
|
|
|
718 |
/**
|
|
|
719 |
Construct an iterator over the specified set.
|
|
|
720 |
The iterator starts at conceptual position one before the beginning of the list
|
|
|
721 |
being iterated.
|
|
|
722 |
|
|
|
723 |
@param aSet The set to be iterated over.
|
|
|
724 |
*/
|
|
|
725 |
inline THashSetIter(const RHashSet<T>& aSet)
|
|
|
726 |
: THashTableIterBase(aSet)
|
|
|
727 |
{}
|
|
|
728 |
|
|
|
729 |
|
|
|
730 |
/**
|
|
|
731 |
Reset the iterator to its initial state.
|
|
|
732 |
|
|
|
733 |
@param aSet The set to be iterated over.
|
|
|
734 |
*/
|
|
|
735 |
inline void Reset()
|
|
|
736 |
{ THashTableIterBase::Reset(); }
|
|
|
737 |
|
|
|
738 |
|
|
|
739 |
/**
|
|
|
740 |
Return the current position of the iterator.
|
|
|
741 |
|
|
|
742 |
@return A pointer to the set member corresponding to the current position of the
|
|
|
743 |
iterator.
|
|
|
744 |
NULL if the iterator has just been constructed or reset, or if it has
|
|
|
745 |
previously reached the end of an iteration.
|
|
|
746 |
*/
|
|
|
747 |
inline const T* Current() const
|
|
|
748 |
{ return (const T*)THashTableIterBase::Current(_FOFF(SFullElement,iT)); }
|
|
|
749 |
|
|
|
750 |
|
|
|
751 |
/**
|
|
|
752 |
Steps the iterator to the next position.
|
|
|
753 |
|
|
|
754 |
@return A pointer to the set member corresponding to the next position of the
|
|
|
755 |
iterator.
|
|
|
756 |
NULL if the iterator has exhausted all the available set elements.
|
|
|
757 |
*/
|
|
|
758 |
inline const T* Next()
|
|
|
759 |
{ return (const T*)THashTableIterBase::Next(_FOFF(SFullElement,iT)); }
|
|
|
760 |
|
|
|
761 |
|
|
|
762 |
/**
|
|
|
763 |
Removes the element at the current iterator position from the hash table.
|
|
|
764 |
If the iterator does not currently point to a valid element, no action is taken.
|
|
|
765 |
Note that the iterator position is not altered so it no longer points to a valid
|
|
|
766 |
element following the Remove(). It is illegal to call Current() on the iterator
|
|
|
767 |
after calling Remove() - the only legal operations are Reset() and Next().
|
|
|
768 |
|
|
|
769 |
*/
|
|
|
770 |
inline void RemoveCurrent()
|
|
|
771 |
{ THashTableIterBase::RemoveCurrent(); }
|
|
|
772 |
};
|
|
|
773 |
|
|
|
774 |
|
|
|
775 |
|
|
|
776 |
template <class T> class TPtrHashSetIter;
|
|
|
777 |
|
|
|
778 |
/**
|
|
|
779 |
@publishedAll
|
|
|
780 |
@released
|
|
|
781 |
|
|
|
782 |
A templated class which implements an unordered extensional set of objects of
|
|
|
783 |
type T using a probe-sequence hash table. The objects are not copied into the set
|
|
|
784 |
when they are added; rather the set stores pointers to the contained objects.
|
|
|
785 |
|
|
|
786 |
*/
|
|
|
787 |
template <class T>
|
|
|
788 |
class RPtrHashSet : public RHashTableBase
|
|
|
789 |
{
|
|
|
790 |
private:
|
|
|
791 |
friend class TPtrHashSetIter<T>;
|
|
|
792 |
|
|
|
793 |
struct SFullElement
|
|
|
794 |
{
|
|
|
795 |
TUint32 iHash;
|
|
|
796 |
T* iT;
|
|
|
797 |
};
|
|
|
798 |
|
|
|
799 |
public:
|
|
|
800 |
|
|
|
801 |
/**
|
|
|
802 |
A class which allows iteration over the elements of a RPtrHashSet<T> class.
|
|
|
803 |
|
|
|
804 |
The set being iterated over may not be modified while an iteration is in progress
|
|
|
805 |
or the iteration operations may malfunction or panic.
|
|
|
806 |
|
|
|
807 |
@see TPtrHashSetIter<T>
|
|
|
808 |
*/
|
|
|
809 |
typedef TPtrHashSetIter<T> TIter;
|
|
|
810 |
|
|
|
811 |
/**
|
|
|
812 |
Construct a set of objects of type T using a specified hash function and identity relation.
|
|
|
813 |
The set is initially empty.
|
|
|
814 |
|
|
|
815 |
@param aHash The hash function used to hash the objects of type T.
|
|
|
816 |
@param aIdentity The identity relation used to determine if two objects of type T
|
|
|
817 |
should be considered identical.
|
|
|
818 |
*/
|
|
|
819 |
inline RPtrHashSet(const THashFunction32<T>& aHash, const TIdentityRelation<T>& aIdentity)
|
|
|
820 |
: RHashTableBase(aHash, aIdentity, sizeof(SFullElement), 0)
|
|
|
821 |
{}
|
|
|
822 |
|
|
|
823 |
|
|
|
824 |
/**
|
|
|
825 |
Construct a set of objects of type T using a default hash function and identity relation.
|
|
|
826 |
The set is initially empty.
|
|
|
827 |
*/
|
|
|
828 |
inline RPtrHashSet()
|
|
|
829 |
: RHashTableBase(Defaults<T,EDefaultSpecifier_Normal>::Hash(), Defaults<T,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), 0)
|
|
|
830 |
{}
|
|
|
831 |
|
|
|
832 |
|
|
|
833 |
/**
|
|
|
834 |
Free all memory used by this set.
|
|
|
835 |
Returns the set to the same state it had following construction.
|
|
|
836 |
*/
|
|
|
837 |
inline void Close()
|
|
|
838 |
{ RHashTableBase::Close(); }
|
|
|
839 |
|
|
|
840 |
|
|
|
841 |
/**
|
|
|
842 |
Locate a specified element in the set.
|
|
|
843 |
|
|
|
844 |
@param aKey The object of type T to search for.
|
|
|
845 |
@return A pointer to the specified object, if it is in the set.
|
|
|
846 |
The object may not be modified via this pointer.
|
|
|
847 |
NULL if the specified object is not a member of this set.
|
|
|
848 |
*/
|
|
|
849 |
inline const T* Find(const T& aKey) const
|
|
|
850 |
{ return (const T*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iT)); }
|
|
|
851 |
|
|
|
852 |
|
|
|
853 |
/**
|
|
|
854 |
Locate a specified element in the set.
|
|
|
855 |
|
|
|
856 |
@param aKey The object of type T to search for.
|
|
|
857 |
@return A reference to the specified object, if it is in the set.
|
|
|
858 |
The object may not be modified via this reference.
|
|
|
859 |
@leave KErrNotFound if the specified object is not a member of this set.
|
|
|
860 |
*/
|
|
|
861 |
inline const T& FindL(const T& aKey) const
|
|
|
862 |
{ return *(const T*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iT)); }
|
|
|
863 |
|
|
|
864 |
|
|
|
865 |
/**
|
|
|
866 |
Locate a specified element in the set.
|
|
|
867 |
|
|
|
868 |
@param aKey The object of type T to search for.
|
|
|
869 |
@return A pointer to the specified object, if it is in the set.
|
|
|
870 |
The object may be modified via this pointer. Care should
|
|
|
871 |
be taken not to modify any parts of the object which are used by
|
|
|
872 |
either the hash function or the identity relation for this set.
|
|
|
873 |
If this is done the set may become inconsistent, resulting in
|
|
|
874 |
malfunctions and/or panics at a later time.
|
|
|
875 |
NULL if the specified object is not a member of this set.
|
|
|
876 |
*/
|
|
|
877 |
inline T* Find(const T& aKey)
|
|
|
878 |
{ return (T*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iT)); }
|
|
|
879 |
|
|
|
880 |
|
|
|
881 |
/**
|
|
|
882 |
Locate a specified element in the set.
|
|
|
883 |
|
|
|
884 |
@param aKey The object of type T to search for.
|
|
|
885 |
@return A reference to the specified object, if it is in the set.
|
|
|
886 |
The object may be modified via this reference. Care should
|
|
|
887 |
be taken not to modify any parts of the object which are used by
|
|
|
888 |
either the hash function or the identity relation for this set.
|
|
|
889 |
If this is done the set may become inconsistent, resulting in
|
|
|
890 |
malfunctions and/or panics at a later time.
|
|
|
891 |
@leave KErrNotFound if the specified object is not a member of this set.
|
|
|
892 |
*/
|
|
|
893 |
inline T& FindL(const T& aKey)
|
|
|
894 |
{ return *(T*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iT)); }
|
|
|
895 |
|
|
|
896 |
|
|
|
897 |
/**
|
|
|
898 |
Insert an element into the set.
|
|
|
899 |
|
|
|
900 |
If the specified object is not currently a member of the set, a pointer to the
|
|
|
901 |
object is added to the set and KErrNone is returned.
|
|
|
902 |
If the specified object is currently a member of the set, the existing pointer
|
|
|
903 |
to the object is replaced by the provided pointer and KErrNone is
|
|
|
904 |
returned.
|
|
|
905 |
In both cases only a pointer to the object is stored - the object is never copied.
|
|
|
906 |
|
|
|
907 |
@param aKey A pointer to the object of type T to add to the set.
|
|
|
908 |
@return KErrNone if the object was added successfully.
|
|
|
909 |
KErrNoMemory if memory could not be allocated to store
|
|
|
910 |
the pointer to the new object.
|
|
|
911 |
*/
|
|
|
912 |
inline TInt Insert(const T* aKey)
|
|
|
913 |
{ return RHashTableBase::PtrInsert(aKey, 0); }
|
|
|
914 |
|
|
|
915 |
|
|
|
916 |
/**
|
|
|
917 |
Insert an element into the set.
|
|
|
918 |
|
|
|
919 |
If the specified object is not currently a member of the set, a pointer to the
|
|
|
920 |
object is added to the set and KErrNone is returned.
|
|
|
921 |
If the specified object is currently a member of the set, the existing pointer
|
|
|
922 |
to the object is replaced by the provided pointer and KErrNone is
|
|
|
923 |
returned.
|
|
|
924 |
In both cases only a pointer to the object is stored - the object is never copied.
|
|
|
925 |
|
|
|
926 |
@param aKey A pointer to the object of type T to add to the set.
|
|
|
927 |
@leave KErrNoMemory if memory could not be allocated to store the pointer to the new object.
|
|
|
928 |
*/
|
|
|
929 |
inline void InsertL(const T* aKey)
|
|
|
930 |
{ RHashTableBase::PtrInsertL(aKey, 0); }
|
|
|
931 |
|
|
|
932 |
|
|
|
933 |
/**
|
|
|
934 |
Remove an element from the set.
|
|
|
935 |
|
|
|
936 |
@param aKey A pointer to the object to be removed.
|
|
|
937 |
@return KErrNone if the object was removed successfully.
|
|
|
938 |
KErrNotFound if the object was not present in the set.
|
|
|
939 |
*/
|
|
|
940 |
inline TInt Remove(const T* aKey)
|
|
|
941 |
{ return RHashTableBase::Remove(aKey); }
|
|
|
942 |
|
|
|
943 |
|
|
|
944 |
/**
|
|
|
945 |
Query the number of elements in the set.
|
|
|
946 |
|
|
|
947 |
@return The number of elements currently in the set.
|
|
|
948 |
*/
|
|
|
949 |
inline TInt Count() const
|
|
|
950 |
{ return RHashTableBase::Count(); }
|
|
|
951 |
|
|
|
952 |
|
|
|
953 |
/**
|
|
|
954 |
Expand the set to accommodate a specified number of elements.
|
|
|
955 |
If the set already has enough space for the specified number of elements, no
|
|
|
956 |
action is taken. Any elements already in the set are retained.
|
|
|
957 |
|
|
|
958 |
@param aCount The number of elements for which space should be allocated.
|
|
|
959 |
@return KErrNone if the operation completed successfully.
|
|
|
960 |
@return KErrNoMemory if sufficient memory could not be allocated.
|
|
|
961 |
*/
|
|
|
962 |
inline TInt Reserve(TInt aCount)
|
|
|
963 |
{ return RHashTableBase::Reserve(aCount); }
|
|
|
964 |
|
|
|
965 |
|
|
|
966 |
/**
|
|
|
967 |
Expand the set to accommodate a specified number of elements.
|
|
|
968 |
If the set already has enough space for the specified number of elements, no
|
|
|
969 |
action is taken. Any elements already in the set are retained.
|
|
|
970 |
|
|
|
971 |
@param aCount The number of elements for which space should be allocated.
|
|
|
972 |
@leave KErrNoMemory if sufficient memory could not be allocated.
|
|
|
973 |
*/
|
|
|
974 |
inline void ReserveL(TInt aCount)
|
|
|
975 |
{ RHashTableBase::ReserveL(aCount); }
|
|
|
976 |
|
|
|
977 |
|
|
|
978 |
void ResetAndDestroy();
|
|
|
979 |
};
|
|
|
980 |
|
|
|
981 |
|
|
|
982 |
/**
|
|
|
983 |
@publishedAll
|
|
|
984 |
@released
|
|
|
985 |
|
|
|
986 |
A templated class which allows iteration over the elements of a RPtrHashSet<T>
|
|
|
987 |
class.
|
|
|
988 |
|
|
|
989 |
The set being iterated over may not be modified while an iteration is in progress
|
|
|
990 |
or the iteration operations may malfunction or panic.
|
|
|
991 |
|
|
|
992 |
@see RPtrHashSet<T>
|
|
|
993 |
*/
|
|
|
994 |
template <class T>
|
|
|
995 |
class TPtrHashSetIter : public THashTableIterBase
|
|
|
996 |
{
|
|
|
997 |
private:
|
|
|
998 |
|
|
|
999 |
struct SFullElement
|
|
|
1000 |
{
|
|
|
1001 |
TUint32 iHash;
|
|
|
1002 |
T* iT;
|
|
|
1003 |
};
|
|
|
1004 |
|
|
|
1005 |
public:
|
|
|
1006 |
|
|
|
1007 |
/**
|
|
|
1008 |
Construct an iterator over the specified set.
|
|
|
1009 |
The iterator starts at conceptual position one before the beginning of the list
|
|
|
1010 |
being iterated.
|
|
|
1011 |
|
|
|
1012 |
@param aSet The set to be iterated over.
|
|
|
1013 |
*/
|
|
|
1014 |
inline TPtrHashSetIter(const RPtrHashSet<T>& aSet)
|
|
|
1015 |
: THashTableIterBase(aSet)
|
|
|
1016 |
{}
|
|
|
1017 |
|
|
|
1018 |
|
|
|
1019 |
/**
|
|
|
1020 |
Reset the iterator to its initial state.
|
|
|
1021 |
|
|
|
1022 |
@param aSet The set to be iterated over.
|
|
|
1023 |
*/
|
|
|
1024 |
inline void Reset()
|
|
|
1025 |
{ THashTableIterBase::Reset(); }
|
|
|
1026 |
|
|
|
1027 |
|
|
|
1028 |
/**
|
|
|
1029 |
Return the current position of the iterator.
|
|
|
1030 |
|
|
|
1031 |
@return A pointer to the set member corresponding to the current position of the
|
|
|
1032 |
iterator.
|
|
|
1033 |
NULL if the iterator has just been constructed or reset, or if it has
|
|
|
1034 |
previously reached the end of an iteration.
|
|
|
1035 |
*/
|
|
|
1036 |
inline const T* Current() const
|
|
|
1037 |
{ return (const T*)THashTableIterBase::Current(-_FOFF(SFullElement,iT)); }
|
|
|
1038 |
|
|
|
1039 |
|
|
|
1040 |
/**
|
|
|
1041 |
Steps the iterator to the next position.
|
|
|
1042 |
|
|
|
1043 |
@return A pointer to the set member corresponding to the next position of the
|
|
|
1044 |
iterator.
|
|
|
1045 |
NULL if the iterator has exhausted all the available set elements.
|
|
|
1046 |
*/
|
|
|
1047 |
inline const T* Next()
|
|
|
1048 |
{ return (const T*)THashTableIterBase::Next(-_FOFF(SFullElement,iT)); }
|
|
|
1049 |
|
|
|
1050 |
|
|
|
1051 |
/**
|
|
|
1052 |
Removes the element at the current iterator position from the hash table.
|
|
|
1053 |
If the iterator does not currently point to a valid element, no action is taken.
|
|
|
1054 |
Note that the iterator position is not altered so it no longer points to a valid
|
|
|
1055 |
element following the Remove(). It is illegal to call Current() on the iterator
|
|
|
1056 |
after calling Remove() - the only legal operations are Reset() and Next().
|
|
|
1057 |
|
|
|
1058 |
*/
|
|
|
1059 |
inline void RemoveCurrent()
|
|
|
1060 |
{ THashTableIterBase::RemoveCurrent(); }
|
|
|
1061 |
};
|
|
|
1062 |
|
|
|
1063 |
|
|
|
1064 |
|
|
|
1065 |
template <class K, class V> class THashMapIter;
|
|
|
1066 |
|
|
|
1067 |
/**
|
|
|
1068 |
@publishedAll
|
|
|
1069 |
@released
|
|
|
1070 |
|
|
|
1071 |
A templated class which implements an associative array with key type K and value type V,
|
|
|
1072 |
using a probe-sequence hash table. Both the key and value objects are copied into the
|
|
|
1073 |
table when they are added. A bitwise binary copy is used here, so neither of the types
|
|
|
1074 |
K and V may implement a nontrivial copy constructor.
|
|
|
1075 |
|
|
|
1076 |
*/
|
|
|
1077 |
template <class K, class V>
|
|
|
1078 |
class RHashMap : public RHashTableBase
|
|
|
1079 |
{
|
|
|
1080 |
private:
|
|
|
1081 |
friend class THashMapIter<K,V>;
|
|
|
1082 |
|
|
|
1083 |
struct SFullElement
|
|
|
1084 |
{
|
|
|
1085 |
TUint32 iHash;
|
|
|
1086 |
K iK;
|
|
|
1087 |
V iV;
|
|
|
1088 |
};
|
|
|
1089 |
|
|
|
1090 |
public:
|
|
|
1091 |
|
|
|
1092 |
/**
|
|
|
1093 |
A class which allows iteration over the elements of a RHashMap<K,V> class.
|
|
|
1094 |
|
|
|
1095 |
The array being iterated over may not be modified while an iteration is in progress
|
|
|
1096 |
or the iteration operations may malfunction or panic.
|
|
|
1097 |
|
|
|
1098 |
@see THashMapIter<K,V>
|
|
|
1099 |
*/
|
|
|
1100 |
typedef THashMapIter<K,V> TIter;
|
|
|
1101 |
|
|
|
1102 |
/**
|
|
|
1103 |
Construct an associative array of key-value pairs of type (K,V) using a
|
|
|
1104 |
specified hash function and identity relation.
|
|
|
1105 |
The array initially contains no key-value pairs.
|
|
|
1106 |
|
|
|
1107 |
@param aHash The hash function used to hash the key objects of type K.
|
|
|
1108 |
@param aIdentity The identity relation used to determine if two key objects
|
|
|
1109 |
of type K should be considered identical.
|
|
|
1110 |
*/
|
|
|
1111 |
inline RHashMap(const THashFunction32<K>& aHash, const TIdentityRelation<K>& aIdentity)
|
|
|
1112 |
: RHashTableBase(aHash, aIdentity, sizeof(SFullElement), _FOFF(SFullElement,iK))
|
|
|
1113 |
{}
|
|
|
1114 |
|
|
|
1115 |
|
|
|
1116 |
/**
|
|
|
1117 |
Construct an associative array of key-value pairs of type (K,V) using a
|
|
|
1118 |
default hash function and identity relation.
|
|
|
1119 |
The array initially contains no key-value pairs.
|
|
|
1120 |
*/
|
|
|
1121 |
inline RHashMap()
|
|
|
1122 |
: RHashTableBase(Defaults<K,EDefaultSpecifier_Normal>::Hash(), Defaults<K,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), _FOFF(SFullElement,iK))
|
|
|
1123 |
{}
|
|
|
1124 |
|
|
|
1125 |
|
|
|
1126 |
/**
|
|
|
1127 |
Free all memory used by this array.
|
|
|
1128 |
Returns the array to the same state it had following construction.
|
|
|
1129 |
*/
|
|
|
1130 |
inline void Close()
|
|
|
1131 |
{ RHashTableBase::Close(); }
|
|
|
1132 |
|
|
|
1133 |
|
|
|
1134 |
/**
|
|
|
1135 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1136 |
corresponding value.
|
|
|
1137 |
|
|
|
1138 |
@param aKey The key object of type K to look up.
|
|
|
1139 |
@return A pointer to the copy of the corresponding value object in the
|
|
|
1140 |
array, if the specified key object was found.
|
|
|
1141 |
The value object may not be modified via this pointer.
|
|
|
1142 |
NULL if the specified key object was not found.
|
|
|
1143 |
*/
|
|
|
1144 |
inline const V* Find(const K& aKey) const
|
|
|
1145 |
{ return (const V*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iV)); }
|
|
|
1146 |
|
|
|
1147 |
|
|
|
1148 |
/**
|
|
|
1149 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1150 |
corresponding value.
|
|
|
1151 |
|
|
|
1152 |
@param aKey The key object of type K to look up.
|
|
|
1153 |
@return A reference to the copy of the corresponding value object in the
|
|
|
1154 |
array, if the specified key object was found.
|
|
|
1155 |
The value object may not be modified via this reference.
|
|
|
1156 |
@leave KErrNotFound if the specified key object was not found.
|
|
|
1157 |
*/
|
|
|
1158 |
inline const V& FindL(const K& aKey) const
|
|
|
1159 |
{ return *(const V*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iV)); }
|
|
|
1160 |
|
|
|
1161 |
|
|
|
1162 |
/**
|
|
|
1163 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1164 |
corresponding value.
|
|
|
1165 |
|
|
|
1166 |
@param aKey The key object of type K to look up.
|
|
|
1167 |
@return A pointer to the copy of the corresponding value object in the
|
|
|
1168 |
array, if the specified key object was found.
|
|
|
1169 |
The value object may be modified via this pointer.
|
|
|
1170 |
NULL if the specified key object was not found.
|
|
|
1171 |
*/
|
|
|
1172 |
inline V* Find(const K& aKey)
|
|
|
1173 |
{ return (V*)RHashTableBase::Find(&aKey, _FOFF(SFullElement,iV)); }
|
|
|
1174 |
|
|
|
1175 |
|
|
|
1176 |
/**
|
|
|
1177 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1178 |
corresponding value.
|
|
|
1179 |
|
|
|
1180 |
@param aKey The key object of type K to look up.
|
|
|
1181 |
@return A reference to the copy of the corresponding value object in the
|
|
|
1182 |
array, if the specified key object was found.
|
|
|
1183 |
The value object may be modified via this reference.
|
|
|
1184 |
@leave KErrNotFound if the specified key object was not found.
|
|
|
1185 |
*/
|
|
|
1186 |
inline V& FindL(const K& aKey)
|
|
|
1187 |
{ return *(V*)RHashTableBase::FindL(&aKey, _FOFF(SFullElement,iV)); }
|
|
|
1188 |
|
|
|
1189 |
|
|
|
1190 |
/**
|
|
|
1191 |
Insert a key-value pair into the array.
|
|
|
1192 |
|
|
|
1193 |
If the specified key object is not found in the array, a copy of the
|
|
|
1194 |
key object along with a copy of the value object are added to the array
|
|
|
1195 |
and KErrNone is returned.
|
|
|
1196 |
If the specified key object is found in the array, the existing copies
|
|
|
1197 |
of both the key and value objects are replaced by the provided objects
|
|
|
1198 |
and KErrNone is returned.
|
|
|
1199 |
In both cases the objects are copied bitwise into the array.
|
|
|
1200 |
|
|
|
1201 |
@param aKey The key object of type K to add to the array.
|
|
|
1202 |
@param aValue The value object of type V to associate with aKey.
|
|
|
1203 |
@return KErrNone if the key-value pair was added successfully.
|
|
|
1204 |
KErrNoMemory if memory could not be allocated to store
|
|
|
1205 |
the copies of aKey and aValue.
|
|
|
1206 |
*/
|
|
|
1207 |
inline TInt Insert(const K& aKey, const V& aValue)
|
|
|
1208 |
{ return RHashTableBase::ValueInsert(&aKey, sizeof(K), &aValue, _FOFF(SFullElement,iV), sizeof(V)); }
|
|
|
1209 |
|
|
|
1210 |
|
|
|
1211 |
/**
|
|
|
1212 |
Insert a key-value pair into the array.
|
|
|
1213 |
|
|
|
1214 |
If the specified key object is not found in the array, a copy of the
|
|
|
1215 |
key object along with a copy of the value object are added to the array
|
|
|
1216 |
and KErrNone is returned.
|
|
|
1217 |
If the specified key object is found in the array, the existing copies
|
|
|
1218 |
of both the key and value objects are replaced by the provided objects
|
|
|
1219 |
and KErrNone is returned.
|
|
|
1220 |
In both cases the objects are copied bitwise into the array.
|
|
|
1221 |
|
|
|
1222 |
@param aKey The key object of type K to add to the array.
|
|
|
1223 |
@param aValue The value object of type V to associate with aKey.
|
|
|
1224 |
@leave KErrNoMemory if memory could not be allocated to store the copies of aKey and aValue.
|
|
|
1225 |
*/
|
|
|
1226 |
inline void InsertL(const K& aKey, const V& aValue)
|
|
|
1227 |
{ RHashTableBase::ValueInsertL(&aKey, sizeof(K), &aValue, _FOFF(SFullElement,iV), sizeof(V)); }
|
|
|
1228 |
|
|
|
1229 |
|
|
|
1230 |
/**
|
|
|
1231 |
Remove a key-value pair from the array.
|
|
|
1232 |
|
|
|
1233 |
@param aKey The key to be removed.
|
|
|
1234 |
@return KErrNone if the key object and corresponding value object were
|
|
|
1235 |
removed successfully.
|
|
|
1236 |
KErrNotFound if the key object was not present in the array.
|
|
|
1237 |
*/
|
|
|
1238 |
inline TInt Remove(const K& aKey)
|
|
|
1239 |
{ return RHashTableBase::Remove(&aKey); }
|
|
|
1240 |
|
|
|
1241 |
|
|
|
1242 |
/**
|
|
|
1243 |
Query the number of key-value pairs in the array.
|
|
|
1244 |
|
|
|
1245 |
@return The number of key-value pairs currently in the array.
|
|
|
1246 |
*/
|
|
|
1247 |
inline TInt Count() const
|
|
|
1248 |
{ return RHashTableBase::Count(); }
|
|
|
1249 |
|
|
|
1250 |
|
|
|
1251 |
/**
|
|
|
1252 |
Expand the array to accommodate a specified number of key-value pairs.
|
|
|
1253 |
If the set already has enough space for the specified number of elements, no
|
|
|
1254 |
action is taken. Any elements already in the set are retained.
|
|
|
1255 |
|
|
|
1256 |
@param aCount The number of key-value pairs for which space should be allocated.
|
|
|
1257 |
@return KErrNone if the operation completed successfully.
|
|
|
1258 |
@return KErrNoMemory if sufficient memory could not be allocated.
|
|
|
1259 |
*/
|
|
|
1260 |
inline TInt Reserve(TInt aCount)
|
|
|
1261 |
{ return RHashTableBase::Reserve(aCount); }
|
|
|
1262 |
|
|
|
1263 |
|
|
|
1264 |
/**
|
|
|
1265 |
Expand the array to accommodate a specified number of key-value pairs.
|
|
|
1266 |
If the set already has enough space for the specified number of elements, no
|
|
|
1267 |
action is taken. Any elements already in the set are retained.
|
|
|
1268 |
|
|
|
1269 |
@param aCount The number of key-value pairs for which space should be allocated.
|
|
|
1270 |
@leave KErrNoMemory if sufficient memory could not be allocated.
|
|
|
1271 |
*/
|
|
|
1272 |
inline void ReserveL(TInt aCount)
|
|
|
1273 |
{ RHashTableBase::ReserveL(aCount); }
|
|
|
1274 |
|
|
|
1275 |
};
|
|
|
1276 |
|
|
|
1277 |
|
|
|
1278 |
/**
|
|
|
1279 |
@publishedAll
|
|
|
1280 |
@released
|
|
|
1281 |
|
|
|
1282 |
A templated class which allows iteration over the elements of a RHashMap<K,V>
|
|
|
1283 |
class.
|
|
|
1284 |
|
|
|
1285 |
The array being iterated over may not be modified while an iteration is in progress
|
|
|
1286 |
or the iteration operations may malfunction or panic.
|
|
|
1287 |
|
|
|
1288 |
@see RHashMap<K,V>
|
|
|
1289 |
*/
|
|
|
1290 |
template <class K, class V>
|
|
|
1291 |
class THashMapIter : public THashTableIterBase
|
|
|
1292 |
{
|
|
|
1293 |
private:
|
|
|
1294 |
|
|
|
1295 |
struct SFullElement
|
|
|
1296 |
{
|
|
|
1297 |
TUint32 iHash;
|
|
|
1298 |
K iK;
|
|
|
1299 |
V iV;
|
|
|
1300 |
};
|
|
|
1301 |
|
|
|
1302 |
public:
|
|
|
1303 |
|
|
|
1304 |
/**
|
|
|
1305 |
Construct an iterator over the specified associative array.
|
|
|
1306 |
The iterator starts at conceptual position one before the beginning of the list
|
|
|
1307 |
being iterated.
|
|
|
1308 |
|
|
|
1309 |
@param aMap The array to be iterated over.
|
|
|
1310 |
*/
|
|
|
1311 |
inline THashMapIter(const RHashMap<K,V>& aMap)
|
|
|
1312 |
: THashTableIterBase(aMap)
|
|
|
1313 |
{}
|
|
|
1314 |
|
|
|
1315 |
|
|
|
1316 |
/**
|
|
|
1317 |
Reset the iterator to its initial state.
|
|
|
1318 |
|
|
|
1319 |
@param aSet The set to be iterated over.
|
|
|
1320 |
*/
|
|
|
1321 |
inline void Reset()
|
|
|
1322 |
{ THashTableIterBase::Reset(); }
|
|
|
1323 |
|
|
|
1324 |
|
|
|
1325 |
/**
|
|
|
1326 |
Return the key corresponding to the current position of the iterator.
|
|
|
1327 |
|
|
|
1328 |
@return A pointer to the key object corresponding to the current position of the
|
|
|
1329 |
iterator.
|
|
|
1330 |
NULL if the iterator has just been constructed or reset, or if it has
|
|
|
1331 |
previously reached the end of an iteration.
|
|
|
1332 |
*/
|
|
|
1333 |
inline const K* CurrentKey() const
|
|
|
1334 |
{ return (const K*)THashTableIterBase::Current(_FOFF(SFullElement,iK)); }
|
|
|
1335 |
|
|
|
1336 |
|
|
|
1337 |
/**
|
|
|
1338 |
Steps the iterator to the next position and returns the corresponding key.
|
|
|
1339 |
|
|
|
1340 |
@return A pointer to the key object corresponding to the next position of the
|
|
|
1341 |
iterator.
|
|
|
1342 |
NULL if the iterator has exhausted all the available key-value pairs.
|
|
|
1343 |
*/
|
|
|
1344 |
inline const K* NextKey()
|
|
|
1345 |
{ return (const K*)THashTableIterBase::Next(_FOFF(SFullElement,iK)); }
|
|
|
1346 |
|
|
|
1347 |
|
|
|
1348 |
/**
|
|
|
1349 |
Return the value corresponding to the current position of the iterator.
|
|
|
1350 |
|
|
|
1351 |
@return A pointer to the value object corresponding to the current position of the
|
|
|
1352 |
iterator.
|
|
|
1353 |
NULL if the iterator has just been constructed or reset, or if it has
|
|
|
1354 |
previously reached the end of an iteration.
|
|
|
1355 |
*/
|
|
|
1356 |
inline V* CurrentValue()
|
|
|
1357 |
{ return (V*)THashTableIterBase::Current(_FOFF(SFullElement,iV)); }
|
|
|
1358 |
|
|
|
1359 |
|
|
|
1360 |
/**
|
|
|
1361 |
Steps the iterator to the next position and returns the corresponding value.
|
|
|
1362 |
|
|
|
1363 |
@return A pointer to the value object corresponding to the next position of the
|
|
|
1364 |
iterator.
|
|
|
1365 |
NULL if the iterator has exhausted all the available key-value pairs.
|
|
|
1366 |
*/
|
|
|
1367 |
inline const V* NextValue()
|
|
|
1368 |
{ return (const V*)THashTableIterBase::Next(_FOFF(SFullElement,iV)); }
|
|
|
1369 |
|
|
|
1370 |
|
|
|
1371 |
/**
|
|
|
1372 |
Removes the element at the current iterator position from the hash table.
|
|
|
1373 |
If the iterator does not currently point to a valid element, no action is taken.
|
|
|
1374 |
Note that the iterator position is not altered so it no longer points to a valid
|
|
|
1375 |
element following the Remove(). It is illegal to call either CurrentKey() or
|
|
|
1376 |
CurrentValue() on the iterator after calling Remove() - the only legal
|
|
|
1377 |
operations are Reset(), NextKey() or NextValue().
|
|
|
1378 |
|
|
|
1379 |
*/
|
|
|
1380 |
inline void RemoveCurrent()
|
|
|
1381 |
{ THashTableIterBase::RemoveCurrent(); }
|
|
|
1382 |
};
|
|
|
1383 |
|
|
|
1384 |
|
|
|
1385 |
|
|
|
1386 |
template <class K, class V> class TPtrHashMapIter;
|
|
|
1387 |
|
|
|
1388 |
/**
|
|
|
1389 |
@publishedAll
|
|
|
1390 |
@released
|
|
|
1391 |
|
|
|
1392 |
A templated class which implements an associative array with key type K and value type V,
|
|
|
1393 |
using a probe-sequence hash table. Neither the key nor value objects are copied into the
|
|
|
1394 |
table when they are added - only pointers are stored.
|
|
|
1395 |
|
|
|
1396 |
*/
|
|
|
1397 |
template <class K, class V>
|
|
|
1398 |
class RPtrHashMap : public RHashTableBase
|
|
|
1399 |
{
|
|
|
1400 |
private:
|
|
|
1401 |
friend class TPtrHashMapIter<K,V>;
|
|
|
1402 |
|
|
|
1403 |
struct SFullElement
|
|
|
1404 |
{
|
|
|
1405 |
TUint32 iHash;
|
|
|
1406 |
K* iK;
|
|
|
1407 |
V* iV;
|
|
|
1408 |
};
|
|
|
1409 |
public:
|
|
|
1410 |
|
|
|
1411 |
/**
|
|
|
1412 |
A class which allows iteration over the elements of a RPtrHashMap<K,V> class.
|
|
|
1413 |
|
|
|
1414 |
The array being iterated over may not be modified while an iteration is in progress
|
|
|
1415 |
or the iteration operations may malfunction or panic.
|
|
|
1416 |
|
|
|
1417 |
@see TPtrHashMapIter<K,V>
|
|
|
1418 |
*/
|
|
|
1419 |
typedef TPtrHashMapIter<K,V> TIter;
|
|
|
1420 |
|
|
|
1421 |
/**
|
|
|
1422 |
Construct an associative array of key-value pairs of type (K,V) using a
|
|
|
1423 |
specified hash function and identity relation.
|
|
|
1424 |
The array initially contains no key-value pairs.
|
|
|
1425 |
|
|
|
1426 |
@param aHash The hash function used to hash the key objects of type K.
|
|
|
1427 |
@param aIdentity The identity relation used to determine if two key objects
|
|
|
1428 |
of type K should be considered identical.
|
|
|
1429 |
*/
|
|
|
1430 |
inline RPtrHashMap(const THashFunction32<K>& aHash, const TIdentityRelation<K>& aIdentity)
|
|
|
1431 |
: RHashTableBase(aHash, aIdentity, sizeof(SFullElement), 0)
|
|
|
1432 |
{}
|
|
|
1433 |
|
|
|
1434 |
|
|
|
1435 |
/**
|
|
|
1436 |
Construct an associative array of key-value pairs of type (K,V) using a
|
|
|
1437 |
default hash function and identity relation.
|
|
|
1438 |
The array initially contains no key-value pairs.
|
|
|
1439 |
*/
|
|
|
1440 |
inline RPtrHashMap()
|
|
|
1441 |
: RHashTableBase(Defaults<K,EDefaultSpecifier_Normal>::Hash(), Defaults<K,EDefaultSpecifier_Normal>::Id(), sizeof(SFullElement), 0)
|
|
|
1442 |
{}
|
|
|
1443 |
|
|
|
1444 |
|
|
|
1445 |
/**
|
|
|
1446 |
Free all memory used by this array.
|
|
|
1447 |
Returns the array to the same state it had following construction.
|
|
|
1448 |
*/
|
|
|
1449 |
inline void Close()
|
|
|
1450 |
{ RHashTableBase::Close(); }
|
|
|
1451 |
|
|
|
1452 |
|
|
|
1453 |
/**
|
|
|
1454 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1455 |
corresponding value.
|
|
|
1456 |
|
|
|
1457 |
@param aKey The key object of type K to look up.
|
|
|
1458 |
@return A pointer to corresponding value object if the specified key
|
|
|
1459 |
object was found. The value object may not be modified via
|
|
|
1460 |
this pointer.
|
|
|
1461 |
NULL if the specified key object was not found.
|
|
|
1462 |
*/
|
|
|
1463 |
inline const V* Find(const K& aKey) const
|
|
|
1464 |
{ return (const V*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iV)); }
|
|
|
1465 |
|
|
|
1466 |
|
|
|
1467 |
/**
|
|
|
1468 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1469 |
corresponding value.
|
|
|
1470 |
|
|
|
1471 |
@param aKey The key object of type K to look up.
|
|
|
1472 |
@return A reference to corresponding value object if the specified key
|
|
|
1473 |
object was found. The value object may not be modified via
|
|
|
1474 |
this reference.
|
|
|
1475 |
@leave KErrNotFound if the specified key object was not found.
|
|
|
1476 |
*/
|
|
|
1477 |
inline const V& FindL(const K& aKey) const
|
|
|
1478 |
{ return *(const V*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iV)); }
|
|
|
1479 |
|
|
|
1480 |
|
|
|
1481 |
/**
|
|
|
1482 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1483 |
corresponding value.
|
|
|
1484 |
|
|
|
1485 |
@param aKey The key object of type K to look up.
|
|
|
1486 |
@return A pointer to corresponding value object if the specified key
|
|
|
1487 |
object was found. The value object may be modified via
|
|
|
1488 |
this pointer.
|
|
|
1489 |
NULL if the specified key object was not found.
|
|
|
1490 |
*/
|
|
|
1491 |
inline V* Find(const K& aKey)
|
|
|
1492 |
{ return (V*)RHashTableBase::Find(&aKey, -_FOFF(SFullElement,iV)); }
|
|
|
1493 |
|
|
|
1494 |
|
|
|
1495 |
/**
|
|
|
1496 |
Look up a specified key in the associative array and return a pointer to the
|
|
|
1497 |
corresponding value.
|
|
|
1498 |
|
|
|
1499 |
@param aKey The key object of type K to look up.
|
|
|
1500 |
@return A reference to corresponding value object if the specified key
|
|
|
1501 |
object was found. The value object may be modified via
|
|
|
1502 |
this reference.
|
|
|
1503 |
@leave KErrNotFound if the specified key object was not found.
|
|
|
1504 |
*/
|
|
|
1505 |
inline V& FindL(const K& aKey)
|
|
|
1506 |
{ return *(V*)RHashTableBase::FindL(&aKey, -_FOFF(SFullElement,iV)); }
|
|
|
1507 |
|
|
|
1508 |
|
|
|
1509 |
/**
|
|
|
1510 |
Insert a key-value pair into the array.
|
|
|
1511 |
|
|
|
1512 |
If the specified key object is not found in the array, a pointer to the
|
|
|
1513 |
key object along with a pointer to the value object are added to the array
|
|
|
1514 |
and KErrNone is returned.
|
|
|
1515 |
If the specified key object is found in the array, the existing pointers
|
|
|
1516 |
to both the key and value objects are replaced by the provided pointers
|
|
|
1517 |
and KErrNone is returned.
|
|
|
1518 |
In both cases only pointers are stored in the array - the objects themselves
|
|
|
1519 |
are not copied.
|
|
|
1520 |
|
|
|
1521 |
@param aKey A pointer to the key object of type K to add to the array.
|
|
|
1522 |
@param aValue A pointer to the value object of type V to associate with aKey.
|
|
|
1523 |
@return KErrNone if the key-value pair was added successfully.
|
|
|
1524 |
KErrNoMemory if memory could not be allocated to store
|
|
|
1525 |
the pointers aKey and aValue.
|
|
|
1526 |
*/
|
|
|
1527 |
inline TInt Insert(const K* aKey, const V* aValue)
|
|
|
1528 |
{ return RHashTableBase::PtrInsert(aKey, aValue); }
|
|
|
1529 |
|
|
|
1530 |
|
|
|
1531 |
/**
|
|
|
1532 |
Insert a key-value pair into the array.
|
|
|
1533 |
|
|
|
1534 |
If the specified key object is not found in the array, a pointer to the
|
|
|
1535 |
key object along with a pointer to the value object are added to the array
|
|
|
1536 |
and KErrNone is returned.
|
|
|
1537 |
If the specified key object is found in the array, the existing pointers
|
|
|
1538 |
to both the key and value objects are replaced by the provided pointers
|
|
|
1539 |
and KErrNone is returned.
|
|
|
1540 |
In both cases only pointers are stored in the array - the objects themselves
|
|
|
1541 |
are not copied.
|
|
|
1542 |
|
|
|
1543 |
@param aKey A pointer to the key object of type K to add to the array.
|
|
|
1544 |
@param aValue A pointer to the value object of type V to associate with aKey.
|
|
|
1545 |
@leave KErrNoMemory if memory could not be allocated to store the pointers aKey and aValue.
|
|
|
1546 |
*/
|
|
|
1547 |
inline void InsertL(const K* aKey, const V* aValue)
|
|
|
1548 |
{ RHashTableBase::PtrInsertL(aKey, aValue); }
|
|
|
1549 |
|
|
|
1550 |
|
|
|
1551 |
/**
|
|
|
1552 |
Remove a key-value pair from the array.
|
|
|
1553 |
|
|
|
1554 |
@param aKey A pointer to the key to be removed.
|
|
|
1555 |
@return KErrNone if the pointers to the key object and corresponding
|
|
|
1556 |
value object were removed successfully.
|
|
|
1557 |
KErrNotFound if the key object was not present in the array.
|
|
|
1558 |
*/
|
|
|
1559 |
inline TInt Remove(const K* aKey)
|
|
|
1560 |
{ return RHashTableBase::Remove(aKey); }
|
|
|
1561 |
|
|
|
1562 |
|
|
|
1563 |
/**
|
|
|
1564 |
Query the number of key-value pairs in the array.
|
|
|
1565 |
|
|
|
1566 |
@return The number of key-value pairs currently in the array.
|
|
|
1567 |
*/
|
|
|
1568 |
inline TInt Count() const
|
|
|
1569 |
{ return RHashTableBase::Count(); }
|
|
|
1570 |
|
|
|
1571 |
|
|
|
1572 |
/**
|
|
|
1573 |
Expand the array to accommodate a specified number of key-value pairs.
|
|
|
1574 |
If the set already has enough space for the specified number of elements, no
|
|
|
1575 |
action is taken. Any elements already in the set are retained.
|
|
|
1576 |
|
|
|
1577 |
@param aCount The number of key-value pairs for which space should be allocated.
|
|
|
1578 |
@return KErrNone if the operation completed successfully.
|
|
|
1579 |
@return KErrNoMemory if sufficient memory could not be allocated.
|
|
|
1580 |
*/
|
|
|
1581 |
inline TInt Reserve(TInt aCount)
|
|
|
1582 |
{ return RHashTableBase::Reserve(aCount); }
|
|
|
1583 |
|
|
|
1584 |
|
|
|
1585 |
/**
|
|
|
1586 |
Expand the array to accommodate a specified number of key-value pairs.
|
|
|
1587 |
If the set already has enough space for the specified number of elements, no
|
|
|
1588 |
action is taken. Any elements already in the set are retained.
|
|
|
1589 |
|
|
|
1590 |
@param aCount The number of key-value pairs for which space should be allocated.
|
|
|
1591 |
@leave KErrNoMemory if sufficient memory could not be allocated.
|
|
|
1592 |
*/
|
|
|
1593 |
inline void ReserveL(TInt aCount)
|
|
|
1594 |
{ RHashTableBase::ReserveL(aCount); }
|
|
|
1595 |
|
|
|
1596 |
|
|
|
1597 |
void ResetAndDestroy();
|
|
|
1598 |
};
|
|
|
1599 |
|
|
|
1600 |
|
|
|
1601 |
/**
|
|
|
1602 |
@publishedAll
|
|
|
1603 |
@released
|
|
|
1604 |
|
|
|
1605 |
A templated class which allows iteration over the elements of a RPtrHashMap<K,V>
|
|
|
1606 |
class.
|
|
|
1607 |
|
|
|
1608 |
The array being iterated over may not be modified while an iteration is in progress
|
|
|
1609 |
or the iteration operations may malfunction or panic.
|
|
|
1610 |
|
|
|
1611 |
@see RPtrHashMap<K,V>
|
|
|
1612 |
*/
|
|
|
1613 |
template <class K, class V>
|
|
|
1614 |
class TPtrHashMapIter : public THashTableIterBase
|
|
|
1615 |
{
|
|
|
1616 |
private:
|
|
|
1617 |
|
|
|
1618 |
struct SFullElement
|
|
|
1619 |
{
|
|
|
1620 |
TUint32 iHash;
|
|
|
1621 |
K* iK;
|
|
|
1622 |
V* iV;
|
|
|
1623 |
};
|
|
|
1624 |
public:
|
|
|
1625 |
|
|
|
1626 |
/**
|
|
|
1627 |
Construct an iterator over the specified associative array.
|
|
|
1628 |
The iterator starts at conceptual position one before the beginning of the list
|
|
|
1629 |
being iterated.
|
|
|
1630 |
|
|
|
1631 |
@param aMap The array to be iterated over.
|
|
|
1632 |
*/
|
|
|
1633 |
inline TPtrHashMapIter(const RPtrHashMap<K,V>& aMap)
|
|
|
1634 |
: THashTableIterBase(aMap)
|
|
|
1635 |
{}
|
|
|
1636 |
|
|
|
1637 |
|
|
|
1638 |
/**
|
|
|
1639 |
Reset the iterator to its initial state.
|
|
|
1640 |
|
|
|
1641 |
@param aSet The set to be iterated over.
|
|
|
1642 |
*/
|
|
|
1643 |
inline void Reset()
|
|
|
1644 |
{ THashTableIterBase::Reset(); }
|
|
|
1645 |
|
|
|
1646 |
|
|
|
1647 |
/**
|
|
|
1648 |
Return the key corresponding to the current position of the iterator.
|
|
|
1649 |
|
|
|
1650 |
@return A pointer to the key object corresponding to the current position of the
|
|
|
1651 |
iterator.
|
|
|
1652 |
NULL if the iterator has just been constructed or reset, or if it has
|
|
|
1653 |
previously reached the end of an iteration.
|
|
|
1654 |
*/
|
|
|
1655 |
inline const K* CurrentKey() const
|
|
|
1656 |
{ return (const K*)THashTableIterBase::Current(-_FOFF(SFullElement,iK)); }
|
|
|
1657 |
|
|
|
1658 |
|
|
|
1659 |
/**
|
|
|
1660 |
Steps the iterator to the next position and returns the corresponding key.
|
|
|
1661 |
|
|
|
1662 |
@return A pointer to the key object corresponding to the next position of the
|
|
|
1663 |
iterator.
|
|
|
1664 |
NULL if the iterator has exhausted all the available key-value pairs.
|
|
|
1665 |
*/
|
|
|
1666 |
inline const K* NextKey()
|
|
|
1667 |
{ return (const K*)THashTableIterBase::Next(-_FOFF(SFullElement,iK)); }
|
|
|
1668 |
|
|
|
1669 |
|
|
|
1670 |
/**
|
|
|
1671 |
Return the value corresponding to the current position of the iterator.
|
|
|
1672 |
|
|
|
1673 |
@return A pointer to the value object corresponding to the current position of the
|
|
|
1674 |
iterator.
|
|
|
1675 |
NULL if the iterator has just been constructed or reset, or if it has
|
|
|
1676 |
previously reached the end of an iteration.
|
|
|
1677 |
*/
|
|
|
1678 |
inline const V* CurrentValue() const
|
|
|
1679 |
{ return (const V*)THashTableIterBase::Current(-_FOFF(SFullElement,iV)); }
|
|
|
1680 |
|
|
|
1681 |
|
|
|
1682 |
/**
|
|
|
1683 |
Steps the iterator to the next position and returns the corresponding value.
|
|
|
1684 |
|
|
|
1685 |
@return A pointer to the value object corresponding to the next position of the
|
|
|
1686 |
iterator.
|
|
|
1687 |
NULL if the iterator has exhausted all the available key-value pairs.
|
|
|
1688 |
*/
|
|
|
1689 |
inline const V* NextValue()
|
|
|
1690 |
{ return (const V*)THashTableIterBase::Next(-_FOFF(SFullElement,iV)); }
|
|
|
1691 |
|
|
|
1692 |
|
|
|
1693 |
/**
|
|
|
1694 |
Removes the element at the current iterator position from the hash table.
|
|
|
1695 |
If the iterator does not currently point to a valid element, no action is taken.
|
|
|
1696 |
Note that the iterator position is not altered so it no longer points to a valid
|
|
|
1697 |
element following the Remove(). It is illegal to call either CurrentKey() or
|
|
|
1698 |
CurrentValue() on the iterator after calling Remove() - the only legal
|
|
|
1699 |
operations are Reset(), NextKey() or NextValue().
|
|
|
1700 |
|
|
|
1701 |
*/
|
|
|
1702 |
inline void RemoveCurrent()
|
|
|
1703 |
{ THashTableIterBase::RemoveCurrent(); }
|
|
|
1704 |
};
|
|
|
1705 |
|
|
|
1706 |
|
|
|
1707 |
|
|
|
1708 |
/**
|
|
|
1709 |
Deletes all the objects of type T to which pointers are stored in this set.
|
|
|
1710 |
Then frees all the memory used by the set and returns the set to the same state
|
|
|
1711 |
as immediately following construction.
|
|
|
1712 |
*/
|
|
|
1713 |
template <class T>
|
|
|
1714 |
void RPtrHashSet<T>::ResetAndDestroy()
|
|
|
1715 |
{
|
|
|
1716 |
TPtrHashSetIter<T> iter(*this);
|
|
|
1717 |
T* p;
|
|
|
1718 |
do {
|
|
|
1719 |
p = (T*)iter.Next();
|
|
|
1720 |
delete p;
|
|
|
1721 |
} while(p);
|
|
|
1722 |
Close();
|
|
|
1723 |
}
|
|
|
1724 |
|
|
|
1725 |
|
|
|
1726 |
/**
|
|
|
1727 |
Deletes all the key objects of type K and corresponding value objects of type V
|
|
|
1728 |
to which pointers are stored in this array.
|
|
|
1729 |
Then frees all the memory used by the array and returns the array to the same
|
|
|
1730 |
state as immediately following construction.
|
|
|
1731 |
*/
|
|
|
1732 |
template <class K, class V>
|
|
|
1733 |
void RPtrHashMap<K,V>::ResetAndDestroy()
|
|
|
1734 |
{
|
|
|
1735 |
TPtrHashMapIter<K,V> iter(*this);
|
|
|
1736 |
K* p;
|
|
|
1737 |
V* q;
|
|
|
1738 |
do {
|
|
|
1739 |
p = (K*)iter.NextKey();
|
|
|
1740 |
q = (V*)iter.CurrentValue();
|
|
|
1741 |
delete p;
|
|
|
1742 |
delete q;
|
|
|
1743 |
} while(p);
|
|
|
1744 |
Close();
|
|
|
1745 |
}
|
|
|
1746 |
|
|
|
1747 |
|
|
|
1748 |
#endif
|