|
1 // Copyright (c) 1998-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 "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 // |
|
15 |
|
16 #if !defined(__S32BTREE_H__) |
|
17 #define __S32BTREE_H__ |
|
18 #if !defined(__S32PAGE_H__) |
|
19 #include <s32page.h> |
|
20 #endif |
|
21 |
|
22 const TInt KMaxBtreeHeight=16; |
|
23 /** Maximum length for a B-tree key. */ |
|
24 const TInt KMaxBtreeKeyLength=255; |
|
25 // |
|
26 typedef TInt TBtreeHeight; |
|
27 /** Buffer to store the result of MBtreeKey::Between(). */ |
|
28 typedef TBuf8<KMaxBtreeKeyLength> TBtreePivot; |
|
29 // |
|
30 enum TBtreeMode {EBtreeSecure,EBtreeFast}; |
|
31 |
|
32 /** |
|
33 * @publishedAll |
|
34 * @released |
|
35 * Encapsulates the persistent parameters for a TBtree. |
|
36 */ |
|
37 class TBtreeToken |
|
38 { |
|
39 public: |
|
40 /** Provides a TBtreeToken initialisation flag. */ |
|
41 enum TEmpty {EEmpty}; |
|
42 public: |
|
43 /** Default constuctor. */ |
|
44 TBtreeToken() {} |
|
45 inline TBtreeToken(TEmpty); |
|
46 inline void Touch(); |
|
47 // |
|
48 inline TBool IsBroken() const; |
|
49 inline TBool IsIntact() const; |
|
50 inline TBool IsEmpty() const; |
|
51 // |
|
52 IMPORT_C void ExternalizeL(RWriteStream& aStream) const; |
|
53 IMPORT_C void InternalizeL(RReadStream& aStream); |
|
54 protected: |
|
55 IMPORT_C void Clear(); |
|
56 private: |
|
57 inline TBtreeToken(TPageRef aFirst,TPageRef aRoot,TBtreeHeight aHeight); |
|
58 private: |
|
59 TPageRef iFirst; |
|
60 TPageRef iRoot; |
|
61 TBtreeHeight iHeight; |
|
62 private: |
|
63 friend class TBtree; |
|
64 }; |
|
65 #define KEmptyBtreeToken TBtreeToken(TBtreeToken::EEmpty) |
|
66 |
|
67 /** |
|
68 * @publishedAll |
|
69 * @released |
|
70 */ |
|
71 class TBtreePath |
|
72 { |
|
73 public: |
|
74 inline TBtreePath(); |
|
75 inline TPageRef Node() const; |
|
76 inline TInt Entry() const; |
|
77 inline TBool IsLeaf() const; |
|
78 inline TBtreeHeight End() const; |
|
79 inline void SetEntry(TInt aEntry); |
|
80 void GotoRoot(TBtreeHeight aHeight,TPageRef aRoot); |
|
81 void Push(TPageRef aRef,TInt aEntry=0); |
|
82 inline void Pop(); |
|
83 private: |
|
84 TBtreeHeight iEnd; |
|
85 TPageRef iNodes[KMaxBtreeHeight]; |
|
86 TUint8 iEntries[KMaxBtreeHeight]; |
|
87 TUint8 iLasts[KMaxBtreeHeight]; |
|
88 }; |
|
89 |
|
90 /** |
|
91 * @publishedAll |
|
92 * @released |
|
93 * Identifies a position in a B-tree. |
|
94 |
|
95 The class has no public members. Clients use it by getting TBtreePos objects |
|
96 from some TBtree functions, and passing them into others. |
|
97 */ |
|
98 class TBtreePos |
|
99 { |
|
100 private: |
|
101 TBtreePath iPath; |
|
102 private: |
|
103 friend class TBtree; |
|
104 }; |
|
105 |
|
106 /** |
|
107 * @publishedAll |
|
108 * @released |
|
109 * An iterator for a B-tree. |
|
110 |
|
111 Functions that use a TBtreeMark are faster than those that use a TBtreePos, |
|
112 and can be used with a broken B-tree. |
|
113 |
|
114 The class has no public members. Clients use it by getting TBtreeMark objects |
|
115 from some TBtree functions, and passing them into others. |
|
116 */ |
|
117 class TBtreeMark |
|
118 { |
|
119 private: |
|
120 TPageRef iLeaf; |
|
121 TPageRef iLink; |
|
122 TUint8 iEntry; |
|
123 TUint8 iLast; |
|
124 private: |
|
125 friend class TBtree; |
|
126 }; |
|
127 |
|
128 /** |
|
129 * @publishedAll |
|
130 * @released |
|
131 * Interface for ordering and creating keys for entries in a B-tree. |
|
132 |
|
133 Derived classes implement this interface for particular types of key. |
|
134 */ |
|
135 class MBtreeKey |
|
136 { |
|
137 public: |
|
138 virtual IMPORT_C const TAny* Key(const TAny* anEntry) const; |
|
139 |
|
140 /** Orders two keys. |
|
141 |
|
142 @param aLeft Pointer to first key |
|
143 @param aRight Pointer to second key |
|
144 @return Positive, if the first key is after the second key; negative, if |
|
145 the first key is before the second key; zero, if the keys are equal */ |
|
146 virtual TInt Compare(const TAny* aLeft,const TAny* aRight) const=0; |
|
147 |
|
148 /** Gets the midpoint between two keys. |
|
149 |
|
150 The generated midpoint will be greater or equal to aLeft (by a comparison |
|
151 performed by the Compare() function), and less than aRight. |
|
152 |
|
153 @param aLeft First key |
|
154 @param aRight Second key |
|
155 @param aPivot On return, the midpoint between the two keys */ |
|
156 virtual void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const=0; |
|
157 }; |
|
158 |
|
159 class MBtreeNodeOrg; |
|
160 class MBtreeLeafOrg; |
|
161 class MBtreeIndexOrg; |
|
162 |
|
163 /** |
|
164 * @publishedAll |
|
165 * @released |
|
166 * Provides ordering of entries by key value in a B+-tree (balanced tree) |
|
167 structure. |
|
168 |
|
169 Entries and keys are handled as untyped TAny* parameters. You specify an entry |
|
170 in the tree to manipulate through a position (TBtreePos) variable. You can |
|
171 also use iterator functions, which take a TBtreeMark, to move through entries |
|
172 in the tree. The tree's settings can be persisted using a TBtreeToken. |
|
173 |
|
174 To use this class, you must provide a page pool, based on MPagePool, in which |
|
175 to store entries in the tree, and a key handler, based on MBtreeKey, to provide |
|
176 order and keys. |
|
177 |
|
178 @see MBtreeKey |
|
179 @see MPagePool |
|
180 @see TBtreeMark |
|
181 @see TBtreePos |
|
182 @see TBtreeToken |
|
183 */ |
|
184 class TBtree |
|
185 { |
|
186 public: |
|
187 /** Sets the condition for a successful match when calling TBtree::Find(). */ |
|
188 enum TFind { |
|
189 /** Find the first entry greater than or equal to the search target. */ |
|
190 EGreaterEqual, |
|
191 /** Find the first entry equal to the search target. */ |
|
192 EEqualTo, |
|
193 /** Find the last entry less than the search target. */ |
|
194 ELessThan, |
|
195 /** Find the first entry greater than the search target. */ |
|
196 EGreaterThan, |
|
197 /** Find the last entry less than or equal to the search target. */ |
|
198 ELessEqual}; |
|
199 public: |
|
200 IMPORT_C TBtree(TBtreeMode aMode); |
|
201 IMPORT_C TBtree(const TBtreeToken& aToken,TBtreeMode aMode); |
|
202 IMPORT_C void Connect(MPagePool* aPool,const MBtreeKey* aKey,const MBtreeLeafOrg* aLeafOrg,const MBtreeIndexOrg* anIndexOrg); |
|
203 IMPORT_C void Set(const TBtreeToken& aToken,TBtreeMode aMode); |
|
204 IMPORT_C TBtreeToken Token() const; |
|
205 // |
|
206 inline TBool IsDirty() const; |
|
207 inline void MarkCurrent(); |
|
208 inline void MarkDirty(); |
|
209 // |
|
210 inline TBool IsBroken() const; |
|
211 inline TBool IsIntact() const; |
|
212 inline void MarkBroken(); |
|
213 IMPORT_C TInt RepairL(); |
|
214 // |
|
215 inline TBool IsEmpty() const; |
|
216 IMPORT_C void ClearL(); |
|
217 // |
|
218 IMPORT_C TBool FirstL(TBtreePos& aPos) const; |
|
219 IMPORT_C TBool LastL(TBtreePos& aPos) const; |
|
220 IMPORT_C TBool NextL(TBtreePos& aPos) const; |
|
221 IMPORT_C TBool PreviousL(TBtreePos& aPos) const; |
|
222 // |
|
223 IMPORT_C TBool FindL(TBtreePos& aPos,const TAny* aKey,TFind aMode=EEqualTo) const; |
|
224 IMPORT_C TBool InsertL(TBtreePos& aPos,const TAny* anEntry,TInt aLength,TAllowDuplicates aDup=ENoDuplicates); |
|
225 IMPORT_C TBool DeleteL(const TAny* aKey); |
|
226 IMPORT_C void DeleteAtL(TBtreePos& aPos); |
|
227 IMPORT_C void ExtractAtL(const TBtreePos& aPos,TAny* anEntry,TInt aMaxLength) const; |
|
228 // |
|
229 IMPORT_C TBool ResetL(TBtreeMark& aMark) const; |
|
230 IMPORT_C TBool NextL(TBtreeMark& aMark) const; |
|
231 IMPORT_C void ExtractAtL(const TBtreeMark& aMark,TAny* anEntry,TInt aMaxLength) const; |
|
232 private: |
|
233 TBool AscendAtLastL(TBtreePath& aPath) const; |
|
234 TBool AscendAtFirstL(TBtreePath& aPath) const; |
|
235 void DescendFirstL(TBtreePath& aPath) const; |
|
236 void DescendLastL(TBtreePath& aPath) const; |
|
237 // |
|
238 TBool SearchL(TBtreePath& aPath,const TAny* aKey,TBool aAfter=EFalse) const; |
|
239 void NewPivot(const TAny* aLeftNode,const TAny* aRightNode,TBtreePivot& aPivot) const; |
|
240 void ReplacePivotL(TBtreePath& aPath,TAny* aNode,TBtreePivot& aPivot); |
|
241 void InsertAtL(TBtreePath& aPath,const TDesC8& anEntry); |
|
242 void InsertAtL(TBtreePath& aPath,TBtreePivot& aPivot,TPageRef aChild); |
|
243 TBool InsertAtL(TBtreePath& aPath,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPivot,TPageRef& aPromote); |
|
244 void DeleteAtL(TBtreePath& aPath); |
|
245 void DeleteIndexSetL(); |
|
246 void DeleteIndexNodesL(TBtreePath& aPath,TBool aLeadingEdge); |
|
247 // |
|
248 void NewTreeL(); |
|
249 void NewRootL(); |
|
250 // |
|
251 void BeginUpdateL(); |
|
252 void EndUpdate(); |
|
253 inline void MarkIntact(); |
|
254 void CheckIntactL() const; |
|
255 // |
|
256 inline TBool IsRoot(const TBtreePath& aPath) const; |
|
257 inline const MBtreeNodeOrg* NodeOrg(TBool aLeaf) const; |
|
258 void GotoRoot(TBtreePath& aPath) const; |
|
259 // |
|
260 TAny* GetNodeL(const TBtreePath& aPath) const; |
|
261 void PutNode(TAny* aNode,TBool aLeaf) const; |
|
262 // |
|
263 TInt LastEntryL(const TBtreePath& aPath) const; |
|
264 TPageRef ChildNodeL(const TBtreePath& aPath) const; |
|
265 TPageRef LastChildNodeL(TBtreePath& aPath) const; |
|
266 TPageRef ChildNodeL(TBtreePath& aPath,TInt aChild) const; |
|
267 private: |
|
268 enum {ESecure=EBtreeSecure,EFast=EBtreeFast,EBroken=0x40000000,EDirty=0x80000000}; |
|
269 private: |
|
270 MPagePool* iPages; |
|
271 const MBtreeKey* iKey; |
|
272 const MBtreeLeafOrg* iLeafOrg; |
|
273 const MBtreeIndexOrg* iIndexOrg; |
|
274 TPageRef iFirst; |
|
275 TPageRef iRoot; |
|
276 TBtreeHeight iHeight; |
|
277 TInt iStatus; |
|
278 }; |
|
279 |
|
280 /** |
|
281 * @publishedAll |
|
282 * @released |
|
283 */ |
|
284 class MBtreeNodeOrg |
|
285 { |
|
286 public: |
|
287 virtual IMPORT_C void Init(TAny* aNode) const; |
|
288 virtual TInt LastEntry(const TAny* aNode) const=0; |
|
289 virtual TPtrC8 Entry(const TAny* aNode,TInt aPos) const=0; |
|
290 virtual const TAny* EntryPtr(const TAny* aNode,TInt aPos) const=0; |
|
291 virtual TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const=0; |
|
292 virtual TBool Delete(TAny* aNode,TInt aPos) const=0; |
|
293 }; |
|
294 |
|
295 /** |
|
296 * @publishedAll |
|
297 * @released |
|
298 */ |
|
299 class MBtreeLeafOrg : public MBtreeNodeOrg |
|
300 { |
|
301 public: |
|
302 IMPORT_C TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const; |
|
303 virtual TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry) const=0; |
|
304 virtual IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const; |
|
305 virtual void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry) const=0; |
|
306 virtual TBool Redistribute(TAny* aLeftNode,TAny* aRightNode) const=0; |
|
307 virtual void Concatenate(TAny* aLeftNode,const TAny* aRightNode) const=0; |
|
308 virtual TPageRef LinkNode(const TAny* aNode) const=0; |
|
309 virtual void SetLinkNode(TAny* aNode,TPageRef aNextNode) const=0; |
|
310 }; |
|
311 |
|
312 /** |
|
313 * @publishedAll |
|
314 * @released |
|
315 */ |
|
316 class MBtreeIndexOrg : public MBtreeNodeOrg |
|
317 { |
|
318 public: |
|
319 IMPORT_C TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const; |
|
320 virtual TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const=0; |
|
321 virtual IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const; |
|
322 virtual void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const=0; |
|
323 virtual IMPORT_C TBool Update(TAny* aNode,TInt aPos,const TDesC8& anEntry) const; |
|
324 virtual TBool Redistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const=0; |
|
325 virtual void Concatenate(TAny* aLeftNode,const TAny* aRightNode,const TDesC8& aPivot) const=0; |
|
326 virtual void MakeRoot(TAny* aNode,TPageRef aChild) const=0; |
|
327 virtual TPageRef ChildNode(const TAny* aNode,TInt aPos) const=0; |
|
328 }; |
|
329 |
|
330 /** |
|
331 * @publishedAll |
|
332 * @released |
|
333 */ |
|
334 class TBtreeInlineLeafOrg : public MBtreeLeafOrg |
|
335 { |
|
336 public: |
|
337 IMPORT_C TBtreeInlineLeafOrg(); |
|
338 IMPORT_C void SetEntrySize(TInt aSize); |
|
339 // |
|
340 IMPORT_C TInt LastEntry(const TAny* aNode) const; |
|
341 IMPORT_C TPtrC8 Entry(const TAny* aNode,TInt aPos) const; |
|
342 IMPORT_C const TAny* EntryPtr(const TAny* aNode,TInt aPos) const; |
|
343 IMPORT_C TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry) const; |
|
344 IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const; |
|
345 IMPORT_C void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry) const; |
|
346 IMPORT_C TBool Delete(TAny* aNode,TInt aPos) const; |
|
347 IMPORT_C TBool Redistribute(TAny* aLeftNode,TAny* aRightNode) const; |
|
348 IMPORT_C void Concatenate(TAny* aLeftNode,const TAny* aRightNode) const; |
|
349 IMPORT_C TPageRef LinkNode(const TAny* aNode) const; |
|
350 IMPORT_C void SetLinkNode(TAny* aNode,TPageRef aNextNode) const; |
|
351 private: |
|
352 TAny* DoRedistribute(TAny* aLeftNode,TAny* aRightNode,TInt aInsertPos=-1) const; |
|
353 struct SHeader |
|
354 { |
|
355 TInt32 iCount; |
|
356 TPageRef iLink; |
|
357 }; |
|
358 struct SNode |
|
359 { |
|
360 SHeader iHead; |
|
361 TUint8 iEntries[KPoolPageSize-sizeof(SHeader)]; |
|
362 }; |
|
363 private: |
|
364 inline static const SNode* Node(const TAny* aNode); |
|
365 inline static SNode* Node(TAny* aNode); |
|
366 inline const TUint8* Entry(const SNode* aNode,TInt anEntry) const; |
|
367 inline TUint8* Entry(SNode* aNode,TInt anEntry) const; |
|
368 private: |
|
369 TInt iEntrySize; |
|
370 TInt iMaxEntries; |
|
371 }; |
|
372 |
|
373 /** |
|
374 * @publishedAll |
|
375 * @released |
|
376 */ |
|
377 class TBtreeInlineIndexOrg : public MBtreeIndexOrg |
|
378 { |
|
379 public: |
|
380 IMPORT_C TBtreeInlineIndexOrg(); |
|
381 IMPORT_C void SetEntrySize(TInt aSize); |
|
382 // |
|
383 IMPORT_C TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const; |
|
384 IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const; |
|
385 IMPORT_C void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const; |
|
386 IMPORT_C TBool Update(TAny* aNode,TInt aPos,const TDesC8& anEntry) const; |
|
387 IMPORT_C TBool Delete(TAny* aNode,TInt aPos) const; |
|
388 IMPORT_C TBool Redistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const; |
|
389 IMPORT_C void Concatenate(TAny* aLeftNode,const TAny* aRightNode,const TDesC8& aPivot) const; |
|
390 |
|
391 IMPORT_C void MakeRoot(TAny* aNode,TPageRef aChild) const; |
|
392 IMPORT_C TInt LastEntry(const TAny* aNode) const; |
|
393 IMPORT_C TPtrC8 Entry(const TAny* aNode,TInt aPos) const; |
|
394 IMPORT_C const TAny* EntryPtr(const TAny* aNode,TInt aPos) const; |
|
395 IMPORT_C TPageRef ChildNode(const TAny* aNode,TInt aPos) const; |
|
396 private: |
|
397 struct SEntry |
|
398 { |
|
399 TPageRef iChild; |
|
400 TUint8 iKey[4]; // at least four bytes of key |
|
401 }; |
|
402 struct SHeader |
|
403 { |
|
404 TInt32 iCount; |
|
405 }; |
|
406 struct SNode |
|
407 { |
|
408 SHeader iHead; |
|
409 TUint8 iEntries[KPoolPageSize-sizeof(SHeader)]; |
|
410 }; |
|
411 SNode* DoRedistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot,TInt aInsertPos=-1) const; |
|
412 private: |
|
413 inline static const SNode* Node(const TAny* aNode); |
|
414 inline static SNode* Node(TAny* aNode); |
|
415 inline const SEntry* Entry(const SNode* aNode,TInt anEntry) const; |
|
416 inline SEntry* Entry(SNode* aNode,TInt anEntry) const; |
|
417 inline TInt KeySize() const; |
|
418 private: |
|
419 TInt iEntrySize; |
|
420 TInt iMaxEntries; |
|
421 }; |
|
422 |
|
423 /** |
|
424 * @publishedAll |
|
425 * @released |
|
426 */ |
|
427 class TBtreeKey : public MBtreeKey |
|
428 { |
|
429 public: |
|
430 IMPORT_C TBtreeKey(); |
|
431 IMPORT_C TBtreeKey(TInt aLength); |
|
432 IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpText aType); |
|
433 IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpText aType,TInt aLength); |
|
434 IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpNumeric aType); |
|
435 // |
|
436 IMPORT_C const TAny* Key(const TAny* anEntry) const; |
|
437 IMPORT_C TInt Compare(const TAny* aLeft,const TAny* aRight) const; |
|
438 IMPORT_C void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const; |
|
439 protected: |
|
440 TInt iKeyOffset; |
|
441 TInt iCmpType; |
|
442 TInt iKeyLength; |
|
443 }; |
|
444 |
|
445 /** |
|
446 * @publishedAll |
|
447 * @released |
|
448 * Base class for TBtreeFix, which provides a B-tree for fixed sized entries. |
|
449 */ |
|
450 class TBtreeFixBase : public TBtree |
|
451 { |
|
452 public: |
|
453 IMPORT_C void Connect(MPagePool* aPool,const MBtreeKey* aKey); |
|
454 IMPORT_C TBool InsertL(TBtreePos& aPos,const TAny* anEntry,TAllowDuplicates aDup=ENoDuplicates); |
|
455 IMPORT_C void ExtractAtL(const TBtreePos& aPos,TAny* anEntry) const; |
|
456 IMPORT_C void ExtractAtL(const TBtreeMark& aMark,TAny* anEntry) const; |
|
457 protected: |
|
458 IMPORT_C TBtreeFixBase(TBtreeMode aMode,TInt anEntrySize,TInt aKeySize); |
|
459 IMPORT_C TBtreeFixBase(const TBtreeToken& aToken,TBtreeMode aMode,TInt anEntrySize,TInt aKeySize); |
|
460 private: |
|
461 TInt iEntrySize; |
|
462 TBtreeInlineLeafOrg iLeafOrgFix; |
|
463 TBtreeInlineIndexOrg iIndexOrgFix; |
|
464 }; |
|
465 |
|
466 /** |
|
467 * @publishedAll |
|
468 * @released |
|
469 * A B-tree for fixed-sized keys and entries. |
|
470 |
|
471 Entry is the type of entry to store. Key defines how items should be ordered: |
|
472 there must be a member of this type in the Entry class. |
|
473 */ |
|
474 template <class Entry,class Key> |
|
475 class TBtreeFix : public TBtreeFixBase |
|
476 { |
|
477 public: |
|
478 inline TBtreeFix(TBtreeMode aMode); |
|
479 inline TBtreeFix(const TBtreeToken& aToken,TBtreeMode aMode); |
|
480 // |
|
481 inline TBool FindL(TBtreePos& aPos,const Key& aKey,TFind aMode=EEqualTo) const; |
|
482 inline TBool InsertL(TBtreePos& aPos,const Entry& anEntry,TAllowDuplicates aDup=ENoDuplicates); |
|
483 inline TBool DeleteL(const Key& aKey); |
|
484 // |
|
485 inline Entry AtL(const TBtreePos& aPos) const; |
|
486 inline Entry AtL(const TBtreeMark& aMark) const; |
|
487 inline void ExtractAtL(const TBtreePos& aPos,Entry& anEntry) const; |
|
488 inline void ExtractAtL(const TBtreeMark& aMark,Entry& anEntry) const; |
|
489 }; |
|
490 |
|
491 /** |
|
492 * @publishedAll |
|
493 * @released |
|
494 * A specialisation of the B-tree for untyped fixed sized items. |
|
495 */ |
|
496 TEMPLATE_SPECIALIZATION class TBtreeFix<TAny,TAny> : public TBtreeFixBase |
|
497 { |
|
498 public: |
|
499 inline TBtreeFix(TBtreeMode aMode,TInt anEntrySize,TInt aKeySize); |
|
500 inline TBtreeFix(const TBtreeToken& aToken,TBtreeMode aMode,TInt anEntrySize,TInt aKeySize); |
|
501 }; |
|
502 |
|
503 #include <s32btree.inl> |
|
504 #endif |