- Implement more of RtlInsertUnicodePrefix: handle case where tree was found, and...
[reactos.git] / reactos / lib / rtl / unicodeprefix.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * PURPOSE: Unicode Prefix implementation
5 * FILE: lib/rtl/unicodeprefix.c
6 * PROGRAMMER: Alex Ionescu (alex@relsoft.net)
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 /*
17 * FIXME: Try to find the official names and add to NDK
18 * Definitions come from fastfat driver.
19 */
20 typedef USHORT NODE_TYPE_CODE;
21 #define PFX_NTC_TABLE ((NODE_TYPE_CODE)0x0800)
22 #define PFX_NTC_ROOT ((NODE_TYPE_CODE)0x0801)
23 #define PFX_NTC_CHILD ((NODE_TYPE_CODE)0x0802)
24 #define PFX_NTC_CASE_MATCH ((NODE_TYPE_CODE)0x0803)
25
26 /* FUNCTIONS ***************************************************************/
27
28 STATIC
29 ULONG
30 NTAPI
31 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
32 {
33 ULONG Chars = UnicodeName->Length / sizeof(WCHAR);
34 ULONG i, NamesFound = 1;
35
36 /* Loop the string */
37 for (i = 0; i < (Chars - 1); i++)
38 {
39 /* Check if we found a backslash, meaning another name */
40 if (UnicodeName->Buffer[i] == '\\') NamesFound++;
41 }
42
43 /* Return the number of names found */
44 return NamesFound;
45 }
46
47
48 STATIC
49 RTL_GENERIC_COMPARE_RESULTS
50 NTAPI
51 CompareUnicodeStrings(IN PUNICODE_STRING String,
52 IN PUNICODE_STRING Prefix,
53 IN ULONG CaseCheckChar)
54 {
55 ULONG StringLength = String->Length / sizeof(WCHAR);
56 ULONG PrefixLength = Prefix->Length / sizeof(WCHAR);
57 ULONG ScanLength = min(StringLength, PrefixLength);
58 ULONG i;
59 WCHAR FoundPrefix, FoundString;
60
61 /* Validate the Case Check Character Position */
62 if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
63
64 /* Do the case sensitive comparison first */
65 for (i = 0; i < CaseCheckChar; i++)
66 {
67 /* Compare the two characters */
68 if (Prefix->Buffer[i] != String->Buffer[i]) break;
69 }
70
71 /* Save the characters we found */
72 FoundPrefix = Prefix->Buffer[i];
73 FoundString = String->Buffer[i];
74
75 /* Check if we exausted the search above */
76 if (i == CaseCheckChar)
77 {
78 /* FIXME: Do a case-insensitive search */
79 }
80
81 /* Check if we weren't able to find a match in the loops */
82 if (i < ScanLength)
83 {
84 /* If the prefix character found was a backslash, this is a less */
85 if (FoundPrefix == '\\') return GenericLessThan;
86
87 /* If the string character found was a backslack, then this is a more */
88 if (FoundString == '\\') return GenericGreaterThan;
89
90 /* None of those two special cases, do a normal check */
91 if (FoundPrefix < FoundString) return GenericLessThan;
92
93 /* The only choice left is that Prefix > String */
94 return GenericGreaterThan;
95 }
96
97 /* If we got here, a match was found. Check if the prefix is smaller */
98 if (PrefixLength < StringLength)
99 {
100 /* Check if the string is actually a prefix */
101 if (String->Buffer[PrefixLength] == '\\') return -1;
102
103 /* It's not a prefix, and it's shorter, so it's a less */
104 return GenericLessThan;
105 }
106
107 /* Check if the prefix is longer */
108 if (PrefixLength > StringLength) return GenericGreaterThan;
109
110 /* If we got here, then they are 100% equal */
111 return GenericEqual;
112 }
113
114 /*
115 * @unimplemented
116 */
117 PUNICODE_PREFIX_TABLE_ENTRY
118 NTAPI
119 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
120 PUNICODE_STRING FullName,
121 ULONG CaseInsensitiveIndex)
122 {
123 UNIMPLEMENTED;
124 return 0;
125 }
126
127 /*
128 * @implemented
129 */
130 VOID
131 NTAPI
132 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
133 {
134 /* Setup the table */
135 PrefixTable->NameLength = 0;
136 PrefixTable->LastNextEntry = NULL;
137 PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
138 PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
139 }
140
141 /*
142 * @unimplemented
143 */
144 BOOLEAN
145 NTAPI
146 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
147 PUNICODE_STRING Prefix,
148 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
149 {
150 /*
151 * implementation notes:
152 * - get name length (number of names) DONE
153 * - init splay links DONE
154 * - find a matching tree DONE
155 * - if !found, insert a new NTC_ROOT entry and return TRUE; DONE
156 * - if found, loop tree and compare strings: DONE
157 * if equal, handle casematch/nomatch DONE
158 * if greater or lesser equal, then add left/right childs accordingly
159 * - splay the tree DONE
160 */
161 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
162 ULONG NameCount;
163 RTL_GENERIC_COMPARE_RESULTS Result;
164 PRTL_SPLAY_LINKS SplayLinks;
165
166 /* Find out how many names there are */
167 NameCount = ComputeUnicodeNameLength(Prefix);
168
169 /* Set up the initial entry data */
170 PrefixTableEntry->NameLength = NameCount;
171 PrefixTableEntry->Prefix = Prefix;
172 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
173
174 /* Find the right spot where to insert this entry */
175 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
176 CurrentEntry = PreviousEntry->NextPrefixTree;
177 while (CurrentEntry->NameLength > NameCount)
178 {
179 /* Not a match, move to the next entry */
180 PreviousEntry = CurrentEntry;
181 CurrentEntry = CurrentEntry->NextPrefixTree;
182 }
183
184 /* Check if we did find a tree by now */
185 if (CurrentEntry->NameLength != NameCount)
186 {
187 /* We didn't, so insert a new entry in the list */
188 PreviousEntry->NextPrefixTree = PrefixTableEntry;
189 PrefixTableEntry->NextPrefixTree = CurrentEntry;
190
191 /* This is now a root entry with case match */
192 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
193 PrefixTableEntry->CaseMatch = PrefixTableEntry;
194
195 /* Quick return */
196 return TRUE;
197 }
198
199 /* We found a tree, so star thte search loop */
200 Entry = CurrentEntry;
201 while (TRUE)
202 {
203 /* Do a case-insensitive comparison to find out the match level */
204 Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
205 if (Result == GenericEqual)
206 {
207 /* We have a match, start doing a case-sensitive search */
208 NextEntry = Entry;
209
210 /* Search the circular case-match list */
211 do
212 {
213 /* Check if we found a match */
214 if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
215 (GenericEqual))
216 {
217 /* We must fail the insert: it already exists */
218 return FALSE;
219 }
220
221 /* Move to the next entry in the circular list */
222 NextEntry = NextEntry->CaseMatch;
223 }
224 while (NextEntry != Entry);
225
226 /*
227 * No match found, so we can safely insert it. Remember that a
228 * case insensitive match was found, so this is not a ROOT NTC
229 * but a Case Match NTC instead.
230 */
231 PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
232 PrefixTableEntry->NextPrefixTree = NULL;
233
234 /* Insert it into the circular list */
235 PrefixTableEntry->CaseMatch = Entry->CaseMatch;
236 Entry->CaseMatch = PrefixTableEntry;
237 }
238 else if (Result == GenericGreaterThan)
239 {
240 /* TODO: Check out the left child and add us */
241 }
242 else
243 {
244 /* TODO: Check out the right child and add us */
245 }
246 }
247
248 /* Get the next tree entry */
249 NextEntry = CurrentEntry->NextPrefixTree;
250
251 /* Set what was the current entry to a child entry */
252 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
253 CurrentEntry->NextPrefixTree = NULL;
254
255 /* Splay the tree */
256 SplayLinks = RtlSplay(&Entry->Links);
257
258 /* The link points to the root, get it */
259 Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
260
261 /* Mark the root as a root entry */
262 Entry->NodeTypeCode = PFX_NTC_ROOT;
263
264 /* Add it to the tree list */
265 PreviousEntry->NextPrefixTree = Entry;
266 Entry->NextPrefixTree = NextEntry;
267
268 /* Return success */
269 return TRUE;
270 }
271
272 /*
273 * @implemented
274 */
275 PUNICODE_PREFIX_TABLE_ENTRY
276 NTAPI
277 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
278 BOOLEAN Restart)
279 {
280 PRTL_SPLAY_LINKS SplayLinks;
281 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
282
283 /* We might need this entry 2/3rd of the time, so cache it now */
284 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
285
286 /* Check if this is a restart or if we don't have a last entry */
287 if ((Restart) || !(PrefixTable->LastNextEntry))
288 {
289 /* Get the next entry and validate it */
290 Entry = PrefixTable->NextPrefixTree;
291 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
292
293 /* Now get the Splay Tree Links */
294 SplayLinks = &Entry->Links;
295
296 /* Loop until we get the first node in the tree */
297 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
298
299 /* Get the entry from it */
300 Entry = CONTAINING_RECORD(SplayLinks,
301 UNICODE_PREFIX_TABLE_ENTRY,
302 Links);
303 }
304 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
305 {
306 /* If the last entry was a Case Match, then return it */
307 Entry = CaseMatchEntry;
308 }
309 else
310 {
311 /* Find the successor */
312 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
313 if (!SplayLinks)
314 {
315 /* Didn't find one, we'll have to search the tree */
316 SplayLinks = &PrefixTable->LastNextEntry->Links;
317
318 /* Get the topmost node (root) */
319 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
320 Entry = CONTAINING_RECORD(SplayLinks,
321 UNICODE_PREFIX_TABLE_ENTRY,
322 Links);
323
324 /* Get its tree and make sure somethign is in it */
325 Entry = Entry->NextPrefixTree;
326 if (Entry->NameLength <= 0) return NULL;
327
328 /* Select these new links and find the first node */
329 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
330 }
331
332 /* Get the entry from it */
333 Entry = CONTAINING_RECORD(SplayLinks,
334 UNICODE_PREFIX_TABLE_ENTRY,
335 Links);
336 }
337
338 /* Save this entry as the last one returned, and return it */
339 PrefixTable->LastNextEntry = Entry;
340 return Entry;
341 }
342
343 /*
344 * @implemented
345 */
346 VOID
347 NTAPI
348 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
349 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
350 {
351 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
352 PRTL_SPLAY_LINKS SplayLinks;
353
354 /* Erase the last entry */
355 PrefixTable->LastNextEntry = NULL;
356
357 /* Check if this was a Case Match Entry */
358 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
359 {
360 /* Get the case match entry */
361 Entry = PrefixTableEntry->CaseMatch;
362
363 /* Now loop until we find one referencing what the caller sent */
364 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
365
366 /* We found the entry that was sent, link them to delete this entry */
367 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
368 }
369 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
370 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
371 {
372 /* Check if this entry is a case match */
373 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
374 {
375 /* Get the case match entry */
376 Entry = PrefixTableEntry->CaseMatch;
377
378 /* Now loop until we find one referencing what the caller sent */
379 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
380
381 /* We found the entry that was sent, link them to delete this entry */
382 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
383
384 /* Copy the data */
385 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
386 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
387 Entry->Links = PrefixTableEntry->Links;
388
389 /* Now check if we are a root entry */
390 if (RtlIsRoot(&PrefixTableEntry->Links))
391 {
392 /* We are, so make this entry root as well */
393 Entry->Links.Parent = &Entry->Links;
394
395 /* Find the entry referencing us */
396 RefEntry = Entry->NextPrefixTree;
397 while (RefEntry->NextPrefixTree != Entry)
398 {
399 /* Not this one, move to the next entry */
400 RefEntry = RefEntry->NextPrefixTree;
401 }
402
403 /* Link them to us now */
404 RefEntry->NextPrefixTree = Entry;
405 }
406 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
407 {
408 /* We were the left child, so make us as well */
409 PrefixTableEntry->Links.LeftChild = &Entry->Links;
410 }
411 else
412 {
413 /* We were the right child, so make us as well */
414 PrefixTableEntry->Links.RightChild = &Entry->Links;
415 }
416
417 /* Check if we have a left child */
418 if (RtlLeftChild(&Entry->Links))
419 {
420 /* Update its parent link */
421 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
422 }
423 /* Check if we have a right child */
424 if (RtlRightChild(&Entry->Links))
425 {
426 /* Update its parent link */
427 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
428 }
429 }
430 else
431 {
432 /* It's not a case match, so we'll delete the actual entry */
433 SplayLinks = &PrefixTableEntry->Links;
434
435 /* Find the root entry */
436 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
437 Entry = CONTAINING_RECORD(SplayLinks,
438 UNICODE_PREFIX_TABLE_ENTRY,
439 Links);
440
441 /* Delete the entry and check if the whole tree is gone */
442 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
443 if (!SplayLinks)
444 {
445 /* The tree is also gone now, find the entry referencing us */
446 RefEntry = Entry->NextPrefixTree;
447 while (RefEntry->NextPrefixTree != Entry)
448 {
449 /* Not this one, move to the next entry */
450 RefEntry = RefEntry->NextPrefixTree;
451 }
452
453 /* Link them so this entry stops being referenced */
454 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
455 }
456 else if (&Entry->Links != SplayLinks)
457 {
458 /* The tree is still here, but we got moved to a new one */
459 NewEntry = CONTAINING_RECORD(SplayLinks,
460 UNICODE_PREFIX_TABLE_ENTRY,
461 Links);
462
463 /* Find the entry referencing us */
464 RefEntry = Entry->NextPrefixTree;
465 while (RefEntry->NextPrefixTree != Entry)
466 {
467 /* Not this one, move to the next entry */
468 RefEntry = RefEntry->NextPrefixTree;
469 }
470
471 /* Since we got moved, make us the new root entry */
472 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
473
474 /* Link us with the entry referencing the old root */
475 RefEntry->NextPrefixTree = NewEntry;
476
477 /* And link us with the old tree */
478 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
479
480 /* Set the old tree as a child */
481 Entry->NodeTypeCode = PFX_NTC_CHILD;
482 Entry->NextPrefixTree = NULL;
483 }
484 }
485 }
486 }
487
488 /* EOF */