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

	{

	__PRINT2(_L("CLeafDirTree created[0x%x] sz:%d"), this, 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()

	{

	__PRINT1(_L("~CLeafDirTree[0x%x]"), this);

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

		}