7de07b254801d75bc3a4cacf6e239aa0ad3053cd
[reactos.git] / reactos / lib / rtl / unicodeprefix.c
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 STATIC
29 ULONG
30 NTAPI
31 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
32 {
33 ULONG Chars = UnicodeName->Length / sizeof(WCHAR);
34 ULONG i, NamesFound = 1;
35
36 /* Loop the string */
37 for (i = 0; i < (Chars - 1); i++)
38 {
39 /* Check if we found a backslash, meaning another name */
40 if (UnicodeName->Buffer[i] == '\\') NamesFound++;
41 }
42
43 /* Return the number of names found */
44 return NamesFound;
45 }
46
47
48 STATIC
49 RTL_GENERIC_COMPARE_RESULTS
50 NTAPI
51 CompareUnicodeStrings(IN PUNICODE_STRING Prefix,
52 IN PUNICODE_STRING String,
53 IN ULONG CaseCheckChar)
54 {
55 ULONG StringLength = String->Length / sizeof(WCHAR);
56 ULONG PrefixLength = Prefix->Length / sizeof(WCHAR);
57 ULONG ScanLength = min(StringLength, PrefixLength);
58 ULONG i;
59 WCHAR FoundPrefix, FoundString;
60 PWCHAR p, p1;
61 DPRINT("CompareUnicodeStrings: %wZ %wZ\n", String, Prefix);
62
63 /* Handle case noticed in npfs when Prefix = '\' and name starts with '\' */
64 if ((PrefixLength == 1) &&
65 (Prefix->Buffer[0] == '\\') &&
66 (StringLength > 1) &&
67 (String->Buffer[0] == '\\'))
68 {
69 /* The string is actually a prefix */
70 return -1;
71 }
72
73 /* Validate the Case Check Character Position */
74 if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
75
76 /* Do the case sensitive comparison first */
77 for (i = 0; i < CaseCheckChar; i++)
78 {
79 /* Compare the two characters */
80 if (Prefix->Buffer[i] != String->Buffer[i]) break;
81 }
82
83 /* Save the characters we found */
84 FoundPrefix = Prefix->Buffer[i];
85 FoundString = String->Buffer[i];
86
87 /* Check if we exausted the search above */
88 if (i == CaseCheckChar)
89 {
90 /* Do a case-insensitive search */
91 p = &Prefix->Buffer[i];
92 p1 = &String->Buffer[i];
93 do
94 {
95 /* Move to the next character */
96 FoundPrefix = *p++;
97 FoundString = *p1++;
98
99 /* Compare it */
100 if (FoundPrefix != FoundString)
101 {
102 /* Upcase the characters */
103 FoundPrefix = RtlUpcaseUnicodeChar(FoundPrefix);
104 FoundString = RtlUpcaseUnicodeChar(FoundString);
105
106 /* Compare them again */
107 if (FoundPrefix != FoundString) break;
108 }
109
110 /* Move to the next char */
111 i++;
112 } while (i < ScanLength);
113 }
114
115 /* Check if we weren't able to find a match in the loops */
116 if (i < ScanLength)
117 {
118 /* If the prefix character found was a backslash, this is a less */
119 if (FoundPrefix == '\\') return GenericLessThan;
120
121 /* If the string character found was a backslack, then this is a more */
122 if (FoundString == '\\') return GenericGreaterThan;
123
124 /* None of those two special cases, do a normal check */
125 if (FoundPrefix < FoundString) return GenericLessThan;
126
127 /* The only choice left is that Prefix > String */
128 return GenericGreaterThan;
129 }
130
131 /* If we got here, a match was found. Check if the prefix is smaller */
132 if (PrefixLength < StringLength)
133 {
134 /* Check if the string is actually a prefix */
135 if (String->Buffer[PrefixLength] == '\\') return -1;
136
137 /* It's not a prefix, and it's shorter, so it's a less */
138 return GenericLessThan;
139 }
140
141 /* Check if the prefix is longer */
142 if (PrefixLength > StringLength) return GenericGreaterThan;
143
144 /* If we got here, then they are 100% equal */
145 return GenericEqual;
146 }
147
148 /*
149 * @implemented
150 */
151 PUNICODE_PREFIX_TABLE_ENTRY
152 NTAPI
153 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
154 PUNICODE_STRING FullName,
155 ULONG CaseInsensitiveIndex)
156 {
157 ULONG NameCount;
158 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
159 PRTL_SPLAY_LINKS SplayLinks;
160 RTL_GENERIC_COMPARE_RESULTS Result;
161 DPRINT("RtlFindUnicodePrefix\n");
162
163 /* Find out how many names there are */
164 NameCount = ComputeUnicodeNameLength(FullName);
165
166 /* Find the right spot where to start looking for this entry */
167 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
168 CurrentEntry = PreviousEntry->NextPrefixTree;
169 while (CurrentEntry->NameLength > NameCount)
170 {
171 /* Not a match, move to the next entry */
172 PreviousEntry = CurrentEntry;
173 CurrentEntry = CurrentEntry->NextPrefixTree;
174 }
175
176 /* Loop every entry which has valid entries */
177 while (CurrentEntry->NameLength)
178 {
179 DPRINT("CurrentEntry->NameLength %lx\n", CurrentEntry->NameLength);
180
181 /* Get the splay links and loop */
182 SplayLinks = &CurrentEntry->Links;
183 while (SplayLinks)
184 {
185 /* Get the entry */
186 DPRINT("SplayLinks %p\n", SplayLinks);
187 Entry = CONTAINING_RECORD(SplayLinks,
188 UNICODE_PREFIX_TABLE_ENTRY,
189 Links);
190
191 /* Do the comparison */
192 Result = CompareUnicodeStrings(Entry->Prefix, FullName, 0);
193 DPRINT("Result %lx\n", Result);
194 if (Result == GenericGreaterThan)
195 {
196 /* Prefix is greater, so restart on the left child */
197 SplayLinks = RtlLeftChild(SplayLinks);
198 continue;
199 }
200 else if (Result == GenericLessThan)
201 {
202 /* Prefix is smaller, so restart on the right child */
203 SplayLinks = RtlRightChild(SplayLinks);
204 continue;
205 }
206
207 /*
208 * We have a match, check if this was a case-sensitive search
209 * NOTE: An index of 0 means case-insensitive(ie, we'll be case
210 * insensitive since index 0, ie, all the time)
211 */
212 DPRINT("CaseInsensitiveIndex %lx\n", CaseInsensitiveIndex);
213 if (!CaseInsensitiveIndex)
214 {
215 /*
216 * Check if this entry was a child. We need to return the root,
217 * so if this entry was a child, we'll splay the tree and get
218 * the root, and set the current entry as a child.
219 */
220 if (Entry->NodeTypeCode == PFX_NTC_CHILD)
221 {
222 /* Get the next entry */
223 NextEntry = CurrentEntry->NextPrefixTree;
224
225 /* Make the current entry become a child */
226 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
227 CurrentEntry->NextPrefixTree = NULL;
228
229 /* Splay the tree */
230 SplayLinks = RtlSplay(&Entry->Links);
231
232 /* Get the new root entry */
233 Entry = CONTAINING_RECORD(SplayLinks,
234 UNICODE_PREFIX_TABLE_ENTRY,
235 Links);
236
237 /* Set it as a root entry */
238 Entry->NodeTypeCode = PFX_NTC_ROOT;
239
240 /* Add it to the root entries list */
241 PreviousEntry->NextPrefixTree = Entry;
242 Entry->NextPrefixTree = NextEntry;
243 }
244
245 /* Return the entry */
246 DPRINT("RtlFindUnicodePrefix: %p\n", Entry);
247 return Entry;
248 }
249
250 /* We'll do a case-sensitive search if we've reached this point */
251 NextEntry = Entry;
252 do
253 {
254 /* Do the case-sensitive search */
255 Result = CompareUnicodeStrings(NextEntry->Prefix,
256 FullName,
257 CaseInsensitiveIndex);
258 if ((Result != GenericLessThan) &&
259 (Result != GenericGreaterThan))
260 {
261 /* This is a positive match, return it */
262 DPRINT("RtlFindUnicodePrefix: %p\n", NextEntry);
263 return NextEntry;
264 }
265
266 /* No match yet, continue looping the circular list */
267 NextEntry = NextEntry->CaseMatch;
268 DPRINT("NextEntry %p\n", NextEntry);
269 } while (NextEntry != Entry);
270
271 /*
272 * If we got here, then we found a non-case-sensitive match, but
273 * we need to find a case-sensitive match, so we'll just keep
274 * searching the next tree (NOTE: we need to break out for this).
275 */
276 break;
277 }
278
279 /* Splay links exausted, move to next entry */
280 PreviousEntry = CurrentEntry;
281 CurrentEntry = CurrentEntry->NextPrefixTree;
282 DPRINT("CurrentEntry %p\n", CurrentEntry);
283 }
284
285 /* If we got here, nothing was found */
286 DPRINT("RtlFindUnicodePrefix: %p\n", NULL);
287 return NULL;
288 }
289
290 /*
291 * @implemented
292 */
293 VOID
294 NTAPI
295 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
296 {
297 /* Setup the table */
298 PrefixTable->NameLength = 0;
299 PrefixTable->LastNextEntry = NULL;
300 PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
301 PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
302 }
303
304 /*
305 * @implemented
306 */
307 BOOLEAN
308 NTAPI
309 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
310 PUNICODE_STRING Prefix,
311 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
312 {
313 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
314 ULONG NameCount;
315 RTL_GENERIC_COMPARE_RESULTS Result;
316 PRTL_SPLAY_LINKS SplayLinks;
317 DPRINT("RtlInsertUnicodePrefix\n");
318
319 /* Find out how many names there are */
320 NameCount = ComputeUnicodeNameLength(Prefix);
321
322 /* Set up the initial entry data */
323 PrefixTableEntry->NameLength = NameCount;
324 PrefixTableEntry->Prefix = Prefix;
325 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
326
327 /* Find the right spot where to insert this entry */
328 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
329 CurrentEntry = PreviousEntry->NextPrefixTree;
330 while (CurrentEntry->NameLength > NameCount)
331 {
332 /* Not a match, move to the next entry */
333 PreviousEntry = CurrentEntry;
334 CurrentEntry = CurrentEntry->NextPrefixTree;
335 }
336
337 /* Check if we did find a tree by now */
338 if (CurrentEntry->NameLength != NameCount)
339 {
340 /* We didn't, so insert a new entry in the list */
341 PreviousEntry->NextPrefixTree = PrefixTableEntry;
342 PrefixTableEntry->NextPrefixTree = CurrentEntry;
343
344 /* This is now a root entry with case match */
345 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
346 PrefixTableEntry->CaseMatch = PrefixTableEntry;
347
348 /* Quick return */
349 DPRINT("RtlInsertUnicodePrefix TRUE\n");
350 return TRUE;
351 }
352
353 /* We found a tree, so star thte search loop */
354 Entry = CurrentEntry;
355 while (TRUE)
356 {
357 /* Do a case-insensitive comparison to find out the match level */
358 Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
359 if (Result == GenericEqual)
360 {
361 /* We have a match, start doing a case-sensitive search */
362 NextEntry = Entry;
363
364 /* Search the circular case-match list */
365 do
366 {
367 /* Check if we found a match */
368 if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
369 (GenericEqual))
370 {
371 /* We must fail the insert: it already exists */
372 DPRINT("RtlInsertUnicodePrefix FALSE\n");
373 return FALSE;
374 }
375
376 /* Move to the next entry in the circular list */
377 NextEntry = NextEntry->CaseMatch;
378 }
379 while (NextEntry != Entry);
380
381 /*
382 * No match found, so we can safely insert it. Remember that a
383 * case insensitive match was found, so this is not a ROOT NTC
384 * but a Case Match NTC instead.
385 */
386 PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
387 PrefixTableEntry->NextPrefixTree = NULL;
388
389 /* Insert it into the circular list */
390 PrefixTableEntry->CaseMatch = Entry->CaseMatch;
391 Entry->CaseMatch = PrefixTableEntry;
392 break;
393 }
394
395 /* Check if the result was greater or lesser than */
396 if (Result == GenericGreaterThan)
397 {
398 /* Check out if we have a left child */
399 if (RtlLeftChild(&Entry->Links))
400 {
401 /* We do, enter it and restart the loop */
402 SplayLinks = RtlLeftChild(&Entry->Links);
403 Entry = CONTAINING_RECORD(SplayLinks,
404 UNICODE_PREFIX_TABLE_ENTRY,
405 Links);
406 }
407 else
408 {
409 /* We don't, set this entry as a child */
410 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
411 PrefixTableEntry->NextPrefixTree = NULL;
412 PrefixTableEntry->CaseMatch = PrefixTableEntry;
413
414 /* Insert us into the tree */
415 RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
416 break;
417 }
418 }
419 else
420 {
421 /* Check out if we have a right child */
422 if (RtlRightChild(&Entry->Links))
423 {
424 /* We do, enter it and restart the loop */
425 SplayLinks = RtlLeftChild(&Entry->Links);
426 Entry = CONTAINING_RECORD(SplayLinks,
427 UNICODE_PREFIX_TABLE_ENTRY,
428 Links);
429 }
430 else
431 {
432 /* We don't, set this entry as a child */
433 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
434 PrefixTableEntry->NextPrefixTree = NULL;
435 PrefixTableEntry->CaseMatch = PrefixTableEntry;
436
437 /* Insert us into the tree */
438 RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
439 break;
440 }
441 }
442 }
443
444 /* Get the next tree entry */
445 NextEntry = CurrentEntry->NextPrefixTree;
446
447 /* Set what was the current entry to a child entry */
448 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
449 CurrentEntry->NextPrefixTree = NULL;
450
451 /* Splay the tree */
452 SplayLinks = RtlSplay(&Entry->Links);
453
454 /* The link points to the root, get it */
455 Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
456
457 /* Mark the root as a root entry */
458 Entry->NodeTypeCode = PFX_NTC_ROOT;
459
460 /* Add it to the tree list */
461 PreviousEntry->NextPrefixTree = Entry;
462 Entry->NextPrefixTree = NextEntry;
463
464 /* Return success */
465 DPRINT("RtlInsertUnicodePrefix TRUE\n");
466 return TRUE;
467 }
468
469 /*
470 * @implemented
471 */
472 PUNICODE_PREFIX_TABLE_ENTRY
473 NTAPI
474 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
475 BOOLEAN Restart)
476 {
477 PRTL_SPLAY_LINKS SplayLinks;
478 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
479 DPRINT("RtlNextUnicodePrefix\n");
480
481 /* We might need this entry 2/3rd of the time, so cache it now */
482 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
483
484 /* Check if this is a restart or if we don't have a last entry */
485 if ((Restart) || !(PrefixTable->LastNextEntry))
486 {
487 /* Get the next entry and validate it */
488 Entry = PrefixTable->NextPrefixTree;
489 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
490
491 /* Now get the Splay Tree Links */
492 SplayLinks = &Entry->Links;
493
494 /* Loop until we get the first node in the tree */
495 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
496
497 /* Get the entry from it */
498 Entry = CONTAINING_RECORD(SplayLinks,
499 UNICODE_PREFIX_TABLE_ENTRY,
500 Links);
501 }
502 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
503 {
504 /* If the last entry was a Case Match, then return it */
505 Entry = CaseMatchEntry;
506 }
507 else
508 {
509 /* Find the successor */
510 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
511 if (!SplayLinks)
512 {
513 /* Didn't find one, we'll have to search the tree */
514 SplayLinks = &PrefixTable->LastNextEntry->Links;
515
516 /* Get the topmost node (root) */
517 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
518 Entry = CONTAINING_RECORD(SplayLinks,
519 UNICODE_PREFIX_TABLE_ENTRY,
520 Links);
521
522 /* Get its tree and make sure somethign is in it */
523 Entry = Entry->NextPrefixTree;
524 if (Entry->NameLength <= 0) return NULL;
525
526 /* Select these new links and find the first node */
527 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
528 }
529
530 /* Get the entry from it */
531 Entry = CONTAINING_RECORD(SplayLinks,
532 UNICODE_PREFIX_TABLE_ENTRY,
533 Links);
534 }
535
536 /* Save this entry as the last one returned, and return it */
537 PrefixTable->LastNextEntry = Entry;
538 DPRINT("RtlNextUnicodePrefix: %p\n", Entry);
539 return Entry;
540 }
541
542 /*
543 * @implemented
544 */
545 VOID
546 NTAPI
547 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
548 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
549 {
550 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
551 PRTL_SPLAY_LINKS SplayLinks;
552 DPRINT("RtlRemoveUnicodePrefix\n");
553
554 /* Erase the last entry */
555 PrefixTable->LastNextEntry = NULL;
556
557 /* Check if this was a Case Match Entry */
558 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
559 {
560 /* Get the case match entry */
561 Entry = PrefixTableEntry->CaseMatch;
562
563 /* Now loop until we find one referencing what the caller sent */
564 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
565
566 /* We found the entry that was sent, link them to delete this entry */
567 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
568 }
569 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
570 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
571 {
572 /* Check if this entry is a case match */
573 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
574 {
575 /* Get the case match entry */
576 Entry = PrefixTableEntry->CaseMatch;
577
578 /* Now loop until we find one referencing what the caller sent */
579 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
580
581 /* We found the entry that was sent, link them to delete this entry */
582 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
583
584 /* Copy the data */
585 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
586 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
587 Entry->Links = PrefixTableEntry->Links;
588
589 /* Now check if we are a root entry */
590 if (RtlIsRoot(&PrefixTableEntry->Links))
591 {
592 /* We are, so make this entry root as well */
593 Entry->Links.Parent = &Entry->Links;
594
595 /* Find the entry referencing us */
596 RefEntry = Entry->NextPrefixTree;
597 while (RefEntry->NextPrefixTree != Entry)
598 {
599 /* Not this one, move to the next entry */
600 RefEntry = RefEntry->NextPrefixTree;
601 }
602
603 /* Link them to us now */
604 RefEntry->NextPrefixTree = Entry;
605 }
606 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
607 {
608 /* We were the left child, so make us as well */
609 RtlParent(&PrefixTableEntry->Links)->LeftChild = &Entry->Links;
610 }
611 else
612 {
613 /* We were the right child, so make us as well */
614 RtlParent(&PrefixTableEntry->Links)->RightChild = &Entry->Links;
615 }
616
617 /* Check if we have a left child */
618 if (RtlLeftChild(&Entry->Links))
619 {
620 /* Update its parent link */
621 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
622 }
623 /* Check if we have a right child */
624 if (RtlRightChild(&Entry->Links))
625 {
626 /* Update its parent link */
627 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
628 }
629 }
630 else
631 {
632 /* It's not a case match, so we'll delete the actual entry */
633 SplayLinks = &PrefixTableEntry->Links;
634
635 /* Find the root entry */
636 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
637 Entry = CONTAINING_RECORD(SplayLinks,
638 UNICODE_PREFIX_TABLE_ENTRY,
639 Links);
640
641 /* Delete the entry and check if the whole tree is gone */
642 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
643 if (!SplayLinks)
644 {
645 /* The tree is also gone now, find the entry referencing us */
646 RefEntry = Entry->NextPrefixTree;
647 while (RefEntry->NextPrefixTree != Entry)
648 {
649 /* Not this one, move to the next entry */
650 RefEntry = RefEntry->NextPrefixTree;
651 }
652
653 /* Link them so this entry stops being referenced */
654 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
655 }
656 else if (&Entry->Links != SplayLinks)
657 {
658 /* The tree is still here, but we got moved to a new one */
659 NewEntry = CONTAINING_RECORD(SplayLinks,
660 UNICODE_PREFIX_TABLE_ENTRY,
661 Links);
662
663 /* Find the entry referencing us */
664 RefEntry = Entry->NextPrefixTree;
665 while (RefEntry->NextPrefixTree != Entry)
666 {
667 /* Not this one, move to the next entry */
668 RefEntry = RefEntry->NextPrefixTree;
669 }
670
671 /* Since we got moved, make us the new root entry */
672 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
673
674 /* Link us with the entry referencing the old root */
675 RefEntry->NextPrefixTree = NewEntry;
676
677 /* And link us with the old tree */
678 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
679
680 /* Set the old tree as a child */
681 Entry->NodeTypeCode = PFX_NTC_CHILD;
682 Entry->NextPrefixTree = NULL;
683 }
684 }
685 }
686 }
687
688 /* EOF */