lib/kmp-test.c

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