Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683/* * COPYRIGHT: See COPYING in the top level directory * PROJECT: ReactOS system libraries * PURPOSE: Unicode Prefix implementation * FILE: lib/rtl/unicodeprefix.c * PROGRAMMER: Alex Ionescu (alex@relsoft.net) */
/* INCLUDES *****************************************************************/
#include <rtl.h>
#define NDEBUG#include <debug.h>
/* * FIXME: Try to find the official names and add to NDK * Definitions come from fastfat driver. */typedef USHORT NODE_TYPE_CODE;#define PFX_NTC_TABLE ((NODE_TYPE_CODE)0x0800)#define PFX_NTC_ROOT ((NODE_TYPE_CODE)0x0801)#define PFX_NTC_CHILD ((NODE_TYPE_CODE)0x0802)#define PFX_NTC_CASE_MATCH ((NODE_TYPE_CODE)0x0803)
/* FUNCTIONS ***************************************************************/
ULONGNTAPIComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName){ ULONG Chars = UnicodeName->Length / sizeof(WCHAR); ULONG i, NamesFound = 1;
/* Loop the string */ for (i = 0; i < (Chars - 1); i++) { /* Check if we found a backslash, meaning another name */ if (UnicodeName->Buffer[i] == '\\') NamesFound++; }
/* Return the number of names found */ return NamesFound;}
RTL_GENERIC_COMPARE_RESULTSNTAPICompareUnicodeStrings(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;
/* 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 = RtlpUpcaseUnicodeChar(FoundPrefix); FoundString = RtlpUpcaseUnicodeChar(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;}
/* * @implemented */PUNICODE_PREFIX_TABLE_ENTRYNTAPIRtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable, PUNICODE_STRING FullName, ULONG CaseInsensitiveIndex){ ULONG NameCount; PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry; PRTL_SPLAY_LINKS SplayLinks; RTL_GENERIC_COMPARE_RESULTS Result;
DPRINT("RtlFindUnicodePrefix(): Table %p, FullName %wZ, " "CaseInsensitive %lu\n", PrefixTable, FullName, CaseInsensitiveIndex);
/* 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 > (CSHORT)NameCount) { /* Not a match, move to the next entry */ PreviousEntry = CurrentEntry; CurrentEntry = CurrentEntry->NextPrefixTree; }
/* Loop every entry which has valid entries */ while (CurrentEntry->NameLength) { /* Get the splay links and loop */ SplayLinks = &CurrentEntry->Links; while (SplayLinks) { /* Get the entry */ Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
/* Do the comparison */ Result = CompareUnicodeStrings(Entry->Prefix, FullName, 0); 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) */ 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 */ 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 */ return NextEntry; }
/* No match yet, continue looping the circular list */ NextEntry = NextEntry->CaseMatch; } 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 exhausted, move to next entry */ PreviousEntry = CurrentEntry; CurrentEntry = CurrentEntry->NextPrefixTree; }
/* If we got here, nothing was found */ return NULL;}
/* * @implemented */VOIDNTAPIRtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable){ DPRINT("RtlInitializeUnicodePrefix(): Table %p\n", PrefixTable);
/* Setup the table */ PrefixTable->NameLength = 0; PrefixTable->LastNextEntry = NULL; PrefixTable->NodeTypeCode = PFX_NTC_TABLE; PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;}
/* * @implemented */BOOLEANNTAPIRtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable, PUNICODE_STRING Prefix, PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry){ PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry; ULONG NameCount; RTL_GENERIC_COMPARE_RESULTS Result; PRTL_SPLAY_LINKS SplayLinks;
DPRINT("RtlInsertUnicodePrefix(): Table %p, Prefix %wZ, " "TableEntry %p\n", PrefixTable, Prefix, PrefixTableEntry);
/* Find out how many names there are */ NameCount = ComputeUnicodeNameLength(Prefix);
/* Set up the initial entry data */ PrefixTableEntry->NameLength = (CSHORT)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 > (CSHORT)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 != (CSHORT)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 */ return TRUE; }
/* We found a tree, so start the 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 */ 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 = RtlRightChild(&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 */ return TRUE;}
/** @implemented*/PUNICODE_PREFIX_TABLE_ENTRYNTAPIRtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable, BOOLEAN Restart){ PRTL_SPLAY_LINKS SplayLinks; PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry = NULL;
DPRINT("RtlNextUnicodePrefix(): Table %p Restart %u\n", PrefixTable, Restart);
/* We might need this entry 2/3rd of the time, so cache it now */ if (PrefixTable->LastNextEntry) CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
/* Check if this is a restart or if we don't have a last entry */ if ((Restart) || !(PrefixTable->LastNextEntry)) { /* Get the next entry and validate it */ Entry = PrefixTable->NextPrefixTree; if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
/* Now get the Splay Tree Links */ SplayLinks = &Entry->Links;
/* Loop until we get the first node in the tree */ while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
/* Get the entry from it */ Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links); } else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH) { /* If the last entry was a Case Match, then return it */ Entry = CaseMatchEntry; } else { /* Find the successor */ SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links); if (!SplayLinks) { /* Didn't find one, we'll have to search the tree */ SplayLinks = &PrefixTable->LastNextEntry->Links;
/* Get the topmost node (root) */ while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks); Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
/* Get its tree and make sure something is in it */ Entry = Entry->NextPrefixTree; if (Entry->NameLength <= 0) return NULL;
/* Select these new links and find the first node */ while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks); }
/* Get the entry from it */ Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links); }
/* Save this entry as the last one returned, and return it */ PrefixTable->LastNextEntry = Entry; return Entry;}
/* * @implemented */VOIDNTAPIRtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable, PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry){ PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry; PRTL_SPLAY_LINKS SplayLinks;
DPRINT("RtlRemoveUnicodePrefix(): Table %p, TableEntry %p\n", PrefixTable, PrefixTableEntry);
/* 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 */