Symaptic: os/persistentdata/persistentstorage/store/INC/S32BTREE.H@260cb5ec6c19

     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 //

    16 #if !defined(__S32BTREE_H__)

    17 #define __S32BTREE_H__

    18 #if !defined(__S32PAGE_H__)

    19 #include <s32page.h>

    20 #endif

    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};

    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)

    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 	};

    90 /**

    91  * @publishedAll

    92  * @released

    93  * Identifies a position in a B-tree.

    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 	};

   106 /**

   107  * @publishedAll

   108  * @released

   109  * An iterator for a B-tree.

   111 Functions that use a TBtreeMark are faster than those that use a TBtreePos,

   112 and can be used with a broken B-tree.

   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 	};

   128 /**

   129  * @publishedAll

   130  * @released

   131  * Interface for ordering and creating keys for entries in a B-tree.

   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;

   140 	/** Orders two keys.

   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;

   148 	/** Gets the midpoint between two keys.

   150 	The generated midpoint will be greater or equal to aLeft (by a comparison

   151 	performed by the Compare() function), and less than aRight.

   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 	};

   159 class MBtreeNodeOrg;

   160 class MBtreeLeafOrg;

   161 class MBtreeIndexOrg;

   163 /**

   164  * @publishedAll

   165  * @released

   166  * Provides ordering of entries by key value in a B+-tree (balanced tree)

   167 structure.

   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.

   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.

   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 	};

   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 	};

   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 	};

   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 	};

   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 	};

   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;

   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 	};

   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 	};

   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 	};

   466 /**

   467  * @publishedAll

   468  * @released

   469  * A B-tree for fixed-sized keys and entries.

   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 	};

   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 	};

   503 #include <s32btree.inl>

   504 #endif

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--