1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/userlibandfileserver/fileserver/sfat32/sl_leafdir_cache.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,1028 @@
1.4 +// Copyright (c) 2008-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 the License "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 +// f32\sfat\sl_leafdir_cache.cpp
1.18 +//
1.19 +//
1.20 +
1.21 +#include "sl_std.h"
1.22 +#include "sl_leafdir_cache.h"
1.23 +
1.24 +
1.25 +
1.26 +
1.27 +/**
1.28 +Get the lru list count
1.29 +
1.30 +@return the count of lru list
1.31 +*/
1.32 +TInt CLeafDirTree::LruCount() const
1.33 + {
1.34 + return iLruList.Count();
1.35 + }
1.36 +
1.37 +/**
1.38 +Count currently cached items
1.39 +
1.40 +@return the number of currently cached items
1.41 +*/
1.42 +TInt CLeafDirCache::CacheCount() const
1.43 + {
1.44 + return iTree->LruCount();
1.45 + }
1.46 +
1.47 +//---------------------------------------------------------------------------------------------------------------------------------
1.48 +/**
1.49 +Default constructor of TDirPosition, a data structure that represents a location of directory
1.50 +*/
1.51 +TLeafDirData::TLeafDirData()
1.52 + :iClusterNum(0),iMRUPos(0,0)
1.53 + {
1.54 + }
1.55 +
1.56 +/**
1.57 +Constructor of TDirPosition, a data structure that represents a location of directory
1.58 +
1.59 +@param aClusterNum the cluster number of the directory stores
1.60 +*/
1.61 +TLeafDirData::TLeafDirData(TUint aClusterNum)
1.62 + :iClusterNum(aClusterNum),iMRUPos(0,0)
1.63 + {
1.64 + }
1.65 +
1.66 +/**
1.67 +Constructor of TDirPosition, a data structure that represents a location of directory
1.68 +
1.69 +@param aClusterNum the cluster number of the directory stores
1.70 +*/
1.71 +TLeafDirData::TLeafDirData(TUint aClusterNum, const TEntryPos& aMRUPos)
1.72 + :iClusterNum(aClusterNum),iMRUPos(aMRUPos.Cluster(), aMRUPos.Pos())
1.73 + {
1.74 + }
1.75 +
1.76 +
1.77 +
1.78 +/**
1.79 +Factory fucntion of tree nodes
1.80 +
1.81 +@param aOwnerTree a pointer of the tree that owns this node
1.82 +@param aPathName the directory path this node represents
1.83 +@param aDirPos the location of the directory this node represents
1.84 +@param aType the type of the node
1.85 +*/
1.86 +CLeafDirTreeNode* CLeafDirTreeNode::NewL(CLeafDirTree* aOwnerTree, const TDesC& aPathName, const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType)
1.87 + {
1.88 + CLeafDirTreeNode* self = new(ELeave) CLeafDirTreeNode(aDirPos, aType);
1.89 + CleanupStack::PushL(self);
1.90 + self->ConstructL(aOwnerTree, aPathName);
1.91 + CleanupStack::Pop();
1.92 + return self;
1.93 + }
1.94 +
1.95 +/**
1.96 +Constructor of tree nodes
1.97 +
1.98 +@param aDirPos the location of the directory this node represents
1.99 +@param aType the type of the node
1.100 +*/
1.101 +CLeafDirTreeNode::CLeafDirTreeNode(const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType)
1.102 + :iParent(NULL), iLeafDirData(aDirPos), iNodeType(aType)
1.103 + {
1.104 + }
1.105 +
1.106 +/**
1.107 +2nd phase constructor of tree nodes
1.108 +
1.109 +@param aOwnerTree a pointer of the tree that owns this node
1.110 +@param aPathName the directory path this node represents
1.111 +*/
1.112 +void CLeafDirTreeNode::ConstructL(CLeafDirTree* aOwnerTree, const TDesC& aPath)
1.113 + {
1.114 + if (aOwnerTree == NULL)
1.115 + {
1.116 + ASSERT(0);
1.117 + User::Leave(KErrArgument);
1.118 + }
1.119 + iOwnerTree = aOwnerTree;
1.120 + iPath.CreateL(aPath);
1.121 +#ifdef _DEBUG
1.122 + iOwnerTree->AddToObjectContainerL(this);
1.123 +#endif //_DEBUG
1.124 + }
1.125 +
1.126 +/**
1.127 +Destructor of tree nodes
1.128 +
1.129 +@pre The node should already be removed from its parent before being deleted
1.130 +*/
1.131 +CLeafDirTreeNode::~CLeafDirTreeNode()
1.132 + {
1.133 +#ifdef _DEBUG
1.134 + TRAPD(err, iOwnerTree->RemoveFromObjectContainerL(this));
1.135 + ASSERT(err == KErrNone);
1.136 +#endif // _DEBUG
1.137 + iPath.Close();
1.138 + iChildren.Close();
1.139 + }
1.140 +
1.141 +/**
1.142 +Set type of the node
1.143 +
1.144 +@param aType the type to be set
1.145 +*/
1.146 +void CLeafDirTreeNode::SetType(const CLeafDirTreeNode::TLeafDirTreeNodeType aType)
1.147 + {
1.148 + // Root node can not be reset type
1.149 + if (iNodeType == CLeafDirTreeNode::ERoot)
1.150 + return;
1.151 + iNodeType = aType;
1.152 + }
1.153 +
1.154 +/**
1.155 +Set path of the directory the node represents
1.156 +
1.157 +@param aPath the path to be set
1.158 +*/
1.159 +void CLeafDirTreeNode::SetPathL(const TDesC& aPath)
1.160 + {
1.161 + ASSERT(aPath.Length() > 0);
1.162 + if (iPath.Length() < aPath.Length())
1.163 + {
1.164 + TInt err = iPath.ReAlloc(aPath.Length());
1.165 + ASSERT(err==KErrNone);
1.166 + User::LeaveIfError(err);
1.167 + }
1.168 + iPath = aPath;
1.169 + }
1.170 +
1.171 +/**
1.172 +Removes from the children list, sets aNode's parent NULL, does not delete aNode
1.173 +
1.174 +@param aNode the node to be removed
1.175 +*/
1.176 +TInt CLeafDirTreeNode::RemoveChild(CLeafDirTreeNode* aNode)
1.177 + {
1.178 + ASSERT(aNode);
1.179 + if (aNode->IsRoot())
1.180 + {
1.181 + ASSERT(0);
1.182 + return KErrArgument;
1.183 + }
1.184 +
1.185 + if (iChildren.Count() > 0)
1.186 + {
1.187 + for (TInt i = iChildren.Count() - 1; i >= 0; i--)
1.188 + {
1.189 + if (iChildren[i] == aNode)
1.190 + {
1.191 + iChildren.Remove(i);
1.192 + aNode->SetParent(NULL);
1.193 + return KErrNone;
1.194 + }
1.195 + }
1.196 + }
1.197 + return KErrNotFound;
1.198 + }
1.199 +
1.200 +/**
1.201 +Add a new child node to self
1.202 +
1.203 +@pre aNode should have been removed from its original parent
1.204 +@param aNode the node to be added
1.205 +*/
1.206 +void CLeafDirTreeNode::MakeItChildL(CLeafDirTreeNode* aNode)
1.207 + {
1.208 + ASSERT(aNode->Parent() == NULL);
1.209 + if (aNode->IsRoot())
1.210 + {
1.211 + ASSERT(0);
1.212 + User::Leave(KErrArgument);
1.213 + }
1.214 + iChildren.AppendL(aNode);
1.215 + aNode->SetParent(this);
1.216 + }
1.217 +
1.218 +
1.219 +/**
1.220 +Factory function of CLeafDirTree
1.221 +
1.222 +@param aLimit the maximum number of 'leaf' nodes allowed of the tree
1.223 +*/
1.224 +CLeafDirTree* CLeafDirTree::NewL(TUint32 aSize)
1.225 + {
1.226 + CLeafDirTree* self = new(ELeave) CLeafDirTree(aSize);
1.227 + CleanupStack::PushL(self);
1.228 + self->ConstructL();
1.229 + CleanupStack::Pop();
1.230 + return self;
1.231 + }
1.232 +
1.233 +/**
1.234 +Constructor of CLeafDirTree
1.235 +
1.236 +@param aLimit the maximum number of 'leaf' nodes allowed of the tree
1.237 +*/
1.238 +CLeafDirTree::CLeafDirTree(TUint32 aSize)
1.239 +:iSize(aSize)
1.240 + {
1.241 + }
1.242 +
1.243 +_LIT(KRootDirPath, "\\");
1.244 +/**
1.245 +2nd phase constructor of CLeafDirTree
1.246 +*/
1.247 +void CLeafDirTree::ConstructL()
1.248 + {
1.249 + TLeafDirData rootDirPos(0);
1.250 + CLeafDirTreeNode* root = CLeafDirTreeNode::NewL(this, KRootDirPath, rootDirPos, CLeafDirTreeNode::ERoot);
1.251 + iRoot = root;
1.252 + iRoot->SetType(CLeafDirTreeNode::ERoot);
1.253 + }
1.254 +
1.255 +/**
1.256 +Destructor of CLeafDirTree
1.257 +*/
1.258 +CLeafDirTree::~CLeafDirTree()
1.259 + {
1.260 + Reset();
1.261 + delete iRoot;
1.262 + iLruList.Close();
1.263 +
1.264 +#ifdef _DEBUG
1.265 + iContainer.Close();
1.266 +#endif //_DEBUG
1.267 + }
1.268 +
1.269 +/**
1.270 +Free all the nodes from the tree except root node
1.271 +*/
1.272 +void CLeafDirTree::Reset()
1.273 + {
1.274 + TInt err = KErrNone;
1.275 + TRAP(err, DeleteSubTreeL(iRoot));
1.276 + ASSERT(err == KErrNone);
1.277 + }
1.278 +
1.279 +/**
1.280 +Search for a node by directory path
1.281 +
1.282 +@param aPath the path as the key to search in the tree
1.283 +@param aNodeFound in return, the node found
1.284 +@param aDirPos the location of the directory
1.285 +@return KErrNone if a node found
1.286 + KErrNotFound if no node is found
1.287 +*/
1.288 +TInt CLeafDirTree::Search(const TDesC& aPath, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aDirPos)
1.289 + {
1.290 + return (DoSearch(aPath, iRoot, aNodeFound, aDirPos));
1.291 + }
1.292 +
1.293 +/**
1.294 +Search for a node by directory path, start from children of aNodeToStart but do not include aNodeToStart.
1.295 +
1.296 +@param aPath the path as the key to search in the tree
1.297 +@param aNodeToStart the node whose children to start with
1.298 +@param aNodeFound in return, the node found
1.299 +@param aDirPos the location of the directory
1.300 +@return KErrNone if a node found
1.301 + KErrNotFound if no node is found
1.302 +*/
1.303 +TInt CLeafDirTree::DoSearch(const TDesC& aPath, CLeafDirTreeNode* aNodeToStart, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aLeafDirData)
1.304 + {
1.305 + RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children();
1.306 + TInt currentPos = currentLevel.Count() - 1;
1.307 + // Current path in search
1.308 + TPtrC currentPath;
1.309 + currentPath.Set(aPath);
1.310 + while (currentLevel.Count() > 0 && currentPos >= 0)
1.311 + {
1.312 + CLeafDirTreeNode* currentNode = currentLevel[currentPos];
1.313 + TPtrC currentNodePath;
1.314 + currentNodePath.Set(currentNode->Path());
1.315 + TInt foundPos = currentPath.FindF(currentNodePath);
1.316 + // If current child's path is part of the searching path,
1.317 + // go to next level
1.318 + // E.g.: current child's path = "1\2\3\", searching path = "1\2\3\5\".
1.319 + if (foundPos == 0 && currentNodePath.Length() < currentPath.Length())
1.320 + {
1.321 + currentPath.Set(currentPath.Mid(currentNodePath.Length()));
1.322 + currentLevel = currentNode->Children();
1.323 + currentPos = currentLevel.Count() - 1;
1.324 + continue;
1.325 + }
1.326 + // If current child's path matches current searching path,
1.327 + // check the node type.
1.328 + else if (foundPos == 0 && currentNodePath.Length() == currentPath.Length())
1.329 + {
1.330 + if (currentNode->IsPureIntermediary())
1.331 + // If found is 'pure intermediary', it is not cached.
1.332 + {
1.333 + return KErrNotFound;
1.334 + }
1.335 + // Otherwise, we have got a cache hit!
1.336 + MakeMostRecentlyUsed(currentNode);
1.337 + aNodeFound = currentNode;
1.338 + aLeafDirData = currentNode->LeafDirData();
1.339 + return KErrNone;
1.340 + }
1.341 + // else, go through current level
1.342 + currentPos--;
1.343 + }
1.344 + // If there is no child or we have not found any matching node,
1.345 + // return KErrNotFound
1.346 + return KErrNotFound;
1.347 + }
1.348 +
1.349 +/**
1.350 +Find the longest common 'path' between two paths.
1.351 +Note: not the longest common 'string'.
1.352 +
1.353 +@param aPathA path A
1.354 +@param aPathB path B
1.355 +@return the length of the longest common path found
1.356 + KErrNotFound if no node is found
1.357 +*/
1.358 +TInt FindLongestCommonPath(const TDesC& aPathA, const TDesC& aPathB)
1.359 + {
1.360 + const TInt compareLength = Min(aPathA.Length(), aPathB.Length());
1.361 + if (compareLength <= 0)
1.362 + {
1.363 + return KErrArgument;
1.364 + }
1.365 + TInt i = 0;
1.366 + TInt lastPathDelimiterPos = KErrNotFound;
1.367 + while (i < compareLength && aPathA[i] == aPathB[i])
1.368 + {
1.369 + if (aPathA[i] == '\\')
1.370 + {
1.371 + lastPathDelimiterPos = i;
1.372 + }
1.373 + i++;
1.374 + }
1.375 +
1.376 + if (i == 0)
1.377 + {
1.378 + return KErrNotFound;
1.379 + }
1.380 + return lastPathDelimiterPos;
1.381 + }
1.382 +
1.383 +/**
1.384 +Insert a new node to the tree according to the path
1.385 +
1.386 +@param aPath the path of the new node to be inserted
1.387 +@param aDirPos the position of the new node to be inserted
1.388 +@param aNodeInserted in return, the node that has been successfully inserted
1.389 +*/
1.390 +void CLeafDirTree::InsertL(const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted)
1.391 + {
1.392 + ASSERT(aPath.Length() > 0);
1.393 + // aPath should always start and end with a '\\'.
1.394 + if (aPath[0] == '\\' && aPath[aPath.Length() - 1] =='\\')
1.395 + {
1.396 + if (aPath.Length() > 1)
1.397 + {
1.398 + TPtrC path;
1.399 + path.Set(aPath.Mid(1));
1.400 + DoInsertL(iRoot, path, aLeafDirData, aNodeInserted);
1.401 + }
1.402 + }
1.403 + else
1.404 + {
1.405 + ASSERT(0);
1.406 + User::Leave(KErrBadName);
1.407 + }
1.408 + }
1.409 +
1.410 +/**
1.411 +Implementation of the insertion algorithm
1.412 +
1.413 +@param aNodeToStart the node whose children to start with
1.414 +@param aPath the path of the new node to be inserted
1.415 +@param aDirPos the position of the new node to be inserted
1.416 +@param aNodeInserted in return, the node that has been successfully inserted
1.417 +*/
1.418 +void CLeafDirTree::DoInsertL(CLeafDirTreeNode* aNodeToStart, const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted)
1.419 + {
1.420 + CLeafDirTreeNode* currentParent = aNodeToStart;
1.421 + TInt foundPos = 0;
1.422 + RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children();
1.423 + TInt currentPos = currentLevel.Count() - 1;
1.424 + TPtrC currentPath;
1.425 + currentPath.Set(aPath);
1.426 + while (currentLevel.Count() > 0 && currentPos >= 0)
1.427 + {
1.428 + CLeafDirTreeNode* currentNode = currentLevel[currentPos];
1.429 + TPtrC currentNodePath;
1.430 + currentNodePath.Set(currentNode->Path());
1.431 +
1.432 + // If current node is contained by aPath.
1.433 + // E.g.: current node = "1\2\3\", currentPath = "1\2\3\5\"
1.434 + // In this case, we need to go to next level,
1.435 + // discard logged position (currentPos) in this level as we don't need to come back.
1.436 + foundPos = currentPath.FindF(currentNodePath);
1.437 + if (foundPos == 0 && currentNodePath.Length() < currentPath.Length())
1.438 + {
1.439 + currentParent = currentNode;
1.440 + currentLevel = currentNode->Children();
1.441 + currentPos = currentLevel.Count() - 1;
1.442 + currentPath.Set(currentPath.Mid(currentNodePath.Length()));
1.443 + continue;
1.444 + }
1.445 +
1.446 + // If current node's path contains aPath
1.447 + // E.g.: current node = "1\2\3\4\", currentPath = "1\2\3\"
1.448 + // We need to split current node to two nodes and return.
1.449 + foundPos = currentNodePath.FindF(currentPath);
1.450 + if (foundPos == 0 && currentNodePath.Length() > currentPath.Length())
1.451 + {
1.452 + CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeafIntermediary);
1.453 + currentParent->MakeItChildL(newNode);
1.454 +
1.455 + TPtrC restPath;
1.456 + restPath.Set(currentNodePath.Mid(currentPath.Length()));
1.457 + currentNode->SetPathL(restPath);
1.458 + currentParent->RemoveChild(currentNode);
1.459 +
1.460 + newNode->MakeItChildL(currentNode);
1.461 + AddOntoLruL(newNode);
1.462 + aNodeInserted = newNode;
1.463 + return;
1.464 + }
1.465 +
1.466 + // If current node's path equals aPath,
1.467 + // change the node type if it is necessary
1.468 + if (foundPos == 0 && currentNodePath.Length() == currentPath.Length())
1.469 + {
1.470 + // Check node type, if already cached, update Lru list and return.
1.471 + if (currentNode->IsLeaf() || currentNode->IsLeafIntermediary())
1.472 + {
1.473 + currentNode->SetLeafDirData(aLeafDirData);
1.474 + aNodeInserted = currentNode;
1.475 + MakeMostRecentlyUsed(currentNode);
1.476 + return;
1.477 + }
1.478 + // If it has not been cached yet, i.e., it is a 'pure intermediary' node,
1.479 + // cache the node and put it onto Lru list
1.480 + else if(currentNode->IsPureIntermediary())
1.481 + {
1.482 + currentNode->SetLeafDirData(aLeafDirData);
1.483 + currentNode->SetType(CLeafDirTreeNode::ELeafIntermediary);
1.484 + AddOntoLruL(currentNode);
1.485 + aNodeInserted = currentNode;
1.486 + return;
1.487 + }
1.488 + }
1.489 +
1.490 + // If none of above is the case (i.e. haven't found exact match or paths
1.491 + // are not contained by each other), we need to find the first common part
1.492 + // between each child and aPath to share path data.
1.493 + foundPos = FindLongestCommonPath(currentNodePath, currentPath);
1.494 + // If a common part of path is found, we need to create a pure intermediary node to share
1.495 + // the common part of path data, and create a new leaf node for the target path.
1.496 + if (foundPos > 0)
1.497 + {
1.498 + TPtrC commonPath;
1.499 + commonPath.Set(currentNodePath.Left(foundPos + 1));
1.500 +
1.501 + currentNodePath.Set(currentNodePath.Mid(foundPos + 1));
1.502 + TPtrC newLeafPath;
1.503 + newLeafPath.Set(currentPath.Mid(foundPos + 1));
1.504 +
1.505 + // Add new pureintermediary node, set it as child of current parent
1.506 + TLeafDirData dummyPos(0);
1.507 + CLeafDirTreeNode* newPureIntermediaryNode = CLeafDirTreeNode::NewL(this, commonPath, dummyPos, CLeafDirTreeNode::EPureIntermediary);
1.508 + currentParent->MakeItChildL(newPureIntermediaryNode);
1.509 +
1.510 + // Remove current child from aNodeToStart, do not need to change
1.511 + // node type of aNodeToStart
1.512 + currentParent->RemoveChild(currentNode);
1.513 +
1.514 + // Modify current pathData, make it child of new node
1.515 + newPureIntermediaryNode->MakeItChildL(currentNode);
1.516 + currentNode->SetPathL(currentNodePath);
1.517 +
1.518 + // Add new leaf node as a child of the new pure intermediary node
1.519 + CLeafDirTreeNode* newLeafNode = CLeafDirTreeNode::NewL(this, newLeafPath, aLeafDirData, CLeafDirTreeNode::ELeaf);
1.520 + newPureIntermediaryNode->MakeItChildL(newLeafNode);
1.521 + aNodeInserted = newLeafNode;
1.522 + AddOntoLruL(newLeafNode);
1.523 + return;
1.524 + }
1.525 +
1.526 + // Otherwise, move on within this level.
1.527 + currentPos--;
1.528 + }
1.529 +
1.530 + // No match case found, add a new node straight on at current level
1.531 + CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeaf);
1.532 +
1.533 + if (currentParent->IsLeaf()) // might be the root node
1.534 + {
1.535 + currentParent->SetType(CLeafDirTreeNode::ELeafIntermediary);
1.536 + }
1.537 + currentParent->MakeItChildL(newNode);
1.538 + aNodeInserted = newNode;
1.539 + AddOntoLruL(newNode);
1.540 + }
1.541 +
1.542 +/**
1.543 +Remove nodes with a specific position from the tree
1.544 +Note: multiple nodes may have the same position value, as directories can be accessed
1.545 + by both long names and short names:
1.546 +E.g.: "\\LongDirName01\\LongDirName02\\LongDirName03\\"
1.547 + "\\LongDirName01\\LongDirName02\\LONGDI~1\\"
1.548 + "\\LongDirName01\\LONGDI~1\\LongDirName03\\"
1.549 + "\\LONGDI~1\\LongDirName02\\LongDirName03\\"
1.550 +
1.551 +@param aDirPos the position of the nodes to be removed
1.552 +*/
1.553 +void CLeafDirTree::RemoveDirL(const TLeafDirData& aDirPos)
1.554 + {
1.555 + // remove alias nodes in cache
1.556 + for (TInt i = iLruList.Count() - 1; i >= 0; i--)
1.557 + {
1.558 + if (iLruList[i]->StartClusterNum() == aDirPos.iClusterNum)
1.559 + {
1.560 + RemoveFromCacheL(iLruList[i]);
1.561 + }
1.562 + }
1.563 + }
1.564 +
1.565 +
1.566 +/**
1.567 +Update the MRU entry position of the tree nodes.
1.568 +@param aLeafDirData contains the index of the cache node and the new MRU entry position
1.569 +*/
1.570 +void CLeafDirTree::UpdateMRUPos(const TLeafDirData& aLeafDirData)
1.571 + {
1.572 + // update alias nodes in cache
1.573 + for (TInt i = iLruList.Count() - 1; i >= 0; i--)
1.574 + {
1.575 + if (iLruList[i]->StartClusterNum() == aLeafDirData.iClusterNum)
1.576 + {
1.577 + iLruList[i]->SetLeafDirData(aLeafDirData);
1.578 + }
1.579 + }
1.580 + }
1.581 +
1.582 +/**
1.583 +Remove a 'leaf' node, i.e. a leaf node or leaf intermediary node.
1.584 +
1.585 +@param aNodeTodelete the node to be removed
1.586 +*/
1.587 +void CLeafDirTree::RemoveFromCacheL(CLeafDirTreeNode* aNodeToDelete)
1.588 + {
1.589 + ASSERT(aNodeToDelete->IsLeaf() || aNodeToDelete->IsLeafIntermediary());
1.590 + CLeafDirTreeNode* parent = aNodeToDelete->Parent();
1.591 + // Deleting 'leaf intermediary' nodes:
1.592 + if (aNodeToDelete->IsLeafIntermediary())
1.593 + {
1.594 + // If there is no child, error! The 'tree' is corrupted.
1.595 + if (aNodeToDelete->Children().Count() == 0)
1.596 + {
1.597 + ASSERT(0);
1.598 + User::Leave(KErrCorrupt);
1.599 + }
1.600 + // If there is only one child, 'promote' the child, delete self
1.601 + else if (aNodeToDelete->Children().Count() == 1)
1.602 + {
1.603 + CLeafDirTreeNode* child = (aNodeToDelete->Children())[0];
1.604 + TFileName newPath = aNodeToDelete->Path();
1.605 + newPath.Append(child->Path());
1.606 + child->SetPathL(newPath);
1.607 + aNodeToDelete->RemoveChild(child);
1.608 + parent->MakeItChildL(child);
1.609 +
1.610 + parent->RemoveChild(aNodeToDelete);
1.611 + RemoveFromLru(aNodeToDelete);
1.612 + delete aNodeToDelete;
1.613 + return;
1.614 + }
1.615 + // If there are more than one child, just change node type to 'pure intermediary',
1.616 + // but remove self from Lru list.
1.617 + else
1.618 + {
1.619 + aNodeToDelete->SetType(CLeafDirTreeNode::EPureIntermediary);
1.620 + RemoveFromLru(aNodeToDelete);
1.621 + return;
1.622 + }
1.623 + }
1.624 + // Deleting 'leaf' nodes:
1.625 + else
1.626 + {
1.627 + // If 'parent' is a 'leaf intermediary' node
1.628 + if (parent->IsLeafIntermediary())
1.629 + {
1.630 + // If there is no other sibling, change parent's node type to 'leaf',
1.631 + // otherwise, leave parent's type as 'leaf intermediary'
1.632 + if (parent->Children().Count() == 1)
1.633 + {
1.634 + parent->SetType(CLeafDirTreeNode::ELeaf);
1.635 + }
1.636 + parent->RemoveChild(aNodeToDelete);
1.637 + RemoveFromLru(aNodeToDelete);
1.638 + delete aNodeToDelete;
1.639 + return;
1.640 + }
1.641 + // If 'parent' is 'pure intermediary'
1.642 + else if (parent->IsPureIntermediary())
1.643 + {
1.644 + // If there is no sibling nodes, the tree is corrupted,
1.645 + // as 'pure intermediary' node should always have more than one child.
1.646 + if (parent->Children().Count() <= 1)
1.647 + {
1.648 + ASSERT(0);
1.649 + User::Leave(KErrCorrupt);
1.650 + }
1.651 + // If there is only one sibling node, we need to merge the sibling node
1.652 + // to 'parent'.
1.653 + else if (parent->Children().Count() == 2)
1.654 + {
1.655 + // Promote the sibling node, delete both parent and self
1.656 + CLeafDirTreeNode* sibling = (parent->Children())[0] ;
1.657 + if (sibling == aNodeToDelete)
1.658 + {
1.659 + sibling = (parent->Children())[1];
1.660 + }
1.661 + TFileName newPath = aNodeToDelete->Parent()->Path();
1.662 + newPath.Append(sibling->Path());
1.663 + sibling->SetPathL(newPath);
1.664 + parent->RemoveChild(sibling);
1.665 + parent->Parent()->MakeItChildL(sibling);
1.666 +
1.667 + parent->RemoveChild(aNodeToDelete);
1.668 + RemoveFromLru(aNodeToDelete);
1.669 + delete aNodeToDelete;
1.670 + aNodeToDelete = NULL;
1.671 +
1.672 + parent->Parent()->RemoveChild(parent);
1.673 + delete parent;
1.674 + return;
1.675 + }
1.676 + // Else if there are more than 2 sibling nodes, simply delete self.
1.677 + else
1.678 + {
1.679 + parent->RemoveChild(aNodeToDelete);
1.680 + RemoveFromLru(aNodeToDelete);
1.681 + delete aNodeToDelete;
1.682 + aNodeToDelete = NULL;
1.683 + return;
1.684 + }
1.685 + }
1.686 + // If 'parent' is root node, delete self straightaway
1.687 + else if (aNodeToDelete->Parent()->IsRoot())
1.688 + {
1.689 + aNodeToDelete->Parent()->RemoveChild(aNodeToDelete);
1.690 + RemoveFromLru(aNodeToDelete);
1.691 + delete aNodeToDelete;
1.692 + aNodeToDelete = NULL;
1.693 + return;
1.694 + }
1.695 + // If 'parent' is 'leaf', the tree is corrupted.
1.696 + else if (aNodeToDelete->Parent()->IsLeaf())
1.697 + {
1.698 + ASSERT(0);
1.699 + User::Leave(KErrCorrupt);
1.700 + }
1.701 + }
1.702 + }
1.703 +
1.704 +/**
1.705 +Find the leftest node
1.706 +Note: the leftest node must be a 'leaf' node
1.707 +
1.708 +@param aNodeToStart a node whose children to start with
1.709 +@return the leftest node
1.710 +*/
1.711 +CLeafDirTreeNode* CLeafDirTree::FindLeftestLeafNode(CLeafDirTreeNode* aNodeToStart) const
1.712 + {
1.713 + CLeafDirTreeNode* current = aNodeToStart;
1.714 + while (current->Children().Count() > 0)
1.715 + {
1.716 + current = (current->Children())[0];
1.717 + }
1.718 + return current;
1.719 + }
1.720 +
1.721 +/**
1.722 +Delete all nodes derived from aNodeToStart, except itself.
1.723 +
1.724 +@param aNodeToStart a node whose children to start with
1.725 +*/
1.726 +void CLeafDirTree::DeleteSubTreeL(CLeafDirTreeNode* aNodeToStart)
1.727 + {
1.728 + while(aNodeToStart->Children().Count() > 0)
1.729 + {
1.730 + CLeafDirTreeNode* aLeafNode = FindLeftestLeafNode(aNodeToStart);
1.731 + RemoveFromCacheL(aLeafNode);
1.732 + }
1.733 + }
1.734 +
1.735 +/**
1.736 +Make the a node most recent used in LRU list
1.737 +
1.738 +@param aNodeUsed the node to be made MRU
1.739 +*/
1.740 +TInt CLeafDirTree::MakeMostRecentlyUsed(CLeafDirTreeNode* aNodeUsed)
1.741 + {
1.742 + for(TInt i = 0; i < iLruList.Count(); i++)
1.743 + {
1.744 + if (aNodeUsed == iLruList[i])
1.745 + {
1.746 + if (i == 0)
1.747 + {
1.748 + return KErrNone;
1.749 + }
1.750 + else
1.751 + {
1.752 + iLruList.Remove(i);
1.753 + iLruList.Insert(aNodeUsed, 0);
1.754 + return KErrNone;
1.755 + }
1.756 + }
1.757 + }
1.758 + return KErrNotFound;
1.759 + }
1.760 +
1.761 +/**
1.762 +Check cache limit, remove least-used cached item when necessary.
1.763 +*/
1.764 +void CLeafDirTree::CheckLimitL()
1.765 + {
1.766 + const TInt cacheSize = iSize;
1.767 + while (iLruList.Count() > cacheSize)
1.768 + {
1.769 + CLeafDirTreeNode* lruNode = LruNode();
1.770 + RemoveFromCacheL(lruNode);
1.771 + }
1.772 + return;
1.773 + }
1.774 +
1.775 +/**
1.776 +Add new node onto cache list
1.777 +
1.778 +@param aNodeToAdd the new node to be added onto cache list
1.779 +*/
1.780 +void CLeafDirTree::AddOntoLruL(CLeafDirTreeNode* aNodeToAdd)
1.781 + {
1.782 + if (aNodeToAdd == NULL)
1.783 + {
1.784 + ASSERT(0);
1.785 + User::Leave(KErrArgument);
1.786 + }
1.787 +
1.788 + TInt r = iLruList.Insert(aNodeToAdd, 0);
1.789 + if (r != KErrNone)
1.790 + {
1.791 + ASSERT(0);
1.792 + User::Leave(KErrArgument);
1.793 + }
1.794 + CheckLimitL();
1.795 + }
1.796 +
1.797 +/**
1.798 +Remove a node from cached list.
1.799 +
1.800 +@param aNodeToRemove the node to be removed from the cache list
1.801 +*/
1.802 +TInt CLeafDirTree::RemoveFromLru(CLeafDirTreeNode* aNodeToRemove)
1.803 + {
1.804 + for (TInt i = 0; i < iLruList.Count(); i++)
1.805 + {
1.806 + if (aNodeToRemove == iLruList[i])
1.807 + {
1.808 + iLruList.Remove(i);
1.809 + return KErrNone;
1.810 + }
1.811 + }
1.812 + return KErrNotFound;
1.813 + }
1.814 +
1.815 +/**
1.816 +Return the least-recent-used node.
1.817 +
1.818 +@return the least recent used node on cache
1.819 +*/
1.820 +CLeafDirTreeNode* CLeafDirTree::LruNode()
1.821 + {
1.822 + if (iLruList.Count() > 0)
1.823 + {
1.824 + return iLruList[iLruList.Count() - 1];
1.825 + }
1.826 + return NULL;
1.827 + }
1.828 +
1.829 +/*
1.830 +Factory function of CLeafDirCache
1.831 +
1.832 +@param aLimit the cache size
1.833 +*/
1.834 +CLeafDirCache* CLeafDirCache::NewL(TUint32 aLimit)
1.835 + {
1.836 + CLeafDirCache* self = new(ELeave) CLeafDirCache(aLimit);
1.837 + CleanupStack::PushL(self);
1.838 + self->ConstructL();
1.839 + CleanupStack::Pop(self);
1.840 + return self;
1.841 + }
1.842 +
1.843 +/*
1.844 +2nd phase constructor of CLeafDirCache
1.845 +*/
1.846 +void CLeafDirCache::ConstructL()
1.847 + {
1.848 + CLeafDirTree* tree = CLeafDirTree::NewL(iSize);
1.849 + iTree = tree;
1.850 + }
1.851 +
1.852 +/*
1.853 +Destructor of CLeafDirCache
1.854 +*/
1.855 +CLeafDirCache::~CLeafDirCache()
1.856 + {
1.857 + delete iTree;
1.858 + }
1.859 +
1.860 +/*
1.861 +Constructor of CLeafDirCache
1.862 +
1.863 +@param aLimit the cache size
1.864 +*/
1.865 +CLeafDirCache::CLeafDirCache(TUint32 aSize)
1.866 + :iSize(aSize)
1.867 + {
1.868 + }
1.869 +
1.870 +/*
1.871 +Reset cache, delete all memory allocated
1.872 +*/
1.873 +void CLeafDirCache::Reset()
1.874 + {
1.875 + iTree->Reset();
1.876 + }
1.877 +
1.878 +/*
1.879 +Cache interface for searching operations.
1.880 +
1.881 +@param aPath the path of the directory to search for
1.882 +@param aDirPos the location of the direcotry found
1.883 +@return KErrNone if a cached direcotry is found,
1.884 + KErrBadName if the path is incorrect, otherwise
1.885 + other system wide error code
1.886 +*/
1.887 +TInt CLeafDirCache::FindInCache(const TDesC& aPath, TLeafDirData& aLeafDirData) const
1.888 + {
1.889 + if (aPath[0] == '\\')
1.890 + {
1.891 + TPtrC path;
1.892 + path.Set(aPath.Mid(1));
1.893 + CLeafDirTreeNode* dummy = NULL;
1.894 + return (iTree->Search(path, dummy, aLeafDirData));
1.895 + }
1.896 + else
1.897 + {
1.898 + return KErrBadName;
1.899 + }
1.900 + }
1.901 +
1.902 +/*
1.903 +Cache interface for insertion operations.
1.904 +
1.905 +@param aPath the path of the directory to be added
1.906 +@param aDirPos the location of the direcotry to be added
1.907 +*/
1.908 +void CLeafDirCache::AddToCacheL(const TDesC& aPath, const TLeafDirData& aDirPos)
1.909 + {
1.910 + if (aPath.Length() == 1 && aPath[0] == '\\')
1.911 + return;
1.912 +
1.913 + CLeafDirTreeNode* dummy = NULL;
1.914 + iTree->InsertL(aPath, aDirPos, dummy);
1.915 + }
1.916 +
1.917 +/*
1.918 +Cache interface for deletion oeprations.
1.919 +Remove all the cached directories with the same specfied position
1.920 +
1.921 +@param aDirPos the location of the direcotry to be removed
1.922 +*/
1.923 +void CLeafDirCache::RemoveDirL(const TLeafDirData& aDirPos)
1.924 + {
1.925 + iTree->RemoveDirL(aDirPos);
1.926 + }
1.927 +
1.928 +/**
1.929 +Update the MRU entry position of the cached leaf dir.
1.930 +@param aLeafDirData contains a cluster number as the index of the leaf dir and the new MRU entry position
1.931 +*/
1.932 +void CLeafDirCache::UpdateMRUPos(const TLeafDirData& aLeafDirData)
1.933 + {
1.934 + iTree->UpdateMRUPos(aLeafDirData);
1.935 + }
1.936 +/*
1.937 + * Helper functions of CLeafDirTree for debugging & testing use
1.938 + */
1.939 +#ifdef _DEBUG
1.940 +/*
1.941 +All node created will be added to the container of its owner tree, so that we can calculate
1.942 + the number of objects created.
1.943 +
1.944 +@param aNodeToAdd the newly created node to be add to object container
1.945 +*/
1.946 +void CLeafDirTree::AddToObjectContainerL(CLeafDirTreeNode* aNodeToAdd)
1.947 + {
1.948 + iContainer.AppendL(aNodeToAdd);
1.949 + }
1.950 +
1.951 +/*
1.952 +A node is removed from object container if it is deleted.
1.953 +
1.954 +@param aNodeToRemove the node to be deleted
1.955 +*/
1.956 +void CLeafDirTree::RemoveFromObjectContainerL(CLeafDirTreeNode* aNodeToRemove)
1.957 + {
1.958 + for (TInt i = 0; i < iContainer.Count(); i++)
1.959 + {
1.960 + if (aNodeToRemove == iContainer[i])
1.961 + {
1.962 + iContainer.Remove(i);
1.963 + return;
1.964 + }
1.965 + }
1.966 + ASSERT(0);
1.967 + User::Leave(KErrNotFound);
1.968 + }
1.969 +
1.970 +/*
1.971 +Print out current tree content
1.972 +*/
1.973 +void CLeafDirTree::DumpTreeContentL() const
1.974 + {
1.975 + RPointerArray<CLeafDirTreeNode>* nodeStack = new(ELeave) RPointerArray<CLeafDirTreeNode>(4);
1.976 + RFs fs;
1.977 + fs.Connect();
1.978 + const TUint32 debugRegister = DebugRegister();
1.979 + fs.SetDebugRegister(debugRegister|KFSYS);
1.980 + if (iRoot != NULL)
1.981 + {
1.982 + nodeStack->Insert(iRoot, 0);
1.983 + while(nodeStack->Count() > 0)
1.984 + {
1.985 + CLeafDirTreeNode* current = (*nodeStack)[0];
1.986 + if (current->Parent() != NULL)
1.987 + {
1.988 + __PRINT3(_L("(\"%S\") -> \"%S\" : (%d)\n"), ¤t->Parent()->Path(), ¤t->Path(), current->StartClusterNum());
1.989 + }
1.990 + else
1.991 + {
1.992 + __PRINT2(_L("\"%S\" : (%d)\n"), ¤t->Path(), current->StartClusterNum());
1.993 + }
1.994 +
1.995 + nodeStack->Remove(0);
1.996 +
1.997 + TInt currentCount = current->Children().Count();
1.998 + if (currentCount > 0)
1.999 + {
1.1000 + RPointerArray<CLeafDirTreeNode> children = current->Children();
1.1001 + for (TInt i = 0; i < currentCount; i++)
1.1002 + {
1.1003 + nodeStack->Insert(children[i], 0);
1.1004 + }
1.1005 + }
1.1006 + }
1.1007 + }
1.1008 +
1.1009 + fs.SetDebugRegister(debugRegister);
1.1010 + fs.Close();
1.1011 + nodeStack->Close();
1.1012 + delete nodeStack;
1.1013 + }
1.1014 +
1.1015 +/*
1.1016 +Print out current cache content
1.1017 +*/
1.1018 +void CLeafDirCache::DumpCacheContentL() const
1.1019 + {
1.1020 + iTree->DumpTreeContentL();
1.1021 + }
1.1022 +
1.1023 +/*
1.1024 +Count of all the nodes
1.1025 +*/
1.1026 +TInt CLeafDirCache::NodeCount() const
1.1027 + {
1.1028 + return iTree->ObjectCount();
1.1029 + }
1.1030 +#endif // _DEBUG
1.1031 +