sdk/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 ULONG
  29 NTAPI
  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
  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
 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
 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
 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
 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
 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 */