From e6b837d6612b501ac69ec5c2cc701417c03cff81 Mon Sep 17 00:00:00 2001
From: Pavel Charvat <pavel.charvat@netcentrum.cz>
Date: Tue, 18 Apr 2006 13:26:44 +0200
Subject: [PATCH] small KMP fixes

---
 lib/kmp-new.h    | 16 +++++++--------
 lib/kmp-search.h |  4 ++--
 lib/kmp-test.c   | 52 +++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 59 insertions(+), 13 deletions(-)

diff --git a/lib/kmp-new.h b/lib/kmp-new.h
index 15c15ae3..e9ae2fad 100644
--- a/lib/kmp-new.h
+++ b/lib/kmp-new.h
@@ -114,7 +114,7 @@ P(hash_eq) (struct P(hash_table) *t UNUSED, struct P(state) *f1, P(char_t) c1, s
 static inline void
 P(hash_init_key) (struct P(hash_table) *t UNUSED, struct P(state) *s, struct P(state) *f, P(char_t) c)
 {
-  memset(s, 0, sizeof(*s));
+  bzero(s, sizeof(*s));
   s->from = f;
   s->c = c;
   s->next = f->back; /* the pointers hold the link-list of sons... change in build() */
@@ -157,9 +157,9 @@ typedef byte *P(source_t);
 
 #ifdef KMP_GET_CHAR
 static inline int
-P(get_char) (struct P(context) *ctx, P(source_t) *src, P(char_t) *c)
+P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src UNUSED, P(char_t) *c UNUSED)
 {
-  return KMP_GET_CHAR(ctx, *src, *c);
+  return KMP_GET_CHAR(ctx, (*src), (*c));
 }
 #else
 #  if defined(KMP_USE_UTF8)
@@ -179,7 +179,7 @@ P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c)
   uns cc;
   *src = (byte *)utf8_get(*src, &cc);
 # ifdef KMP_ONLYALPHA
-  if (unlikely(!cc)) {}
+  if (!cc) {}
   else if (!Ualpha(cc))
     cc = P(control_char)();
   else
@@ -195,7 +195,7 @@ P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c)
 # else
   uns cc = *(*src)++;
 # ifdef KMP_ONLYALPHA
-  if (unlikely(!cc)) {}
+  if (!cc) {}
   else if (!Calpha(cc))
     cc = P(control_char)();
   else
@@ -224,7 +224,7 @@ P(add) (struct P(context) *ctx, P(source_t) src
 # endif
 
   P(char_t) c;
-  if (unlikely(!P(get_char)(ctx, &src, &c)))
+  if (!P(get_char)(ctx, &src, &c))
     return NULL;
   struct P(state) *p = &ctx->null, *s;
   uns len = 0;
@@ -236,7 +236,7 @@ P(add) (struct P(context) *ctx, P(source_t) src
 	  {
 	    s = P(hash_new)(&ctx->hash, p, c);
 	    len++;
-	    if (unlikely(!(P(get_char)(ctx, &src, &c))))
+	    if (!(P(get_char)(ctx, &src, &c)))
 	      goto enter_new;
 	    p = s;
 	  }
@@ -266,7 +266,7 @@ enter_new:
 static void
 P(init) (struct P(context) *ctx)
 {
-  memset(ctx, 0, sizeof(*ctx));
+  bzero(ctx, sizeof(*ctx));
   P(hash_init)(&ctx->hash);
 }
 
diff --git a/lib/kmp-search.h b/lib/kmp-search.h
index 3978c847..3452821d 100644
--- a/lib/kmp-search.h
+++ b/lib/kmp-search.h
@@ -123,7 +123,7 @@ P(search) (struct KP(context) *ctx, P(search_source_t) src
 #     endif
 
 #   ifdef KMPS_ADD_CONTROLS    
-    if (unlikely(s.eof))
+    if (s.eof)
       break;
 #   endif    
 
@@ -136,7 +136,7 @@ start_read: ;
 
     do
       {
-	if (unlikely(!KMPS_GET_CHAR(ctx, src, s)))
+	if (!KMPS_GET_CHAR(ctx, src, s))
 	  {
 #           ifdef KMPS_ADD_CONTROLS
 	    if (s.c != KP(control_char)())
diff --git a/lib/kmp-test.c b/lib/kmp-test.c
index fa07f060..bee8d3fa 100644
--- a/lib/kmp-test.c
+++ b/lib/kmp-test.c
@@ -8,13 +8,26 @@
 #define TRACE(x...) do{}while(0)
 #endif
 
+/* TEST1 - multiple searches */
+
 #define KMP_PREFIX(x) GLUE_(kmp1,x)
 #define KMP_WANT_CLEANUP
-#define KMP_WANT_SEARCH
+#include "lib/kmp-new.h"
+#define KMPS_PREFIX(x) GLUE_(kmp1s1,x)
+#define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x)
 #define KMPS_WANT_BEST
 #define KMPS_T uns
 #define KMPS_EXIT(ctx,src,s) do{ return s.best->len; }while(0)
-#include "lib/kmp-new.h"
+#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
+#include "lib/kmp-search.h"
 
 static void
 test1(void)
@@ -26,12 +39,16 @@ test1(void)
   kmp1_add(&ctx, "hoj");
   kmp1_add(&ctx, "aho");
   kmp1_build(&ctx);
-  UNUSED uns best = kmp1_search(&ctx, "asjlahslhalahosjkjhojsas");
+  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);
 }
 
+/* TEST2 - various tracing */
+
 #define KMP_PREFIX(x) GLUE_(kmp2,x)
 #define KMP_USE_UTF8
 #define KMP_TOLOWER
@@ -71,6 +88,8 @@ test2(void)
   kmp2_cleanup(&ctx);
 }
 
+/* TEST3 - random tests */
+
 #define KMP_PREFIX(x) GLUE_(kmp3,x)
 #define KMP_NODE uns
 #define KMP_ADD_EXTRA_ARGS uns index
@@ -130,11 +149,38 @@ test3(void)
   mp_delete(pool);
 }
 
+/* TEST4 - user-defined character type
+ * FIXME: it would need custom compare and hash functions to be really valid */
+
+#define KMP_PREFIX(x) GLUE_(kmp4,x)
+#define KMP_CHAR byte *
+#define KMP_CONTROL_CHAR NULL
+#define KMP_GET_CHAR(ctx,src,c) ({ c = src++; !!*c; })
+#define KMP_WANT_CLEANUP
+#define KMP_WANT_SEARCH
+#define KMPS_FOUND(ctx,src,s) do{ ASSERT(0); }while(0)
+#define KMPS_ADD_CONTROLS
+#define KMPS_MERGE_CONTROLS
+#include "lib/kmp-new.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);
+}
+
 int
 main(void)
 {
   test1();
   test2();
   test3();
+  test4();
   return 0;
 }
-- 
2.39.2