在一个死亡的论坛上发一个从未活过的代码， 致我已经风飘云散的过去

zylthinking

在一个死亡的论坛上发一个从未活过的 symbian 代码


致我已经风飘云散的过去

1. 
   
2. #ifndef _RBTree_H_
   
3. #define _RBTree_H_
   
4. #include <e32base.h>
   
5. 
   
6. #define EFailed ((TAny *)(-1))
   
7. typedef void (*TFree)(void*);
   
8. typedef TInt (*TComp)(void*, void*);
   
9. 
   
10. struct TUserOP{
    
11.     TFree iFree;
    
12.     TComp iCompare;
    
13. };
    
14. 
    
15. class TTreeNode;
    
16. class TTreeIterator;
    
17. 
    
18. class CRBTree : public CBase{
    
19. public:
    
20.     // TUser must not be NULL and iCompare should be
    
21.     // provided too. while, iFree can be NULL if not needed
    
22.     static IMPORT_C CRBTree* NewL(TUserOP* op);
    
23.     IMPORT_C ~CRBTree();
    
24. 
    
25.     // add a node to tree
    
26.     // aUser, data proviced by user which will be added to tree
    
27.     // aRep, if the data has exists, would it replace the old one
    
28.     // or failed
    
29.     // return value: EFailed, error occured
    
30.     // the old one being replaced by the aUser, if aRep is false or
    
31.     // there is data which is equal to aUser, return NULL
    
32.     IMPORT_C TAny* AddL(TAny* aUser, TBool aRep);
    
33. 
    
34.     // remove node
    
35.     IMPORT_C TAny* Unlink(TAny* aUser);
    
36.     IMPORT_C void Remove(TAny* aUser);
    
37. 
    
38.     // clear all nodes in the tree
    
39.     // the tree will be empty, while ok to add nodes again
    
40.     IMPORT_C void Reset();
    
41. 
    
42.     // number of nodes of the tree
    
43.     IMPORT_C TInt Length();
    
44. 
    
45.     // the min node in the tree
    
46.     // the compare is provided by TUserOP
    
47.     IMPORT_C TAny* Min();
    
48. 
    
49.     // the max node in the tree
    
50.     // the compare is provided by TUserOP
    
51.     IMPORT_C TAny* Max();
    
52. 
    
53.     // find the node in the tree, which is euqal to aUser
    
54.     // compared with TUserOP::iCompare
    
55.     IMPORT_C TAny* Find(TAny* aUser);
    
56. 
    
57.     // generate a handle for later FindNext
    
58.     // return -1, when can't find the aUser
    
59.     // the handle will be used for forward search only
    
60.     IMPORT_C TInt FindFirst(TAny* aUser);
    
61. 
    
62.     // generate a handle for later RFindNext
    
63.     // return -1, when can't find the aUser
    
64.     // the handle will be used for backward search only
    
65.     IMPORT_C TInt RFindFirst(TAny* aUser);
    
66. 
    
67.     // return data referenced by handle, and reposition the
    
68.     // handle to nexr data
    
69.     // return value: the data referenced by handle
    
70.     // EFailed if error occured
    
71.     // NULL when there is no more data
    
72.     IMPORT_C TAny* FindNext(TInt aHandle);
    
73. 
    
74.     // same with FindNext, but is a safer method, meaning, the
    
75.     // method will validate the handle provided by user, while
    
76.     // FindNext will not. The method is slower.
    
77.     IMPORT_C TAny* FindNextSafe(TInt aHandle);
    
78. 
    
79.     // return data referenced by handle, and reposition the
    
80.     // handle to previous data
    
81.     // return value: the data referenced by handle
    
82.     // EFailed if error occured
    
83.     // NULL when there is no more data
    
84.     IMPORT_C TAny* RFindNext(TInt aHandle);
    
85. 
    
86.     // same with RFindNext, but is a safer method, meaning, the
    
87.     // method will validate the handle provided by user, while
    
88.     // RFindNext will not. The method is slower.
    
89.     IMPORT_C TAny* RFindNextSafe(TInt aHandle);
    
90. 
    
91.     // Close the handle when finish using it.
    
92.     // must be called after using it to release resouce used internal
    
93.     IMPORT_C void CloseFindHandle(TInt handle);
    
94. 
    
95.     // A safe version of CloseFindHandle
    
96.     IMPORT_C void CloseFindHandleSafe(TInt handle);
    
97. 
    
98. #ifdef _DEBUG
    
99.     IMPORT_C TInt BlackHeight();
    
100. private:
     
101.     TInt CRBTree::BlackHeight(TTreeNode* aNode);
     
102. #endif
     
103. 
     
104. public:
     
105.     enum TColor{EBlack, ERed};
     
106.     enum TDirect{EForward, EBackward};
     
107. 
     
108. private:
     
109.     CRBTree(TUserOP* op);
     
110.     CRBTree::CRBTree(const CRBTree&);
     
111.     CRBTree& operator = (const CRBTree&);
     
112.     void ConstructL();
     
113.    
     
114.     void AdjustBeforeInsert(TTreeNode* aNode);
     
115.     void AdjustBeforeRemove(TTreeNode* aNode);
     
116.     void InsertL(TAny* aUser, TTreeNode* aFather, TInt aFlag);
     
117.     void InsertRotate(TTreeNode* aFather, TTreeNode* aNode);
     
118.     TAny* RemoveNode(TTreeNode* aNode);
     
119.    
     
120.     TTreeNode* Find(TAny* aUser, TInt& aFlag);
     
121.     TInt FindFirst(TAny* aUser, TDirect aDirect);
     
122.     TTreeNode* FindNext(TTreeNode* aNode);
     
123.     TTreeNode* RFindNext(TTreeNode* aNode);
     
124.     void AdjustFindHandles(TTreeNode* aNode);
     
125.    
     
126.     TInt ValidateHandle(TInt aHandle);
     
127.     TTreeNode** PointerOf(TTreeNode* aNode);
     
128.     void RotateLeft(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode);
     
129.     void RotateRight(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode);
     
130.    
     
131. private:
     
132.     TUserOP* iOps;
     
133.     TTreeNode* iRoot;
     
134.     TTreeIterator* iIterator;
     
135.     TInt iNrNodes;
     
136. };
     
137. 
     
138. #endif
     
139. 
     
140. 
     
141. #include "rbtree.h"
     
142. #include <e32std.h>
     
143. 
     
144. #define BLACK(x)    (x == NULL || x->iColor == EBlack)
     
145. 
     
146. class TTreeNode{
     
147. public:
     
148.     TTreeNode(CRBTree::TColor aColor){
     
149.         iLChild = iRChild = iFather = NULL;
     
150.         iColor = aColor;
     
151.     }
     
152. public:
     
153.     TTreeNode* iFather;
     
154.     TTreeNode* iLChild;
     
155.     TTreeNode* iRChild;
     
156.     CRBTree::TColor iColor;
     
157.     TAny* iUser;
     
158. };
     
159. 
     
160. class TTreeIterator{
     
161. public:
     
162.     TTreeIterator(TTreeNode* aNode, CRBTree::TDirect aDirection){
     
163.         ASSERT(aNode);
     
164. 
     
165.         iNext = iPrev = NULL;
     
166.         iNode = aNode;
     
167.         iDirection = aDirection;
     
168.     }
     
169. 
     
170.     TTreeNode* iNode;
     
171.     CRBTree::TDirect iDirection;
     
172.     TTreeIterator* iNext;
     
173.     TTreeIterator* iPrev;
     
174. };
     
175. 
     
176. //========================================================
     
177. 
     
178. CRBTree::CRBTree(TUserOP* aOp){
     
179.     iOps = aOp;
     
180. }
     
181. 
     
182. EXPORT_C CRBTree::~CRBTree(){
     
183.     Reset();
     
184. }
     
185. 
     
186. EXPORT_C CRBTree* CRBTree::NewL(TUserOP* aOp){
     
187.     CRBTree* self = new (ELeave) CRBTree(aOp);
     
188.     CleanupStack::PushL(self);
     
189.     self->ConstructL();
     
190.     CleanupStack::Pop();
     
191.     return self;
     
192. }
     
193. 
     
194. void CRBTree::ConstructL(){
     
195.     if(iOps == NULL || iOps->iCompare == NULL)
     
196.         User::Leave(KErrArgument);
     
197. }
     
198. 
     
199. EXPORT_C TInt CRBTree::Length(){
     
200.     return iNrNodes;
     
201. }
     
202. 
     
203. EXPORT_C TAny* CRBTree::Min(){
     
204.     TTreeNode* cur = iRoot;
     
205.     if(cur != NULL){
     
206.         while(cur->iLChild){
     
207.             cur = cur->iLChild;
     
208.         }
     
209.     }
     
210.     return cur->iUser;
     
211. }
     
212. 
     
213. EXPORT_C TAny* CRBTree::Max(){
     
214.     TTreeNode* cur = iRoot;
     
215.     if(cur != NULL){
     
216.         while(cur->iRChild){
     
217.             cur = cur->iRChild;
     
218.         }
     
219.     }
     
220.     return cur->iUser;
     
221. }
     
222. 
     
223. EXPORT_C void CRBTree::Reset(){
     
224.     TTreeNode* cur = iRoot;
     
225. LABEL:
     
226.     if(cur){
     
227.         if(cur->iLChild){
     
228.             cur = cur->iLChild;
     
229.             goto LABEL;
     
230.         }
     
231. 
     
232.         if(cur->iRChild){
     
233.             cur = cur->iRChild;
     
234.             goto LABEL;
     
235.         }
     
236. 
     
237.         if(iOps->iFree){
     
238.             iOps->iFree(cur->iUser);
     
239.         }
     
240. 
     
241.         TTreeNode* father = cur->iFather;
     
242.         delete cur;
     
243. 
     
244.         if(cur != iRoot){
     
245.             if(father->iLChild == cur)
     
246.                 father->iLChild = NULL;
     
247.             else
     
248.                 father->iRChild = NULL;
     
249. 
     
250.             cur = father;
     
251.             goto LABEL;
     
252.         }
     
253.     }
     
254. 
     
255.     TTreeIterator* it = iIterator;
     
256.     while(it){
     
257.         TTreeIterator* next = it->iNext;
     
258.         delete it;
     
259.         it = next;
     
260.     }
     
261. 
     
262.     iRoot = NULL;
     
263.     iIterator = NULL;
     
264.     iNrNodes = 0;
     
265. }
     
266. 
     
267. EXPORT_C TAny* CRBTree::AddL(TAny* aUser, TBool aRep){
     
268.     if(aUser == NULL)
     
269.         User::Leave(KErrArgument);
     
270. 
     
271.     if(iRoot == NULL){
     
272.         TTreeNode* node = new (ELeave) TTreeNode(EBlack);
     
273.         ++iNrNodes;
     
274. 
     
275.         iRoot = node;
     
276.         iRoot->iUser = aUser;
     
277.         return NULL;
     
278.     }
     
279.    
     
280.     TInt flag = 1;
     
281.     TTreeNode* node = Find(aUser, flag);
     
282.     ASSERT(node);
     
283. 
     
284.     TAny* oldkey = node->iUser;
     
285.     if(flag == 0){
     
286.         if(aRep){
     
287.             node->iUser = oldkey;
     
288.             return oldkey;
     
289.         }
     
290.         User::Leave(KErrAlreadyExists);
     
291.     }
     
292. 
     
293.     InsertL(aUser, node, flag);
     
294.     ++iNrNodes;
     
295.     return NULL;
     
296. }
     
297. 
     
298. void CRBTree::InsertL(TAny* aUser, TTreeNode* aFather, TInt aFlag){
     
299.     TTreeNode* newNode = new (ELeave) TTreeNode(ERed);
     
300.     newNode->iUser = aUser;
     
301. 
     
302.     if(aFlag > 0){
     
303.         aFather->iLChild = newNode;
     
304.         newNode->iFather = aFather;
     
305.     }else{
     
306.         aFather->iRChild = newNode;
     
307.         newNode->iFather = aFather;
     
308.     }
     
309. 
     
310.     if(aFather->iColor == ERed){
     
311.         InsertRotate(aFather, newNode);
     
312.     }
     
313. }
     
314. 
     
315. TTreeNode* CRBTree::Find(TAny* aUser, TInt& aFlag){
     
316.     ASSERT(aUser);
     
317. 
     
318.     TInt adjust = aFlag;
     
319.     TTreeNode* cur = iRoot;
     
320. 
     
321.     while(cur){
     
322.         aFlag = iOps->iCompare(cur->iUser, aUser);
     
323.         if(aFlag == 0)
     
324.             return cur;
     
325.         
     
326.         if(adjust && cur->iLChild && cur->iRChild &&
     
327.            cur->iColor == EBlack && cur->iLChild->iColor == ERed &&
     
328.            cur->iRChild->iColor == ERed){
     
329.             AdjustBeforeInsert(cur);
     
330.         }
     
331. 
     
332.         if(aFlag > 0 && cur->iLChild){
     
333.             cur = cur->iLChild;
     
334.         }else if(aFlag < 0 && cur->iRChild){
     
335.             cur = cur->iRChild;
     
336.         }else{
     
337.             return cur;
     
338.         }
     
339.     }
     
340. 
     
341.     return NULL;
     
342. }
     
343. 
     
344. void CRBTree::AdjustBeforeInsert(TTreeNode* aNode){
     
345.     aNode->iLChild->iColor = EBlack;
     
346.     aNode->iRChild->iColor = EBlack;
     
347. 
     
348.     if(aNode->iFather){
     
349.         aNode->iColor = ERed;
     
350.         if(aNode->iFather->iColor == ERed)
     
351.             InsertRotate(aNode->iFather, aNode);
     
352.     }
     
353. }
     
354. 
     
355. void CRBTree::InsertRotate(TTreeNode* aFather, TTreeNode* aNode){
     
356.     ASSERT(aNode->iColor == ERed);
     
357.     ASSERT(aFather->iColor == ERed);
     
358.     ASSERT(aFather->iFather);
     
359.    
     
360.     TTreeNode* grandpa = aFather->iFather;
     
361.     TBool left1 = (aFather->iLChild == aNode);
     
362.     TBool left2 = (grandpa->iLChild == aFather);
     
363.     TBool same = (left1 == left2);
     
364. 
     
365.     if(same){
     
366.         aNode = aFather;
     
367.         aFather = aNode->iFather;
     
368.     }
     
369. 
     
370. LABEL:
     
371.     TTreeNode** pp_node = PointerOf(aFather);
     
372.     if(left1){
     
373.         RotateRight(aFather, aNode, pp_node);
     
374.     }else{
     
375.         RotateLeft(aFather, aNode, pp_node);
     
376.     }
     
377. 
     
378.     if(!same){
     
379.         left1 = !left1;
     
380.         aFather = aNode->iFather;
     
381.         same = true;
     
382.         goto LABEL;
     
383.     }
     
384. 
     
385.     aNode->iColor = EBlack;
     
386.     if(left1){
     
387.         aNode->iRChild->iColor = ERed;
     
388.     }else{
     
389.         aNode->iLChild->iColor = ERed;
     
390.     }
     
391. }
     
392. 
     
393. void CRBTree::RotateLeft(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode){
     
394.     *aPPNode = aNode;
     
395.     aNode->iFather = aFather->iFather;
     
396.    
     
397.     aFather->iRChild = aNode->iLChild;
     
398.     if(aNode->iLChild){
     
399.         aNode->iLChild->iFather = aFather;
     
400.     }
     
401. 
     
402.     aNode->iLChild = aFather;
     
403.     aFather->iFather = aNode;
     
404. }
     
405.    
     
406. void CRBTree::RotateRight(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode){
     
407.     *aPPNode = aNode;
     
408.     aNode->iFather = aFather->iFather;
     
409.    
     
410.     aFather->iLChild = aNode->iRChild;
     
411.     if(aNode->iRChild){
     
412.         aNode->iRChild->iFather = aFather;
     
413.     }
     
414. 
     
415.     aNode->iRChild = aFather;
     
416.     aFather->iFather = aNode;
     
417. }
     
418. 
     
419. EXPORT_C TAny* CRBTree::Unlink(TAny* aUser){
     
420.     if(aUser == NULL){
     
421.         return NULL;
     
422.     }
     
423. 
     
424.     TAny* user = NULL;
     
425.     TInt flag = 0;
     
426. 
     
427.     TTreeNode* node = Find(aUser, flag);
     
428.     if(node != NULL && flag == 0){
     
429.         AdjustFindHandles(node);
     
430.         user = RemoveNode(node);
     
431.         --iNrNodes;
     
432.     }
     
433.     return user;
     
434. }
     
435. 
     
436. EXPORT_C void CRBTree::Remove(TAny* aUser){
     
437.     TAny* user = Unlink(aUser);
     
438.     if(user && iOps->iFree){
     
439.         iOps->iFree(user);
     
440.     }
     
441. }
     
442. 
     
443. TAny* CRBTree::RemoveNode(TTreeNode* aNode){
     
444.     ASSERT(aNode);
     
445. 
     
446.     if(aNode->iLChild && aNode->iRChild){
     
447.         TTreeNode* next = FindNext(aNode);
     
448.         TAny* saved_key = next->iUser;
     
449.         next->iUser = aNode->iUser;
     
450.         aNode->iUser = saved_key;
     
451.         aNode = next;
     
452.     }
     
453. 
     
454.     TTreeNode** pp_node = PointerOf(aNode);
     
455.     if(aNode->iRChild != NULL){
     
456.         aNode->iRChild->iFather = aNode->iFather;
     
457.         aNode->iRChild->iColor = EBlack;
     
458.         *pp_node = aNode->iRChild;
     
459.     }else if(aNode->iLChild != NULL){
     
460.         aNode->iLChild->iFather = aNode->iFather;
     
461.         aNode->iLChild->iColor = EBlack;
     
462.         *pp_node = aNode->iLChild;
     
463.     }else{
     
464.         if(aNode->iColor == EBlack){
     
465.             AdjustBeforeRemove(aNode);
     
466.         }
     
467.         *pp_node = NULL;
     
468.     }
     
469. 
     
470.     TAny* user = aNode->iUser;
     
471.     delete aNode;
     
472.     return user;
     
473. }
     
474. 
     
475. void CRBTree::AdjustBeforeRemove(TTreeNode* aNode){
     
476. LABEL:
     
477.     TTreeNode* father = aNode->iFather;
     
478.     if(father == NULL){
     
479.         return;
     
480.     }
     
481. 
     
482.     TTreeNode* brother;
     
483.     TBool left = father->iLChild == aNode;
     
484.     if(left){
     
485.         brother = father->iRChild;
     
486.     }else{
     
487.         brother = father->iLChild;
     
488.     }
     
489.     ASSERT(brother);
     
490. 
     
491.     if(brother->iColor == ERed){
     
492.         TTreeNode** pp_node = PointerOf(father);
     
493. 
     
494.         if(left){
     
495.             RotateLeft(father, brother, pp_node);
     
496.             brother = father->iRChild;
     
497.         }else{
     
498.             RotateRight(father, brother, pp_node);
     
499.             brother = father->iLChild;
     
500.         }
     
501. 
     
502.         father->iColor = ERed;
     
503.         father->iFather->iColor = EBlack;
     
504.     }
     
505. 
     
506.     if(BLACK(brother->iLChild) && BLACK(brother->iRChild)){
     
507.         if(father->iColor == ERed){
     
508.             father->iColor = EBlack;
     
509.             brother->iColor = ERed;
     
510.             return;
     
511.         }
     
512. 
     
513.         brother->iColor = ERed;
     
514.         aNode = father;
     
515.         goto LABEL;
     
516.     }
     
517. 
     
518.     if(left){
     
519.         if(BLACK(brother->iRChild)){
     
520.             ASSERT(brother->iLChild->iColor == ERed);
     
521.             RotateRight(brother, brother->iLChild, &(father->iRChild));
     
522. 
     
523.             brother = brother->iFather;
     
524.             brother->iColor = EBlack;
     
525.             brother->iRChild->iColor = ERed;
     
526.         }
     
527.     }else if(BLACK(brother->iLChild)){
     
528.         ASSERT(brother->iRChild->iColor == ERed);
     
529.         RotateLeft(brother, brother->iRChild, &(father->iLChild));
     
530. 
     
531.         brother = brother->iFather;
     
532.         brother->iColor = EBlack;
     
533.         brother->iLChild->iColor = ERed;
     
534.     }
     
535. 
     
536.     TTreeNode** pp_node = PointerOf(father);
     
537.     if(left){
     
538.         RotateLeft(father, brother, pp_node);
     
539.         brother->iRChild->iColor = EBlack;
     
540.     }else{
     
541.         RotateRight(father, brother, pp_node);
     
542.         brother->iLChild->iColor = EBlack;
     
543.     }
     
544. 
     
545.     brother->iColor = father->iColor;
     
546.     father->iColor = EBlack;
     
547. }
     
548. 
     
549. TTreeNode** CRBTree::PointerOf(TTreeNode* aNode){
     
550.     ASSERT(aNode);
     
551. 
     
552.     TTreeNode** pp_node;
     
553.     if(aNode->iFather){
     
554.         if(aNode->iFather->iLChild == aNode)
     
555.             pp_node = &aNode->iFather->iLChild;
     
556.         else
     
557.             pp_node = &aNode->iFather->iRChild;
     
558.     }else{
     
559.         pp_node = &iRoot;
     
560.     }
     
561. 
     
562.     return pp_node;
     
563. }
     
564. 
     
565. TTreeNode* CRBTree::FindNext(TTreeNode* aNode){
     
566.     ASSERT(aNode);
     
567. 
     
568.     TTreeNode* cur = aNode->iRChild;
     
569.     if(cur){
     
570.         while(cur->iLChild){
     
571.             cur = cur->iLChild;
     
572.         }
     
573.         return cur;
     
574.     }
     
575. 
     
576.     cur = aNode->iFather;
     
577.     while(cur){
     
578.         if(cur->iLChild == aNode){
     
579.             return cur;
     
580.         }
     
581.         aNode = cur;
     
582.         cur = cur->iFather;
     
583.     }
     
584. 
     
585.     return NULL;
     
586. }
     
587. 
     
588. TTreeNode* CRBTree::RFindNext(TTreeNode* aNode){
     
589.     ASSERT(aNode);
     
590. 
     
591.     TTreeNode* cur = aNode->iLChild;
     
592.     if(cur){
     
593.         while(cur->iRChild){
     
594.             cur = cur->iRChild;
     
595.         }
     
596.         return cur;
     
597.     }
     
598. 
     
599.     cur = aNode->iFather;
     
600.     while(cur){
     
601.         if(cur->iRChild == aNode){
     
602.             return cur;
     
603.         }
     
604.         aNode = cur;
     
605.         cur = cur->iFather;
     
606.     }
     
607. 
     
608.     return NULL;
     
609. }
     
610. 
     
611. void CRBTree::AdjustFindHandles(TTreeNode* aNode){
     
612.     TTreeIterator* it = iIterator;
     
613.     while(it){
     
614.         if(it->iNode == aNode){
     
615.             if(it->iDirection == EForward){
     
616.                 it->iNode = FindNext(aNode);
     
617.             }else{
     
618.                 it->iNode = RFindNext(aNode);
     
619.             }
     
620.         }
     
621.         it = it->iNext;
     
622.     }
     
623. }
     
624. 
     
625. TInt CRBTree::ValidateHandle(TInt aHandle){
     
626.     TTreeIterator* it = iIterator;
     
627.     TTreeIterator* in = (TTreeIterator *) aHandle;
     
628.     while(it){
     
629.         if(it == in){
     
630.             break;
     
631.         }
     
632.         it = it->iNext;
     
633.     }
     
634. 
     
635.     if(it == NULL){
     
636.         return -1;
     
637.     }
     
638.     return 0;
     
639. }
     
640. 
     
641. EXPORT_C TAny* CRBTree::Find(TAny* aUser){
     
642.     if(aUser == NULL){
     
643.         return NULL;
     
644.     }
     
645. 
     
646.     TInt flag = 0;
     
647.     TTreeNode* node = Find(aUser, flag);
     
648.     if(node == NULL || flag != 0){
     
649.         return NULL;
     
650.     }
     
651.     return node->iUser;   
     
652. }
     
653. 
     
654. TInt CRBTree::FindFirst(TAny* aUser, TDirect aDirect){
     
655.     if(aUser == NULL){
     
656.         return -1;
     
657.     }
     
658. 
     
659.     TInt flag = 0;
     
660.     TTreeNode* node = Find(aUser, flag);
     
661.     if(node == NULL){
     
662.         return -1;
     
663.     }
     
664. 
     
665.     if(flag == 0){
     
666.         TTreeIterator* it;
     
667.         TRAPD(err, it = new (ELeave) TTreeIterator(node, aDirect));
     
668.         if(KErrNone != err){
     
669.             return -1;
     
670.         }
     
671. 
     
672.         if(iIterator != NULL){
     
673.             it->iNext = iIterator;
     
674.             iIterator->iPrev = it;
     
675.         }
     
676. 
     
677.         iIterator = it;
     
678.         return (TInt) (iIterator);
     
679.     }
     
680. 
     
681.     return -1;
     
682. }
     
683. 
     
684. EXPORT_C TInt CRBTree::FindFirst(TAny* aUser){
     
685.     return FindFirst(aUser, EForward);
     
686. }
     
687. 
     
688. EXPORT_C TInt CRBTree::RFindFirst(TAny* aUser){
     
689.     return FindFirst(aUser, EBackward);
     
690. }
     
691. 
     
692. EXPORT_C TAny* CRBTree::FindNext(TInt handle){
     
693.     TTreeIterator* it = (TTreeIterator *) handle;
     
694.     if(it->iDirection != EForward){
     
695.         return EFailed;
     
696.     }
     
697. 
     
698.     TTreeNode* node = it->iNode;
     
699.     if(node == NULL){
     
700.         return NULL;
     
701.     }
     
702. 
     
703.     TTreeNode* next = FindNext(node);
     
704.     it->iNode = next;
     
705.     return node->iUser;
     
706. }
     
707. 
     
708. EXPORT_C TAny* CRBTree::FindNextSafe(TInt handle){
     
709.     if(-1 == ValidateHandle(handle)){
     
710.         return EFailed;
     
711.     }
     
712.     return FindNext(handle);
     
713. }
     
714. 
     
715. EXPORT_C TAny* CRBTree::RFindNext(TInt handle){
     
716.     TTreeIterator* it = (TTreeIterator *) handle;
     
717.     if(it->iDirection != EBackward){
     
718.         return EFailed;
     
719.     }
     
720. 
     
721.     TTreeNode* node = it->iNode;
     
722.     if(node == NULL){
     
723.         return NULL;
     
724.     }
     
725. 
     
726.     TTreeNode* next = RFindNext(node);
     
727.     it->iNode = next;
     
728.     return node->iUser;
     
729. }
     
730. 
     
731. EXPORT_C TAny* CRBTree::RFindNextSafe(TInt handle){
     
732.     if(-1 == ValidateHandle(handle)){
     
733.         return EFailed;
     
734.     }
     
735.     return RFindNext(handle);
     
736. }
     
737. 
     
738. EXPORT_C void CRBTree::CloseFindHandle(TInt handle){
     
739.     if(iIterator == NULL){
     
740.         return;
     
741.     }
     
742. 
     
743.     TTreeIterator* in = (TTreeIterator *) handle;
     
744.     if(iIterator == in){
     
745.         iIterator = in->iNext;
     
746.         if(iIterator)
     
747.             iIterator->iPrev = NULL;
     
748.     }else{
     
749.         in->iPrev->iNext = in->iNext;
     
750.         if(in->iNext)
     
751.             in->iNext->iPrev = in->iPrev;
     
752.     }
     
753. 
     
754.     delete in;
     
755. }
     
756.    
     
757. EXPORT_C void CRBTree::CloseFindHandleSafe(TInt handle){
     
758.     if(-1 != ValidateHandle(handle)){
     
759.         CloseFindHandle(handle);
     
760.     }
     
761. }
     
762. 
     
763. #ifdef _DEBUG
     
764. EXPORT_C TInt CRBTree::BlackHeight(){
     
765.     ASSERT(BLACK(iRoot));
     
766.     return BlackHeight(iRoot);
     
767. }
     
768. 
     
769. TInt CRBTree::BlackHeight(TTreeNode* aNode){
     
770.     TInt n = 0;
     
771.     if(BLACK(aNode)){
     
772.         n = 1;
     
773.     }else{
     
774.         ASSERT(BLACK(aNode->iLChild));
     
775.         ASSERT(BLACK(aNode->iRChild));
     
776.     }
     
777. 
     
778.     TInt n1 = 0;
     
779.     TInt n2 = 0;
     
780.     if(aNode){
     
781.         n1 = BlackHeight(aNode->iLChild);
     
782.         n2 = BlackHeight(aNode->iRChild);
     
783.     }
     
784.     ASSERT(n1 == n2);
     
785. 
     
786.     return (n + n1);
     
787. }
     
788. #endif
     
789. 
     

复制代码

starwing83

1.     TAny* oldkey = node->iUser;
   
2.     if(flag == 0){
   
3.         if(aRep){
   
4.             node->iUser = oldkey;
   
5.             return oldkey;
   
6.         }
   
7.         User::Leave(KErrAlreadyExists);
   
8.     }

复制代码

AddL的这一段，应该是赋值aUser而不是oldkey吧？

pandaiam

人都已经散了。。

zylthinking

回复 2# starwing83

看上去像

zylthinking

pandaiam 发表于 2022-11-21 13:37
人都已经散了。。

这代码以为早丢了， 然后科学上网上了一次 gmail 居然发现了
无论如何当时也写了好几天， 总要让它吹吹风