sl@0: // Copyright (c) 2008-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of the License "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // f32\sfat\sl_leafdir_cache.cpp
sl@0: // 
sl@0: //
sl@0: 
sl@0: //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
sl@0: //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
sl@0: //!!
sl@0: //!! WARNING!! DO NOT edit this file !! '\sfat' component is obsolete and is not being used. '\sfat32'replaces it
sl@0: //!!
sl@0: //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
sl@0: //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
sl@0: 
sl@0: 
sl@0: #include "sl_std.h"
sl@0: #include "sl_leafdir_cache.h"
sl@0: 
sl@0: 
sl@0: 
sl@0: 
sl@0: /**
sl@0: Get the lru list count
sl@0: 
sl@0: @return the count of lru list
sl@0: */
sl@0: TInt CLeafDirTree::LruCount() const 
sl@0:     {
sl@0:     return iLruList.Count();
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Count currently cached items
sl@0: 
sl@0: @return the number of currently cached items
sl@0: */
sl@0: TInt CLeafDirCache::CacheCount() const 
sl@0:     {
sl@0:     return iTree->LruCount();
sl@0:     }
sl@0: 
sl@0: //---------------------------------------------------------------------------------------------------------------------------------
sl@0: /**
sl@0: Default constructor of TDirPosition, a data structure that represents a location of directory
sl@0: */
sl@0: TLeafDirData::TLeafDirData()
sl@0:              :iClusterNum(0),iMRUPos(0,0)
sl@0:     {
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Constructor of TDirPosition, a data structure that represents a location of directory
sl@0: 
sl@0: @param  aClusterNum     the cluster number of the directory stores   
sl@0: */
sl@0: TLeafDirData::TLeafDirData(TUint aClusterNum)
sl@0:              :iClusterNum(aClusterNum),iMRUPos(0,0)
sl@0:     {
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Constructor of TDirPosition, a data structure that represents a location of directory
sl@0: 
sl@0: @param  aClusterNum     the cluster number of the directory stores   
sl@0: */
sl@0: TLeafDirData::TLeafDirData(TUint aClusterNum, const TEntryPos& aMRUPos)
sl@0:              :iClusterNum(aClusterNum),iMRUPos(aMRUPos.Cluster(), aMRUPos.Pos())
sl@0:     {
sl@0:     }
sl@0: 
sl@0: 
sl@0: 
sl@0: /**
sl@0: Factory fucntion of tree nodes
sl@0: 
sl@0: @param  aOwnerTree  a pointer of the tree that owns this node   
sl@0: @param  aPathName   the directory path this node represents
sl@0: @param  aDirPos     the location of the directory this node represents   
sl@0: @param  aType       the type of the node   
sl@0: */
sl@0: CLeafDirTreeNode* CLeafDirTreeNode::NewL(CLeafDirTree* aOwnerTree, const TDesC& aPathName, const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType)
sl@0:     {
sl@0:     CLeafDirTreeNode* self = new(ELeave) CLeafDirTreeNode(aDirPos, aType);
sl@0:     CleanupStack::PushL(self);
sl@0:     self->ConstructL(aOwnerTree, aPathName);
sl@0:     CleanupStack::Pop();
sl@0:     return self;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Constructor of tree nodes
sl@0: 
sl@0: @param  aDirPos     the location of the directory this node represents   
sl@0: @param  aType       the type of the node   
sl@0: */
sl@0: CLeafDirTreeNode::CLeafDirTreeNode(const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType)
sl@0:                   :iParent(NULL), iLeafDirData(aDirPos), iNodeType(aType)
sl@0:     {
sl@0:     }
sl@0: 
sl@0: /**
sl@0: 2nd phase constructor of tree nodes
sl@0: 
sl@0: @param  aOwnerTree  a pointer of the tree that owns this node   
sl@0: @param  aPathName   the directory path this node represents
sl@0: */
sl@0: void CLeafDirTreeNode::ConstructL(CLeafDirTree* aOwnerTree, const TDesC& aPath)
sl@0:     {
sl@0:     if (aOwnerTree == NULL)
sl@0:         {
sl@0:         ASSERT(0);
sl@0:         User::Leave(KErrArgument);
sl@0:         }
sl@0:     iOwnerTree = aOwnerTree;
sl@0:     iPath.CreateL(aPath);
sl@0: #ifdef _DEBUG
sl@0:     iOwnerTree->AddToObjectContainerL(this);
sl@0: #endif //_DEBUG
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Destructor of tree nodes
sl@0: 
sl@0: @pre    The node should already be removed from its parent before being deleted
sl@0: */
sl@0: CLeafDirTreeNode::~CLeafDirTreeNode()
sl@0:     {
sl@0: #ifdef _DEBUG
sl@0:     TRAPD(err, iOwnerTree->RemoveFromObjectContainerL(this));
sl@0:     ASSERT(err == KErrNone);
sl@0: #endif // _DEBUG
sl@0:     iPath.Close();
sl@0:     iChildren.Close();
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Set type of the node
sl@0: 
sl@0: @param  aType   the type to be set
sl@0: */
sl@0: void CLeafDirTreeNode::SetType(const CLeafDirTreeNode::TLeafDirTreeNodeType aType)
sl@0:     {
sl@0:     // Root node can not be reset type
sl@0:     if (iNodeType == CLeafDirTreeNode::ERoot)
sl@0:         return;
sl@0:     iNodeType = aType;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Set path of the directory the node represents
sl@0: 
sl@0: @param  aPath   the path to be set   
sl@0: */
sl@0: void CLeafDirTreeNode::SetPathL(const TDesC& aPath)
sl@0:     {
sl@0:     ASSERT(aPath.Length() > 0);
sl@0:     if (iPath.Length() < aPath.Length())
sl@0:         {
sl@0:         TInt err = iPath.ReAlloc(aPath.Length());
sl@0:         ASSERT(err==KErrNone);
sl@0:         User::LeaveIfError(err);
sl@0:         }
sl@0:     iPath = aPath;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Removes from the children list, sets aNode's parent NULL, does not delete aNode
sl@0: 
sl@0: @param  aNode   the node to be removed   
sl@0: */
sl@0: TInt CLeafDirTreeNode::RemoveChild(CLeafDirTreeNode* aNode)
sl@0:     {
sl@0:     ASSERT(aNode);
sl@0:     if (aNode->IsRoot())
sl@0:         {
sl@0:         ASSERT(0);
sl@0:         return KErrArgument;
sl@0:         }
sl@0:     
sl@0:     if (iChildren.Count() > 0)
sl@0:         {
sl@0:         for (TInt i = iChildren.Count() - 1; i >= 0; i--)
sl@0:             {
sl@0:             if (iChildren[i] == aNode)
sl@0:                 {
sl@0:                 iChildren.Remove(i);
sl@0:                 aNode->SetParent(NULL);
sl@0:                 return KErrNone;
sl@0:                 }
sl@0:             }
sl@0:         }
sl@0:     return KErrNotFound;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Add a new child node to self
sl@0: 
sl@0: @pre    aNode should have been removed from its original parent
sl@0: @param  aNode   the node to be added   
sl@0: */
sl@0: void CLeafDirTreeNode::MakeItChildL(CLeafDirTreeNode* aNode)
sl@0:     {
sl@0:     ASSERT(aNode->Parent() == NULL);
sl@0:     if (aNode->IsRoot())
sl@0:         {
sl@0:         ASSERT(0);
sl@0:         User::Leave(KErrArgument);
sl@0:         }
sl@0:     iChildren.AppendL(aNode);
sl@0:     aNode->SetParent(this);
sl@0:     }
sl@0: 
sl@0: 
sl@0: /**
sl@0: Factory function of CLeafDirTree
sl@0: 
sl@0: @param  aLimit  the maximum number of 'leaf' nodes allowed of the tree   
sl@0: */
sl@0: CLeafDirTree* CLeafDirTree::NewL(TUint32 aSize)
sl@0:     {
sl@0:     CLeafDirTree* self = new(ELeave) CLeafDirTree(aSize);
sl@0:     CleanupStack::PushL(self);
sl@0:     self->ConstructL();
sl@0:     CleanupStack::Pop();
sl@0:     return self;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Constructor of CLeafDirTree
sl@0: 
sl@0: @param  aLimit  the maximum number of 'leaf' nodes allowed of the tree   
sl@0: */
sl@0: CLeafDirTree::CLeafDirTree(TUint32 aSize)
sl@0: :iSize(aSize)
sl@0:     {
sl@0:     }
sl@0: 
sl@0: _LIT(KRootDirPath, "\\");
sl@0: /**
sl@0: 2nd phase constructor of CLeafDirTree
sl@0: */
sl@0: void CLeafDirTree::ConstructL()
sl@0:     {
sl@0:     TLeafDirData rootDirPos(0);
sl@0:     CLeafDirTreeNode* root = CLeafDirTreeNode::NewL(this, KRootDirPath, rootDirPos, CLeafDirTreeNode::ERoot);
sl@0:     iRoot = root;
sl@0:     iRoot->SetType(CLeafDirTreeNode::ERoot);
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Destructor of CLeafDirTree
sl@0: */
sl@0: CLeafDirTree::~CLeafDirTree()
sl@0:     {
sl@0:     Reset();
sl@0:     delete iRoot;
sl@0:     iLruList.Close();
sl@0: 
sl@0: #ifdef _DEBUG
sl@0:     iContainer.Close();
sl@0: #endif //_DEBUG
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Free all the nodes from the tree except root node
sl@0: */
sl@0: void CLeafDirTree::Reset()
sl@0:     {
sl@0:     TInt err = KErrNone;
sl@0:     TRAP(err, DeleteSubTreeL(iRoot));
sl@0:     ASSERT(err == KErrNone);
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Search for a node by directory path
sl@0: 
sl@0: @param  aPath       the path as the key to search in the tree
sl@0: @param  aNodeFound  in return, the node found 
sl@0: @param  aDirPos     the location of the directory
sl@0: @return KErrNone    if a node found
sl@0:         KErrNotFound if no node is found
sl@0: */
sl@0: TInt CLeafDirTree::Search(const TDesC& aPath, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aDirPos)
sl@0:     {
sl@0:     return (DoSearch(aPath, iRoot, aNodeFound, aDirPos));
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Search for a node by directory path, start from children of aNodeToStart but do not include aNodeToStart.
sl@0: 
sl@0: @param  aPath           the path as the key to search in the tree
sl@0: @param  aNodeToStart    the node whose children to start with 
sl@0: @param  aNodeFound      in return, the node found 
sl@0: @param  aDirPos         the location of the directory
sl@0: @return KErrNone        if a node found
sl@0:         KErrNotFound    if no node is found
sl@0: */
sl@0: TInt CLeafDirTree::DoSearch(const TDesC& aPath, CLeafDirTreeNode* aNodeToStart, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aLeafDirData)
sl@0:     {
sl@0:     RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children();
sl@0:     TInt currentPos = currentLevel.Count() - 1;
sl@0:     // Current path in search
sl@0:     TPtrC currentPath;
sl@0:     currentPath.Set(aPath);
sl@0:     while (currentLevel.Count() > 0 && currentPos >= 0)
sl@0:         {
sl@0:         CLeafDirTreeNode* currentNode = currentLevel[currentPos];
sl@0:         TPtrC currentNodePath;
sl@0:         currentNodePath.Set(currentNode->Path());
sl@0:         TInt foundPos = currentPath.FindF(currentNodePath);
sl@0:         // If current child's path is part of the searching path, 
sl@0:         //  go to next level
sl@0:         //  E.g.: current child's path = "1\2\3\", searching path = "1\2\3\5\".
sl@0:         if (foundPos == 0 && currentNodePath.Length() < currentPath.Length())
sl@0:             {
sl@0:             currentPath.Set(currentPath.Mid(currentNodePath.Length()));
sl@0:             currentLevel = currentNode->Children();
sl@0:             currentPos = currentLevel.Count() - 1;
sl@0:             continue;
sl@0:             }
sl@0:         // If current child's path matches current searching path,
sl@0:         //  check the node type.
sl@0:         else if (foundPos == 0 && currentNodePath.Length() == currentPath.Length())
sl@0:             {
sl@0:             if (currentNode->IsPureIntermediary())
sl@0:             // If found is 'pure intermediary', it is not cached. 
sl@0:                 {
sl@0:                 return KErrNotFound;
sl@0:                 }
sl@0:             // Otherwise, we have got a cache hit!
sl@0:             MakeMostRecentlyUsed(currentNode);
sl@0:             aNodeFound = currentNode;
sl@0:             aLeafDirData = currentNode->LeafDirData();
sl@0:             return KErrNone;
sl@0:             }
sl@0:         // else, go through current level
sl@0:         currentPos--;
sl@0:         }
sl@0:     // If there is no child or we have not found any matching node,
sl@0:     //  return KErrNotFound
sl@0:     return KErrNotFound;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Find the longest common 'path' between two paths.
sl@0: Note: not the longest common 'string'.
sl@0: 
sl@0: @param  aPathA  path A
sl@0: @param  aPathB  path B 
sl@0: @return     the length of the longest common path found
sl@0:             KErrNotFound    if no node is found
sl@0: */
sl@0: TInt FindLongestCommonPath(const TDesC& aPathA, const TDesC& aPathB)
sl@0:     {
sl@0:     const TInt compareLength = Min(aPathA.Length(), aPathB.Length());
sl@0:     if (compareLength <= 0)
sl@0:         {
sl@0:         return KErrArgument;
sl@0:         }
sl@0:     TInt i = 0;
sl@0:     TInt lastPathDelimiterPos = KErrNotFound;
sl@0:     while (i < compareLength && aPathA[i] == aPathB[i])
sl@0:         {
sl@0:         if (aPathA[i] == '\\')
sl@0:             {
sl@0:             lastPathDelimiterPos = i;
sl@0:             }
sl@0:         i++;
sl@0:         }
sl@0:     
sl@0:     if (i == 0)
sl@0:         {
sl@0:         return KErrNotFound;
sl@0:         }
sl@0:     return lastPathDelimiterPos;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Insert a new node to the tree according to the path 
sl@0: 
sl@0: @param  aPath           the path of the new node to be inserted
sl@0: @param  aDirPos         the position of the new node to be inserted
sl@0: @param  aNodeInserted   in return, the node that has been successfully inserted
sl@0: */
sl@0: void CLeafDirTree::InsertL(const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted)
sl@0:     {
sl@0:     ASSERT(aPath.Length() > 0);
sl@0:     // aPath should always start and end with a '\\'.
sl@0:     if (aPath[0] == '\\' && aPath[aPath.Length() - 1] =='\\')
sl@0:         {
sl@0:         if (aPath.Length() > 1)
sl@0:             {
sl@0:             TPtrC path;
sl@0:             path.Set(aPath.Mid(1));
sl@0:             DoInsertL(iRoot, path, aLeafDirData, aNodeInserted);
sl@0:             }
sl@0:         }
sl@0:     else
sl@0:         {
sl@0:         ASSERT(0);
sl@0:         User::Leave(KErrBadName);
sl@0:         }
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Implementation of the insertion algorithm 
sl@0: 
sl@0: @param  aNodeToStart    the node whose children to start with
sl@0: @param  aPath           the path of the new node to be inserted
sl@0: @param  aDirPos         the position of the new node to be inserted
sl@0: @param  aNodeInserted   in return, the node that has been successfully inserted
sl@0: */
sl@0: void CLeafDirTree::DoInsertL(CLeafDirTreeNode* aNodeToStart, const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted)
sl@0:     {
sl@0:     CLeafDirTreeNode* currentParent = aNodeToStart;
sl@0:     TInt foundPos = 0;
sl@0:     RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children();
sl@0:     TInt currentPos = currentLevel.Count() - 1;
sl@0:     TPtrC currentPath;
sl@0:     currentPath.Set(aPath);
sl@0:     while (currentLevel.Count() > 0 && currentPos >= 0)
sl@0:         {
sl@0:         CLeafDirTreeNode* currentNode = currentLevel[currentPos];
sl@0:         TPtrC currentNodePath;
sl@0:         currentNodePath.Set(currentNode->Path());
sl@0: 
sl@0:         // If current node is contained by aPath.
sl@0:         //  E.g.: current node = "1\2\3\", currentPath = "1\2\3\5\"
sl@0:         //  In this case, we need to go to next level,
sl@0:         //  discard logged position (currentPos) in this level as we don't need to come back.
sl@0:         foundPos = currentPath.FindF(currentNodePath);
sl@0:         if (foundPos == 0 && currentNodePath.Length() < currentPath.Length())
sl@0:             {
sl@0:             currentParent = currentNode;
sl@0:             currentLevel = currentNode->Children();
sl@0:             currentPos = currentLevel.Count() - 1;
sl@0:             currentPath.Set(currentPath.Mid(currentNodePath.Length()));
sl@0:             continue;
sl@0:             }
sl@0: 
sl@0:         // If current node's path contains aPath 
sl@0:         //  E.g.: current node = "1\2\3\4\", currentPath = "1\2\3\"
sl@0:         //  We need to split current node to two nodes and return.
sl@0:         foundPos = currentNodePath.FindF(currentPath);
sl@0:         if (foundPos == 0 && currentNodePath.Length() > currentPath.Length())
sl@0:             {
sl@0:             CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeafIntermediary);
sl@0:             currentParent->MakeItChildL(newNode);
sl@0:             
sl@0:             TPtrC restPath;
sl@0:             restPath.Set(currentNodePath.Mid(currentPath.Length()));
sl@0:             currentNode->SetPathL(restPath);
sl@0:             currentParent->RemoveChild(currentNode);
sl@0:             
sl@0:             newNode->MakeItChildL(currentNode);
sl@0:             AddOntoLruL(newNode);
sl@0:             aNodeInserted = newNode;
sl@0:             return;
sl@0:             }
sl@0: 
sl@0:         // If current node's path equals aPath,
sl@0:         //  change the node type if it is necessary
sl@0:         if (foundPos == 0 && currentNodePath.Length() == currentPath.Length())
sl@0:             {
sl@0:             // Check node type, if already cached, update Lru list and return.
sl@0:             if (currentNode->IsLeaf() || currentNode->IsLeafIntermediary())
sl@0:                 {
sl@0:                 currentNode->SetLeafDirData(aLeafDirData);
sl@0:                 aNodeInserted = currentNode;
sl@0:                 MakeMostRecentlyUsed(currentNode);
sl@0:                 return;
sl@0:                 }
sl@0:             // If it has not been cached yet, i.e., it is a 'pure intermediary' node,
sl@0:             //  cache the node and put it onto Lru list
sl@0:             else if(currentNode->IsPureIntermediary())
sl@0:                 {
sl@0:                 currentNode->SetLeafDirData(aLeafDirData);
sl@0:                 currentNode->SetType(CLeafDirTreeNode::ELeafIntermediary);
sl@0:                 AddOntoLruL(currentNode);
sl@0:                 aNodeInserted = currentNode;
sl@0:                 return;
sl@0:                 }
sl@0:             }
sl@0:         
sl@0:         // If none of above is the case (i.e. haven't found exact match or paths 
sl@0:         //  are not contained by each other), we need to find the first common part 
sl@0:         //  between each child and aPath to share path data.
sl@0:         foundPos = FindLongestCommonPath(currentNodePath, currentPath);
sl@0:         // If a common part of path is found, we need to create a pure intermediary node to share
sl@0:         //  the common part of path data, and create a new leaf node for the target path.
sl@0:         if (foundPos > 0)
sl@0:             {
sl@0:             TPtrC commonPath;
sl@0:             commonPath.Set(currentNodePath.Left(foundPos + 1));
sl@0: 
sl@0:             currentNodePath.Set(currentNodePath.Mid(foundPos + 1));
sl@0:             TPtrC newLeafPath;
sl@0:             newLeafPath.Set(currentPath.Mid(foundPos + 1));
sl@0: 
sl@0:             // Add new pureintermediary node, set it as child of current parent
sl@0:             TLeafDirData dummyPos(0);
sl@0:             CLeafDirTreeNode* newPureIntermediaryNode = CLeafDirTreeNode::NewL(this, commonPath, dummyPos, CLeafDirTreeNode::EPureIntermediary);
sl@0:             currentParent->MakeItChildL(newPureIntermediaryNode);
sl@0: 
sl@0:             // Remove current child from aNodeToStart, do not need to change
sl@0:             //  node type of aNodeToStart
sl@0:             currentParent->RemoveChild(currentNode);
sl@0: 
sl@0:             // Modify current pathData, make it child of new node
sl@0:             newPureIntermediaryNode->MakeItChildL(currentNode);
sl@0:             currentNode->SetPathL(currentNodePath);
sl@0: 
sl@0:             // Add new leaf node as a child of the new pure intermediary node
sl@0:             CLeafDirTreeNode* newLeafNode = CLeafDirTreeNode::NewL(this, newLeafPath, aLeafDirData, CLeafDirTreeNode::ELeaf);
sl@0:             newPureIntermediaryNode->MakeItChildL(newLeafNode);
sl@0:             aNodeInserted = newLeafNode;
sl@0:             AddOntoLruL(newLeafNode);
sl@0:             return;
sl@0:             }
sl@0: 
sl@0:         // Otherwise, move on within this level.
sl@0:         currentPos--;
sl@0:         }
sl@0:     
sl@0:     // No match case found, add a new node straight on at current level
sl@0:     CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeaf);
sl@0: 
sl@0:     if (currentParent->IsLeaf())        // might be the root node
sl@0:         {
sl@0:         currentParent->SetType(CLeafDirTreeNode::ELeafIntermediary);
sl@0:         }
sl@0:     currentParent->MakeItChildL(newNode);
sl@0:     aNodeInserted = newNode;
sl@0:     AddOntoLruL(newNode);
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Remove nodes with a specific position from the tree  
sl@0: Note: multiple nodes may have the same position value, as directories can be accessed
sl@0:     by both long names and short names:
sl@0: E.g.:   "\\LongDirName01\\LongDirName02\\LongDirName03\\"
sl@0:         "\\LongDirName01\\LongDirName02\\LONGDI~1\\"
sl@0:         "\\LongDirName01\\LONGDI~1\\LongDirName03\\"
sl@0:         "\\LONGDI~1\\LongDirName02\\LongDirName03\\"
sl@0: 
sl@0: @param  aDirPos     the position of the nodes to be removed
sl@0: */
sl@0: void CLeafDirTree::RemoveDirL(const TLeafDirData& aDirPos)
sl@0:     {
sl@0:     // remove alias nodes in cache
sl@0:     for (TInt i = iLruList.Count() - 1; i >= 0; i--)
sl@0:         {
sl@0:         if (iLruList[i]->StartClusterNum() == aDirPos.iClusterNum)
sl@0:             {
sl@0:             RemoveFromCacheL(iLruList[i]);
sl@0:             }
sl@0:         }
sl@0:     }
sl@0: 
sl@0: 
sl@0: /**
sl@0: Update the MRU entry position of the tree nodes.
sl@0: @param  aLeafDirData    contains the index of the cache node and the new MRU entry position 
sl@0: */
sl@0: void CLeafDirTree::UpdateMRUPos(const TLeafDirData& aLeafDirData)
sl@0:     {
sl@0:     // update alias nodes in cache
sl@0:     for (TInt i = iLruList.Count() - 1; i >= 0; i--)
sl@0:         {
sl@0:         if (iLruList[i]->StartClusterNum() == aLeafDirData.iClusterNum)
sl@0:             {
sl@0:             iLruList[i]->SetLeafDirData(aLeafDirData);
sl@0:             }
sl@0:         }
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Remove a 'leaf' node, i.e. a leaf node or leaf intermediary node.
sl@0: 
sl@0: @param  aNodeTodelete the node to be removed
sl@0: */
sl@0: void CLeafDirTree::RemoveFromCacheL(CLeafDirTreeNode* aNodeToDelete)
sl@0:     {
sl@0:     ASSERT(aNodeToDelete->IsLeaf() || aNodeToDelete->IsLeafIntermediary());
sl@0:     CLeafDirTreeNode* parent = aNodeToDelete->Parent(); 
sl@0:     // Deleting 'leaf intermediary' nodes:
sl@0:     if (aNodeToDelete->IsLeafIntermediary())
sl@0:         {
sl@0:         // If there is no child, error! The 'tree' is corrupted.
sl@0:         if (aNodeToDelete->Children().Count() == 0)
sl@0:             {
sl@0:             ASSERT(0);
sl@0:             User::Leave(KErrCorrupt);
sl@0:             }
sl@0:         // If there is only one child, 'promote' the child, delete self
sl@0:         else if (aNodeToDelete->Children().Count() == 1)
sl@0:             {
sl@0:             CLeafDirTreeNode* child = (aNodeToDelete->Children())[0];
sl@0:             TFileName newPath = aNodeToDelete->Path();
sl@0:             newPath.Append(child->Path());
sl@0:             child->SetPathL(newPath);
sl@0:             aNodeToDelete->RemoveChild(child);
sl@0:             parent->MakeItChildL(child);
sl@0: 
sl@0:             parent->RemoveChild(aNodeToDelete);
sl@0:             RemoveFromLru(aNodeToDelete);
sl@0:             delete aNodeToDelete;
sl@0:             return;
sl@0:             }
sl@0:         // If there are more than one child, just change node type to 'pure intermediary',
sl@0:         //  but remove self from Lru list.
sl@0:         else
sl@0:             {
sl@0:             aNodeToDelete->SetType(CLeafDirTreeNode::EPureIntermediary);
sl@0:             RemoveFromLru(aNodeToDelete);
sl@0:             return;
sl@0:             }
sl@0:         }
sl@0:     // Deleting 'leaf' nodes:
sl@0:     else
sl@0:         {
sl@0:         // If 'parent' is a 'leaf intermediary' node
sl@0:         if (parent->IsLeafIntermediary())
sl@0:             {
sl@0:             // If there is no other sibling, change parent's node type to 'leaf',
sl@0:             //  otherwise, leave parent's type as 'leaf intermediary' 
sl@0:             if (parent->Children().Count() == 1)
sl@0:                 {
sl@0:                 parent->SetType(CLeafDirTreeNode::ELeaf);
sl@0:                 }
sl@0:             parent->RemoveChild(aNodeToDelete);
sl@0:             RemoveFromLru(aNodeToDelete);
sl@0:             delete aNodeToDelete;
sl@0:             return;
sl@0:             }
sl@0:         // If 'parent' is 'pure intermediary'
sl@0:         else if (parent->IsPureIntermediary())
sl@0:             {
sl@0:             // If there is no sibling nodes, the tree is corrupted,
sl@0:             //  as 'pure intermediary' node should always have more than one child.
sl@0:             if (parent->Children().Count() <= 1)
sl@0:                 {
sl@0:                 ASSERT(0);
sl@0:                 User::Leave(KErrCorrupt);
sl@0:                 }
sl@0:             // If there is only one sibling node, we need to merge the sibling node
sl@0:             //  to 'parent'.
sl@0:             else if (parent->Children().Count() == 2)
sl@0:                 {
sl@0:                 // Promote the sibling node, delete both parent and self
sl@0:                 CLeafDirTreeNode* sibling = (parent->Children())[0] ;
sl@0:                 if (sibling == aNodeToDelete)
sl@0:                     {
sl@0:                     sibling = (parent->Children())[1];
sl@0:                     }
sl@0:                 TFileName newPath = aNodeToDelete->Parent()->Path();
sl@0:                 newPath.Append(sibling->Path());
sl@0:                 sibling->SetPathL(newPath);
sl@0:                 parent->RemoveChild(sibling);
sl@0:                 parent->Parent()->MakeItChildL(sibling);
sl@0:                 
sl@0:                 parent->RemoveChild(aNodeToDelete);
sl@0:                 RemoveFromLru(aNodeToDelete);
sl@0:                 delete aNodeToDelete;
sl@0:                 aNodeToDelete = NULL;
sl@0: 
sl@0:                 parent->Parent()->RemoveChild(parent);
sl@0:                 delete parent;
sl@0:                 return;
sl@0:                 }
sl@0:             // Else if there are more than 2 sibling nodes, simply delete self.
sl@0:             else
sl@0:                 {
sl@0:                 parent->RemoveChild(aNodeToDelete);
sl@0:                 RemoveFromLru(aNodeToDelete);
sl@0:                 delete aNodeToDelete;
sl@0:                 aNodeToDelete = NULL;
sl@0:                 return;
sl@0:                 }
sl@0:             }
sl@0:         // If 'parent' is root node, delete self straightaway
sl@0:         else if (aNodeToDelete->Parent()->IsRoot())
sl@0:             {
sl@0:             aNodeToDelete->Parent()->RemoveChild(aNodeToDelete);
sl@0:             RemoveFromLru(aNodeToDelete);
sl@0:             delete aNodeToDelete;
sl@0:             aNodeToDelete = NULL;
sl@0:             return;
sl@0:             }
sl@0:         // If 'parent' is 'leaf', the tree is corrupted. 
sl@0:         else if (aNodeToDelete->Parent()->IsLeaf())
sl@0:             {
sl@0:             ASSERT(0);
sl@0:             User::Leave(KErrCorrupt);
sl@0:             }
sl@0:         }
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Find the leftest node
sl@0: Note: the leftest node must be a 'leaf' node
sl@0: 
sl@0: @param  aNodeToStart    a node whose children to start with
sl@0: @return the leftest node
sl@0: */
sl@0: CLeafDirTreeNode* CLeafDirTree::FindLeftestLeafNode(CLeafDirTreeNode* aNodeToStart) const
sl@0:     {
sl@0:     CLeafDirTreeNode* current = aNodeToStart;
sl@0:     while (current->Children().Count() > 0)
sl@0:         {
sl@0:         current = (current->Children())[0];
sl@0:         }
sl@0:     return current;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Delete all nodes derived from aNodeToStart, except itself.
sl@0: 
sl@0: @param  aNodeToStart    a node whose children to start with
sl@0: */
sl@0: void CLeafDirTree::DeleteSubTreeL(CLeafDirTreeNode* aNodeToStart)
sl@0:     {
sl@0:     while(aNodeToStart->Children().Count() > 0)
sl@0:         {
sl@0:         CLeafDirTreeNode* aLeafNode = FindLeftestLeafNode(aNodeToStart);
sl@0:         RemoveFromCacheL(aLeafNode);
sl@0:         }
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Make the a node most recent used in LRU list
sl@0: 
sl@0: @param  aNodeUsed   the node to be made MRU
sl@0: */
sl@0: TInt CLeafDirTree::MakeMostRecentlyUsed(CLeafDirTreeNode* aNodeUsed)
sl@0:     {
sl@0:     for(TInt i = 0; i < iLruList.Count(); i++)
sl@0:         {
sl@0:         if (aNodeUsed == iLruList[i])
sl@0:             {
sl@0:             if (i == 0)
sl@0:                 {
sl@0:                 return KErrNone;
sl@0:                 }
sl@0:             else
sl@0:                 {
sl@0:                 iLruList.Remove(i);
sl@0:                 iLruList.Insert(aNodeUsed, 0);
sl@0:                 return KErrNone;
sl@0:                 }
sl@0:             }
sl@0:         }
sl@0:     return KErrNotFound;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Check cache limit, remove least-used cached item when necessary.
sl@0: */
sl@0: void CLeafDirTree::CheckLimitL()
sl@0:     {
sl@0:     const TInt cacheSize = iSize;
sl@0:     while (iLruList.Count() > cacheSize)
sl@0:         {
sl@0:         CLeafDirTreeNode* lruNode = LruNode();
sl@0:         RemoveFromCacheL(lruNode);
sl@0:         }
sl@0:     return;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Add new node onto cache list
sl@0: 
sl@0: @param  aNodeToAdd  the new node to be added onto cache list
sl@0: */
sl@0: void CLeafDirTree::AddOntoLruL(CLeafDirTreeNode* aNodeToAdd)
sl@0:     {
sl@0:     if (aNodeToAdd == NULL)
sl@0:         {
sl@0:         ASSERT(0);
sl@0:         User::Leave(KErrArgument);
sl@0:         }
sl@0:     
sl@0:     TInt r = iLruList.Insert(aNodeToAdd, 0);
sl@0:     if (r != KErrNone)
sl@0:         {
sl@0:         ASSERT(0);
sl@0:         User::Leave(KErrArgument);
sl@0:         }
sl@0:     CheckLimitL();
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Remove a node from cached list.
sl@0: 
sl@0: @param  aNodeToRemove   the node to be removed from the cache list
sl@0: */
sl@0: TInt CLeafDirTree::RemoveFromLru(CLeafDirTreeNode* aNodeToRemove)
sl@0:     {
sl@0:     for (TInt i = 0; i < iLruList.Count(); i++)
sl@0:         {
sl@0:         if (aNodeToRemove == iLruList[i])
sl@0:             {
sl@0:             iLruList.Remove(i);
sl@0:             return KErrNone;
sl@0:             }
sl@0:         }
sl@0:     return KErrNotFound;
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Return the least-recent-used node.
sl@0: 
sl@0: @return the least recent used node on cache
sl@0: */
sl@0: CLeafDirTreeNode* CLeafDirTree::LruNode()
sl@0:     {
sl@0:     if (iLruList.Count() > 0)
sl@0:         {
sl@0:         return iLruList[iLruList.Count() - 1];
sl@0:         }
sl@0:     return NULL;
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Factory function of CLeafDirCache
sl@0: 
sl@0: @param  aLimit  the cache size 
sl@0: */
sl@0: CLeafDirCache* CLeafDirCache::NewL(TUint32 aLimit)
sl@0:     {
sl@0:     CLeafDirCache* self = new(ELeave) CLeafDirCache(aLimit);
sl@0:     CleanupStack::PushL(self);
sl@0:     self->ConstructL();
sl@0:     CleanupStack::Pop(self);
sl@0:     return self;
sl@0:     }
sl@0: 
sl@0: /*
sl@0: 2nd phase constructor of CLeafDirCache
sl@0: */
sl@0: void CLeafDirCache::ConstructL()
sl@0:     {
sl@0:     CLeafDirTree* tree = CLeafDirTree::NewL(iSize);
sl@0:     iTree = tree;
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Destructor of CLeafDirCache
sl@0: */
sl@0: CLeafDirCache::~CLeafDirCache()
sl@0:     {
sl@0:     delete iTree;
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Constructor of CLeafDirCache
sl@0: 
sl@0: @param aLimit the cache size
sl@0: */
sl@0: CLeafDirCache::CLeafDirCache(TUint32 aSize)
sl@0:               :iSize(aSize)
sl@0:     {
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Reset cache, delete all memory allocated
sl@0: */
sl@0: void CLeafDirCache::Reset()
sl@0:     {
sl@0:     iTree->Reset();
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Cache interface for searching operations.
sl@0: 
sl@0: @param  aPath   the path of the directory to search for
sl@0: @param  aDirPos the location of the direcotry found
sl@0: @return KErrNone if a cached direcotry is found,
sl@0:         KErrBadName if the path is incorrect, otherwise 
sl@0:         other system wide error code
sl@0: */
sl@0: TInt CLeafDirCache::FindInCache(const TDesC& aPath, TLeafDirData& aLeafDirData) const 
sl@0:     {
sl@0:     if (aPath[0] == '\\')
sl@0:         {
sl@0:         TPtrC path;
sl@0:         path.Set(aPath.Mid(1));
sl@0:         CLeafDirTreeNode* dummy = NULL;
sl@0:         return (iTree->Search(path, dummy, aLeafDirData));
sl@0:         }
sl@0:     else
sl@0:         {
sl@0:         return KErrBadName;
sl@0:         }
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Cache interface for insertion operations.
sl@0: 
sl@0: @param  aPath   the path of the directory to be added
sl@0: @param  aDirPos the location of the direcotry to be added
sl@0: */
sl@0: void CLeafDirCache::AddToCacheL(const TDesC& aPath, const TLeafDirData& aDirPos)
sl@0:     {
sl@0:     if (aPath.Length() == 1 && aPath[0] == '\\')
sl@0:         return;
sl@0: 
sl@0:     CLeafDirTreeNode* dummy = NULL;
sl@0:     iTree->InsertL(aPath, aDirPos, dummy);
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Cache interface for deletion oeprations.
sl@0: Remove all the cached directories with the same specfied position
sl@0: 
sl@0: @param  aDirPos the location of the direcotry to be removed
sl@0: */
sl@0: void CLeafDirCache::RemoveDirL(const TLeafDirData& aDirPos)
sl@0:     {
sl@0:     iTree->RemoveDirL(aDirPos);
sl@0:     }
sl@0: 
sl@0: /**
sl@0: Update the MRU entry position of the cached leaf dir.
sl@0: @param  aLeafDirData    contains a cluster number as the index of the leaf dir and the new MRU entry position 
sl@0: */
sl@0: void CLeafDirCache::UpdateMRUPos(const TLeafDirData& aLeafDirData)
sl@0:     {
sl@0:     iTree->UpdateMRUPos(aLeafDirData);
sl@0:     }
sl@0: /*
sl@0:  * Helper functions of CLeafDirTree for debugging & testing use
sl@0:  */
sl@0: #ifdef _DEBUG
sl@0: /*
sl@0: All node created will be added to the container of its owner tree, so that we can calculate
sl@0:     the number of objects created.
sl@0: 
sl@0: @param  aNodeToAdd  the newly created node to be add to object container 
sl@0: */
sl@0: void CLeafDirTree::AddToObjectContainerL(CLeafDirTreeNode* aNodeToAdd)
sl@0:     {
sl@0:     iContainer.AppendL(aNodeToAdd);
sl@0:     }
sl@0: 
sl@0: /*
sl@0: A node is removed from object container if it is deleted.
sl@0: 
sl@0: @param  aNodeToRemove   the node to be deleted 
sl@0: */
sl@0: void CLeafDirTree::RemoveFromObjectContainerL(CLeafDirTreeNode* aNodeToRemove)
sl@0:     {
sl@0:     for (TInt i = 0; i < iContainer.Count(); i++)
sl@0:         {
sl@0:         if (aNodeToRemove == iContainer[i])
sl@0:             {
sl@0:             iContainer.Remove(i);
sl@0:             return;
sl@0:             }
sl@0:         }
sl@0:     ASSERT(0);
sl@0:     User::Leave(KErrNotFound);
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Print out current tree content
sl@0: */
sl@0: void CLeafDirTree::DumpTreeContentL() const
sl@0:     {
sl@0:     RPointerArray<CLeafDirTreeNode>* nodeStack = new(ELeave) RPointerArray<CLeafDirTreeNode>(4);
sl@0:     RFs fs;
sl@0:     fs.Connect();
sl@0:     const TUint32 debugRegister = DebugRegister();
sl@0:     fs.SetDebugRegister(debugRegister|KFSYS);
sl@0:     if (iRoot != NULL)
sl@0:         {
sl@0:         nodeStack->Insert(iRoot, 0);
sl@0:         while(nodeStack->Count() > 0)
sl@0:             {
sl@0:             CLeafDirTreeNode* current = (*nodeStack)[0];
sl@0:             if (current->Parent() != NULL)
sl@0:                 {
sl@0:                 __PRINT3(_L("(\"%S\") -> \"%S\" : (%d)\n"), &current->Parent()->Path(), &current->Path(), current->StartClusterNum());
sl@0:                 }
sl@0:             else
sl@0:                 {
sl@0:                 __PRINT2(_L("\"%S\" : (%d)\n"), &current->Path(), current->StartClusterNum());              
sl@0:                 }
sl@0: 
sl@0:             nodeStack->Remove(0);
sl@0:             
sl@0:             TInt currentCount = current->Children().Count();
sl@0:             if (currentCount > 0)
sl@0:                 {
sl@0:                 RPointerArray<CLeafDirTreeNode> children = current->Children();
sl@0:                 for (TInt i = 0; i < currentCount; i++)
sl@0:                     {
sl@0:                     nodeStack->Insert(children[i], 0);
sl@0:                     }
sl@0:                 }
sl@0:             }
sl@0:         }
sl@0: 
sl@0:     fs.SetDebugRegister(debugRegister);
sl@0:     fs.Close();
sl@0:     nodeStack->Close();
sl@0:     delete nodeStack;
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Print out current cache content
sl@0: */
sl@0: void CLeafDirCache::DumpCacheContentL() const
sl@0:     {
sl@0:     iTree->DumpTreeContentL();
sl@0:     }
sl@0: 
sl@0: /*
sl@0: Count of all the nodes
sl@0: */
sl@0: TInt CLeafDirCache::NodeCount() const
sl@0:     {
sl@0:     return iTree->ObjectCount();
sl@0:     }
sl@0: #endif // _DEBUG
sl@0: