diff options
Diffstat (limited to 'src/base/string/raw/efind.c')
-rw-r--r-- | src/base/string/raw/efind.c | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/src/base/string/raw/efind.c b/src/base/string/raw/efind.c new file mode 100644 index 0000000..e097b42 --- /dev/null +++ b/src/base/string/raw/efind.c @@ -0,0 +1,48 @@ +#include <u.h> +#include <base/memory.h> +#include <base/string.h> + +char * +str·efind(char *h, char *e, char *n) +{ + char *s, *ih, *in; + intptr i, sum, sz; + + if(!n || !n[0]) + return h; + + if(!h || !h[0] || h > e) + return nil; + + /* two way string matching */ + + /* align first characters */ + if(!(s = str·findc(h, n[0]))) + return nil; + + ih = s+1; + in = n+1; + i = 1, sum = 0; + while(*ih && *in && ih != e){ + sum += *ih; + sum -= *in; + i &= (*ih++ == *in++); + } + + if(*in) /* needle is larger than haystack! */ + return nil; + else if(i) /* found match */ + return s; + + /* no hit: loop for remainder of haystack + * if prefix sum ever falls to zero, we have equal hashes + * compare! */ + sz = in - n - 1; + for(; *ih && ih != e; ih++){ + sum -= *s++; /* sub the last character, advance the location on haystack */ + sum += *ih; /* add the next character */ + if(sum == 0 && mem·compare(s, sz, n)==0) + return s; + } + return nil; +} |