// 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);
                TInt r = iLruList.Insert(aNodeUsed, 0);
                return r;
                }
            }
        }
    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

