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 /* TEST1 - multiple searches */
  12
  13 #define KMP_PREFIX(x) GLUE_(kmp1,x)
  14 #define KMP_WANT_CLEANUP
  15 #include "lib/kmp-new.h"
  16 #define KMPS_PREFIX(x) GLUE_(kmp1s1,x)
  17 #define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x)
  18 #define KMPS_WANT_BEST
  19 #define KMPS_T uns
  20 #define KMPS_EXIT(ctx,src,s) do{ return s.best->len; }while(0)
  21 #include "lib/kmp-search.h"
  22 #define KMPS_PREFIX(x) GLUE_(kmp1s2,x)
  23 #define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x)
  24 #define KMPS_EXTRA_VAR uns
  25 #define KMPS_INIT(ctx,src,s) do{ s.v = 0; }while(0)
  26 #define KMPS_T uns
  27 #define KMPS_FOUND(ctx,src,s) do{ s.v++; }while(0)
  28 #define KMPS_EXIT(ctx,src,s) do{ return s.v; }while(0)
  29 #define KMPS_WANT_BEST
  30 #include "lib/kmp-search.h"
  31
  32 static void
  33 test1(void)
  34 {
  35   log(L_INFO, "Running test1");
  36   struct kmp1_context ctx;
  37   kmp1_init(&ctx);
  38   kmp1_add(&ctx, "ahoj");
  39   kmp1_add(&ctx, "hoj");
  40   kmp1_add(&ctx, "aho");
  41   kmp1_build(&ctx);
  42   UNUSED uns best = kmp1s1_search(&ctx, "asjlahslhalahosjkjhojsas");
  43   TRACE("Best match has %d characters", best);
  44   ASSERT(best == 3);
  45   UNUSED uns count = kmp1s2_search(&ctx, "asjlahslhalahojsjkjhojsas");
  46   ASSERT(count == 4);
  47   kmp1_cleanup(&ctx);
  48 }
  49
  50 /* TEST2 - various tracing */
  51
  52 #define KMP_PREFIX(x) GLUE_(kmp2,x)
  53 #define KMP_USE_UTF8
  54 #define KMP_TOLOWER
  55 #define KMP_ONLYALPHA
  56 #define KMP_NODE struct { byte *str; uns id; }
  57 #define KMP_ADD_EXTRA_ARGS uns id
  58 #define KMP_ADD_EXTRA_VAR byte *
  59 #define KMP_ADD_INIT(ctx,src,var) do{ var = src; }while(0)
  60 #define KMP_ADD_NEW(ctx,src,var,state) do{ TRACE("Inserting string %s with id %d", var, id); \
  61   state->n.str = var; state->n.id = id; }while(0)
  62 #define KMP_ADD_DUP(ctx,src,var,state) do{ TRACE("String %s already inserted", var); }while(0)
  63 #define KMP_WANT_CLEANUP
  64 #define KMP_WANT_SEARCH
  65 #define KMPS_ADD_CONTROLS
  66 #define KMPS_MERGE_CONTROLS
  67 #define KMPS_WANT_BEST
  68 #define KMPS_FOUND(ctx,src,s) do{ TRACE("String %s with id %d found", s.out->n.str, s.out->n.id); }while(0)
  69 #define KMPS_STEP(ctx,src,s) do{ TRACE("Got to state %p after reading %d", s.s, s.c); }while(0)
  70 #define KMPS_EXIT(ctx,src,s) do{ if (s.best->len) TRACE("Best match is %s", s.best->n.str); } while(0)
  71 #include "lib/kmp-new.h"
  72
  73 static void
  74 test2(void)
  75 {
  76   log(L_INFO, "Running test2");
  77   struct kmp2_context ctx;
  78   kmp2_init(&ctx);
  79   kmp2_add(&ctx, "ahoj", 1);
  80   kmp2_add(&ctx, "ahoj", 2);
  81   kmp2_add(&ctx, "hoj", 3);
  82   kmp2_add(&ctx, "aho", 4);
  83   kmp2_add(&ctx, "aba", 5);
  84   kmp2_add(&ctx, "aba", 5);
  85   kmp2_add(&ctx, "pěl", 5);
  86   kmp2_build(&ctx);
  87   kmp2_search(&ctx, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla");
  88   kmp2_cleanup(&ctx);
  89 }
  90
  91 /* TEST3 - random tests */
  92
  93 #define KMP_PREFIX(x) GLUE_(kmp3,x)
  94 #define KMP_NODE uns
  95 #define KMP_ADD_EXTRA_ARGS uns index
  96 #define KMP_ADD_EXTRA_VAR byte *
  97 #define KMP_ADD_INIT(ctx,src,v) do{ v = src; }while(0)
  98 #define KMP_ADD_NEW(ctx,src,v,s) do{ s->n = index; }while(0)
  99 #define KMP_ADD_DUP(ctx,src,v,s) do{ *v = 0; }while(0)
 100 #define KMP_WANT_CLEANUP
 101 #define KMP_WANT_SEARCH
 102 #define KMPS_EXTRA_ARGS uns *cnt, uns *sum
 103 #define KMPS_FOUND(ctx,src,s) do{ ASSERT(cnt[s.out->n]); cnt[s.out->n]--; sum[0]--; }while(0)
 104 #include "lib/kmp-new.h"
 105
 106 static void
 107 test3(void)
 108 {
 109   log(L_INFO, "Running test3");
 110   struct mempool *pool = mp_new(1024);
 111   for (uns testn = 0; testn < 100; testn++)
 112   {
 113     mp_flush(pool);
 114     uns n = random_max(100);
 115     byte *s[n];
 116     struct kmp3_context ctx;
 117     kmp3_init(&ctx);
 118     for (uns i = 0; i < n; i++)
 119       {
 120         uns m = random_max(10);
 121         s[i] = mp_alloc(pool, m + 1);
 122         for (uns j = 0; j < m; j++)
 123           s[i][j] = 'a' + random_max(3);
 124         s[i][m] = 0;
 125         kmp3_add(&ctx, s[i], i);
 126       }
 127     kmp3_build(&ctx);
 128     for (uns i = 0; i < 10; i++)
 129       {
 130         uns m = random_max(100);
 131         byte b[m + 1];
 132         for (uns j = 0; j < m; j++)
 133           b[j] = 'a' + random_max(4);
 134         b[m] = 0;
 135         uns cnt[n], sum = 0;
 136         for (uns j = 0; j < n; j++)
 137           {
 138             cnt[j] = 0;
 139             if (*s[j])
 140               for (uns k = 0; k < m; k++)
 141                 if (!strncmp(b + k, s[j], strlen(s[j])))
 142                   cnt[j]++, sum++;
 143           }
 144         kmp3_search(&ctx, b, cnt, &sum);
 145         ASSERT(sum == 0);
 146       }
 147     kmp3_cleanup(&ctx);
 148   }
 149   mp_delete(pool);
 150 }
 151
 152 /* TEST4 - user-defined character type
 153  * FIXME: it would need custom compare and hash functions to be really valid */
 154
 155 #define KMP_PREFIX(x) GLUE_(kmp4,x)
 156 #define KMP_CHAR byte *
 157 #define KMP_CONTROL_CHAR NULL
 158 #define KMP_GET_CHAR(ctx,src,c) ({ c = src++; !!*c; })
 159 #define KMP_WANT_CLEANUP
 160 #define KMP_WANT_SEARCH
 161 #define KMPS_FOUND(ctx,src,s) do{ ASSERT(0); }while(0)
 162 #define KMPS_ADD_CONTROLS
 163 #define KMPS_MERGE_CONTROLS
 164 #include "lib/kmp-new.h"
 165
 166 static void
 167 test4(void)
 168 {
 169   log(L_INFO, "Running test4");
 170   struct kmp4_context ctx;
 171   kmp4_init(&ctx);
 172   kmp4_add(&ctx, "ahoj");
 173   kmp4_build(&ctx);
 174   kmp4_search(&ctx, "djdhaskjdahoahaahojojshdaksjahdahojskj");
 175   kmp4_cleanup(&ctx);
 176 }
 177
 178 int
 179 main(void)
 180 {
 181   test1();
 182   test2();
 183   test3();
 184   test4();
 185   return 0;
 186 }