// 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