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