25 Get the lru list count |
34 Get the lru list count |
26 |
35 |
27 @return the count of lru list |
36 @return the count of lru list |
28 */ |
37 */ |
29 TInt CLeafDirTree::LruCount() const |
38 TInt CLeafDirTree::LruCount() const |
30 { |
39 { |
31 return iLruList.Count(); |
40 return iLruList.Count(); |
32 } |
41 } |
33 |
42 |
34 /** |
43 /** |
35 Count currently cached items |
44 Count currently cached items |
36 |
45 |
37 @return the number of currently cached items |
46 @return the number of currently cached items |
38 */ |
47 */ |
39 TInt CLeafDirCache::CacheCount() const |
48 TInt CLeafDirCache::CacheCount() const |
40 { |
49 { |
41 return iTree->LruCount(); |
50 return iTree->LruCount(); |
42 } |
51 } |
43 |
52 |
44 //--------------------------------------------------------------------------------------------------------------------------------- |
53 //--------------------------------------------------------------------------------------------------------------------------------- |
45 /** |
54 /** |
46 Default constructor of TDirPosition, a data structure that represents a location of directory |
55 Default constructor of TDirPosition, a data structure that represents a location of directory |
47 */ |
56 */ |
48 TLeafDirData::TLeafDirData() |
57 TLeafDirData::TLeafDirData() |
49 :iClusterNum(0),iMRUPos(0,0) |
58 :iClusterNum(0),iMRUPos(0,0) |
50 { |
59 { |
51 } |
60 } |
52 |
61 |
53 /** |
62 /** |
54 Constructor of TDirPosition, a data structure that represents a location of directory |
63 Constructor of TDirPosition, a data structure that represents a location of directory |
55 |
64 |
56 @param aClusterNum the cluster number of the directory stores |
65 @param aClusterNum the cluster number of the directory stores |
57 */ |
66 */ |
58 TLeafDirData::TLeafDirData(TUint aClusterNum) |
67 TLeafDirData::TLeafDirData(TUint aClusterNum) |
59 :iClusterNum(aClusterNum),iMRUPos(0,0) |
68 :iClusterNum(aClusterNum),iMRUPos(0,0) |
60 { |
69 { |
61 } |
70 } |
62 |
71 |
63 /** |
72 /** |
64 Constructor of TDirPosition, a data structure that represents a location of directory |
73 Constructor of TDirPosition, a data structure that represents a location of directory |
65 |
74 |
66 @param aClusterNum the cluster number of the directory stores |
75 @param aClusterNum the cluster number of the directory stores |
67 */ |
76 */ |
68 TLeafDirData::TLeafDirData(TUint aClusterNum, const TEntryPos& aMRUPos) |
77 TLeafDirData::TLeafDirData(TUint aClusterNum, const TEntryPos& aMRUPos) |
69 :iClusterNum(aClusterNum),iMRUPos(aMRUPos.Cluster(), aMRUPos.Pos()) |
78 :iClusterNum(aClusterNum),iMRUPos(aMRUPos.Cluster(), aMRUPos.Pos()) |
70 { |
79 { |
71 } |
80 } |
72 |
81 |
73 |
82 |
74 |
83 |
75 /** |
84 /** |
76 Factory fucntion of tree nodes |
85 Factory fucntion of tree nodes |
77 |
86 |
78 @param aOwnerTree a pointer of the tree that owns this node |
87 @param aOwnerTree a pointer of the tree that owns this node |
79 @param aPathName the directory path this node represents |
88 @param aPathName the directory path this node represents |
80 @param aDirPos the location of the directory this node represents |
89 @param aDirPos the location of the directory this node represents |
81 @param aType the type of the node |
90 @param aType the type of the node |
82 */ |
91 */ |
83 CLeafDirTreeNode* CLeafDirTreeNode::NewL(CLeafDirTree* aOwnerTree, const TDesC& aPathName, const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType) |
92 CLeafDirTreeNode* CLeafDirTreeNode::NewL(CLeafDirTree* aOwnerTree, const TDesC& aPathName, const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType) |
84 { |
93 { |
85 CLeafDirTreeNode* self = new(ELeave) CLeafDirTreeNode(aDirPos, aType); |
94 CLeafDirTreeNode* self = new(ELeave) CLeafDirTreeNode(aDirPos, aType); |
86 CleanupStack::PushL(self); |
95 CleanupStack::PushL(self); |
87 self->ConstructL(aOwnerTree, aPathName); |
96 self->ConstructL(aOwnerTree, aPathName); |
88 CleanupStack::Pop(); |
97 CleanupStack::Pop(); |
89 return self; |
98 return self; |
90 } |
99 } |
91 |
100 |
92 /** |
101 /** |
93 Constructor of tree nodes |
102 Constructor of tree nodes |
94 |
103 |
95 @param aDirPos the location of the directory this node represents |
104 @param aDirPos the location of the directory this node represents |
96 @param aType the type of the node |
105 @param aType the type of the node |
97 */ |
106 */ |
98 CLeafDirTreeNode::CLeafDirTreeNode(const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType) |
107 CLeafDirTreeNode::CLeafDirTreeNode(const TLeafDirData& aDirPos, TLeafDirTreeNodeType aType) |
99 :iParent(NULL), iLeafDirData(aDirPos), iNodeType(aType) |
108 :iParent(NULL), iLeafDirData(aDirPos), iNodeType(aType) |
100 { |
109 { |
101 } |
110 } |
102 |
111 |
103 /** |
112 /** |
104 2nd phase constructor of tree nodes |
113 2nd phase constructor of tree nodes |
105 |
114 |
106 @param aOwnerTree a pointer of the tree that owns this node |
115 @param aOwnerTree a pointer of the tree that owns this node |
107 @param aPathName the directory path this node represents |
116 @param aPathName the directory path this node represents |
108 */ |
117 */ |
109 void CLeafDirTreeNode::ConstructL(CLeafDirTree* aOwnerTree, const TDesC& aPath) |
118 void CLeafDirTreeNode::ConstructL(CLeafDirTree* aOwnerTree, const TDesC& aPath) |
110 { |
119 { |
111 if (aOwnerTree == NULL) |
120 if (aOwnerTree == NULL) |
112 { |
121 { |
113 ASSERT(0); |
122 ASSERT(0); |
114 User::Leave(KErrArgument); |
123 User::Leave(KErrArgument); |
115 } |
124 } |
116 iOwnerTree = aOwnerTree; |
125 iOwnerTree = aOwnerTree; |
117 iPath.CreateL(aPath); |
126 iPath.CreateL(aPath); |
118 #ifdef _DEBUG |
127 #ifdef _DEBUG |
119 iOwnerTree->AddToObjectContainerL(this); |
128 iOwnerTree->AddToObjectContainerL(this); |
120 #endif //_DEBUG |
129 #endif //_DEBUG |
121 } |
130 } |
122 |
131 |
123 /** |
132 /** |
124 Destructor of tree nodes |
133 Destructor of tree nodes |
125 |
134 |
126 @pre The node should already be removed from its parent before being deleted |
135 @pre The node should already be removed from its parent before being deleted |
127 */ |
136 */ |
128 CLeafDirTreeNode::~CLeafDirTreeNode() |
137 CLeafDirTreeNode::~CLeafDirTreeNode() |
129 { |
138 { |
130 #ifdef _DEBUG |
139 #ifdef _DEBUG |
131 TRAPD(err, iOwnerTree->RemoveFromObjectContainerL(this)); |
140 TRAPD(err, iOwnerTree->RemoveFromObjectContainerL(this)); |
132 ASSERT(err == KErrNone); |
141 ASSERT(err == KErrNone); |
133 #endif // _DEBUG |
142 #endif // _DEBUG |
134 iPath.Close(); |
143 iPath.Close(); |
135 iChildren.Close(); |
144 iChildren.Close(); |
136 } |
145 } |
137 |
146 |
138 /** |
147 /** |
139 Set type of the node |
148 Set type of the node |
140 |
149 |
141 @param aType the type to be set |
150 @param aType the type to be set |
142 */ |
151 */ |
143 void CLeafDirTreeNode::SetType(const CLeafDirTreeNode::TLeafDirTreeNodeType aType) |
152 void CLeafDirTreeNode::SetType(const CLeafDirTreeNode::TLeafDirTreeNodeType aType) |
144 { |
153 { |
145 // Root node can not be reset type |
154 // Root node can not be reset type |
146 if (iNodeType == CLeafDirTreeNode::ERoot) |
155 if (iNodeType == CLeafDirTreeNode::ERoot) |
147 return; |
156 return; |
148 iNodeType = aType; |
157 iNodeType = aType; |
149 } |
158 } |
150 |
159 |
151 /** |
160 /** |
152 Set path of the directory the node represents |
161 Set path of the directory the node represents |
153 |
162 |
154 @param aPath the path to be set |
163 @param aPath the path to be set |
155 */ |
164 */ |
156 void CLeafDirTreeNode::SetPathL(const TDesC& aPath) |
165 void CLeafDirTreeNode::SetPathL(const TDesC& aPath) |
157 { |
166 { |
158 ASSERT(aPath.Length() > 0); |
167 ASSERT(aPath.Length() > 0); |
159 if (iPath.Length() < aPath.Length()) |
168 if (iPath.Length() < aPath.Length()) |
160 { |
169 { |
161 TInt err = iPath.ReAlloc(aPath.Length()); |
170 TInt err = iPath.ReAlloc(aPath.Length()); |
162 ASSERT(err==KErrNone); |
171 ASSERT(err==KErrNone); |
163 User::LeaveIfError(err); |
172 User::LeaveIfError(err); |
164 } |
173 } |
165 iPath = aPath; |
174 iPath = aPath; |
166 } |
175 } |
167 |
176 |
168 /** |
177 /** |
169 Removes from the children list, sets aNode's parent NULL, does not delete aNode |
178 Removes from the children list, sets aNode's parent NULL, does not delete aNode |
170 |
179 |
171 @param aNode the node to be removed |
180 @param aNode the node to be removed |
172 */ |
181 */ |
173 TInt CLeafDirTreeNode::RemoveChild(CLeafDirTreeNode* aNode) |
182 TInt CLeafDirTreeNode::RemoveChild(CLeafDirTreeNode* aNode) |
174 { |
183 { |
175 ASSERT(aNode); |
184 ASSERT(aNode); |
176 if (aNode->IsRoot()) |
185 if (aNode->IsRoot()) |
177 { |
186 { |
178 ASSERT(0); |
187 ASSERT(0); |
179 return KErrArgument; |
188 return KErrArgument; |
180 } |
189 } |
181 |
190 |
182 if (iChildren.Count() > 0) |
191 if (iChildren.Count() > 0) |
183 { |
192 { |
184 for (TInt i = iChildren.Count() - 1; i >= 0; i--) |
193 for (TInt i = iChildren.Count() - 1; i >= 0; i--) |
185 { |
194 { |
186 if (iChildren[i] == aNode) |
195 if (iChildren[i] == aNode) |
187 { |
196 { |
188 iChildren.Remove(i); |
197 iChildren.Remove(i); |
189 aNode->SetParent(NULL); |
198 aNode->SetParent(NULL); |
190 return KErrNone; |
199 return KErrNone; |
191 } |
200 } |
192 } |
201 } |
193 } |
202 } |
194 return KErrNotFound; |
203 return KErrNotFound; |
195 } |
204 } |
196 |
205 |
197 /** |
206 /** |
198 Add a new child node to self |
207 Add a new child node to self |
199 |
208 |
200 @pre aNode should have been removed from its original parent |
209 @pre aNode should have been removed from its original parent |
201 @param aNode the node to be added |
210 @param aNode the node to be added |
202 */ |
211 */ |
203 void CLeafDirTreeNode::MakeItChildL(CLeafDirTreeNode* aNode) |
212 void CLeafDirTreeNode::MakeItChildL(CLeafDirTreeNode* aNode) |
204 { |
213 { |
205 ASSERT(aNode->Parent() == NULL); |
214 ASSERT(aNode->Parent() == NULL); |
206 if (aNode->IsRoot()) |
215 if (aNode->IsRoot()) |
207 { |
216 { |
208 ASSERT(0); |
217 ASSERT(0); |
209 User::Leave(KErrArgument); |
218 User::Leave(KErrArgument); |
210 } |
219 } |
211 iChildren.AppendL(aNode); |
220 iChildren.AppendL(aNode); |
212 aNode->SetParent(this); |
221 aNode->SetParent(this); |
213 } |
222 } |
214 |
223 |
215 |
224 |
216 /** |
225 /** |
217 Factory function of CLeafDirTree |
226 Factory function of CLeafDirTree |
218 |
227 |
219 @param aLimit the maximum number of 'leaf' nodes allowed of the tree |
228 @param aLimit the maximum number of 'leaf' nodes allowed of the tree |
220 */ |
229 */ |
221 CLeafDirTree* CLeafDirTree::NewL(TUint32 aSize) |
230 CLeafDirTree* CLeafDirTree::NewL(TUint32 aSize) |
222 { |
231 { |
223 CLeafDirTree* self = new(ELeave) CLeafDirTree(aSize); |
232 CLeafDirTree* self = new(ELeave) CLeafDirTree(aSize); |
224 CleanupStack::PushL(self); |
233 CleanupStack::PushL(self); |
225 self->ConstructL(); |
234 self->ConstructL(); |
226 CleanupStack::Pop(); |
235 CleanupStack::Pop(); |
227 return self; |
236 return self; |
228 } |
237 } |
229 |
238 |
230 /** |
239 /** |
231 Constructor of CLeafDirTree |
240 Constructor of CLeafDirTree |
232 |
241 |
233 @param aLimit the maximum number of 'leaf' nodes allowed of the tree |
242 @param aLimit the maximum number of 'leaf' nodes allowed of the tree |
234 */ |
243 */ |
235 CLeafDirTree::CLeafDirTree(TUint32 aSize) |
244 CLeafDirTree::CLeafDirTree(TUint32 aSize) |
236 :iSize(aSize) |
245 :iSize(aSize) |
237 { |
246 { |
238 } |
247 } |
239 |
248 |
240 _LIT(KRootDirPath, "\\"); |
249 _LIT(KRootDirPath, "\\"); |
241 /** |
250 /** |
242 2nd phase constructor of CLeafDirTree |
251 2nd phase constructor of CLeafDirTree |
243 */ |
252 */ |
244 void CLeafDirTree::ConstructL() |
253 void CLeafDirTree::ConstructL() |
245 { |
254 { |
246 TLeafDirData rootDirPos(0); |
255 TLeafDirData rootDirPos(0); |
247 CLeafDirTreeNode* root = CLeafDirTreeNode::NewL(this, KRootDirPath, rootDirPos, CLeafDirTreeNode::ERoot); |
256 CLeafDirTreeNode* root = CLeafDirTreeNode::NewL(this, KRootDirPath, rootDirPos, CLeafDirTreeNode::ERoot); |
248 iRoot = root; |
257 iRoot = root; |
249 iRoot->SetType(CLeafDirTreeNode::ERoot); |
258 iRoot->SetType(CLeafDirTreeNode::ERoot); |
250 } |
259 } |
251 |
260 |
252 /** |
261 /** |
253 Destructor of CLeafDirTree |
262 Destructor of CLeafDirTree |
254 */ |
263 */ |
255 CLeafDirTree::~CLeafDirTree() |
264 CLeafDirTree::~CLeafDirTree() |
256 { |
265 { |
257 Reset(); |
266 Reset(); |
258 delete iRoot; |
267 delete iRoot; |
259 iLruList.Close(); |
268 iLruList.Close(); |
260 |
269 |
261 #ifdef _DEBUG |
270 #ifdef _DEBUG |
262 iContainer.Close(); |
271 iContainer.Close(); |
263 #endif //_DEBUG |
272 #endif //_DEBUG |
264 } |
273 } |
265 |
274 |
266 /** |
275 /** |
267 Free all the nodes from the tree except root node |
276 Free all the nodes from the tree except root node |
268 */ |
277 */ |
269 void CLeafDirTree::Reset() |
278 void CLeafDirTree::Reset() |
270 { |
279 { |
271 TInt err = KErrNone; |
280 TInt err = KErrNone; |
272 TRAP(err, DeleteSubTreeL(iRoot)); |
281 TRAP(err, DeleteSubTreeL(iRoot)); |
273 ASSERT(err == KErrNone); |
282 ASSERT(err == KErrNone); |
274 } |
283 } |
275 |
284 |
276 /** |
285 /** |
277 Search for a node by directory path |
286 Search for a node by directory path |
278 |
287 |
279 @param aPath the path as the key to search in the tree |
288 @param aPath the path as the key to search in the tree |
280 @param aNodeFound in return, the node found |
289 @param aNodeFound in return, the node found |
281 @param aDirPos the location of the directory |
290 @param aDirPos the location of the directory |
282 @return KErrNone if a node found |
291 @return KErrNone if a node found |
283 KErrNotFound if no node is found |
292 KErrNotFound if no node is found |
284 */ |
293 */ |
285 TInt CLeafDirTree::Search(const TDesC& aPath, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aDirPos) |
294 TInt CLeafDirTree::Search(const TDesC& aPath, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aDirPos) |
286 { |
295 { |
287 return (DoSearch(aPath, iRoot, aNodeFound, aDirPos)); |
296 return (DoSearch(aPath, iRoot, aNodeFound, aDirPos)); |
288 } |
297 } |
289 |
298 |
290 /** |
299 /** |
291 Search for a node by directory path, start from children of aNodeToStart but do not include aNodeToStart. |
300 Search for a node by directory path, start from children of aNodeToStart but do not include aNodeToStart. |
292 |
301 |
293 @param aPath the path as the key to search in the tree |
302 @param aPath the path as the key to search in the tree |
294 @param aNodeToStart the node whose children to start with |
303 @param aNodeToStart the node whose children to start with |
295 @param aNodeFound in return, the node found |
304 @param aNodeFound in return, the node found |
296 @param aDirPos the location of the directory |
305 @param aDirPos the location of the directory |
297 @return KErrNone if a node found |
306 @return KErrNone if a node found |
298 KErrNotFound if no node is found |
307 KErrNotFound if no node is found |
299 */ |
308 */ |
300 TInt CLeafDirTree::DoSearch(const TDesC& aPath, CLeafDirTreeNode* aNodeToStart, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aLeafDirData) |
309 TInt CLeafDirTree::DoSearch(const TDesC& aPath, CLeafDirTreeNode* aNodeToStart, CLeafDirTreeNode*& aNodeFound, TLeafDirData& aLeafDirData) |
301 { |
310 { |
302 RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children(); |
311 RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children(); |
303 TInt currentPos = currentLevel.Count() - 1; |
312 TInt currentPos = currentLevel.Count() - 1; |
304 // Current path in search |
313 // Current path in search |
305 TPtrC currentPath; |
314 TPtrC currentPath; |
306 currentPath.Set(aPath); |
315 currentPath.Set(aPath); |
307 while (currentLevel.Count() > 0 && currentPos >= 0) |
316 while (currentLevel.Count() > 0 && currentPos >= 0) |
308 { |
317 { |
309 CLeafDirTreeNode* currentNode = currentLevel[currentPos]; |
318 CLeafDirTreeNode* currentNode = currentLevel[currentPos]; |
310 TPtrC currentNodePath; |
319 TPtrC currentNodePath; |
311 currentNodePath.Set(currentNode->Path()); |
320 currentNodePath.Set(currentNode->Path()); |
312 TInt foundPos = currentPath.FindF(currentNodePath); |
321 TInt foundPos = currentPath.FindF(currentNodePath); |
313 // If current child's path is part of the searching path, |
322 // If current child's path is part of the searching path, |
314 // go to next level |
323 // go to next level |
315 // E.g.: current child's path = "1\2\3\", searching path = "1\2\3\5\". |
324 // E.g.: current child's path = "1\2\3\", searching path = "1\2\3\5\". |
316 if (foundPos == 0 && currentNodePath.Length() < currentPath.Length()) |
325 if (foundPos == 0 && currentNodePath.Length() < currentPath.Length()) |
317 { |
326 { |
318 currentPath.Set(currentPath.Mid(currentNodePath.Length())); |
327 currentPath.Set(currentPath.Mid(currentNodePath.Length())); |
319 currentLevel = currentNode->Children(); |
328 currentLevel = currentNode->Children(); |
320 currentPos = currentLevel.Count() - 1; |
329 currentPos = currentLevel.Count() - 1; |
321 continue; |
330 continue; |
322 } |
331 } |
323 // If current child's path matches current searching path, |
332 // If current child's path matches current searching path, |
324 // check the node type. |
333 // check the node type. |
325 else if (foundPos == 0 && currentNodePath.Length() == currentPath.Length()) |
334 else if (foundPos == 0 && currentNodePath.Length() == currentPath.Length()) |
326 { |
335 { |
327 if (currentNode->IsPureIntermediary()) |
336 if (currentNode->IsPureIntermediary()) |
328 // If found is 'pure intermediary', it is not cached. |
337 // If found is 'pure intermediary', it is not cached. |
329 { |
338 { |
330 return KErrNotFound; |
339 return KErrNotFound; |
331 } |
340 } |
332 // Otherwise, we have got a cache hit! |
341 // Otherwise, we have got a cache hit! |
333 MakeMostRecentlyUsed(currentNode); |
342 MakeMostRecentlyUsed(currentNode); |
334 aNodeFound = currentNode; |
343 aNodeFound = currentNode; |
335 aLeafDirData = currentNode->LeafDirData(); |
344 aLeafDirData = currentNode->LeafDirData(); |
336 return KErrNone; |
345 return KErrNone; |
337 } |
346 } |
338 // else, go through current level |
347 // else, go through current level |
339 currentPos--; |
348 currentPos--; |
340 } |
349 } |
341 // If there is no child or we have not found any matching node, |
350 // If there is no child or we have not found any matching node, |
342 // return KErrNotFound |
351 // return KErrNotFound |
343 return KErrNotFound; |
352 return KErrNotFound; |
344 } |
353 } |
345 |
354 |
346 /** |
355 /** |
347 Find the longest common 'path' between two paths. |
356 Find the longest common 'path' between two paths. |
348 Note: not the longest common 'string'. |
357 Note: not the longest common 'string'. |
349 |
358 |
350 @param aPathA path A |
359 @param aPathA path A |
351 @param aPathB path B |
360 @param aPathB path B |
352 @return the length of the longest common path found |
361 @return the length of the longest common path found |
353 KErrNotFound if no node is found |
362 KErrNotFound if no node is found |
354 */ |
363 */ |
355 TInt FindLongestCommonPath(const TDesC& aPathA, const TDesC& aPathB) |
364 TInt FindLongestCommonPath(const TDesC& aPathA, const TDesC& aPathB) |
356 { |
365 { |
357 const TInt compareLength = Min(aPathA.Length(), aPathB.Length()); |
366 const TInt compareLength = Min(aPathA.Length(), aPathB.Length()); |
358 if (compareLength <= 0) |
367 if (compareLength <= 0) |
359 { |
368 { |
360 return KErrArgument; |
369 return KErrArgument; |
361 } |
370 } |
362 TInt i = 0; |
371 TInt i = 0; |
363 TInt lastPathDelimiterPos = KErrNotFound; |
372 TInt lastPathDelimiterPos = KErrNotFound; |
364 while (i < compareLength && aPathA[i] == aPathB[i]) |
373 while (i < compareLength && aPathA[i] == aPathB[i]) |
365 { |
374 { |
366 if (aPathA[i] == '\\') |
375 if (aPathA[i] == '\\') |
367 { |
376 { |
368 lastPathDelimiterPos = i; |
377 lastPathDelimiterPos = i; |
369 } |
378 } |
370 i++; |
379 i++; |
371 } |
380 } |
372 |
381 |
373 if (i == 0) |
382 if (i == 0) |
374 { |
383 { |
375 return KErrNotFound; |
384 return KErrNotFound; |
376 } |
385 } |
377 return lastPathDelimiterPos; |
386 return lastPathDelimiterPos; |
378 } |
387 } |
379 |
388 |
380 /** |
389 /** |
381 Insert a new node to the tree according to the path |
390 Insert a new node to the tree according to the path |
382 |
391 |
383 @param aPath the path of the new node to be inserted |
392 @param aPath the path of the new node to be inserted |
384 @param aDirPos the position of the new node to be inserted |
393 @param aDirPos the position of the new node to be inserted |
385 @param aNodeInserted in return, the node that has been successfully inserted |
394 @param aNodeInserted in return, the node that has been successfully inserted |
386 */ |
395 */ |
387 void CLeafDirTree::InsertL(const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted) |
396 void CLeafDirTree::InsertL(const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted) |
388 { |
397 { |
389 ASSERT(aPath.Length() > 0); |
398 ASSERT(aPath.Length() > 0); |
390 // aPath should always start and end with a '\\'. |
399 // aPath should always start and end with a '\\'. |
391 if (aPath[0] == '\\' && aPath[aPath.Length() - 1] =='\\') |
400 if (aPath[0] == '\\' && aPath[aPath.Length() - 1] =='\\') |
392 { |
401 { |
393 if (aPath.Length() > 1) |
402 if (aPath.Length() > 1) |
394 { |
403 { |
395 TPtrC path; |
404 TPtrC path; |
396 path.Set(aPath.Mid(1)); |
405 path.Set(aPath.Mid(1)); |
397 DoInsertL(iRoot, path, aLeafDirData, aNodeInserted); |
406 DoInsertL(iRoot, path, aLeafDirData, aNodeInserted); |
398 } |
407 } |
399 } |
408 } |
400 else |
409 else |
401 { |
410 { |
402 ASSERT(0); |
411 ASSERT(0); |
403 User::Leave(KErrBadName); |
412 User::Leave(KErrBadName); |
404 } |
413 } |
405 } |
414 } |
406 |
415 |
407 /** |
416 /** |
408 Implementation of the insertion algorithm |
417 Implementation of the insertion algorithm |
409 |
418 |
410 @param aNodeToStart the node whose children to start with |
419 @param aNodeToStart the node whose children to start with |
411 @param aPath the path of the new node to be inserted |
420 @param aPath the path of the new node to be inserted |
412 @param aDirPos the position of the new node to be inserted |
421 @param aDirPos the position of the new node to be inserted |
413 @param aNodeInserted in return, the node that has been successfully inserted |
422 @param aNodeInserted in return, the node that has been successfully inserted |
414 */ |
423 */ |
415 void CLeafDirTree::DoInsertL(CLeafDirTreeNode* aNodeToStart, const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted) |
424 void CLeafDirTree::DoInsertL(CLeafDirTreeNode* aNodeToStart, const TDesC& aPath, const TLeafDirData& aLeafDirData, CLeafDirTreeNode*& aNodeInserted) |
416 { |
425 { |
417 CLeafDirTreeNode* currentParent = aNodeToStart; |
426 CLeafDirTreeNode* currentParent = aNodeToStart; |
418 TInt foundPos = 0; |
427 TInt foundPos = 0; |
419 RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children(); |
428 RPointerArray<CLeafDirTreeNode> currentLevel = aNodeToStart->Children(); |
420 TInt currentPos = currentLevel.Count() - 1; |
429 TInt currentPos = currentLevel.Count() - 1; |
421 TPtrC currentPath; |
430 TPtrC currentPath; |
422 currentPath.Set(aPath); |
431 currentPath.Set(aPath); |
423 while (currentLevel.Count() > 0 && currentPos >= 0) |
432 while (currentLevel.Count() > 0 && currentPos >= 0) |
424 { |
433 { |
425 CLeafDirTreeNode* currentNode = currentLevel[currentPos]; |
434 CLeafDirTreeNode* currentNode = currentLevel[currentPos]; |
426 TPtrC currentNodePath; |
435 TPtrC currentNodePath; |
427 currentNodePath.Set(currentNode->Path()); |
436 currentNodePath.Set(currentNode->Path()); |
428 |
437 |
429 // If current node is contained by aPath. |
438 // If current node is contained by aPath. |
430 // E.g.: current node = "1\2\3\", currentPath = "1\2\3\5\" |
439 // E.g.: current node = "1\2\3\", currentPath = "1\2\3\5\" |
431 // In this case, we need to go to next level, |
440 // In this case, we need to go to next level, |
432 // discard logged position (currentPos) in this level as we don't need to come back. |
441 // discard logged position (currentPos) in this level as we don't need to come back. |
433 foundPos = currentPath.FindF(currentNodePath); |
442 foundPos = currentPath.FindF(currentNodePath); |
434 if (foundPos == 0 && currentNodePath.Length() < currentPath.Length()) |
443 if (foundPos == 0 && currentNodePath.Length() < currentPath.Length()) |
435 { |
444 { |
436 currentParent = currentNode; |
445 currentParent = currentNode; |
437 currentLevel = currentNode->Children(); |
446 currentLevel = currentNode->Children(); |
438 currentPos = currentLevel.Count() - 1; |
447 currentPos = currentLevel.Count() - 1; |
439 currentPath.Set(currentPath.Mid(currentNodePath.Length())); |
448 currentPath.Set(currentPath.Mid(currentNodePath.Length())); |
440 continue; |
449 continue; |
441 } |
450 } |
442 |
451 |
443 // If current node's path contains aPath |
452 // If current node's path contains aPath |
444 // E.g.: current node = "1\2\3\4\", currentPath = "1\2\3\" |
453 // E.g.: current node = "1\2\3\4\", currentPath = "1\2\3\" |
445 // We need to split current node to two nodes and return. |
454 // We need to split current node to two nodes and return. |
446 foundPos = currentNodePath.FindF(currentPath); |
455 foundPos = currentNodePath.FindF(currentPath); |
447 if (foundPos == 0 && currentNodePath.Length() > currentPath.Length()) |
456 if (foundPos == 0 && currentNodePath.Length() > currentPath.Length()) |
448 { |
457 { |
449 CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeafIntermediary); |
458 CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeafIntermediary); |
450 currentParent->MakeItChildL(newNode); |
459 currentParent->MakeItChildL(newNode); |
451 |
460 |
452 TPtrC restPath; |
461 TPtrC restPath; |
453 restPath.Set(currentNodePath.Mid(currentPath.Length())); |
462 restPath.Set(currentNodePath.Mid(currentPath.Length())); |
454 currentNode->SetPathL(restPath); |
463 currentNode->SetPathL(restPath); |
455 currentParent->RemoveChild(currentNode); |
464 currentParent->RemoveChild(currentNode); |
456 |
465 |
457 newNode->MakeItChildL(currentNode); |
466 newNode->MakeItChildL(currentNode); |
458 AddOntoLruL(newNode); |
467 AddOntoLruL(newNode); |
459 aNodeInserted = newNode; |
468 aNodeInserted = newNode; |
460 return; |
469 return; |
461 } |
470 } |
462 |
471 |
463 // If current node's path equals aPath, |
472 // If current node's path equals aPath, |
464 // change the node type if it is necessary |
473 // change the node type if it is necessary |
465 if (foundPos == 0 && currentNodePath.Length() == currentPath.Length()) |
474 if (foundPos == 0 && currentNodePath.Length() == currentPath.Length()) |
466 { |
475 { |
467 // Check node type, if already cached, update Lru list and return. |
476 // Check node type, if already cached, update Lru list and return. |
468 if (currentNode->IsLeaf() || currentNode->IsLeafIntermediary()) |
477 if (currentNode->IsLeaf() || currentNode->IsLeafIntermediary()) |
469 { |
478 { |
470 currentNode->SetLeafDirData(aLeafDirData); |
479 currentNode->SetLeafDirData(aLeafDirData); |
471 aNodeInserted = currentNode; |
480 aNodeInserted = currentNode; |
472 MakeMostRecentlyUsed(currentNode); |
481 MakeMostRecentlyUsed(currentNode); |
473 return; |
482 return; |
474 } |
483 } |
475 // If it has not been cached yet, i.e., it is a 'pure intermediary' node, |
484 // If it has not been cached yet, i.e., it is a 'pure intermediary' node, |
476 // cache the node and put it onto Lru list |
485 // cache the node and put it onto Lru list |
477 else if(currentNode->IsPureIntermediary()) |
486 else if(currentNode->IsPureIntermediary()) |
478 { |
487 { |
479 currentNode->SetLeafDirData(aLeafDirData); |
488 currentNode->SetLeafDirData(aLeafDirData); |
480 currentNode->SetType(CLeafDirTreeNode::ELeafIntermediary); |
489 currentNode->SetType(CLeafDirTreeNode::ELeafIntermediary); |
481 AddOntoLruL(currentNode); |
490 AddOntoLruL(currentNode); |
482 aNodeInserted = currentNode; |
491 aNodeInserted = currentNode; |
483 return; |
492 return; |
484 } |
493 } |
485 } |
494 } |
486 |
495 |
487 // If none of above is the case (i.e. haven't found exact match or paths |
496 // If none of above is the case (i.e. haven't found exact match or paths |
488 // are not contained by each other), we need to find the first common part |
497 // are not contained by each other), we need to find the first common part |
489 // between each child and aPath to share path data. |
498 // between each child and aPath to share path data. |
490 foundPos = FindLongestCommonPath(currentNodePath, currentPath); |
499 foundPos = FindLongestCommonPath(currentNodePath, currentPath); |
491 // If a common part of path is found, we need to create a pure intermediary node to share |
500 // If a common part of path is found, we need to create a pure intermediary node to share |
492 // the common part of path data, and create a new leaf node for the target path. |
501 // the common part of path data, and create a new leaf node for the target path. |
493 if (foundPos > 0) |
502 if (foundPos > 0) |
494 { |
503 { |
495 TPtrC commonPath; |
504 TPtrC commonPath; |
496 commonPath.Set(currentNodePath.Left(foundPos + 1)); |
505 commonPath.Set(currentNodePath.Left(foundPos + 1)); |
497 |
506 |
498 currentNodePath.Set(currentNodePath.Mid(foundPos + 1)); |
507 currentNodePath.Set(currentNodePath.Mid(foundPos + 1)); |
499 TPtrC newLeafPath; |
508 TPtrC newLeafPath; |
500 newLeafPath.Set(currentPath.Mid(foundPos + 1)); |
509 newLeafPath.Set(currentPath.Mid(foundPos + 1)); |
501 |
510 |
502 // Add new pureintermediary node, set it as child of current parent |
511 // Add new pureintermediary node, set it as child of current parent |
503 TLeafDirData dummyPos(0); |
512 TLeafDirData dummyPos(0); |
504 CLeafDirTreeNode* newPureIntermediaryNode = CLeafDirTreeNode::NewL(this, commonPath, dummyPos, CLeafDirTreeNode::EPureIntermediary); |
513 CLeafDirTreeNode* newPureIntermediaryNode = CLeafDirTreeNode::NewL(this, commonPath, dummyPos, CLeafDirTreeNode::EPureIntermediary); |
505 currentParent->MakeItChildL(newPureIntermediaryNode); |
514 currentParent->MakeItChildL(newPureIntermediaryNode); |
506 |
515 |
507 // Remove current child from aNodeToStart, do not need to change |
516 // Remove current child from aNodeToStart, do not need to change |
508 // node type of aNodeToStart |
517 // node type of aNodeToStart |
509 currentParent->RemoveChild(currentNode); |
518 currentParent->RemoveChild(currentNode); |
510 |
519 |
511 // Modify current pathData, make it child of new node |
520 // Modify current pathData, make it child of new node |
512 newPureIntermediaryNode->MakeItChildL(currentNode); |
521 newPureIntermediaryNode->MakeItChildL(currentNode); |
513 currentNode->SetPathL(currentNodePath); |
522 currentNode->SetPathL(currentNodePath); |
514 |
523 |
515 // Add new leaf node as a child of the new pure intermediary node |
524 // Add new leaf node as a child of the new pure intermediary node |
516 CLeafDirTreeNode* newLeafNode = CLeafDirTreeNode::NewL(this, newLeafPath, aLeafDirData, CLeafDirTreeNode::ELeaf); |
525 CLeafDirTreeNode* newLeafNode = CLeafDirTreeNode::NewL(this, newLeafPath, aLeafDirData, CLeafDirTreeNode::ELeaf); |
517 newPureIntermediaryNode->MakeItChildL(newLeafNode); |
526 newPureIntermediaryNode->MakeItChildL(newLeafNode); |
518 aNodeInserted = newLeafNode; |
527 aNodeInserted = newLeafNode; |
519 AddOntoLruL(newLeafNode); |
528 AddOntoLruL(newLeafNode); |
520 return; |
529 return; |
521 } |
530 } |
522 |
531 |
523 // Otherwise, move on within this level. |
532 // Otherwise, move on within this level. |
524 currentPos--; |
533 currentPos--; |
525 } |
534 } |
526 |
535 |
527 // No match case found, add a new node straight on at current level |
536 // No match case found, add a new node straight on at current level |
528 CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeaf); |
537 CLeafDirTreeNode* newNode = CLeafDirTreeNode::NewL(this, currentPath, aLeafDirData, CLeafDirTreeNode::ELeaf); |
529 |
538 |
530 if (currentParent->IsLeaf()) // might be the root node |
539 if (currentParent->IsLeaf()) // might be the root node |
531 { |
540 { |
532 currentParent->SetType(CLeafDirTreeNode::ELeafIntermediary); |
541 currentParent->SetType(CLeafDirTreeNode::ELeafIntermediary); |
533 } |
542 } |
534 currentParent->MakeItChildL(newNode); |
543 currentParent->MakeItChildL(newNode); |
535 aNodeInserted = newNode; |
544 aNodeInserted = newNode; |
536 AddOntoLruL(newNode); |
545 AddOntoLruL(newNode); |
537 } |
546 } |
538 |
547 |
539 /** |
548 /** |
540 Remove nodes with a specific position from the tree |
549 Remove nodes with a specific position from the tree |
541 Note: multiple nodes may have the same position value, as directories can be accessed |
550 Note: multiple nodes may have the same position value, as directories can be accessed |
542 by both long names and short names: |
551 by both long names and short names: |
543 E.g.: "\\LongDirName01\\LongDirName02\\LongDirName03\\" |
552 E.g.: "\\LongDirName01\\LongDirName02\\LongDirName03\\" |
544 "\\LongDirName01\\LongDirName02\\LONGDI~1\\" |
553 "\\LongDirName01\\LongDirName02\\LONGDI~1\\" |
545 "\\LongDirName01\\LONGDI~1\\LongDirName03\\" |
554 "\\LongDirName01\\LONGDI~1\\LongDirName03\\" |
546 "\\LONGDI~1\\LongDirName02\\LongDirName03\\" |
555 "\\LONGDI~1\\LongDirName02\\LongDirName03\\" |
547 |
556 |
548 @param aDirPos the position of the nodes to be removed |
557 @param aDirPos the position of the nodes to be removed |
549 */ |
558 */ |
550 void CLeafDirTree::RemoveDirL(const TLeafDirData& aDirPos) |
559 void CLeafDirTree::RemoveDirL(const TLeafDirData& aDirPos) |
551 { |
560 { |
552 // remove alias nodes in cache |
561 // remove alias nodes in cache |
553 for (TInt i = iLruList.Count() - 1; i >= 0; i--) |
562 for (TInt i = iLruList.Count() - 1; i >= 0; i--) |
554 { |
563 { |
555 if (iLruList[i]->StartClusterNum() == aDirPos.iClusterNum) |
564 if (iLruList[i]->StartClusterNum() == aDirPos.iClusterNum) |
556 { |
565 { |
557 RemoveFromCacheL(iLruList[i]); |
566 RemoveFromCacheL(iLruList[i]); |
558 } |
567 } |
559 } |
568 } |
560 } |
569 } |
561 |
570 |
562 |
571 |
563 /** |
572 /** |
564 Update the MRU entry position of the tree nodes. |
573 Update the MRU entry position of the tree nodes. |
565 @param aLeafDirData contains the index of the cache node and the new MRU entry position |
574 @param aLeafDirData contains the index of the cache node and the new MRU entry position |
566 */ |
575 */ |
567 void CLeafDirTree::UpdateMRUPos(const TLeafDirData& aLeafDirData) |
576 void CLeafDirTree::UpdateMRUPos(const TLeafDirData& aLeafDirData) |
568 { |
577 { |
569 // update alias nodes in cache |
578 // update alias nodes in cache |
570 for (TInt i = iLruList.Count() - 1; i >= 0; i--) |
579 for (TInt i = iLruList.Count() - 1; i >= 0; i--) |
571 { |
580 { |
572 if (iLruList[i]->StartClusterNum() == aLeafDirData.iClusterNum) |
581 if (iLruList[i]->StartClusterNum() == aLeafDirData.iClusterNum) |
573 { |
582 { |
574 iLruList[i]->SetLeafDirData(aLeafDirData); |
583 iLruList[i]->SetLeafDirData(aLeafDirData); |
575 } |
584 } |
576 } |
585 } |
577 } |
586 } |
578 |
587 |
579 /** |
588 /** |
580 Remove a 'leaf' node, i.e. a leaf node or leaf intermediary node. |
589 Remove a 'leaf' node, i.e. a leaf node or leaf intermediary node. |
581 |
590 |
582 @param aNodeTodelete the node to be removed |
591 @param aNodeTodelete the node to be removed |
583 */ |
592 */ |
584 void CLeafDirTree::RemoveFromCacheL(CLeafDirTreeNode* aNodeToDelete) |
593 void CLeafDirTree::RemoveFromCacheL(CLeafDirTreeNode* aNodeToDelete) |
585 { |
594 { |
586 ASSERT(aNodeToDelete->IsLeaf() || aNodeToDelete->IsLeafIntermediary()); |
595 ASSERT(aNodeToDelete->IsLeaf() || aNodeToDelete->IsLeafIntermediary()); |
587 CLeafDirTreeNode* parent = aNodeToDelete->Parent(); |
596 CLeafDirTreeNode* parent = aNodeToDelete->Parent(); |
588 // Deleting 'leaf intermediary' nodes: |
597 // Deleting 'leaf intermediary' nodes: |
589 if (aNodeToDelete->IsLeafIntermediary()) |
598 if (aNodeToDelete->IsLeafIntermediary()) |
590 { |
599 { |
591 // If there is no child, error! The 'tree' is corrupted. |
600 // If there is no child, error! The 'tree' is corrupted. |
592 if (aNodeToDelete->Children().Count() == 0) |
601 if (aNodeToDelete->Children().Count() == 0) |
593 { |
602 { |
594 ASSERT(0); |
603 ASSERT(0); |
595 User::Leave(KErrCorrupt); |
604 User::Leave(KErrCorrupt); |
596 } |
605 } |
597 // If there is only one child, 'promote' the child, delete self |
606 // If there is only one child, 'promote' the child, delete self |
598 else if (aNodeToDelete->Children().Count() == 1) |
607 else if (aNodeToDelete->Children().Count() == 1) |
599 { |
608 { |
600 CLeafDirTreeNode* child = (aNodeToDelete->Children())[0]; |
609 CLeafDirTreeNode* child = (aNodeToDelete->Children())[0]; |
601 TFileName newPath = aNodeToDelete->Path(); |
610 TFileName newPath = aNodeToDelete->Path(); |
602 newPath.Append(child->Path()); |
611 newPath.Append(child->Path()); |
603 child->SetPathL(newPath); |
612 child->SetPathL(newPath); |
604 aNodeToDelete->RemoveChild(child); |
613 aNodeToDelete->RemoveChild(child); |
605 parent->MakeItChildL(child); |
614 parent->MakeItChildL(child); |
606 |
615 |
607 parent->RemoveChild(aNodeToDelete); |
616 parent->RemoveChild(aNodeToDelete); |
608 RemoveFromLru(aNodeToDelete); |
617 RemoveFromLru(aNodeToDelete); |
609 delete aNodeToDelete; |
618 delete aNodeToDelete; |
610 return; |
619 return; |
611 } |
620 } |
612 // If there are more than one child, just change node type to 'pure intermediary', |
621 // If there are more than one child, just change node type to 'pure intermediary', |
613 // but remove self from Lru list. |
622 // but remove self from Lru list. |
614 else |
623 else |
615 { |
624 { |
616 aNodeToDelete->SetType(CLeafDirTreeNode::EPureIntermediary); |
625 aNodeToDelete->SetType(CLeafDirTreeNode::EPureIntermediary); |
617 RemoveFromLru(aNodeToDelete); |
626 RemoveFromLru(aNodeToDelete); |
618 return; |
627 return; |
619 } |
628 } |
620 } |
629 } |
621 // Deleting 'leaf' nodes: |
630 // Deleting 'leaf' nodes: |
622 else |
631 else |
623 { |
632 { |
624 // If 'parent' is a 'leaf intermediary' node |
633 // If 'parent' is a 'leaf intermediary' node |
625 if (parent->IsLeafIntermediary()) |
634 if (parent->IsLeafIntermediary()) |
626 { |
635 { |
627 // If there is no other sibling, change parent's node type to 'leaf', |
636 // If there is no other sibling, change parent's node type to 'leaf', |
628 // otherwise, leave parent's type as 'leaf intermediary' |
637 // otherwise, leave parent's type as 'leaf intermediary' |
629 if (parent->Children().Count() == 1) |
638 if (parent->Children().Count() == 1) |
630 { |
639 { |
631 parent->SetType(CLeafDirTreeNode::ELeaf); |
640 parent->SetType(CLeafDirTreeNode::ELeaf); |
632 } |
641 } |
633 parent->RemoveChild(aNodeToDelete); |
642 parent->RemoveChild(aNodeToDelete); |
634 RemoveFromLru(aNodeToDelete); |
643 RemoveFromLru(aNodeToDelete); |
635 delete aNodeToDelete; |
644 delete aNodeToDelete; |
636 return; |
645 return; |
637 } |
646 } |
638 // If 'parent' is 'pure intermediary' |
647 // If 'parent' is 'pure intermediary' |
639 else if (parent->IsPureIntermediary()) |
648 else if (parent->IsPureIntermediary()) |
640 { |
649 { |
641 // If there is no sibling nodes, the tree is corrupted, |
650 // If there is no sibling nodes, the tree is corrupted, |
642 // as 'pure intermediary' node should always have more than one child. |
651 // as 'pure intermediary' node should always have more than one child. |
643 if (parent->Children().Count() <= 1) |
652 if (parent->Children().Count() <= 1) |
644 { |
653 { |
645 ASSERT(0); |
654 ASSERT(0); |
646 User::Leave(KErrCorrupt); |
655 User::Leave(KErrCorrupt); |
647 } |
656 } |
648 // If there is only one sibling node, we need to merge the sibling node |
657 // If there is only one sibling node, we need to merge the sibling node |
649 // to 'parent'. |
658 // to 'parent'. |
650 else if (parent->Children().Count() == 2) |
659 else if (parent->Children().Count() == 2) |
651 { |
660 { |
652 // Promote the sibling node, delete both parent and self |
661 // Promote the sibling node, delete both parent and self |
653 CLeafDirTreeNode* sibling = (parent->Children())[0] ; |
662 CLeafDirTreeNode* sibling = (parent->Children())[0] ; |
654 if (sibling == aNodeToDelete) |
663 if (sibling == aNodeToDelete) |
655 { |
664 { |
656 sibling = (parent->Children())[1]; |
665 sibling = (parent->Children())[1]; |
657 } |
666 } |
658 TFileName newPath = aNodeToDelete->Parent()->Path(); |
667 TFileName newPath = aNodeToDelete->Parent()->Path(); |
659 newPath.Append(sibling->Path()); |
668 newPath.Append(sibling->Path()); |
660 sibling->SetPathL(newPath); |
669 sibling->SetPathL(newPath); |
661 parent->RemoveChild(sibling); |
670 parent->RemoveChild(sibling); |
662 parent->Parent()->MakeItChildL(sibling); |
671 parent->Parent()->MakeItChildL(sibling); |
663 |
672 |
664 parent->RemoveChild(aNodeToDelete); |
673 parent->RemoveChild(aNodeToDelete); |
665 RemoveFromLru(aNodeToDelete); |
674 RemoveFromLru(aNodeToDelete); |
666 delete aNodeToDelete; |
675 delete aNodeToDelete; |
667 aNodeToDelete = NULL; |
676 aNodeToDelete = NULL; |
668 |
677 |
669 parent->Parent()->RemoveChild(parent); |
678 parent->Parent()->RemoveChild(parent); |
670 delete parent; |
679 delete parent; |
671 return; |
680 return; |
672 } |
681 } |
673 // Else if there are more than 2 sibling nodes, simply delete self. |
682 // Else if there are more than 2 sibling nodes, simply delete self. |
674 else |
683 else |
675 { |
684 { |
676 parent->RemoveChild(aNodeToDelete); |
685 parent->RemoveChild(aNodeToDelete); |
677 RemoveFromLru(aNodeToDelete); |
686 RemoveFromLru(aNodeToDelete); |
678 delete aNodeToDelete; |
687 delete aNodeToDelete; |
679 aNodeToDelete = NULL; |
688 aNodeToDelete = NULL; |
680 return; |
689 return; |
681 } |
690 } |
682 } |
691 } |
683 // If 'parent' is root node, delete self straightaway |
692 // If 'parent' is root node, delete self straightaway |
684 else if (aNodeToDelete->Parent()->IsRoot()) |
693 else if (aNodeToDelete->Parent()->IsRoot()) |
685 { |
694 { |
686 aNodeToDelete->Parent()->RemoveChild(aNodeToDelete); |
695 aNodeToDelete->Parent()->RemoveChild(aNodeToDelete); |
687 RemoveFromLru(aNodeToDelete); |
696 RemoveFromLru(aNodeToDelete); |
688 delete aNodeToDelete; |
697 delete aNodeToDelete; |
689 aNodeToDelete = NULL; |
698 aNodeToDelete = NULL; |
690 return; |
699 return; |
691 } |
700 } |
692 // If 'parent' is 'leaf', the tree is corrupted. |
701 // If 'parent' is 'leaf', the tree is corrupted. |
693 else if (aNodeToDelete->Parent()->IsLeaf()) |
702 else if (aNodeToDelete->Parent()->IsLeaf()) |
694 { |
703 { |
695 ASSERT(0); |
704 ASSERT(0); |
696 User::Leave(KErrCorrupt); |
705 User::Leave(KErrCorrupt); |
697 } |
706 } |
698 } |
707 } |
699 } |
708 } |
700 |
709 |
701 /** |
710 /** |
702 Find the leftest node |
711 Find the leftest node |
703 Note: the leftest node must be a 'leaf' node |
712 Note: the leftest node must be a 'leaf' node |
704 |
713 |
705 @param aNodeToStart a node whose children to start with |
714 @param aNodeToStart a node whose children to start with |
706 @return the leftest node |
715 @return the leftest node |
707 */ |
716 */ |
708 CLeafDirTreeNode* CLeafDirTree::FindLeftestLeafNode(CLeafDirTreeNode* aNodeToStart) const |
717 CLeafDirTreeNode* CLeafDirTree::FindLeftestLeafNode(CLeafDirTreeNode* aNodeToStart) const |
709 { |
718 { |
710 CLeafDirTreeNode* current = aNodeToStart; |
719 CLeafDirTreeNode* current = aNodeToStart; |
711 while (current->Children().Count() > 0) |
720 while (current->Children().Count() > 0) |
712 { |
721 { |
713 current = (current->Children())[0]; |
722 current = (current->Children())[0]; |
714 } |
723 } |
715 return current; |
724 return current; |
716 } |
725 } |
717 |
726 |
718 /** |
727 /** |
719 Delete all nodes derived from aNodeToStart, except itself. |
728 Delete all nodes derived from aNodeToStart, except itself. |
720 |
729 |
721 @param aNodeToStart a node whose children to start with |
730 @param aNodeToStart a node whose children to start with |
722 */ |
731 */ |
723 void CLeafDirTree::DeleteSubTreeL(CLeafDirTreeNode* aNodeToStart) |
732 void CLeafDirTree::DeleteSubTreeL(CLeafDirTreeNode* aNodeToStart) |
724 { |
733 { |
725 while(aNodeToStart->Children().Count() > 0) |
734 while(aNodeToStart->Children().Count() > 0) |
726 { |
735 { |
727 CLeafDirTreeNode* aLeafNode = FindLeftestLeafNode(aNodeToStart); |
736 CLeafDirTreeNode* aLeafNode = FindLeftestLeafNode(aNodeToStart); |
728 RemoveFromCacheL(aLeafNode); |
737 RemoveFromCacheL(aLeafNode); |
729 } |
738 } |
730 } |
739 } |
731 |
740 |
732 /** |
741 /** |
733 Make the a node most recent used in LRU list |
742 Make the a node most recent used in LRU list |
734 |
743 |
735 @param aNodeUsed the node to be made MRU |
744 @param aNodeUsed the node to be made MRU |
736 */ |
745 */ |
737 TInt CLeafDirTree::MakeMostRecentlyUsed(CLeafDirTreeNode* aNodeUsed) |
746 TInt CLeafDirTree::MakeMostRecentlyUsed(CLeafDirTreeNode* aNodeUsed) |
738 { |
747 { |
739 for(TInt i = 0; i < iLruList.Count(); i++) |
748 for(TInt i = 0; i < iLruList.Count(); i++) |
740 { |
749 { |
741 if (aNodeUsed == iLruList[i]) |
750 if (aNodeUsed == iLruList[i]) |
742 { |
751 { |
743 if (i == 0) |
752 if (i == 0) |
744 { |
753 { |
745 return KErrNone; |
754 return KErrNone; |
746 } |
755 } |
747 else |
756 else |
748 { |
757 { |
749 iLruList.Remove(i); |
758 iLruList.Remove(i); |
750 iLruList.Insert(aNodeUsed, 0); |
759 iLruList.Insert(aNodeUsed, 0); |
751 return KErrNone; |
760 return KErrNone; |
752 } |
761 } |
753 } |
762 } |
754 } |
763 } |
755 return KErrNotFound; |
764 return KErrNotFound; |
756 } |
765 } |
757 |
766 |
758 /** |
767 /** |
759 Check cache limit, remove least-used cached item when necessary. |
768 Check cache limit, remove least-used cached item when necessary. |
760 */ |
769 */ |
761 void CLeafDirTree::CheckLimitL() |
770 void CLeafDirTree::CheckLimitL() |
762 { |
771 { |
763 const TInt cacheSize = iSize; |
772 const TInt cacheSize = iSize; |
764 while (iLruList.Count() > cacheSize) |
773 while (iLruList.Count() > cacheSize) |
765 { |
774 { |
766 CLeafDirTreeNode* lruNode = LruNode(); |
775 CLeafDirTreeNode* lruNode = LruNode(); |
767 RemoveFromCacheL(lruNode); |
776 RemoveFromCacheL(lruNode); |
768 } |
777 } |
769 return; |
778 return; |
770 } |
779 } |
771 |
780 |
772 /** |
781 /** |
773 Add new node onto cache list |
782 Add new node onto cache list |
774 |
783 |
775 @param aNodeToAdd the new node to be added onto cache list |
784 @param aNodeToAdd the new node to be added onto cache list |
776 */ |
785 */ |
777 void CLeafDirTree::AddOntoLruL(CLeafDirTreeNode* aNodeToAdd) |
786 void CLeafDirTree::AddOntoLruL(CLeafDirTreeNode* aNodeToAdd) |
778 { |
787 { |
779 if (aNodeToAdd == NULL) |
788 if (aNodeToAdd == NULL) |
780 { |
789 { |
781 ASSERT(0); |
790 ASSERT(0); |
782 User::Leave(KErrArgument); |
791 User::Leave(KErrArgument); |
783 } |
792 } |
784 |
793 |
785 TInt r = iLruList.Insert(aNodeToAdd, 0); |
794 TInt r = iLruList.Insert(aNodeToAdd, 0); |
786 if (r != KErrNone) |
795 if (r != KErrNone) |
787 { |
796 { |
788 ASSERT(0); |
797 ASSERT(0); |
789 User::Leave(KErrArgument); |
798 User::Leave(KErrArgument); |
790 } |
799 } |
791 CheckLimitL(); |
800 CheckLimitL(); |
792 } |
801 } |
793 |
802 |
794 /** |
803 /** |
795 Remove a node from cached list. |
804 Remove a node from cached list. |
796 |
805 |
797 @param aNodeToRemove the node to be removed from the cache list |
806 @param aNodeToRemove the node to be removed from the cache list |
798 */ |
807 */ |
799 TInt CLeafDirTree::RemoveFromLru(CLeafDirTreeNode* aNodeToRemove) |
808 TInt CLeafDirTree::RemoveFromLru(CLeafDirTreeNode* aNodeToRemove) |
800 { |
809 { |
801 for (TInt i = 0; i < iLruList.Count(); i++) |
810 for (TInt i = 0; i < iLruList.Count(); i++) |
802 { |
811 { |
803 if (aNodeToRemove == iLruList[i]) |
812 if (aNodeToRemove == iLruList[i]) |
804 { |
813 { |
805 iLruList.Remove(i); |
814 iLruList.Remove(i); |
806 return KErrNone; |
815 return KErrNone; |
807 } |
816 } |
808 } |
817 } |
809 return KErrNotFound; |
818 return KErrNotFound; |
810 } |
819 } |
811 |
820 |
812 /** |
821 /** |
813 Return the least-recent-used node. |
822 Return the least-recent-used node. |
814 |
823 |
815 @return the least recent used node on cache |
824 @return the least recent used node on cache |
816 */ |
825 */ |
817 CLeafDirTreeNode* CLeafDirTree::LruNode() |
826 CLeafDirTreeNode* CLeafDirTree::LruNode() |
818 { |
827 { |
819 if (iLruList.Count() > 0) |
828 if (iLruList.Count() > 0) |
820 { |
829 { |
821 return iLruList[iLruList.Count() - 1]; |
830 return iLruList[iLruList.Count() - 1]; |
822 } |
831 } |
823 return NULL; |
832 return NULL; |
824 } |
833 } |
825 |
834 |
826 /* |
835 /* |
827 Factory function of CLeafDirCache |
836 Factory function of CLeafDirCache |
828 |
837 |
829 @param aLimit the cache size |
838 @param aLimit the cache size |
830 */ |
839 */ |
831 CLeafDirCache* CLeafDirCache::NewL(TUint32 aLimit) |
840 CLeafDirCache* CLeafDirCache::NewL(TUint32 aLimit) |
832 { |
841 { |
833 CLeafDirCache* self = new(ELeave) CLeafDirCache(aLimit); |
842 CLeafDirCache* self = new(ELeave) CLeafDirCache(aLimit); |
834 CleanupStack::PushL(self); |
843 CleanupStack::PushL(self); |
835 self->ConstructL(); |
844 self->ConstructL(); |
836 CleanupStack::Pop(self); |
845 CleanupStack::Pop(self); |
837 return self; |
846 return self; |
838 } |
847 } |
839 |
848 |
840 /* |
849 /* |
841 2nd phase constructor of CLeafDirCache |
850 2nd phase constructor of CLeafDirCache |
842 */ |
851 */ |
843 void CLeafDirCache::ConstructL() |
852 void CLeafDirCache::ConstructL() |
844 { |
853 { |
845 CLeafDirTree* tree = CLeafDirTree::NewL(iSize); |
854 CLeafDirTree* tree = CLeafDirTree::NewL(iSize); |
846 iTree = tree; |
855 iTree = tree; |
847 } |
856 } |
848 |
857 |
849 /* |
858 /* |
850 Destructor of CLeafDirCache |
859 Destructor of CLeafDirCache |
851 */ |
860 */ |
852 CLeafDirCache::~CLeafDirCache() |
861 CLeafDirCache::~CLeafDirCache() |
853 { |
862 { |
854 delete iTree; |
863 delete iTree; |
855 } |
864 } |
856 |
865 |
857 /* |
866 /* |
858 Constructor of CLeafDirCache |
867 Constructor of CLeafDirCache |
859 |
868 |
860 @param aLimit the cache size |
869 @param aLimit the cache size |
861 */ |
870 */ |
862 CLeafDirCache::CLeafDirCache(TUint32 aSize) |
871 CLeafDirCache::CLeafDirCache(TUint32 aSize) |
863 :iSize(aSize) |
872 :iSize(aSize) |
864 { |
873 { |
865 } |
874 } |
866 |
875 |
867 /* |
876 /* |
868 Reset cache, delete all memory allocated |
877 Reset cache, delete all memory allocated |
869 */ |
878 */ |
870 void CLeafDirCache::Reset() |
879 void CLeafDirCache::Reset() |
871 { |
880 { |
872 iTree->Reset(); |
881 iTree->Reset(); |
873 } |
882 } |
874 |
883 |
875 /* |
884 /* |
876 Cache interface for searching operations. |
885 Cache interface for searching operations. |
877 |
886 |
878 @param aPath the path of the directory to search for |
887 @param aPath the path of the directory to search for |
879 @param aDirPos the location of the direcotry found |
888 @param aDirPos the location of the direcotry found |
880 @return KErrNone if a cached direcotry is found, |
889 @return KErrNone if a cached direcotry is found, |
881 KErrBadName if the path is incorrect, otherwise |
890 KErrBadName if the path is incorrect, otherwise |
882 other system wide error code |
891 other system wide error code |
883 */ |
892 */ |
884 TInt CLeafDirCache::FindInCache(const TDesC& aPath, TLeafDirData& aLeafDirData) const |
893 TInt CLeafDirCache::FindInCache(const TDesC& aPath, TLeafDirData& aLeafDirData) const |
885 { |
894 { |
886 if (aPath[0] == '\\') |
895 if (aPath[0] == '\\') |
887 { |
896 { |
888 TPtrC path; |
897 TPtrC path; |
889 path.Set(aPath.Mid(1)); |
898 path.Set(aPath.Mid(1)); |
890 CLeafDirTreeNode* dummy = NULL; |
899 CLeafDirTreeNode* dummy = NULL; |
891 return (iTree->Search(path, dummy, aLeafDirData)); |
900 return (iTree->Search(path, dummy, aLeafDirData)); |
892 } |
901 } |
893 else |
902 else |
894 { |
903 { |
895 return KErrBadName; |
904 return KErrBadName; |
896 } |
905 } |
897 } |
906 } |
898 |
907 |
899 /* |
908 /* |
900 Cache interface for insertion operations. |
909 Cache interface for insertion operations. |
901 |
910 |
902 @param aPath the path of the directory to be added |
911 @param aPath the path of the directory to be added |
903 @param aDirPos the location of the direcotry to be added |
912 @param aDirPos the location of the direcotry to be added |
904 */ |
913 */ |
905 void CLeafDirCache::AddToCacheL(const TDesC& aPath, const TLeafDirData& aDirPos) |
914 void CLeafDirCache::AddToCacheL(const TDesC& aPath, const TLeafDirData& aDirPos) |
906 { |
915 { |
907 if (aPath.Length() == 1 && aPath[0] == '\\') |
916 if (aPath.Length() == 1 && aPath[0] == '\\') |
908 return; |
917 return; |
909 |
918 |
910 CLeafDirTreeNode* dummy = NULL; |
919 CLeafDirTreeNode* dummy = NULL; |
911 iTree->InsertL(aPath, aDirPos, dummy); |
920 iTree->InsertL(aPath, aDirPos, dummy); |
912 } |
921 } |
913 |
922 |
914 /* |
923 /* |
915 Cache interface for deletion oeprations. |
924 Cache interface for deletion oeprations. |
916 Remove all the cached directories with the same specfied position |
925 Remove all the cached directories with the same specfied position |
917 |
926 |
918 @param aDirPos the location of the direcotry to be removed |
927 @param aDirPos the location of the direcotry to be removed |
919 */ |
928 */ |
920 void CLeafDirCache::RemoveDirL(const TLeafDirData& aDirPos) |
929 void CLeafDirCache::RemoveDirL(const TLeafDirData& aDirPos) |
921 { |
930 { |
922 iTree->RemoveDirL(aDirPos); |
931 iTree->RemoveDirL(aDirPos); |
923 } |
932 } |
924 |
933 |
925 /** |
934 /** |
926 Update the MRU entry position of the cached leaf dir. |
935 Update the MRU entry position of the cached leaf dir. |
927 @param aLeafDirData contains a cluster number as the index of the leaf dir and the new MRU entry position |
936 @param aLeafDirData contains a cluster number as the index of the leaf dir and the new MRU entry position |
928 */ |
937 */ |
929 void CLeafDirCache::UpdateMRUPos(const TLeafDirData& aLeafDirData) |
938 void CLeafDirCache::UpdateMRUPos(const TLeafDirData& aLeafDirData) |
930 { |
939 { |
931 iTree->UpdateMRUPos(aLeafDirData); |
940 iTree->UpdateMRUPos(aLeafDirData); |
932 } |
941 } |
933 /* |
942 /* |
934 * Helper functions of CLeafDirTree for debugging & testing use |
943 * Helper functions of CLeafDirTree for debugging & testing use |
935 */ |
944 */ |
936 #ifdef _DEBUG |
945 #ifdef _DEBUG |
937 /* |
946 /* |
938 All node created will be added to the container of its owner tree, so that we can calculate |
947 All node created will be added to the container of its owner tree, so that we can calculate |
939 the number of objects created. |
948 the number of objects created. |
940 |
949 |
941 @param aNodeToAdd the newly created node to be add to object container |
950 @param aNodeToAdd the newly created node to be add to object container |
942 */ |
951 */ |
943 void CLeafDirTree::AddToObjectContainerL(CLeafDirTreeNode* aNodeToAdd) |
952 void CLeafDirTree::AddToObjectContainerL(CLeafDirTreeNode* aNodeToAdd) |
944 { |
953 { |
945 iContainer.AppendL(aNodeToAdd); |
954 iContainer.AppendL(aNodeToAdd); |
946 } |
955 } |
947 |
956 |
948 /* |
957 /* |
949 A node is removed from object container if it is deleted. |
958 A node is removed from object container if it is deleted. |
950 |
959 |
951 @param aNodeToRemove the node to be deleted |
960 @param aNodeToRemove the node to be deleted |
952 */ |
961 */ |
953 void CLeafDirTree::RemoveFromObjectContainerL(CLeafDirTreeNode* aNodeToRemove) |
962 void CLeafDirTree::RemoveFromObjectContainerL(CLeafDirTreeNode* aNodeToRemove) |
954 { |
963 { |
955 for (TInt i = 0; i < iContainer.Count(); i++) |
964 for (TInt i = 0; i < iContainer.Count(); i++) |
956 { |
965 { |
957 if (aNodeToRemove == iContainer[i]) |
966 if (aNodeToRemove == iContainer[i]) |
958 { |
967 { |
959 iContainer.Remove(i); |
968 iContainer.Remove(i); |
960 return; |
969 return; |
961 } |
970 } |
962 } |
971 } |
963 ASSERT(0); |
972 ASSERT(0); |
964 User::Leave(KErrNotFound); |
973 User::Leave(KErrNotFound); |
965 } |
974 } |
966 |
975 |
967 /* |
976 /* |
968 Print out current tree content |
977 Print out current tree content |
969 */ |
978 */ |
970 void CLeafDirTree::DumpTreeContentL() const |
979 void CLeafDirTree::DumpTreeContentL() const |
971 { |
980 { |
972 RPointerArray<CLeafDirTreeNode>* nodeStack = new(ELeave) RPointerArray<CLeafDirTreeNode>(4); |
981 RPointerArray<CLeafDirTreeNode>* nodeStack = new(ELeave) RPointerArray<CLeafDirTreeNode>(4); |
973 RFs fs; |
982 RFs fs; |
974 fs.Connect(); |
983 fs.Connect(); |
975 const TUint32 debugRegister = DebugRegister(); |
984 const TUint32 debugRegister = DebugRegister(); |
976 fs.SetDebugRegister(debugRegister|KFSYS); |
985 fs.SetDebugRegister(debugRegister|KFSYS); |
977 if (iRoot != NULL) |
986 if (iRoot != NULL) |
978 { |
987 { |
979 nodeStack->Insert(iRoot, 0); |
988 nodeStack->Insert(iRoot, 0); |
980 while(nodeStack->Count() > 0) |
989 while(nodeStack->Count() > 0) |
981 { |
990 { |
982 CLeafDirTreeNode* current = (*nodeStack)[0]; |
991 CLeafDirTreeNode* current = (*nodeStack)[0]; |
983 if (current->Parent() != NULL) |
992 if (current->Parent() != NULL) |
984 { |
993 { |
985 __PRINT3(_L("(\"%S\") -> \"%S\" : (%d)\n"), ¤t->Parent()->Path(), ¤t->Path(), current->StartClusterNum()); |
994 __PRINT3(_L("(\"%S\") -> \"%S\" : (%d)\n"), ¤t->Parent()->Path(), ¤t->Path(), current->StartClusterNum()); |
986 } |
995 } |
987 else |
996 else |
988 { |
997 { |
989 __PRINT2(_L("\"%S\" : (%d)\n"), ¤t->Path(), current->StartClusterNum()); |
998 __PRINT2(_L("\"%S\" : (%d)\n"), ¤t->Path(), current->StartClusterNum()); |
990 } |
999 } |
991 |
1000 |
992 nodeStack->Remove(0); |
1001 nodeStack->Remove(0); |
993 |
1002 |
994 TInt currentCount = current->Children().Count(); |
1003 TInt currentCount = current->Children().Count(); |
995 if (currentCount > 0) |
1004 if (currentCount > 0) |
996 { |
1005 { |
997 RPointerArray<CLeafDirTreeNode> children = current->Children(); |
1006 RPointerArray<CLeafDirTreeNode> children = current->Children(); |
998 for (TInt i = 0; i < currentCount; i++) |
1007 for (TInt i = 0; i < currentCount; i++) |
999 { |
1008 { |
1000 nodeStack->Insert(children[i], 0); |
1009 nodeStack->Insert(children[i], 0); |
1001 } |
1010 } |
1002 } |
1011 } |
1003 } |
1012 } |
1004 } |
1013 } |
1005 |
1014 |
1006 fs.SetDebugRegister(debugRegister); |
1015 fs.SetDebugRegister(debugRegister); |
1007 fs.Close(); |
1016 fs.Close(); |
1008 nodeStack->Close(); |
1017 nodeStack->Close(); |
1009 delete nodeStack; |
1018 delete nodeStack; |
1010 } |
1019 } |
1011 |
1020 |
1012 /* |
1021 /* |
1013 Print out current cache content |
1022 Print out current cache content |
1014 */ |
1023 */ |
1015 void CLeafDirCache::DumpCacheContentL() const |
1024 void CLeafDirCache::DumpCacheContentL() const |
1016 { |
1025 { |
1017 iTree->DumpTreeContentL(); |
1026 iTree->DumpTreeContentL(); |
1018 } |
1027 } |
1019 |
1028 |
1020 /* |
1029 /* |
1021 Count of all the nodes |
1030 Count of all the nodes |
1022 */ |
1031 */ |
1023 TInt CLeafDirCache::NodeCount() const |
1032 TInt CLeafDirCache::NodeCount() const |
1024 { |
1033 { |
1025 return iTree->ObjectCount(); |
1034 return iTree->ObjectCount(); |
1026 } |
1035 } |
1027 #endif // _DEBUG |
1036 #endif // _DEBUG |
1028 |
1037 |