ucw/kmp-test.c

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