From 0a427b3dd9a646348042d47c2027e63c6dbe3b43 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Thu, 20 Apr 2006 12:01:09 +0200 Subject: [PATCH] custom arguments and return type of kmp_search replaced with user's access to struct search --- lib/kmp-search.h | 77 +++++++++++++++++++++++------------------------- lib/kmp-test.c | 48 +++++++++++++++--------------- 2 files changed, 61 insertions(+), 64 deletions(-) diff --git a/lib/kmp-search.h b/lib/kmp-search.h index ab276b5a..a2fc9864 100644 --- a/lib/kmp-search.h +++ b/lib/kmp-search.h @@ -24,16 +24,15 @@ * KMPS_GET_CHAR(kmp,src,s) * * KMPS_ADD_CONTROLS add control characters at both ends of the input string - * KMPS_MERGE_CONTROLS merge adjacent control characters to a single one + * KMPS_MERGE_CONTROLS merge adjacent control characters to a single onei + * + * KMPS_VARS * - * KMPS_EXTRA_ARGS extra arguments to the search routine - * KMPS_EXTRA_VAR extra user-defined structure in search structures * KMPS_INIT(kmp,src,s) * KMPS_EXIT(kmp,src,s) + * KMPS_STEP(kmp,src,s) * KMPS_FOUND(kmp,src,s) * KMPS_FOUND_CHAIN(kmp,src,s) - * KMPS_STEP(kmp,src,s) - * KMPS_T * * KMPS_WANT_BEST */ @@ -48,7 +47,7 @@ typedef KP(source_t) P(search_source_t); #endif #ifndef KMPS_GET_CHAR -#define KMPS_GET_CHAR(kmp,src,s) ({ KP(get_char)(kmp, &src, &s.c); }) +#define KMPS_GET_CHAR(kmp,src,s) ({ KP(get_char)(kmp, &src, &s->c); }) #endif struct P(search) { @@ -58,35 +57,28 @@ struct P(search) { struct KP(state) *best; /* longest match */ # endif KP(char_t) c; /* last character */ -# ifdef KMPS_EXTRA_VAR - KMPS_EXTRA_VAR v; /* user-defined */ -# endif # ifdef KMPS_ADD_CONTROLS uns eof; # endif +# ifdef KMPS_VARS + struct { + KMPS_VARS + } u; /* user-defined */ +# endif }; -#ifdef KMPS_T -static KMPS_T -#else static void -#endif -P(search) (struct KP(struct) *kmp, P(search_source_t) src -# ifdef KMPS_EXTRA_ARGS - , KMPS_EXTRA_ARGS -# endif -) +P(search) (struct KP(struct) *kmp, struct P(search) *s, P(search_source_t) src) { - struct P(search) s; - s.s = &kmp->null; + s->s = &kmp->null; # ifdef KMPS_WANT_BEST - s.best = &kmp->null; + s->best = &kmp->null; # endif # ifdef KMPS_ADD_CONTROLS - s.c = KP(control)(); - s.eof = 0; + s->c = KP(control)(); + s->eof = 0; # else - s.c = 0; + s->c = 0; # endif # ifdef KMPS_INIT { KMPS_INIT(kmp, src, s); } @@ -96,20 +88,20 @@ P(search) (struct KP(struct) *kmp, P(search_source_t) src #endif for (;;) { - for (struct KP(state) *t = s.s; t && !(s.s = KP(hash_find)(&kmp->hash, t, s.c)); t = t->back); - s.s = s.s ? : &kmp->null; + for (struct KP(state) *t = s->s; t && !(s->s = KP(hash_find)(&kmp->hash, t, s->c)); t = t->back); + s->s = s->s ? : &kmp->null; # ifdef KMPS_STEP { KMPS_STEP(kmp, src, s); } # endif # if defined(KMPS_FOUND) || defined(KMPS_FOUND_CHAIN) || defined(KMPS_WANT_BEST) - s.out = s.s->len ? s.s : s.s->next; - if (s.out) + s->out = s->s->len ? s->s : s->s->next; + if (s->out) { # ifdef KMPS_WANT_BEST - if (s.out->len > s.best->len) - s.best = s.out; + if (s->out->len > s->best->len) + s->best = s->out; # endif #ifdef KMPS_FOUND_CHAIN { KMPS_FOUND_CHAIN(kmp, src, s); } @@ -117,13 +109,13 @@ P(search) (struct KP(struct) *kmp, P(search_source_t) src # ifdef KMPS_FOUND do { KMPS_FOUND(kmp, src, s); } - while (s.out = s.out->next); + while (s->out = s->out->next); # endif } # endif # ifdef KMPS_ADD_CONTROLS - if (s.eof) + if (s->eof) break; # endif @@ -131,7 +123,7 @@ P(search) (struct KP(struct) *kmp, P(search_source_t) src start_read: ; # endif # ifdef KMPS_MERGE_CONTROLS - KP(char_t) last_c = s.c; + KP(char_t) last_c = s->c; # endif do @@ -139,10 +131,10 @@ start_read: ; if (!KMPS_GET_CHAR(kmp, src, s)) { # ifdef KMPS_ADD_CONTROLS - if (!KP(is_control)(kmp, s.c)) + if (!KP(is_control)(kmp, s->c)) { - s.c = KP(control)(); - s.eof = 1; + s->c = KP(control)(); + s->eof = 1; break; } # endif @@ -151,7 +143,7 @@ start_read: ; } while (0 # ifdef KMPS_MERGE_CONTROLS - || (KP(is_control)(kmp, last_c) && KP(is_control)(kmp, s.c)) + || (KP(is_control)(kmp, last_c) && KP(is_control)(kmp, s->c)) # endif ); } @@ -161,6 +153,13 @@ exit: ; # endif } +static inline void +P(run) (struct KP(struct) *kmp, P(search_source_t) src) +{ + struct P(search) search; + P(search)(kmp, &search, src); +} + #undef P #undef KMPS_PREFIX #undef KMPS_KMP_PREFIX @@ -168,12 +167,10 @@ exit: ; #undef KMPS_GET_CHAR #undef KMPS_ADD_CONTROLS #undef KMPS_MERGE_CONTROLS -#undef KMPS_EXTRA_ARGS -#undef KMPS_EXTRA_VAR +#undef KMPS_VARS #undef KMPS_INIT #undef KMPS_EXIT #undef KMPS_FOUND #undef KMPS_FOUND_CHAIN #undef KMPS_STEP -#undef KMPS_T #undef KMPS_WANT_BEST diff --git a/lib/kmp-test.c b/lib/kmp-test.c index 63a5974e..6156edbf 100644 --- a/lib/kmp-test.c +++ b/lib/kmp-test.c @@ -22,17 +22,12 @@ #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(kmp,src,s) do{ return s.best->len; }while(0) #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(kmp,src,s) do{ s.v = 0; }while(0) -#define KMPS_T uns -#define KMPS_FOUND(kmp,src,s) do{ s.v++; }while(0) -#define KMPS_EXIT(kmp,src,s) do{ return s.v; }while(0) -#define KMPS_WANT_BEST +#define KMPS_VARS uns count; +#define KMPS_INIT(kmp,src,s) do{ s->u.count = 0; }while(0) +#define KMPS_FOUND(kmp,src,s) do{ s->u.count++; }while(0) #include "lib/kmp-search.h" static void @@ -45,11 +40,13 @@ test1(void) kmp1_add(&kmp, "hoj"); kmp1_add(&kmp, "aho"); kmp1_build(&kmp); - UNUSED uns best = kmp1s1_search(&kmp, "asjlahslhalahosjkjhojsas"); - TRACE("Best match has %d characters", best); - ASSERT(best == 3); - UNUSED uns count = kmp1s2_search(&kmp, "asjlahslhalahojsjkjhojsas"); - ASSERT(count == 4); + 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"); + ASSERT(s2.u.count == 4); kmp1_cleanup(&kmp); } @@ -71,9 +68,9 @@ test1(void) #define KMPS_ADD_CONTROLS #define KMPS_MERGE_CONTROLS #define KMPS_WANT_BEST -#define KMPS_FOUND(kmp,src,s) do{ TRACE("String %s with id %d found", s.out->u.str, s.out->u.id); }while(0) -#define KMPS_STEP(kmp,src,s) do{ TRACE("Got to state %p after reading %d", s.s, s.c); }while(0) -#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) do{ TRACE("String %s with id %d found", s->out->u.str, s->out->u.id); }while(0) +#define KMPS_STEP(kmp,src,s) do{ TRACE("Got to state %p after reading %d", s->s, s->c); }while(0) +#define KMPS_EXIT(kmp,src,s) do{ if (s->best->len) TRACE("Best match is %s", s->best->u.str); } while(0) #include "lib/kmp.h" static void @@ -90,7 +87,7 @@ test2(void) kmp2_add(&kmp, "aba", 5); kmp2_add(&kmp, "pěl", 5); kmp2_build(&kmp); - kmp2_search(&kmp, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla"); + kmp2_run(&kmp, "Šíleně žluťoučký kůň úpěl ďábelské ódy labababaks sdahojdhsaladsjhla"); kmp2_cleanup(&kmp); } @@ -105,8 +102,8 @@ test2(void) #define KMP_ADD_DUP(kmp,src,v,s) do{ *v = 0; }while(0) #define KMP_WANT_CLEANUP #define KMP_WANT_SEARCH -#define KMPS_EXTRA_ARGS uns *cnt, uns *sum -#define KMPS_FOUND(kmp,src,s) do{ ASSERT(cnt[s.out->u.index]); cnt[s.out->u.index]--; sum[0]--; }while(0) +#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 @@ -138,17 +135,20 @@ 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(&kmp, b, cnt, &sum); - ASSERT(sum == 0); + kmp3_search(&kmp, &search, b); + ASSERT(search.u.sum == 0); } kmp3_cleanup(&kmp); } @@ -193,7 +193,7 @@ test4(void) kmp4_init(&kmp); kmp4_add(&kmp, "ahoj"); kmp4_build(&kmp); - kmp4_search(&kmp, "djdhaskjdahoahaahojojshdaksjahdahojskj"); + kmp4_run(&kmp, "djdhaskjdahoahaahojojshdaksjahdahojskj"); kmp4_cleanup(&kmp); } -- 2.39.5