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 */