- Finish implementing RtlFindUnicodePrefix. The Windows NPFS driver should load now...
[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 PWCHAR p, p1;
61
62 /* Validate the Case Check Character Position */
63 if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
64
65 /* Do the case sensitive comparison first */
66 for (i = 0; i < CaseCheckChar; i++)
67 {
68 /* Compare the two characters */
69 if (Prefix->Buffer[i] != String->Buffer[i]) break;
70 }
71
72 /* Save the characters we found */
73 FoundPrefix = Prefix->Buffer[i];
74 FoundString = String->Buffer[i];
75
76 /* Check if we exausted the search above */
77 if (i == CaseCheckChar)
78 {
79 /* Do a case-insensitive search */
80 p = &Prefix->Buffer[i];
81 p1 = &String->Buffer[i];
82 do
83 {
84 /* Move to the next character */
85 FoundPrefix = *p++;
86 FoundString = *p1++;
87
88 /* Compare it */
89 if (FoundPrefix != FoundString)
90 {
91 /* Upcase the characters */
92 FoundPrefix = RtlUpcaseUnicodeChar(FoundPrefix);
93 FoundString = RtlUpcaseUnicodeChar(FoundString);
94
95 /* Compare them again */
96 if (FoundPrefix != FoundString) break;
97 }
98
99 /* Move to the next char */
100 i++;
101 } while (i < ScanLength);
102 }
103
104 /* Check if we weren't able to find a match in the loops */
105 if (i < ScanLength)
106 {
107 /* If the prefix character found was a backslash, this is a less */
108 if (FoundPrefix == '\\') return GenericLessThan;
109
110 /* If the string character found was a backslack, then this is a more */
111 if (FoundString == '\\') return GenericGreaterThan;
112
113 /* None of those two special cases, do a normal check */
114 if (FoundPrefix < FoundString) return GenericLessThan;
115
116 /* The only choice left is that Prefix > String */
117 return GenericGreaterThan;
118 }
119
120 /* If we got here, a match was found. Check if the prefix is smaller */
121 if (PrefixLength < StringLength)
122 {
123 /* Check if the string is actually a prefix */
124 if (String->Buffer[PrefixLength] == '\\') return -1;
125
126 /* It's not a prefix, and it's shorter, so it's a less */
127 return GenericLessThan;
128 }
129
130 /* Check if the prefix is longer */
131 if (PrefixLength > StringLength) return GenericGreaterThan;
132
133 /* If we got here, then they are 100% equal */
134 return GenericEqual;
135 }
136
137 /*
138 * @implemented
139 */
140 PUNICODE_PREFIX_TABLE_ENTRY
141 NTAPI
142 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
143 PUNICODE_STRING FullName,
144 ULONG CaseInsensitiveIndex)
145 {
146 ULONG NameCount;
147 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
148 PRTL_SPLAY_LINKS SplayLinks;
149 RTL_GENERIC_COMPARE_RESULTS Result;
150
151 /* Find out how many names there are */
152 NameCount = ComputeUnicodeNameLength(FullName);
153
154 /* Find the right spot where to start looking for this entry */
155 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
156 CurrentEntry = PreviousEntry->NextPrefixTree;
157 while (CurrentEntry->NameLength > NameCount)
158 {
159 /* Not a match, move to the next entry */
160 PreviousEntry = CurrentEntry;
161 CurrentEntry = CurrentEntry->NextPrefixTree;
162 }
163
164 /* Loop every entry which has valid entries */
165 while (CurrentEntry->NameLength)
166 {
167 /* Get the splay links and loop */
168 while ((SplayLinks = &CurrentEntry->Links))
169 {
170 /*
171 * Implementation notes:
172 * - get the entry
173 * - compare the entry's prefix with the fullname:
174 * if greater: restart on the left child
175 * if lesser: restart on the right child
176 * - else if equal:
177 * for caseinsensitive, just return the entry and
178 * splay it and set it as root if it's a child
179 * for casesensitive, loop the circular case match list and
180 * keep comparing for each entry
181 */
182 Entry = CONTAINING_RECORD(SplayLinks,
183 UNICODE_PREFIX_TABLE_ENTRY,
184 Links);
185
186 /* Do the comparison */
187 Result = CompareUnicodeStrings(Entry->Prefix, FullName, 0);
188 if (Result == GenericGreaterThan)
189 {
190 /* Prefix is greater, so restart on the left child */
191 SplayLinks = RtlLeftChild(SplayLinks);
192 continue;
193 }
194 else if (Result == GenericLessThan)
195 {
196 /* Prefix is smaller, so restart on the right child */
197 SplayLinks = RtlRightChild(SplayLinks);
198 continue;
199 }
200
201 /*
202 * We have a match, check if this was a case-sensitive search
203 * NOTE: An index of 0 means case-insensitive(ie, we'll be case
204 * insensitive since index 0, ie, all the time)
205 */
206 if (!CaseInsensitiveIndex)
207 {
208 /*
209 * Check if this entry was a child. We need to return the root,
210 * so if this entry was a child, we'll splay the tree and get
211 * the root, and set the current entry as a child.
212 */
213 if (Entry->NodeTypeCode == PFX_NTC_CHILD)
214 {
215 /* Get the next entry */
216 NextEntry = CurrentEntry->NextPrefixTree;
217
218 /* Make the current entry become a child */
219 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
220 CurrentEntry->NextPrefixTree = NULL;
221
222 /* Splay the tree */
223 SplayLinks = RtlSplay(&Entry->Links);
224
225 /* Get the new root entry */
226 Entry = CONTAINING_RECORD(SplayLinks,
227 UNICODE_PREFIX_TABLE_ENTRY,
228 Links);
229
230 /* Set it as a root entry */
231 Entry->NodeTypeCode = PFX_NTC_ROOT;
232
233 /* Add it to the root entries list */
234 PreviousEntry->NextPrefixTree = Entry;
235 Entry->NextPrefixTree = NextEntry;
236 }
237
238 /* Return the entry */
239 return Entry;
240 }
241
242 /* We'll do a case-sensitive search if we've reached this point */
243 NextEntry = Entry;
244 do
245 {
246 /* Do the case-sensitive search */
247 Result = CompareUnicodeStrings(NextEntry->Prefix,
248 FullName,
249 CaseInsensitiveIndex);
250 if ((Result != GenericLessThan) &&
251 (Result != GenericGreaterThan))
252 {
253 /* This is a positive match, return it */
254 return NextEntry;
255 }
256
257 /* No match yet, continue looping the circular list */
258 NextEntry = NextEntry->CaseMatch;
259 } while (NextEntry != Entry);
260
261 /*
262 * If we got here, then we found a non-case-sensitive match, but
263 * we need to find a case-sensitive match, so we'll just keep
264 * searching the next tree (NOTE: we need to break out for this).
265 */
266 break;
267 }
268
269 /* Splay links exausted, move to next entry */
270 PreviousEntry = CurrentEntry;
271 CurrentEntry = CurrentEntry->NextPrefixTree;
272 }
273
274 /* If we got here, nothing was found */
275 return NULL;
276 }
277
278 /*
279 * @implemented
280 */
281 VOID
282 NTAPI
283 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
284 {
285 /* Setup the table */
286 PrefixTable->NameLength = 0;
287 PrefixTable->LastNextEntry = NULL;
288 PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
289 PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
290 }
291
292 /*
293 * @implemented
294 */
295 BOOLEAN
296 NTAPI
297 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
298 PUNICODE_STRING Prefix,
299 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
300 {
301 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
302 ULONG NameCount;
303 RTL_GENERIC_COMPARE_RESULTS Result;
304 PRTL_SPLAY_LINKS SplayLinks;
305
306 /* Find out how many names there are */
307 NameCount = ComputeUnicodeNameLength(Prefix);
308
309 /* Set up the initial entry data */
310 PrefixTableEntry->NameLength = NameCount;
311 PrefixTableEntry->Prefix = Prefix;
312 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
313
314 /* Find the right spot where to insert this entry */
315 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
316 CurrentEntry = PreviousEntry->NextPrefixTree;
317 while (CurrentEntry->NameLength > NameCount)
318 {
319 /* Not a match, move to the next entry */
320 PreviousEntry = CurrentEntry;
321 CurrentEntry = CurrentEntry->NextPrefixTree;
322 }
323
324 /* Check if we did find a tree by now */
325 if (CurrentEntry->NameLength != NameCount)
326 {
327 /* We didn't, so insert a new entry in the list */
328 PreviousEntry->NextPrefixTree = PrefixTableEntry;
329 PrefixTableEntry->NextPrefixTree = CurrentEntry;
330
331 /* This is now a root entry with case match */
332 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
333 PrefixTableEntry->CaseMatch = PrefixTableEntry;
334
335 /* Quick return */
336 return TRUE;
337 }
338
339 /* We found a tree, so star thte search loop */
340 Entry = CurrentEntry;
341 while (TRUE)
342 {
343 /* Do a case-insensitive comparison to find out the match level */
344 Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
345 if (Result == GenericEqual)
346 {
347 /* We have a match, start doing a case-sensitive search */
348 NextEntry = Entry;
349
350 /* Search the circular case-match list */
351 do
352 {
353 /* Check if we found a match */
354 if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
355 (GenericEqual))
356 {
357 /* We must fail the insert: it already exists */
358 return FALSE;
359 }
360
361 /* Move to the next entry in the circular list */
362 NextEntry = NextEntry->CaseMatch;
363 }
364 while (NextEntry != Entry);
365
366 /*
367 * No match found, so we can safely insert it. Remember that a
368 * case insensitive match was found, so this is not a ROOT NTC
369 * but a Case Match NTC instead.
370 */
371 PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
372 PrefixTableEntry->NextPrefixTree = NULL;
373
374 /* Insert it into the circular list */
375 PrefixTableEntry->CaseMatch = Entry->CaseMatch;
376 Entry->CaseMatch = PrefixTableEntry;
377 }
378 else if (Result == GenericGreaterThan)
379 {
380 /* Check out if we have a left child */
381 if (RtlLeftChild(&Entry->Links))
382 {
383 /* We do, enter it and restart the loop */
384 SplayLinks = RtlLeftChild(&Entry->Links);
385 Entry = CONTAINING_RECORD(SplayLinks,
386 UNICODE_PREFIX_TABLE_ENTRY,
387 Links);
388 }
389 else
390 {
391 /* We don't, set this entry as a child */
392 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
393 PrefixTableEntry->NextPrefixTree = NULL;
394 PrefixTableEntry->CaseMatch = PrefixTableEntry;
395
396 /* Insert us into the tree */
397 RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
398 break;
399 }
400 }
401 else
402 {
403 /* Check out if we have a right child */
404 if (RtlRightChild(&Entry->Links))
405 {
406 /* We do, enter it and restart the loop */
407 SplayLinks = RtlLeftChild(&Entry->Links);
408 Entry = CONTAINING_RECORD(SplayLinks,
409 UNICODE_PREFIX_TABLE_ENTRY,
410 Links);
411 }
412 else
413 {
414 /* We don't, set this entry as a child */
415 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
416 PrefixTableEntry->NextPrefixTree = NULL;
417 PrefixTableEntry->CaseMatch = PrefixTableEntry;
418
419 /* Insert us into the tree */
420 RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
421 break;
422 }
423 }
424 }
425
426 /* Get the next tree entry */
427 NextEntry = CurrentEntry->NextPrefixTree;
428
429 /* Set what was the current entry to a child entry */
430 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
431 CurrentEntry->NextPrefixTree = NULL;
432
433 /* Splay the tree */
434 SplayLinks = RtlSplay(&Entry->Links);
435
436 /* The link points to the root, get it */
437 Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
438
439 /* Mark the root as a root entry */
440 Entry->NodeTypeCode = PFX_NTC_ROOT;
441
442 /* Add it to the tree list */
443 PreviousEntry->NextPrefixTree = Entry;
444 Entry->NextPrefixTree = NextEntry;
445
446 /* Return success */
447 return TRUE;
448 }
449
450 /*
451 * @implemented
452 */
453 PUNICODE_PREFIX_TABLE_ENTRY
454 NTAPI
455 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
456 BOOLEAN Restart)
457 {
458 PRTL_SPLAY_LINKS SplayLinks;
459 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
460
461 /* We might need this entry 2/3rd of the time, so cache it now */
462 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
463
464 /* Check if this is a restart or if we don't have a last entry */
465 if ((Restart) || !(PrefixTable->LastNextEntry))
466 {
467 /* Get the next entry and validate it */
468 Entry = PrefixTable->NextPrefixTree;
469 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
470
471 /* Now get the Splay Tree Links */
472 SplayLinks = &Entry->Links;
473
474 /* Loop until we get the first node in the tree */
475 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
476
477 /* Get the entry from it */
478 Entry = CONTAINING_RECORD(SplayLinks,
479 UNICODE_PREFIX_TABLE_ENTRY,
480 Links);
481 }
482 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
483 {
484 /* If the last entry was a Case Match, then return it */
485 Entry = CaseMatchEntry;
486 }
487 else
488 {
489 /* Find the successor */
490 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
491 if (!SplayLinks)
492 {
493 /* Didn't find one, we'll have to search the tree */
494 SplayLinks = &PrefixTable->LastNextEntry->Links;
495
496 /* Get the topmost node (root) */
497 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
498 Entry = CONTAINING_RECORD(SplayLinks,
499 UNICODE_PREFIX_TABLE_ENTRY,
500 Links);
501
502 /* Get its tree and make sure somethign is in it */
503 Entry = Entry->NextPrefixTree;
504 if (Entry->NameLength <= 0) return NULL;
505
506 /* Select these new links and find the first node */
507 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
508 }
509
510 /* Get the entry from it */
511 Entry = CONTAINING_RECORD(SplayLinks,
512 UNICODE_PREFIX_TABLE_ENTRY,
513 Links);
514 }
515
516 /* Save this entry as the last one returned, and return it */
517 PrefixTable->LastNextEntry = Entry;
518 return Entry;
519 }
520
521 /*
522 * @implemented
523 */
524 VOID
525 NTAPI
526 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
527 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
528 {
529 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
530 PRTL_SPLAY_LINKS SplayLinks;
531
532 /* Erase the last entry */
533 PrefixTable->LastNextEntry = NULL;
534
535 /* Check if this was a Case Match Entry */
536 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
537 {
538 /* Get the case match entry */
539 Entry = PrefixTableEntry->CaseMatch;
540
541 /* Now loop until we find one referencing what the caller sent */
542 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
543
544 /* We found the entry that was sent, link them to delete this entry */
545 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
546 }
547 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
548 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
549 {
550 /* Check if this entry is a case match */
551 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
552 {
553 /* Get the case match entry */
554 Entry = PrefixTableEntry->CaseMatch;
555
556 /* Now loop until we find one referencing what the caller sent */
557 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
558
559 /* We found the entry that was sent, link them to delete this entry */
560 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
561
562 /* Copy the data */
563 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
564 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
565 Entry->Links = PrefixTableEntry->Links;
566
567 /* Now check if we are a root entry */
568 if (RtlIsRoot(&PrefixTableEntry->Links))
569 {
570 /* We are, so make this entry root as well */
571 Entry->Links.Parent = &Entry->Links;
572
573 /* Find the entry referencing us */
574 RefEntry = Entry->NextPrefixTree;
575 while (RefEntry->NextPrefixTree != Entry)
576 {
577 /* Not this one, move to the next entry */
578 RefEntry = RefEntry->NextPrefixTree;
579 }
580
581 /* Link them to us now */
582 RefEntry->NextPrefixTree = Entry;
583 }
584 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
585 {
586 /* We were the left child, so make us as well */
587 RtlParent(&PrefixTableEntry->Links)->LeftChild = &Entry->Links;
588 }
589 else
590 {
591 /* We were the right child, so make us as well */
592 RtlParent(&PrefixTableEntry->Links)->RightChild = &Entry->Links;
593 }
594
595 /* Check if we have a left child */
596 if (RtlLeftChild(&Entry->Links))
597 {
598 /* Update its parent link */
599 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
600 }
601 /* Check if we have a right child */
602 if (RtlRightChild(&Entry->Links))
603 {
604 /* Update its parent link */
605 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
606 }
607 }
608 else
609 {
610 /* It's not a case match, so we'll delete the actual entry */
611 SplayLinks = &PrefixTableEntry->Links;
612
613 /* Find the root entry */
614 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
615 Entry = CONTAINING_RECORD(SplayLinks,
616 UNICODE_PREFIX_TABLE_ENTRY,
617 Links);
618
619 /* Delete the entry and check if the whole tree is gone */
620 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
621 if (!SplayLinks)
622 {
623 /* The tree is also gone now, find the entry referencing us */
624 RefEntry = Entry->NextPrefixTree;
625 while (RefEntry->NextPrefixTree != Entry)
626 {
627 /* Not this one, move to the next entry */
628 RefEntry = RefEntry->NextPrefixTree;
629 }
630
631 /* Link them so this entry stops being referenced */
632 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
633 }
634 else if (&Entry->Links != SplayLinks)
635 {
636 /* The tree is still here, but we got moved to a new one */
637 NewEntry = CONTAINING_RECORD(SplayLinks,
638 UNICODE_PREFIX_TABLE_ENTRY,
639 Links);
640
641 /* Find the entry referencing us */
642 RefEntry = Entry->NextPrefixTree;
643 while (RefEntry->NextPrefixTree != Entry)
644 {
645 /* Not this one, move to the next entry */
646 RefEntry = RefEntry->NextPrefixTree;
647 }
648
649 /* Since we got moved, make us the new root entry */
650 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
651
652 /* Link us with the entry referencing the old root */
653 RefEntry->NextPrefixTree = NewEntry;
654
655 /* And link us with the old tree */
656 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
657
658 /* Set the old tree as a child */
659 Entry->NodeTypeCode = PFX_NTC_CHILD;
660 Entry->NextPrefixTree = NULL;
661 }
662 }
663 }
664 }
665
666 /* EOF */