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

// 

//

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

//!!

//!! WARNING!! DO NOT edit this file !! '\sfat' component is obsolete and is not being used. '\sfat32'replaces it

//!!

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

#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