My goal was to create a function as performant as possible with results being:
- True/False as to whether
wild
matchesstr
. - Optional capture of certain patterns.
My purposes required:
- Case sensitive match.
- Pattern must match entire string to succeed.
- Assumption that
*
and?
do not exist instr
. *
matches zero or more characters.?
matches exactly one character.- Lazy
*
in this case meaning that going from left to right,*
would match as little as possible while still ensuring a match if such were possible.
It's been a challenge as many times I almost had it but then found an edge case that didn't work. This is basically globbing, but I need such to work for strings rather than files and I also hoped to make something much faster than using a regex which IMHO would be overkill for my needs.
I have tested the following to work on many patterns but I can't be certain yet if there isn't a permutation where it fails. I would be very interested if anyone can point out a situation where it fails the terms set above. I'm also interested to hear if there are any ways the code can be improved (made faster).
Hacks like (unsigned)(*wild-40)<=1
are probably unnecessary given the ability of gcc to optimize, but I put it in there anyway.
static __attribute__ ((noinline)) int globSearch(char *wild,char *str,char **c)
{
int N=-1,n=0,nm=0;
while(*str)
{
if(*wild == '*'){ N=n; wild++; }
else if((unsigned)(*wild-40)<=1) // faster version of if(*wild=='('||*wild==')')
{
c[n++]=str;
wild++;
}
else if(*wild == '?'){ wild++; str++; }
else if(*wild == *str)
{
if(nm){while(N < n){ c[N++]+=nm; }}
nm=0;
N=-1;
wild++;
str++;
}
else if(N > -1){ str++; nm++; }
else return 0;
}
while((unsigned)(*wild-40) <= 2) // while( *wild == '(' || *wild == ')' || *wild == '*' )
{
if(*wild++ != '*')c[n++]=str;
}
if(nm){while(N < n){ c[N++]+=nm; }}
return !*wild;
}
Testing function
int main()
{
char tmp[100]={0};
char *c[20]={0};
char *m="(hello) (*)(?*?)?(?)?(*)(*)";
char *str="hello world";
int t=globSearch(m,str,c);
if(t)
{
for(int x=0;c[x]&&c[x+1];x+=2)
{
int z=c[x+1]-c[x];
memcpy(tmp,c[x],z);
tmp[z]=0;
printf("%s:%d\n",tmp,z);
}
}
return 0;
}
The above code returns successful match with patterns captured: (hello:5) (0) (wo:2) (l:1) (0) (0)
Other patterns and results:
*(hello*)*
->(hello:5)
hello *(d)
->(d:1)
(hello) (*)(d)
->(hello:5) (worl:4) (d:1)
(hello) *(*)r(*)?
->(hello:5) (wo:2) (l:1)
(hello) *(*)r(*)*?
->(hello:5) (wo:2) (0)
All the results are exactly what I was hoping given the parameters. Can it be done faster?
__attribute__ ((noinline))
is rarely used. What's your reason behind it? \$\endgroup\$