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 ***************************************************************/
30 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName
)
32 ULONG Chars
= UnicodeName
->Length
/ sizeof(WCHAR
);
33 ULONG i
, NamesFound
= 1;
36 for (i
= 0; i
< (Chars
- 1); i
++)
38 /* Check if we found a backslash, meaning another name */
39 if (UnicodeName
->Buffer
[i
] == '\\') NamesFound
++;
42 /* Return the number of names found */
46 RTL_GENERIC_COMPARE_RESULTS
48 CompareUnicodeStrings(IN PUNICODE_STRING Prefix
,
49 IN PUNICODE_STRING String
,
50 IN ULONG CaseCheckChar
)
52 ULONG StringLength
= String
->Length
/ sizeof(WCHAR
);
53 ULONG PrefixLength
= Prefix
->Length
/ sizeof(WCHAR
);
54 ULONG ScanLength
= min(StringLength
, PrefixLength
);
56 WCHAR FoundPrefix
, FoundString
;
59 /* Handle case noticed in npfs when Prefix = '\' and name starts with '\' */
60 if ((PrefixLength
== 1) &&
61 (Prefix
->Buffer
[0] == '\\') &&
63 (String
->Buffer
[0] == '\\'))
65 /* The string is actually a prefix */
69 /* Validate the Case Check Character Position */
70 if (CaseCheckChar
> ScanLength
) CaseCheckChar
= ScanLength
;
72 /* Do the case sensitive comparison first */
73 for (i
= 0; i
< CaseCheckChar
; i
++)
75 /* Compare the two characters */
76 if (Prefix
->Buffer
[i
] != String
->Buffer
[i
]) break;
79 /* Save the characters we found */
80 FoundPrefix
= Prefix
->Buffer
[i
];
81 FoundString
= String
->Buffer
[i
];
83 /* Check if we exausted the search above */
84 if (i
== CaseCheckChar
)
86 /* Do a case-insensitive search */
87 p
= &Prefix
->Buffer
[i
];
88 p1
= &String
->Buffer
[i
];
91 /* Move to the next character */
96 if (FoundPrefix
!= FoundString
)
98 /* Upcase the characters */
99 FoundPrefix
= RtlUpcaseUnicodeChar(FoundPrefix
);
100 FoundString
= RtlUpcaseUnicodeChar(FoundString
);
102 /* Compare them again */
103 if (FoundPrefix
!= FoundString
) break;
106 /* Move to the next char */
108 } while (i
< ScanLength
);
111 /* Check if we weren't able to find a match in the loops */
114 /* If the prefix character found was a backslash, this is a less */
115 if (FoundPrefix
== '\\') return GenericLessThan
;
117 /* If the string character found was a backslack, then this is a more */
118 if (FoundString
== '\\') return GenericGreaterThan
;
120 /* None of those two special cases, do a normal check */
121 if (FoundPrefix
< FoundString
) return GenericLessThan
;
123 /* The only choice left is that Prefix > String */
124 return GenericGreaterThan
;
127 /* If we got here, a match was found. Check if the prefix is smaller */
128 if (PrefixLength
< StringLength
)
130 /* Check if the string is actually a prefix */
131 if (String
->Buffer
[PrefixLength
] == '\\') return -1;
133 /* It's not a prefix, and it's shorter, so it's a less */
134 return GenericLessThan
;
137 /* Check if the prefix is longer */
138 if (PrefixLength
> StringLength
) return GenericGreaterThan
;
140 /* If we got here, then they are 100% equal */
147 PUNICODE_PREFIX_TABLE_ENTRY
149 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
150 PUNICODE_STRING FullName
,
151 ULONG CaseInsensitiveIndex
)
154 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry
, PreviousEntry
, Entry
, NextEntry
;
155 PRTL_SPLAY_LINKS SplayLinks
;
156 RTL_GENERIC_COMPARE_RESULTS Result
;
158 DPRINT("RtlFindUnicodePrefix(): Table %p, FullName %wZ, "
159 "CaseInsensitive %b\n", PrefixTable
, FullName
, CaseInsensitiveIndex
);
161 /* Find out how many names there are */
162 NameCount
= ComputeUnicodeNameLength(FullName
);
164 /* Find the right spot where to start looking for this entry */
165 PreviousEntry
= (PUNICODE_PREFIX_TABLE_ENTRY
)PrefixTable
;
166 CurrentEntry
= PreviousEntry
->NextPrefixTree
;
167 while (CurrentEntry
->NameLength
> (CSHORT
)NameCount
)
169 /* Not a match, move to the next entry */
170 PreviousEntry
= CurrentEntry
;
171 CurrentEntry
= CurrentEntry
->NextPrefixTree
;
174 /* Loop every entry which has valid entries */
175 while (CurrentEntry
->NameLength
)
177 /* Get the splay links and loop */
178 SplayLinks
= &CurrentEntry
->Links
;
182 Entry
= CONTAINING_RECORD(SplayLinks
,
183 UNICODE_PREFIX_TABLE_ENTRY
,
186 /* Do the comparison */
187 Result
= CompareUnicodeStrings(Entry
->Prefix
, FullName
, 0);
188 if (Result
== GenericGreaterThan
)
190 /* Prefix is greater, so restart on the left child */
191 SplayLinks
= RtlLeftChild(SplayLinks
);
194 else if (Result
== GenericLessThan
)
196 /* Prefix is smaller, so restart on the right child */
197 SplayLinks
= RtlRightChild(SplayLinks
);
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)
206 if (!CaseInsensitiveIndex
)
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.
213 if (Entry
->NodeTypeCode
== PFX_NTC_CHILD
)
215 /* Get the next entry */
216 NextEntry
= CurrentEntry
->NextPrefixTree
;
218 /* Make the current entry become a child */
219 CurrentEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
220 CurrentEntry
->NextPrefixTree
= NULL
;
223 SplayLinks
= RtlSplay(&Entry
->Links
);
225 /* Get the new root entry */
226 Entry
= CONTAINING_RECORD(SplayLinks
,
227 UNICODE_PREFIX_TABLE_ENTRY
,
230 /* Set it as a root entry */
231 Entry
->NodeTypeCode
= PFX_NTC_ROOT
;
233 /* Add it to the root entries list */
234 PreviousEntry
->NextPrefixTree
= Entry
;
235 Entry
->NextPrefixTree
= NextEntry
;
238 /* Return the entry */
242 /* We'll do a case-sensitive search if we've reached this point */
246 /* Do the case-sensitive search */
247 Result
= CompareUnicodeStrings(NextEntry
->Prefix
,
249 CaseInsensitiveIndex
);
250 if ((Result
!= GenericLessThan
) &&
251 (Result
!= GenericGreaterThan
))
253 /* This is a positive match, return it */
257 /* No match yet, continue looping the circular list */
258 NextEntry
= NextEntry
->CaseMatch
;
259 } while (NextEntry
!= Entry
);
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).
269 /* Splay links exhausted, move to next entry */
270 PreviousEntry
= CurrentEntry
;
271 CurrentEntry
= CurrentEntry
->NextPrefixTree
;
274 /* If we got here, nothing was found */
283 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
)
285 DPRINT("RtlInitializeUnicodePrefix(): Table %p\n",
288 /* Setup the table */
289 PrefixTable
->NameLength
= 0;
290 PrefixTable
->LastNextEntry
= NULL
;
291 PrefixTable
->NodeTypeCode
= PFX_NTC_TABLE
;
292 PrefixTable
->NextPrefixTree
= (PUNICODE_PREFIX_TABLE_ENTRY
)PrefixTable
;
300 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
301 PUNICODE_STRING Prefix
,
302 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
)
304 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry
, PreviousEntry
, Entry
, NextEntry
;
306 RTL_GENERIC_COMPARE_RESULTS Result
;
307 PRTL_SPLAY_LINKS SplayLinks
;
309 DPRINT("RtlInsertUnicodePrefix(): Table %p, Prefix %wZ, "
310 "TableEntry %p\n", PrefixTable
, Prefix
, PrefixTableEntry
);
312 /* Find out how many names there are */
313 NameCount
= ComputeUnicodeNameLength(Prefix
);
315 /* Set up the initial entry data */
316 PrefixTableEntry
->NameLength
= (CSHORT
)NameCount
;
317 PrefixTableEntry
->Prefix
= Prefix
;
318 RtlInitializeSplayLinks(&PrefixTableEntry
->Links
);
320 /* Find the right spot where to insert this entry */
321 PreviousEntry
= (PUNICODE_PREFIX_TABLE_ENTRY
)PrefixTable
;
322 CurrentEntry
= PreviousEntry
->NextPrefixTree
;
323 while (CurrentEntry
->NameLength
> (CSHORT
)NameCount
)
325 /* Not a match, move to the next entry */
326 PreviousEntry
= CurrentEntry
;
327 CurrentEntry
= CurrentEntry
->NextPrefixTree
;
330 /* Check if we did find a tree by now */
331 if (CurrentEntry
->NameLength
!= (CSHORT
)NameCount
)
333 /* We didn't, so insert a new entry in the list */
334 PreviousEntry
->NextPrefixTree
= PrefixTableEntry
;
335 PrefixTableEntry
->NextPrefixTree
= CurrentEntry
;
337 /* This is now a root entry with case match */
338 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_ROOT
;
339 PrefixTableEntry
->CaseMatch
= PrefixTableEntry
;
345 /* We found a tree, so start the search loop */
346 Entry
= CurrentEntry
;
349 /* Do a case-insensitive comparison to find out the match level */
350 Result
= CompareUnicodeStrings(Entry
->Prefix
, Prefix
, 0);
351 if (Result
== GenericEqual
)
353 /* We have a match, start doing a case-sensitive search */
356 /* Search the circular case-match list */
359 /* Check if we found a match */
360 if (CompareUnicodeStrings(NextEntry
->Prefix
, Prefix
, -1) ==
363 /* We must fail the insert: it already exists */
367 /* Move to the next entry in the circular list */
368 NextEntry
= NextEntry
->CaseMatch
;
370 while (NextEntry
!= Entry
);
373 * No match found, so we can safely insert it. Remember that a
374 * case insensitive match was found, so this is not a ROOT NTC
375 * but a Case Match NTC instead.
377 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_CASE_MATCH
;
378 PrefixTableEntry
->NextPrefixTree
= NULL
;
380 /* Insert it into the circular list */
381 PrefixTableEntry
->CaseMatch
= Entry
->CaseMatch
;
382 Entry
->CaseMatch
= PrefixTableEntry
;
386 /* Check if the result was greater or lesser than */
387 if (Result
== GenericGreaterThan
)
389 /* Check out if we have a left child */
390 if (RtlLeftChild(&Entry
->Links
))
392 /* We do, enter it and restart the loop */
393 SplayLinks
= RtlLeftChild(&Entry
->Links
);
394 Entry
= CONTAINING_RECORD(SplayLinks
,
395 UNICODE_PREFIX_TABLE_ENTRY
,
400 /* We don't, set this entry as a child */
401 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
402 PrefixTableEntry
->NextPrefixTree
= NULL
;
403 PrefixTableEntry
->CaseMatch
= PrefixTableEntry
;
405 /* Insert us into the tree */
406 RtlInsertAsLeftChild(&Entry
->Links
, &PrefixTableEntry
->Links
);
412 /* Check out if we have a right child */
413 if (RtlRightChild(&Entry
->Links
))
415 /* We do, enter it and restart the loop */
416 SplayLinks
= RtlRightChild(&Entry
->Links
);
417 Entry
= CONTAINING_RECORD(SplayLinks
,
418 UNICODE_PREFIX_TABLE_ENTRY
,
423 /* We don't, set this entry as a child */
424 PrefixTableEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
425 PrefixTableEntry
->NextPrefixTree
= NULL
;
426 PrefixTableEntry
->CaseMatch
= PrefixTableEntry
;
428 /* Insert us into the tree */
429 RtlInsertAsRightChild(&Entry
->Links
, &PrefixTableEntry
->Links
);
435 /* Get the next tree entry */
436 NextEntry
= CurrentEntry
->NextPrefixTree
;
438 /* Set what was the current entry to a child entry */
439 CurrentEntry
->NodeTypeCode
= PFX_NTC_CHILD
;
440 CurrentEntry
->NextPrefixTree
= NULL
;
443 SplayLinks
= RtlSplay(&Entry
->Links
);
445 /* The link points to the root, get it */
446 Entry
= CONTAINING_RECORD(SplayLinks
, UNICODE_PREFIX_TABLE_ENTRY
, Links
);
448 /* Mark the root as a root entry */
449 Entry
->NodeTypeCode
= PFX_NTC_ROOT
;
451 /* Add it to the tree list */
452 PreviousEntry
->NextPrefixTree
= Entry
;
453 Entry
->NextPrefixTree
= NextEntry
;
462 PUNICODE_PREFIX_TABLE_ENTRY
464 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
467 PRTL_SPLAY_LINKS SplayLinks
;
468 PUNICODE_PREFIX_TABLE_ENTRY Entry
, CaseMatchEntry
;
470 DPRINT("RtlNextUnicodePrefix(): Table %p Restart %b\n",
471 PrefixTable
, Restart
);
473 /* We might need this entry 2/3rd of the time, so cache it now */
474 CaseMatchEntry
= PrefixTable
->LastNextEntry
->CaseMatch
;
476 /* Check if this is a restart or if we don't have a last entry */
477 if ((Restart
) || !(PrefixTable
->LastNextEntry
))
479 /* Get the next entry and validate it */
480 Entry
= PrefixTable
->NextPrefixTree
;
481 if (Entry
->NodeTypeCode
== PFX_NTC_TABLE
) return NULL
;
483 /* Now get the Splay Tree Links */
484 SplayLinks
= &Entry
->Links
;
486 /* Loop until we get the first node in the tree */
487 while (RtlLeftChild(SplayLinks
)) SplayLinks
= RtlLeftChild(SplayLinks
);
489 /* Get the entry from it */
490 Entry
= CONTAINING_RECORD(SplayLinks
,
491 UNICODE_PREFIX_TABLE_ENTRY
,
494 else if (CaseMatchEntry
->NodeTypeCode
== PFX_NTC_CASE_MATCH
)
496 /* If the last entry was a Case Match, then return it */
497 Entry
= CaseMatchEntry
;
501 /* Find the successor */
502 SplayLinks
= RtlRealSuccessor(&CaseMatchEntry
->Links
);
505 /* Didn't find one, we'll have to search the tree */
506 SplayLinks
= &PrefixTable
->LastNextEntry
->Links
;
508 /* Get the topmost node (root) */
509 while (!RtlIsRoot(SplayLinks
)) SplayLinks
= RtlParent(SplayLinks
);
510 Entry
= CONTAINING_RECORD(SplayLinks
,
511 UNICODE_PREFIX_TABLE_ENTRY
,
514 /* Get its tree and make sure somethign is in it */
515 Entry
= Entry
->NextPrefixTree
;
516 if (Entry
->NameLength
<= 0) return NULL
;
518 /* Select these new links and find the first node */
519 while (RtlLeftChild(SplayLinks
)) SplayLinks
= RtlLeftChild(SplayLinks
);
522 /* Get the entry from it */
523 Entry
= CONTAINING_RECORD(SplayLinks
,
524 UNICODE_PREFIX_TABLE_ENTRY
,
528 /* Save this entry as the last one returned, and return it */
529 PrefixTable
->LastNextEntry
= Entry
;
538 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
539 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
)
541 PUNICODE_PREFIX_TABLE_ENTRY Entry
, RefEntry
, NewEntry
;
542 PRTL_SPLAY_LINKS SplayLinks
;
544 DPRINT("RtlRemoveUnicodePrefix(): Table %p, TableEntry %p\n",
545 PrefixTable
, PrefixTableEntry
);
547 /* Erase the last entry */
548 PrefixTable
->LastNextEntry
= NULL
;
550 /* Check if this was a Case Match Entry */
551 if (PrefixTableEntry
->NodeTypeCode
== PFX_NTC_CASE_MATCH
)
553 /* Get the case match entry */
554 Entry
= PrefixTableEntry
->CaseMatch
;
556 /* Now loop until we find one referencing what the caller sent */
557 while (Entry
->CaseMatch
!= PrefixTableEntry
) Entry
= Entry
->CaseMatch
;
559 /* We found the entry that was sent, link them to delete this entry */
560 Entry
->CaseMatch
= PrefixTableEntry
->CaseMatch
;
562 else if ((PrefixTableEntry
->NodeTypeCode
== PFX_NTC_ROOT
) ||
563 (PrefixTableEntry
->NodeTypeCode
== PFX_NTC_CHILD
))
565 /* Check if this entry is a case match */
566 if (PrefixTableEntry
->CaseMatch
!= PrefixTableEntry
)
568 /* Get the case match entry */
569 Entry
= PrefixTableEntry
->CaseMatch
;
571 /* Now loop until we find one referencing what the caller sent */
572 while (Entry
->CaseMatch
!= PrefixTableEntry
) Entry
= Entry
->CaseMatch
;
574 /* We found the entry that was sent, link them to delete this entry */
575 Entry
->CaseMatch
= PrefixTableEntry
->CaseMatch
;
578 Entry
->NodeTypeCode
= PrefixTableEntry
->NodeTypeCode
;
579 Entry
->NextPrefixTree
= PrefixTableEntry
->NextPrefixTree
;
580 Entry
->Links
= PrefixTableEntry
->Links
;
582 /* Now check if we are a root entry */
583 if (RtlIsRoot(&PrefixTableEntry
->Links
))
585 /* We are, so make this entry root as well */
586 Entry
->Links
.Parent
= &Entry
->Links
;
588 /* Find the entry referencing us */
589 RefEntry
= Entry
->NextPrefixTree
;
590 while (RefEntry
->NextPrefixTree
!= Entry
)
592 /* Not this one, move to the next entry */
593 RefEntry
= RefEntry
->NextPrefixTree
;
596 /* Link them to us now */
597 RefEntry
->NextPrefixTree
= Entry
;
599 else if (RtlIsLeftChild(&PrefixTableEntry
->Links
))
601 /* We were the left child, so make us as well */
602 RtlParent(&PrefixTableEntry
->Links
)->LeftChild
= &Entry
->Links
;
606 /* We were the right child, so make us as well */
607 RtlParent(&PrefixTableEntry
->Links
)->RightChild
= &Entry
->Links
;
610 /* Check if we have a left child */
611 if (RtlLeftChild(&Entry
->Links
))
613 /* Update its parent link */
614 RtlLeftChild(&Entry
->Links
)->Parent
= &Entry
->Links
;
616 /* Check if we have a right child */
617 if (RtlRightChild(&Entry
->Links
))
619 /* Update its parent link */
620 RtlRightChild(&Entry
->Links
)->Parent
= &Entry
->Links
;
625 /* It's not a case match, so we'll delete the actual entry */
626 SplayLinks
= &PrefixTableEntry
->Links
;
628 /* Find the root entry */
629 while (!RtlIsRoot(SplayLinks
)) SplayLinks
= RtlParent(SplayLinks
);
630 Entry
= CONTAINING_RECORD(SplayLinks
,
631 UNICODE_PREFIX_TABLE_ENTRY
,
634 /* Delete the entry and check if the whole tree is gone */
635 SplayLinks
= RtlDelete(&PrefixTableEntry
->Links
);
638 /* The tree is also gone now, find the entry referencing us */
639 RefEntry
= Entry
->NextPrefixTree
;
640 while (RefEntry
->NextPrefixTree
!= Entry
)
642 /* Not this one, move to the next entry */
643 RefEntry
= RefEntry
->NextPrefixTree
;
646 /* Link them so this entry stops being referenced */
647 RefEntry
->NextPrefixTree
= Entry
->NextPrefixTree
;
649 else if (&Entry
->Links
!= SplayLinks
)
651 /* The tree is still here, but we got moved to a new one */
652 NewEntry
= CONTAINING_RECORD(SplayLinks
,
653 UNICODE_PREFIX_TABLE_ENTRY
,
656 /* Find the entry referencing us */
657 RefEntry
= Entry
->NextPrefixTree
;
658 while (RefEntry
->NextPrefixTree
!= Entry
)
660 /* Not this one, move to the next entry */
661 RefEntry
= RefEntry
->NextPrefixTree
;
664 /* Since we got moved, make us the new root entry */
665 NewEntry
->NodeTypeCode
= PFX_NTC_ROOT
;
667 /* Link us with the entry referencing the old root */
668 RefEntry
->NextPrefixTree
= NewEntry
;
670 /* And link us with the old tree */
671 NewEntry
->NextPrefixTree
= Entry
->NextPrefixTree
;
673 /* Set the old tree as a child */
674 Entry
->NodeTypeCode
= PFX_NTC_CHILD
;
675 Entry
->NextPrefixTree
= NULL
;