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

                 }

             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