X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=inline;f=lib%2Fkmp-test.c;h=fcbc96efcff40a7e3997205c76f7207c89611beb;hb=239f3fb07d3b69db82ddb097f16c495c6a289349;hp=bee8d3fadf81ccbb04167540977459f8238d3e0a;hpb=e6b837d6612b501ac69ec5c2cc701417c03cff81;p=libucw.git

diff --git a/lib/kmp-test.c b/lib/kmp-test.c
index bee8d3fa..fcbc96ef 100644
--- a/lib/kmp-test.c
+++ b/lib/kmp-test.c
@@ -1,3 +1,9 @@
+/*
+ *      Test of KMP search
+ *
+ *      (c) 2006, Pavel Charvat <pchar@ucw.cz>
+ */
+
 #include "lib/lib.h"
 #include "lib/mempool.h"
 #include <string.h>
@@ -10,111 +16,106 @@
 
 /* TEST1 - multiple searches */
 
-#define KMP_PREFIX(x) GLUE_(kmp1,x)
+#define KMP_PREFIX(x) kmp1_##x
 #define KMP_WANT_CLEANUP
-#include "lib/kmp-new.h"
-#define KMPS_PREFIX(x) GLUE_(kmp1s1,x)
-#define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x)
+#include "lib/kmp.h"
+#define KMPS_PREFIX(x) kmp1s1_##x
+#define KMPS_KMP_PREFIX(x) kmp1_##x
 #define KMPS_WANT_BEST
-#define KMPS_T uns
-#define KMPS_EXIT(ctx,src,s) do{ return s.best->len; }while(0)
+#define KMPS_EXIT(kmp,src,s) TRACE("Best match has %d characters", s->best->len)
 #include "lib/kmp-search.h"
-#define KMPS_PREFIX(x) GLUE_(kmp1s2,x)
-#define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x)
-#define KMPS_EXTRA_VAR uns
-#define KMPS_INIT(ctx,src,s) do{ s.v = 0; }while(0)
-#define KMPS_T uns
-#define KMPS_FOUND(ctx,src,s) do{ s.v++; }while(0)
-#define KMPS_EXIT(ctx,src,s) do{ return s.v; }while(0)
-#define KMPS_WANT_BEST
+#define KMPS_PREFIX(x) kmp1s2_##x
+#define KMPS_KMP_PREFIX(x) kmp1_##x
+#define KMPS_VARS uns count;
+#define KMPS_INIT(kmp,src,s) s->u.count = 0
+#define KMPS_FOUND(kmp,src,s) s->u.count++
 #include "lib/kmp-search.h"
 
 static void
 test1(void)
 {
-  log(L_INFO, "Running test1");
-  struct kmp1_context ctx;
-  kmp1_init(&ctx);
-  kmp1_add(&ctx, "ahoj");
-  kmp1_add(&ctx, "hoj");
-  kmp1_add(&ctx, "aho");
-  kmp1_build(&ctx);
-  UNUSED uns best = kmp1s1_search(&ctx, "asjlahslhalahosjkjhojsas");
-  TRACE("Best match has %d characters", best);
-  ASSERT(best == 3);
-  UNUSED uns count = kmp1s2_search(&ctx, "asjlahslhalahojsjkjhojsas");
-  ASSERT(count == 4);
-  kmp1_cleanup(&ctx);
+  TRACE("Running test1");
+  struct kmp1_struct kmp;
+  kmp1_init(&kmp);
+  kmp1_add(&kmp, "ahoj");
+  kmp1_add(&kmp, "hoj");
+  kmp1_add(&kmp, "aho");
+  kmp1_build(&kmp);
+  struct kmp1s1_search s1;
+  kmp1s1_search(&kmp, &s1, "asjlahslhalahosjkjhojsas");
+  ASSERT(s1.best->len == 3);
+  struct kmp1s2_search s2;
+  kmp1s2_search(&kmp, &s2, "asjlahslhalahojsjkjhojsas");
+  ASSERT(s2.u.count == 4);
+  kmp1_cleanup(&kmp);
 }
 
 /* TEST2 - various tracing */
 
-#define KMP_PREFIX(x) GLUE_(kmp2,x)
+#define KMP_PREFIX(x) kmp2_##x
 #define KMP_USE_UTF8
 #define KMP_TOLOWER
 #define KMP_ONLYALPHA
-#define KMP_NODE struct { byte *str; uns id; }
+#define KMP_STATE_VARS byte *str; uns id;
 #define KMP_ADD_EXTRA_ARGS uns id
-#define KMP_ADD_EXTRA_VAR byte *
-#define KMP_ADD_INIT(ctx,src,var) do{ var = src; }while(0)
-#define KMP_ADD_NEW(ctx,src,var,state) do{ TRACE("Inserting string %s with id %d", var, id); \
-  state->n.str = var; state->n.id = id; }while(0)
-#define KMP_ADD_DUP(ctx,src,var,state) do{ TRACE("String %s already inserted", var); }while(0)
+#define KMP_VARS byte *start;
+#define KMP_ADD_INIT(kmp,src) kmp->u.start = src
+#define KMP_ADD_NEW(kmp,src,s) do{ TRACE("Inserting string %s with id %d", kmp->u.start, id); \
+  s->u.str = kmp->u.start; s->u.id = id; }while(0)
+#define KMP_ADD_DUP(kmp,src,s) TRACE("String %s already inserted", kmp->u.start)
 #define KMP_WANT_CLEANUP
 #define KMP_WANT_SEARCH
 #define KMPS_ADD_CONTROLS
 #define KMPS_MERGE_CONTROLS
-#define KMPS_WANT_BEST
-#define KMPS_FOUND(ctx,src,s) do{ TRACE("String %s with id %d found", s.out->n.str, s.out->n.id); }while(0)
-#define KMPS_STEP(ctx,src,s) do{ TRACE("Got to state %p after reading %d", s.s, s.c); }while(0)
-#define KMPS_EXIT(ctx,src,s) do{ if (s.best->len) TRACE("Best match is %s", s.best->n.str); } while(0)
-#include "lib/kmp-new.h"
+#define KMPS_FOUND(kmp,src,s) TRACE("String %s with id %d found", s->out->u.str, s->out->u.id)
+#define KMPS_STEP(kmp,src,s) TRACE("Got to state %p after reading %d", s->s, s->c)
+#include "lib/kmp.h"
 
 static void
 test2(void)
 {
-  log(L_INFO, "Running test2");
-  struct kmp2_context ctx;
-  kmp2_init(&ctx);
-  kmp2_add(&ctx, "ahoj", 1);
-  kmp2_add(&ctx, "ahoj", 2);
-  kmp2_add(&ctx, "hoj", 3);
-  kmp2_add(&ctx, "aho", 4);
-  kmp2_add(&ctx, "aba", 5);
-  kmp2_add(&ctx, "aba", 5);
-  kmp2_add(&ctx, "pěl", 5);
-  kmp2_build(&ctx);
-  kmp2_search(&ctx, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla");
-  kmp2_cleanup(&ctx);
+  TRACE("Running test2");
+  struct kmp2_struct kmp;
+  kmp2_init(&kmp);
+  kmp2_add(&kmp, "ahoj", 1);
+  kmp2_add(&kmp, "ahoj", 2);
+  kmp2_add(&kmp, "hoj", 3);
+  kmp2_add(&kmp, "aho", 4);
+  kmp2_add(&kmp, "aba", 5);
+  kmp2_add(&kmp, "aba", 5);
+  kmp2_add(&kmp, "pěl", 5);
+  kmp2_build(&kmp);
+  kmp2_run(&kmp, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla");
+  kmp2_cleanup(&kmp);
 }
 
 /* TEST3 - random tests */
 
-#define KMP_PREFIX(x) GLUE_(kmp3,x)
-#define KMP_NODE uns
+#define KMP_PREFIX(x) kmp3_##x
+#define KMP_STATE_VARS uns index;
 #define KMP_ADD_EXTRA_ARGS uns index
-#define KMP_ADD_EXTRA_VAR byte *
-#define KMP_ADD_INIT(ctx,src,v) do{ v = src; }while(0)
-#define KMP_ADD_NEW(ctx,src,v,s) do{ s->n = index; }while(0)
-#define KMP_ADD_DUP(ctx,src,v,s) do{ *v = 0; }while(0)
+#define KMP_VARS byte *start;
+#define KMP_ADD_INIT(kmp,src) kmp->u.start = src
+#define KMP_ADD_NEW(kmp,src,s) s->u.index = index
+#define KMP_ADD_DUP(kmp,src,s) *(kmp->u.start) = 0
 #define KMP_WANT_CLEANUP
 #define KMP_WANT_SEARCH
-#define KMPS_EXTRA_ARGS uns *cnt, uns *sum
-#define KMPS_FOUND(ctx,src,s) do{ ASSERT(cnt[s.out->n]); cnt[s.out->n]--; sum[0]--; }while(0)
-#include "lib/kmp-new.h"
+#define KMPS_VARS uns sum, *cnt;
+#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)
+#include "lib/kmp.h"
 
 static void
 test3(void)
 {
-  log(L_INFO, "Running test3");
+  TRACE("Running test3");
   struct mempool *pool = mp_new(1024);
   for (uns testn = 0; testn < 100; testn++)
   {
     mp_flush(pool);
     uns n = random_max(100);
     byte *s[n];
-    struct kmp3_context ctx;
-    kmp3_init(&ctx);
+    struct kmp3_struct kmp;
+    kmp3_init(&kmp);
     for (uns i = 0; i < n; i++)
       {
         uns m = random_max(10);
@@ -122,9 +123,9 @@ test3(void)
         for (uns j = 0; j < m; j++)
 	  s[i][j] = 'a' + random_max(3);
         s[i][m] = 0;
-        kmp3_add(&ctx, s[i], i);
+        kmp3_add(&kmp, s[i], i);
       }
-    kmp3_build(&ctx);
+    kmp3_build(&kmp);
     for (uns i = 0; i < 10; i++)
       {
         uns m = random_max(100);
@@ -132,47 +133,66 @@ test3(void)
         for (uns j = 0; j < m; j++)
 	  b[j] = 'a' + random_max(4);
         b[m] = 0;
-        uns cnt[n], sum = 0;
+        uns cnt[n];
+	struct kmp3_search search;
+	search.u.sum = 0;
+	search.u.cnt = cnt;
         for (uns j = 0; j < n; j++)
           {
 	    cnt[j] = 0;
 	    if (*s[j])
 	      for (uns k = 0; k < m; k++)
 	        if (!strncmp(b + k, s[j], strlen(s[j])))
-	          cnt[j]++, sum++;
+	          cnt[j]++, search.u.sum++;
 	  }
-        kmp3_search(&ctx, b, cnt, &sum);
-        ASSERT(sum == 0);
+        kmp3_search(&kmp, &search, b);
+        ASSERT(search.u.sum == 0);
       }
-    kmp3_cleanup(&ctx);
+    kmp3_cleanup(&kmp);
   }
   mp_delete(pool);
 }
 
-/* TEST4 - user-defined character type
- * FIXME: it would need custom compare and hash functions to be really valid */
+/* TEST4 - user-defined character type */
+
+struct kmp4_struct;
+struct kmp4_state;
+
+static inline int
+kmp4_eq(struct kmp4_struct *kmp UNUSED, byte *a, byte *b)
+{
+  return (a == b) || (a && b && *a == *b);
+}
+
+static inline uns
+kmp4_hash(struct kmp4_struct *kmp UNUSED, struct kmp4_state *s, byte *c)
+{
+  return (c ? (*c << 16) : 0) + (uns)(uintptr_t)s;
+}
 
-#define KMP_PREFIX(x) GLUE_(kmp4,x)
+#define KMP_PREFIX(x) kmp4_##x
 #define KMP_CHAR byte *
 #define KMP_CONTROL_CHAR NULL
-#define KMP_GET_CHAR(ctx,src,c) ({ c = src++; !!*c; })
+#define KMP_GET_CHAR(kmp,src,c) ({ c = src++; !!*c; })
+#define KMP_GIVE_HASHFN
+#define KMP_GIVE_EQ
 #define KMP_WANT_CLEANUP
 #define KMP_WANT_SEARCH
-#define KMPS_FOUND(ctx,src,s) do{ ASSERT(0); }while(0)
+#define KMPS_FOUND(kmp,src,s) TRACE("found")
 #define KMPS_ADD_CONTROLS
 #define KMPS_MERGE_CONTROLS
-#include "lib/kmp-new.h"
+#include "lib/kmp.h"
 
 static void
 test4(void)
 {
-  log(L_INFO, "Running test4");
-  struct kmp4_context ctx;
-  kmp4_init(&ctx);
-  kmp4_add(&ctx, "ahoj");
-  kmp4_build(&ctx);
-  kmp4_search(&ctx, "djdhaskjdahoahaahojojshdaksjahdahojskj");
-  kmp4_cleanup(&ctx);
+  TRACE("Running test4");
+  struct kmp4_struct kmp;
+  kmp4_init(&kmp);
+  kmp4_add(&kmp, "ahoj");
+  kmp4_build(&kmp);
+  kmp4_run(&kmp, "djdhaskjdahoahaahojojshdaksjahdahojskj");
+  kmp4_cleanup(&kmp);
 }
 
 int