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)
9 /* INCLUDES *****************************************************************/
17 * FIXME: Try to find the official names and add to NDK
18 * Definitions come from fastfat driver.
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)
26 /* FUNCTIONS ***************************************************************/
31 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName
)
33 ULONG Chars
= UnicodeName
->Length
/ sizeof(WCHAR
);
34 ULONG i
, NamesFound
= 1;
37 for (i
= 0; i
< (Chars
- 1); i
++)
39 /* Check if we found a backslash, meaning another name */
40 if (UnicodeName
->Buffer
[i
] == '\\') NamesFound
++;
43 /* Return the number of names found */
48 RTL_GENERIC_COMPARE_RESULTS
50 CompareUnicodeStrings(IN PUNICODE_STRING Prefix
,
51 IN PUNICODE_STRING String
,
52 IN ULONG CaseCheckChar
)
54 ULONG StringLength
= String
->Length
/ sizeof(WCHAR
);
55 ULONG PrefixLength
= Prefix
->Length
/ sizeof(WCHAR
);
56 ULONG ScanLength
= min(StringLength
, PrefixLength
);
58 WCHAR FoundPrefix
, FoundString
;
60 DPRINT("CompareUnicodeStrings: %wZ %wZ\n", String
, Prefix
);
62 /* Handle case noticed in npfs when Prefix = '\' and name starts with '\' */
63 if ((PrefixLength
== 1) &&
64 (Prefix
->Buffer
[0] == '\\') &&
66 (String
->Buffer
[0] == '\\'))
68 /* The string is actually a prefix */
72 /* Validate the Case Check Character Position */
73 if (CaseCheckChar
> ScanLength
) CaseCheckChar
= ScanLength
;
75 /* Do the case sensitive comparison first */
76 for (i
= 0; i
< CaseCheckChar
; i
++)
78 /* Compare the two characters */
79 if (Prefix
->Buffer
[i
] != String
->Buffer
[i
]) break;
82 /* Save the characters we found */
83 FoundPrefix
= Prefix
->Buffer
[i
];
84 FoundString
= String
->Buffer
[i
];
86 /* Check if we exausted the search above */
87 if (i
== CaseCheckChar
)
89 /* Do a case-insensitive search */
90 p
= &Prefix
->Buffer
[i
];
91 p1
= &String
->Buffer
[i
];
94 /* Move to the next character */
99 if (FoundPrefix
!= FoundString
)
101 /* Upcase the characters */
102 FoundPrefix
= RtlUpcaseUnicodeChar(FoundPrefix
);
103 FoundString
= RtlUpcaseUnicodeChar(FoundString
);
105 /* Compare them again */
106 if (FoundPrefix
!= FoundString
) break;
109 /* Move to the next char */
111 } while (i
< ScanLength
);
114 /* Check if we weren't able to find a match in the loops */
117 /* If the prefix character found was a backslash, this is a less */
118 if (FoundPrefix
== '\\') return GenericLessThan
;
120 /* If the string character found was a backslack, then this is a more */
121 if (FoundString
== '\\') return GenericGreaterThan
;
123 /* None of those two special cases, do a normal check */
124 if (FoundPrefix
< FoundString
) return GenericLessThan
;
126 /* The only choice left is that Prefix > String */
127 return GenericGreaterThan
;
130 /* If we got here, a match was found. Check if the prefix is smaller */
131 if (PrefixLength
< StringLength
)
133 /* Check if the string is actually a prefix */
134 if (String
->Buffer
[PrefixLength
] == '\\') return -1;
136 /* It's not a prefix, and it's shorter, so it's a less */
137 return GenericLessThan
;
140 /* Check if the prefix is longer */
141 if (PrefixLength
> StringLength
) return GenericGreaterThan
;
143 /* If we got here, then they are 100% equal */
150 PUNICODE_PREFIX_TABLE_ENTRY
152 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
153 PUNICODE_STRING FullName
,
154 ULONG CaseInsensitiveIndex
)
157 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry
, PreviousEntry
, Entry
, NextEntry
;
158 PRTL_SPLAY_LINKS SplayLinks
;
159 RTL_GENERIC_COMPARE_RESULTS Result
;
160 DPRINT("RtlFindUnicodePrefix\n");
162 /* Find out how many names there are */
163 NameCount
= ComputeUnicodeNameLength(FullName
);
165 /* Find the right spot where to start looking for this entry */
166 PreviousEntry
= (PUNICODE_PREFIX_TABLE_ENTRY
)PrefixTable
;
167 CurrentEntry
= PreviousEntry
->NextPrefixTree
;
168 while (CurrentEntry
->NameLength
> NameCount
)
170 /* Not a match, move to the next entry */
171 PreviousEntry
= CurrentEntry
;
172 CurrentEntry
= CurrentEntry
->NextPrefixTree
;
175 /* Loop every entry which has valid entries */
176 while (CurrentEntry
->NameLength
)
178 DPRINT("CurrentEntry->NameLength 0x%x\n", CurrentEntry
->NameLength
);
180 /* Get the splay links and loop */
181 SplayLinks
= &CurrentEntry
->Links
;
185 DPRINT("SplayLinks %p\n", SplayLinks
);
186 Entry
= CONTAINING_RECORD(SplayLinks
,
187 UNICODE_PREFIX_TABLE_ENTRY
,
190 /* Do the comparison */
191 Result
= CompareUnicodeStrings(Entry
->Prefix
, FullName
, 0);
192 DPRINT("Result 0x%x\n", Result
);
193 if (Result
== GenericGreaterThan
)
195 /* Prefix is greater, so restart on the left child */
196 SplayLinks
= RtlLeftChild(SplayLinks
);
199 else if (Result
== GenericLessThan
)
201 /* Prefix is smaller, so restart on the right child */
202 SplayLinks
= RtlRightChild(SplayLinks
);
207 * We have a match, check if this was a case-sensitive search
208 * NOTE: An index of 0 means case-insensitive(ie, we'll be case
209 * insensitive since index 0, ie, all the time)
211 DPRINT("CaseInsensitiveIndex %lx\n", CaseInsensitiveIndex
);
212 if (!CaseInsensitiveIndex
)
215 * Check if this entry was a child. We need to return the root,
216 * so if this entry was a child, we'll splay the tree and get
217 * the root, and set the current entry as a child.
219 if (Entry
->NodeTypeCode
== PFX_NTC_CHILD
)
221 /* Get the next entry */
222 NextEntry
= CurrentEntry
->NextPrefixTree
;
224 /* Make the current entry become a child */
225 CurrentEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
226 CurrentEntry
->NextPrefixTree
= NULL
;
229 SplayLinks
= RtlSplay(&Entry
->Links
);
231 /* Get the new root entry */
232 Entry
= CONTAINING_RECORD(SplayLinks
,
233 UNICODE_PREFIX_TABLE_ENTRY
,
236 /* Set it as a root entry */
237 Entry
->NodeTypeCode
= PFX_NTC_ROOT
;
239 /* Add it to the root entries list */
240 PreviousEntry
->NextPrefixTree
= Entry
;
241 Entry
->NextPrefixTree
= NextEntry
;
244 /* Return the entry */
245 DPRINT("RtlFindUnicodePrefix: %p\n", Entry
);
249 /* We'll do a case-sensitive search if we've reached this point */
253 /* Do the case-sensitive search */
254 Result
= CompareUnicodeStrings(NextEntry
->Prefix
,
256 CaseInsensitiveIndex
);
257 if ((Result
!= GenericLessThan
) &&
258 (Result
!= GenericGreaterThan
))
260 /* This is a positive match, return it */
261 DPRINT("RtlFindUnicodePrefix: %p\n", NextEntry
);
265 /* No match yet, continue looping the circular list */
266 NextEntry
= NextEntry
->CaseMatch
;
267 DPRINT("NextEntry %p\n", NextEntry
);
268 } while (NextEntry
!= Entry
);
271 * If we got here, then we found a non-case-sensitive match, but
272 * we need to find a case-sensitive match, so we'll just keep
273 * searching the next tree (NOTE: we need to break out for this).
278 /* Splay links exausted, move to next entry */
279 PreviousEntry
= CurrentEntry
;
280 CurrentEntry
= CurrentEntry
->NextPrefixTree
;
281 DPRINT("CurrentEntry %p\n", CurrentEntry
);
284 /* If we got here, nothing was found */
285 DPRINT("RtlFindUnicodePrefix: %p\n", NULL
);
294 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
)
296 /* Setup the table */
297 PrefixTable
->NameLength
= 0;
298 PrefixTable
->LastNextEntry
= NULL
;
299 PrefixTable
->NodeTypeCode
= PFX_NTC_TABLE
;
300 PrefixTable
->NextPrefixTree
= (PUNICODE_PREFIX_TABLE_ENTRY
)PrefixTable
;
308 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
309 PUNICODE_STRING Prefix
,
310 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
)
312 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry
, PreviousEntry
, Entry
, NextEntry
;
314 RTL_GENERIC_COMPARE_RESULTS Result
;
315 PRTL_SPLAY_LINKS SplayLinks
;
316 DPRINT("RtlInsertUnicodePrefix\n");
318 /* Find out how many names there are */
319 NameCount
= ComputeUnicodeNameLength(Prefix
);
321 /* Set up the initial entry data */
322 PrefixTableEntry
->NameLength
= NameCount
;
323 PrefixTableEntry
->Prefix
= Prefix
;
324 RtlInitializeSplayLinks(&PrefixTableEntry
->Links
);
326 /* Find the right spot where to insert this entry */
327 PreviousEntry
= (PUNICODE_PREFIX_TABLE_ENTRY
)PrefixTable
;
328 CurrentEntry
= PreviousEntry
->NextPrefixTree
;
329 while (CurrentEntry
->NameLength
> NameCount
)
331 /* Not a match, move to the next entry */
332 PreviousEntry
= CurrentEntry
;
333 CurrentEntry
= CurrentEntry
->NextPrefixTree
;
336 /* Check if we did find a tree by now */
337 if (CurrentEntry
->NameLength
!= NameCount
)
339 /* We didn't, so insert a new entry in the list */
340 PreviousEntry
->NextPrefixTree
= PrefixTableEntry
;
341 PrefixTableEntry
->NextPrefixTree
= CurrentEntry
;
343 /* This is now a root entry with case match */
344 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_ROOT
;
345 PrefixTableEntry
->CaseMatch
= PrefixTableEntry
;
348 DPRINT("RtlInsertUnicodePrefix TRUE\n");
352 /* We found a tree, so star thte search loop */
353 Entry
= CurrentEntry
;
356 /* Do a case-insensitive comparison to find out the match level */
357 Result
= CompareUnicodeStrings(Entry
->Prefix
, Prefix
, 0);
358 if (Result
== GenericEqual
)
360 /* We have a match, start doing a case-sensitive search */
363 /* Search the circular case-match list */
366 /* Check if we found a match */
367 if (CompareUnicodeStrings(NextEntry
->Prefix
, Prefix
, -1) ==
370 /* We must fail the insert: it already exists */
371 DPRINT("RtlInsertUnicodePrefix FALSE\n");
375 /* Move to the next entry in the circular list */
376 NextEntry
= NextEntry
->CaseMatch
;
378 while (NextEntry
!= Entry
);
381 * No match found, so we can safely insert it. Remember that a
382 * case insensitive match was found, so this is not a ROOT NTC
383 * but a Case Match NTC instead.
385 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_CASE_MATCH
;
386 PrefixTableEntry
->NextPrefixTree
= NULL
;
388 /* Insert it into the circular list */
389 PrefixTableEntry
->CaseMatch
= Entry
->CaseMatch
;
390 Entry
->CaseMatch
= PrefixTableEntry
;
394 /* Check if the result was greater or lesser than */
395 if (Result
== GenericGreaterThan
)
397 /* Check out if we have a left child */
398 if (RtlLeftChild(&Entry
->Links
))
400 /* We do, enter it and restart the loop */
401 SplayLinks
= RtlLeftChild(&Entry
->Links
);
402 Entry
= CONTAINING_RECORD(SplayLinks
,
403 UNICODE_PREFIX_TABLE_ENTRY
,
408 /* We don't, set this entry as a child */
409 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
410 PrefixTableEntry
->NextPrefixTree
= NULL
;
411 PrefixTableEntry
->CaseMatch
= PrefixTableEntry
;
413 /* Insert us into the tree */
414 RtlInsertAsLeftChild(&Entry
->Links
, &PrefixTableEntry
->Links
);
420 /* Check out if we have a right child */
421 if (RtlRightChild(&Entry
->Links
))
423 /* We do, enter it and restart the loop */
424 SplayLinks
= RtlLeftChild(&Entry
->Links
);
425 Entry
= CONTAINING_RECORD(SplayLinks
,
426 UNICODE_PREFIX_TABLE_ENTRY
,
431 /* We don't, set this entry as a child */
432 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
433 PrefixTableEntry
->NextPrefixTree
= NULL
;
434 PrefixTableEntry
->CaseMatch
= PrefixTableEntry
;
436 /* Insert us into the tree */
437 RtlInsertAsRightChild(&Entry
->Links
, &PrefixTableEntry
->Links
);
443 /* Get the next tree entry */
444 NextEntry
= CurrentEntry
->NextPrefixTree
;
446 /* Set what was the current entry to a child entry */
447 CurrentEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
448 CurrentEntry
->NextPrefixTree
= NULL
;
451 SplayLinks
= RtlSplay(&Entry
->Links
);
453 /* The link points to the root, get it */
454 Entry
= CONTAINING_RECORD(SplayLinks
, UNICODE_PREFIX_TABLE_ENTRY
, Links
);
456 /* Mark the root as a root entry */
457 Entry
->NodeTypeCode
= PFX_NTC_ROOT
;
459 /* Add it to the tree list */
460 PreviousEntry
->NextPrefixTree
= Entry
;
461 Entry
->NextPrefixTree
= NextEntry
;
464 DPRINT("RtlInsertUnicodePrefix TRUE\n");
471 PUNICODE_PREFIX_TABLE_ENTRY
473 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
476 PRTL_SPLAY_LINKS SplayLinks
;
477 PUNICODE_PREFIX_TABLE_ENTRY Entry
, CaseMatchEntry
;
478 DPRINT("RtlNextUnicodePrefix\n");
480 /* We might need this entry 2/3rd of the time, so cache it now */
481 CaseMatchEntry
= PrefixTable
->LastNextEntry
->CaseMatch
;
483 /* Check if this is a restart or if we don't have a last entry */
484 if ((Restart
) || !(PrefixTable
->LastNextEntry
))
486 /* Get the next entry and validate it */
487 Entry
= PrefixTable
->NextPrefixTree
;
488 if (Entry
->NodeTypeCode
== PFX_NTC_TABLE
) return NULL
;
490 /* Now get the Splay Tree Links */
491 SplayLinks
= &Entry
->Links
;
493 /* Loop until we get the first node in the tree */
494 while (RtlLeftChild(SplayLinks
)) SplayLinks
= RtlLeftChild(SplayLinks
);
496 /* Get the entry from it */
497 Entry
= CONTAINING_RECORD(SplayLinks
,
498 UNICODE_PREFIX_TABLE_ENTRY
,
501 else if (CaseMatchEntry
->NodeTypeCode
== PFX_NTC_CASE_MATCH
)
503 /* If the last entry was a Case Match, then return it */
504 Entry
= CaseMatchEntry
;
508 /* Find the successor */
509 SplayLinks
= RtlRealSuccessor(&CaseMatchEntry
->Links
);
512 /* Didn't find one, we'll have to search the tree */
513 SplayLinks
= &PrefixTable
->LastNextEntry
->Links
;
515 /* Get the topmost node (root) */
516 while (!RtlIsRoot(SplayLinks
)) SplayLinks
= RtlParent(SplayLinks
);
517 Entry
= CONTAINING_RECORD(SplayLinks
,
518 UNICODE_PREFIX_TABLE_ENTRY
,
521 /* Get its tree and make sure somethign is in it */
522 Entry
= Entry
->NextPrefixTree
;
523 if (Entry
->NameLength
<= 0) return NULL
;
525 /* Select these new links and find the first node */
526 while (RtlLeftChild(SplayLinks
)) SplayLinks
= RtlLeftChild(SplayLinks
);
529 /* Get the entry from it */
530 Entry
= CONTAINING_RECORD(SplayLinks
,
531 UNICODE_PREFIX_TABLE_ENTRY
,
535 /* Save this entry as the last one returned, and return it */
536 PrefixTable
->LastNextEntry
= Entry
;
537 DPRINT("RtlNextUnicodePrefix: %p\n", Entry
);
546 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
547 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
)
549 PUNICODE_PREFIX_TABLE_ENTRY Entry
, RefEntry
, NewEntry
;
550 PRTL_SPLAY_LINKS SplayLinks
;
551 DPRINT("RtlRemoveUnicodePrefix\n");
553 /* Erase the last entry */
554 PrefixTable
->LastNextEntry
= NULL
;
556 /* Check if this was a Case Match Entry */
557 if (PrefixTableEntry
->NodeTypeCode
== PFX_NTC_CASE_MATCH
)
559 /* Get the case match entry */
560 Entry
= PrefixTableEntry
->CaseMatch
;
562 /* Now loop until we find one referencing what the caller sent */
563 while (Entry
->CaseMatch
!= PrefixTableEntry
) Entry
= Entry
->CaseMatch
;
565 /* We found the entry that was sent, link them to delete this entry */
566 Entry
->CaseMatch
= PrefixTableEntry
->CaseMatch
;
568 else if ((PrefixTableEntry
->NodeTypeCode
== PFX_NTC_ROOT
) ||
569 (PrefixTableEntry
->NodeTypeCode
== PFX_NTC_CHILD
))
571 /* Check if this entry is a case match */
572 if (PrefixTableEntry
->CaseMatch
!= PrefixTableEntry
)
574 /* Get the case match entry */
575 Entry
= PrefixTableEntry
->CaseMatch
;
577 /* Now loop until we find one referencing what the caller sent */
578 while (Entry
->CaseMatch
!= PrefixTableEntry
) Entry
= Entry
->CaseMatch
;
580 /* We found the entry that was sent, link them to delete this entry */
581 Entry
->CaseMatch
= PrefixTableEntry
->CaseMatch
;
584 Entry
->NodeTypeCode
= PrefixTableEntry
->NodeTypeCode
;
585 Entry
->NextPrefixTree
= PrefixTableEntry
->NextPrefixTree
;
586 Entry
->Links
= PrefixTableEntry
->Links
;
588 /* Now check if we are a root entry */
589 if (RtlIsRoot(&PrefixTableEntry
->Links
))
591 /* We are, so make this entry root as well */
592 Entry
->Links
.Parent
= &Entry
->Links
;
594 /* Find the entry referencing us */
595 RefEntry
= Entry
->NextPrefixTree
;
596 while (RefEntry
->NextPrefixTree
!= Entry
)
598 /* Not this one, move to the next entry */
599 RefEntry
= RefEntry
->NextPrefixTree
;
602 /* Link them to us now */
603 RefEntry
->NextPrefixTree
= Entry
;
605 else if (RtlIsLeftChild(&PrefixTableEntry
->Links
))
607 /* We were the left child, so make us as well */
608 RtlParent(&PrefixTableEntry
->Links
)->LeftChild
= &Entry
->Links
;
612 /* We were the right child, so make us as well */
613 RtlParent(&PrefixTableEntry
->Links
)->RightChild
= &Entry
->Links
;
616 /* Check if we have a left child */
617 if (RtlLeftChild(&Entry
->Links
))
619 /* Update its parent link */
620 RtlLeftChild(&Entry
->Links
)->Parent
= &Entry
->Links
;
622 /* Check if we have a right child */
623 if (RtlRightChild(&Entry
->Links
))
625 /* Update its parent link */
626 RtlRightChild(&Entry
->Links
)->Parent
= &Entry
->Links
;
631 /* It's not a case match, so we'll delete the actual entry */
632 SplayLinks
= &PrefixTableEntry
->Links
;
634 /* Find the root entry */
635 while (!RtlIsRoot(SplayLinks
)) SplayLinks
= RtlParent(SplayLinks
);
636 Entry
= CONTAINING_RECORD(SplayLinks
,
637 UNICODE_PREFIX_TABLE_ENTRY
,
640 /* Delete the entry and check if the whole tree is gone */
641 SplayLinks
= RtlDelete(&PrefixTableEntry
->Links
);
644 /* The tree is also gone now, find the entry referencing us */
645 RefEntry
= Entry
->NextPrefixTree
;
646 while (RefEntry
->NextPrefixTree
!= Entry
)
648 /* Not this one, move to the next entry */
649 RefEntry
= RefEntry
->NextPrefixTree
;
652 /* Link them so this entry stops being referenced */
653 RefEntry
->NextPrefixTree
= Entry
->NextPrefixTree
;
655 else if (&Entry
->Links
!= SplayLinks
)
657 /* The tree is still here, but we got moved to a new one */
658 NewEntry
= CONTAINING_RECORD(SplayLinks
,
659 UNICODE_PREFIX_TABLE_ENTRY
,
662 /* Find the entry referencing us */
663 RefEntry
= Entry
->NextPrefixTree
;
664 while (RefEntry
->NextPrefixTree
!= Entry
)
666 /* Not this one, move to the next entry */
667 RefEntry
= RefEntry
->NextPrefixTree
;
670 /* Since we got moved, make us the new root entry */
671 NewEntry
->NodeTypeCode
= PFX_NTC_ROOT
;
673 /* Link us with the entry referencing the old root */
674 RefEntry
->NextPrefixTree
= NewEntry
;
676 /* And link us with the old tree */
677 NewEntry
->NextPrefixTree
= Entry
->NextPrefixTree
;
679 /* Set the old tree as a child */
680 Entry
->NodeTypeCode
= PFX_NTC_CHILD
;
681 Entry
->NextPrefixTree
= NULL
;