1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/store/INC/S32BTREE.H Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,504 @@
1.4 +// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +//
1.18 +
1.19 +#if !defined(__S32BTREE_H__)
1.20 +#define __S32BTREE_H__
1.21 +#if !defined(__S32PAGE_H__)
1.22 +#include <s32page.h>
1.23 +#endif
1.24 +
1.25 +const TInt KMaxBtreeHeight=16;
1.26 +/** Maximum length for a B-tree key. */
1.27 +const TInt KMaxBtreeKeyLength=255;
1.28 +//
1.29 +typedef TInt TBtreeHeight;
1.30 +/** Buffer to store the result of MBtreeKey::Between(). */
1.31 +typedef TBuf8<KMaxBtreeKeyLength> TBtreePivot;
1.32 +//
1.33 +enum TBtreeMode {EBtreeSecure,EBtreeFast};
1.34 +
1.35 +/**
1.36 + * @publishedAll
1.37 + * @released
1.38 + * Encapsulates the persistent parameters for a TBtree.
1.39 +*/
1.40 +class TBtreeToken
1.41 + {
1.42 +public:
1.43 +/** Provides a TBtreeToken initialisation flag. */
1.44 + enum TEmpty {EEmpty};
1.45 +public:
1.46 + /** Default constuctor. */
1.47 + TBtreeToken() {}
1.48 + inline TBtreeToken(TEmpty);
1.49 + inline void Touch();
1.50 +//
1.51 + inline TBool IsBroken() const;
1.52 + inline TBool IsIntact() const;
1.53 + inline TBool IsEmpty() const;
1.54 +//
1.55 + IMPORT_C void ExternalizeL(RWriteStream& aStream) const;
1.56 + IMPORT_C void InternalizeL(RReadStream& aStream);
1.57 +protected:
1.58 + IMPORT_C void Clear();
1.59 +private:
1.60 + inline TBtreeToken(TPageRef aFirst,TPageRef aRoot,TBtreeHeight aHeight);
1.61 +private:
1.62 + TPageRef iFirst;
1.63 + TPageRef iRoot;
1.64 + TBtreeHeight iHeight;
1.65 +private:
1.66 + friend class TBtree;
1.67 + };
1.68 +#define KEmptyBtreeToken TBtreeToken(TBtreeToken::EEmpty)
1.69 +
1.70 +/**
1.71 + * @publishedAll
1.72 + * @released
1.73 + */
1.74 +class TBtreePath
1.75 + {
1.76 +public:
1.77 + inline TBtreePath();
1.78 + inline TPageRef Node() const;
1.79 + inline TInt Entry() const;
1.80 + inline TBool IsLeaf() const;
1.81 + inline TBtreeHeight End() const;
1.82 + inline void SetEntry(TInt aEntry);
1.83 + void GotoRoot(TBtreeHeight aHeight,TPageRef aRoot);
1.84 + void Push(TPageRef aRef,TInt aEntry=0);
1.85 + inline void Pop();
1.86 +private:
1.87 + TBtreeHeight iEnd;
1.88 + TPageRef iNodes[KMaxBtreeHeight];
1.89 + TUint8 iEntries[KMaxBtreeHeight];
1.90 + TUint8 iLasts[KMaxBtreeHeight];
1.91 + };
1.92 +
1.93 +/**
1.94 + * @publishedAll
1.95 + * @released
1.96 + * Identifies a position in a B-tree.
1.97 +
1.98 +The class has no public members. Clients use it by getting TBtreePos objects
1.99 +from some TBtree functions, and passing them into others.
1.100 +*/
1.101 +class TBtreePos
1.102 + {
1.103 +private:
1.104 + TBtreePath iPath;
1.105 +private:
1.106 + friend class TBtree;
1.107 + };
1.108 +
1.109 +/**
1.110 + * @publishedAll
1.111 + * @released
1.112 + * An iterator for a B-tree.
1.113 +
1.114 +Functions that use a TBtreeMark are faster than those that use a TBtreePos,
1.115 +and can be used with a broken B-tree.
1.116 +
1.117 +The class has no public members. Clients use it by getting TBtreeMark objects
1.118 +from some TBtree functions, and passing them into others.
1.119 +*/
1.120 +class TBtreeMark
1.121 + {
1.122 +private:
1.123 + TPageRef iLeaf;
1.124 + TPageRef iLink;
1.125 + TUint8 iEntry;
1.126 + TUint8 iLast;
1.127 +private:
1.128 + friend class TBtree;
1.129 + };
1.130 +
1.131 +/**
1.132 + * @publishedAll
1.133 + * @released
1.134 + * Interface for ordering and creating keys for entries in a B-tree.
1.135 +
1.136 +Derived classes implement this interface for particular types of key.
1.137 +*/
1.138 +class MBtreeKey
1.139 + {
1.140 +public:
1.141 + virtual IMPORT_C const TAny* Key(const TAny* anEntry) const;
1.142 +
1.143 + /** Orders two keys.
1.144 +
1.145 + @param aLeft Pointer to first key
1.146 + @param aRight Pointer to second key
1.147 + @return Positive, if the first key is after the second key; negative, if
1.148 + the first key is before the second key; zero, if the keys are equal */
1.149 + virtual TInt Compare(const TAny* aLeft,const TAny* aRight) const=0;
1.150 +
1.151 + /** Gets the midpoint between two keys.
1.152 +
1.153 + The generated midpoint will be greater or equal to aLeft (by a comparison
1.154 + performed by the Compare() function), and less than aRight.
1.155 +
1.156 + @param aLeft First key
1.157 + @param aRight Second key
1.158 + @param aPivot On return, the midpoint between the two keys */
1.159 + virtual void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const=0;
1.160 + };
1.161 +
1.162 +class MBtreeNodeOrg;
1.163 +class MBtreeLeafOrg;
1.164 +class MBtreeIndexOrg;
1.165 +
1.166 +/**
1.167 + * @publishedAll
1.168 + * @released
1.169 + * Provides ordering of entries by key value in a B+-tree (balanced tree)
1.170 +structure.
1.171 +
1.172 +Entries and keys are handled as untyped TAny* parameters. You specify an entry
1.173 +in the tree to manipulate through a position (TBtreePos) variable. You can
1.174 +also use iterator functions, which take a TBtreeMark, to move through entries
1.175 +in the tree. The tree's settings can be persisted using a TBtreeToken.
1.176 +
1.177 +To use this class, you must provide a page pool, based on MPagePool, in which
1.178 +to store entries in the tree, and a key handler, based on MBtreeKey, to provide
1.179 +order and keys.
1.180 +
1.181 +@see MBtreeKey
1.182 +@see MPagePool
1.183 +@see TBtreeMark
1.184 +@see TBtreePos
1.185 +@see TBtreeToken
1.186 +*/
1.187 +class TBtree
1.188 + {
1.189 +public:
1.190 +/** Sets the condition for a successful match when calling TBtree::Find(). */
1.191 + enum TFind {
1.192 + /** Find the first entry greater than or equal to the search target. */
1.193 + EGreaterEqual,
1.194 + /** Find the first entry equal to the search target. */
1.195 + EEqualTo,
1.196 + /** Find the last entry less than the search target. */
1.197 + ELessThan,
1.198 + /** Find the first entry greater than the search target. */
1.199 + EGreaterThan,
1.200 + /** Find the last entry less than or equal to the search target. */
1.201 + ELessEqual};
1.202 +public:
1.203 + IMPORT_C TBtree(TBtreeMode aMode);
1.204 + IMPORT_C TBtree(const TBtreeToken& aToken,TBtreeMode aMode);
1.205 + IMPORT_C void Connect(MPagePool* aPool,const MBtreeKey* aKey,const MBtreeLeafOrg* aLeafOrg,const MBtreeIndexOrg* anIndexOrg);
1.206 + IMPORT_C void Set(const TBtreeToken& aToken,TBtreeMode aMode);
1.207 + IMPORT_C TBtreeToken Token() const;
1.208 +//
1.209 + inline TBool IsDirty() const;
1.210 + inline void MarkCurrent();
1.211 + inline void MarkDirty();
1.212 +//
1.213 + inline TBool IsBroken() const;
1.214 + inline TBool IsIntact() const;
1.215 + inline void MarkBroken();
1.216 + IMPORT_C TInt RepairL();
1.217 +//
1.218 + inline TBool IsEmpty() const;
1.219 + IMPORT_C void ClearL();
1.220 +//
1.221 + IMPORT_C TBool FirstL(TBtreePos& aPos) const;
1.222 + IMPORT_C TBool LastL(TBtreePos& aPos) const;
1.223 + IMPORT_C TBool NextL(TBtreePos& aPos) const;
1.224 + IMPORT_C TBool PreviousL(TBtreePos& aPos) const;
1.225 +//
1.226 + IMPORT_C TBool FindL(TBtreePos& aPos,const TAny* aKey,TFind aMode=EEqualTo) const;
1.227 + IMPORT_C TBool InsertL(TBtreePos& aPos,const TAny* anEntry,TInt aLength,TAllowDuplicates aDup=ENoDuplicates);
1.228 + IMPORT_C TBool DeleteL(const TAny* aKey);
1.229 + IMPORT_C void DeleteAtL(TBtreePos& aPos);
1.230 + IMPORT_C void ExtractAtL(const TBtreePos& aPos,TAny* anEntry,TInt aMaxLength) const;
1.231 +//
1.232 + IMPORT_C TBool ResetL(TBtreeMark& aMark) const;
1.233 + IMPORT_C TBool NextL(TBtreeMark& aMark) const;
1.234 + IMPORT_C void ExtractAtL(const TBtreeMark& aMark,TAny* anEntry,TInt aMaxLength) const;
1.235 +private:
1.236 + TBool AscendAtLastL(TBtreePath& aPath) const;
1.237 + TBool AscendAtFirstL(TBtreePath& aPath) const;
1.238 + void DescendFirstL(TBtreePath& aPath) const;
1.239 + void DescendLastL(TBtreePath& aPath) const;
1.240 +//
1.241 + TBool SearchL(TBtreePath& aPath,const TAny* aKey,TBool aAfter=EFalse) const;
1.242 + void NewPivot(const TAny* aLeftNode,const TAny* aRightNode,TBtreePivot& aPivot) const;
1.243 + void ReplacePivotL(TBtreePath& aPath,TAny* aNode,TBtreePivot& aPivot);
1.244 + void InsertAtL(TBtreePath& aPath,const TDesC8& anEntry);
1.245 + void InsertAtL(TBtreePath& aPath,TBtreePivot& aPivot,TPageRef aChild);
1.246 + TBool InsertAtL(TBtreePath& aPath,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPivot,TPageRef& aPromote);
1.247 + void DeleteAtL(TBtreePath& aPath);
1.248 + void DeleteIndexSetL();
1.249 + void DeleteIndexNodesL(TBtreePath& aPath,TBool aLeadingEdge);
1.250 +//
1.251 + void NewTreeL();
1.252 + void NewRootL();
1.253 +//
1.254 + void BeginUpdateL();
1.255 + void EndUpdate();
1.256 + inline void MarkIntact();
1.257 + void CheckIntactL() const;
1.258 +//
1.259 + inline TBool IsRoot(const TBtreePath& aPath) const;
1.260 + inline const MBtreeNodeOrg* NodeOrg(TBool aLeaf) const;
1.261 + void GotoRoot(TBtreePath& aPath) const;
1.262 +//
1.263 + TAny* GetNodeL(const TBtreePath& aPath) const;
1.264 + void PutNode(TAny* aNode,TBool aLeaf) const;
1.265 +//
1.266 + TInt LastEntryL(const TBtreePath& aPath) const;
1.267 + TPageRef ChildNodeL(const TBtreePath& aPath) const;
1.268 + TPageRef LastChildNodeL(TBtreePath& aPath) const;
1.269 + TPageRef ChildNodeL(TBtreePath& aPath,TInt aChild) const;
1.270 +private:
1.271 + enum {ESecure=EBtreeSecure,EFast=EBtreeFast,EBroken=0x40000000,EDirty=0x80000000};
1.272 +private:
1.273 + MPagePool* iPages;
1.274 + const MBtreeKey* iKey;
1.275 + const MBtreeLeafOrg* iLeafOrg;
1.276 + const MBtreeIndexOrg* iIndexOrg;
1.277 + TPageRef iFirst;
1.278 + TPageRef iRoot;
1.279 + TBtreeHeight iHeight;
1.280 + TInt iStatus;
1.281 + };
1.282 +
1.283 +/**
1.284 + * @publishedAll
1.285 + * @released
1.286 + */
1.287 +class MBtreeNodeOrg
1.288 + {
1.289 +public:
1.290 + virtual IMPORT_C void Init(TAny* aNode) const;
1.291 + virtual TInt LastEntry(const TAny* aNode) const=0;
1.292 + virtual TPtrC8 Entry(const TAny* aNode,TInt aPos) const=0;
1.293 + virtual const TAny* EntryPtr(const TAny* aNode,TInt aPos) const=0;
1.294 + virtual TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const=0;
1.295 + virtual TBool Delete(TAny* aNode,TInt aPos) const=0;
1.296 + };
1.297 +
1.298 +/**
1.299 + * @publishedAll
1.300 + * @released
1.301 + */
1.302 +class MBtreeLeafOrg : public MBtreeNodeOrg
1.303 + {
1.304 +public:
1.305 + IMPORT_C TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const;
1.306 + virtual TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry) const=0;
1.307 + virtual IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const;
1.308 + virtual void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry) const=0;
1.309 + virtual TBool Redistribute(TAny* aLeftNode,TAny* aRightNode) const=0;
1.310 + virtual void Concatenate(TAny* aLeftNode,const TAny* aRightNode) const=0;
1.311 + virtual TPageRef LinkNode(const TAny* aNode) const=0;
1.312 + virtual void SetLinkNode(TAny* aNode,TPageRef aNextNode) const=0;
1.313 + };
1.314 +
1.315 +/**
1.316 + * @publishedAll
1.317 + * @released
1.318 + */
1.319 +class MBtreeIndexOrg : public MBtreeNodeOrg
1.320 + {
1.321 +public:
1.322 + IMPORT_C TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const;
1.323 + virtual TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const=0;
1.324 + virtual IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const;
1.325 + virtual void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const=0;
1.326 + virtual IMPORT_C TBool Update(TAny* aNode,TInt aPos,const TDesC8& anEntry) const;
1.327 + virtual TBool Redistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const=0;
1.328 + virtual void Concatenate(TAny* aLeftNode,const TAny* aRightNode,const TDesC8& aPivot) const=0;
1.329 + virtual void MakeRoot(TAny* aNode,TPageRef aChild) const=0;
1.330 + virtual TPageRef ChildNode(const TAny* aNode,TInt aPos) const=0;
1.331 + };
1.332 +
1.333 +/**
1.334 + * @publishedAll
1.335 + * @released
1.336 + */
1.337 +class TBtreeInlineLeafOrg : public MBtreeLeafOrg
1.338 + {
1.339 +public:
1.340 + IMPORT_C TBtreeInlineLeafOrg();
1.341 + IMPORT_C void SetEntrySize(TInt aSize);
1.342 +//
1.343 + IMPORT_C TInt LastEntry(const TAny* aNode) const;
1.344 + IMPORT_C TPtrC8 Entry(const TAny* aNode,TInt aPos) const;
1.345 + IMPORT_C const TAny* EntryPtr(const TAny* aNode,TInt aPos) const;
1.346 + IMPORT_C TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry) const;
1.347 + IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const;
1.348 + IMPORT_C void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry) const;
1.349 + IMPORT_C TBool Delete(TAny* aNode,TInt aPos) const;
1.350 + IMPORT_C TBool Redistribute(TAny* aLeftNode,TAny* aRightNode) const;
1.351 + IMPORT_C void Concatenate(TAny* aLeftNode,const TAny* aRightNode) const;
1.352 + IMPORT_C TPageRef LinkNode(const TAny* aNode) const;
1.353 + IMPORT_C void SetLinkNode(TAny* aNode,TPageRef aNextNode) const;
1.354 +private:
1.355 + TAny* DoRedistribute(TAny* aLeftNode,TAny* aRightNode,TInt aInsertPos=-1) const;
1.356 + struct SHeader
1.357 + {
1.358 + TInt32 iCount;
1.359 + TPageRef iLink;
1.360 + };
1.361 + struct SNode
1.362 + {
1.363 + SHeader iHead;
1.364 + TUint8 iEntries[KPoolPageSize-sizeof(SHeader)];
1.365 + };
1.366 +private:
1.367 + inline static const SNode* Node(const TAny* aNode);
1.368 + inline static SNode* Node(TAny* aNode);
1.369 + inline const TUint8* Entry(const SNode* aNode,TInt anEntry) const;
1.370 + inline TUint8* Entry(SNode* aNode,TInt anEntry) const;
1.371 +private:
1.372 + TInt iEntrySize;
1.373 + TInt iMaxEntries;
1.374 + };
1.375 +
1.376 +/**
1.377 + * @publishedAll
1.378 + * @released
1.379 + */
1.380 +class TBtreeInlineIndexOrg : public MBtreeIndexOrg
1.381 + {
1.382 +public:
1.383 + IMPORT_C TBtreeInlineIndexOrg();
1.384 + IMPORT_C void SetEntrySize(TInt aSize);
1.385 +//
1.386 + IMPORT_C TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const;
1.387 + IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const;
1.388 + IMPORT_C void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const;
1.389 + IMPORT_C TBool Update(TAny* aNode,TInt aPos,const TDesC8& anEntry) const;
1.390 + IMPORT_C TBool Delete(TAny* aNode,TInt aPos) const;
1.391 + IMPORT_C TBool Redistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const;
1.392 + IMPORT_C void Concatenate(TAny* aLeftNode,const TAny* aRightNode,const TDesC8& aPivot) const;
1.393 +
1.394 + IMPORT_C void MakeRoot(TAny* aNode,TPageRef aChild) const;
1.395 + IMPORT_C TInt LastEntry(const TAny* aNode) const;
1.396 + IMPORT_C TPtrC8 Entry(const TAny* aNode,TInt aPos) const;
1.397 + IMPORT_C const TAny* EntryPtr(const TAny* aNode,TInt aPos) const;
1.398 + IMPORT_C TPageRef ChildNode(const TAny* aNode,TInt aPos) const;
1.399 +private:
1.400 + struct SEntry
1.401 + {
1.402 + TPageRef iChild;
1.403 + TUint8 iKey[4]; // at least four bytes of key
1.404 + };
1.405 + struct SHeader
1.406 + {
1.407 + TInt32 iCount;
1.408 + };
1.409 + struct SNode
1.410 + {
1.411 + SHeader iHead;
1.412 + TUint8 iEntries[KPoolPageSize-sizeof(SHeader)];
1.413 + };
1.414 + SNode* DoRedistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot,TInt aInsertPos=-1) const;
1.415 +private:
1.416 + inline static const SNode* Node(const TAny* aNode);
1.417 + inline static SNode* Node(TAny* aNode);
1.418 + inline const SEntry* Entry(const SNode* aNode,TInt anEntry) const;
1.419 + inline SEntry* Entry(SNode* aNode,TInt anEntry) const;
1.420 + inline TInt KeySize() const;
1.421 +private:
1.422 + TInt iEntrySize;
1.423 + TInt iMaxEntries;
1.424 + };
1.425 +
1.426 +/**
1.427 + * @publishedAll
1.428 + * @released
1.429 + */
1.430 +class TBtreeKey : public MBtreeKey
1.431 + {
1.432 +public:
1.433 + IMPORT_C TBtreeKey();
1.434 + IMPORT_C TBtreeKey(TInt aLength);
1.435 + IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpText aType);
1.436 + IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpText aType,TInt aLength);
1.437 + IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpNumeric aType);
1.438 +//
1.439 + IMPORT_C const TAny* Key(const TAny* anEntry) const;
1.440 + IMPORT_C TInt Compare(const TAny* aLeft,const TAny* aRight) const;
1.441 + IMPORT_C void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const;
1.442 +protected:
1.443 + TInt iKeyOffset;
1.444 + TInt iCmpType;
1.445 + TInt iKeyLength;
1.446 + };
1.447 +
1.448 +/**
1.449 + * @publishedAll
1.450 + * @released
1.451 + * Base class for TBtreeFix, which provides a B-tree for fixed sized entries.
1.452 +*/
1.453 +class TBtreeFixBase : public TBtree
1.454 + {
1.455 +public:
1.456 + IMPORT_C void Connect(MPagePool* aPool,const MBtreeKey* aKey);
1.457 + IMPORT_C TBool InsertL(TBtreePos& aPos,const TAny* anEntry,TAllowDuplicates aDup=ENoDuplicates);
1.458 + IMPORT_C void ExtractAtL(const TBtreePos& aPos,TAny* anEntry) const;
1.459 + IMPORT_C void ExtractAtL(const TBtreeMark& aMark,TAny* anEntry) const;
1.460 +protected:
1.461 + IMPORT_C TBtreeFixBase(TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
1.462 + IMPORT_C TBtreeFixBase(const TBtreeToken& aToken,TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
1.463 +private:
1.464 + TInt iEntrySize;
1.465 + TBtreeInlineLeafOrg iLeafOrgFix;
1.466 + TBtreeInlineIndexOrg iIndexOrgFix;
1.467 + };
1.468 +
1.469 +/**
1.470 + * @publishedAll
1.471 + * @released
1.472 + * A B-tree for fixed-sized keys and entries.
1.473 +
1.474 +Entry is the type of entry to store. Key defines how items should be ordered:
1.475 +there must be a member of this type in the Entry class.
1.476 +*/
1.477 +template <class Entry,class Key>
1.478 +class TBtreeFix : public TBtreeFixBase
1.479 + {
1.480 +public:
1.481 + inline TBtreeFix(TBtreeMode aMode);
1.482 + inline TBtreeFix(const TBtreeToken& aToken,TBtreeMode aMode);
1.483 +//
1.484 + inline TBool FindL(TBtreePos& aPos,const Key& aKey,TFind aMode=EEqualTo) const;
1.485 + inline TBool InsertL(TBtreePos& aPos,const Entry& anEntry,TAllowDuplicates aDup=ENoDuplicates);
1.486 + inline TBool DeleteL(const Key& aKey);
1.487 +//
1.488 + inline Entry AtL(const TBtreePos& aPos) const;
1.489 + inline Entry AtL(const TBtreeMark& aMark) const;
1.490 + inline void ExtractAtL(const TBtreePos& aPos,Entry& anEntry) const;
1.491 + inline void ExtractAtL(const TBtreeMark& aMark,Entry& anEntry) const;
1.492 + };
1.493 +
1.494 +/**
1.495 + * @publishedAll
1.496 + * @released
1.497 + * A specialisation of the B-tree for untyped fixed sized items.
1.498 +*/
1.499 +TEMPLATE_SPECIALIZATION class TBtreeFix<TAny,TAny> : public TBtreeFixBase
1.500 + {
1.501 +public:
1.502 + inline TBtreeFix(TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
1.503 + inline TBtreeFix(const TBtreeToken& aToken,TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
1.504 + };
1.505 +
1.506 +#include <s32btree.inl>
1.507 +#endif