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