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

   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 }