1 /*
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)
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 /*
17 * FIXME: Try to find the official names and add to NDK
18 * Definitions come from fastfat driver.
19 */
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)
25
26 /* FUNCTIONS ***************************************************************/
27
28 ULONG
29 NTAPI
ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)30 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
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 }
45
46 RTL_GENERIC_COMPARE_RESULTS
47 NTAPI
CompareUnicodeStrings(IN PUNICODE_STRING Prefix,IN PUNICODE_STRING String,IN ULONG CaseCheckChar)48 CompareUnicodeStrings(IN PUNICODE_STRING Prefix,
49 IN PUNICODE_STRING String,
50 IN ULONG CaseCheckChar)
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 }
143
144 /*
145 * @implemented
146 */
147 PUNICODE_PREFIX_TABLE_ENTRY
148 NTAPI
RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,PUNICODE_STRING FullName,ULONG CaseInsensitiveIndex)149 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
150 PUNICODE_STRING FullName,
151 ULONG CaseInsensitiveIndex)
152 {
153 ULONG NameCount;
154 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
155 PRTL_SPLAY_LINKS SplayLinks;
156 RTL_GENERIC_COMPARE_RESULTS Result;
157
158 DPRINT("RtlFindUnicodePrefix(): Table %p, FullName %wZ, "
159 "CaseInsensitive %lu\n", PrefixTable, FullName, CaseInsensitiveIndex);
160
161 /* Find out how many names there are */
162 NameCount = ComputeUnicodeNameLength(FullName);
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,
183 UNICODE_PREFIX_TABLE_ENTRY,
184 Links);
185
186 /* Do the comparison */
187 Result = CompareUnicodeStrings(Entry->Prefix, FullName, 0);
188 if (Result == GenericGreaterThan)
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 */
206 if (!CaseInsensitiveIndex)
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,
227 UNICODE_PREFIX_TABLE_ENTRY,
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 */
247 Result = CompareUnicodeStrings(NextEntry->Prefix,
248 FullName,
249 CaseInsensitiveIndex);
250 if ((Result != GenericLessThan) &&
251 (Result != GenericGreaterThan))
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 }
277
278 /*
279 * @implemented
280 */
281 VOID
282 NTAPI
RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)283 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
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 }
294
295 /*
296 * @implemented
297 */
298 BOOLEAN
299 NTAPI
RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,PUNICODE_STRING Prefix,PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)300 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
301 PUNICODE_STRING Prefix,
302 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
303 {
304 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
305 ULONG NameCount;
306 RTL_GENERIC_COMPARE_RESULTS Result;
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;
318 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
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;
339 PrefixTableEntry->CaseMatch = PrefixTableEntry;
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 */
350 Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
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 */
387 if (Result == GenericGreaterThan)
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,
395 UNICODE_PREFIX_TABLE_ENTRY,
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;
403 PrefixTableEntry->CaseMatch = PrefixTableEntry;
404
405 /* Insert us into the tree */
406 RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
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,
418 UNICODE_PREFIX_TABLE_ENTRY,
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;
426 PrefixTableEntry->CaseMatch = PrefixTableEntry;
427
428 /* Insert us into the tree */
429 RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
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 */
446 Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
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 }
458
459 /*
460 * @implemented
461 */
462 PUNICODE_PREFIX_TABLE_ENTRY
463 NTAPI
RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,BOOLEAN Restart)464 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
465 BOOLEAN Restart)
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,
492 UNICODE_PREFIX_TABLE_ENTRY,
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,
512 UNICODE_PREFIX_TABLE_ENTRY,
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,
525 UNICODE_PREFIX_TABLE_ENTRY,
526 Links);
527 }
528
529 /* Save this entry as the last one returned, and return it */
530 PrefixTable->LastNextEntry = Entry;
531 return Entry;
532 }
533
534 /*
535 * @implemented
536 */
537 VOID
538 NTAPI
RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)539 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
540 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
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,
632 UNICODE_PREFIX_TABLE_ENTRY,
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,
654 UNICODE_PREFIX_TABLE_ENTRY,
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 }
681
682 /* EOF */
683