From d308e3c0bf17f68cbf62d37136c107cef7438626 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Thu, 20 Apr 2006 14:42:22 +0200 Subject: [PATCH] minor changes to KMP: - added state initializer (KMP_STATE_INIT) - fixed some formatting rules --- lib/kmp-search.h | 26 +++++++++++++------------- lib/kmp-test.c | 24 +++++++++++------------- lib/kmp.h | 6 ++++++ 3 files changed, 30 insertions(+), 26 deletions(-) diff --git a/lib/kmp-search.h b/lib/kmp-search.h index e5049993..4b7c7028 100644 --- a/lib/kmp-search.h +++ b/lib/kmp-search.h @@ -74,18 +74,18 @@ P(search) (struct KP(struct) *kmp, struct P(search) *s, P(search_source_t) src) # ifdef KMPS_WANT_BEST s->best = &kmp->null; # endif -# ifdef KMPS_ADD_CONTROLS +# ifdef KMPS_ADD_CONTROLS s->c = KP(control)(); s->eof = 0; # else s->c = 0; -# endif +# endif # ifdef KMPS_INIT { KMPS_INIT(kmp, src, s); } # endif -# ifndef KMPS_ADD_CONTROLS +# ifndef KMPS_ADD_CONTROLS goto start_read; -#endif +#endif for (;;) { for (struct KP(state) *t = s->s; t && !(s->s = KP(hash_find)(&kmp->hash, t, s->c)); t = t->back); @@ -99,29 +99,29 @@ P(search) (struct KP(struct) *kmp, struct P(search) *s, P(search_source_t) src) s->out = s->s->len ? s->s : s->s->next; if (s->out) { -# ifdef KMPS_WANT_BEST +# ifdef KMPS_WANT_BEST if (s->out->len > s->best->len) s->best = s->out; -# endif - #ifdef KMPS_FOUND_CHAIN +# endif +# ifdef KMPS_FOUND_CHAIN { KMPS_FOUND_CHAIN(kmp, src, s); } # endif # ifdef KMPS_FOUND do { KMPS_FOUND(kmp, src, s); } while (s->out = s->out->next); -# endif +# endif } # endif -# ifdef KMPS_ADD_CONTROLS +# ifdef KMPS_ADD_CONTROLS if (s->eof) break; -# endif +# endif -# ifndef KMPS_ADD_CONTROLS +# ifndef KMPS_ADD_CONTROLS start_read: ; -# endif +# endif # ifdef KMPS_MERGE_CONTROLS KP(char_t) last_c = s->c; # endif @@ -172,5 +172,5 @@ P(run) (struct KP(struct) *kmp, P(search_source_t) src) #undef KMPS_EXIT #undef KMPS_FOUND #undef KMPS_FOUND_CHAIN -#undef KMPS_STEP #undef KMPS_WANT_BEST +#undef KMPS_STEP diff --git a/lib/kmp-test.c b/lib/kmp-test.c index 4f8890ae..28ea6d50 100644 --- a/lib/kmp-test.c +++ b/lib/kmp-test.c @@ -22,12 +22,13 @@ #define KMPS_PREFIX(x) GLUE_(kmp1s1,x) #define KMPS_KMP_PREFIX(x) GLUE_(kmp1,x) #define KMPS_WANT_BEST +#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_VARS uns count; -#define KMPS_INIT(kmp,src,s) s->u.count = 0; -#define KMPS_FOUND(kmp,src,s) s->u.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 @@ -42,7 +43,6 @@ test1(void) kmp1_build(&kmp); struct kmp1s1_search s1; kmp1s1_search(&kmp, &s1, "asjlahslhalahosjkjhojsas"); - TRACE("Best match has %d characters", s1.best->len); ASSERT(s1.best->len == 3); struct kmp1s2_search s2; kmp1s2_search(&kmp, &s2, "asjlahslhalahojsjkjhojsas"); @@ -59,18 +59,16 @@ test1(void) #define KMP_STATE_VARS byte *str; uns id; #define KMP_ADD_EXTRA_ARGS uns id #define KMP_VARS byte *start; -#define KMP_ADD_INIT(kmp,src) kmp->u.start = src; +#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_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(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); -#define KMPS_EXIT(kmp,src,s) do{ if (s->best->len) TRACE("Best match is %s", s->best->u.str); } while(0) +#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 @@ -97,9 +95,9 @@ test2(void) #define KMP_STATE_VARS uns index; #define KMP_ADD_EXTRA_ARGS uns index #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_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_VARS uns sum, *cnt; @@ -180,7 +178,7 @@ kmp4_hash(struct kmp4_struct *kmp UNUSED, struct kmp4_state *s, byte *c) #define KMP_GIVE_EQ #define KMP_WANT_CLEANUP #define KMP_WANT_SEARCH -#define KMPS_FOUND(kmp,src,s) do{ TRACE("found"); }while(0) +#define KMPS_FOUND(kmp,src,s) TRACE("found") #define KMPS_ADD_CONTROLS #define KMPS_MERGE_CONTROLS #include "lib/kmp.h" diff --git a/lib/kmp.h b/lib/kmp.h index d4836988..aa97aa68 100644 --- a/lib/kmp.h +++ b/lib/kmp.h @@ -42,6 +42,7 @@ * KMP_ADD_INIT(kmp,src) * KMP_ADD_NEW(kmp,src,s) * KMP_ADD_DUP(kmp,src,s) + * KMP_INIT_STATE(kmp,s) initialize new state (called before KMP_ADD_{NEW,DUP}) * * Parameters to build(): * KMP_BUILD_STATE(kmp,s) called for all states (including null) in order of non-decreasing tree depth @@ -167,6 +168,10 @@ 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) { bzero(s, sizeof(*s)); +# ifdef KMP_INIT_STATE + struct P(struct) *kmp = (struct P(struct) *)t; + { KMP_INIT_STATE(kmp, s); } +# endif s->from = f; s->c = c; s->next = f->back; /* the pointers hold the link-list of sons... changed in build() */ @@ -396,6 +401,7 @@ P(build) (struct P(struct) *kmp) #undef KMP_ADD_INIT #undef KMP_ADD_NEW #undef KMP_ADD_DUP +#undef KMP_INIT_STATE #undef KMP_BUILD_STATE #undef KMP_USE_POOL #undef KMP_GIVE_ALLOC -- 2.39.2