|
1 // bsymtree.cpp |
|
2 // |
|
3 // Copyright (c) 2010 Accenture. All rights reserved. |
|
4 // This component and the accompanying materials are made available |
|
5 // under the terms of the "Eclipse Public License v1.0" |
|
6 // which accompanies this distribution, and is available |
|
7 // at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 // |
|
9 // Initial Contributors: |
|
10 // Accenture - Initial contribution |
|
11 // |
|
12 #include "bsymtree.h" |
|
13 #include <badesca.h> |
|
14 #include <fshell/descriptorutils.h> |
|
15 //#include <e32debug.h> |
|
16 |
|
17 using namespace LtkUtils; |
|
18 |
|
19 RNode* RNode::NewL() |
|
20 { |
|
21 RNode* top = new(ELeave) RNode(0); |
|
22 CleanupDeletePushL(top); |
|
23 top->iPtr = new(ELeave) RArray<RNode*>(8); |
|
24 top->iHasChildArray = 1; |
|
25 CleanupStack::Pop(top); |
|
26 return top; |
|
27 } |
|
28 |
|
29 RNode::RNode(char aLetter) |
|
30 : iLetter(aLetter), iHasChildArray(0), iPad(0), iPtr(NULL) |
|
31 { |
|
32 } |
|
33 |
|
34 RNode* RNode::Sprog() const |
|
35 { |
|
36 ASSERT(!iHasChildArray); |
|
37 ASSERT(iLetter != 0); |
|
38 return reinterpret_cast<RNode*>(iPtr); |
|
39 } |
|
40 |
|
41 RArray<RNode*>& RNode::Sprogs() const |
|
42 { |
|
43 ASSERT(iHasChildArray); |
|
44 return *reinterpret_cast<RArray<RNode*>*>(iPtr); |
|
45 } |
|
46 |
|
47 RNode* RNode::ChildForLetter(char aChild) const |
|
48 { |
|
49 if (iHasChildArray) |
|
50 { |
|
51 const TInt count = Sprogs().Count(); |
|
52 for (TInt i = 0; i < count; i++) |
|
53 { |
|
54 RNode* node = Sprogs()[i]; |
|
55 if (node->iLetter == aChild) return node; |
|
56 } |
|
57 } |
|
58 else if (iLetter != 0) // null terminators use next for the value |
|
59 { |
|
60 RNode* child = Sprog(); |
|
61 if (child && child->iLetter == aChild) return child; |
|
62 } |
|
63 return NULL; |
|
64 } |
|
65 |
|
66 RNode* RNode::AddChildL(char aChild) |
|
67 { |
|
68 RNode* node = new(ELeave) RNode(aChild); |
|
69 CleanupStack::PushL(node); |
|
70 if (!iHasChildArray) |
|
71 { |
|
72 if (iPtr == NULL) |
|
73 { |
|
74 // Easy |
|
75 CleanupStack::Pop(node); |
|
76 iPtr = node; |
|
77 return node; |
|
78 } |
|
79 else |
|
80 { |
|
81 // Need to upgrade to a childArray |
|
82 RArray<RNode*>* children = new(ELeave) RArray<RNode*>(8); |
|
83 CleanupStack::PushL(children); |
|
84 children->AppendL(reinterpret_cast<RNode*>(iPtr)); |
|
85 iPtr = children; |
|
86 CleanupStack::Pop(children); |
|
87 iHasChildArray = 1; |
|
88 } |
|
89 } |
|
90 Sprogs().AppendL(node); |
|
91 CleanupStack::Pop(node); |
|
92 return node; |
|
93 } |
|
94 |
|
95 void RNode::InsertStringL(const TUint16* aString, TInt aValue) |
|
96 { |
|
97 char letter = (char)*aString; |
|
98 RNode* child = ChildForLetter(letter); |
|
99 if (!child) |
|
100 { |
|
101 child = AddChildL(letter); |
|
102 } |
|
103 |
|
104 if (letter == 0) |
|
105 { |
|
106 // If the letter was the null termination at the end, we're finished and just need to set the value |
|
107 //ASSERT(child->iPtr == NULL); // There should never be a child of a null terminator (unless the same string has been inserted twice...) |
|
108 // ^ Annoyingly there can be duplicate symbols that are only distinguished by information we've actually thrown away in the BSYM. |
|
109 // We will ignore such duplicate symbols. If this is a problem, someone feel free to fix it. |
|
110 if (!child->iPtr) |
|
111 { |
|
112 child->iPtr = (TAny*)aValue; |
|
113 } |
|
114 } |
|
115 else |
|
116 { |
|
117 aString++; |
|
118 child->InsertStringL(aString, aValue); |
|
119 } |
|
120 } |
|
121 |
|
122 RNode* RNode::WalkToEndOfString(TUint16*& aString) |
|
123 { |
|
124 RNode* currentNode = this; |
|
125 while (*aString) |
|
126 { |
|
127 RNode* child = currentNode->ChildForLetter((char)*aString); |
|
128 if (!child) return currentNode; |
|
129 currentNode = child; |
|
130 aString++; |
|
131 } |
|
132 return currentNode; |
|
133 } |
|
134 |
|
135 RNode* RNode::TabFill(TUint16*& aString, const TUint16* aEnd) |
|
136 { |
|
137 // This function completes as far as the next choice point |
|
138 // aString is a pointer into a buffer with plenty of space in it |
|
139 |
|
140 //Dump(); // DEBUG |
|
141 if (!iHasChildArray && iLetter && iPtr && aString+1 < aEnd) |
|
142 { |
|
143 *aString = Sprog()->iLetter; |
|
144 aString++; |
|
145 *aString = 0; |
|
146 return Sprog()->TabFill(aString, aEnd); |
|
147 } |
|
148 else |
|
149 { |
|
150 return this; |
|
151 } |
|
152 } |
|
153 |
|
154 void RNode::CompleteL(TDes& aPrefix, CDesC16Array& aResults) |
|
155 { |
|
156 TUint16* ptr = (TUint16*)aPrefix.PtrZ(); |
|
157 TUint16* end = ptr + aPrefix.MaxLength(); |
|
158 RNode* endNode = WalkToEndOfString(ptr); |
|
159 if (ptr != aPrefix.Ptr() + aPrefix.Length()) return; // We failed to walk the whole of the string so we have nothing to suggest (the string is longer than anything in the tree) |
|
160 |
|
161 endNode = endNode->TabFill(ptr, end); |
|
162 TInt newLen = ptr - aPrefix.Ptr(); |
|
163 if (endNode->iLetter == 0 && newLen > 0) newLen--; // If ptr got as far as the null termination, we need to make our length one shorter |
|
164 //RDebug::Printf("Setting aPrefix len to %d, len=%d maxlen=%d", newLen, aPrefix.Length(), aPrefix.MaxLength()); |
|
165 aPrefix.SetLength(newLen); |
|
166 |
|
167 // Now that aPrefix has been completed with as much as didn't have any choices, fill aResults with the choices |
|
168 RLtkBuf current; |
|
169 current.CreateLC(256); |
|
170 current.AppendL(aPrefix); |
|
171 if (current.Length()) current.SetLength(current.Length()-1); // Remove endNode's char as DoCompleteOptionsL expects to do that bit |
|
172 endNode->DoCompleteOptionsL(aResults, current); |
|
173 // Make sure last string is included |
|
174 aResults.AppendL(current); |
|
175 CleanupStack::PopAndDestroy(¤t); |
|
176 aResults.Sort(); |
|
177 } |
|
178 |
|
179 void RNode::DoCompleteOptionsL(CDesC16Array& aResults, RLtkBuf& aCurrent) |
|
180 { |
|
181 if (iLetter) |
|
182 { |
|
183 aCurrent.ReserveExtraL(1); |
|
184 aCurrent.Append(TChar(iLetter)); |
|
185 } |
|
186 TInt currentLen = aCurrent.Length(); |
|
187 |
|
188 if (iHasChildArray) |
|
189 { |
|
190 for (int i = 0; i < Sprogs().Count(); i++) |
|
191 { |
|
192 RNode* child = Sprogs()[i]; |
|
193 if (i > 0) |
|
194 { |
|
195 // A new prefix is in order |
|
196 aResults.AppendL(aCurrent); |
|
197 aCurrent.SetLength(currentLen); |
|
198 } |
|
199 child->DoCompleteOptionsL(aResults, aCurrent); |
|
200 } |
|
201 } |
|
202 else if (iLetter != 0) |
|
203 { |
|
204 if (Sprog()) Sprog()->DoCompleteOptionsL(aResults, aCurrent); |
|
205 } |
|
206 } |
|
207 |
|
208 RNode::~RNode() |
|
209 { |
|
210 if (iHasChildArray) |
|
211 { |
|
212 RArray<RNode*>& children = Sprogs(); |
|
213 const TInt count = children.Count(); |
|
214 for (TInt i = 0; i < count; i++) |
|
215 { |
|
216 RNode* node = children[i]; |
|
217 delete node; |
|
218 } |
|
219 children.Close(); |
|
220 delete &children; |
|
221 } |
|
222 else if (iLetter != 0) |
|
223 { |
|
224 delete Sprog(); |
|
225 } |
|
226 } |
|
227 |
|
228 /* |
|
229 #include <e32debug.h> |
|
230 void RNode::Dump() const |
|
231 { |
|
232 TInt sprogCount = Sprogs().Count(); |
|
233 for (int i = 0; i < sprogCount; i++) |
|
234 { |
|
235 RNode* child = Sprogs()[i]; |
|
236 RDebug::Printf("Sprog %i is letter %c", i, child->iLetter); |
|
237 } |
|
238 } |
|
239 */ |
|
240 |
|
241 TInt RNode::ValueForStringL(const TDesC& aString) const |
|
242 { |
|
243 const RNode* node = this; |
|
244 for (TInt i = 0; i < aString.Length(); i++) |
|
245 { |
|
246 node = node->ChildForLetter(aString[i]); |
|
247 if (!node) User::Leave(KErrNotFound); |
|
248 } |
|
249 node = node->ChildForLetter(0); // The null terminator node is the one with the value in |
|
250 if (!node) User::Leave(KErrNotFound); |
|
251 ASSERT(!node->iHasChildArray); |
|
252 return reinterpret_cast<TInt>(node->iPtr); |
|
253 } |