test: name.c File Reference

00491 : 00492 00493 This routine compares a Dbcs name and an expression and tells the caller 00494 if the name is in the language defined by the expression. The input name 00495 cannot contain wildcards, while the expression may contain wildcards. 00496 00497 Expression wild cards are evaluated as shown in the nondeterministic 00498 finite automatons below. Note that ~* and ~? are DOS_STAR and DOS_QM. 00499 00500 00501 ~* is DOS_STAR, ~? is DOS_QM, and ~. is DOS_DOT 00502 00503 00504 S 00505 <-----< 00506 X | | e Y 00507 X * Y == (0)----->-(1)->-----(2)-----(3) 00508 00509 00510 S-. 00511 <-----< 00512 X | | e Y 00513 X ~* Y == (0)----->-(1)->-----(2)-----(3) 00514 00515 00516 00517 X S S Y 00518 X ?? Y == (0)---(1)---(2)---(3)---(4) 00519 00520 00521 00522 X . . Y 00523 X ~.~. Y == (0)---(1)----(2)------(3)---(4) 00524 | |________| 00525 | ^ | 00526 |_______________| 00527 ^EOF or .^ 00528 00529 00530 X S-. S-. Y 00531 X ~?~? Y == (0)---(1)-----(2)-----(3)---(4) 00532 | |________| 00533 | ^ | 00534 |_______________| 00535 ^EOF or .^ 00536 00537 00538 00539 where S is any single character 00540 00541 S-. is any single character except the final . 00542 00543 e is a null character transition 00544 00545 EOF is the end of the name string 00546 00547 In words: 00548 00549 * matches 0 or more characters. 00550 00551 ? matches exactly 1 character. 00552 00553 DOS_STAR matches 0 or more characters until encountering and matching 00554 the final . in the name. 00555 00556 DOS_QM matches any single character, or upon encountering a period or 00557 end of name string, advances the expression to the end of the 00558 set of contiguous DOS_QMs. 00559 00560 DOS_DOT matches either a . or zero characters beyond name string. 00561 00562 Arguments: 00563 00564 Expression - Supplies the input expression to check against 00565 (Caller must already upcase if passing CaseInsensitive TRUE.) 00566 00567 Name - Supplies the input name to check for. 00568 00569 CaseInsensitive - TRUE if Name should be Upcased before comparing. 00570 00571 Return Value: 00572 00573 BOOLEAN - TRUE if Name is an element in the set of strings denoted 00574 by the input Expression and FALSE otherwise. 00575 00576 --*/ 00577 00578 { 00579 USHORT NameOffset; 00580 USHORT ExprOffset; 00581 00582 ULONG SrcCount; 00583 ULONG DestCount; 00584 ULONG PreviousDestCount; 00585 ULONG MatchesCount; 00586 00587 WCHAR NameChar, ExprChar; 00588 00589 USHORT LocalBuffer[MATCHES_ARRAY_SIZE * 2]; 00590 00591 USHORT *AuxBuffer = NULL; 00592 USHORT *PreviousMatches; 00593 USHORT *CurrentMatches; 00594 00595 USHORT MaxState; 00596 USHORT CurrentState; 00597 00598 BOOLEAN NameFinished = FALSE; 00599 00600 // 00601 // The idea behind the algorithm is pretty simple. We keep track of 00602 // all possible locations in the regular expression that are matching 00603 // the name. If when the name has been exhausted one of the locations 00604 // in the expression is also just exhausted, the name is in the language 00605 // defined by the regular expression. 00606 // 00607 00608 PAGED_CODE(); 00609 00610 DebugTrace(+1, Dbg, "FsRtlIsNameInExpression\n", 0); 00611 DebugTrace( 0, Dbg, " Expression = %Z\n", Expression ); 00612 DebugTrace( 0, Dbg, " Name = %Z\n", Name ); 00613 DebugTrace( 0, Dbg, " CaseInsensitive = %08lx\n", CaseInsensitive ); 00614 00615 ASSERT( Name->Length != 0 ); 00616 ASSERT( Expression->Length != 0 ); 00617 00618 // 00619 // If one string is empty return FALSE. If both are empty return TRUE. 00620 // 00621 00622 if ( (Name->Length == 0) || (Expression->Length == 0) ) { 00623 00624 return (BOOLEAN)(!(Name->Length + Expression->Length)); 00625 } 00626 00627 // 00628 // Special case by far the most common wild card search of * 00629 // 00630 00631 if ((Expression->Length == 2) && (Expression->Buffer[0] == L'*')) { 00632 00633 return TRUE; 00634 } 00635 00636 ASSERT( FsRtlDoesNameContainWildCards( Expression ) ); 00637 00638 ASSERT( !IgnoreCase || ARGUMENT_PRESENT(UpcaseTable) ); 00639 00640 // 00641 // Also special case expressions of the form *X. With this and the prior 00642 // case we have covered virtually all normal queries. 00643 // 00644 00645 if (Expression->Buffer[0] == L'*') { 00646 00647 UNICODE_STRING LocalExpression; 00648 00649 LocalExpression = *Expression; 00650 00651 LocalExpression.Buffer += 1; 00652 LocalExpression.Length -= 2; 00653 00654 // 00655 // Only special case an expression with a single * 00656 // 00657 00658 if ( !FsRtlDoesNameContainWildCards( &LocalExpression ) ) { 00659 00660 ULONG StartingNameOffset; 00661 00662 if (Name->Length < (USHORT)(Expression->Length - sizeof(WCHAR))) { 00663 00664 return FALSE; 00665 } 00666 00667 StartingNameOffset = ( Name->Length - 00668 LocalExpression.Length ) / sizeof(WCHAR); 00669 00670 // 00671 // Do a simple memory compare if case sensitive, otherwise 00672 // we have got to check this one character at a time. 00673 // 00674 00675 if ( !IgnoreCase ) { 00676 00677 return (BOOLEAN) RtlEqualMemory( LocalExpression.Buffer, 00678 Name->Buffer + StartingNameOffset, 00679 LocalExpression.Length ); 00680 00681 } else { 00682 00683 for ( ExprOffset = 0; 00684 ExprOffset < (USHORT)(LocalExpression.Length / sizeof(WCHAR)); 00685 ExprOffset += 1 ) { 00686 00687 NameChar = Name->Buffer[StartingNameOffset + ExprOffset]; 00688 NameChar = UpcaseTable[NameChar]; 00689 00690 ExprChar = LocalExpression.Buffer[ExprOffset]; 00691 00692 ASSERT( ExprChar == UpcaseTable[ExprChar] ); 00693 00694 if ( NameChar != ExprChar ) { 00695 00696 return FALSE; 00697 } 00698 } 00699 00700 return TRUE; 00701 } 00702 } 00703 } 00704 00705 // 00706 // Walk through the name string, picking off characters. We go one 00707 // character beyond the end because some wild cards are able to match 00708 // zero characters beyond the end of the string. 00709 // 00710 // With each new name character we determine a new set of states that 00711 // match the name so far. We use two arrays that we swap back and forth 00712 // for this purpose. One array lists the possible expression states for 00713 // all name characters up to but not including the current one, and other 00714 // array is used to build up the list of states considering the current 00715 // name character as well. The arrays are then switched and the process 00716 // repeated. 00717 // 00718 // There is not a one-to-one correspondence between state number and 00719 // offset into the expression. This is evident from the NFAs in the 00720 // initial comment to this function. State numbering is not continuous. 00721 // This allows a simple conversion between state number and expression 00722 // offset. Each character in the expression can represent one or two 00723 // states. * and DOS_STAR generate two states: ExprOffset*2 and 00724 // ExprOffset*2 + 1. All other expreesion characters can produce only 00725 // a single state. Thus ExprOffset = State/2. 00726 // 00727 // 00728 // Here is a short description of the variables involved: 00729 // 00730 // NameOffset - The offset of the current name char being processed. 00731 // 00732 // ExprOffset - The offset of the current expression char being processed. 00733 // 00734 // SrcCount - Prior match being investigated with current name char 00735 // 00736 // DestCount - Next location to put a matching assuming current name char 00737 // 00738 // NameFinished - Allows one more itteration through the Matches array 00739 // after the name is exhusted (to come *s for example) 00740 // 00741 // PreviousDestCount - This is used to prevent entry duplication, see coment 00742 // 00743 // PreviousMatches - Holds the previous set of matches (the Src array) 00744 // 00745 // CurrentMatches - Holds the current set of matches (the Dest array) 00746 // 00747 // AuxBuffer, LocalBuffer - the storage for the Matches arrays 00748 // 00749 00750 // 00751 // Set up the initial variables 00752 // 00753 00754 PreviousMatches = &LocalBuffer[0]; 00755 CurrentMatches = &LocalBuffer[MATCHES_ARRAY_SIZE]; 00756 00757 PreviousMatches[0] = 0; 00758 MatchesCount = 1; 00759 00760 NameOffset = 0; 00761 00762 MaxState = (USHORT)(Expression->Length * 2); 00763 00764 while ( !NameFinished ) { 00765 00766 if ( NameOffset < Name->Length ) { 00767 00768 NameChar = Name->Buffer[NameOffset / sizeof(WCHAR)]; 00769 00770 NameOffset += sizeof(WCHAR);; 00771 00772 } else { 00773 00774 NameFinished = TRUE; 00775 00776 // 00777 // if we have already exhasted the expression, cool. Don't 00778 // continue. 00779 // 00780 00781 if ( PreviousMatches[MatchesCount-1] == MaxState ) { 00782 00783 break; 00784 } 00785 } 00786 00787 00788 // 00789 // Now, for each of the previous stored expression matches, see what 00790 // we can do with this name character. 00791 // 00792 00793 SrcCount = 0; 00794 DestCount = 0; 00795 PreviousDestCount = 0; 00796 00797 while ( SrcCount < MatchesCount ) { 00798 00799 USHORT Length; 00800 00801 // 00802 // We have to carry on our expression analysis as far as possible 00803 // for each character of name, so we loop here until the 00804 // expression stops matching. A clue here is that expression 00805 // cases that can match zero or more characters end with a 00806 // continue, while those that can accept only a single character 00807 // end with a break. 00808 // 00809 00810 ExprOffset = (USHORT)((PreviousMatches[SrcCount++] + 1) / 2); 00811 00812 00813 Length = 0; 00814 00815 while ( TRUE ) { 00816 00817 if ( ExprOffset == Expression->Length ) { 00818 00819 break; 00820 } 00821 00822 // 00823 // The first time through the loop we don't want 00824 // to increment ExprOffset. 00825 // 00826 00827 ExprOffset += Length; 00828 Length = sizeof(WCHAR); 00829 00830 CurrentState = (USHORT)(ExprOffset * 2); 00831 00832 if ( ExprOffset == Expression->Length ) { 00833 00834 CurrentMatches[DestCount++] = MaxState; 00835 break; 00836 } 00837 00838 ExprChar = Expression->Buffer[ExprOffset / sizeof(WCHAR)]; 00839 00840 ASSERT( !IgnoreCase || !((ExprChar >= L'a') && (ExprChar <= L'z')) ); 00841 00842 // 00843 // Before we get started, we have to check for something 00844 // really gross. We may be about to exhaust the local 00845 // space for ExpressionMatches[][], so we have to allocate 00846 // some pool if this is the case. Yuk! 00847 // 00848 00849 if ( (DestCount >= MATCHES_ARRAY_SIZE - 2) && 00850 (AuxBuffer == NULL) ) { 00851 00852 ULONG ExpressionChars; 00853 00854 ExpressionChars = Expression->Length / sizeof(WCHAR); 00855 00856 AuxBuffer = FsRtlpAllocatePool( PagedPool, 00857 (ExpressionChars+1) * 00858 sizeof(USHORT)*2*2 ); 00859 00860 RtlCopyMemory( AuxBuffer, 00861 CurrentMatches, 00862 MATCHES_ARRAY_SIZE * sizeof(USHORT) ); 00863 00864 CurrentMatches = AuxBuffer; 00865 00866 RtlCopyMemory( AuxBuffer + (ExpressionChars+1)*2, 00867 PreviousMatches, 00868 MATCHES_ARRAY_SIZE * sizeof(USHORT) ); 00869 00870 PreviousMatches = AuxBuffer + (ExpressionChars+1)*2; 00871 } 00872 00873 // 00874 // * matches any character zero or more times. 00875 // 00876 00877 if (ExprChar == L'*') { 00878 00879 CurrentMatches[DestCount++] = CurrentState; 00880 CurrentMatches[DestCount++] = CurrentState + 3; 00881 continue; 00882 } 00883 00884 // 00885 // DOS_STAR matches any character except . zero or more times. 00886 // 00887 00888 if (ExprChar == DOS_STAR) { 00889 00890 BOOLEAN ICanEatADot = FALSE; 00891 00892 // 00893 // If we are at a period, determine if we are allowed to 00894 // consume it, ie. make sure it is not the last one. 00895 // 00896 00897 if ( !NameFinished && (NameChar == '.') ) { 00898 00899 USHORT Offset; 00900 00901 for ( Offset = NameOffset; 00902 Offset < Name->Length; 00903 Offset += Length ) { 00904 00905 if (Name->Buffer[Offset / sizeof(WCHAR)] == L'.') { 00906 00907 ICanEatADot = TRUE; 00908 break; 00909 } 00910 } 00911 } 00912 00913 if (NameFinished || (NameChar != L'.') || ICanEatADot) { 00914 00915 CurrentMatches[DestCount++] = CurrentState; 00916 CurrentMatches[DestCount++] = CurrentState + 3; 00917 continue; 00918 00919 } else { 00920 00921 // 00922 // We are at a period. We can only match zero 00923 // characters (ie. the epsilon transition). 00924 // 00925 00926 CurrentMatches[DestCount++] = CurrentState + 3; 00927 continue; 00928 } 00929 } 00930 00931 // 00932 // The following expreesion characters all match by consuming 00933 // a character, thus force the expression, and thus state 00934 // forward. 00935 // 00936 00937 CurrentState += (USHORT)(sizeof(WCHAR) * 2); 00938 00939 // 00940 // DOS_QM is the most complicated. If the name is finished, 00941 // we can match zero characters. If this name is a '.', we 00942 // don't match, but look at the next expression. Otherwise 00943 // we match a single character. 00944 // 00945 00946 if ( ExprChar == DOS_QM ) { 00947 00948 if ( NameFinished || (NameChar == L'.') ) { 00949 00950 continue; 00951 } 00952 00953 CurrentMatches[DestCount++] = CurrentState; 00954 break; 00955 } 00956 00957 // 00958 // A DOS_DOT can match either a period, or zero characters 00959 // beyond the end of name. 00960 // 00961 00962 if (ExprChar == DOS_DOT) { 00963 00964 if ( NameFinished ) { 00965 00966 continue; 00967 } 00968 00969 if (NameChar == L'.') { 00970 00971 CurrentMatches[DestCount++] = CurrentState; 00972 break; 00973 } 00974 } 00975 00976 // 00977 // From this point on a name character is required to even 00978 // continue, let alone make a match. 00979 // 00980 00981 if ( NameFinished ) { 00982 00983 break; 00984 } 00985 00986 // 00987 // If this expression was a '?' we can match it once. 00988 // 00989 00990 if (ExprChar == L'?') { 00991 00992 CurrentMatches[DestCount++] = CurrentState; 00993 break; 00994 } 00995 00996 // 00997 // Finally, check if the expression char matches the name char 00998 // 00999 01000 if (ExprChar == (WCHAR)(IgnoreCase ? 01001 UpcaseTable[NameChar] : NameChar)) { 01002 01003 CurrentMatches[DestCount++] = CurrentState; 01004 break; 01005 } 01006 01007 // 01008 // The expression didn't match so go look at the next 01009 // previous match. 01010 // 01011 01012 break; 01013 } 01014 01015 01016 // 01017 // Prevent duplication in the destination array. 01018 // 01019 // Each of the arrays is montonically increasing and non- 01020 // duplicating, thus we skip over any source element in the src 01021 // array if we just added the same element to the destination 01022 // array. This guarentees non-duplication in the dest. array. 01023 // 01024 01025 if ((SrcCount < MatchesCount) && 01026 (PreviousDestCount < DestCount) ) { 01027 01028 while (PreviousDestCount < DestCount) { 01029 01030 while ( PreviousMatches[SrcCount] < 01031 CurrentMatches[PreviousDestCount] ) { 01032 01033 SrcCount += 1; 01034 } 01035 01036 PreviousDestCount += 1; 01037 } 01038 } 01039 } 01040 01041 // 01042 // If we found no matches in the just finished itteration, it's time 01043 // to bail. 01044 // 01045 01046 if ( DestCount == 0 ) { 01047 01048 if (AuxBuffer != NULL) { ExFreePool( AuxBuffer ); } 01049 01050 return FALSE; 01051 } 01052 01053 // 01054 // Swap the meaning the two arrays 01055 // 01056 01057 { 01058 USHORT *Tmp; 01059 01060 Tmp = PreviousMatches; 01061 01062 PreviousMatches = CurrentMatches; 01063 01064 CurrentMatches = Tmp; 01065 } 01066 01067 MatchesCount = DestCount; 01068 } 01069 01070 01071 CurrentState = PreviousMatches[MatchesCount-1]; 01072 01073 if (AuxBuffer != NULL) { ExFreePool( AuxBuffer ); } 01074 01075 01076 return (BOOLEAN)(CurrentState == MaxState); 01077 } }


Defines
#define	Dbg (0x10000000)
#define	DavePrint NOTHING
#define	MODULE_POOL_TAG ('nrSF')
#define	MATCHES_ARRAY_SIZE 16
Functions
BOOLEAN	FsRtlIsNameInExpressionPrivate (IN PUNICODE_STRING Expression, IN PUNICODE_STRING Name, IN BOOLEAN IgnoreCase, IN PWCH UpcaseTable)
VOID	FsRtlDissectName (IN UNICODE_STRING Path, OUT PUNICODE_STRING FirstName, OUT PUNICODE_STRING RemainingName)
BOOLEAN	FsRtlDoesNameContainWildCards (IN PUNICODE_STRING Name)
BOOLEAN	FsRtlAreNamesEqual (PCUNICODE_STRING ConstantNameA, PCUNICODE_STRING ConstantNameB, IN BOOLEAN IgnoreCase, IN PCWCH UpcaseTable OPTIONAL)
BOOLEAN	FsRtlIsNameInExpression (IN PUNICODE_STRING Expression, IN PUNICODE_STRING Name, IN BOOLEAN IgnoreCase, IN PWCH UpcaseTable OPTIONAL)

name.c File Reference

Defines

Functions

Define Documentation

Function Documentation