src/base/string/raw/find.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <u.h>
#include <base/memory.h>
#include <base/string.h>

char *
str·find(char *h, char *n)
{
    char *s, *ih, *in;
    intptr i, sum, len;

    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;

    ih = s+1;
    in = n+1;
    i = 1, sum = 0;
    while(*ih && *in){
        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! */
    len = in - n - 1;
    for(; *ih; ih++){
        sum -= *s++; /* sub the last character, advance the location on haystack */
        sum += *ih;  /* add the next character */
        if(sum == 0 && mem·compare(s, len, n)==0)
            return s;
    }
    return nil;
}