IN BOOLEAN IgnoreCase,
IN PWCHAR UpcaseTable OPTIONAL)
{
- USHORT ExpressionPosition = 0, NamePosition = 0, MatchingChars, StarFound = MAXUSHORT;
+ SHORT StarFound = -1, DosStarFound = -1;
+ USHORT BackTrackingBuffer[5], DosBackTrackingBuffer[5];
+ PUSHORT BackTracking = BackTrackingBuffer, DosBackTracking = DosBackTrackingBuffer;
+ SHORT BackTrackingSize = RTL_NUMBER_OF(BackTrackingBuffer);
+ SHORT DosBackTrackingSize = RTL_NUMBER_OF(DosBackTrackingBuffer);
UNICODE_STRING IntExpression;
+ USHORT ExpressionPosition = 0, NamePosition = 0, MatchingChars, LastDot;
+ WCHAR CompareChar;
PAGED_CODE();
/* Check if we were given strings at all */
}
}
- while (NamePosition < Name->Length / sizeof(WCHAR) && ExpressionPosition < Expression->Length / sizeof(WCHAR))
+ while ((NamePosition < Name->Length / sizeof(WCHAR)) &&
+ (ExpressionPosition < Expression->Length / sizeof(WCHAR)))
{
- if ((Expression->Buffer[ExpressionPosition] == (IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] : Name->Buffer[NamePosition])))
+ /* Basic check to test if chars are equal */
+ CompareChar = IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] :
+ Name->Buffer[NamePosition];
+ if (Expression->Buffer[ExpressionPosition] == CompareChar)
{
NamePosition++;
ExpressionPosition++;
}
- else if (StarFound != MAXUSHORT && (Expression->Buffer[StarFound + 1] == L'*' ||
- Expression->Buffer[StarFound + 1] == L'?' || Expression->Buffer[StarFound + 1] == DOS_DOT))
- {
- ExpressionPosition = StarFound + 1;
- switch (Expression->Buffer[ExpressionPosition])
- {
- case L'*':
- StarFound = MAXUSHORT;
- break;
-
- case L'?':
- if (++ExpressionPosition == Expression->Length / sizeof(WCHAR))
- {
- NamePosition = Name->Length / sizeof(WCHAR);
- break;
- }
-
- MatchingChars = NamePosition;
- while (NamePosition < Name->Length / sizeof(WCHAR) &&
- (IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] :
- Name->Buffer[NamePosition]) != Expression->Buffer[ExpressionPosition])
- {
- NamePosition++;
- }
-
- if (NamePosition - MatchingChars > 0)
- {
- StarFound = MAXUSHORT;
- }
- break;
-
- case DOS_DOT:
- while (NamePosition < Name->Length / sizeof(WCHAR) &&
- Name->Buffer[NamePosition] != L'.')
- {
- NamePosition++;
- }
- ExpressionPosition++;
- StarFound = MAXUSHORT;
- break;
-
- default:
- /* Should never happen */
- ASSERT(FALSE);
- }
- }
- else if (Expression->Buffer[ExpressionPosition] == L'?' || (Expression->Buffer[ExpressionPosition] == DOS_QM) ||
- (Expression->Buffer[ExpressionPosition] == DOS_DOT && Name->Buffer[NamePosition] == L'.'))
+ /* Check cases that eat one char */
+ else if (Expression->Buffer[ExpressionPosition] == L'?')
{
NamePosition++;
ExpressionPosition++;
- StarFound = MAXUSHORT;
}
+ /* Test star */
else if (Expression->Buffer[ExpressionPosition] == L'*')
{
- StarFound = ExpressionPosition++;
+ /* Skip contigous stars */
+ while ((ExpressionPosition + 1 < (USHORT)(Expression->Length / sizeof(WCHAR))) &&
+ (Expression->Buffer[ExpressionPosition + 1] == L'*'))
+ {
+ ExpressionPosition++;
+ }
+
+ /* If star is at the end, then eat all rest and leave */
if (ExpressionPosition == Expression->Length / sizeof(WCHAR))
{
NamePosition = Name->Length / sizeof(WCHAR);
break;
}
+
+ /* Save star position */
+ StarFound++;
+ if (StarFound >= BackTrackingSize)
+ {
+ BackTrackingSize = Expression->Length / sizeof(WCHAR);
+ BackTracking = ExAllocatePoolWithTag(PagedPool | POOL_RAISE_IF_ALLOCATION_FAILURE,
+ BackTrackingSize * sizeof(USHORT),
+ 'nrSF');
+ RtlCopyMemory(BackTracking, BackTrackingBuffer, sizeof(BackTrackingBuffer));
+
+ }
+ BackTracking[StarFound] = ExpressionPosition++;
+
+ /* Allow null matching */
+ if (Expression->Buffer[ExpressionPosition] != L'?' &&
+ Expression->Buffer[ExpressionPosition] != Name->Buffer[NamePosition])
+ {
+ NamePosition++;
+ }
}
+ /* Check DOS_STAR */
else if (Expression->Buffer[ExpressionPosition] == DOS_STAR)
{
- StarFound = MAXUSHORT;
- MatchingChars = NamePosition;
+ /* Skip contigous stars */
+ while ((ExpressionPosition + 1 < (USHORT)(Expression->Length / sizeof(WCHAR))) &&
+ (Expression->Buffer[ExpressionPosition + 1] == DOS_STAR))
+ {
+ ExpressionPosition++;
+ }
+
+ /* Look for last dot */
+ MatchingChars = 0;
+ LastDot = (USHORT)-1;
while (MatchingChars < Name->Length / sizeof(WCHAR))
{
if (Name->Buffer[MatchingChars] == L'.')
{
- NamePosition = MatchingChars;
+ LastDot = MatchingChars;
+ if (LastDot > NamePosition)
+ break;
}
+
MatchingChars++;
}
+
+ /* If we don't have dots or we didn't find last yet
+ * start eating everything
+ */
+ if (MatchingChars != Name->Length || LastDot == (USHORT)-1)
+ {
+ DosStarFound++;
+ if (DosStarFound >= DosBackTrackingSize)
+ {
+ DosBackTrackingSize = Expression->Length / sizeof(WCHAR);
+ DosBackTracking = ExAllocatePoolWithTag(PagedPool | POOL_RAISE_IF_ALLOCATION_FAILURE,
+ DosBackTrackingSize * sizeof(USHORT),
+ 'nrSF');
+ RtlCopyMemory(DosBackTracking, DosBackTrackingBuffer, sizeof(DosBackTrackingBuffer));
+ }
+ DosBackTracking[DosStarFound] = ExpressionPosition++;
+
+ /* Not the same char, start exploring */
+ if (Expression->Buffer[ExpressionPosition] != Name->Buffer[NamePosition])
+ NamePosition++;
+ }
+ else
+ {
+ /* Else, if we are at last dot, eat it - otherwise, null match */
+ if (Name->Buffer[NamePosition] == '.')
+ NamePosition++;
+
+ ExpressionPosition++;
+ }
+ }
+ /* Check DOS_DOT */
+ else if (Expression->Buffer[ExpressionPosition] == DOS_DOT)
+ {
+ /* We only match dots */
+ if (Name->Buffer[NamePosition] == L'.')
+ {
+ NamePosition++;
+ }
+ /* Try to explore later on for null matching */
+ else if ((ExpressionPosition + 1 < (USHORT)(Expression->Length / sizeof(WCHAR))) &&
+ (Name->Buffer[NamePosition] == Expression->Buffer[ExpressionPosition + 1]))
+ {
+ NamePosition++;
+ }
ExpressionPosition++;
}
- else if (StarFound != MAXUSHORT)
+ /* Check DOS_QM */
+ else if (Expression->Buffer[ExpressionPosition] == DOS_QM)
{
- ExpressionPosition = StarFound + 1;
- while (NamePosition < Name->Length / sizeof(WCHAR) &&
- (IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] :
- Name->Buffer[NamePosition]) != Expression->Buffer[ExpressionPosition])
+ /* We match everything except dots */
+ if (Name->Buffer[NamePosition] != L'.')
{
NamePosition++;
}
+ ExpressionPosition++;
}
+ /* If nothing match, try to backtrack */
+ else if (StarFound >= 0)
+ {
+ ExpressionPosition = BackTracking[StarFound--];
+ }
+ else if (DosStarFound >= 0)
+ {
+ ExpressionPosition = DosBackTracking[DosStarFound--];
+ }
+ /* Otherwise, fail */
else
{
break;
}
+
+ /* Under certain circumstances, expression is over, but name isn't
+ * and we can backtrack, then, backtrack */
+ if (ExpressionPosition == Expression->Length / sizeof(WCHAR) &&
+ NamePosition != Name->Length / sizeof(WCHAR) &&
+ StarFound >= 0)
+ {
+ ExpressionPosition = BackTracking[StarFound--];
+ }
+ }
+ /* If we have nullable matching wc at the end of the string, eat them */
+ if (ExpressionPosition != Expression->Length / sizeof(WCHAR) && NamePosition == Name->Length / sizeof(WCHAR))
+ {
+ while (ExpressionPosition < Expression->Length / sizeof(WCHAR))
+ {
+ if (Expression->Buffer[ExpressionPosition] != DOS_DOT &&
+ Expression->Buffer[ExpressionPosition] != L'*' &&
+ Expression->Buffer[ExpressionPosition] != DOS_STAR)
+ {
+ break;
+ }
+ ExpressionPosition++;
+ }
+ }
+
+ if (BackTracking != BackTrackingBuffer)
+ {
+ ExFreePoolWithTag(BackTracking, 'nrSF');
}
- if (ExpressionPosition + 1 == Expression->Length / sizeof(WCHAR) && NamePosition == Name->Length / sizeof(WCHAR) &&
- Expression->Buffer[ExpressionPosition] == DOS_DOT)
+ if (DosBackTracking != DosBackTrackingBuffer)
{
- ExpressionPosition++;
+ ExFreePoolWithTag(DosBackTracking, 'nrSF');
}
return (ExpressionPosition == Expression->Length / sizeof(WCHAR) && NamePosition == Name->Length / sizeof(WCHAR));
*
* @param Expression
* The string in which we've to find Name. It can contain wildcards.
- * If IgnoreCase is set to TRUE, this string MUST BE uppercase.
+ * If IgnoreCase is set to TRUE, this string MUST BE uppercase.
*
* @param Name
* The string to find. It cannot contain wildcards
*
* @param UpcaseTable
* If not NULL, and if IgnoreCase is set to TRUE, it will be used to
- * upcase the both strings
+ * upcase the both strings
*
* @return TRUE if Name is in Expression, FALSE otherwise
*
projects / reactos.git / blobdiff