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

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