]> mj.ucw.cz Git - libucw.git/blob - lib/kmp-test.c
Removed KMP_ADD_EXTRA_VAR and some useless parenteses.
[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 #include "lib/kmp-search.h"
26 #define KMPS_PREFIX(x) GLUE_(kmp1s2,x)
27 #define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x)
28 #define KMPS_VARS uns count;
29 #define KMPS_INIT(kmp,src,s) s->u.count = 0;
30 #define KMPS_FOUND(kmp,src,s) s->u.count++;
31 #include "lib/kmp-search.h"
32
33 static void
34 test1(void)
35 {
36   TRACE("Running test1");
37   struct kmp1_struct kmp;
38   kmp1_init(&kmp);
39   kmp1_add(&kmp, "ahoj");
40   kmp1_add(&kmp, "hoj");
41   kmp1_add(&kmp, "aho");
42   kmp1_build(&kmp);
43   struct kmp1s1_search s1;
44   kmp1s1_search(&kmp, &s1, "asjlahslhalahosjkjhojsas");
45   TRACE("Best match has %d characters", s1.best->len);
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 /* TEST2 - various tracing */
54
55 #define KMP_PREFIX(x) GLUE_(kmp2,x)
56 #define KMP_USE_UTF8
57 #define KMP_TOLOWER
58 #define KMP_ONLYALPHA
59 #define KMP_STATE_VARS byte *str; uns id;
60 #define KMP_ADD_EXTRA_ARGS uns id
61 #define KMP_VARS byte *start;
62 #define KMP_ADD_INIT(kmp,src) kmp->u.start = src;
63 #define KMP_ADD_NEW(kmp,src,s) do{ TRACE("Inserting string %s with id %d", kmp->u.start, id); \
64   s->u.str = kmp->u.start; s->u.id = id; }while(0)
65 #define KMP_ADD_DUP(kmp,src,s) TRACE("String %s already inserted", kmp->u.start);
66 #define KMP_WANT_CLEANUP
67 #define KMP_WANT_SEARCH
68 #define KMPS_ADD_CONTROLS
69 #define KMPS_MERGE_CONTROLS
70 #define KMPS_WANT_BEST
71 #define KMPS_FOUND(kmp,src,s) TRACE("String %s with id %d found", s->out->u.str, s->out->u.id);
72 #define KMPS_STEP(kmp,src,s) TRACE("Got to state %p after reading %d", s->s, s->c);
73 #define KMPS_EXIT(kmp,src,s) do{ if (s->best->len) TRACE("Best match is %s", s->best->u.str); } while(0)
74 #include "lib/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 /* TEST3 - random tests */
95
96 #define KMP_PREFIX(x) GLUE_(kmp3,x)
97 #define KMP_STATE_VARS uns index;
98 #define KMP_ADD_EXTRA_ARGS uns index
99 #define KMP_VARS byte *start;
100 #define KMP_ADD_INIT(kmp,src) kmp->u.start = src;
101 #define KMP_ADD_NEW(kmp,src,s) s->u.index = index;
102 #define KMP_ADD_DUP(kmp,src,s) *(kmp->u.start) = 0;
103 #define KMP_WANT_CLEANUP
104 #define KMP_WANT_SEARCH
105 #define KMPS_VARS uns sum, *cnt;
106 #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)
107 #include "lib/kmp.h"
108
109 static void
110 test3(void)
111 {
112   TRACE("Running test3");
113   struct mempool *pool = mp_new(1024);
114   for (uns testn = 0; testn < 100; testn++)
115   {
116     mp_flush(pool);
117     uns n = random_max(100);
118     byte *s[n];
119     struct kmp3_struct kmp;
120     kmp3_init(&kmp);
121     for (uns i = 0; i < n; i++)
122       {
123         uns m = random_max(10);
124         s[i] = mp_alloc(pool, m + 1);
125         for (uns j = 0; j < m; j++)
126           s[i][j] = 'a' + random_max(3);
127         s[i][m] = 0;
128         kmp3_add(&kmp, s[i], i);
129       }
130     kmp3_build(&kmp);
131     for (uns i = 0; i < 10; i++)
132       {
133         uns m = random_max(100);
134         byte b[m + 1];
135         for (uns j = 0; j < m; j++)
136           b[j] = 'a' + random_max(4);
137         b[m] = 0;
138         uns cnt[n];
139         struct kmp3_search search;
140         search.u.sum = 0;
141         search.u.cnt = cnt;
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]++, search.u.sum++;
149           }
150         kmp3_search(&kmp, &search, b);
151         ASSERT(search.u.sum == 0);
152       }
153     kmp3_cleanup(&kmp);
154   }
155   mp_delete(pool);
156 }
157
158 /* TEST4 - user-defined character type */
159
160 struct kmp4_struct;
161 struct kmp4_state;
162
163 static inline int
164 kmp4_eq(struct kmp4_struct *kmp 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_struct *kmp 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(kmp,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(kmp,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_struct kmp;
193   kmp4_init(&kmp);
194   kmp4_add(&kmp, "ahoj");
195   kmp4_build(&kmp);
196   kmp4_run(&kmp, "djdhaskjdahoahaahojojshdaksjahdahojskj");
197   kmp4_cleanup(&kmp);
198 }
199
200 int
201 main(void)
202 {
203   test1();
204   test2();
205   test3();
206   test4();
207   return 0;
208 }