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