1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/store/UBTREE/UB_TREE.CPP Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,928 @@
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 +#include "UB_STD.H"
1.20 +
1.21 +//#pragma message( __FILE__ " : 'TBtreePath' does not track insertion position" )
1.22 +//#pragma message( __FILE__ " : 'TBtreePath' record of last entry unused" )
1.23 +//#pragma message( __FILE__ " : 'TBtree' lots of opportunities for on-the-fly integrity checking" )
1.24 +
1.25 +EXPORT_C void TBtreeToken::ExternalizeL(RWriteStream& aStream) const
1.26 +/** Externalises a TBtreeToken object to a stream.
1.27 +
1.28 +@param aStream Stream to which the object should be externalised. */
1.29 + {
1.30 + aStream<<iFirst;
1.31 + aStream<<iRoot;
1.32 + aStream.WriteInt8L(iHeight);
1.33 + }
1.34 +
1.35 +EXPORT_C void TBtreeToken::InternalizeL(RReadStream& aStream)
1.36 +/** Internalises a TBtreeToken object from a stream.
1.37 +
1.38 +@param aStream Stream from which the object should be internalised. */
1.39 + {
1.40 + aStream>>iFirst;
1.41 + aStream>>iRoot;
1.42 + TInt height=aStream.ReadInt8L();
1.43 + if (height<0||height>KMaxBtreeHeight)
1.44 + __LEAVE(KErrCorrupt);
1.45 +//
1.46 + iHeight=height;
1.47 + }
1.48 +
1.49 +EXPORT_C void TBtreeToken::Clear()
1.50 + {
1.51 + iFirst=KNullPageRef;
1.52 + iRoot=KNullPageRef;
1.53 + iHeight=0;
1.54 + }
1.55 +
1.56 +void TBtreePath::Push(TPageRef aRef,TInt aEntry)
1.57 + {
1.58 + __ASSERT_DEBUG(aEntry==TInt(TUint8(aEntry)),Panic(EBadEntryPos));
1.59 + TInt end=--iEnd;
1.60 + __ASSERT_DEBUG(end>=0,Panic(EPathUnderflow));
1.61 + iNodes[end]=aRef;
1.62 + iEntries[end]=TUint8(aEntry);
1.63 + }
1.64 +
1.65 +void TBtreePath::GotoRoot(TBtreeHeight aHeight,TPageRef aRoot)
1.66 +//
1.67 +// Set the end of path to height and root-node given.
1.68 +//
1.69 + {
1.70 + __ASSERT_DEBUG(aHeight>0&&aHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));
1.71 + iEnd=--aHeight;
1.72 + iNodes[aHeight]=aRoot;
1.73 + iEntries[aHeight]=0;
1.74 + }
1.75 +
1.76 +EXPORT_C TBtree::TBtree(TBtreeMode aMode)
1.77 + : iPages(NULL),iFirst(KNullPageRef),iRoot(KNullPageRef),iHeight(0),iStatus(aMode)
1.78 +/** Constructor that sets the B-tree mode.
1.79 +
1.80 +@param aMode B-tree operating mode */
1.81 + {}
1.82 +
1.83 +EXPORT_C TBtree::TBtree(const TBtreeToken& aToken,TBtreeMode aMode)
1.84 + : iPages(NULL)
1.85 +/** Constructor that sets the B-tree mode and initialisation parameters.
1.86 +
1.87 +@param aToken Parameters with which to initialise B-tree
1.88 +@param aMode B-tree operating mode */
1.89 + {
1.90 + Set(aToken,aMode);
1.91 + __ASSERT_DEBUG(iHeight>=0&&iHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));
1.92 + }
1.93 +
1.94 +EXPORT_C void TBtree::Connect(MPagePool* aPool,const MBtreeKey* aKey,const MBtreeLeafOrg* aLeafOrg,const MBtreeIndexOrg* anIndexOrg)
1.95 + {
1.96 + iPages=aPool;
1.97 + iKey=aKey;
1.98 + iLeafOrg=aLeafOrg;
1.99 + iIndexOrg=anIndexOrg;
1.100 + }
1.101 +
1.102 +EXPORT_C void TBtree::Set(const TBtreeToken& aToken,TBtreeMode aMode)
1.103 +/** Initialises the B-tree.
1.104 +
1.105 +@param aToken Parameters with which to initialise the B-tree
1.106 +@param aMode B-tree operating mode */
1.107 + {
1.108 + iFirst=aToken.iFirst;
1.109 + iRoot=aToken.iRoot;
1.110 + iHeight=aToken.iHeight;
1.111 + iStatus=aToken.IsBroken()?aMode|EBroken:aMode;
1.112 + __ASSERT_DEBUG(iHeight>=0&&iHeight<=KMaxBtreeHeight,Panic(EBadTreeHeight));
1.113 + }
1.114 +
1.115 +EXPORT_C TBtreeToken TBtree::Token() const
1.116 +/** Gets an object that encapsulates the TBtree settings.
1.117 +
1.118 +That object can then be used to externalise the settings.
1.119 +
1.120 +@return Encapsulates the TBtree settings. */
1.121 + {
1.122 + return TBtreeToken(iFirst,iRoot,IsIntact()?iHeight:0);
1.123 + }
1.124 +
1.125 +EXPORT_C TBool TBtree::FirstL(TBtreePos& aPos) const
1.126 +/** Goes to the first entry in the B-tree.
1.127 +
1.128 +@param aPos On return, the position of the first entry
1.129 +@return True if there is a first entry, otherwise false */
1.130 + {
1.131 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.132 + CheckIntactL();
1.133 + if (IsEmpty())
1.134 + return EFalse;
1.135 +//
1.136 + TBtreePath& path=aPos.iPath;
1.137 + GotoRoot(path);
1.138 + DescendFirstL(path);
1.139 + return ETrue;
1.140 + }
1.141 +
1.142 +EXPORT_C TBool TBtree::LastL(TBtreePos& aPos) const
1.143 +/** Goes to the last entry in the B-tree.
1.144 +
1.145 +@param aPos On return, the position of the last entry
1.146 +@return True if there are any entries, otherwise false */
1.147 + {
1.148 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.149 + CheckIntactL();
1.150 + if (IsEmpty())
1.151 + return EFalse;
1.152 +//
1.153 + TBtreePath& path=aPos.iPath;
1.154 + GotoRoot(path);
1.155 + DescendLastL(path);
1.156 + return ETrue;
1.157 + }
1.158 +
1.159 +EXPORT_C TBool TBtree::NextL(TBtreePos& aPos) const
1.160 +/** Gets the position of the entry following the specified entry.
1.161 +
1.162 +@param aPos On return, the position of the next entry
1.163 +@return True if there are any more entries, otherwise false */
1.164 + {
1.165 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.166 + TBtreePath& path=aPos.iPath;
1.167 + __ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
1.168 + CheckIntactL();
1.169 + if (IsEmpty()||!AscendAtLastL(path))
1.170 + return EFalse;
1.171 +//
1.172 + DescendFirstL(path);
1.173 + return ETrue;
1.174 + }
1.175 +
1.176 +EXPORT_C TBool TBtree::PreviousL(TBtreePos& aPos) const
1.177 +/** Gets the position of the entry preceding the specified entry.
1.178 +
1.179 +@param aPos On return, the position of the preceding entry
1.180 +@return True if there is a preceding entry, otherwise false */
1.181 + {
1.182 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.183 + TBtreePath& path=aPos.iPath;
1.184 + __ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
1.185 + CheckIntactL();
1.186 + if (IsEmpty()||!AscendAtFirstL(path))
1.187 + return EFalse;
1.188 +//
1.189 + if (!path.IsLeaf())
1.190 + {
1.191 + path.Push(ChildNodeL(path));
1.192 + DescendLastL(path);
1.193 + }
1.194 + return ETrue;
1.195 + }
1.196 +
1.197 +EXPORT_C void TBtree::ClearL()
1.198 +/** Resets the B-tree to have zero-height, and a null root, and deletes all index
1.199 +pages. */
1.200 + {
1.201 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.202 + if (IsEmpty())
1.203 + return;
1.204 + BeginUpdateL();
1.205 + DeleteIndexSetL();
1.206 + while (iFirst!=KNullPageRef)
1.207 + {
1.208 + TPageRef link=iLeafOrg->LinkNode(iPages->LockL(iFirst));
1.209 + iPages->DeleteL(iFirst);
1.210 + iFirst=link;
1.211 + }
1.212 + EndUpdate();
1.213 + }
1.214 +
1.215 +EXPORT_C TInt TBtree::RepairL()
1.216 +/** Attempts to repair a broken B-tree.
1.217 +
1.218 +If the operating mode (TBtreeMode) is set to EBtreeSecure, then the tree can
1.219 +be repaired without any loss of data. Otherwise, the tree must be deleted
1.220 +entirely using ClearL(), and reconstructed using other means.
1.221 +
1.222 +Note that if multiple B-trees share a single store page pool, then reclaiming
1.223 +the pool will break all the other B-trees (but the Broken flag will not be
1.224 +set automatically). These trees can be repaired by calling MarkBroken() and
1.225 +then RepairL(), even if they were not of the EBtreeSecure type.
1.226 +
1.227 +@return Number of leaves in the tree
1.228 +@see TBtreeMode */
1.229 + {
1.230 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.231 + if (IsEmpty())
1.232 + return 0;
1.233 + BeginUpdateL();
1.234 + DeleteIndexSetL();
1.235 +// create the new index set, insert pivots on the end of the index set
1.236 + iHeight=1;
1.237 + iRoot=iFirst;
1.238 + TBtreePath path;
1.239 + TBtreePivot pivot;
1.240 + TInt count=0;
1.241 + TAny* seq=iPages->LockL(iFirst);
1.242 + for (;;)
1.243 + {
1.244 + count+=iLeafOrg->LastEntry(seq);
1.245 + TPageRef link=iLeafOrg->LinkNode(seq);
1.246 + if (link==KNullPageRef)
1.247 + break;
1.248 + TAny* next=iPages->LockL(link);
1.249 + NewPivot(seq,next,pivot);
1.250 + iPages->Unlock(seq);
1.251 + seq=next;
1.252 + if (iHeight==1)
1.253 + { // first insertion, create a new index set
1.254 + iRoot=iFirst;
1.255 + NewRootL();
1.256 + GotoRoot(path);
1.257 + }
1.258 + TBtreeHeight end=path.End();
1.259 + InsertAtL(path,pivot,link);
1.260 + if (path.End()!=end)
1.261 + { // path has been messed up by insertion, set path to last index entry
1.262 + GotoRoot(path);
1.263 + do path.Push(LastChildNodeL(path)); while (!path.IsLeaf());
1.264 + path.Pop();
1.265 + }
1.266 + else
1.267 + path.SetEntry(path.Entry()+1);
1.268 + }
1.269 + iPages->Unlock(seq);
1.270 + EndUpdate();
1.271 + return count;
1.272 + }
1.273 +
1.274 +EXPORT_C TBool TBtree::FindL(TBtreePos& aPos,const TAny* aKey,TFind aMode) const
1.275 +/** Searches for an entry and returns its position.
1.276 +
1.277 +@param aPos On return, the position of the entry found
1.278 +@param aKey Pointer to the key of the entry for which to search
1.279 +@param aMode Type of search to perform
1.280 +@return True if search was successful, else false */
1.281 + {
1.282 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.283 + CheckIntactL();
1.284 + if (IsEmpty())
1.285 + return EFalse;
1.286 + TBtreePath& path=aPos.iPath;
1.287 + TBool match=SearchL(path,aKey,aMode==ELessEqual||aMode==EGreaterThan);
1.288 + switch (aMode)
1.289 + {
1.290 + case EGreaterThan:
1.291 + case EGreaterEqual: // move on if at end of node
1.292 + if (LastEntryL(path)==path.Entry())
1.293 + return NextL(aPos);
1.294 + return ETrue;
1.295 + case ELessThan:
1.296 + case ELessEqual:
1.297 + return PreviousL(aPos);
1.298 + case EEqualTo:
1.299 + break;
1.300 + }
1.301 + return match;
1.302 + }
1.303 +
1.304 +EXPORT_C TBool TBtree::InsertL(TBtreePos& aPos,const TAny* anEntry,TInt aLength,TAllowDuplicates aDup)
1.305 +/** Inserts an entry into the tree.
1.306 +
1.307 +@param aPos On return, the position of the entry inserted
1.308 +@param anEntry Pointer to the entry to insert
1.309 +@param aLength Length of entry
1.310 +@param aDup Flag to indicate whether duplicate entries are allowed in the tree
1.311 +@return True if successful, false if the entry was a duplicate and aDup was
1.312 +set to ENoDuplicates */
1.313 + {
1.314 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.315 + CheckIntactL();
1.316 + TBtreePath& path=aPos.iPath;
1.317 + if (IsEmpty())
1.318 + {
1.319 + NewTreeL();
1.320 + GotoRoot(path);
1.321 + }
1.322 + else
1.323 + {
1.324 + if (SearchL(path,iKey->Key(anEntry))&&aDup==ENoDuplicates)
1.325 + return EFalse; // oops a duplicate
1.326 + }
1.327 + InsertAtL(path,TPtrC8((const TUint8*)anEntry,aLength));
1.328 + return ETrue;
1.329 + }
1.330 +
1.331 +EXPORT_C TBool TBtree::DeleteL(const TAny* aKey)
1.332 +/** Deletes an entry.
1.333 +
1.334 +@param aKey Pointer to the key of the entry to delete
1.335 +@return True if successful, false if the entry was not found */
1.336 + {
1.337 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.338 + CheckIntactL();
1.339 + TBtreePath path;
1.340 + if (IsEmpty()||SearchL(path,aKey)==0)
1.341 + return EFalse; // not found
1.342 + DeleteAtL(path);
1.343 + return ETrue;
1.344 + }
1.345 +
1.346 +EXPORT_C void TBtree::DeleteAtL(TBtreePos& aPos)
1.347 +/** Deletes the entry at the specified position
1.348 +
1.349 +@param aPos Position of the entry to delete */
1.350 + {
1.351 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.352 + TBtreePath& path=aPos.iPath;
1.353 + __ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
1.354 + CheckIntactL();
1.355 + DeleteAtL(path);
1.356 + }
1.357 +
1.358 +EXPORT_C void TBtree::ExtractAtL(const TBtreePos& aPos,TAny* anEntry,TInt aMaxLength) const
1.359 +/** Gets the entry at the specified position.
1.360 +
1.361 +@param aPos Position of the entry to get
1.362 +@param anEntry Buffer into which to copy the entry
1.363 +@param aMaxLength Length of the anEntry buffer. If the entry is longer than
1.364 +this, only the first aMaxLength bytes will be copied. */
1.365 + {
1.366 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.367 + const TBtreePath& path=aPos.iPath;
1.368 + __ASSERT_ALWAYS(path.IsLeaf(),Panic(EInvalidTreePos));
1.369 + CheckIntactL();
1.370 + TAny* pp=GetNodeL(path);
1.371 + TPtrC8 entry=iLeafOrg->Entry(pp,path.Entry());
1.372 + Mem::Copy((TUint8*)anEntry,entry.Ptr(),Min(aMaxLength,entry.Size()));
1.373 + iPages->Unlock(pp);
1.374 + }
1.375 +
1.376 +EXPORT_C TBool TBtree::ResetL(TBtreeMark& aMark) const
1.377 +/** Resets an iterator to the root of the tree.
1.378 +
1.379 +@param aMark Iterator to set
1.380 +@return True if successful, false if the B-tree is empty */
1.381 + {
1.382 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.383 + if (IsEmpty())
1.384 + return EFalse;
1.385 +//
1.386 + TAny* first=iPages->LockL(iFirst);
1.387 + aMark.iLeaf=iFirst;
1.388 + aMark.iLink=iLeafOrg->LinkNode(first);
1.389 + aMark.iEntry=0;
1.390 + aMark.iLast=TUint8(iLeafOrg->LastEntry(first));
1.391 + iPages->Unlock(first);
1.392 + return ETrue;
1.393 + }
1.394 +
1.395 +EXPORT_C TBool TBtree::NextL(TBtreeMark& aMark) const
1.396 +/** Advances an iterator to the next entry.
1.397 +
1.398 +@param aMark Iterator to use. On return, the iterator is advanced to the next
1.399 +entry.
1.400 +@return True if successful, false if there is no next entry */
1.401 + {
1.402 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.403 + if (IsEmpty())
1.404 + return EFalse;
1.405 +//
1.406 + ++aMark.iEntry;
1.407 + if (aMark.iEntry<aMark.iLast)
1.408 + return ETrue;
1.409 +//
1.410 + if (aMark.iLink!=KNullPageRef)
1.411 + {
1.412 + TAny* next=iPages->LockL(aMark.iLink);
1.413 + aMark.iLeaf=aMark.iLink;
1.414 + aMark.iLink=iLeafOrg->LinkNode(next);
1.415 + aMark.iEntry=0;
1.416 + aMark.iLast=TUint8(iLeafOrg->LastEntry(next));
1.417 + iPages->Unlock(next);
1.418 + return ETrue;
1.419 + }
1.420 +//
1.421 + return EFalse;
1.422 + }
1.423 +
1.424 +EXPORT_C void TBtree::ExtractAtL(const TBtreeMark& aMark,TAny* anEntry,TInt aMaxLength) const
1.425 +/** Gets an entry at specified iterator position.
1.426 +
1.427 +@param aMark Position of the entry to get
1.428 +@param anEntry Buffer into which to copy the entry
1.429 +@param aMaxLength Length of anEntry buffer. If the entry is longer than this,
1.430 +only the first aMaxLength bytes are copied. */
1.431 + {
1.432 + __ASSERT_DEBUG(iPages!=0,Panic(ENoConnect));
1.433 + TAny* pp=iPages->LockL(aMark.iLeaf);
1.434 + TPtrC8 entry=iLeafOrg->Entry(pp,aMark.iEntry);
1.435 + Mem::Copy((TUint8*)anEntry,entry.Ptr(),Min(aMaxLength,entry.Size()));
1.436 + iPages->Unlock(pp);
1.437 + }
1.438 +
1.439 +TBool TBtree::AscendAtLastL(TBtreePath& aPath) const
1.440 +//
1.441 +// While aPath is at the end of its node, ascend.
1.442 +// If not at end, then move right and return true. Return false if we've run out of tree.
1.443 +//
1.444 + {
1.445 + for (;;)
1.446 + {
1.447 + TInt last=LastEntryL(aPath);
1.448 + if (aPath.IsLeaf())
1.449 + --last;
1.450 + TInt entry=aPath.Entry();
1.451 + if (entry<last)
1.452 + {
1.453 + aPath.SetEntry(entry+1);
1.454 + return ETrue; // have a next entry at this level
1.455 + }
1.456 + if (IsRoot(aPath))
1.457 + return EFalse; // end of tree
1.458 + aPath.Pop();
1.459 + }
1.460 + }
1.461 +
1.462 +TBool TBtree::AscendAtFirstL(TBtreePath& aPath) const
1.463 +//
1.464 +// While aPath is at the beginning of its node, ascend.
1.465 +// If not at start, then move left and return true. Return false if we've run out of tree.
1.466 +//
1.467 + {
1.468 + for (;;)
1.469 + {
1.470 + TInt entry=aPath.Entry();
1.471 + if (entry>0)
1.472 + {
1.473 + aPath.SetEntry(entry-1);
1.474 + return ETrue; // have a previous entry at this level
1.475 + }
1.476 + if (IsRoot(aPath))
1.477 + return EFalse; // beginning of sequence
1.478 + aPath.Pop();
1.479 + }
1.480 + }
1.481 +
1.482 +void TBtree::DescendFirstL(TBtreePath& aPath) const
1.483 +//
1.484 +// Descend the tree to next entry on the bottom level.
1.485 +//
1.486 + {
1.487 + while (!aPath.IsLeaf())
1.488 + aPath.Push(ChildNodeL(aPath));
1.489 + }
1.490 +
1.491 +void TBtree::DescendLastL(TBtreePath& aPath) const
1.492 +//
1.493 +// Descend the tree to the last entry on the bottom level.
1.494 +//
1.495 + {
1.496 + while (!aPath.IsLeaf())
1.497 + aPath.Push(LastChildNodeL(aPath));
1.498 + aPath.SetEntry(LastEntryL(aPath)-1);
1.499 + }
1.500 +
1.501 +TBool TBtree::SearchL(TBtreePath& aPath,const TAny* aKey,TBool aAfter) const
1.502 +//
1.503 +// Search the B-tree for an entry. Return true if an exact match is found at base level.
1.504 +//
1.505 + {
1.506 + __ASSERT_DEBUG(!IsEmpty(),Panic(ENoTree));
1.507 + TInt entry;
1.508 + GotoRoot(aPath);
1.509 + while (!aPath.IsLeaf())
1.510 + {
1.511 + TAny* pp=GetNodeL(aPath);
1.512 + iIndexOrg->Search(pp,aKey,*iKey,aAfter,entry);
1.513 + aPath.SetEntry(entry);
1.514 + aPath.Push(iIndexOrg->ChildNode(pp,entry));
1.515 + iPages->Unlock(pp);
1.516 + }
1.517 + TAny* pp=GetNodeL(aPath);
1.518 + TBool found=iLeafOrg->Search(pp,aKey,*iKey,aAfter,entry);
1.519 + aPath.SetEntry(entry);
1.520 + iPages->Unlock(pp);
1.521 + return found;
1.522 + }
1.523 +
1.524 +void TBtree::InsertAtL(TBtreePath& aPath,const TDesC8& anEntry)
1.525 +//
1.526 +// Insert anEntry at the current entry in aPath.
1.527 +//
1.528 + {
1.529 + TBtreePivot pivot;
1.530 + TPageRef promote;
1.531 + BeginUpdateL();
1.532 + if (InsertAtL(aPath,anEntry,KNullPageRef,pivot,promote))
1.533 + InsertAtL(aPath,pivot,promote);
1.534 + EndUpdate();
1.535 + }
1.536 +
1.537 +void TBtree::NewPivot(const TAny* aLeftNode,const TAny* aRightNode,TBtreePivot& aPivot) const
1.538 +//
1.539 +// Get the key organisation to generate a new pivot between the given leaf nodes.
1.540 +//
1.541 + {
1.542 + const TAny* left=iLeafOrg->EntryPtr(aLeftNode,iLeafOrg->LastEntry(aLeftNode)-1);
1.543 + const TAny* right=iLeafOrg->EntryPtr(aRightNode,0);
1.544 + iKey->Between(iKey->Key(left),iKey->Key(right),aPivot);
1.545 + __DEBUG(TInt cleft=iKey->Compare(iKey->Key(left),aPivot.Ptr()));
1.546 + __DEBUG(TInt cright=iKey->Compare(iKey->Key(right),aPivot.Ptr()));
1.547 + __ASSERT_DEBUG((cleft<=0&&cright>0)||(cleft==0&&cright==0),Panic(EIllegalPivot));
1.548 + }
1.549 +
1.550 +void TBtree::ReplacePivotL(TBtreePath& aPath,TAny* aNode,TBtreePivot& aPivot)
1.551 +//
1.552 +// Replace current pivot entry in aPath with aPivot.
1.553 +//
1.554 + {
1.555 + TInt entry=aPath.Entry();
1.556 + // update the pivot in the parent
1.557 + if (iIndexOrg->Update(aNode,entry,aPivot))
1.558 + iPages->Unlock(aNode,EPageDirty);
1.559 + else
1.560 + { // have to delete the old pivot and insert new one
1.561 + TPageRef child=iIndexOrg->ChildNode(aNode,entry+1);
1.562 + iIndexOrg->Delete(aNode,entry);
1.563 + iPages->Unlock(aNode,EPageDirty);
1.564 + InsertAtL(aPath,aPivot,child);
1.565 + }
1.566 + }
1.567 +
1.568 +void TBtree::InsertAtL(TBtreePath& aPath,TBtreePivot& aPivot,TPageRef aChild)
1.569 + {
1.570 + TBtreePivot togglePivot;
1.571 + for (;;)
1.572 + {
1.573 + if (!InsertAtL(aPath,aPivot,aChild,togglePivot,aChild))
1.574 + break;
1.575 + if (!InsertAtL(aPath,togglePivot,aChild,aPivot,aChild))
1.576 + break;
1.577 + }
1.578 + }
1.579 +
1.580 +TBool TBtree::InsertAtL(TBtreePath& aPath,const TDesC8& anEntry,TPageRef aChild,TBtreePivot& aPivot,TPageRef& aPromote)
1.581 +//
1.582 +// Insert entry on this level. Return requirement to propagate with aPromote, aChild and aPath ready.
1.583 +//
1.584 + {
1.585 + TBool leaf=aPath.IsLeaf();
1.586 + const MBtreeNodeOrg* nodeOrg=NodeOrg(leaf);
1.587 + TInt entry=aPath.Entry();
1.588 + TAny* pNode=GetNodeL(aPath);
1.589 +
1.590 + if (leaf?iLeafOrg->Insert(pNode,entry,anEntry):iIndexOrg->Insert(pNode,entry,anEntry,aChild))
1.591 + {
1.592 + PutNode(pNode,leaf);
1.593 + return EFalse;
1.594 + }
1.595 + // whatever happens next, we will affect the index set
1.596 + MarkBroken();
1.597 + // attempt an overflow insertion
1.598 + if (!IsRoot(aPath))
1.599 + { // we have an ancestor
1.600 + TPageRef node=aPath.Node(); // save this in case we cannot overflow
1.601 + aPath.Pop();
1.602 + TInt child=aPath.Entry();
1.603 + TAny* pParent=GetNodeL(aPath);
1.604 + TAny* pSibling;
1.605 + if (child<iIndexOrg->LastEntry(pParent))
1.606 + { // try to overflow to the right
1.607 + pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,child+1));
1.608 + if (leaf)
1.609 + {
1.610 + if (iLeafOrg->InsertOverflow(pNode,pSibling,entry,ETrue,anEntry))
1.611 + {
1.612 + NewPivot(pNode,pSibling,aPivot);
1.613 +overflowOK: PutNode(pSibling,leaf);
1.614 + PutNode(pNode,leaf);
1.615 + aPath.SetEntry(child);
1.616 + ReplacePivotL(aPath,pParent,aPivot);
1.617 + return EFalse; // completed insertion
1.618 + }
1.619 + }
1.620 + else
1.621 + {
1.622 + const TPtrC8 pivot=iIndexOrg->Entry(pParent,child);
1.623 + if (iIndexOrg->InsertOverflow(pNode,pSibling,entry,ETrue,anEntry,aChild,pivot,aPivot))
1.624 + goto overflowOK;
1.625 + }
1.626 + iPages->Unlock(pSibling);
1.627 + }
1.628 + if (--child>=0)
1.629 + {
1.630 + pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,child));
1.631 + if (leaf)
1.632 + {
1.633 + if (iLeafOrg->InsertOverflow(pSibling,pNode,entry,EFalse,anEntry))
1.634 + {
1.635 + NewPivot(pSibling,pNode,aPivot);
1.636 + goto overflowOK;
1.637 + }
1.638 + }
1.639 + else
1.640 + {
1.641 + const TPtrC8 pivot=iIndexOrg->Entry(pParent,child);
1.642 + if (iIndexOrg->InsertOverflow(pSibling,pNode,entry,EFalse,anEntry,aChild,pivot,aPivot))
1.643 + goto overflowOK;
1.644 + }
1.645 + iPages->Unlock(pSibling);
1.646 + }
1.647 + // cannot overflow, so...
1.648 + iPages->Unlock(pParent);
1.649 + aPath.Push(node);
1.650 + }
1.651 +
1.652 + // do a split insertion
1.653 + TAny* pSibling=iPages->AllocL();
1.654 + nodeOrg->Init(pSibling);
1.655 + if (leaf)
1.656 + {
1.657 + iLeafOrg->InsertSplit(pNode,pSibling,entry,anEntry);
1.658 + NewPivot(pNode,pSibling,aPivot);
1.659 + aPromote=iPages->AssignL(pSibling); // non-reclaimable, mustn't lose track of leaves
1.660 + iLeafOrg->SetLinkNode(pNode,aPromote); // set up sequencing
1.661 + iPages->Unlock(pNode,EPageUpdate);
1.662 + }
1.663 + else
1.664 + {
1.665 + iIndexOrg->InsertSplit(pNode,pSibling,entry,anEntry,aChild,aPivot);
1.666 + aPromote=iPages->AssignL(pSibling,EPageReclaimable);
1.667 + iPages->Unlock(pNode,EPageDirty);
1.668 + }
1.669 + // propagate insert up the tree
1.670 + if (IsRoot(aPath))
1.671 + { // new root node needed
1.672 + NewRootL();
1.673 + GotoRoot(aPath);
1.674 + }
1.675 + else
1.676 + aPath.Pop();
1.677 + return ETrue;
1.678 + }
1.679 +
1.680 +void TBtree::DeleteAtL(TBtreePath& aPath)
1.681 +//
1.682 +// Delete the current entry on the path
1.683 +//
1.684 + {
1.685 + __ASSERT_DEBUG(aPath.IsLeaf(),Panic(EInvalidTreePos));
1.686 + TBool leaf=ETrue;
1.687 + const MBtreeNodeOrg* nodeOrg=iLeafOrg;
1.688 + TAny* pNode=GetNodeL(aPath);
1.689 + BeginUpdateL();
1.690 + TBtreePivot newPivot;
1.691 +//
1.692 + for (;;)
1.693 + {
1.694 + TPageRef node=aPath.Node();
1.695 + TInt entry=aPath.Entry();
1.696 + if (nodeOrg->Delete(pNode,entry))
1.697 + { // success, no underflow
1.698 + if (leaf&&iLeafOrg->LastEntry(pNode)==entry)
1.699 + { // we deleted the last entry so... replace the pivot to ensure invariant
1.700 + TPageRef next=iLeafOrg->LinkNode(pNode);
1.701 + if (next!=KNullPageRef)
1.702 + { // replace the pivot
1.703 + MarkBroken();
1.704 + TAny* pSibling=iPages->LockL(next);
1.705 + NewPivot(pNode,pSibling,newPivot);
1.706 + iPages->Unlock(pSibling);
1.707 + PutNode(pNode,leaf);
1.708 + // find dividing pivot which we know is there
1.709 + do aPath.Pop(); while (aPath.Entry()==LastEntryL(aPath));
1.710 + ReplacePivotL(aPath,GetNodeL(aPath),newPivot);
1.711 + break;
1.712 + }
1.713 + }
1.714 + PutNode(pNode,leaf);
1.715 + break;
1.716 + }
1.717 + if (IsRoot(aPath))
1.718 + { // the root! If it has entries then we're done
1.719 + if (nodeOrg->LastEntry(pNode)>0)
1.720 + PutNode(pNode,leaf);
1.721 + else
1.722 + {
1.723 + if (--iHeight!=0) // get child as root
1.724 + iRoot=iIndexOrg->ChildNode(pNode,0);
1.725 + else // tree is empty
1.726 + iRoot=iFirst=KNullPageRef;
1.727 + iPages->DeleteL(node);
1.728 + }
1.729 + break;
1.730 + }
1.731 + // will definitely affect the index set
1.732 + MarkBroken();
1.733 + // block has underflowed.. must try to redistribute or concatenate
1.734 + aPath.Pop();
1.735 + TAny* pParent=GetNodeL(aPath);
1.736 + TAny* pSibling;
1.737 + entry=aPath.Entry();
1.738 + if (entry>0)
1.739 + {
1.740 + aPath.SetEntry(--entry);
1.741 + pSibling=iPages->LockL(iIndexOrg->ChildNode(pParent,entry)); // on left
1.742 + }
1.743 + else
1.744 + { // There must be a sibling for non-root nodes!
1.745 + __ASSERT_DEBUG(iIndexOrg->LastEntry(pParent)>0,Panic(EBadEntryCount));
1.746 + pSibling=pNode;
1.747 + node=iIndexOrg->ChildNode(pParent,1); // on right of first child
1.748 + pNode=iPages->LockL(node);
1.749 + }
1.750 + // redistribute between nodes
1.751 + if (leaf)
1.752 + {
1.753 + if (iLeafOrg->Redistribute(pSibling,pNode))
1.754 + {
1.755 + NewPivot(pSibling,pNode,newPivot);
1.756 +redistributeOK: PutNode(pSibling,leaf);
1.757 + PutNode(pNode,leaf);
1.758 + ReplacePivotL(aPath,pParent,newPivot);
1.759 + break;
1.760 + }
1.761 + // failed so concatenate
1.762 + iLeafOrg->Concatenate(pSibling,pNode);
1.763 + iPages->UpdateL(pSibling); // must change it here and now: link target is being deleted
1.764 + }
1.765 + else
1.766 + {
1.767 + TPtrC8 pivot=iIndexOrg->Entry(pParent,entry);
1.768 + if (iIndexOrg->Redistribute(pSibling,pNode,pivot,newPivot))
1.769 + goto redistributeOK;
1.770 + // failed so concatenate
1.771 + iIndexOrg->Concatenate(pSibling,pNode,pivot);
1.772 + iPages->Unlock(pSibling,EPageDirty);
1.773 + }
1.774 + iPages->DeleteL(node);
1.775 + leaf=EFalse;
1.776 + nodeOrg=iIndexOrg;
1.777 + pNode=pParent;
1.778 + }
1.779 + EndUpdate();
1.780 + }
1.781 +
1.782 +void TBtree::DeleteIndexSetL()
1.783 +//
1.784 +// Destroy the index set, handle broken state too
1.785 +//
1.786 + {
1.787 + __ASSERT_DEBUG(!IsEmpty(),User::Invariant());
1.788 + if (IsIntact())
1.789 + {
1.790 + TBtreePath path;
1.791 + GotoRoot(path);
1.792 + if (!path.IsLeaf())
1.793 + {
1.794 + MarkBroken();
1.795 + DeleteIndexNodesL(path,ETrue);
1.796 + }
1.797 + }
1.798 + // delete the leading edge
1.799 + while (iRoot!=iFirst)
1.800 + {
1.801 + TPageRef edge=iIndexOrg->ChildNode(iPages->LockL(iRoot),0);
1.802 + iPages->DeleteL(iRoot);
1.803 + iRoot=edge;
1.804 + }
1.805 + }
1.806 +
1.807 +void TBtree::DeleteIndexNodesL(TBtreePath& aPath,TBool aLeadingEdge)
1.808 +//
1.809 +// Destroy the children of the node in aPath, then destroy the node itself.
1.810 +// do not destroy the sequence set or the leading edge
1.811 +//
1.812 + {
1.813 + if (aPath.End()>1)
1.814 + { // erase children
1.815 + for (TInt ii=LastEntryL(aPath);ii>=0;--ii)
1.816 + {
1.817 + aPath.Push(ChildNodeL(aPath,ii));
1.818 + DeleteIndexNodesL(aPath,aLeadingEdge && ii==0);
1.819 + aPath.Pop();
1.820 + }
1.821 + }
1.822 + if (!aLeadingEdge)
1.823 + iPages->DeleteL(aPath.Node());
1.824 + }
1.825 +
1.826 +void TBtree::NewTreeL()
1.827 +//
1.828 +// Construct the initial node on empty tree.
1.829 +//
1.830 + {
1.831 + TAny* first=iPages->AllocL();
1.832 + iLeafOrg->Init(first);
1.833 + iRoot=iFirst=iPages->AssignL(first); // non-reclaimable, it's a leaf as well as the initial root
1.834 + iHeight=1;
1.835 + }
1.836 +
1.837 +void TBtree::NewRootL()
1.838 +//
1.839 +// Create a new root node and set its child to the current root.
1.840 +//
1.841 + {
1.842 + if (iHeight==KMaxBtreeHeight)
1.843 + __LEAVE(KErrOverflow); // tree is max height
1.844 + TAny* root=iPages->AllocL();
1.845 + iIndexOrg->Init(root);
1.846 + iIndexOrg->MakeRoot(root,iRoot);
1.847 + iRoot=iPages->AssignL(root); // non-reclaimable, mustn't lose track of successive roots
1.848 + ++iHeight;
1.849 + }
1.850 +
1.851 +void TBtree::BeginUpdateL()
1.852 +//
1.853 +// Prepare to update the tree. Mark it dirty and ensure locked pages are abandoned on failure.
1.854 +//
1.855 + {
1.856 + iPages->PushL();
1.857 + MarkDirty();
1.858 + }
1.859 +
1.860 +void TBtree::EndUpdate()
1.861 +//
1.862 +// Update complete, clear the broken flag and discard page pool acquisition
1.863 +//
1.864 + {
1.865 + iPages->Pop();
1.866 + MarkIntact();
1.867 + }
1.868 +
1.869 +void TBtree::CheckIntactL() const
1.870 + {
1.871 + if (IsBroken())
1.872 + __LEAVE(KErrCorrupt);
1.873 + }
1.874 +
1.875 +void TBtree::GotoRoot(TBtreePath& aPath) const
1.876 +//
1.877 +// Set the path to the root of the tree.
1.878 +//
1.879 + {
1.880 + __ASSERT_DEBUG(!IsEmpty(),Panic(ENoTree));
1.881 + aPath.GotoRoot(iHeight,iRoot);
1.882 + }
1.883 +
1.884 +TAny* TBtree::GetNodeL(const TBtreePath& aPath) const
1.885 + {
1.886 + return iPages->LockL(aPath.Node());
1.887 + }
1.888 +
1.889 +void TBtree::PutNode(TAny* aNode,TBool aLeaf) const
1.890 + {
1.891 + iPages->Unlock(aNode,aLeaf&&(iStatus&ESecure)?EPageUpdate:EPageDirty);
1.892 + }
1.893 +
1.894 +TInt TBtree::LastEntryL(const TBtreePath& aPath) const
1.895 + {
1.896 +//#pragma message( __FILE__ " : 'TBtree::LastEntryL()' should have this information without having to look at the tree" )
1.897 + TAny* pp=GetNodeL(aPath);
1.898 + TInt cc=NodeOrg(aPath.IsLeaf())->LastEntry(pp);
1.899 + iPages->Unlock(pp);
1.900 + return cc;
1.901 + }
1.902 +
1.903 +TPageRef TBtree::ChildNodeL(const TBtreePath& aPath) const
1.904 +//
1.905 +// Get current child node.
1.906 +//
1.907 + {
1.908 + __ASSERT_DEBUG(!aPath.IsLeaf(),Panic(EInvalidTreePos));
1.909 + TAny* pp=GetNodeL(aPath);
1.910 + TPageRef pg=iIndexOrg->ChildNode(pp,aPath.Entry());
1.911 + iPages->Unlock(pp);
1.912 + return pg;
1.913 + }
1.914 +
1.915 +TPageRef TBtree::ChildNodeL(TBtreePath& aPath,TInt aChild) const
1.916 + {
1.917 + aPath.SetEntry(aChild);
1.918 + return ChildNodeL(aPath);
1.919 + }
1.920 +
1.921 +TPageRef TBtree::LastChildNodeL(TBtreePath& aPath) const
1.922 + {
1.923 + __ASSERT_DEBUG(!aPath.IsLeaf(),Panic(EInvalidTreePos));
1.924 + TAny* pp=GetNodeL(aPath);
1.925 + TInt entry=iIndexOrg->LastEntry(pp);
1.926 + aPath.SetEntry(entry);
1.927 + TPageRef pg=iIndexOrg->ChildNode(pp,entry);
1.928 + iPages->Unlock(pp);
1.929 + return pg;
1.930 + }
1.931 +