search.c 969 Bytes
Newer Older
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 49 50 51 52 53 54 55 56
#include "tweak.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static DFA build_dfa (char *pattern, int len)
{
    int i, j, k, b;
    char *tmp = malloc(len);
    DFA dfa = malloc(len * sizeof(*dfa));

    if (!dfa)
	return NULL;
    if (!tmp)
	return NULL;

    memcpy (tmp, pattern, len);

    for (i=len; i-- ;) {
	j = i+1;
	for (b=0; b<256; b++) {
	    dfa[i][b] = 0;
	    if (memchr(pattern, b, len)) {
		tmp[j-1] = b;
		for (k=1; k<=j; k++)
		    if (!memcmp(tmp+j-k, pattern, k))
			dfa[i][b] = k;
	    }
	}
    }

    return dfa;
}

Search *build_search(char *pattern, int len)
{
    Search *ret = malloc(sizeof(Search));
    char *revpat = malloc(len);
    int i;

    ret->len = len;
    ret->forward = build_dfa(pattern, len);
    for (i = 0; i < len; i++)
	revpat[i] = pattern[len-1-i];
    ret->reverse = build_dfa(revpat, len);

    return ret;
}

void free_search(Search *s)
{
    free(s->forward);
    free(s->reverse);
    free(s);
}