/* FUNCTIONS ***************************************************************/
-/*STATIC*/
+static
ULONG
NTAPI
ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
return NamesFound;
}
+static
+RTL_GENERIC_COMPARE_RESULTS
+NTAPI
+CompareUnicodeStrings(IN PUNICODE_STRING Prefix,
+ IN PUNICODE_STRING String,
+ IN ULONG CaseCheckChar)
+{
+ ULONG StringLength = String->Length / sizeof(WCHAR);
+ ULONG PrefixLength = Prefix->Length / sizeof(WCHAR);
+ ULONG ScanLength = min(StringLength, PrefixLength);
+ ULONG i;
+ WCHAR FoundPrefix, FoundString;
+ PWCHAR p, p1;
+ DPRINT("CompareUnicodeStrings: %wZ %wZ\n", String, Prefix);
+
+ /* Handle case noticed in npfs when Prefix = '\' and name starts with '\' */
+ if ((PrefixLength == 1) &&
+ (Prefix->Buffer[0] == '\\') &&
+ (StringLength > 1) &&
+ (String->Buffer[0] == '\\'))
+ {
+ /* The string is actually a prefix */
+ return -1;
+ }
+
+ /* Validate the Case Check Character Position */
+ if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
+
+ /* Do the case sensitive comparison first */
+ for (i = 0; i < CaseCheckChar; i++)
+ {
+ /* Compare the two characters */
+ if (Prefix->Buffer[i] != String->Buffer[i]) break;
+ }
+
+ /* Save the characters we found */
+ FoundPrefix = Prefix->Buffer[i];
+ FoundString = String->Buffer[i];
+
+ /* Check if we exausted the search above */
+ if (i == CaseCheckChar)
+ {
+ /* Do a case-insensitive search */
+ p = &Prefix->Buffer[i];
+ p1 = &String->Buffer[i];
+ do
+ {
+ /* Move to the next character */
+ FoundPrefix = *p++;
+ FoundString = *p1++;
+
+ /* Compare it */
+ if (FoundPrefix != FoundString)
+ {
+ /* Upcase the characters */
+ FoundPrefix = RtlUpcaseUnicodeChar(FoundPrefix);
+ FoundString = RtlUpcaseUnicodeChar(FoundString);
+
+ /* Compare them again */
+ if (FoundPrefix != FoundString) break;
+ }
+
+ /* Move to the next char */
+ i++;
+ } while (i < ScanLength);
+ }
+
+ /* Check if we weren't able to find a match in the loops */
+ if (i < ScanLength)
+ {
+ /* If the prefix character found was a backslash, this is a less */
+ if (FoundPrefix == '\\') return GenericLessThan;
+
+ /* If the string character found was a backslack, then this is a more */
+ if (FoundString == '\\') return GenericGreaterThan;
+
+ /* None of those two special cases, do a normal check */
+ if (FoundPrefix < FoundString) return GenericLessThan;
+
+ /* The only choice left is that Prefix > String */
+ return GenericGreaterThan;
+ }
+
+ /* If we got here, a match was found. Check if the prefix is smaller */
+ if (PrefixLength < StringLength)
+ {
+ /* Check if the string is actually a prefix */
+ if (String->Buffer[PrefixLength] == '\\') return -1;
+
+ /* It's not a prefix, and it's shorter, so it's a less */
+ return GenericLessThan;
+ }
+
+ /* Check if the prefix is longer */
+ if (PrefixLength > StringLength) return GenericGreaterThan;
+
+ /* If we got here, then they are 100% equal */
+ return GenericEqual;
+}
+
/*
-* @unimplemented
-*/
+ * @implemented
+ */
PUNICODE_PREFIX_TABLE_ENTRY
NTAPI
RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
PUNICODE_STRING FullName,
ULONG CaseInsensitiveIndex)
{
- UNIMPLEMENTED;
- return 0;
+ ULONG NameCount;
+ PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
+ PRTL_SPLAY_LINKS SplayLinks;
+ RTL_GENERIC_COMPARE_RESULTS Result;
+ DPRINT("RtlFindUnicodePrefix\n");
+
+ /* Find out how many names there are */
+ NameCount = ComputeUnicodeNameLength(FullName);
+
+ /* Find the right spot where to start looking for this entry */
+ PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
+ CurrentEntry = PreviousEntry->NextPrefixTree;
+ while (CurrentEntry->NameLength > NameCount)
+ {
+ /* Not a match, move to the next entry */
+ PreviousEntry = CurrentEntry;
+ CurrentEntry = CurrentEntry->NextPrefixTree;
+ }
+
+ /* Loop every entry which has valid entries */
+ while (CurrentEntry->NameLength)
+ {
+ DPRINT("CurrentEntry->NameLength %lx\n", CurrentEntry->NameLength);
+
+ /* Get the splay links and loop */
+ SplayLinks = &CurrentEntry->Links;
+ while (SplayLinks)
+ {
+ /* Get the entry */
+ DPRINT("SplayLinks %p\n", SplayLinks);
+ Entry = CONTAINING_RECORD(SplayLinks,
+ UNICODE_PREFIX_TABLE_ENTRY,
+ Links);
+
+ /* Do the comparison */
+ Result = CompareUnicodeStrings(Entry->Prefix, FullName, 0);
+ DPRINT("Result %lx\n", Result);
+ if (Result == GenericGreaterThan)
+ {
+ /* Prefix is greater, so restart on the left child */
+ SplayLinks = RtlLeftChild(SplayLinks);
+ continue;
+ }
+ else if (Result == GenericLessThan)
+ {
+ /* Prefix is smaller, so restart on the right child */
+ SplayLinks = RtlRightChild(SplayLinks);
+ continue;
+ }
+
+ /*
+ * We have a match, check if this was a case-sensitive search
+ * NOTE: An index of 0 means case-insensitive(ie, we'll be case
+ * insensitive since index 0, ie, all the time)
+ */
+ DPRINT("CaseInsensitiveIndex %lx\n", CaseInsensitiveIndex);
+ if (!CaseInsensitiveIndex)
+ {
+ /*
+ * Check if this entry was a child. We need to return the root,
+ * so if this entry was a child, we'll splay the tree and get
+ * the root, and set the current entry as a child.
+ */
+ if (Entry->NodeTypeCode == PFX_NTC_CHILD)
+ {
+ /* Get the next entry */
+ NextEntry = CurrentEntry->NextPrefixTree;
+
+ /* Make the current entry become a child */
+ CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
+ CurrentEntry->NextPrefixTree = NULL;
+
+ /* Splay the tree */
+ SplayLinks = RtlSplay(&Entry->Links);
+
+ /* Get the new root entry */
+ Entry = CONTAINING_RECORD(SplayLinks,
+ UNICODE_PREFIX_TABLE_ENTRY,
+ Links);
+
+ /* Set it as a root entry */
+ Entry->NodeTypeCode = PFX_NTC_ROOT;
+
+ /* Add it to the root entries list */
+ PreviousEntry->NextPrefixTree = Entry;
+ Entry->NextPrefixTree = NextEntry;
+ }
+
+ /* Return the entry */
+ DPRINT("RtlFindUnicodePrefix: %p\n", Entry);
+ return Entry;
+ }
+
+ /* We'll do a case-sensitive search if we've reached this point */
+ NextEntry = Entry;
+ do
+ {
+ /* Do the case-sensitive search */
+ Result = CompareUnicodeStrings(NextEntry->Prefix,
+ FullName,
+ CaseInsensitiveIndex);
+ if ((Result != GenericLessThan) &&
+ (Result != GenericGreaterThan))
+ {
+ /* This is a positive match, return it */
+ DPRINT("RtlFindUnicodePrefix: %p\n", NextEntry);
+ return NextEntry;
+ }
+
+ /* No match yet, continue looping the circular list */
+ NextEntry = NextEntry->CaseMatch;
+ DPRINT("NextEntry %p\n", NextEntry);
+ } while (NextEntry != Entry);
+
+ /*
+ * If we got here, then we found a non-case-sensitive match, but
+ * we need to find a case-sensitive match, so we'll just keep
+ * searching the next tree (NOTE: we need to break out for this).
+ */
+ break;
+ }
+
+ /* Splay links exausted, move to next entry */
+ PreviousEntry = CurrentEntry;
+ CurrentEntry = CurrentEntry->NextPrefixTree;
+ DPRINT("CurrentEntry %p\n", CurrentEntry);
+ }
+
+ /* If we got here, nothing was found */
+ DPRINT("RtlFindUnicodePrefix: %p\n", NULL);
+ return NULL;
}
/*
-* @implemented
-*/
+ * @implemented
+ */
VOID
NTAPI
RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
}
/*
-* @unimplemented
-*/
+ * @implemented
+ */
BOOLEAN
NTAPI
RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
PUNICODE_STRING Prefix,
PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
{
- /*
- * implementation notes:
- * - get name length (number of names)
- * - init splay links
- * - find a matching tree
- * - if !found, insert a new NTC_ROOT entry and return TRUE;
- * - if found, loop tree and compare strings:
- * if equal, handle casematch/nomatch
- * if greater or lesser equal, then add left/right childs accordingly
- * - splay the tree
- */
- UNIMPLEMENTED;
- return FALSE;
+ PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
+ ULONG NameCount;
+ RTL_GENERIC_COMPARE_RESULTS Result;
+ PRTL_SPLAY_LINKS SplayLinks;
+ DPRINT("RtlInsertUnicodePrefix\n");
+
+ /* Find out how many names there are */
+ NameCount = ComputeUnicodeNameLength(Prefix);
+
+ /* Set up the initial entry data */
+ PrefixTableEntry->NameLength = NameCount;
+ PrefixTableEntry->Prefix = Prefix;
+ RtlInitializeSplayLinks(&PrefixTableEntry->Links);
+
+ /* Find the right spot where to insert this entry */
+ PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
+ CurrentEntry = PreviousEntry->NextPrefixTree;
+ while (CurrentEntry->NameLength > NameCount)
+ {
+ /* Not a match, move to the next entry */
+ PreviousEntry = CurrentEntry;
+ CurrentEntry = CurrentEntry->NextPrefixTree;
+ }
+
+ /* Check if we did find a tree by now */
+ if (CurrentEntry->NameLength != NameCount)
+ {
+ /* We didn't, so insert a new entry in the list */
+ PreviousEntry->NextPrefixTree = PrefixTableEntry;
+ PrefixTableEntry->NextPrefixTree = CurrentEntry;
+
+ /* This is now a root entry with case match */
+ PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
+ PrefixTableEntry->CaseMatch = PrefixTableEntry;
+
+ /* Quick return */
+ DPRINT("RtlInsertUnicodePrefix TRUE\n");
+ return TRUE;
+ }
+
+ /* We found a tree, so star thte search loop */
+ Entry = CurrentEntry;
+ while (TRUE)
+ {
+ /* Do a case-insensitive comparison to find out the match level */
+ Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
+ if (Result == GenericEqual)
+ {
+ /* We have a match, start doing a case-sensitive search */
+ NextEntry = Entry;
+
+ /* Search the circular case-match list */
+ do
+ {
+ /* Check if we found a match */
+ if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
+ (GenericEqual))
+ {
+ /* We must fail the insert: it already exists */
+ DPRINT("RtlInsertUnicodePrefix FALSE\n");
+ return FALSE;
+ }
+
+ /* Move to the next entry in the circular list */
+ NextEntry = NextEntry->CaseMatch;
+ }
+ while (NextEntry != Entry);
+
+ /*
+ * No match found, so we can safely insert it. Remember that a
+ * case insensitive match was found, so this is not a ROOT NTC
+ * but a Case Match NTC instead.
+ */
+ PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
+ PrefixTableEntry->NextPrefixTree = NULL;
+
+ /* Insert it into the circular list */
+ PrefixTableEntry->CaseMatch = Entry->CaseMatch;
+ Entry->CaseMatch = PrefixTableEntry;
+ break;
+ }
+
+ /* Check if the result was greater or lesser than */
+ if (Result == GenericGreaterThan)
+ {
+ /* Check out if we have a left child */
+ if (RtlLeftChild(&Entry->Links))
+ {
+ /* We do, enter it and restart the loop */
+ SplayLinks = RtlLeftChild(&Entry->Links);
+ Entry = CONTAINING_RECORD(SplayLinks,
+ UNICODE_PREFIX_TABLE_ENTRY,
+ Links);
+ }
+ else
+ {
+ /* We don't, set this entry as a child */
+ PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
+ PrefixTableEntry->NextPrefixTree = NULL;
+ PrefixTableEntry->CaseMatch = PrefixTableEntry;
+
+ /* Insert us into the tree */
+ RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
+ break;
+ }
+ }
+ else
+ {
+ /* Check out if we have a right child */
+ if (RtlRightChild(&Entry->Links))
+ {
+ /* We do, enter it and restart the loop */
+ SplayLinks = RtlLeftChild(&Entry->Links);
+ Entry = CONTAINING_RECORD(SplayLinks,
+ UNICODE_PREFIX_TABLE_ENTRY,
+ Links);
+ }
+ else
+ {
+ /* We don't, set this entry as a child */
+ PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
+ PrefixTableEntry->NextPrefixTree = NULL;
+ PrefixTableEntry->CaseMatch = PrefixTableEntry;
+
+ /* Insert us into the tree */
+ RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
+ break;
+ }
+ }
+ }
+
+ /* Get the next tree entry */
+ NextEntry = CurrentEntry->NextPrefixTree;
+
+ /* Set what was the current entry to a child entry */
+ CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
+ CurrentEntry->NextPrefixTree = NULL;
+
+ /* Splay the tree */
+ SplayLinks = RtlSplay(&Entry->Links);
+
+ /* The link points to the root, get it */
+ Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
+
+ /* Mark the root as a root entry */
+ Entry->NodeTypeCode = PFX_NTC_ROOT;
+
+ /* Add it to the tree list */
+ PreviousEntry->NextPrefixTree = Entry;
+ Entry->NextPrefixTree = NextEntry;
+
+ /* Return success */
+ DPRINT("RtlInsertUnicodePrefix TRUE\n");
+ return TRUE;
}
/*
BOOLEAN Restart)
{
PRTL_SPLAY_LINKS SplayLinks;
- PUNICODE_PREFIX_TABLE_ENTRY Entry;
- PUNICODE_PREFIX_TABLE_ENTRY CaseMatchEntry;
+ PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
+ DPRINT("RtlNextUnicodePrefix\n");
/* We might need this entry 2/3rd of the time, so cache it now */
CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
/* Save this entry as the last one returned, and return it */
PrefixTable->LastNextEntry = Entry;
+ DPRINT("RtlNextUnicodePrefix: %p\n", Entry);
return Entry;
}
/*
-* @unimplemented
-*/
+ * @implemented
+ */
VOID
NTAPI
RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
{
- UNIMPLEMENTED;
+ PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
+ PRTL_SPLAY_LINKS SplayLinks;
+ DPRINT("RtlRemoveUnicodePrefix\n");
+
+ /* Erase the last entry */
+ PrefixTable->LastNextEntry = NULL;
+
+ /* Check if this was a Case Match Entry */
+ if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
+ {
+ /* Get the case match entry */
+ Entry = PrefixTableEntry->CaseMatch;
+
+ /* Now loop until we find one referencing what the caller sent */
+ while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
+
+ /* We found the entry that was sent, link them to delete this entry */
+ Entry->CaseMatch = PrefixTableEntry->CaseMatch;
+ }
+ else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
+ (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
+ {
+ /* Check if this entry is a case match */
+ if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
+ {
+ /* Get the case match entry */
+ Entry = PrefixTableEntry->CaseMatch;
+
+ /* Now loop until we find one referencing what the caller sent */
+ while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
+
+ /* We found the entry that was sent, link them to delete this entry */
+ Entry->CaseMatch = PrefixTableEntry->CaseMatch;
+
+ /* Copy the data */
+ Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
+ Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
+ Entry->Links = PrefixTableEntry->Links;
+
+ /* Now check if we are a root entry */
+ if (RtlIsRoot(&PrefixTableEntry->Links))
+ {
+ /* We are, so make this entry root as well */
+ Entry->Links.Parent = &Entry->Links;
+
+ /* Find the entry referencing us */
+ RefEntry = Entry->NextPrefixTree;
+ while (RefEntry->NextPrefixTree != Entry)
+ {
+ /* Not this one, move to the next entry */
+ RefEntry = RefEntry->NextPrefixTree;
+ }
+
+ /* Link them to us now */
+ RefEntry->NextPrefixTree = Entry;
+ }
+ else if (RtlIsLeftChild(&PrefixTableEntry->Links))
+ {
+ /* We were the left child, so make us as well */
+ RtlParent(&PrefixTableEntry->Links)->LeftChild = &Entry->Links;
+ }
+ else
+ {
+ /* We were the right child, so make us as well */
+ RtlParent(&PrefixTableEntry->Links)->RightChild = &Entry->Links;
+ }
+
+ /* Check if we have a left child */
+ if (RtlLeftChild(&Entry->Links))
+ {
+ /* Update its parent link */
+ RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
+ }
+ /* Check if we have a right child */
+ if (RtlRightChild(&Entry->Links))
+ {
+ /* Update its parent link */
+ RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
+ }
+ }
+ else
+ {
+ /* It's not a case match, so we'll delete the actual entry */
+ SplayLinks = &PrefixTableEntry->Links;
+
+ /* Find the root entry */
+ while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
+ Entry = CONTAINING_RECORD(SplayLinks,
+ UNICODE_PREFIX_TABLE_ENTRY,
+ Links);
+
+ /* Delete the entry and check if the whole tree is gone */
+ SplayLinks = RtlDelete(&PrefixTableEntry->Links);
+ if (!SplayLinks)
+ {
+ /* The tree is also gone now, find the entry referencing us */
+ RefEntry = Entry->NextPrefixTree;
+ while (RefEntry->NextPrefixTree != Entry)
+ {
+ /* Not this one, move to the next entry */
+ RefEntry = RefEntry->NextPrefixTree;
+ }
+
+ /* Link them so this entry stops being referenced */
+ RefEntry->NextPrefixTree = Entry->NextPrefixTree;
+ }
+ else if (&Entry->Links != SplayLinks)
+ {
+ /* The tree is still here, but we got moved to a new one */
+ NewEntry = CONTAINING_RECORD(SplayLinks,
+ UNICODE_PREFIX_TABLE_ENTRY,
+ Links);
+
+ /* Find the entry referencing us */
+ RefEntry = Entry->NextPrefixTree;
+ while (RefEntry->NextPrefixTree != Entry)
+ {
+ /* Not this one, move to the next entry */
+ RefEntry = RefEntry->NextPrefixTree;
+ }
+
+ /* Since we got moved, make us the new root entry */
+ NewEntry->NodeTypeCode = PFX_NTC_ROOT;
+
+ /* Link us with the entry referencing the old root */
+ RefEntry->NextPrefixTree = NewEntry;
+
+ /* And link us with the old tree */
+ NewEntry->NextPrefixTree = Entry->NextPrefixTree;
+
+ /* Set the old tree as a child */
+ Entry->NodeTypeCode = PFX_NTC_CHILD;
+ Entry->NextPrefixTree = NULL;
+ }
+ }
+ }
}
/* EOF */
projects / reactos.git / blobdiff