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  * @unimplemented
  49  */
  50 PUNICODE_PREFIX_TABLE_ENTRY
  51 NTAPI
  52 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
  53                      PUNICODE_STRING FullName,
  54                      ULONG CaseInsensitiveIndex)
  55 {
  56         UNIMPLEMENTED;
  57         return 0;
  58 }
  59
  60 /*
  61  * @implemented
  62  */
  63 VOID
  64 NTAPI
  65 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
  66 {
  67         /* Setup the table */
  68     PrefixTable->NameLength = 0;
  69     PrefixTable->LastNextEntry = NULL;
  70     PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
  71     PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
  72 }
  73
  74 /*
  75  * @unimplemented
  76  */
  77 BOOLEAN
  78 NTAPI
  79 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
  80                        PUNICODE_STRING Prefix,
  81                        PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
  82 {
  83     /*
  84      * implementation notes:
  85      * - get name length (number of names) DONE
  86      * - init splay links DONE
  87      * - find a matching tree DONE
  88      * - if !found, insert a new NTC_ROOT entry and return TRUE; DONE
  89      * - if found, loop tree and compare strings:
  90      *   if equal, handle casematch/nomatch
  91      *   if greater or lesser equal, then add left/right childs accordingly
  92      * - splay the tree
  93      */
  94     PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry;
  95     ULONG NameCount;
  96
  97     /* Find out how many names there are */
  98     NameCount = ComputeUnicodeNameLength(Prefix);
  99
 100     /* Set up the initial entry data */
 101     PrefixTableEntry->NameLength = NameCount;
 102     PrefixTableEntry->Prefix = Prefix;
 103     RtlInitializeSplayLinks(&PrefixTableEntry->Links);
 104
 105     /* Find the right spot where to insert this entry */
 106     PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
 107     CurrentEntry = PreviousEntry->NextPrefixTree;
 108     while (CurrentEntry->NameLength > NameCount)
 109     {
 110         /* Not a match, move to the next entry */
 111         PreviousEntry = CurrentEntry;
 112         CurrentEntry = CurrentEntry->NextPrefixTree;
 113     }
 114
 115     /* Check if we did find a tree by now */
 116     if (CurrentEntry->NameLength != NameCount)
 117     {
 118         /* We didn't, so insert a new entry in the list */
 119         PreviousEntry->NextPrefixTree = PrefixTableEntry;
 120         PrefixTableEntry->NextPrefixTree = CurrentEntry;
 121
 122         /* This is now a root entry with case match */
 123         PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
 124         PrefixTableEntry->CaseMatch = PrefixTableEntry;
 125
 126         /* Quick return */
 127         return TRUE;
 128     }
 129
 130     /* FIXME */
 131         UNIMPLEMENTED;
 132         return FALSE;
 133 }
 134
 135 /*
 136 * @implemented
 137 */
 138 PUNICODE_PREFIX_TABLE_ENTRY
 139 NTAPI
 140 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
 141                      BOOLEAN Restart)
 142 {
 143     PRTL_SPLAY_LINKS SplayLinks;
 144     PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
 145
 146     /* We might need this entry 2/3rd of the time, so cache it now */
 147     CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
 148
 149     /* Check if this is a restart or if we don't have a last entry */
 150     if ((Restart) || !(PrefixTable->LastNextEntry))
 151     {
 152         /* Get the next entry and validate it */
 153         Entry = PrefixTable->NextPrefixTree;
 154         if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
 155
 156         /* Now get the Splay Tree Links */
 157         SplayLinks = &Entry->Links;
 158
 159         /* Loop until we get the first node in the tree */
 160         while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
 161
 162         /* Get the entry from it */
 163         Entry = CONTAINING_RECORD(SplayLinks,
 164                                   UNICODE_PREFIX_TABLE_ENTRY,
 165                                   Links);
 166     }
 167     else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
 168     {
 169         /* If the last entry was a Case Match, then return it */
 170         Entry = CaseMatchEntry;
 171     }
 172     else
 173     {
 174         /* Find the successor */
 175         SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
 176         if (!SplayLinks)
 177         {
 178             /* Didn't find one, we'll have to search the tree */
 179             SplayLinks = &PrefixTable->LastNextEntry->Links;
 180
 181             /* Get the topmost node (root) */
 182             while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
 183             Entry = CONTAINING_RECORD(SplayLinks,
 184                                       UNICODE_PREFIX_TABLE_ENTRY,
 185                                       Links);
 186
 187             /* Get its tree and make sure somethign is in it */
 188             Entry = Entry->NextPrefixTree;
 189             if (Entry->NameLength <= 0) return NULL;
 190
 191             /* Select these new links and find the first node */
 192             while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
 193         }
 194
 195         /* Get the entry from it */
 196         Entry = CONTAINING_RECORD(SplayLinks,
 197                                   UNICODE_PREFIX_TABLE_ENTRY,
 198                                   Links);
 199     }
 200
 201     /* Save this entry as the last one returned, and return it */
 202     PrefixTable->LastNextEntry = Entry;
 203     return Entry;
 204 }
 205
 206 /*
 207  * @implemented
 208  */
 209 VOID
 210 NTAPI
 211 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
 212                        PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
 213 {
 214     PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
 215     PRTL_SPLAY_LINKS SplayLinks;
 216
 217     /* Erase the last entry */
 218     PrefixTable->LastNextEntry = NULL;
 219
 220     /* Check if this was a Case Match Entry */
 221     if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
 222     {
 223         /* Get the case match entry */
 224         Entry = PrefixTableEntry->CaseMatch;
 225
 226         /* Now loop until we find one referencing what the caller sent */
 227         while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
 228
 229         /* We found the entry that was sent, link them to delete this entry */
 230         Entry->CaseMatch = PrefixTableEntry->CaseMatch;
 231     }
 232     else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
 233             (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
 234     {
 235         /* Check if this entry is a case match */
 236         if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
 237         {
 238             /* Get the case match entry */
 239             Entry = PrefixTableEntry->CaseMatch;
 240
 241             /* Now loop until we find one referencing what the caller sent */
 242             while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
 243
 244             /* We found the entry that was sent, link them to delete this entry */
 245             Entry->CaseMatch = PrefixTableEntry->CaseMatch;
 246
 247             /* Copy the data */
 248             Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
 249             Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
 250             Entry->Links = PrefixTableEntry->Links;
 251
 252             /* Now check if we are a root entry */
 253             if (RtlIsRoot(&PrefixTableEntry->Links))
 254             {
 255                 /* We are, so make this entry root as well */
 256                 Entry->Links.Parent = &Entry->Links;
 257
 258                 /* Find the entry referencing us */
 259                 RefEntry = Entry->NextPrefixTree;
 260                 while (RefEntry->NextPrefixTree != Entry)
 261                 {
 262                     /* Not this one, move to the next entry */
 263                     RefEntry = RefEntry->NextPrefixTree;
 264                 }
 265
 266                 /* Link them to us now */
 267                 RefEntry->NextPrefixTree = Entry;
 268             }
 269             else if (RtlIsLeftChild(&PrefixTableEntry->Links))
 270             {
 271                 /* We were the left child, so make us as well */
 272                 Entry->Links.LeftChild = &Entry->Links;
 273             }
 274             else
 275             {
 276                 /* We were the right child, so make us as well */
 277                 Entry->Links.RightChild = &Entry->Links;
 278             }
 279
 280             /* Check if we have a left child */
 281             if (RtlLeftChild(&Entry->Links))
 282             {
 283                 /* Update its parent link */
 284                 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
 285             }
 286             /* Check if we have a right child */
 287             if (RtlRightChild(&Entry->Links))
 288             {
 289                 /* Update its parent link */
 290                 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
 291             }
 292         }
 293         else
 294         {
 295             /* It's not a case match, so we'll delete the actual entry */
 296             SplayLinks = &PrefixTableEntry->Links;
 297
 298             /* Find the root entry */
 299             while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
 300             Entry = CONTAINING_RECORD(SplayLinks,
 301                                       UNICODE_PREFIX_TABLE_ENTRY,
 302                                       Links);
 303
 304             /* Delete the entry and check if the whole tree is gone */
 305             SplayLinks = RtlDelete(&PrefixTableEntry->Links);
 306             if (!SplayLinks)
 307             {
 308                 /* The tree is also gone now, find the entry referencing us */
 309                 RefEntry = Entry->NextPrefixTree;
 310                 while (RefEntry->NextPrefixTree != Entry)
 311                 {
 312                     /* Not this one, move to the next entry */
 313                     RefEntry = RefEntry->NextPrefixTree;
 314                 }
 315
 316                 /* Link them so this entry stops being referenced */
 317                 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
 318             }
 319             else if (&Entry->Links != SplayLinks)
 320             {
 321                 /* The tree is still here, but we got moved to a new one */
 322                 NewEntry = CONTAINING_RECORD(SplayLinks,
 323                                              UNICODE_PREFIX_TABLE_ENTRY,
 324                                              Links);
 325
 326                 /* Find the entry referencing us */
 327                 RefEntry = Entry->NextPrefixTree;
 328                 while (RefEntry->NextPrefixTree != Entry)
 329                 {
 330                     /* Not this one, move to the next entry */
 331                     RefEntry = RefEntry->NextPrefixTree;
 332                 }
 333
 334                 /* Since we got moved, make us the new root entry */
 335                 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
 336
 337                 /* Link us with the entry referencing the old root */
 338                 RefEntry->NextPrefixTree = NewEntry;
 339
 340                 /* And link us with the old tree */
 341                 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
 342
 343                 /* Set the old tree as a child */
 344                 Entry->NodeTypeCode = PFX_NTC_CHILD;
 345                 Entry->NextPrefixTree = NULL;
 346             }
 347         }
 348     }
 349 }
 350
 351 /* EOF */