lib/kmp-test.c

   1 #include "lib/lib.h"
   2 #include "lib/mempool.h"
   3 #include <string.h>
   4
   5 #if 0
   6 #define TRACE(x...) do{log(L_DEBUG, x);}while(0)
   7 #else
   8 #define TRACE(x...) do{}while(0)
   9 #endif
  10
  11 #define KMP_PREFIX(x) GLUE_(kmp1,x)
  12 #define KMP_WANT_CLEANUP
  13 #define KMP_WANT_SEARCH
  14 #define KMPS_WANT_BEST
  15 #define KMPS_T uns
  16 #define KMPS_EXIT(ctx,src,s) do{ return s.best->len; }while(0)
  17 #include "lib/kmp-new.h"
  18
  19 static void
  20 test1(void)
  21 {
  22   log(L_INFO, "Running test1");
  23   struct kmp1_context ctx;
  24   kmp1_init(&ctx);
  25   kmp1_add(&ctx, "ahoj");
  26   kmp1_add(&ctx, "hoj");
  27   kmp1_add(&ctx, "aho");
  28   kmp1_build(&ctx);
  29   UNUSED uns best = kmp1_search(&ctx, "asjlahslhalahosjkjhojsas");
  30   TRACE("Best match has %d characters", best);
  31   ASSERT(best == 3);
  32   kmp1_cleanup(&ctx);
  33 }
  34
  35 #define KMP_PREFIX(x) GLUE_(kmp2,x)
  36 #define KMP_USE_UTF8
  37 #define KMP_TOLOWER
  38 #define KMP_ONLYALPHA
  39 #define KMP_NODE struct { byte *str; uns id; }
  40 #define KMP_ADD_EXTRA_ARGS uns id
  41 #define KMP_ADD_EXTRA_VAR byte *
  42 #define KMP_ADD_INIT(ctx,src,var) do{ var = src; }while(0)
  43 #define KMP_ADD_NEW(ctx,src,var,state) do{ TRACE("Inserting string %s with id %d", var, id); \
  44   state->n.str = var; state->n.id = id; }while(0)
  45 #define KMP_ADD_DUP(ctx,src,var,state) do{ TRACE("String %s already inserted", var); }while(0)
  46 #define KMP_WANT_CLEANUP
  47 #define KMP_WANT_SEARCH
  48 #define KMPS_ADD_CONTROLS
  49 #define KMPS_MERGE_CONTROLS
  50 #define KMPS_WANT_BEST
  51 #define KMPS_FOUND(ctx,src,s) do{ TRACE("String %s with id %d found", s.out->n.str, s.out->n.id); }while(0)
  52 #define KMPS_STEP(ctx,src,s) do{ TRACE("Got to state %p after reading %d", s.s, s.c); }while(0)
  53 #define KMPS_EXIT(ctx,src,s) do{ if (s.best->len) TRACE("Best match is %s", s.best->n.str); } while(0)
  54 #include "lib/kmp-new.h"
  55
  56 static void
  57 test2(void)
  58 {
  59   log(L_INFO, "Running test2");
  60   struct kmp2_context ctx;
  61   kmp2_init(&ctx);
  62   kmp2_add(&ctx, "ahoj", 1);
  63   kmp2_add(&ctx, "ahoj", 2);
  64   kmp2_add(&ctx, "hoj", 3);
  65   kmp2_add(&ctx, "aho", 4);
  66   kmp2_add(&ctx, "aba", 5);
  67   kmp2_add(&ctx, "aba", 5);
  68   kmp2_add(&ctx, "pěl", 5);
  69   kmp2_build(&ctx);
  70   kmp2_search(&ctx, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla");
  71   kmp2_cleanup(&ctx);
  72 }
  73
  74 #define KMP_PREFIX(x) GLUE_(kmp3,x)
  75 #define KMP_NODE uns
  76 #define KMP_ADD_EXTRA_ARGS uns index
  77 #define KMP_ADD_EXTRA_VAR byte *
  78 #define KMP_ADD_INIT(ctx,src,v) do{ v = src; }while(0)
  79 #define KMP_ADD_NEW(ctx,src,v,s) do{ s->n = index; }while(0)
  80 #define KMP_ADD_DUP(ctx,src,v,s) do{ *v = 0; }while(0)
  81 #define KMP_WANT_CLEANUP
  82 #define KMP_WANT_SEARCH
  83 #define KMPS_EXTRA_ARGS uns *cnt, uns *sum
  84 #define KMPS_FOUND(ctx,src,s) do{ ASSERT(cnt[s.out->n]); cnt[s.out->n]--; sum[0]--; }while(0)
  85 #include "lib/kmp-new.h"
  86
  87 static void
  88 test3(void)
  89 {
  90   log(L_INFO, "Running test3");
  91   struct mempool *pool = mp_new(1024);
  92   for (uns testn = 0; testn < 100; testn++)
  93   {
  94     mp_flush(pool);
  95     uns n = random_max(100);
  96     byte *s[n];
  97     struct kmp3_context ctx;
  98     kmp3_init(&ctx);
  99     for (uns i = 0; i < n; i++)
 100       {
 101         uns m = random_max(10);
 102         s[i] = mp_alloc(pool, m + 1);
 103         for (uns j = 0; j < m; j++)
 104           s[i][j] = 'a' + random_max(3);
 105         s[i][m] = 0;
 106         kmp3_add(&ctx, s[i], i);
 107       }
 108     kmp3_build(&ctx);
 109     for (uns i = 0; i < 10; i++)
 110       {
 111         uns m = random_max(100);
 112         byte b[m + 1];
 113         for (uns j = 0; j < m; j++)
 114           b[j] = 'a' + random_max(4);
 115         b[m] = 0;
 116         uns cnt[n], sum = 0;
 117         for (uns j = 0; j < n; j++)
 118           {
 119             cnt[j] = 0;
 120             if (*s[j])
 121               for (uns k = 0; k < m; k++)
 122                 if (!strncmp(b + k, s[j], strlen(s[j])))
 123                   cnt[j]++, sum++;
 124           }
 125         kmp3_search(&ctx, b, cnt, &sum);
 126         ASSERT(sum == 0);
 127       }
 128     kmp3_cleanup(&ctx);
 129   }
 130   mp_delete(pool);
 131 }
 132
 133 int
 134 main(void)
 135 {
 136   test1();
 137   test2();
 138   test3();
 139   return 0;
 140 }