mdw@git.distorted.org.uk Git - sgt/tweak/blob - search.c

   1 #include "tweak.h"
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 static DFA build_dfa (char *pattern, int len)
   8 {
   9     int i, j, k, b;
  10     char *tmp = malloc(len);
  11     DFA dfa = malloc(len * sizeof(*dfa));
  12
  13     if (!dfa)
  14         return NULL;
  15     if (!tmp)
  16         return NULL;
  17
  18     memcpy (tmp, pattern, len);
  19
  20     for (i=len; i-- ;) {
  21         j = i+1;
  22         for (b=0; b<256; b++) {
  23             dfa[i][b] = 0;
  24             if (memchr(pattern, b, len)) {
  25                 tmp[j-1] = b;
  26                 for (k=1; k<=j; k++)
  27                     if (!memcmp(tmp+j-k, pattern, k))
  28                         dfa[i][b] = k;
  29             }
  30         }
  31     }
  32
  33     return dfa;
  34 }
  35
  36 Search *build_search(char *pattern, int len)
  37 {
  38     Search *ret = malloc(sizeof(Search));
  39     char *revpat = malloc(len);
  40     int i;
  41
  42     ret->len = len;
  43     ret->forward = build_dfa(pattern, len);
  44     for (i = 0; i < len; i++)
  45         revpat[i] = pattern[len-1-i];
  46     ret->reverse = build_dfa(revpat, len);
  47
  48     return ret;
  49 }
  50
  51 void free_search(Search *s)
  52 {
  53     free(s->forward);
  54     free(s->reverse);
  55     free(s);
  56 }