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