2 #include "lib/mempool.h"
6 #define TRACE(x...) do{log(L_DEBUG, x);}while(0)
8 #define TRACE(x...) do{}while(0)
11 #define KMP_PREFIX(x) GLUE_(kmp1,x)
12 #define KMP_WANT_CLEANUP
13 #define KMP_WANT_SEARCH
14 #define KMPS_WANT_BEST
16 #define KMPS_EXIT(ctx,src,s) do{ return s.best->len; }while(0)
17 #include "lib/kmp-new.h"
22 log(L_INFO, "Running test1");
23 struct kmp1_context ctx;
25 kmp1_add(&ctx, "ahoj");
26 kmp1_add(&ctx, "hoj");
27 kmp1_add(&ctx, "aho");
29 UNUSED uns best = kmp1_search(&ctx, "asjlahslhalahosjkjhojsas");
30 TRACE("Best match has %d characters", best);
35 #define KMP_PREFIX(x) GLUE_(kmp2,x)
39 #define KMP_NODE struct { byte *str; uns id; }
40 #define KMP_ADD_EXTRA_ARGS uns id
41 #define KMP_ADD_EXTRA_VAR byte *
42 #define KMP_ADD_INIT(ctx,src,var) do{ var = src; }while(0)
43 #define KMP_ADD_NEW(ctx,src,var,state) do{ TRACE("Inserting string %s with id %d", var, id); \
44 state->n.str = var; state->n.id = id; }while(0)
45 #define KMP_ADD_DUP(ctx,src,var,state) do{ TRACE("String %s already inserted", var); }while(0)
46 #define KMP_WANT_CLEANUP
47 #define KMP_WANT_SEARCH
48 #define KMPS_ADD_CONTROLS
49 #define KMPS_MERGE_CONTROLS
50 #define KMPS_WANT_BEST
51 #define KMPS_FOUND(ctx,src,s) do{ TRACE("String %s with id %d found", s.out->n.str, s.out->n.id); }while(0)
52 #define KMPS_STEP(ctx,src,s) do{ TRACE("Got to state %p after reading %d", s.s, s.c); }while(0)
53 #define KMPS_EXIT(ctx,src,s) do{ if (s.best->len) TRACE("Best match is %s", s.best->n.str); } while(0)
54 #include "lib/kmp-new.h"
59 log(L_INFO, "Running test2");
60 struct kmp2_context ctx;
62 kmp2_add(&ctx, "ahoj", 1);
63 kmp2_add(&ctx, "ahoj", 2);
64 kmp2_add(&ctx, "hoj", 3);
65 kmp2_add(&ctx, "aho", 4);
66 kmp2_add(&ctx, "aba", 5);
67 kmp2_add(&ctx, "aba", 5);
68 kmp2_add(&ctx, "pěl", 5);
70 kmp2_search(&ctx, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla");
74 #define KMP_PREFIX(x) GLUE_(kmp3,x)
76 #define KMP_ADD_EXTRA_ARGS uns index
77 #define KMP_ADD_EXTRA_VAR byte *
78 #define KMP_ADD_INIT(ctx,src,v) do{ v = src; }while(0)
79 #define KMP_ADD_NEW(ctx,src,v,s) do{ s->n = index; }while(0)
80 #define KMP_ADD_DUP(ctx,src,v,s) do{ *v = 0; }while(0)
81 #define KMP_WANT_CLEANUP
82 #define KMP_WANT_SEARCH
83 #define KMPS_EXTRA_ARGS uns *cnt, uns *sum
84 #define KMPS_FOUND(ctx,src,s) do{ ASSERT(cnt[s.out->n]); cnt[s.out->n]--; sum[0]--; }while(0)
85 #include "lib/kmp-new.h"
90 log(L_INFO, "Running test3");
91 struct mempool *pool = mp_new(1024);
92 for (uns testn = 0; testn < 100; testn++)
95 uns n = random_max(100);
97 struct kmp3_context ctx;
99 for (uns i = 0; i < n; i++)
101 uns m = random_max(10);
102 s[i] = mp_alloc(pool, m + 1);
103 for (uns j = 0; j < m; j++)
104 s[i][j] = 'a' + random_max(3);
106 kmp3_add(&ctx, s[i], i);
109 for (uns i = 0; i < 10; i++)
111 uns m = random_max(100);
113 for (uns j = 0; j < m; j++)
114 b[j] = 'a' + random_max(4);
117 for (uns j = 0; j < n; j++)
121 for (uns k = 0; k < m; k++)
122 if (!strncmp(b + k, s[j], strlen(s[j])))
125 kmp3_search(&ctx, b, cnt, &sum);