userlibandfileserver/fileserver/sfat32/sl_leafdir_cache.cpp
changeset 2 4122176ea935
child 22 2f92ad2dc5db
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/userlibandfileserver/fileserver/sfat32/sl_leafdir_cache.cpp	Mon Dec 21 16:14:42 2009 +0000
@@ -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"), &current->Parent()->Path(), &current->Path(), current->StartClusterNum());
+				}
+			else
+				{
+				__PRINT2(_L("\"%S\" : (%d)\n"), &current->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
+