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