--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/userlibandfileserver/fileserver/sfat/sl_leafdir_cache.cpp Mon Oct 19 15:55:17 2009 +0100
@@ -0,0 +1,1028 @@
+// Copyright (c) 2008-2009 Nokia Corporation and/or its subsidiary(-ies).
+// All rights reserved.
+// This component and the accompanying materials are made available
+// under the terms of the License "Eclipse Public License v1.0"
+// which accompanies this distribution, and is available
+// at the URL "http://www.eclipse.org/legal/epl-v10.html".
+//
+// Initial Contributors:
+// Nokia Corporation - initial contribution.
+//
+// Contributors:
+//
+// Description:
+// f32\sfat\sl_leafdir_cache.cpp
+//
+//
+
+#include "sl_std.h"
+#include "sl_leafdir_cache.h"
+
+
+
+
+/**
+Get the lru list count
+
+@return the count of lru list
+*/
+TInt CLeafDirTree::LruCount() const
+ {
+ return iLruList.Count();
+ }
+
+/**
+Count currently cached items
+
+@return the number of currently cached items
+*/
+TInt CLeafDirCache::CacheCount() const
+ {
+ return iTree->LruCount();
+ }
+
+//---------------------------------------------------------------------------------------------------------------------------------
+/**
+Default constructor of TDirPosition, a data structure that represents a location of directory
+*/
+TLeafDirData::TLeafDirData()
+ :iClusterNum(0),iMRUPos(0,0)
+ {
+ }
+
+/**
+Constructor of TDirPosition, a data structure that represents a location of directory
+
+@param aClusterNum the cluster number of the directory stores
+*/
+TLeafDirData::TLeafDirData(TUint aClusterNum)
+ :iClusterNum(aClusterNum),iMRUPos(0,0)
+ {
+ }
+
+/**
+Constructor of TDirPosition, a data structure that represents a location of directory
+
+@param aClusterNum the cluster number of the directory stores
+*/
+TLeafDirData::TLeafDirData(TUint aClusterNum, const TEntryPos& aMRUPos)
+ :iClusterNum(aClusterNum),iMRUPos(aMRUPos.Cluster(), aMRUPos.Pos())
+ {
+ }
+
+
+
+/**
+Factory fucntion of tree nodes
+
+@param aOwnerTree a pointer of the tree that owns this node
+@param aPathName the directory path this node represents
+@param aDirPos the location of the directory this node represents
+@param aType the type of the node
+*/
+CLeafDirTreeNode* CLeafDirTreeNode::NewL(CLeafDirTree* aOwnerTree, const TDesC& aPathName, const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType)
+ {
+ CLeafDirTreeNode* self = new(ELeave) CLeafDirTreeNode(aDirPos, aType);
+ CleanupStack::PushL(self);
+ self->ConstructL(aOwnerTree, aPathName);
+ CleanupStack::Pop();
+ return self;
+ }
+
+/**
+Constructor of tree nodes
+
+@param aDirPos the location of the directory this node represents
+@param aType the type of the node
+*/
+CLeafDirTreeNode::CLeafDirTreeNode(const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType)
+ :iParent(NULL), iLeafDirData(aDirPos), iNodeType(aType)
+ {
+ }
+
+/**
+2nd phase constructor of tree nodes
+
+@param aOwnerTree a pointer of the tree that owns this node
+@param aPathName the directory path this node represents
+*/
+void CLeafDirTreeNode::ConstructL(CLeafDirTree* aOwnerTree, const TDesC& aPath)
+ {
+ if (aOwnerTree == NULL)
+ {
+ ASSERT(0);
+ User::Leave(KErrArgument);
+ }
+ iOwnerTree = aOwnerTree;
+ iPath.CreateL(aPath);
+#ifdef _DEBUG
+ iOwnerTree->AddToObjectContainerL(this);
+#endif //_DEBUG
+ }
+
+/**
+Destructor of tree nodes
+
+@pre The node should already be removed from its parent before being deleted
+*/
+CLeafDirTreeNode::~CLeafDirTreeNode()
+ {
+#ifdef _DEBUG
+ TRAPD(err, iOwnerTree->RemoveFromObjectContainerL(this));
+ ASSERT(err == KErrNone);
+#endif // _DEBUG
+ iPath.Close();
+ iChildren.Close();
+ }
+
+/**
+Set type of the node
+
+@param aType the type to be set
+*/
+void CLeafDirTreeNode::SetType(const CLeafDirTreeNode::TLeafDirTreeNodeType aType)
+ {
+ // Root node can not be reset type
+ if (iNodeType == CLeafDirTreeNode::ERoot)
+ return;
+ iNodeType = aType;
+ }
+
+/**
+Set path of the directory the node represents
+
+@param aPath the path to be set
+*/
+void CLeafDirTreeNode::SetPathL(const TDesC& aPath)
+ {
+ ASSERT(aPath.Length() > 0);
+ if (iPath.Length() < aPath.Length())
+ {
+ TInt err = iPath.ReAlloc(aPath.Length());
+ ASSERT(err==KErrNone);
+ User::LeaveIfError(err);
+ }
+ iPath = aPath;
+ }
+
+/**
+Removes from the children list, sets aNode's parent NULL, does not delete aNode
+
+@param aNode the node to be removed
+*/
+TInt CLeafDirTreeNode::RemoveChild(CLeafDirTreeNode* aNode)
+ {
+ ASSERT(aNode);
+ if (aNode->IsRoot())
+ {
+ ASSERT(0);
+ return KErrArgument;
+ }
+
+ if (iChildren.Count() > 0)
+ {
+ for (TInt i = iChildren.Count() - 1; i >= 0; i--)
+ {
+ if (iChildren[i] == aNode)
+ {
+ iChildren.Remove(i);
+ aNode->SetParent(NULL);
+ return KErrNone;
+ }
+ }
+ }
+ return KErrNotFound;
+ }
+
+/**
+Add a new child node to self
+
+@pre aNode should have been removed from its original parent
+@param aNode the node to be added
+*/
+void CLeafDirTreeNode::MakeItChildL(CLeafDirTreeNode* aNode)
+ {
+ ASSERT(aNode->Parent() == NULL);
+ if (aNode->IsRoot())
+ {
+ ASSERT(0);
+ User::Leave(KErrArgument);
+ }
+ iChildren.AppendL(aNode);
+ aNode->SetParent(this);
+ }
+
+
+/**
+Factory function of CLeafDirTree
+
+@param aLimit the maximum number of 'leaf' nodes allowed of the tree
+*/
+CLeafDirTree* CLeafDirTree::NewL(TUint32 aSize)
+ {
+ CLeafDirTree* self = new(ELeave) CLeafDirTree(aSize);
+ CleanupStack::PushL(self);
+ self->ConstructL();
+ CleanupStack::Pop();
+ return self;
+ }
+
+/**
+Constructor of CLeafDirTree
+
+@param aLimit the maximum number of 'leaf' nodes allowed of the tree
+*/
+CLeafDirTree::CLeafDirTree(TUint32 aSize)
+:iSize(aSize)
+ {
+ }
+
+_LIT(KRootDirPath, "\\");
+/**
+2nd phase constructor of CLeafDirTree
+*/
+void CLeafDirTree::ConstructL()
+ {
+ TLeafDirData rootDirPos(0);
+ CLeafDirTreeNode* root = CLeafDirTreeNode::NewL(this, KRootDirPath, rootDirPos, CLeafDirTreeNode::ERoot);
+ iRoot = root;
+ iRoot->SetType(CLeafDirTreeNode::ERoot);
+ }
+
+/**
+Destructor of CLeafDirTree
+*/
+CLeafDirTree::~CLeafDirTree()
+ {
+ Reset();
+ delete iRoot;
+ iLruList.Close();
+
+#ifdef _DEBUG
+ iContainer.Close();
+#endif //_DEBUG
+ }
+
+/**
+Free all the nodes from the tree except root node
+*/
+void CLeafDirTree::Reset()
+ {
+ TInt err = KErrNone;
+ TRAP(err, DeleteSubTreeL(iRoot));
+ ASSERT(err == KErrNone);
+ }
+
+/**
+Search for a node by directory path
+
+@param aPath the path as the key to search in the tree
+@param aNodeFound in return, the node found
+@param aDirPos the location of the directory
+@return KErrNone if a node found
+ KErrNotFound if no node is found
+*/
+TInt CLeafDirTree::Search(const TDesC& aPath, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aDirPos)
+ {
+ return (DoSearch(aPath, iRoot, aNodeFound, aDirPos));
+ }
+
+/**
+Search for a node by directory path, start from children of aNodeToStart but do not include aNodeToStart.
+
+@param aPath the path as the key to search in the tree
+@param aNodeToStart the node whose children to start with
+@param aNodeFound in return, the node found
+@param aDirPos the location of the directory
+@return KErrNone if a node found
+ KErrNotFound if no node is found
+*/
+TInt CLeafDirTree::DoSearch(const TDesC& aPath, CLeafDirTreeNode* aNodeToStart, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aLeafDirData)
+ {
+ RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children();
+ TInt currentPos = currentLevel.Count() - 1;
+ // Current path in search
+ TPtrC currentPath;
+ currentPath.Set(aPath);
+ while (currentLevel.Count() > 0 && currentPos >= 0)
+ {
+ CLeafDirTreeNode* currentNode = currentLevel[currentPos];
+ TPtrC currentNodePath;
+ currentNodePath.Set(currentNode->Path());
+ TInt foundPos = currentPath.FindF(currentNodePath);
+ // If current child's path is part of the searching path,
+ // go to next level
+ // E.g.: current child's path = "1\2\3\", searching path = "1\2\3\5\".
+ if (foundPos == 0 && currentNodePath.Length() < currentPath.Length())
+ {
+ currentPath.Set(currentPath.Mid(currentNodePath.Length()));
+ currentLevel = currentNode->Children();
+ currentPos = currentLevel.Count() - 1;
+ continue;
+ }
+ // If current child's path matches current searching path,
+ // check the node type.
+ else if (foundPos == 0 && currentNodePath.Length() == currentPath.Length())
+ {
+ if (currentNode->IsPureIntermediary())
+ // If found is 'pure intermediary', it is not cached.
+ {
+ return KErrNotFound;
+ }
+ // Otherwise, we have got a cache hit!
+ MakeMostRecentlyUsed(currentNode);
+ aNodeFound = currentNode;
+ aLeafDirData = currentNode->LeafDirData();
+ return KErrNone;
+ }
+ // else, go through current level
+ currentPos--;
+ }
+ // If there is no child or we have not found any matching node,
+ // return KErrNotFound
+ return KErrNotFound;
+ }
+
+/**
+Find the longest common 'path' between two paths.
+Note: not the longest common 'string'.
+
+@param aPathA path A
+@param aPathB path B
+@return the length of the longest common path found
+ KErrNotFound if no node is found
+*/
+TInt FindLongestCommonPath(const TDesC& aPathA, const TDesC& aPathB)
+ {
+ const TInt compareLength = Min(aPathA.Length(), aPathB.Length());
+ if (compareLength <= 0)
+ {
+ return KErrArgument;
+ }
+ TInt i = 0;
+ TInt lastPathDelimiterPos = KErrNotFound;
+ while (i < compareLength && aPathA[i] == aPathB[i])
+ {
+ if (aPathA[i] == '\\')
+ {
+ lastPathDelimiterPos = i;
+ }
+ i++;
+ }
+
+ if (i == 0)
+ {
+ return KErrNotFound;
+ }
+ return lastPathDelimiterPos;
+ }
+
+/**
+Insert a new node to the tree according to the path
+
+@param aPath the path of the new node to be inserted
+@param aDirPos the position of the new node to be inserted
+@param aNodeInserted in return, the node that has been successfully inserted
+*/
+void CLeafDirTree::InsertL(const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted)
+ {
+ ASSERT(aPath.Length() > 0);
+ // aPath should always start and end with a '\\'.
+ if (aPath[0] == '\\' && aPath[aPath.Length() - 1] =='\\')
+ {
+ if (aPath.Length() > 1)
+ {
+ TPtrC path;
+ path.Set(aPath.Mid(1));
+ DoInsertL(iRoot, path, aLeafDirData, aNodeInserted);
+ }
+ }
+ else
+ {
+ ASSERT(0);
+ User::Leave(KErrBadName);
+ }
+ }
+
+/**
+Implementation of the insertion algorithm
+
+@param aNodeToStart the node whose children to start with
+@param aPath the path of the new node to be inserted
+@param aDirPos the position of the new node to be inserted
+@param aNodeInserted in return, the node that has been successfully inserted
+*/
+void CLeafDirTree::DoInsertL(CLeafDirTreeNode* aNodeToStart, const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted)
+ {
+ CLeafDirTreeNode* currentParent = aNodeToStart;
+ TInt foundPos = 0;
+ RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children();
+ TInt currentPos = currentLevel.Count() - 1;
+ TPtrC currentPath;
+ currentPath.Set(aPath);
+ while (currentLevel.Count() > 0 && currentPos >= 0)
+ {
+ CLeafDirTreeNode* currentNode = currentLevel[currentPos];
+ TPtrC currentNodePath;
+ currentNodePath.Set(currentNode->Path());
+
+ // If current node is contained by aPath.
+ // E.g.: current node = "1\2\3\", currentPath = "1\2\3\5\"
+ // In this case, we need to go to next level,
+ // discard logged position (currentPos) in this level as we don't need to come back.
+ foundPos = currentPath.FindF(currentNodePath);
+ if (foundPos == 0 && currentNodePath.Length() < currentPath.Length())
+ {
+ currentParent = currentNode;
+ currentLevel = currentNode->Children();
+ currentPos = currentLevel.Count() - 1;
+ currentPath.Set(currentPath.Mid(currentNodePath.Length()));
+ continue;
+ }
+
+ // If current node's path contains aPath
+ // E.g.: current node = "1\2\3\4\", currentPath = "1\2\3\"
+ // We need to split current node to two nodes and return.
+ foundPos = currentNodePath.FindF(currentPath);
+ if (foundPos == 0 && currentNodePath.Length() > currentPath.Length())
+ {
+ CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeafIntermediary);
+ currentParent->MakeItChildL(newNode);
+
+ TPtrC restPath;
+ restPath.Set(currentNodePath.Mid(currentPath.Length()));
+ currentNode->SetPathL(restPath);
+ currentParent->RemoveChild(currentNode);
+
+ newNode->MakeItChildL(currentNode);
+ AddOntoLruL(newNode);
+ aNodeInserted = newNode;
+ return;
+ }
+
+ // If current node's path equals aPath,
+ // change the node type if it is necessary
+ if (foundPos == 0 && currentNodePath.Length() == currentPath.Length())
+ {
+ // Check node type, if already cached, update Lru list and return.
+ if (currentNode->IsLeaf() || currentNode->IsLeafIntermediary())
+ {
+ currentNode->SetLeafDirData(aLeafDirData);
+ aNodeInserted = currentNode;
+ MakeMostRecentlyUsed(currentNode);
+ return;
+ }
+ // If it has not been cached yet, i.e., it is a 'pure intermediary' node,
+ // cache the node and put it onto Lru list
+ else if(currentNode->IsPureIntermediary())
+ {
+ currentNode->SetLeafDirData(aLeafDirData);
+ currentNode->SetType(CLeafDirTreeNode::ELeafIntermediary);
+ AddOntoLruL(currentNode);
+ aNodeInserted = currentNode;
+ return;
+ }
+ }
+
+ // If none of above is the case (i.e. haven't found exact match or paths
+ // are not contained by each other), we need to find the first common part
+ // between each child and aPath to share path data.
+ foundPos = FindLongestCommonPath(currentNodePath, currentPath);
+ // If a common part of path is found, we need to create a pure intermediary node to share
+ // the common part of path data, and create a new leaf node for the target path.
+ if (foundPos > 0)
+ {
+ TPtrC commonPath;
+ commonPath.Set(currentNodePath.Left(foundPos + 1));
+
+ currentNodePath.Set(currentNodePath.Mid(foundPos + 1));
+ TPtrC newLeafPath;
+ newLeafPath.Set(currentPath.Mid(foundPos + 1));
+
+ // Add new pureintermediary node, set it as child of current parent
+ TLeafDirData dummyPos(0);
+ CLeafDirTreeNode* newPureIntermediaryNode = CLeafDirTreeNode::NewL(this, commonPath, dummyPos, CLeafDirTreeNode::EPureIntermediary);
+ currentParent->MakeItChildL(newPureIntermediaryNode);
+
+ // Remove current child from aNodeToStart, do not need to change
+ // node type of aNodeToStart
+ currentParent->RemoveChild(currentNode);
+
+ // Modify current pathData, make it child of new node
+ newPureIntermediaryNode->MakeItChildL(currentNode);
+ currentNode->SetPathL(currentNodePath);
+
+ // Add new leaf node as a child of the new pure intermediary node
+ CLeafDirTreeNode* newLeafNode = CLeafDirTreeNode::NewL(this, newLeafPath, aLeafDirData, CLeafDirTreeNode::ELeaf);
+ newPureIntermediaryNode->MakeItChildL(newLeafNode);
+ aNodeInserted = newLeafNode;
+ AddOntoLruL(newLeafNode);
+ return;
+ }
+
+ // Otherwise, move on within this level.
+ currentPos--;
+ }
+
+ // No match case found, add a new node straight on at current level
+ CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeaf);
+
+ if (currentParent->IsLeaf()) // might be the root node
+ {
+ currentParent->SetType(CLeafDirTreeNode::ELeafIntermediary);
+ }
+ currentParent->MakeItChildL(newNode);
+ aNodeInserted = newNode;
+ AddOntoLruL(newNode);
+ }
+
+/**
+Remove nodes with a specific position from the tree
+Note: multiple nodes may have the same position value, as directories can be accessed
+ by both long names and short names:
+E.g.: "\\LongDirName01\\LongDirName02\\LongDirName03\\"
+ "\\LongDirName01\\LongDirName02\\LONGDI~1\\"
+ "\\LongDirName01\\LONGDI~1\\LongDirName03\\"
+ "\\LONGDI~1\\LongDirName02\\LongDirName03\\"
+
+@param aDirPos the position of the nodes to be removed
+*/
+void CLeafDirTree::RemoveDirL(const TLeafDirData& aDirPos)
+ {
+ // remove alias nodes in cache
+ for (TInt i = iLruList.Count() - 1; i >= 0; i--)
+ {
+ if (iLruList[i]->StartClusterNum() == aDirPos.iClusterNum)
+ {
+ RemoveFromCacheL(iLruList[i]);
+ }
+ }
+ }
+
+
+/**
+Update the MRU entry position of the tree nodes.
+@param aLeafDirData contains the index of the cache node and the new MRU entry position
+*/
+void CLeafDirTree::UpdateMRUPos(const TLeafDirData& aLeafDirData)
+ {
+ // update alias nodes in cache
+ for (TInt i = iLruList.Count() - 1; i >= 0; i--)
+ {
+ if (iLruList[i]->StartClusterNum() == aLeafDirData.iClusterNum)
+ {
+ iLruList[i]->SetLeafDirData(aLeafDirData);
+ }
+ }
+ }
+
+/**
+Remove a 'leaf' node, i.e. a leaf node or leaf intermediary node.
+
+@param aNodeTodelete the node to be removed
+*/
+void CLeafDirTree::RemoveFromCacheL(CLeafDirTreeNode* aNodeToDelete)
+ {
+ ASSERT(aNodeToDelete->IsLeaf() || aNodeToDelete->IsLeafIntermediary());
+ CLeafDirTreeNode* parent = aNodeToDelete->Parent();
+ // Deleting 'leaf intermediary' nodes:
+ if (aNodeToDelete->IsLeafIntermediary())
+ {
+ // If there is no child, error! The 'tree' is corrupted.
+ if (aNodeToDelete->Children().Count() == 0)
+ {
+ ASSERT(0);
+ User::Leave(KErrCorrupt);
+ }
+ // If there is only one child, 'promote' the child, delete self
+ else if (aNodeToDelete->Children().Count() == 1)
+ {
+ CLeafDirTreeNode* child = (aNodeToDelete->Children())[0];
+ TFileName newPath = aNodeToDelete->Path();
+ newPath.Append(child->Path());
+ child->SetPathL(newPath);
+ aNodeToDelete->RemoveChild(child);
+ parent->MakeItChildL(child);
+
+ parent->RemoveChild(aNodeToDelete);
+ RemoveFromLru(aNodeToDelete);
+ delete aNodeToDelete;
+ return;
+ }
+ // If there are more than one child, just change node type to 'pure intermediary',
+ // but remove self from Lru list.
+ else
+ {
+ aNodeToDelete->SetType(CLeafDirTreeNode::EPureIntermediary);
+ RemoveFromLru(aNodeToDelete);
+ return;
+ }
+ }
+ // Deleting 'leaf' nodes:
+ else
+ {
+ // If 'parent' is a 'leaf intermediary' node
+ if (parent->IsLeafIntermediary())
+ {
+ // If there is no other sibling, change parent's node type to 'leaf',
+ // otherwise, leave parent's type as 'leaf intermediary'
+ if (parent->Children().Count() == 1)
+ {
+ parent->SetType(CLeafDirTreeNode::ELeaf);
+ }
+ parent->RemoveChild(aNodeToDelete);
+ RemoveFromLru(aNodeToDelete);
+ delete aNodeToDelete;
+ return;
+ }
+ // If 'parent' is 'pure intermediary'
+ else if (parent->IsPureIntermediary())
+ {
+ // If there is no sibling nodes, the tree is corrupted,
+ // as 'pure intermediary' node should always have more than one child.
+ if (parent->Children().Count() <= 1)
+ {
+ ASSERT(0);
+ User::Leave(KErrCorrupt);
+ }
+ // If there is only one sibling node, we need to merge the sibling node
+ // to 'parent'.
+ else if (parent->Children().Count() == 2)
+ {
+ // Promote the sibling node, delete both parent and self
+ CLeafDirTreeNode* sibling = (parent->Children())[0] ;
+ if (sibling == aNodeToDelete)
+ {
+ sibling = (parent->Children())[1];
+ }
+ TFileName newPath = aNodeToDelete->Parent()->Path();
+ newPath.Append(sibling->Path());
+ sibling->SetPathL(newPath);
+ parent->RemoveChild(sibling);
+ parent->Parent()->MakeItChildL(sibling);
+
+ parent->RemoveChild(aNodeToDelete);
+ RemoveFromLru(aNodeToDelete);
+ delete aNodeToDelete;
+ aNodeToDelete = NULL;
+
+ parent->Parent()->RemoveChild(parent);
+ delete parent;
+ return;
+ }
+ // Else if there are more than 2 sibling nodes, simply delete self.
+ else
+ {
+ parent->RemoveChild(aNodeToDelete);
+ RemoveFromLru(aNodeToDelete);
+ delete aNodeToDelete;
+ aNodeToDelete = NULL;
+ return;
+ }
+ }
+ // If 'parent' is root node, delete self straightaway
+ else if (aNodeToDelete->Parent()->IsRoot())
+ {
+ aNodeToDelete->Parent()->RemoveChild(aNodeToDelete);
+ RemoveFromLru(aNodeToDelete);
+ delete aNodeToDelete;
+ aNodeToDelete = NULL;
+ return;
+ }
+ // If 'parent' is 'leaf', the tree is corrupted.
+ else if (aNodeToDelete->Parent()->IsLeaf())
+ {
+ ASSERT(0);
+ User::Leave(KErrCorrupt);
+ }
+ }
+ }
+
+/**
+Find the leftest node
+Note: the leftest node must be a 'leaf' node
+
+@param aNodeToStart a node whose children to start with
+@return the leftest node
+*/
+CLeafDirTreeNode* CLeafDirTree::FindLeftestLeafNode(CLeafDirTreeNode* aNodeToStart) const
+ {
+ CLeafDirTreeNode* current = aNodeToStart;
+ while (current->Children().Count() > 0)
+ {
+ current = (current->Children())[0];
+ }
+ return current;
+ }
+
+/**
+Delete all nodes derived from aNodeToStart, except itself.
+
+@param aNodeToStart a node whose children to start with
+*/
+void CLeafDirTree::DeleteSubTreeL(CLeafDirTreeNode* aNodeToStart)
+ {
+ while(aNodeToStart->Children().Count() > 0)
+ {
+ CLeafDirTreeNode* aLeafNode = FindLeftestLeafNode(aNodeToStart);
+ RemoveFromCacheL(aLeafNode);
+ }
+ }
+
+/**
+Make the a node most recent used in LRU list
+
+@param aNodeUsed the node to be made MRU
+*/
+TInt CLeafDirTree::MakeMostRecentlyUsed(CLeafDirTreeNode* aNodeUsed)
+ {
+ for(TInt i = 0; i < iLruList.Count(); i++)
+ {
+ if (aNodeUsed == iLruList[i])
+ {
+ if (i == 0)
+ {
+ return KErrNone;
+ }
+ else
+ {
+ iLruList.Remove(i);
+ iLruList.Insert(aNodeUsed, 0);
+ return KErrNone;
+ }
+ }
+ }
+ return KErrNotFound;
+ }
+
+/**
+Check cache limit, remove least-used cached item when necessary.
+*/
+void CLeafDirTree::CheckLimitL()
+ {
+ const TInt cacheSize = iSize;
+ while (iLruList.Count() > cacheSize)
+ {
+ CLeafDirTreeNode* lruNode = LruNode();
+ RemoveFromCacheL(lruNode);
+ }
+ return;
+ }
+
+/**
+Add new node onto cache list
+
+@param aNodeToAdd the new node to be added onto cache list
+*/
+void CLeafDirTree::AddOntoLruL(CLeafDirTreeNode* aNodeToAdd)
+ {
+ if (aNodeToAdd == NULL)
+ {
+ ASSERT(0);
+ User::Leave(KErrArgument);
+ }
+
+ TInt r = iLruList.Insert(aNodeToAdd, 0);
+ if (r != KErrNone)
+ {
+ ASSERT(0);
+ User::Leave(KErrArgument);
+ }
+ CheckLimitL();
+ }
+
+/**
+Remove a node from cached list.
+
+@param aNodeToRemove the node to be removed from the cache list
+*/
+TInt CLeafDirTree::RemoveFromLru(CLeafDirTreeNode* aNodeToRemove)
+ {
+ for (TInt i = 0; i < iLruList.Count(); i++)
+ {
+ if (aNodeToRemove == iLruList[i])
+ {
+ iLruList.Remove(i);
+ return KErrNone;
+ }
+ }
+ return KErrNotFound;
+ }
+
+/**
+Return the least-recent-used node.
+
+@return the least recent used node on cache
+*/
+CLeafDirTreeNode* CLeafDirTree::LruNode()
+ {
+ if (iLruList.Count() > 0)
+ {
+ return iLruList[iLruList.Count() - 1];
+ }
+ return NULL;
+ }
+
+/*
+Factory function of CLeafDirCache
+
+@param aLimit the cache size
+*/
+CLeafDirCache* CLeafDirCache::NewL(TUint32 aLimit)
+ {
+ CLeafDirCache* self = new(ELeave) CLeafDirCache(aLimit);
+ CleanupStack::PushL(self);
+ self->ConstructL();
+ CleanupStack::Pop(self);
+ return self;
+ }
+
+/*
+2nd phase constructor of CLeafDirCache
+*/
+void CLeafDirCache::ConstructL()
+ {
+ CLeafDirTree* tree = CLeafDirTree::NewL(iSize);
+ iTree = tree;
+ }
+
+/*
+Destructor of CLeafDirCache
+*/
+CLeafDirCache::~CLeafDirCache()
+ {
+ delete iTree;
+ }
+
+/*
+Constructor of CLeafDirCache
+
+@param aLimit the cache size
+*/
+CLeafDirCache::CLeafDirCache(TUint32 aSize)
+ :iSize(aSize)
+ {
+ }
+
+/*
+Reset cache, delete all memory allocated
+*/
+void CLeafDirCache::Reset()
+ {
+ iTree->Reset();
+ }
+
+/*
+Cache interface for searching operations.
+
+@param aPath the path of the directory to search for
+@param aDirPos the location of the direcotry found
+@return KErrNone if a cached direcotry is found,
+ KErrBadName if the path is incorrect, otherwise
+ other system wide error code
+*/
+TInt CLeafDirCache::FindInCache(const TDesC& aPath, TLeafDirData& aLeafDirData) const
+ {
+ if (aPath[0] == '\\')
+ {
+ TPtrC path;
+ path.Set(aPath.Mid(1));
+ CLeafDirTreeNode* dummy = NULL;
+ return (iTree->Search(path, dummy, aLeafDirData));
+ }
+ else
+ {
+ return KErrBadName;
+ }
+ }
+
+/*
+Cache interface for insertion operations.
+
+@param aPath the path of the directory to be added
+@param aDirPos the location of the direcotry to be added
+*/
+void CLeafDirCache::AddToCacheL(const TDesC& aPath, const TLeafDirData& aDirPos)
+ {
+ if (aPath.Length() == 1 && aPath[0] == '\\')
+ return;
+
+ CLeafDirTreeNode* dummy = NULL;
+ iTree->InsertL(aPath, aDirPos, dummy);
+ }
+
+/*
+Cache interface for deletion oeprations.
+Remove all the cached directories with the same specfied position
+
+@param aDirPos the location of the direcotry to be removed
+*/
+void CLeafDirCache::RemoveDirL(const TLeafDirData& aDirPos)
+ {
+ iTree->RemoveDirL(aDirPos);
+ }
+
+/**
+Update the MRU entry position of the cached leaf dir.
+@param aLeafDirData contains a cluster number as the index of the leaf dir and the new MRU entry position
+*/
+void CLeafDirCache::UpdateMRUPos(const TLeafDirData& aLeafDirData)
+ {
+ iTree->UpdateMRUPos(aLeafDirData);
+ }
+/*
+ * Helper functions of CLeafDirTree for debugging & testing use
+ */
+#ifdef _DEBUG
+/*
+All node created will be added to the container of its owner tree, so that we can calculate
+ the number of objects created.
+
+@param aNodeToAdd the newly created node to be add to object container
+*/
+void CLeafDirTree::AddToObjectContainerL(CLeafDirTreeNode* aNodeToAdd)
+ {
+ iContainer.AppendL(aNodeToAdd);
+ }
+
+/*
+A node is removed from object container if it is deleted.
+
+@param aNodeToRemove the node to be deleted
+*/
+void CLeafDirTree::RemoveFromObjectContainerL(CLeafDirTreeNode* aNodeToRemove)
+ {
+ for (TInt i = 0; i < iContainer.Count(); i++)
+ {
+ if (aNodeToRemove == iContainer[i])
+ {
+ iContainer.Remove(i);
+ return;
+ }
+ }
+ ASSERT(0);
+ User::Leave(KErrNotFound);
+ }
+
+/*
+Print out current tree content
+*/
+void CLeafDirTree::DumpTreeContentL() const
+ {
+ RPointerArray<CLeafDirTreeNode>* nodeStack = new(ELeave) RPointerArray<CLeafDirTreeNode>(4);
+ RFs fs;
+ fs.Connect();
+ const TUint32 debugRegister = DebugRegister();
+ fs.SetDebugRegister(debugRegister|KFSYS);
+ if (iRoot != NULL)
+ {
+ nodeStack->Insert(iRoot, 0);
+ while(nodeStack->Count() > 0)
+ {
+ CLeafDirTreeNode* current = (*nodeStack)[0];
+ if (current->Parent() != NULL)
+ {
+ __PRINT3(_L("(\"%S\") -> \"%S\" : (%d)\n"), ¤t->Parent()->Path(), ¤t->Path(), current->StartClusterNum());
+ }
+ else
+ {
+ __PRINT2(_L("\"%S\" : (%d)\n"), ¤t->Path(), current->StartClusterNum());
+ }
+
+ nodeStack->Remove(0);
+
+ TInt currentCount = current->Children().Count();
+ if (currentCount > 0)
+ {
+ RPointerArray<CLeafDirTreeNode> children = current->Children();
+ for (TInt i = 0; i < currentCount; i++)
+ {
+ nodeStack->Insert(children[i], 0);
+ }
+ }
+ }
+ }
+
+ fs.SetDebugRegister(debugRegister);
+ fs.Close();
+ nodeStack->Close();
+ delete nodeStack;
+ }
+
+/*
+Print out current cache content
+*/
+void CLeafDirCache::DumpCacheContentL() const
+ {
+ iTree->DumpTreeContentL();
+ }
+
+/*
+Count of all the nodes
+*/
+TInt CLeafDirCache::NodeCount() const
+ {
+ return iTree->ObjectCount();
+ }
+#endif // _DEBUG
+