williamr@2: // Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
williamr@2: // All rights reserved.
williamr@2: // This component and the accompanying materials are made available
williamr@4: // under the terms of "Eclipse Public License v1.0"
williamr@2: // which accompanies this distribution, and is available
williamr@4: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
williamr@2: //
williamr@2: // Initial Contributors:
williamr@2: // Nokia Corporation - initial contribution.
williamr@2: //
williamr@2: // Contributors:
williamr@2: //
williamr@2: // Description:
williamr@2: //
williamr@2: 
williamr@2: #if !defined(__S32BTREE_H__)
williamr@2: #define __S32BTREE_H__
williamr@2: #if !defined(__S32PAGE_H__)
williamr@2: #include <s32page.h>
williamr@2: #endif
williamr@2: 
williamr@2: const TInt KMaxBtreeHeight=16;
williamr@2: /** Maximum length for a B-tree key. */
williamr@2: const TInt KMaxBtreeKeyLength=255;
williamr@2: //
williamr@2: typedef TInt TBtreeHeight;
williamr@2: /** Buffer to store the result of MBtreeKey::Between(). */
williamr@2: typedef TBuf8<KMaxBtreeKeyLength> TBtreePivot;
williamr@2: //
williamr@2: enum TBtreeMode {EBtreeSecure,EBtreeFast};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * Encapsulates the persistent parameters for a TBtree. 
williamr@2: */
williamr@2: class TBtreeToken
williamr@2: 	{
williamr@2: public:
williamr@2: /** Provides a TBtreeToken initialisation flag. */
williamr@2: 	enum TEmpty {EEmpty};
williamr@2: public:
williamr@2: 	/** Default constuctor. */
williamr@2: 	TBtreeToken() {}
williamr@2: 	inline TBtreeToken(TEmpty);
williamr@2: 	inline void Touch();
williamr@2: //
williamr@2: 	inline TBool IsBroken() const;
williamr@2: 	inline TBool IsIntact() const;
williamr@2: 	inline TBool IsEmpty() const;
williamr@2: //
williamr@2: 	IMPORT_C void ExternalizeL(RWriteStream& aStream) const;
williamr@2: 	IMPORT_C void InternalizeL(RReadStream& aStream);
williamr@2: protected:
williamr@2: 	IMPORT_C void Clear();
williamr@2: private:
williamr@2: 	inline TBtreeToken(TPageRef aFirst,TPageRef aRoot,TBtreeHeight aHeight);
williamr@2: private:
williamr@2: 	TPageRef iFirst;
williamr@2: 	TPageRef iRoot;
williamr@2: 	TBtreeHeight iHeight;
williamr@2: private:
williamr@2: 	friend class TBtree;
williamr@2: 	};
williamr@2: #define KEmptyBtreeToken TBtreeToken(TBtreeToken::EEmpty)
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class TBtreePath
williamr@2: 	{
williamr@2: public:
williamr@2: 	inline TBtreePath();
williamr@2: 	inline TPageRef Node() const;
williamr@2: 	inline TInt Entry() const;
williamr@2: 	inline TBool IsLeaf() const;
williamr@2: 	inline TBtreeHeight End() const;
williamr@2: 	inline void SetEntry(TInt aEntry);
williamr@2: 	void GotoRoot(TBtreeHeight aHeight,TPageRef aRoot);
williamr@2: 	void Push(TPageRef aRef,TInt aEntry=0);
williamr@2: 	inline void Pop();
williamr@2: private:
williamr@2: 	TBtreeHeight iEnd;
williamr@2: 	TPageRef iNodes[KMaxBtreeHeight];
williamr@2: 	TUint8 iEntries[KMaxBtreeHeight];
williamr@2: 	TUint8 iLasts[KMaxBtreeHeight];
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * Identifies a position in a B-tree.
williamr@2: 
williamr@2: The class has no public members. Clients use it by getting TBtreePos objects 
williamr@2: from some TBtree functions, and passing them into others.  
williamr@2: */
williamr@2: class TBtreePos
williamr@2: 	{
williamr@2: private:
williamr@2: 	TBtreePath iPath;
williamr@2: private:
williamr@2: 	friend class TBtree;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * An iterator for a B-tree.
williamr@2: 
williamr@2: Functions that use a TBtreeMark are faster than those that use a TBtreePos, 
williamr@2: and can be used with a broken B-tree. 
williamr@2: 
williamr@2: The class has no public members. Clients use it by getting TBtreeMark objects 
williamr@2: from some TBtree functions, and passing them into others. 
williamr@2: */
williamr@2: class TBtreeMark
williamr@2: 	{
williamr@2: private:
williamr@2: 	TPageRef iLeaf;
williamr@2: 	TPageRef iLink;
williamr@2: 	TUint8 iEntry;
williamr@2: 	TUint8 iLast;
williamr@2: private:
williamr@2: 	friend class TBtree;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * Interface for ordering and creating keys for entries in a B-tree.
williamr@2: 
williamr@2: Derived classes implement this interface for particular types of key. 
williamr@2: */
williamr@2: class MBtreeKey
williamr@2: 	{
williamr@2: public:
williamr@2: 	virtual IMPORT_C const TAny* Key(const TAny* anEntry) const;
williamr@2: 	
williamr@2: 	/** Orders two keys.
williamr@2: 	
williamr@2: 	@param aLeft Pointer to first key
williamr@2: 	@param aRight Pointer to second key
williamr@2: 	@return Positive, if the first key is after the second key; negative, if 
williamr@2: 	the first key is before the second key; zero, if the keys are equal */
williamr@2: 	virtual TInt Compare(const TAny* aLeft,const TAny* aRight) const=0;
williamr@2: 	
williamr@2: 	/** Gets the midpoint between two keys.
williamr@2: 	
williamr@2: 	The generated midpoint will be greater or equal to aLeft (by a comparison 
williamr@2: 	performed by the Compare() function), and less than aRight.
williamr@2: 	
williamr@2: 	@param aLeft First key
williamr@2: 	@param aRight Second key
williamr@2: 	@param aPivot On return, the midpoint between the two keys */
williamr@2: 	virtual void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const=0;
williamr@2: 	};
williamr@2: 
williamr@2: class MBtreeNodeOrg;
williamr@2: class MBtreeLeafOrg;
williamr@2: class MBtreeIndexOrg;
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * Provides ordering of entries by key value in a B+-tree (balanced tree) 
williamr@2: structure.
williamr@2: 
williamr@2: Entries and keys are handled as untyped TAny* parameters. You specify an entry 
williamr@2: in the tree to manipulate through a position (TBtreePos) variable. You can 
williamr@2: also use iterator functions, which take a TBtreeMark, to move through entries 
williamr@2: in the tree. The tree's settings can be persisted using a TBtreeToken.
williamr@2: 
williamr@2: To use this class, you must provide a page pool, based on MPagePool, in which 
williamr@2: to store entries in the tree, and a key handler, based on MBtreeKey, to provide 
williamr@2: order and keys.
williamr@2: 
williamr@2: @see MBtreeKey
williamr@2: @see MPagePool
williamr@2: @see TBtreeMark
williamr@2: @see TBtreePos
williamr@2: @see TBtreeToken 
williamr@2: */
williamr@2: class TBtree
williamr@2: 	{
williamr@2: public:
williamr@2: /** Sets the condition for a successful match when calling TBtree::Find(). */
williamr@2: 	enum TFind {
williamr@2: 		/** Find the first entry greater than or equal to the search target. */
williamr@2: 		EGreaterEqual,
williamr@2: 		/** Find the first entry equal to the search target. */
williamr@2: 		EEqualTo,
williamr@2: 		/** Find the last entry less than the search target. */
williamr@2: 		ELessThan,
williamr@2: 		/** Find the first entry greater than the search target. */
williamr@2: 		EGreaterThan,
williamr@2: 		/** Find the last entry less than or equal to the search target. */
williamr@2: 		ELessEqual};
williamr@2: public:
williamr@2: 	IMPORT_C TBtree(TBtreeMode aMode);
williamr@2: 	IMPORT_C TBtree(const TBtreeToken& aToken,TBtreeMode aMode);
williamr@2: 	IMPORT_C void Connect(MPagePool* aPool,const MBtreeKey* aKey,const MBtreeLeafOrg* aLeafOrg,const MBtreeIndexOrg* anIndexOrg);
williamr@2: 	IMPORT_C void Set(const TBtreeToken& aToken,TBtreeMode aMode);
williamr@2: 	IMPORT_C TBtreeToken Token() const;
williamr@2: //
williamr@2: 	inline TBool IsDirty() const;
williamr@2: 	inline void MarkCurrent();
williamr@2: 	inline void MarkDirty();
williamr@2: //
williamr@2: 	inline TBool IsBroken() const;
williamr@2: 	inline TBool IsIntact() const;
williamr@2: 	inline void MarkBroken();
williamr@2: 	IMPORT_C TInt RepairL();
williamr@2: //
williamr@2: 	inline TBool IsEmpty() const;
williamr@2: 	IMPORT_C void ClearL();
williamr@2: //
williamr@2: 	IMPORT_C TBool FirstL(TBtreePos& aPos) const;
williamr@2: 	IMPORT_C TBool LastL(TBtreePos& aPos) const;
williamr@2: 	IMPORT_C TBool NextL(TBtreePos& aPos) const;
williamr@2: 	IMPORT_C TBool PreviousL(TBtreePos& aPos) const;
williamr@2: //
williamr@2: 	IMPORT_C TBool FindL(TBtreePos& aPos,const TAny* aKey,TFind aMode=EEqualTo) const;
williamr@2: 	IMPORT_C TBool InsertL(TBtreePos& aPos,const TAny* anEntry,TInt aLength,TAllowDuplicates aDup=ENoDuplicates);
williamr@2: 	IMPORT_C TBool DeleteL(const TAny* aKey);
williamr@2: 	IMPORT_C void DeleteAtL(TBtreePos& aPos);
williamr@2: 	IMPORT_C void ExtractAtL(const TBtreePos& aPos,TAny* anEntry,TInt aMaxLength) const;
williamr@2: //
williamr@2: 	IMPORT_C TBool ResetL(TBtreeMark& aMark) const;
williamr@2: 	IMPORT_C TBool NextL(TBtreeMark& aMark) const;
williamr@2: 	IMPORT_C void ExtractAtL(const TBtreeMark& aMark,TAny* anEntry,TInt aMaxLength) const;
williamr@2: private:
williamr@2: 	TBool AscendAtLastL(TBtreePath& aPath) const;
williamr@2: 	TBool AscendAtFirstL(TBtreePath& aPath) const;
williamr@2: 	void DescendFirstL(TBtreePath& aPath) const;
williamr@2: 	void DescendLastL(TBtreePath& aPath) const;
williamr@2: //
williamr@2: 	TBool SearchL(TBtreePath& aPath,const TAny* aKey,TBool aAfter=EFalse) const;
williamr@2: 	void NewPivot(const TAny* aLeftNode,const TAny* aRightNode,TBtreePivot& aPivot) const;
williamr@2: 	void ReplacePivotL(TBtreePath& aPath,TAny* aNode,TBtreePivot& aPivot);
williamr@2: 	void InsertAtL(TBtreePath& aPath,const TDesC8& anEntry);
williamr@2: 	void InsertAtL(TBtreePath& aPath,TBtreePivot& aPivot,TPageRef aChild);
williamr@2: 	TBool InsertAtL(TBtreePath& aPath,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPivot,TPageRef& aPromote);
williamr@2: 	void DeleteAtL(TBtreePath& aPath);
williamr@2: 	void DeleteIndexSetL();
williamr@2: 	void DeleteIndexNodesL(TBtreePath& aPath,TBool aLeadingEdge);
williamr@2: //
williamr@2: 	void NewTreeL();
williamr@2: 	void NewRootL();
williamr@2: //
williamr@2: 	void BeginUpdateL();
williamr@2: 	void EndUpdate();
williamr@2: 	inline void MarkIntact();
williamr@2: 	void CheckIntactL() const;
williamr@2: //
williamr@2: 	inline TBool IsRoot(const TBtreePath& aPath) const;
williamr@2: 	inline const MBtreeNodeOrg* NodeOrg(TBool aLeaf) const;
williamr@2: 	void GotoRoot(TBtreePath& aPath) const;
williamr@2: //
williamr@2: 	TAny* GetNodeL(const TBtreePath& aPath) const;
williamr@2: 	void PutNode(TAny* aNode,TBool aLeaf) const;
williamr@2: //
williamr@2: 	TInt LastEntryL(const TBtreePath& aPath) const;
williamr@2: 	TPageRef ChildNodeL(const TBtreePath& aPath) const;
williamr@2: 	TPageRef LastChildNodeL(TBtreePath& aPath) const;
williamr@2: 	TPageRef ChildNodeL(TBtreePath& aPath,TInt aChild) const;
williamr@2: private:
williamr@2: 	enum {ESecure=EBtreeSecure,EFast=EBtreeFast,EBroken=0x40000000,EDirty=0x80000000};
williamr@2: private:
williamr@2: 	MPagePool* iPages;
williamr@2: 	const MBtreeKey* iKey;
williamr@2: 	const MBtreeLeafOrg* iLeafOrg;
williamr@2: 	const MBtreeIndexOrg* iIndexOrg;
williamr@2: 	TPageRef iFirst;
williamr@2: 	TPageRef iRoot;
williamr@2: 	TBtreeHeight iHeight;
williamr@2: 	TInt iStatus;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class MBtreeNodeOrg
williamr@2: 	{
williamr@2: public:
williamr@2: 	virtual IMPORT_C void Init(TAny* aNode) const;
williamr@2: 	virtual TInt LastEntry(const TAny* aNode) const=0;
williamr@2: 	virtual TPtrC8 Entry(const TAny* aNode,TInt aPos) const=0;
williamr@2: 	virtual const TAny* EntryPtr(const TAny* aNode,TInt aPos) const=0;
williamr@2: 	virtual TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const=0;
williamr@2: 	virtual TBool Delete(TAny* aNode,TInt aPos) const=0;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class MBtreeLeafOrg : public MBtreeNodeOrg
williamr@2: 	{
williamr@2: public:
williamr@2: 	IMPORT_C TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const;
williamr@2: 	virtual TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry) const=0;
williamr@2: 	virtual IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const;
williamr@2: 	virtual void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry) const=0;
williamr@2: 	virtual TBool Redistribute(TAny* aLeftNode,TAny* aRightNode) const=0;
williamr@2: 	virtual void Concatenate(TAny* aLeftNode,const TAny* aRightNode) const=0;
williamr@2: 	virtual TPageRef LinkNode(const TAny* aNode) const=0;
williamr@2: 	virtual void SetLinkNode(TAny* aNode,TPageRef aNextNode) const=0;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class MBtreeIndexOrg : public MBtreeNodeOrg
williamr@2: 	{
williamr@2: public:
williamr@2: 	IMPORT_C TBool Search(const TAny* aNode,const TAny* aKey,const MBtreeKey& aComp,TBool aLast,TInt& aPos) const;
williamr@2: 	virtual TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const=0;
williamr@2: 	virtual IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const;
williamr@2: 	virtual void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const=0;
williamr@2: 	virtual IMPORT_C TBool Update(TAny* aNode,TInt aPos,const TDesC8& anEntry) const;
williamr@2: 	virtual TBool Redistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const=0;
williamr@2: 	virtual void Concatenate(TAny* aLeftNode,const TAny* aRightNode,const TDesC8& aPivot) const=0;
williamr@2: 	virtual void MakeRoot(TAny* aNode,TPageRef aChild) const=0;
williamr@2: 	virtual TPageRef ChildNode(const TAny* aNode,TInt aPos) const=0;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class TBtreeInlineLeafOrg : public MBtreeLeafOrg
williamr@2: 	{
williamr@2: public:
williamr@2: 	IMPORT_C TBtreeInlineLeafOrg();
williamr@2: 	IMPORT_C void SetEntrySize(TInt aSize);
williamr@2: //
williamr@2: 	IMPORT_C TInt LastEntry(const TAny* aNode) const;
williamr@2: 	IMPORT_C TPtrC8 Entry(const TAny* aNode,TInt aPos) const;
williamr@2: 	IMPORT_C const TAny* EntryPtr(const TAny* aNode,TInt aPos) const;
williamr@2: 	IMPORT_C TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry) const;
williamr@2: 	IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry) const;
williamr@2: 	IMPORT_C void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry) const;
williamr@2: 	IMPORT_C TBool Delete(TAny* aNode,TInt aPos) const;
williamr@2: 	IMPORT_C TBool Redistribute(TAny* aLeftNode,TAny* aRightNode) const;
williamr@2: 	IMPORT_C void Concatenate(TAny* aLeftNode,const TAny* aRightNode) const;
williamr@2: 	IMPORT_C TPageRef LinkNode(const TAny* aNode) const;
williamr@2: 	IMPORT_C void SetLinkNode(TAny* aNode,TPageRef aNextNode) const;
williamr@2: private:
williamr@2: 	TAny* DoRedistribute(TAny* aLeftNode,TAny* aRightNode,TInt aInsertPos=-1) const;
williamr@2: 	struct SHeader
williamr@2: 		{
williamr@2: 		TInt32 iCount;
williamr@2: 		TPageRef iLink;
williamr@2: 		};
williamr@2: 	struct SNode
williamr@2: 		{
williamr@2: 		SHeader iHead;
williamr@2: 		TUint8 iEntries[KPoolPageSize-sizeof(SHeader)];
williamr@2: 		};
williamr@2: private:
williamr@2: 	inline static const SNode* Node(const TAny* aNode);
williamr@2: 	inline static SNode* Node(TAny* aNode);
williamr@2: 	inline const TUint8* Entry(const SNode* aNode,TInt anEntry) const;
williamr@2: 	inline TUint8* Entry(SNode* aNode,TInt anEntry) const;
williamr@2: private:
williamr@2: 	TInt iEntrySize;
williamr@2: 	TInt iMaxEntries;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class TBtreeInlineIndexOrg : public MBtreeIndexOrg
williamr@2: 	{
williamr@2: public:
williamr@2: 	IMPORT_C TBtreeInlineIndexOrg();
williamr@2: 	IMPORT_C void SetEntrySize(TInt aSize);
williamr@2: //
williamr@2: 	IMPORT_C TBool Insert(TAny* aNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild) const;
williamr@2: 	IMPORT_C TBool InsertOverflow(TAny* aLeftNode,TAny* aRightNode,TInt aPos,TBool aInsertOnLeft,const TDesC8& anEntry,TPageRef aChild,const TDesC8& aPivot,TBtreePivot& aNewPivot) const;
williamr@2: 	IMPORT_C void InsertSplit(TAny* aLeftNode,TAny* aRightNode,TInt aPos,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPromote) const;
williamr@2: 	IMPORT_C TBool Update(TAny* aNode,TInt aPos,const TDesC8& anEntry) const;
williamr@2: 	IMPORT_C TBool Delete(TAny* aNode,TInt aPos) const;
williamr@2: 	IMPORT_C TBool Redistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot) const;
williamr@2: 	IMPORT_C void Concatenate(TAny* aLeftNode,const TAny* aRightNode,const TDesC8& aPivot) const;
williamr@2: 
williamr@2: 	IMPORT_C void MakeRoot(TAny* aNode,TPageRef aChild) const;
williamr@2: 	IMPORT_C TInt LastEntry(const TAny* aNode) const;
williamr@2: 	IMPORT_C TPtrC8 Entry(const TAny* aNode,TInt aPos) const;
williamr@2: 	IMPORT_C const TAny* EntryPtr(const TAny* aNode,TInt aPos) const;
williamr@2: 	IMPORT_C TPageRef ChildNode(const TAny* aNode,TInt aPos) const;
williamr@2: private:
williamr@2: 	struct SEntry
williamr@2: 		{
williamr@2: 		TPageRef iChild;
williamr@2: 		TUint8 iKey[4]; // at least four bytes of key
williamr@2: 		};
williamr@2: 	struct SHeader
williamr@2: 		{
williamr@2: 		TInt32 iCount;
williamr@2: 		};
williamr@2: 	struct SNode
williamr@2: 		{
williamr@2: 		SHeader iHead;
williamr@2: 		TUint8 iEntries[KPoolPageSize-sizeof(SHeader)];
williamr@2: 		};
williamr@2: 	SNode* DoRedistribute(TAny* aLeftNode,TAny* aRightNode,const TDesC8& aPivot,TBtreePivot& aNewPivot,TInt aInsertPos=-1) const;
williamr@2: private:
williamr@2: 	inline static const SNode* Node(const TAny* aNode);
williamr@2: 	inline static SNode* Node(TAny* aNode);
williamr@2: 	inline const SEntry* Entry(const SNode* aNode,TInt anEntry) const;
williamr@2: 	inline SEntry* Entry(SNode* aNode,TInt anEntry) const;
williamr@2: 	inline TInt KeySize() const;
williamr@2: private:
williamr@2: 	TInt iEntrySize;
williamr@2: 	TInt iMaxEntries;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  */
williamr@2: class TBtreeKey : public MBtreeKey
williamr@2: 	{
williamr@2: public:
williamr@2: 	IMPORT_C TBtreeKey();
williamr@2: 	IMPORT_C TBtreeKey(TInt aLength);
williamr@2: 	IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpText aType);
williamr@2: 	IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpText aType,TInt aLength);
williamr@2: 	IMPORT_C TBtreeKey(TInt anOffset,TKeyCmpNumeric aType);
williamr@2: //
williamr@2: 	IMPORT_C const TAny* Key(const TAny* anEntry) const;
williamr@2: 	IMPORT_C TInt Compare(const TAny* aLeft,const TAny* aRight) const;
williamr@2: 	IMPORT_C void Between(const TAny* aLeft,const TAny* aRight,TBtreePivot& aPivot) const;
williamr@2: protected:
williamr@2: 	TInt iKeyOffset;
williamr@2: 	TInt iCmpType;
williamr@2: 	TInt iKeyLength;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * Base class for TBtreeFix, which provides a B-tree for fixed sized entries.  
williamr@2: */
williamr@2: class TBtreeFixBase : public TBtree
williamr@2: 	{
williamr@2: public:
williamr@2: 	IMPORT_C void Connect(MPagePool* aPool,const MBtreeKey* aKey);
williamr@2: 	IMPORT_C TBool InsertL(TBtreePos& aPos,const TAny* anEntry,TAllowDuplicates aDup=ENoDuplicates);
williamr@2: 	IMPORT_C void ExtractAtL(const TBtreePos& aPos,TAny* anEntry) const;
williamr@2: 	IMPORT_C void ExtractAtL(const TBtreeMark& aMark,TAny* anEntry) const;
williamr@2: protected:
williamr@2: 	IMPORT_C TBtreeFixBase(TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
williamr@2: 	IMPORT_C TBtreeFixBase(const TBtreeToken& aToken,TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
williamr@2: private:
williamr@2: 	TInt iEntrySize;
williamr@2: 	TBtreeInlineLeafOrg iLeafOrgFix;
williamr@2: 	TBtreeInlineIndexOrg iIndexOrgFix;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * A B-tree for fixed-sized keys and entries.
williamr@2: 
williamr@2: Entry is the type of entry to store. Key defines how items should be ordered: 
williamr@2: there must be a member of this type in the Entry class. 
williamr@2: */
williamr@2: template <class Entry,class Key>
williamr@2: class TBtreeFix : public TBtreeFixBase
williamr@2: 	{
williamr@2: public:
williamr@2: 	inline TBtreeFix(TBtreeMode aMode);
williamr@2: 	inline TBtreeFix(const TBtreeToken& aToken,TBtreeMode aMode);
williamr@2: //
williamr@2: 	inline TBool FindL(TBtreePos& aPos,const Key& aKey,TFind aMode=EEqualTo) const;
williamr@2: 	inline TBool InsertL(TBtreePos& aPos,const Entry& anEntry,TAllowDuplicates aDup=ENoDuplicates);
williamr@2: 	inline TBool DeleteL(const Key& aKey);
williamr@2: //
williamr@2: 	inline Entry AtL(const TBtreePos& aPos) const;
williamr@2: 	inline Entry AtL(const TBtreeMark& aMark) const;
williamr@2: 	inline void ExtractAtL(const TBtreePos& aPos,Entry& anEntry) const;
williamr@2: 	inline void ExtractAtL(const TBtreeMark& aMark,Entry& anEntry) const;
williamr@2: 	};
williamr@2: 
williamr@2: /**
williamr@2:  * @publishedAll 
williamr@2:  * @released
williamr@2:  * A specialisation of the B-tree for untyped fixed sized items. 
williamr@2: */
williamr@2: TEMPLATE_SPECIALIZATION class TBtreeFix<TAny,TAny> : public TBtreeFixBase
williamr@2: 	{
williamr@2: public:
williamr@2: 	inline TBtreeFix(TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
williamr@2: 	inline TBtreeFix(const TBtreeToken& aToken,TBtreeMode aMode,TInt anEntrySize,TInt aKeySize);
williamr@2: 	};
williamr@2: 
williamr@2: #include <s32btree.inl>
williamr@2: #endif