[sgt/tweak] / search.c

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

#include "tweak.h"

static DFA dfa = NULL;
static char *tmp = NULL;
static int dfa_size = 0, dfa_len = 0;

DFA build_dfa (char *pattern, int len) {
    int i, j, k, b;

    if (dfa_size < len) {
	dfa_size = len;
	dfa = (dfa ? realloc(dfa, dfa_size * sizeof(*dfa)) :
	       malloc(dfa_size * sizeof(*dfa)));
	if (!dfa)
	    return NULL;
	tmp = (tmp ? realloc(tmp, dfa_size) : malloc(dfa_size));
	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;
	    }
	}
    }
    dfa_len = len;
    return dfa;
}

DFA last_dfa (void) {
    return dfa;
}

int last_len (void) {
    return dfa_len;
}
Commit	Line	Data
6e182d98	1	#include <stdio.h>
	2	#include <stdlib.h>
	3	#include <string.h>
	4
	5	#include "tweak.h"
	6
	7	static DFA dfa = NULL;
	8	static char *tmp = NULL;
	9	static int dfa_size = 0, dfa_len = 0;
	10
	11	DFA build_dfa (char *pattern, int len) {
	12	int i, j, k, b;
	13
	14	if (dfa_size < len) {
	15	dfa_size = len;
	16	dfa = (dfa ? realloc(dfa, dfa_size * sizeof(*dfa)) :
	17	malloc(dfa_size * sizeof(*dfa)));
	18	if (!dfa)
	19	return NULL;
	20	tmp = (tmp ? realloc(tmp, dfa_size) : malloc(dfa_size));
	21	if (!tmp)
	22	return NULL;
	23	}
	24
	25	memcpy (tmp, pattern, len);
	26
	27	for (i=len; i-- ;) {
	28	j = i+1;
	29	for (b=0; b<256; b++) {
	30	dfa[i][b] = 0;
	31	if (memchr(pattern, b, len)) {
	32	tmp[j-1] = b;
	33	for (k=1; k<=j; k++)
	34	if (!memcmp(tmp+j-k, pattern, k))
	35	dfa[i][b] = k;
	36	}
	37	}
	38	}
	39	dfa_len = len;
	40	return dfa;
	41	}
	42
	43	DFA last_dfa (void) {
	44	return dfa;
	45	}
	46
	47	int last_len (void) {
	48	return dfa_len;
	49	}