test: prefix.c Source File

Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

# prefix.c

Go to the documentation of this file.

    00001 /*++
    00002
    00003 Copyright (c) 1989  Microsoft Corporation
    00004
    00005 Module Name:
    00006
    00007     Prefix.c
    00008
    00009 Abstract:
    00010
    00011     This module implements the prefix table utility.  The two structures
    00012     used in a prefix table are the PREFIX_TABLE and PREFIX_TABLE_ENTRY.
    00013     Each table has one prefix table and multiple prefix table entries
    00014     corresponding to each prefix stored in the table.
    00015
    00016     A prefix table is a list of prefix trees, where each tree contains
    00017     the prefixes corresponding to a particular name length (i.e., all
    00018     prefixes of length 1 are stored in one tree, prefixes of length 2
    00019     are stored in another tree, and so forth).  A prefixes name length
    00020     is the number of separate names that appear in the string, and not
    00021     the number of characters in the string (e.g., Length("\alpha\beta") = 2).
    00022
    00023     The elements of each tree are ordered lexicalgraphically (case blind)
    00024     using a splay tree data structure.  If two or more prefixes are identical
    00025     except for case then one of the corresponding table entries is actually
    00026     in the tree, while the other entries are in a circular linked list joined
    00027     with the tree member.
    00028
    00029 Author:
    00030
    00031     Gary Kimura     [GaryKi]    3-Aug-1989
    00032
    00033 Environment:
    00034
    00035     Pure utility routine
    00036
    00037 Revision History:
    00038
    00039     08-Mar-1993    JulieB    Moved Upcase Macro to ntrtlp.h.
    00040
    00041 --*/
    00042
    00043 #include "ntrtlp.h"
    00044
    00045 //
    00046 //  Local procedures and types used only in this package
    00047 //
    00048
    00049 typedef enum _COMPARISON {
    00050     IsLessThan,
    00051     IsPrefix,
    00052     IsEqual,
    00053     IsGreaterThan
    00054 } COMPARISON;
    00055
    00056 CLONG
    00057 ComputeNameLength(
    00058     IN PSTRING Name
    00059     );
    00060
    00061 COMPARISON
    00062 CompareNamesCaseSensitive (
    00063     IN PSTRING Prefix,
    00064     IN PSTRING Name
    00065     );
    00066
    00067 CLONG
    00068 ComputeUnicodeNameLength(
    00069     IN PUNICODE_STRING Name
    00070     );
    00071
    00072 COMPARISON
    00073 CompareUnicodeStrings (
    00074     IN PUNICODE_STRING Prefix,
    00075     IN PUNICODE_STRING Name,
    00076     IN ULONG CaseInsensitiveIndex
    00077     );
    00078
    00079 #if defined(ALLOC_PRAGMA) && defined(NTOS_KERNEL_RUNTIME)
    00080 #pragma alloc_text(PAGE,ComputeNameLength)
    00081 #pragma alloc_text(PAGE,CompareNamesCaseSensitive)
    00082 #pragma alloc_text(PAGE,PfxInitialize)
    00083 #pragma alloc_text(PAGE,PfxInsertPrefix)
    00084 #pragma alloc_text(PAGE,PfxRemovePrefix)
    00085 #pragma alloc_text(PAGE,PfxFindPrefix)
    00086 #pragma alloc_text(PAGE,ComputeUnicodeNameLength)
    00087 #pragma alloc_text(PAGE,CompareUnicodeStrings)
    00088 #pragma alloc_text(PAGE,RtlInitializeUnicodePrefix)
    00089 #pragma alloc_text(PAGE,RtlInsertUnicodePrefix)
    00090 #pragma alloc_text(PAGE,RtlRemoveUnicodePrefix)
    00091 #pragma alloc_text(PAGE,RtlFindUnicodePrefix)
    00092 #pragma alloc_text(PAGE,RtlNextUnicodePrefix)
    00093 #endif
    00094
    00095
    00096 //
    00097 //  The node type codes for the prefix data structures
    00098 //
    00099
    00100 #define RTL_NTC_PREFIX_TABLE             ((CSHORT)0x0200)
    00101 #define RTL_NTC_ROOT                     ((CSHORT)0x0201)
    00102 #define RTL_NTC_INTERNAL                 ((CSHORT)0x0202)
    00103
    00104
    00105 VOID
    00106 PfxInitialize (
    00107     IN PPREFIX_TABLE PrefixTable
    00108     )
    00109
    00110 /*++
    00111
    00112 Routine Description:
    00113
    00114     This routine initializes a prefix table record to the empty state.
    00115
    00116 Arguments:
    00117
    00118     PrefixTable - Supplies the prefix table being initialized
    00119
    00120 Return Value:
    00121
    00122     None.
    00123
    00124 --*/
    00125
    00126 {
    00127     RTL_PAGED_CODE();
    00128
    00129     PrefixTable->NodeTypeCode = RTL_NTC_PREFIX_TABLE;
    00130
    00131     PrefixTable->NameLength = 0;
    00132
    00133     PrefixTable->NextPrefixTree = (PPREFIX_TABLE_ENTRY)PrefixTable;
    00134
    00135     //
    00136     //  return to our caller
    00137     //
    00138
    00139     return;
    00140 }
    00141
    00142
    00143 BOOLEAN
    00144 PfxInsertPrefix (
    00145     IN PPREFIX_TABLE PrefixTable,
    00146     IN PSTRING Prefix,
    00147     IN PPREFIX_TABLE_ENTRY PrefixTableEntry
    00148     )
    00149
    00150 /*++
    00151
    00152 Routine Description:
    00153
    00154     This routine inserts a new prefix into the specified prefix table
    00155
    00156 Arguments:
    00157
    00158     PrefixTable - Supplies the target prefix table
    00159
    00160     Prefix - Supplies the string to be inserted in the prefix table
    00161
    00162     PrefixTableEntry - Supplies the entry to use to insert the prefix
    00163
    00164 Return Value:
    00165
    00166     BOOLEAN - TRUE if the Prefix is not already in the table, and FALSE
    00167         otherwise
    00168
    00169 --*/
    00170
    00171 {
    00172     ULONG PrefixNameLength;
    00173
    00174     PPREFIX_TABLE_ENTRY PreviousTree;
    00175     PPREFIX_TABLE_ENTRY CurrentTree;
    00176     PPREFIX_TABLE_ENTRY NextTree;
    00177
    00178     PPREFIX_TABLE_ENTRY Node;
    00179
    00180     COMPARISON Comparison;
    00181
    00182     RTL_PAGED_CODE();
    00183
    00184     //
    00185     //  Determine the name length of the input string
    00186     //
    00187
    00188     PrefixNameLength = ComputeNameLength(Prefix);
    00189
    00190     //
    00191     //  Setup parts of the prefix table entry that we will always need
    00192     //
    00193
    00194     PrefixTableEntry->NameLength = (CSHORT)PrefixNameLength;
    00195     PrefixTableEntry->Prefix = Prefix;
    00196
    00197     RtlInitializeSplayLinks(&PrefixTableEntry->Links);
    00198
    00199     //
    00200     //  find the corresponding tree, or find where the tree should go
    00201     //
    00202
    00203     PreviousTree = (PPREFIX_TABLE_ENTRY)PrefixTable;
    00204     CurrentTree = PreviousTree->NextPrefixTree;
    00205
    00206     while (CurrentTree->NameLength > (CSHORT)PrefixNameLength) {
    00207
    00208         PreviousTree = CurrentTree;
    00209         CurrentTree = CurrentTree->NextPrefixTree;
    00210
    00211     }
    00212
    00213     //
    00214     //  If the name length of the current tree is not equal to the
    00215     //  prefix name length then the tree does not exist and we need
    00216     //  to make a new tree node.
    00217     //
    00218
    00219     if (CurrentTree->NameLength != (CSHORT)PrefixNameLength) {
    00220
    00221         //
    00222         //  Insert the new prefix entry to the list between
    00223         //  previous and current tree
    00224         //
    00225
    00226         PreviousTree->NextPrefixTree = PrefixTableEntry;
    00227         PrefixTableEntry->NextPrefixTree = CurrentTree;
    00228
    00229         //
    00230         //  And set the node type code
    00231         //
    00232
    00233         PrefixTableEntry->NodeTypeCode = RTL_NTC_ROOT;
    00234
    00235         //
    00236         //  And tell our caller everything worked fine
    00237         //
    00238
    00239         return TRUE;
    00240
    00241     }
    00242
    00243     //
    00244     //  The tree does exist so now search the tree for our
    00245     //  position in it.  We only exit the loop if we've inserted
    00246     //  a new node, and node is left is left pointing to the
    00247     //  tree position
    00248     //
    00249
    00250     Node = CurrentTree;
    00251
    00252     while (TRUE) {
    00253
    00254         //
    00255         //  Compare the prefix in the tree with the prefix we want
    00256         //  to insert
    00257         //
    00258
    00259         Comparison = CompareNamesCaseSensitive(Node->Prefix, Prefix);
    00260
    00261         //
    00262         //  If we do match case sensitive then we cannot add
    00263         //  this prefix so we return false.  Note this is the
    00264         //  only condition where we return false
    00265         //
    00266
    00267         if (Comparison == IsEqual) {
    00268
    00269             return FALSE;
    00270         }
    00271
    00272         //
    00273         //  If the tree prefix is greater than the new prefix then
    00274         //  we go down the left subtree
    00275         //
    00276
    00277         if (Comparison == IsGreaterThan) {
    00278
    00279             //
    00280             //  We want to go down the left subtree, first check to see
    00281             //  if we have a left subtree
    00282             //
    00283
    00284             if (RtlLeftChild(&Node->Links) == NULL) {
    00285
    00286                 //
    00287                 //  there isn't a left child so we insert ourselves as the
    00288                 //  new left child
    00289                 //
    00290
    00291                 PrefixTableEntry->NodeTypeCode = RTL_NTC_INTERNAL;
    00292                 PrefixTableEntry->NextPrefixTree = NULL;
    00293
    00294                 RtlInsertAsLeftChild(&Node->Links, &PrefixTableEntry->Links);
    00295
    00296                 //
    00297                 //  and exit the while loop
    00298                 //
    00299
    00300                 break;
    00301
    00302             } else {
    00303
    00304                 //
    00305                 //  there is a left child so simply go down that path, and
    00306                 //  go back to the top of the loop
    00307                 //
    00308
    00309                 Node = CONTAINING_RECORD( RtlLeftChild(&Node->Links),
    00310                                           PREFIX_TABLE_ENTRY,
    00311                                           Links );
    00312
    00313             }
    00314
    00315         } else {
    00316
    00317             //
    00318             //  The tree prefix is either less than or a proper prefix
    00319             //  of the new string.  We treat both cases a less than when
    00320             //  we do insert.  So we want to go down the right subtree,
    00321             //  first check to see if we have a right subtree
    00322             //
    00323
    00324             if (RtlRightChild(&Node->Links) == NULL) {
    00325
    00326                 //
    00327                 //  These isn't a right child so we insert ourselves as the
    00328                 //  new right child
    00329                 //
    00330
    00331                 PrefixTableEntry->NodeTypeCode = RTL_NTC_INTERNAL;
    00332                 PrefixTableEntry->NextPrefixTree = NULL;
    00333
    00334                 RtlInsertAsRightChild(&Node->Links, &PrefixTableEntry->Links);
    00335
    00336                 //
    00337                 //  and exit the while loop
    00338                 //
    00339
    00340                 break;
    00341
    00342             } else {
    00343
    00344                 //
    00345                 //  there is a right child so simply go down that path, and
    00346                 //  go back to the top of the loop
    00347                 //
    00348
    00349                 Node = CONTAINING_RECORD( RtlRightChild(&Node->Links),
    00350                                           PREFIX_TABLE_ENTRY,
    00351                                           Links );
    00352             }
    00353
    00354         }
    00355
    00356     }
    00357
    00358     //
    00359     //  Now that we've inserted the new node we can splay the tree.
    00360     //  To do this we need to remember how we find this tree in the root
    00361     //  tree list, set the root to be an internal, splay, the tree, and
    00362     //  then setup the new root node.  Note: we cannot splay the prefix table
    00363     //  entry because it might be a case match node so we only splay
    00364     //  the Node variable, which for case match insertions is the
    00365     //  internal node for the case match and for non-case match insertions
    00366     //  the Node variable is the parent node.
    00367     //
    00368
    00369     //
    00370     //  Save a pointer to the next tree, we already have the previous tree
    00371     //
    00372
    00373     NextTree = CurrentTree->NextPrefixTree;
    00374
    00375     //
    00376     //  Reset the current root to be an internal node
    00377     //
    00378
    00379     CurrentTree->NodeTypeCode = RTL_NTC_INTERNAL;
    00380     CurrentTree->NextPrefixTree = NULL;
    00381
    00382     //
    00383     //  Splay the tree and get the root
    00384     //
    00385
    00386     Node = CONTAINING_RECORD(RtlSplay(&Node->Links), PREFIX_TABLE_ENTRY, Links);
    00387
    00388     //
    00389     //  Set the new root's node type code and make it part of the
    00390     //  root tree list
    00391     //
    00392
    00393     Node->NodeTypeCode = RTL_NTC_ROOT;
    00394     PreviousTree->NextPrefixTree = Node;
    00395     Node->NextPrefixTree = NextTree;
    00396
    00397     //
    00398     //  tell our caller everything worked fine
    00399     //
    00400
    00401     return TRUE;
    00402 }
    00403
    00404
    00405 VOID
    00406 PfxRemovePrefix (
    00407     IN PPREFIX_TABLE PrefixTable,
    00408     IN PPREFIX_TABLE_ENTRY PrefixTableEntry
    00409     )
    00410
    00411 /*++
    00412
    00413 Routine Description:
    00414
    00415     This routine removes the indicated prefix table entry from
    00416     the prefix table
    00417
    00418 Arguments:
    00419
    00420     PrefixTable - Supplies the prefix table affected
    00421
    00422     PrefixTableEntry - Supplies the prefix entry to remove
    00423
    00424 Return Value:
    00425
    00426     None.
    00427
    00428 --*/
    00429
    00430 {
    00431     PRTL_SPLAY_LINKS Links;
    00432
    00433     PPREFIX_TABLE_ENTRY Root;
    00434     PPREFIX_TABLE_ENTRY NewRoot;
    00435
    00436     PPREFIX_TABLE_ENTRY PreviousTree;
    00437
    00438     RTL_PAGED_CODE();
    00439
    00440     //
    00441     //  case on the type of node that we are trying to delete
    00442     //
    00443
    00444     switch (PrefixTableEntry->NodeTypeCode) {
    00445
    00446     case RTL_NTC_INTERNAL:
    00447     case RTL_NTC_ROOT:
    00448
    00449         //
    00450         //  The node is internal or root node so we need to delete it from
    00451         //  the tree, but first find the root of the tree
    00452         //
    00453
    00454         Links = &PrefixTableEntry->Links;
    00455
    00456         while (!RtlIsRoot(Links)) {
    00457
    00458             Links = RtlParent(Links);
    00459         }
    00460
    00461         Root = CONTAINING_RECORD( Links, PREFIX_TABLE_ENTRY, Links );
    00462
    00463         //
    00464         //  Now delete the node
    00465         //
    00466
    00467         Links = RtlDelete(&PrefixTableEntry->Links);
    00468
    00469         //
    00470         //  Now see if the tree is deleted
    00471         //
    00472
    00473         if (Links == NULL) {
    00474
    00475             //
    00476             //  The tree is now empty so remove this tree from
    00477             //  the tree list, by first finding the previous tree that
    00478             //  references us
    00479             //
    00480
    00481             PreviousTree = Root->NextPrefixTree;
    00482
    00483             while ( PreviousTree->NextPrefixTree != Root ) {
    00484
    00485                 PreviousTree = PreviousTree->NextPrefixTree;
    00486             }
    00487
    00488             //
    00489             //  We've located the previous tree so now just have it
    00490             //  point around the deleted node
    00491             //
    00492
    00493             PreviousTree->NextPrefixTree = Root->NextPrefixTree;
    00494
    00495             //
    00496             //  and return the our caller
    00497             //
    00498
    00499             return;
    00500         }
    00501
    00502         //
    00503         //  The tree is not deleted but see if we changed roots
    00504         //
    00505
    00506         if (&Root->Links != Links) {
    00507
    00508             //
    00509             //  Get a pointer to the new root
    00510             //
    00511
    00512             NewRoot = CONTAINING_RECORD(Links, PREFIX_TABLE_ENTRY, Links);
    00513
    00514             //
    00515             //  We changed root so we better need to make the new
    00516             //  root part of the prefix data structure, by
    00517             //  first finding the previous tree that
    00518             //  references us
    00519             //
    00520
    00521             PreviousTree = Root->NextPrefixTree;
    00522
    00523             while ( PreviousTree->NextPrefixTree != Root ) {
    00524
    00525                 PreviousTree = PreviousTree->NextPrefixTree;
    00526             }
    00527
    00528             //
    00529             //  Set the new root
    00530             //
    00531
    00532             NewRoot->NodeTypeCode = RTL_NTC_ROOT;
    00533
    00534             PreviousTree->NextPrefixTree = NewRoot;
    00535             NewRoot->NextPrefixTree = Root->NextPrefixTree;
    00536
    00537             //
    00538             //  Set the old root to be an internal node
    00539             //
    00540
    00541             Root->NodeTypeCode = RTL_NTC_INTERNAL;
    00542
    00543             Root->NextPrefixTree = NULL;
    00544
    00545             //
    00546             //  And return to our caller
    00547             //
    00548
    00549             return;
    00550         }
    00551
    00552         //
    00553         //  We didn't change roots so everything is fine and we can
    00554         //  simply return to our caller
    00555         //
    00556
    00557         return;
    00558
    00559     default:
    00560
    00561         //
    00562         //  If we get here then there was an error and the node type
    00563         //  code is unknown
    00564         //
    00565
    00566         return;
    00567     }
    00568 }
    00569
    00570
    00571 PPREFIX_TABLE_ENTRY
    00572 PfxFindPrefix (
    00573     IN PPREFIX_TABLE PrefixTable,
    00574     IN PSTRING FullName
    00575     )
    00576
    00577 /*++
    00578
    00579 Routine Description:
    00580
    00581     This routine finds if a full name has a prefix in a prefix table.
    00582     It returns a pointer to the largest proper prefix found if one exists.
    00583
    00584 Arguments:
    00585
    00586     PrefixTable - Supplies the prefix table to search
    00587
    00588     FullString - Supplies the name to search for
    00589
    00590 Return Value:
    00591
    00592     PPREFIX_TABLE_ENTRY - a pointer to the longest prefix found if one
    00593         exists, and NULL otherwise
    00594
    00595 --*/
    00596
    00597 {
    00598     CLONG NameLength;
    00599
    00600     PPREFIX_TABLE_ENTRY PreviousTree;
    00601     PPREFIX_TABLE_ENTRY CurrentTree;
    00602     PPREFIX_TABLE_ENTRY NextTree;
    00603
    00604     PRTL_SPLAY_LINKS Links;
    00605
    00606     PPREFIX_TABLE_ENTRY Node;
    00607
    00608     COMPARISON Comparison;
    00609
    00610     RTL_PAGED_CODE();
    00611
    00612     //
    00613     //  Determine the name length of the input string
    00614     //
    00615
    00616     NameLength = ComputeNameLength(FullName);
    00617
    00618     //
    00619     //  Locate the first tree that can contain a prefix
    00620     //
    00621
    00622     PreviousTree = (PPREFIX_TABLE_ENTRY)PrefixTable;
    00623     CurrentTree = PreviousTree->NextPrefixTree;
    00624
    00625     while (CurrentTree->NameLength > (CSHORT)NameLength) {
    00626
    00627         PreviousTree = CurrentTree;
    00628         CurrentTree = CurrentTree->NextPrefixTree;
    00629     }
    00630
    00631     //
    00632     //  Now search for a prefix until we find one or until we exhaust
    00633     //  the prefix trees
    00634     //
    00635
    00636     while (CurrentTree->NameLength > 0) {
    00637
    00638         Links = &CurrentTree->Links;
    00639
    00640         while (Links != NULL) {
    00641
    00642             Node = CONTAINING_RECORD(Links, PREFIX_TABLE_ENTRY, Links);
    00643
    00644             //
    00645             //  Compare the prefix in the tree with the full name
    00646             //
    00647
    00648             Comparison = CompareNamesCaseSensitive(Node->Prefix, FullName);
    00649
    00650             //
    00651             //  See if they don't match
    00652             //
    00653
    00654             if (Comparison == IsGreaterThan) {
    00655
    00656                 //
    00657                 //  The prefix is greater than the full name
    00658                 //  so we go down the left child
    00659                 //
    00660
    00661                 Links = RtlLeftChild(Links);
    00662
    00663                 //
    00664                 //  And continue searching down this tree
    00665                 //
    00666
    00667             } else if (Comparison == IsLessThan) {
    00668
    00669                 //
    00670                 //  The prefix is less than the full name
    00671                 //  so we go down the right child
    00672                 //
    00673
    00674                 Links = RtlRightChild(Links);
    00675
    00676                 //
    00677                 //  And continue searching down this tree
    00678                 //
    00679
    00680             } else {
    00681
    00682                 //
    00683                 //  We found it.
    00684                 //
    00685                 //  Now that we've located the node we can splay the tree.
    00686                 //  To do this we need to remember how we find this tree in the root
    00687                 //  tree list, set the root to be an internal, splay, the tree, and
    00688                 //  then setup the new root node.
    00689                 //
    00690
    00691                 if (Node->NodeTypeCode == RTL_NTC_INTERNAL) {
    00692
    00693                     //DbgPrint("PrefixTable  = %08lx\n", PrefixTable);
    00694                     //DbgPrint("Node         = %08lx\n", Node);
    00695                     //DbgPrint("CurrentTree  = %08lx\n", CurrentTree);
    00696                     //DbgPrint("PreviousTree = %08lx\n", PreviousTree);
    00697                     //DbgBreakPoint();
    00698
    00699                     //
    00700                     //  Save a pointer to the next tree, we already have the previous tree
    00701                     //
    00702
    00703                     NextTree = CurrentTree->NextPrefixTree;
    00704
    00705                     //
    00706                     //  Reset the current root to be an internal node
    00707                     //
    00708
    00709                     CurrentTree->NodeTypeCode = RTL_NTC_INTERNAL;
    00710                     CurrentTree->NextPrefixTree = NULL;
    00711
    00712                     //
    00713                     //  Splay the tree and get the root
    00714                     //
    00715
    00716                     Node = CONTAINING_RECORD(RtlSplay(&Node->Links), PREFIX_TABLE_ENTRY, Links);
    00717
    00718                     //
    00719                     //  Set the new root's node type code and make it part of the
    00720                     //  root tree list
    00721                     //
    00722
    00723                     Node->NodeTypeCode = RTL_NTC_ROOT;
    00724                     PreviousTree->NextPrefixTree = Node;
    00725                     Node->NextPrefixTree = NextTree;
    00726                 }
    00727
    00728                 return Node;
    00729             }
    00730         }
    00731
    00732         //
    00733         //  This tree is done so now find the next tree
    00734         //
    00735
    00736         PreviousTree = CurrentTree;
    00737         CurrentTree = CurrentTree->NextPrefixTree;
    00738     }
    00739
    00740     //
    00741     //  We sesarched everywhere and didn't find a prefix so tell the
    00742     //  caller none was found
    00743     //
    00744
    00745     return NULL;
    00746 }
    00747
    00748
    00749 CLONG
    00750 ComputeNameLength(
    00751     IN PSTRING Name
    00752     )
    00753
    00754 /*++
    00755
    00756 Routine Description:
    00757
    00758     This routine counts the number of names appearing in the input string.
    00759     It does this by simply counting the number of backslashes in the string.
    00760     To handle ill-formed names (i.e., names that do not contain a backslash)
    00761     this routine really returns the number of backslashes plus 1.
    00762
    00763 Arguments:
    00764
    00765     Name - Supplies the input name to examine
    00766
    00767 Returns Value:
    00768
    00769     CLONG - the number of names in the input string
    00770
    00771 --*/
    00772
    00773 {
    00774     ULONG NameLength;
    00775     ULONG i;
    00776     ULONG Count;
    00777
    00778     extern PUSHORT NlsLeadByteInfo;  // Lead byte info. for ACP ( nlsxlat.c )
    00779     extern BOOLEAN NlsMbCodePageTag;
    00780
    00781     RTL_PAGED_CODE();
    00782
    00783     //
    00784     //  Save the name length, this should make the compiler be able to
    00785     //  optimize not having to reload the length each time
    00786     //
    00787
    00788     NameLength = Name->Length - 1;
    00789
    00790     //
    00791     //  Now loop through the input string counting back slashes
    00792     //
    00793
    00794     if (NlsMbCodePageTag) {
    00795
    00796         //
    00797         // ComputeNameLength() skip DBCS character when counting '\'
    00798         //
    00799
    00800         for (i = 0, Count = 1; i < NameLength; ) {
    00801
    00802             if (NlsLeadByteInfo[(UCHAR)Name->Buffer[i]]) {
    00803
    00804                 i += 2;
    00805
    00806             } else {
    00807
    00808                 if (Name->Buffer[i] == '\\') {
    00809
    00810                     Count += 1;
    00811                 }
    00812
    00813                 i += 1;
    00814             }
    00815         }
    00816
    00817     } else {
    00818
    00819         for (i = 0, Count = 1; i < NameLength; i += 1) {
    00820
    00821             //
    00822             //  check for a back slash
    00823             //
    00824
    00825             if (Name->Buffer[i] == '\\') {
    00826
    00827                 Count += 1;
    00828             }
    00829         }
    00830     }
    00831
    00832     //
    00833     //  return the number of back slashes we found
    00834     //
    00835
    00836     //DbgPrint("ComputeNameLength(%s) = %x\n", Name->Buffer, Count);
    00837
    00838     return Count;
    00839 }
    00840
    00841
    00842 COMPARISON
    00843 CompareNamesCaseSensitive (
    00844     IN PSTRING Prefix,
    00845     IN PSTRING Name
    00846     )
    00847
    00848 /*++
    00849
    00850 Routine Description:
    00851
    00852     This routine takes a prefix string and a full name string and determines
    00853     if the prefix string is a proper prefix of the name string (case sensitive)
    00854
    00855 Arguments:
    00856
    00857     Prefix - Supplies the input prefix string
    00858
    00859     Name - Supplies the full name input string
    00860
    00861 Return Value:
    00862
    00863     COMPARISON - returns
    00864
    00865         IsLessThan    if Prefix < Name lexicalgraphically,
    00866         IsPrefix      if Prefix is a proper prefix of Name
    00867         IsEqual       if Prefix is equal to Name, and
    00868         IsGreaterThan if Prefix > Name lexicalgraphically
    00869
    00870 --*/
    00871
    00872 {
    00873     ULONG PrefixLength;
    00874     ULONG NameLength;
    00875     ULONG MinLength;
    00876     ULONG i;
    00877
    00878     UCHAR PrefixChar;
    00879     UCHAR NameChar;
    00880
    00881     extern PUSHORT NlsLeadByteInfo;  // Lead byte info. for ACP ( nlsxlat.c )
    00882     extern BOOLEAN NlsMbCodePageTag;
    00883
    00884     RTL_PAGED_CODE();
    00885
    00886     //DbgPrint("CompareNamesCaseSensitive(\"%s\", \"%s\") = ", Prefix->Buffer, Name->Buffer);
    00887
    00888     //
    00889     //  Save the length of the prefix and name string, this should allow
    00890     //  the compiler to not need to reload the length through a pointer every
    00891     //  time we need their values
    00892     //
    00893
    00894     PrefixLength = Prefix->Length;
    00895     NameLength = Name->Length;
    00896
    00897     //
    00898     //  Special case the situation where the prefix string is simply "\" and
    00899     //  the name starts with an "\"
    00900     //
    00901
    00902     if ((Prefix->Length == 1) && (Prefix->Buffer[0] == '\\') &&
    00903         (Name->Length > 1) && (Name->Buffer[0] == '\\')) {
    00904         //DbgPrint("IsPrefix\n");
    00905         return IsPrefix;
    00906     }
    00907
    00908     //
    00909     //  Figure out the minimum of the two lengths
    00910     //
    00911
    00912     MinLength = (PrefixLength < NameLength ? PrefixLength : NameLength);
    00913
    00914     //
    00915     //  Loop through looking at all of the characters in both strings
    00916     //  testing for equalilty, less than, and greater than
    00917     //
    00918
    00919     i = (ULONG) RtlCompareMemory( &Prefix->Buffer[0], &Name->Buffer[0], MinLength );
    00920
    00921     if (i < MinLength) {
    00922
    00923         UCHAR c;
    00924
    00925         //
    00926         //  Get both characters to examine and keep their case
    00927         //
    00928
    00929         PrefixChar = ((c = Prefix->Buffer[i]) == '\\' ? (CHAR)0 : c);
    00930         NameChar   = ((c = Name->Buffer[i])   == '\\' ? (CHAR)0 : c);
    00931
    00932         //
    00933         //  Unfortunately life is not so easy in DBCS land.
    00934         //
    00935
    00936         if (NlsMbCodePageTag) {
    00937
    00938             //
    00939             // CompareNamesCaseSensitive(): check backslash in trailing bytes
    00940             //
    00941
    00942             if (Prefix->Buffer[i] == '\\') {
    00943
    00944                 ULONG j;
    00945                 extern PUSHORT   NlsLeadByteInfo;  // Lead byte info. for ACP ( nlsxlat.c )
    00946
    00947                 for (j = 0; j < i;) {
    00948
    00949                     j += NlsLeadByteInfo[(UCHAR)Prefix->Buffer[j]] ? 2 : 1;
    00950                 }
    00951
    00952                 if (j != i) {
    00953
    00954                     PrefixChar = '\\';
    00955                     //DbgPrint("RTL:CompareNamesCaseSensitive encountered a fake backslash!\n");
    00956                 }
    00957             }
    00958
    00959             if (Name->Buffer[i] == '\\') {
    00960
    00961                 ULONG j;
    00962                 extern PUSHORT   NlsLeadByteInfo;  // Lead byte info. for ACP ( nlsxlat.c )
    00963
    00964                 for (j = 0; j < i;) {
    00965
    00966                     j += NlsLeadByteInfo[(UCHAR)Name->Buffer[j]] ? 2 : 1;
    00967                 }
    00968
    00969                 if (j != i) {
    00970
    00971                     NameChar = '\\';
    00972                     //DbgPrint("RTL:CompareNamesCaseSensitive encountered a fake backslash!\n");
    00973                 }
    00974             }
    00975         }
    00976
    00977         //
    00978         //  Now compare the characters
    00979         //
    00980
    00981         if (PrefixChar < NameChar) {
    00982
    00983             return IsLessThan;
    00984
    00985         } else if (PrefixChar > NameChar) {
    00986
    00987             return IsGreaterThan;
    00988         }
    00989     }
    00990
    00991     //
    00992     //  They match upto the minimum length so now figure out the largest string
    00993     //  and see if one is a proper prefix of the other
    00994     //
    00995
    00996     if (PrefixLength < NameLength) {
    00997
    00998         //
    00999         //  The prefix string is shorter so if it is a proper prefix we
    01000         //  return prefix otherwise we return less than (e.g., "\a" < "\ab")
    01001         //
    01002
    01003         if (Name->Buffer[PrefixLength] == '\\') {
    01004
    01005             return IsPrefix;
    01006
    01007         } else {
    01008
    01009             return IsLessThan;
    01010         }
    01011
    01012     } else if (PrefixLength > NameLength) {
    01013
    01014         //
    01015         //  The Prefix string is longer so we say that the prefix is
    01016         //  greater than the name (e.g., "\ab" > "\a")
    01017         //
    01018
    01019         return IsGreaterThan;
    01020
    01021     } else {
    01022
    01023         //
    01024         //  They lengths are equal so the strings are equal
    01025         //
    01026
    01027         return IsEqual;
    01028     }
    01029 }
    01030
    01031
    01032 //
    01033 //  The node type codes for the prefix data structures
    01034 //
    01035
    01036 #define RTL_NTC_UNICODE_PREFIX_TABLE     ((CSHORT)0x0800)
    01037 #define RTL_NTC_UNICODE_ROOT             ((CSHORT)0x0801)
    01038 #define RTL_NTC_UNICODE_INTERNAL         ((CSHORT)0x0802)
    01039 #define RTL_NTC_UNICODE_CASE_MATCH       ((CSHORT)0x0803)
    01040
    01041
    01042 VOID
    01043 RtlInitializeUnicodePrefix (
    01044     IN PUNICODE_PREFIX_TABLE PrefixTable
    01045     )
    01046
    01047 /*++
    01048
    01049 Routine Description:
    01050
    01051     This routine initializes a unicode prefix table record to the empty state.
    01052
    01053 Arguments:
    01054
    01055     PrefixTable - Supplies the prefix table being initialized
    01056
    01057 Return Value:
    01058
    01059     None.
    01060
    01061 --*/
    01062
    01063 {
    01064     RTL_PAGED_CODE();
    01065
    01066     PrefixTable->NodeTypeCode = RTL_NTC_UNICODE_PREFIX_TABLE;
    01067     PrefixTable->NameLength = 0;
    01068     PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
    01069     PrefixTable->LastNextEntry = NULL;
    01070
    01071     //
    01072     //  return to our caller
    01073     //
    01074
    01075     return;
    01076 }
    01077
    01078
    01079 BOOLEAN
    01080 RtlInsertUnicodePrefix (
    01081     IN PUNICODE_PREFIX_TABLE PrefixTable,
    01082     IN PUNICODE_STRING Prefix,
    01083     IN PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
    01084     )
    01085
    01086 /*++
    01087
    01088 Routine Description:
    01089
    01090     This routine inserts a new unicode prefix into the specified prefix table
    01091
    01092 Arguments:
    01093
    01094     PrefixTable - Supplies the target prefix table
    01095
    01096     Prefix - Supplies the string to be inserted in the prefix table
    01097
    01098     PrefixTableEntry - Supplies the entry to use to insert the prefix
    01099
    01100 Return Value:
    01101
    01102     BOOLEAN - TRUE if the Prefix is not already in the table, and FALSE
    01103         otherwise
    01104
    01105 --*/
    01106
    01107 {
    01108     ULONG PrefixNameLength;
    01109
    01110     PUNICODE_PREFIX_TABLE_ENTRY PreviousTree;
    01111     PUNICODE_PREFIX_TABLE_ENTRY CurrentTree;
    01112     PUNICODE_PREFIX_TABLE_ENTRY NextTree;
    01113
    01114     PUNICODE_PREFIX_TABLE_ENTRY Node;
    01115
    01116     COMPARISON Comparison;
    01117
    01118     RTL_PAGED_CODE();
    01119
    01120     //
    01121     //  Determine the name length of the input string
    01122     //
    01123
    01124     PrefixNameLength = ComputeUnicodeNameLength(Prefix);
    01125
    01126     //
    01127     //  Setup parts of the prefix table entry that we will always need
    01128     //
    01129
    01130     PrefixTableEntry->NameLength = (CSHORT)PrefixNameLength;
    01131     PrefixTableEntry->Prefix = Prefix;
    01132
    01133     RtlInitializeSplayLinks(&PrefixTableEntry->Links);
    01134
    01135     //
    01136     //  find the corresponding tree, or find where the tree should go
    01137     //
    01138
    01139     PreviousTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
    01140     CurrentTree = PreviousTree->NextPrefixTree;
    01141
    01142     while (CurrentTree->NameLength > (CSHORT)PrefixNameLength) {
    01143
    01144         PreviousTree = CurrentTree;
    01145         CurrentTree = CurrentTree->NextPrefixTree;
    01146     }
    01147
    01148     //
    01149     //  If the name length of the current tree is not equal to the
    01150     //  prefix name length then the tree does not exist and we need
    01151     //  to make a new tree node.
    01152     //
    01153
    01154     if (CurrentTree->NameLength != (CSHORT)PrefixNameLength) {
    01155
    01156         //
    01157         //  Insert the new prefix entry to the list between
    01158         //  previous and current tree
    01159         //
    01160
    01161         PreviousTree->NextPrefixTree = PrefixTableEntry;
    01162         PrefixTableEntry->NextPrefixTree = CurrentTree;
    01163
    01164         //
    01165         //  And set the node type code, case match for the root tree node
    01166         //
    01167
    01168         PrefixTableEntry->NodeTypeCode = RTL_NTC_UNICODE_ROOT;
    01169         PrefixTableEntry->CaseMatch = PrefixTableEntry;
    01170
    01171         //
    01172         //  And tell our caller everything worked fine
    01173         //
    01174
    01175         return TRUE;
    01176     }
    01177
    01178     //
    01179     //  The tree does exist so now search the tree for our
    01180     //  position in it.  We only exit the loop if we've inserted
    01181     //  a new node, and node is left is left pointing to the
    01182     //  tree position
    01183     //
    01184
    01185     Node = CurrentTree;
    01186
    01187     while (TRUE) {
    01188
    01189         //
    01190         //  Compare the prefix in the tree with the prefix we want
    01191         //  to insert.  Do the compare case blind
    01192         //
    01193
    01194         Comparison = CompareUnicodeStrings(Node->Prefix, Prefix, 0);
    01195
    01196         //
    01197         //  If they are equal then this node gets added as a case
    01198         //  match, provided it doesn't case sensitive match anyone
    01199         //
    01200
    01201         if (Comparison == IsEqual) {
    01202
    01203             PUNICODE_PREFIX_TABLE_ENTRY Next;
    01204
    01205             //
    01206             //  Loop through the case match list checking to see if we
    01207             //  match case sensitive with anyone.  Get the first node
    01208             //
    01209
    01210             Next = Node;
    01211
    01212             //
    01213             //  And loop checking each node until we're back to where
    01214             //  we started
    01215             //
    01216
    01217             do {
    01218
    01219                 //
    01220                 //  If we do match case sensitive then we cannot add
    01221                 //  this prefix so we return false.  Note this is the
    01222                 //  only condition where we return false
    01223                 //
    01224
    01225                 if (CompareUnicodeStrings(Next->Prefix, Prefix, MAXULONG) == IsEqual) {
    01226
    01227                     return FALSE;
    01228                 }
    01229
    01230                 //
    01231                 //  Get the next node in the case match list
    01232                 //
    01233
    01234                 Next = Next->CaseMatch;
    01235
    01236                 //
    01237                 //  And continue looping until we're back where we started
    01238                 //
    01239
    01240             } while ( Next != Node );
    01241
    01242             //
    01243             //  We've searched the case match and didn't find an exact match
    01244             //  so we can insert this node in the case match list
    01245             //
    01246
    01247             PrefixTableEntry->NodeTypeCode = RTL_NTC_UNICODE_CASE_MATCH;
    01248             PrefixTableEntry->NextPrefixTree = NULL;
    01249
    01250             PrefixTableEntry->CaseMatch = Node->CaseMatch;
    01251             Node->CaseMatch = PrefixTableEntry;
    01252
    01253             //
    01254             //  And exit out of the while loop
    01255             //
    01256
    01257             break;
    01258         }
    01259
    01260         //
    01261         //  If the tree prefix is greater than the new prefix then
    01262         //  we go down the left subtree
    01263         //
    01264
    01265         if (Comparison == IsGreaterThan) {
    01266
    01267             //
    01268             //  We want to go down the left subtree, first check to see
    01269             //  if we have a left subtree
    01270             //
    01271
    01272             if (RtlLeftChild(&Node->Links) == NULL) {
    01273
    01274                 //
    01275                 //  there isn't a left child so we insert ourselves as the
    01276                 //  new left child
    01277                 //
    01278
    01279                 PrefixTableEntry->NodeTypeCode = RTL_NTC_UNICODE_INTERNAL;
    01280                 PrefixTableEntry->NextPrefixTree = NULL;
    01281                 PrefixTableEntry->CaseMatch = PrefixTableEntry;
    01282
    01283                 RtlInsertAsLeftChild(&Node->Links, &PrefixTableEntry->Links);
    01284
    01285                 //
    01286                 //  and exit the while loop
    01287                 //
    01288
    01289                 break;
    01290
    01291             } else {
    01292
    01293                 //
    01294                 //  there is a left child so simply go down that path, and
    01295                 //  go back to the top of the loop
    01296                 //
    01297
    01298                 Node = CONTAINING_RECORD( RtlLeftChild(&Node->Links),
    01299                                           UNICODE_PREFIX_TABLE_ENTRY,
    01300                                           Links );
    01301             }
    01302
    01303         } else {
    01304
    01305             //
    01306             //  The tree prefix is either less than or a proper prefix
    01307             //  of the new string.  We treat both cases a less than when
    01308             //  we do insert.  So we want to go down the right subtree,
    01309             //  first check to see if we have a right subtree
    01310             //
    01311
    01312             if (RtlRightChild(&Node->Links) == NULL) {
    01313
    01314                 //
    01315                 //  These isn't a right child so we insert ourselves as the
    01316                 //  new right child
    01317                 //
    01318
    01319                 PrefixTableEntry->NodeTypeCode = RTL_NTC_UNICODE_INTERNAL;
    01320                 PrefixTableEntry->NextPrefixTree = NULL;
    01321                 PrefixTableEntry->CaseMatch = PrefixTableEntry;
    01322
    01323                 RtlInsertAsRightChild(&Node->Links, &PrefixTableEntry->Links);
    01324
    01325                 //
    01326                 //  and exit the while loop
    01327                 //
    01328
    01329                 break;
    01330
    01331             } else {
    01332
    01333                 //
    01334                 //  there is a right child so simply go down that path, and
    01335                 //  go back to the top of the loop
    01336                 //
    01337
    01338                 Node = CONTAINING_RECORD( RtlRightChild(&Node->Links),
    01339                                           UNICODE_PREFIX_TABLE_ENTRY,
    01340                                           Links );
    01341             }
    01342         }
    01343     }
    01344
    01345     //
    01346     //  Now that we've inserted the new node we can splay the tree.
    01347     //  To do this we need to remember how we find this tree in the root
    01348     //  tree list, set the root to be an internal, splay, the tree, and
    01349     //  then setup the new root node.  Note: we cannot splay the prefix table
    01350     //  entry because it might be a case match node so we only splay
    01351     //  the Node variable, which for case match insertions is the
    01352     //  internal node for the case match and for non-case match insertions
    01353     //  the Node variable is the parent node.
    01354     //
    01355
    01356     //
    01357     //  Save a pointer to the next tree, we already have the previous tree
    01358     //
    01359
    01360     NextTree = CurrentTree->NextPrefixTree;
    01361
    01362     //
    01363     //  Reset the current root to be an internal node
    01364     //
    01365
    01366     CurrentTree->NodeTypeCode = RTL_NTC_UNICODE_INTERNAL;
    01367     CurrentTree->NextPrefixTree = NULL;
    01368
    01369     //
    01370     //  Splay the tree and get the root
    01371     //
    01372
    01373     Node = CONTAINING_RECORD(RtlSplay(&Node->Links), UNICODE_PREFIX_TABLE_ENTRY, Links);
    01374
    01375     //
    01376     //  Set the new root's node type code and make it part of the
    01377     //  root tree list
    01378     //
    01379
    01380     Node->NodeTypeCode = RTL_NTC_UNICODE_ROOT;
    01381     PreviousTree->NextPrefixTree = Node;
    01382     Node->NextPrefixTree = NextTree;
    01383
    01384     //
    01385     //  tell our caller everything worked fine
    01386     //
    01387
    01388     return TRUE;
    01389 }
    01390
    01391
    01392 VOID
    01393 RtlRemoveUnicodePrefix (
    01394     IN PUNICODE_PREFIX_TABLE PrefixTable,
    01395     IN PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry
    01396     )
    01397
    01398 /*++
    01399
    01400 Routine Description:
    01401
    01402     This routine removes the indicated prefix table entry from
    01403     the prefix table
    01404
    01405 Arguments:
    01406
    01407     PrefixTable - Supplies the prefix table affected
    01408
    01409     PrefixTableEntry - Supplies the prefix entry to remove
    01410
    01411 Return Value:
    01412
    01413     None.
    01414
    01415 --*/
    01416
    01417 {
    01418     PUNICODE_PREFIX_TABLE_ENTRY PreviousCaseMatch;
    01419
    01420     PRTL_SPLAY_LINKS Links;
    01421
    01422     PUNICODE_PREFIX_TABLE_ENTRY Root;
    01423     PUNICODE_PREFIX_TABLE_ENTRY NewRoot;
    01424
    01425     PUNICODE_PREFIX_TABLE_ENTRY PreviousTree;
    01426
    01427     RTL_PAGED_CODE();
    01428
    01429     //
    01430     //  Wipe out the next last entry field of the prefix table
    01431     //
    01432
    01433     PrefixTable->LastNextEntry = NULL;
    01434
    01435     //
    01436     //  case on the type of node that we are trying to delete
    01437     //
    01438
    01439     switch (PrefixTableEntry->NodeTypeCode) {
    01440
    01441     case RTL_NTC_UNICODE_CASE_MATCH:
    01442
    01443         //
    01444         //  The prefix entry is a case match record so
    01445         //  we only need to remove it from the case match list.
    01446         //  Locate the previous PrefixTableEntry that reference this
    01447         //  case match record
    01448         //
    01449
    01450         PreviousCaseMatch = PrefixTableEntry->CaseMatch;
    01451
    01452         while ( PreviousCaseMatch->CaseMatch != PrefixTableEntry ) {
    01453
    01454              PreviousCaseMatch = PreviousCaseMatch->CaseMatch;
    01455         }
    01456
    01457         //
    01458         //  Now that we have the previous record just have it point
    01459         //  around the case match that is being deleted
    01460         //
    01461
    01462         PreviousCaseMatch->CaseMatch = PrefixTableEntry->CaseMatch;
    01463
    01464         //
    01465         //  And return to our caller
    01466         //
    01467
    01468         return;
    01469
    01470     case RTL_NTC_UNICODE_INTERNAL:
    01471     case RTL_NTC_UNICODE_ROOT:
    01472
    01473         //
    01474         //  The prefix entry is an internal/root node so check to see if it
    01475         //  has any case match nodes with it
    01476         //
    01477
    01478         if (PrefixTableEntry->CaseMatch != PrefixTableEntry) {
    01479
    01480             //
    01481             //  There is at least one case match that goes with this
    01482             //  node, so we need to make the next case match the
    01483             //  new node and remove this node.
    01484             //  Locate the previous prefix table entry that references this
    01485             //  case match record
    01486             //
    01487
    01488             PreviousCaseMatch = PrefixTableEntry->CaseMatch;
    01489
    01490             while ( PreviousCaseMatch->CaseMatch != PrefixTableEntry ) {
    01491
    01492                 PreviousCaseMatch = PreviousCaseMatch->CaseMatch;
    01493             }
    01494
    01495             //
    01496             //  Now that we have the previous record just have it point
    01497             //  around the node being deleted
    01498             //
    01499
    01500             PreviousCaseMatch->CaseMatch = PrefixTableEntry->CaseMatch;
    01501
    01502             //
    01503             //  Now make the previous case match in the new node
    01504             //
    01505
    01506             PreviousCaseMatch->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
    01507             PreviousCaseMatch->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
    01508             PreviousCaseMatch->Links = PrefixTableEntry->Links;
    01509
    01510             //
    01511             //  Now take care of the back pointers to this new internal
    01512             //  node in the splay tree, first do the parent's pointer to us.
    01513             //
    01514
    01515             if (RtlIsRoot(&PrefixTableEntry->Links)) {
    01516
    01517                 //
    01518                 //  This is the root so make this new node the root
    01519                 //
    01520
    01521                 PreviousCaseMatch->Links.Parent = &PreviousCaseMatch->Links;
    01522
    01523                 //
    01524                 //  Fix up the root tree list, by first finding the previous
    01525                 //  pointer to us
    01526
    01527                 PreviousTree = PrefixTableEntry->NextPrefixTree;
    01528
    01529                 while ( PreviousTree->NextPrefixTree != PrefixTableEntry ) {
    01530
    01531                     PreviousTree = PreviousTree->NextPrefixTree;
    01532                 }
    01533
    01534                 //
    01535                 //  We've located the previous tree so now have the previous
    01536                 //  tree point to our new root
    01537                 //
    01538
    01539                 PreviousTree->NextPrefixTree = PreviousCaseMatch;
    01540
    01541             } else if (RtlIsLeftChild(&PrefixTableEntry->Links)) {
    01542
    01543                 //
    01544                 //  The node was the left child so make the new node the
    01545                 //  left child
    01546                 //
    01547
    01548                 RtlParent(&PrefixTableEntry->Links)->LeftChild = &PreviousCaseMatch->Links;
    01549
    01550             } else {
    01551
    01552                 //
    01553                 //  The node was the right child so make the new node the
    01554                 //  right child
    01555                 //
    01556
    01557                 RtlParent(&PrefixTableEntry->Links)->RightChild = &PreviousCaseMatch->Links;
    01558             }
    01559
    01560             //
    01561             //  Now update the parent pointer for our new children
    01562             //
    01563
    01564             if (RtlLeftChild(&PreviousCaseMatch->Links) != NULL) {
    01565
    01566                 RtlLeftChild(&PreviousCaseMatch->Links)->Parent = &PreviousCaseMatch->Links;
    01567             }
    01568
    01569             if (RtlRightChild(&PreviousCaseMatch->Links) != NULL) {
    01570
    01571                 RtlRightChild(&PreviousCaseMatch->Links)->Parent = &PreviousCaseMatch->Links;
    01572             }
    01573
    01574             //
    01575             //  And return to our caller
    01576             //
    01577
    01578             return;
    01579         }
    01580
    01581         //
    01582         //  The node is internal or root node and does not have any case match
    01583         //  nodes so we need to delete it from the tree, but first find
    01584         //  the root of the tree
    01585         //
    01586
    01587         Links = &PrefixTableEntry->Links;
    01588
    01589         while (!RtlIsRoot(Links)) {
    01590
    01591             Links = RtlParent(Links);
    01592         }
    01593
    01594         Root = CONTAINING_RECORD( Links, UNICODE_PREFIX_TABLE_ENTRY, Links );
    01595
    01596         //
    01597         //  Now delete the node
    01598         //
    01599
    01600         Links = RtlDelete(&PrefixTableEntry->Links);
    01601
    01602         //
    01603         //  Now see if the tree is deleted
    01604         //
    01605
    01606         if (Links == NULL) {
    01607
    01608             //
    01609             //  The tree is now empty so remove this tree from
    01610             //  the tree list, by first finding the previous tree that
    01611             //  references us
    01612             //
    01613
    01614             PreviousTree = Root->NextPrefixTree;
    01615
    01616             while ( PreviousTree->NextPrefixTree != Root ) {
    01617
    01618                 PreviousTree = PreviousTree->NextPrefixTree;
    01619             }
    01620
    01621             //
    01622             //  We've located the previous tree so now just have it
    01623             //  point around the deleted node
    01624             //
    01625
    01626             PreviousTree->NextPrefixTree = Root->NextPrefixTree;
    01627
    01628             //
    01629             //  and return the our caller
    01630             //
    01631
    01632             return;
    01633         }
    01634
    01635         //
    01636         //  The tree is not deleted but see if we changed roots
    01637         //
    01638
    01639         if (&Root->Links != Links) {
    01640
    01641             //
    01642             //  Get a pointer to the new root
    01643             //
    01644
    01645             NewRoot = CONTAINING_RECORD(Links, UNICODE_PREFIX_TABLE_ENTRY, Links);
    01646
    01647             //
    01648             //  We changed root so we better need to make the new
    01649             //  root part of the prefix data structure, by
    01650             //  first finding the previous tree that
    01651             //  references us
    01652             //
    01653
    01654             PreviousTree = Root->NextPrefixTree;
    01655
    01656             while ( PreviousTree->NextPrefixTree != Root ) {
    01657
    01658                 PreviousTree = PreviousTree->NextPrefixTree;
    01659             }
    01660
    01661             //
    01662             //  Set the new root
    01663             //
    01664
    01665             NewRoot->NodeTypeCode = RTL_NTC_UNICODE_ROOT;
    01666
    01667             PreviousTree->NextPrefixTree = NewRoot;
    01668             NewRoot->NextPrefixTree = Root->NextPrefixTree;
    01669
    01670             //
    01671             //  Set the old root to be an internal node
    01672             //
    01673
    01674             Root->NodeTypeCode = RTL_NTC_UNICODE_INTERNAL;
    01675
    01676             Root->NextPrefixTree = NULL;
    01677
    01678             //
    01679             //  And return to our caller
    01680             //
    01681
    01682             return;
    01683         }
    01684
    01685         //
    01686         //  We didn't change roots so everything is fine and we can
    01687         //  simply return to our caller
    01688         //
    01689
    01690         return;
    01691
    01692     default:
    01693
    01694         //
    01695         //  If we get here then there was an error and the node type
    01696         //  code is unknown
    01697         //
    01698
    01699         return;
    01700     }
    01701 }
    01702
    01703
    01704 PUNICODE_PREFIX_TABLE_ENTRY
    01705 RtlFindUnicodePrefix (
    01706     IN PUNICODE_PREFIX_TABLE PrefixTable,
    01707     IN PUNICODE_STRING FullName,
    01708     IN ULONG CaseInsensitiveIndex
    01709     )
    01710
    01711 /*++
    01712
    01713 Routine Description:
    01714
    01715     This routine finds if a full name has a prefix in a prefix table.
    01716     It returns a pointer to the largest proper prefix found if one exists.
    01717
    01718 Arguments:
    01719
    01720     PrefixTable - Supplies the prefix table to search
    01721
    01722     FullString - Supplies the name to search for
    01723
    01724     CaseInsensitiveIndex - Indicates the wchar index at which to do a case
    01725         insensitive search.  All characters before the index are searched
    01726         case sensitive and all characters at and after the index are searched
    01727         insensitive.
    01728
    01729 Return Value:
    01730
    01731     PPREFIX_TABLE_ENTRY - a pointer to the longest prefix found if one
    01732         exists, and NULL otherwise
    01733
    01734 --*/
    01735
    01736 {
    01737     CLONG NameLength;
    01738
    01739     PUNICODE_PREFIX_TABLE_ENTRY PreviousTree;
    01740     PUNICODE_PREFIX_TABLE_ENTRY CurrentTree;
    01741     PUNICODE_PREFIX_TABLE_ENTRY NextTree;
    01742
    01743     PRTL_SPLAY_LINKS Links;
    01744
    01745     PUNICODE_PREFIX_TABLE_ENTRY Node;
    01746     PUNICODE_PREFIX_TABLE_ENTRY Next;
    01747
    01748     COMPARISON Comparison;
    01749
    01750     RTL_PAGED_CODE();
    01751
    01752     //
    01753     //  Determine the name length of the input string
    01754     //
    01755
    01756     NameLength = ComputeUnicodeNameLength(FullName);
    01757
    01758     //
    01759     //  Locate the first tree that can contain a prefix
    01760     //
    01761
    01762     PreviousTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
    01763     CurrentTree = PreviousTree->NextPrefixTree;
    01764
    01765     while (CurrentTree->NameLength > (CSHORT)NameLength) {
    01766
    01767         PreviousTree = CurrentTree;
    01768         CurrentTree = CurrentTree->NextPrefixTree;
    01769     }
    01770
    01771     //
    01772     //  Now search for a prefix until we find one or until we exhaust
    01773     //  the prefix trees
    01774     //
    01775
    01776     while (CurrentTree->NameLength > 0) {
    01777
    01778         Links = &CurrentTree->Links;
    01779
    01780         while (Links != NULL) {
    01781
    01782             Node = CONTAINING_RECORD(Links, UNICODE_PREFIX_TABLE_ENTRY, Links);
    01783
    01784             //
    01785             //  Compare the prefix in the tree with the full name, do the
    01786             //  compare case blind
    01787             //
    01788
    01789             Comparison = CompareUnicodeStrings(Node->Prefix, FullName, 0);
    01790
    01791             //
    01792             //  See if they don't match
    01793             //
    01794
    01795             if (Comparison == IsGreaterThan) {
    01796
    01797                 //
    01798                 //  The prefix is greater than the full name
    01799                 //  so we go down the left child
    01800                 //
    01801
    01802                 Links = RtlLeftChild(Links);
    01803
    01804                 //
    01805                 //  And continue searching down this tree
    01806                 //
    01807
    01808             } else if (Comparison == IsLessThan) {
    01809
    01810                 //
    01811                 //  The prefix is less than the full name
    01812                 //  so we go down the right child
    01813                 //
    01814
    01815                 Links = RtlRightChild(Links);
    01816
    01817                 //
    01818                 //  And continue searching down this tree
    01819                 //
    01820
    01821             } else {
    01822
    01823                 //
    01824                 //  We have either a prefix or a match either way
    01825                 //  we need to check if we should do case sensitive
    01826                 //  seearches
    01827                 //
    01828
    01829                 if (CaseInsensitiveIndex == 0) {
    01830
    01831                     //
    01832                     //  The caller wants case insensitive so we'll
    01833                     //  return the first one we found
    01834                     //
    01835                     //  Now that we've located the node we can splay the tree.
    01836                     //  To do this we need to remember how we find this tree in the root
    01837                     //  tree list, set the root to be an internal, splay, the tree, and
    01838                     //  then setup the new root node.
    01839                     //
    01840
    01841                     if (Node->NodeTypeCode == RTL_NTC_UNICODE_INTERNAL) {
    01842
    01843                         //DbgPrint("PrefixTable  = %08lx\n", PrefixTable);
    01844                         //DbgPrint("Node         = %08lx\n", Node);
    01845                         //DbgPrint("CurrentTree  = %08lx\n", CurrentTree);
    01846                         //DbgPrint("PreviousTree = %08lx\n", PreviousTree);
    01847                         //DbgBreakPoint();
    01848
    01849                         //
    01850                         //  Save a pointer to the next tree, we already have the previous tree
    01851                         //
    01852
    01853                         NextTree = CurrentTree->NextPrefixTree;
    01854
    01855                         //
    01856                         //  Reset the current root to be an internal node
    01857                         //
    01858
    01859                         CurrentTree->NodeTypeCode = RTL_NTC_UNICODE_INTERNAL;
    01860                         CurrentTree->NextPrefixTree = NULL;
    01861
    01862                         //
    01863                         //  Splay the tree and get the root
    01864                         //
    01865
    01866                         Node = CONTAINING_RECORD(RtlSplay(&Node->Links), UNICODE_PREFIX_TABLE_ENTRY, Links);
    01867
    01868                         //
    01869                         //  Set the new root's node type code and make it part of the
    01870                         //  root tree list
    01871                         //
    01872
    01873                         Node->NodeTypeCode = RTL_NTC_UNICODE_ROOT;
    01874                         PreviousTree->NextPrefixTree = Node;
    01875                         Node->NextPrefixTree = NextTree;
    01876                     }
    01877
    01878                     //
    01879                     //  Now return the root to our caller
    01880                     //
    01881
    01882                     return Node;
    01883                 }
    01884
    01885                 //
    01886                 //  The caller wants an exact match so search the case match
    01887                 //  until we find a complete match.  Get the first node
    01888                 //
    01889
    01890                 Next = Node;
    01891
    01892                 //
    01893                 //  Loop through the case match list checking to see if we
    01894                 //  match case sensitive with anyone.
    01895                 //
    01896
    01897                 do {
    01898
    01899                     //
    01900                     //  If we do match case sensitive then we found one
    01901                     //  and we return it to our caller
    01902                     //
    01903
    01904                     Comparison = CompareUnicodeStrings( Next->Prefix,
    01905                                                         FullName,
    01906                                                         CaseInsensitiveIndex );
    01907
    01908                     if ((Comparison == IsEqual) || (Comparison == IsPrefix)) {
    01909
    01910                         //
    01911                         //  We found a good one, so return it to our caller
    01912                         //
    01913
    01914                         return Next;
    01915                     }
    01916
    01917                     //
    01918                     //  Get the next case match record
    01919                     //
    01920
    01921                     Next = Next->CaseMatch;
    01922
    01923                     //
    01924                     //  And continue the loop until we reach the original
    01925                     //  node again
    01926                     //
    01927
    01928                 } while ( Next != Node );
    01929
    01930                 //
    01931                 //  We found a case blind prefix but the caller wants
    01932                 //  case sensitive and we weren't able to find one of those
    01933                 //  so we need to go on to the next tree, by breaking out
    01934                 //  of the inner while-loop
    01935                 //
    01936
    01937                 break;
    01938             }
    01939         }
    01940
    01941         //
    01942         //  This tree is done so now find the next tree
    01943         //
    01944
    01945         PreviousTree = CurrentTree;
    01946         CurrentTree = CurrentTree->NextPrefixTree;
    01947     }
    01948
    01949     //
    01950     //  We sesarched everywhere and didn't find a prefix so tell the
    01951     //  caller none was found
    01952     //
    01953
    01954     return NULL;
    01955 }
    01956
    01957
    01958 PUNICODE_PREFIX_TABLE_ENTRY
    01959 RtlNextUnicodePrefix (
    01960     IN PUNICODE_PREFIX_TABLE PrefixTable,
    01961     IN BOOLEAN Restart
    01962     )
    01963
    01964 /*++
    01965
    01966 Routine Description:
    01967
    01968     This routine returns the next prefix entry stored in the prefix table
    01969
    01970 Arguments:
    01971
    01972     PrefixTable - Supplies the prefix table to enumerate
    01973
    01974     Restart - Indicates if the enumeration should start over
    01975
    01976 Return Value:
    01977
    01978     PPREFIX_TABLE_ENTRY - A pointer to the next prefix table entry if
    01979         one exists otherwise NULL
    01980
    01981 --*/
    01982
    01983 {
    01984     PUNICODE_PREFIX_TABLE_ENTRY Node;
    01985
    01986     PRTL_SPLAY_LINKS Links;
    01987
    01988     RTL_PAGED_CODE();
    01989
    01990     //
    01991     //  See if we are restarting the sequence
    01992     //
    01993
    01994     if (Restart || (PrefixTable->LastNextEntry == NULL)) {
    01995
    01996         //
    01997         //  we are restarting the sequence so locate the first entry
    01998         //  in the first tree
    01999         //
    02000
    02001         Node = PrefixTable->NextPrefixTree;
    02002
    02003         //
    02004         //  Make sure we've pointing at a prefix tree
    02005         //
    02006
    02007         if (Node->NodeTypeCode == RTL_NTC_UNICODE_PREFIX_TABLE) {
    02008
    02009             //
    02010             //  No we aren't so the table must be empty
    02011             //
    02012
    02013             return NULL;
    02014         }
    02015
    02016         //
    02017         //  Find the first node in the tree
    02018         //
    02019
    02020         Links = &Node->Links;
    02021
    02022         while (RtlLeftChild(Links) != NULL) {
    02023
    02024             Links = RtlLeftChild(Links);
    02025         }
    02026
    02027         //
    02028         //  Set it as our the node we're returning
    02029         //
    02030
    02031         Node = CONTAINING_RECORD( Links, UNICODE_PREFIX_TABLE_ENTRY, Links);
    02032
    02033     } else if (PrefixTable->LastNextEntry->CaseMatch->NodeTypeCode == RTL_NTC_UNICODE_CASE_MATCH) {
    02034
    02035         //
    02036         //  The last node has a case match that we should be returning
    02037         //  this time around
    02038         //
    02039
    02040         Node = PrefixTable->LastNextEntry->CaseMatch;
    02041
    02042     } else {
    02043
    02044         //
    02045         //  Move over the last node returned by the case match link, this
    02046         //  will enable us to finish off the last case match node if there
    02047         //  was one, and go to the next internal/root node. If this node
    02048         //  does not have a case match then we simply circle back to ourselves
    02049         //
    02050
    02051         Node = PrefixTable->LastNextEntry->CaseMatch;
    02052
    02053         //
    02054         //  Find the successor for the last node we returned
    02055         //
    02056
    02057         Links = RtlRealSuccessor(&Node->Links);
    02058
    02059         //
    02060         //  If links is null then we've exhausted this tree and need to
    02061         //  the the next tree to use
    02062         //
    02063
    02064         if (Links == NULL) {
    02065
    02066             Links = &PrefixTable->LastNextEntry->Links;
    02067
    02068             while (!RtlIsRoot(Links)) {
    02069
    02070                 Links = RtlParent(Links);
    02071             }
    02072
    02073             Node = CONTAINING_RECORD(Links, UNICODE_PREFIX_TABLE_ENTRY, Links);
    02074
    02075             //
    02076             //  Now we've found the root see if there is another
    02077             //  tree to enumerate
    02078             //
    02079
    02080             Node = Node->NextPrefixTree;
    02081
    02082             if (Node->NameLength <= 0) {
    02083
    02084                 //
    02085                 //  We've run out of tree so tell our caller there
    02086                 //  are no more
    02087                 //
    02088
    02089                 return NULL;
    02090             }
    02091
    02092             //
    02093             //  We have another tree to go down
    02094             //
    02095
    02096             Links = &Node->Links;
    02097
    02098             while (RtlLeftChild(Links) != NULL) {
    02099
    02100                 Links = RtlLeftChild(Links);
    02101             }
    02102         }
    02103
    02104         //
    02105         //  Set it as our the node we're returning
    02106         //
    02107
    02108         Node = CONTAINING_RECORD( Links, UNICODE_PREFIX_TABLE_ENTRY, Links);
    02109     }
    02110
    02111     //
    02112     //  Save node as the last next entry
    02113     //
    02114
    02115     PrefixTable->LastNextEntry = Node;
    02116
    02117     //
    02118     //  And return this entry to our caller
    02119     //
    02120
    02121     return Node;
    02122 }
    02123
    02124
    02125 CLONG
    02126 ComputeUnicodeNameLength(
    02127     IN PUNICODE_STRING Name
    02128     )
    02129
    02130 /*++
    02131
    02132 Routine Description:
    02133
    02134     This routine counts the number of names appearing in the input string.
    02135     It does this by simply counting the number of backslashes in the string.
    02136     To handle ill-formed names (i.e., names that do not contain a backslash)
    02137     this routine really returns the number of backslashes plus 1.
    02138
    02139 Arguments:
    02140
    02141     Name - Supplies the input name to examine
    02142
    02143 Returns Value:
    02144
    02145     CLONG - the number of names in the input string
    02146
    02147 --*/
    02148
    02149 {
    02150     WCHAR UnicodeBackSlash = '\\';
    02151     ULONG NameLength;
    02152     ULONG i;
    02153     ULONG Count;
    02154
    02155     RTL_PAGED_CODE();
    02156
    02157     //
    02158     //  Save the name length, this should make the compiler be able to
    02159     //  optimize not having to reload the length each time
    02160     //
    02161
    02162     NameLength = (ULONG)Name->Length/2;
    02163
    02164     //
    02165     //  Now loop through the input string counting back slashes
    02166     //
    02167
    02168     for (i = 0, Count = 1; i < (ULONG)NameLength - 1; i += 1) {
    02169
    02170         //
    02171         //  check for a back slash
    02172         //
    02173
    02174         if (Name->Buffer[i] == UnicodeBackSlash) {
    02175
    02176             Count += 1;
    02177         }
    02178     }
    02179
    02180     //
    02181     //  return the number of back slashes we found
    02182     //
    02183
    02184     //DbgPrint("ComputeUnicodeNameLength(%Z) = %x\n", Name, Count);
    02185
    02186     return Count;
    02187 }
    02188
    02189
    02190 COMPARISON
    02191 CompareUnicodeStrings (
    02192     IN PUNICODE_STRING Prefix,
    02193     IN PUNICODE_STRING Name,
    02194     IN ULONG CaseInsensitiveIndex
    02195     )
    02196
    02197 /*++
    02198
    02199 Routine Description:
    02200
    02201     This routine takes a prefix string and a full name string and determines
    02202     if the prefix string is a proper prefix of the name string (case sensitive)
    02203
    02204 Arguments:
    02205
    02206     Prefix - Supplies the input prefix string
    02207
    02208     Name - Supplies the full name input string
    02209
    02210     CaseInsensitiveIndex - Indicates the wchar index at which to do a case
    02211         insensitive search.  All characters before the index are searched
    02212         case sensitive and all characters at and after the index are searched
    02213
    02214 Return Value:
    02215
    02216     COMPARISON - returns
    02217
    02218         IsLessThan    if Prefix < Name lexicalgraphically,
    02219         IsPrefix      if Prefix is a proper prefix of Name
    02220         IsEqual       if Prefix is equal to Name, and
    02221         IsGreaterThan if Prefix > Name lexicalgraphically
    02222
    02223 --*/
    02224
    02225 {
    02226     WCHAR UnicodeBackSlash = '\\';
    02227     ULONG PrefixLength;
    02228     ULONG NameLength;
    02229     ULONG MinLength;
    02230     ULONG i;
    02231
    02232     WCHAR PrefixChar;
    02233     WCHAR NameChar;
    02234
    02235     RTL_PAGED_CODE();
    02236
    02237     //DbgPrint("CompareUnicodeStrings(\"%Z\", \"%Z\") = ", Prefix, Name);
    02238
    02239     //
    02240     //  Save the length of the prefix and name string, this should allow
    02241     //  the compiler to not need to reload the length through a pointer every
    02242     //  time we need their values
    02243     //
    02244
    02245     PrefixLength = (ULONG)Prefix->Length/2;
    02246     NameLength = (ULONG)Name->Length/2;
    02247
    02248     //
    02249     //  Special case the situation where the prefix string is simply "\" and
    02250     //  the name starts with an "\"
    02251     //
    02252
    02253     if ((PrefixLength == 1) && (Prefix->Buffer[0] == UnicodeBackSlash) &&
    02254         (NameLength > 1) && (Name->Buffer[0] == UnicodeBackSlash)) {
    02255         //DbgPrint("IsPrefix\n");
    02256         return IsPrefix;
    02257     }
    02258
    02259     //
    02260     //  Figure out the minimum of the two lengths
    02261     //
    02262
    02263     MinLength = (PrefixLength < NameLength ? PrefixLength : NameLength);
    02264
    02265     //
    02266     //  Loop through looking at all of the characters in both strings
    02267     //  testing for equalilty.  First to the CaseSensitive part, then the
    02268     //  CaseInsensitive part.
    02269     //
    02270
    02271     if (CaseInsensitiveIndex > MinLength) {
    02272
    02273         CaseInsensitiveIndex = MinLength;
    02274     }
    02275
    02276     //
    02277     //  CaseSensitive compare
    02278     //
    02279
    02280     for (i = 0; i < CaseInsensitiveIndex; i += 1) {
    02281
    02282         PrefixChar = Prefix->Buffer[i];
    02283         NameChar   = Name->Buffer[i];
    02284
    02285         if (PrefixChar != NameChar) {
    02286
    02287             break;
    02288         }
    02289     }
    02290
    02291     //
    02292     //  If we didn't break out of the above loop, do the
    02293     //  CaseInsensitive compare.
    02294     //
    02295
    02296     if (i == CaseInsensitiveIndex) {
    02297
    02298         WCHAR *s1 = &Prefix->Buffer[i];
    02299         WCHAR *s2 = &Name->Buffer[i];
    02300
    02301         for (; i < MinLength; i += 1) {
    02302
    02303             PrefixChar = *s1++;
    02304             NameChar = *s2++;
    02305
    02306             if (PrefixChar != NameChar) {
    02307
    02308                 PrefixChar = NLS_UPCASE(PrefixChar);
    02309                 NameChar   = NLS_UPCASE(NameChar);
    02310
    02311                 if (PrefixChar != NameChar) {
    02312                     break;
    02313                 }
    02314             }
    02315         }
    02316     }
    02317
    02318     //
    02319     //  If we broke out of the above loop because of a mismatch, determine
    02320     //  the result of the comparison.
    02321     //
    02322
    02323     if (i < MinLength) {
    02324
    02325         //
    02326         //  We also need to treat "\" as less than all other characters, so
    02327         //  if the char is a "\" we'll drop it down to a value of zero.
    02328         //
    02329
    02330         if (PrefixChar == UnicodeBackSlash) {
    02331
    02332             return IsLessThan;
    02333         }
    02334
    02335         if (NameChar == UnicodeBackSlash) {
    02336
    02337             return IsGreaterThan;
    02338         }
    02339
    02340         //
    02341         //  Now compare the characters
    02342         //
    02343
    02344         if (PrefixChar < NameChar) {
    02345
    02346             return IsLessThan;
    02347
    02348         } else if (PrefixChar > NameChar) {
    02349
    02350             return IsGreaterThan;
    02351         }
    02352     }
    02353
    02354     //
    02355     //  They match upto the minimum length so now figure out the largest string
    02356     //  and see if one is a proper prefix of the other
    02357     //
    02358
    02359     if (PrefixLength < NameLength) {
    02360
    02361         //
    02362         //  The prefix string is shorter so if it is a proper prefix we
    02363         //  return prefix otherwise we return less than (e.g., "\a" < "\ab")
    02364         //
    02365
    02366         if (Name->Buffer[PrefixLength] == UnicodeBackSlash) {
    02367
    02368             //DbgPrint("IsPrefix\n");
    02369
    02370             return IsPrefix;
    02371
    02372         } else {
    02373
    02374             //DbgPrint("IsLessThan\n");
    02375
    02376             return IsLessThan;
    02377         }
    02378
    02379     } else if (PrefixLength > NameLength) {
    02380
    02381         //
    02382         //  The Prefix string is longer so we say that the prefix is
    02383         //  greater than the name (e.g., "\ab" > "\a")
    02384         //
    02385
    02386         //DbgPrint("IsGreaterThan\n");
    02387
    02388         return IsGreaterThan;
    02389
    02390     } else {
    02391
    02392         //
    02393         //  They lengths are equal so the strings are equal
    02394         //
    02395
    02396         //DbgPrint("IsEqual\n");
    02397
    02398         return IsEqual;
    02399     }
    02400 }
    02401