On Thu, Apr 16, 2009 at 09:09:44PM +0200, Ondrej Bilka wrote:
> Hello. I am writing partial fnmatch to speed up locate et al.
> Idea is save state state to match common prefix only once.
Forgot attach code.
--
Browser's cookie is corrupted -- someone's been nibbling on it.
#include <stdint.h>
#include <fnmatch.h>
#include <stdio.h>
#include <string.h>
#define UINT uint32_t
#define UINTSIZE 4
typedef struct { char tp;
} pattern;
typedef struct { char tp;
char chr;
} char_pattern;
typedef struct { char tp;
UINT chars;
} chars_pattern;
typedef struct { char tp;
} qst_pattern;
typedef struct { char tp;
char chr;
short sizerest;
} star_pattern;
typedef struct { char tp;
} end_pattern;
typedef struct { char tp;
} endstar_pattern;
enum PATTERNS {PATTERN_char,PATTERN_qst,PATTERN_star,PATTERN_chars,PATTERN_end,PATTERN_endstar};
#define NEXTPATTERN(type) pat->tp=PATTERN_##type;pat+=sizeof(type##_pattern);
pattern *makepattern(char *str){
unsigned char *s;
pattern *pat,*ret;
int canpack;int i,m;
ret=pat=(pattern *) malloc(200);
int rest=0;
for (s=(unsigned char *)str;*s;s++) {
if (*s!='*') rest++;
}
for (s=(unsigned char *)str;*s;s++) {
switch(*s){
case '*':
while (*(s+1)=='?') {/* *?=?* */
NEXTPATTERN(qst)
rest--;
s++;
}
if (*(s+1)){
((star_pattern*) pat)->sizerest=rest;
((star_pattern*) pat)->chr=*(s+1);
s++;
NEXTPATTERN(star)
}else{
NEXTPATTERN(endstar)
}
break;
case '?':
NEXTPATTERN(qst)
rest--;
break;
default:
canpack=1;
for (i=0;i<4;i++)
if (*(s+i)=='*'||*(s+i)=='?') canpack=0;
if (canpack){
((chars_pattern*) pat)->chars=*((UINT*) s);
rest-=UINTSIZE;
s+=UINTSIZE-1;
NEXTPATTERN(chars)
}else{
((char_pattern*) pat)->chr=*s;
rest--;
NEXTPATTERN(char)
}
break;
}
}
NEXTPATTERN(end)
return ret;
}
#undef NEXTPATTERN
#define NEXTPATTERN(type) p+=sizeof(type##_pattern);
int fnmatch3(pattern *p,char *str,int len){
char *s=str; int i,j; int sizerest,chars,chr;
while (1){
switch (p->tp){
case PATTERN_char:
if (*s != ((char_pattern*) p )->chr) return 1;
NEXTPATTERN(char);
s++;
break;
case PATTERN_chars:
if ((* (UINT *)s)!=((chars_pattern*) p )->chars) return 1;
s+=UINTSIZE;
NEXTPATTERN(chars);
break;
case PATTERN_qst:
s+=1;
NEXTPATTERN(qst);
break;
case PATTERN_star:
sizerest=((star_pattern*) p)->sizerest;
chr=((star_pattern*) p)->chr;
NEXTPATTERN(star);
for (i=s-str;i<=len-sizerest ; i++ )
{
if (( *(str+i) == chr)
&& !fnmatch3(p,str+i+1,len-i-1)) return 0;
}
return 1;
break;
case PATTERN_end:
return *s;
break;
case PATTERN_endstar:
return 0;
break;
}
}
}
char buf[1000];
int fnmatch2(pattern *p, char *str,int flags){
char *bu=buf;
if (flags){
while (*str) *bu++=tolower(*str++);
str=buf;
}
return fnmatch3(p,str,strlen(str));
}
int main(){int i;
char ptr[]="*abc*";
pattern *p=makepattern(ptr);
int cnt=0;
char s1[]="abcda", s2[]="bbida",s3[]="nabcx";
for (i=0;i<1000000;i++) {
s1[1]++;s2[1]++;s3[1]++;
int flags=1<<4;
#ifdef COMPARE
cnt+=fnmatch(ptr,s1,flags)+fnmatch(ptr,s2,flags)+fnmatch(ptr,s3,flags);
#else
cnt+=fnmatch2(p,s1,flags)+fnmatch2(p,s2,flags)+fnmatch2(p,s3,flags);
#endif
}
printf("%i",cnt);
}
_______________________________________________
Bug-coreutils mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/bug-coreutils
