]> mj.ucw.cz Git - libucw.git/blob - lib/kmp-test.c
Removed old KMP completely
[libucw.git] / 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 }