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