ReactOS 0.4.16-dev-290-g89a3b8f
unicodeprefix.c File Reference
#include <rtl.h>
#include <debug.h>
Include dependency graph for unicodeprefix.c:

Go to the source code of this file.

Macros

#define NDEBUG
 
#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)
 

Typedefs

typedef USHORT NODE_TYPE_CODE
 

Functions

ULONG NTAPI ComputeUnicodeNameLength (IN PUNICODE_STRING UnicodeName)
 
RTL_GENERIC_COMPARE_RESULTS NTAPI CompareUnicodeStrings (IN PUNICODE_STRING Prefix, IN PUNICODE_STRING String, IN ULONG CaseCheckChar)
 
PUNICODE_PREFIX_TABLE_ENTRY NTAPI RtlFindUnicodePrefix (PUNICODE_PREFIX_TABLE PrefixTable, PUNICODE_STRING FullName, ULONG CaseInsensitiveIndex)
 
VOID NTAPI RtlInitializeUnicodePrefix (PUNICODE_PREFIX_TABLE PrefixTable)
 
BOOLEAN NTAPI RtlInsertUnicodePrefix (PUNICODE_PREFIX_TABLE PrefixTable, PUNICODE_STRING Prefix, PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
 
PUNICODE_PREFIX_TABLE_ENTRY NTAPI RtlNextUnicodePrefix (PUNICODE_PREFIX_TABLE PrefixTable, BOOLEAN Restart)
 
VOID NTAPI RtlRemoveUnicodePrefix (PUNICODE_PREFIX_TABLE PrefixTable, PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
 

Macro Definition Documentation

◆ NDEBUG

#define NDEBUG

Definition at line 13 of file unicodeprefix.c.

◆ PFX_NTC_CASE_MATCH

#define PFX_NTC_CASE_MATCH   ((NODE_TYPE_CODE)0x0803)

Definition at line 24 of file unicodeprefix.c.

◆ PFX_NTC_CHILD

#define PFX_NTC_CHILD   ((NODE_TYPE_CODE)0x0802)

Definition at line 23 of file unicodeprefix.c.

◆ PFX_NTC_ROOT

#define PFX_NTC_ROOT   ((NODE_TYPE_CODE)0x0801)

Definition at line 22 of file unicodeprefix.c.

◆ PFX_NTC_TABLE

#define PFX_NTC_TABLE   ((NODE_TYPE_CODE)0x0800)

Definition at line 21 of file unicodeprefix.c.

Typedef Documentation

◆ NODE_TYPE_CODE

Definition at line 20 of file unicodeprefix.c.

Function Documentation

◆ CompareUnicodeStrings()

RTL_GENERIC_COMPARE_RESULTS NTAPI CompareUnicodeStrings ( IN PUNICODE_STRING  Prefix,
IN PUNICODE_STRING  String,
IN ULONG  CaseCheckChar 
)

Definition at line 48 of file unicodeprefix.c.

51{
52 ULONG StringLength = String->Length / sizeof(WCHAR);
53 ULONG PrefixLength = Prefix->Length / sizeof(WCHAR);
54 ULONG ScanLength = min(StringLength, PrefixLength);
55 ULONG i;
56 WCHAR FoundPrefix, FoundString;
57 PWCHAR p, p1;
58
59 /* Handle case noticed in npfs when Prefix = '\' and name starts with '\' */
60 if ((PrefixLength == 1) &&
61 (Prefix->Buffer[0] == '\\') &&
62 (StringLength > 1) &&
63 (String->Buffer[0] == '\\'))
64 {
65 /* The string is actually a prefix */
66 return -1;
67 }
68
69 /* Validate the Case Check Character Position */
70 if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
71
72 /* Do the case sensitive comparison first */
73 for (i = 0; i < CaseCheckChar; i++)
74 {
75 /* Compare the two characters */
76 if (Prefix->Buffer[i] != String->Buffer[i]) break;
77 }
78
79 /* Save the characters we found */
80 FoundPrefix = Prefix->Buffer[i];
81 FoundString = String->Buffer[i];
82
83 /* Check if we exausted the search above */
84 if (i == CaseCheckChar)
85 {
86 /* Do a case-insensitive search */
87 p = &Prefix->Buffer[i];
88 p1 = &String->Buffer[i];
89 do
90 {
91 /* Move to the next character */
92 FoundPrefix = *p++;
93 FoundString = *p1++;
94
95 /* Compare it */
96 if (FoundPrefix != FoundString)
97 {
98 /* Upcase the characters */
99 FoundPrefix = RtlpUpcaseUnicodeChar(FoundPrefix);
100 FoundString = RtlpUpcaseUnicodeChar(FoundString);
101
102 /* Compare them again */
103 if (FoundPrefix != FoundString) break;
104 }
105
106 /* Move to the next char */
107 i++;
108 } while (i < ScanLength);
109 }
110
111 /* Check if we weren't able to find a match in the loops */
112 if (i < ScanLength)
113 {
114 /* If the prefix character found was a backslash, this is a less */
115 if (FoundPrefix == '\\') return GenericLessThan;
116
117 /* If the string character found was a backslack, then this is a more */
118 if (FoundString == '\\') return GenericGreaterThan;
119
120 /* None of those two special cases, do a normal check */
121 if (FoundPrefix < FoundString) return GenericLessThan;
122
123 /* The only choice left is that Prefix > String */
124 return GenericGreaterThan;
125 }
126
127 /* If we got here, a match was found. Check if the prefix is smaller */
128 if (PrefixLength < StringLength)
129 {
130 /* Check if the string is actually a prefix */
131 if (String->Buffer[PrefixLength] == '\\') return -1;
132
133 /* It's not a prefix, and it's shorter, so it's a less */
134 return GenericLessThan;
135 }
136
137 /* Check if the prefix is longer */
138 if (PrefixLength > StringLength) return GenericGreaterThan;
139
140 /* If we got here, then they are 100% equal */
141 return GenericEqual;
142}
GLfloat GLfloat p
Definition: glext.h:8902
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define min(a, b)
Definition: monoChain.cc:55
WCHAR NTAPI RtlpUpcaseUnicodeChar(_In_ WCHAR Source)
Definition: nlsboot.c:160
unsigned short Length
Definition: sprintf.c:451
void * Buffer
Definition: sprintf.c:453
uint16_t * PWCHAR
Definition: typedefs.h:56
uint32_t ULONG
Definition: typedefs.h:59
_Must_inspect_result_ _In_ WDFDEVICE _In_ WDFSTRING String
Definition: wdfdevice.h:2433
_In_ __drv_aliasesMem PSTRING Prefix
Definition: rtlfuncs.h:1647
@ GenericLessThan
Definition: rtltypes.h:389
@ GenericEqual
Definition: rtltypes.h:391
@ GenericGreaterThan
Definition: rtltypes.h:390
__wchar_t WCHAR
Definition: xmlstorage.h:180

Referenced by RtlFindUnicodePrefix(), and RtlInsertUnicodePrefix().

◆ ComputeUnicodeNameLength()

ULONG NTAPI ComputeUnicodeNameLength ( IN PUNICODE_STRING  UnicodeName)

Definition at line 30 of file unicodeprefix.c.

31{
32 ULONG Chars = UnicodeName->Length / sizeof(WCHAR);
33 ULONG i, NamesFound = 1;
34
35 /* Loop the string */
36 for (i = 0; i < (Chars - 1); i++)
37 {
38 /* Check if we found a backslash, meaning another name */
39 if (UnicodeName->Buffer[i] == '\\') NamesFound++;
40 }
41
42 /* Return the number of names found */
43 return NamesFound;
44}
IN PDCB IN POEM_STRING IN PUNICODE_STRING UnicodeName
Definition: fatprocs.h:1306

Referenced by RtlFindUnicodePrefix(), and RtlInsertUnicodePrefix().

◆ RtlFindUnicodePrefix()

PUNICODE_PREFIX_TABLE_ENTRY NTAPI RtlFindUnicodePrefix ( PUNICODE_PREFIX_TABLE  PrefixTable,
PUNICODE_STRING  FullName,
ULONG  CaseInsensitiveIndex 
)

Definition at line 149 of file unicodeprefix.c.

152{
153 ULONG NameCount;
154 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
155 PRTL_SPLAY_LINKS SplayLinks;
157
158 DPRINT("RtlFindUnicodePrefix(): Table %p, FullName %wZ, "
159 "CaseInsensitive %lu\n", PrefixTable, FullName, CaseInsensitiveIndex);
160
161 /* Find out how many names there are */
163
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)
168 {
169 /* Not a match, move to the next entry */
170 PreviousEntry = CurrentEntry;
171 CurrentEntry = CurrentEntry->NextPrefixTree;
172 }
173
174 /* Loop every entry which has valid entries */
175 while (CurrentEntry->NameLength)
176 {
177 /* Get the splay links and loop */
178 SplayLinks = &CurrentEntry->Links;
179 while (SplayLinks)
180 {
181 /* Get the entry */
182 Entry = CONTAINING_RECORD(SplayLinks,
184 Links);
185
186 /* Do the comparison */
189 {
190 /* Prefix is greater, so restart on the left child */
191 SplayLinks = RtlLeftChild(SplayLinks);
192 continue;
193 }
194 else if (Result == GenericLessThan)
195 {
196 /* Prefix is smaller, so restart on the right child */
197 SplayLinks = RtlRightChild(SplayLinks);
198 continue;
199 }
200
201 /*
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)
205 */
207 {
208 /*
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.
212 */
213 if (Entry->NodeTypeCode == PFX_NTC_CHILD)
214 {
215 /* Get the next entry */
216 NextEntry = CurrentEntry->NextPrefixTree;
217
218 /* Make the current entry become a child */
219 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
220 CurrentEntry->NextPrefixTree = NULL;
221
222 /* Splay the tree */
223 SplayLinks = RtlSplay(&Entry->Links);
224
225 /* Get the new root entry */
226 Entry = CONTAINING_RECORD(SplayLinks,
228 Links);
229
230 /* Set it as a root entry */
231 Entry->NodeTypeCode = PFX_NTC_ROOT;
232
233 /* Add it to the root entries list */
234 PreviousEntry->NextPrefixTree = Entry;
235 Entry->NextPrefixTree = NextEntry;
236 }
237
238 /* Return the entry */
239 return Entry;
240 }
241
242 /* We'll do a case-sensitive search if we've reached this point */
243 NextEntry = Entry;
244 do
245 {
246 /* Do the case-sensitive search */
248 FullName,
250 if ((Result != GenericLessThan) &&
252 {
253 /* This is a positive match, return it */
254 return NextEntry;
255 }
256
257 /* No match yet, continue looping the circular list */
258 NextEntry = NextEntry->CaseMatch;
259 } while (NextEntry != Entry);
260
261 /*
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).
265 */
266 break;
267 }
268
269 /* Splay links exhausted, move to next entry */
270 PreviousEntry = CurrentEntry;
271 CurrentEntry = CurrentEntry->NextPrefixTree;
272 }
273
274 /* If we got here, nothing was found */
275 return NULL;
276}
#define NULL
Definition: types.h:112
#define DPRINT
Definition: sndvol32.h:73
base of all file and directory entries
Definition: entries.h:83
Definition: rtltypes.h:640
struct _UNICODE_PREFIX_TABLE_ENTRY * CaseMatch
Definition: rtltypes.h:644
PUNICODE_STRING Prefix
Definition: rtltypes.h:646
struct _UNICODE_PREFIX_TABLE_ENTRY * NextPrefixTree
Definition: rtltypes.h:643
CSHORT NameLength
Definition: rtltypes.h:642
RTL_SPLAY_LINKS Links
Definition: rtltypes.h:645
CSHORT NodeTypeCode
Definition: rtltypes.h:641
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
short CSHORT
Definition: umtypes.h:127
RTL_GENERIC_COMPARE_RESULTS NTAPI CompareUnicodeStrings(IN PUNICODE_STRING Prefix, IN PUNICODE_STRING String, IN ULONG CaseCheckChar)
Definition: unicodeprefix.c:48
#define PFX_NTC_CHILD
Definition: unicodeprefix.c:23
ULONG NTAPI ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
Definition: unicodeprefix.c:30
#define PFX_NTC_ROOT
Definition: unicodeprefix.c:22
_At_(*)(_In_ PWSK_CLIENT Client, _In_opt_ PUNICODE_STRING NodeName, _In_opt_ PUNICODE_STRING ServiceName, _In_opt_ ULONG NameSpace, _In_opt_ GUID *Provider, _In_opt_ PADDRINFOEXW Hints, _Outptr_ PADDRINFOEXW *Result, _In_opt_ PEPROCESS OwningProcess, _In_opt_ PETHREAD OwningThread, _Inout_ PIRP Irp Result)(Mem)) NTSTATUS(WSKAPI *PFN_WSK_GET_ADDRESS_INFO
Definition: wsk.h:409
_In_ PUNICODE_STRING _In_ ULONG CaseInsensitiveIndex
Definition: rtlfuncs.h:1699
#define RtlRightChild(Links)
_In_ PSTRING FullName
Definition: rtlfuncs.h:1665
#define RtlLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
struct _UNICODE_PREFIX_TABLE_ENTRY * PUNICODE_PREFIX_TABLE_ENTRY
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS

Referenced by CreateRedirectedFile(), and NpFindPrefix().

◆ RtlInitializeUnicodePrefix()

VOID NTAPI RtlInitializeUnicodePrefix ( PUNICODE_PREFIX_TABLE  PrefixTable)

Definition at line 283 of file unicodeprefix.c.

284{
285 DPRINT("RtlInitializeUnicodePrefix(): Table %p\n",
286 PrefixTable);
287
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;
293}
PUNICODE_PREFIX_TABLE_ENTRY LastNextEntry
Definition: rtltypes.h:653
PUNICODE_PREFIX_TABLE_ENTRY NextPrefixTree
Definition: rtltypes.h:652
#define PFX_NTC_TABLE
Definition: unicodeprefix.c:21

Referenced by MupInitializeData(), and NpInitializeVcb().

◆ RtlInsertUnicodePrefix()

BOOLEAN NTAPI RtlInsertUnicodePrefix ( PUNICODE_PREFIX_TABLE  PrefixTable,
PUNICODE_STRING  Prefix,
PUNICODE_PREFIX_TABLE_ENTRY  PrefixTableEntry 
)

Definition at line 300 of file unicodeprefix.c.

303{
304 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
305 ULONG NameCount;
307 PRTL_SPLAY_LINKS SplayLinks;
308
309 DPRINT("RtlInsertUnicodePrefix(): Table %p, Prefix %wZ, "
310 "TableEntry %p\n", PrefixTable, Prefix, PrefixTableEntry);
311
312 /* Find out how many names there are */
313 NameCount = ComputeUnicodeNameLength(Prefix);
314
315 /* Set up the initial entry data */
316 PrefixTableEntry->NameLength = (CSHORT)NameCount;
317 PrefixTableEntry->Prefix = Prefix;
319
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)
324 {
325 /* Not a match, move to the next entry */
326 PreviousEntry = CurrentEntry;
327 CurrentEntry = CurrentEntry->NextPrefixTree;
328 }
329
330 /* Check if we did find a tree by now */
331 if (CurrentEntry->NameLength != (CSHORT)NameCount)
332 {
333 /* We didn't, so insert a new entry in the list */
334 PreviousEntry->NextPrefixTree = PrefixTableEntry;
335 PrefixTableEntry->NextPrefixTree = CurrentEntry;
336
337 /* This is now a root entry with case match */
338 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
340
341 /* Quick return */
342 return TRUE;
343 }
344
345 /* We found a tree, so start the search loop */
346 Entry = CurrentEntry;
347 while (TRUE)
348 {
349 /* Do a case-insensitive comparison to find out the match level */
351 if (Result == GenericEqual)
352 {
353 /* We have a match, start doing a case-sensitive search */
354 NextEntry = Entry;
355
356 /* Search the circular case-match list */
357 do
358 {
359 /* Check if we found a match */
360 if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
361 (GenericEqual))
362 {
363 /* We must fail the insert: it already exists */
364 return FALSE;
365 }
366
367 /* Move to the next entry in the circular list */
368 NextEntry = NextEntry->CaseMatch;
369 }
370 while (NextEntry != Entry);
371
372 /*
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.
376 */
377 PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
378 PrefixTableEntry->NextPrefixTree = NULL;
379
380 /* Insert it into the circular list */
381 PrefixTableEntry->CaseMatch = Entry->CaseMatch;
382 Entry->CaseMatch = PrefixTableEntry;
383 break;
384 }
385
386 /* Check if the result was greater or lesser than */
388 {
389 /* Check out if we have a left child */
390 if (RtlLeftChild(&Entry->Links))
391 {
392 /* We do, enter it and restart the loop */
393 SplayLinks = RtlLeftChild(&Entry->Links);
394 Entry = CONTAINING_RECORD(SplayLinks,
396 Links);
397 }
398 else
399 {
400 /* We don't, set this entry as a child */
401 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
402 PrefixTableEntry->NextPrefixTree = NULL;
404
405 /* Insert us into the tree */
407 break;
408 }
409 }
410 else
411 {
412 /* Check out if we have a right child */
413 if (RtlRightChild(&Entry->Links))
414 {
415 /* We do, enter it and restart the loop */
416 SplayLinks = RtlRightChild(&Entry->Links);
417 Entry = CONTAINING_RECORD(SplayLinks,
419 Links);
420 }
421 else
422 {
423 /* We don't, set this entry as a child */
424 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
425 PrefixTableEntry->NextPrefixTree = NULL;
427
428 /* Insert us into the tree */
430 break;
431 }
432 }
433 }
434
435 /* Get the next tree entry */
436 NextEntry = CurrentEntry->NextPrefixTree;
437
438 /* Set what was the current entry to a child entry */
439 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
440 CurrentEntry->NextPrefixTree = NULL;
441
442 /* Splay the tree */
443 SplayLinks = RtlSplay(&Entry->Links);
444
445 /* The link points to the root, get it */
447
448 /* Mark the root as a root entry */
449 Entry->NodeTypeCode = PFX_NTC_ROOT;
450
451 /* Add it to the tree list */
452 PreviousEntry->NextPrefixTree = Entry;
453 Entry->NextPrefixTree = NextEntry;
454
455 /* Return success */
456 return TRUE;
457}
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define PFX_NTC_CASE_MATCH
Definition: unicodeprefix.c:24
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
#define RtlInitializeSplayLinks(Links)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
_In_ __drv_aliasesMem PSTRING _Out_ PPREFIX_TABLE_ENTRY PrefixTableEntry
Definition: rtlfuncs.h:1648

Referenced by NpCreateFcb(), NpCreateRootDcb(), and QueryPathCompletionRoutine().

◆ RtlNextUnicodePrefix()

PUNICODE_PREFIX_TABLE_ENTRY NTAPI RtlNextUnicodePrefix ( PUNICODE_PREFIX_TABLE  PrefixTable,
BOOLEAN  Restart 
)

Definition at line 464 of file unicodeprefix.c.

466{
467 PRTL_SPLAY_LINKS SplayLinks;
468 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry = NULL;
469
470 DPRINT("RtlNextUnicodePrefix(): Table %p Restart %u\n",
471 PrefixTable, Restart);
472
473 /* We might need this entry 2/3rd of the time, so cache it now */
474 if (PrefixTable->LastNextEntry)
475 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
476
477 /* Check if this is a restart or if we don't have a last entry */
478 if ((Restart) || !(PrefixTable->LastNextEntry))
479 {
480 /* Get the next entry and validate it */
481 Entry = PrefixTable->NextPrefixTree;
482 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
483
484 /* Now get the Splay Tree Links */
485 SplayLinks = &Entry->Links;
486
487 /* Loop until we get the first node in the tree */
488 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
489
490 /* Get the entry from it */
491 Entry = CONTAINING_RECORD(SplayLinks,
493 Links);
494 }
495 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
496 {
497 /* If the last entry was a Case Match, then return it */
498 Entry = CaseMatchEntry;
499 }
500 else
501 {
502 /* Find the successor */
503 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
504 if (!SplayLinks)
505 {
506 /* Didn't find one, we'll have to search the tree */
507 SplayLinks = &PrefixTable->LastNextEntry->Links;
508
509 /* Get the topmost node (root) */
510 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
511 Entry = CONTAINING_RECORD(SplayLinks,
513 Links);
514
515 /* Get its tree and make sure something is in it */
516 Entry = Entry->NextPrefixTree;
517 if (Entry->NameLength <= 0) return NULL;
518
519 /* Select these new links and find the first node */
520 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
521 }
522
523 /* Get the entry from it */
524 Entry = CONTAINING_RECORD(SplayLinks,
526 Links);
527 }
528
529 /* Save this entry as the last one returned, and return it */
530 PrefixTable->LastNextEntry = Entry;
531 return Entry;
532}
@ Restart
Definition: sacdrv.h:269
#define RtlIsRoot(Links)
#define RtlParent(Links)
_Must_inspect_result_ NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlRealSuccessor(_In_ PRTL_SPLAY_LINKS Links)

◆ RtlRemoveUnicodePrefix()

VOID NTAPI RtlRemoveUnicodePrefix ( PUNICODE_PREFIX_TABLE  PrefixTable,
PUNICODE_PREFIX_TABLE_ENTRY  PrefixTableEntry 
)

Definition at line 539 of file unicodeprefix.c.

541{
542 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
543 PRTL_SPLAY_LINKS SplayLinks;
544
545 DPRINT("RtlRemoveUnicodePrefix(): Table %p, TableEntry %p\n",
546 PrefixTable, PrefixTableEntry);
547
548 /* Erase the last entry */
549 PrefixTable->LastNextEntry = NULL;
550
551 /* Check if this was a Case Match Entry */
552 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
553 {
554 /* Get the case match entry */
555 Entry = PrefixTableEntry->CaseMatch;
556
557 /* Now loop until we find one referencing what the caller sent */
558 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
559
560 /* We found the entry that was sent, link them to delete this entry */
561 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
562 }
563 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
564 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
565 {
566 /* Check if this entry is a case match */
567 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
568 {
569 /* Get the case match entry */
570 Entry = PrefixTableEntry->CaseMatch;
571
572 /* Now loop until we find one referencing what the caller sent */
573 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
574
575 /* We found the entry that was sent, link them to delete this entry */
576 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
577
578 /* Copy the data */
579 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
580 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
581 Entry->Links = PrefixTableEntry->Links;
582
583 /* Now check if we are a root entry */
584 if (RtlIsRoot(&PrefixTableEntry->Links))
585 {
586 /* We are, so make this entry root as well */
587 Entry->Links.Parent = &Entry->Links;
588
589 /* Find the entry referencing us */
590 RefEntry = Entry->NextPrefixTree;
591 while (RefEntry->NextPrefixTree != Entry)
592 {
593 /* Not this one, move to the next entry */
594 RefEntry = RefEntry->NextPrefixTree;
595 }
596
597 /* Link them to us now */
598 RefEntry->NextPrefixTree = Entry;
599 }
600 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
601 {
602 /* We were the left child, so make us as well */
603 RtlParent(&PrefixTableEntry->Links)->LeftChild = &Entry->Links;
604 }
605 else
606 {
607 /* We were the right child, so make us as well */
608 RtlParent(&PrefixTableEntry->Links)->RightChild = &Entry->Links;
609 }
610
611 /* Check if we have a left child */
612 if (RtlLeftChild(&Entry->Links))
613 {
614 /* Update its parent link */
615 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
616 }
617 /* Check if we have a right child */
618 if (RtlRightChild(&Entry->Links))
619 {
620 /* Update its parent link */
621 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
622 }
623 }
624 else
625 {
626 /* It's not a case match, so we'll delete the actual entry */
627 SplayLinks = &PrefixTableEntry->Links;
628
629 /* Find the root entry */
630 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
631 Entry = CONTAINING_RECORD(SplayLinks,
633 Links);
634
635 /* Delete the entry and check if the whole tree is gone */
636 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
637 if (!SplayLinks)
638 {
639 /* The tree is also gone now, find the entry referencing us */
640 RefEntry = Entry->NextPrefixTree;
641 while (RefEntry->NextPrefixTree != Entry)
642 {
643 /* Not this one, move to the next entry */
644 RefEntry = RefEntry->NextPrefixTree;
645 }
646
647 /* Link them so this entry stops being referenced */
648 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
649 }
650 else if (&Entry->Links != SplayLinks)
651 {
652 /* The tree is still here, but we got moved to a new one */
653 NewEntry = CONTAINING_RECORD(SplayLinks,
655 Links);
656
657 /* Find the entry referencing us */
658 RefEntry = Entry->NextPrefixTree;
659 while (RefEntry->NextPrefixTree != Entry)
660 {
661 /* Not this one, move to the next entry */
662 RefEntry = RefEntry->NextPrefixTree;
663 }
664
665 /* Since we got moved, make us the new root entry */
666 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
667
668 /* Link us with the entry referencing the old root */
669 RefEntry->NextPrefixTree = NewEntry;
670
671 /* And link us with the old tree */
672 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
673
674 /* Set the old tree as a child */
675 Entry->NodeTypeCode = PFX_NTC_CHILD;
676 Entry->NextPrefixTree = NULL;
677 }
678 }
679 }
680}
#define RtlIsLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)

Referenced by MupDereferenceKnownPrefix(), MupRemoveKnownPrefixEntry(), NpDeleteFcb(), and QueryPathCompletionRoutine().