diff options
Diffstat (limited to 'src/base/string/raw/nfind.c')
-rw-r--r-- | src/base/string/raw/nfind.c | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/src/base/string/raw/nfind.c b/src/base/string/raw/nfind.c new file mode 100644 index 0000000..181cc03 --- /dev/null +++ b/src/base/string/raw/nfind.c @@ -0,0 +1,51 @@ +#include <u.h> +#include <base/memory.h> +#include <base/string.h> + +char * +str·nfind(char *h, intptr len, char *n) +{ + char *s, *ih, *in; + intptr i, sum, sz; + + if(!n || !n[0]) + return h; + + if(!h || !h[0]) + return nil; + + /* two way string matching */ + + /* align first characters */ + if(!(s = str·findc(h, n[0]))) + return nil; + + len -= (s-h); + sz = len; + + ih = s+1; + in = n+1; + i = 1, sum = 0; + while(*ih && *in && len-- > 0){ + 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(len=sz; *ih && len>0; ih++,len--){ + 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; +} |