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
= NULL
;
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 if (PrefixTable
->LastNextEntry
)
475 CaseMatchEntry
= PrefixTable
->LastNextEntry
->CaseMatch
;
477 /* Check if this is a restart or if we don't have a last entry */
478 if ((Restart
) || !(PrefixTable
->LastNextEntry
))
480 /* Get the next entry and validate it */
481 Entry
= PrefixTable
->NextPrefixTree
;
482 if (Entry
->NodeTypeCode
== PFX_NTC_TABLE
) return NULL
;
484 /* Now get the Splay Tree Links */
485 SplayLinks
= &Entry
->Links
;
487 /* Loop until we get the first node in the tree */
488 while (RtlLeftChild(SplayLinks
)) SplayLinks
= RtlLeftChild(SplayLinks
);
490 /* Get the entry from it */
491 Entry
= CONTAINING_RECORD(SplayLinks
,
492 UNICODE_PREFIX_TABLE_ENTRY
,
495 else if (CaseMatchEntry
->NodeTypeCode
== PFX_NTC_CASE_MATCH
)
497 /* If the last entry was a Case Match, then return it */
498 Entry
= CaseMatchEntry
;
502 /* Find the successor */
503 SplayLinks
= RtlRealSuccessor(&CaseMatchEntry
->Links
);
506 /* Didn't find one, we'll have to search the tree */
507 SplayLinks
= &PrefixTable
->LastNextEntry
->Links
;
509 /* Get the topmost node (root) */
510 while (!RtlIsRoot(SplayLinks
)) SplayLinks
= RtlParent(SplayLinks
);
511 Entry
= CONTAINING_RECORD(SplayLinks
,
512 UNICODE_PREFIX_TABLE_ENTRY
,
515 /* Get its tree and make sure somethign is in it */
516 Entry
= Entry
->NextPrefixTree
;
517 if (Entry
->NameLength
<= 0) return NULL
;
519 /* Select these new links and find the first node */
520 while (RtlLeftChild(SplayLinks
)) SplayLinks
= RtlLeftChild(SplayLinks
);
523 /* Get the entry from it */
524 Entry
= CONTAINING_RECORD(SplayLinks
,
525 UNICODE_PREFIX_TABLE_ENTRY
,
529 /* Save this entry as the last one returned, and return it */
530 PrefixTable
->LastNextEntry
= Entry
;
539 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable
,
540 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
)
542 PUNICODE_PREFIX_TABLE_ENTRY Entry
, RefEntry
, NewEntry
;
543 PRTL_SPLAY_LINKS SplayLinks
;
545 DPRINT("RtlRemoveUnicodePrefix(): Table %p, TableEntry %p\n",
546 PrefixTable
, PrefixTableEntry
);
548 /* Erase the last entry */
549 PrefixTable
->LastNextEntry
= NULL
;
551 /* Check if this was a Case Match Entry */
552 if (PrefixTableEntry
->NodeTypeCode
== PFX_NTC_CASE_MATCH
)
554 /* Get the case match entry */
555 Entry
= PrefixTableEntry
->CaseMatch
;
557 /* Now loop until we find one referencing what the caller sent */
558 while (Entry
->CaseMatch
!= PrefixTableEntry
) Entry
= Entry
->CaseMatch
;
560 /* We found the entry that was sent, link them to delete this entry */
561 Entry
->CaseMatch
= PrefixTableEntry
->CaseMatch
;
563 else if ((PrefixTableEntry
->NodeTypeCode
== PFX_NTC_ROOT
) ||
564 (PrefixTableEntry
->NodeTypeCode
== PFX_NTC_CHILD
))
566 /* Check if this entry is a case match */
567 if (PrefixTableEntry
->CaseMatch
!= PrefixTableEntry
)
569 /* Get the case match entry */
570 Entry
= PrefixTableEntry
->CaseMatch
;
572 /* Now loop until we find one referencing what the caller sent */
573 while (Entry
->CaseMatch
!= PrefixTableEntry
) Entry
= Entry
->CaseMatch
;
575 /* We found the entry that was sent, link them to delete this entry */
576 Entry
->CaseMatch
= PrefixTableEntry
->CaseMatch
;
579 Entry
->NodeTypeCode
= PrefixTableEntry
->NodeTypeCode
;
580 Entry
->NextPrefixTree
= PrefixTableEntry
->NextPrefixTree
;
581 Entry
->Links
= PrefixTableEntry
->Links
;
583 /* Now check if we are a root entry */
584 if (RtlIsRoot(&PrefixTableEntry
->Links
))
586 /* We are, so make this entry root as well */
587 Entry
->Links
.Parent
= &Entry
->Links
;
589 /* Find the entry referencing us */
590 RefEntry
= Entry
->NextPrefixTree
;
591 while (RefEntry
->NextPrefixTree
!= Entry
)
593 /* Not this one, move to the next entry */
594 RefEntry
= RefEntry
->NextPrefixTree
;
597 /* Link them to us now */
598 RefEntry
->NextPrefixTree
= Entry
;
600 else if (RtlIsLeftChild(&PrefixTableEntry
->Links
))
602 /* We were the left child, so make us as well */
603 RtlParent(&PrefixTableEntry
->Links
)->LeftChild
= &Entry
->Links
;
607 /* We were the right child, so make us as well */
608 RtlParent(&PrefixTableEntry
->Links
)->RightChild
= &Entry
->Links
;
611 /* Check if we have a left child */
612 if (RtlLeftChild(&Entry
->Links
))
614 /* Update its parent link */
615 RtlLeftChild(&Entry
->Links
)->Parent
= &Entry
->Links
;
617 /* Check if we have a right child */
618 if (RtlRightChild(&Entry
->Links
))
620 /* Update its parent link */
621 RtlRightChild(&Entry
->Links
)->Parent
= &Entry
->Links
;
626 /* It's not a case match, so we'll delete the actual entry */
627 SplayLinks
= &PrefixTableEntry
->Links
;
629 /* Find the root entry */
630 while (!RtlIsRoot(SplayLinks
)) SplayLinks
= RtlParent(SplayLinks
);
631 Entry
= CONTAINING_RECORD(SplayLinks
,
632 UNICODE_PREFIX_TABLE_ENTRY
,
635 /* Delete the entry and check if the whole tree is gone */
636 SplayLinks
= RtlDelete(&PrefixTableEntry
->Links
);
639 /* The tree is also gone now, find the entry referencing us */
640 RefEntry
= Entry
->NextPrefixTree
;
641 while (RefEntry
->NextPrefixTree
!= Entry
)
643 /* Not this one, move to the next entry */
644 RefEntry
= RefEntry
->NextPrefixTree
;
647 /* Link them so this entry stops being referenced */
648 RefEntry
->NextPrefixTree
= Entry
->NextPrefixTree
;
650 else if (&Entry
->Links
!= SplayLinks
)
652 /* The tree is still here, but we got moved to a new one */
653 NewEntry
= CONTAINING_RECORD(SplayLinks
,
654 UNICODE_PREFIX_TABLE_ENTRY
,
657 /* Find the entry referencing us */
658 RefEntry
= Entry
->NextPrefixTree
;
659 while (RefEntry
->NextPrefixTree
!= Entry
)
661 /* Not this one, move to the next entry */
662 RefEntry
= RefEntry
->NextPrefixTree
;
665 /* Since we got moved, make us the new root entry */
666 NewEntry
->NodeTypeCode
= PFX_NTC_ROOT
;
668 /* Link us with the entry referencing the old root */
669 RefEntry
->NextPrefixTree
= NewEntry
;
671 /* And link us with the old tree */
672 NewEntry
->NextPrefixTree
= Entry
->NextPrefixTree
;
674 /* Set the old tree as a child */
675 Entry
->NodeTypeCode
= PFX_NTC_CHILD
;
676 Entry
->NextPrefixTree
= NULL
;