From 50f5bc89e3c03a0fdf56bf6ab860e437a7731b03 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Thu, 20 Apr 2006 08:58:00 +0200 Subject: [PATCH] Removed previously added parameter {KMP,HASH}_PARAM_POOL from hashtable and KMP... it is not really necessary. Added full support for non-integer character types and custom allocation routines to KMP. --- lib/hashtable.h | 20 +----------- lib/kmp-new.h | 79 ++++++++++++++++++++++++++++++++++-------------- lib/kmp-search.h | 8 ++--- lib/kmp-test.c | 22 ++++++++++++-- 4 files changed, 81 insertions(+), 48 deletions(-) diff --git a/lib/hashtable.h b/lib/hashtable.h index c96f0a61..0419a47c 100644 --- a/lib/hashtable.h +++ b/lib/hashtable.h @@ -93,7 +93,6 @@ * deallocation is not supported by mempools, so delete/remove * will leak pool memory. * HASH_AUTO_POOL=size Create a pool of the given block size automatically. - * HASH_PARAM_POOL Allocate all nodes from mempool given as a parameter to init(). * HASH_ZERO_FILL New entries should be initialized to all zeroes. * HASH_TABLE_ALLOC The hash table itself will be allocated and freed using * the same allocation functions as the nodes instead of @@ -155,7 +154,7 @@ struct P(table) { uns hash_size; uns hash_count, hash_max, hash_min, hash_hard_max; P(bucket) **ht; -#if defined(HASH_AUTO_POOL) || defined(HASH_PARAM_POOL) +#ifdef HASH_AUTO_POOL struct mempool *pool; #endif }; @@ -331,15 +330,6 @@ static inline void P(free) (TAUC void *x UNUSED) { } static inline void P(init_alloc) (TAU) { } static inline void P(cleanup_alloc) (TAU) { } -#elif defined(HASH_PARAM_POOL) -/* Use mempools given as a parameter to init() */ -#include "lib/mempool.h" -static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(T.pool, size); } -static inline void P(free) (TAUC void *x UNUSED) { } -static inline void P(init_alloc) (TAU) { } -static inline void P(cleanup_alloc) (TAU) { } -#define HASH_USE_POOL - #elif defined(HASH_AUTO_POOL) /* Use our own pools */ #include "lib/mempool.h" @@ -402,11 +392,7 @@ static void P(alloc_table) (TAU) T.hash_min = 0; } -#ifndef HASH_PARAM_POOL static void P(init) (TA) -#else -static void P(init) (TAC struct mempool *pool) -#endif { T.hash_count = 0; T.hash_size = HASH_DEFAULT_SIZE; @@ -416,9 +402,6 @@ static void P(init) (TAC struct mempool *pool) T.hash_hard_max = 1 << 28; #endif P(alloc_table)(TT); -#ifdef HASH_PARAM_POOL - T.pool = pool; -#endif P(init_alloc)(TT); } @@ -666,7 +649,6 @@ do { \ #undef HASH_PREFIX #undef HASH_USE_POOL #undef HASH_AUTO_POOL -#undef HASH_PARAM_POOL #undef HASH_WANT_CLEANUP #undef HASH_WANT_DELETE #undef HASH_WANT_FIND diff --git a/lib/kmp-new.h b/lib/kmp-new.h index 741efba9..2ce01b3a 100644 --- a/lib/kmp-new.h +++ b/lib/kmp-new.h @@ -54,6 +54,10 @@ * there can be multiple search variants for a single KMP structure * * KMP_USE_POOL allocates in a given pool + * + * KMP_GIVE_ALLOC + * KMP_GIVE_HASHFN + * KMP_GIVE_EQ */ #ifndef KMP_PREFIX @@ -80,6 +84,8 @@ typedef KMP_NODE P(node_t); typedef struct {} P(node_t); #endif +struct P(context); + struct P(state) { struct P(state) *from; /* state with previous character */ struct P(state) *back; /* backwards edge to the largest shorter state */ @@ -91,7 +97,7 @@ struct P(state) { /* Control char */ static inline P(char_t) -P(control_char) (void) +P(control) (void) { #ifdef KMP_CONTROL_CHAR return KMP_CONTROL_CHAR; @@ -103,18 +109,58 @@ P(control_char) (void) /* User-defined source */ struct P(hash_table); +#define HASH_GIVE_HASHFN +#ifdef KMP_GIVE_HASHFN +static inline uns +P(hash_hash) (struct P(hash_table) *t, struct P(state) *f, P(char_t) c) +{ + return P(hash) ((struct P(context) *) t, f, c); +} +#else static inline uns P(hash_hash) (struct P(hash_table) *t UNUSED, struct P(state) *f, P(char_t) c) { return (((uns)c) << 16) + (uns)(addr_int_t)f; } +#endif + +#ifndef KMP_GIVE_EQ +static inline int +P(eq) (struct P(context) *ctx UNUSED, P(char_t) c1, P(char_t) c2) +{ + return c1 == c2; +} +#endif static inline int -P(hash_eq) (struct P(hash_table) *t UNUSED, struct P(state) *f1, P(char_t) c1, struct P(state) *f2, P(char_t) c2) +P(is_control) (struct P(context) *ctx, P(char_t) c) { - return f1 == f2 && c1 == c2; + return P(eq) (ctx, c, P(control)()); +} + +#define HASH_GIVE_EQ +static inline int +P(hash_eq) (struct P(hash_table) *t, struct P(state) *f1, P(char_t) c1, struct P(state) *f2, P(char_t) c2) +{ + return f1 == f2 && P(eq)((struct P(context) *) t, c1, c2); +} + +#ifdef KMP_GIVE_ALLOC +#define HASH_GIVE_ALLOC +static inline void * +P(hash_alloc) (struct P(hash_table) *t, uns size) +{ + return P(alloc) ((struct P(context) *) t, size); } +static inline void +P(hash_free) (struct P(hash_table) *t, void *ptr) +{ + P(free) ((struct P(context) *) t, ptr); +} +#endif + +#define HASH_GIVE_INIT_KEY 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) { @@ -135,13 +181,8 @@ P(hash_init_key) (struct P(hash_table) *t UNUSED, struct P(state) *s, struct P(s #ifdef KMP_WANT_CLEANUP #define HASH_WANT_CLEANUP #endif -#define HASH_GIVE_HASHFN -#define HASH_GIVE_EQ -#define HASH_GIVE_INIT_KEY #if defined(KMP_USE_POOL) #define HASH_USE_POOL KMP_USE_POOL -#elif defined(KMP_PARAM_POOL) -#define HASH_PARAM_POOL #else #define HASH_AUTO_POOL 4096 #endif @@ -190,7 +231,7 @@ P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c) # ifdef KMP_ONLYALPHA if (!cc) {} else if (!Ualpha(cc)) - cc = P(control_char)(); + cc = P(control)(); else # endif { @@ -206,7 +247,7 @@ P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c) # ifdef KMP_ONLYALPHA if (!cc) {} else if (!Calpha(cc)) - cc = P(control_char)(); + cc = P(control)(); else # endif # ifdef KMP_TOLOWER @@ -276,18 +317,10 @@ enter_new: } static void -P(init) (struct P(context) *ctx -# ifdef KMP_PARAM_POOL - , struct mempool *pool -# endif - ) +P(init) (struct P(context) *ctx) { - bzero(ctx, sizeof(*ctx)); - P(hash_init)(&ctx->hash -# ifdef KMP_PARAM_POOL - , pool -# endif - ); + bzero(&ctx->null, sizeof(struct P(state))); + P(hash_init)(&ctx->hash); } #ifdef KMP_WANT_CLEANUP @@ -369,7 +402,9 @@ P(build) (struct P(context) *ctx) #undef KMP_NO_DUPS #undef KMP_BUILD_STATE #undef KMP_USE_POOL -#undef KMP_PARAM_POOL +#undef KMP_GIVE_ALLOC +#undef KMP_GIVE_HASHFN +#undef KMP_GIVE_EQ #ifdef KMP_WANT_SEARCH # undef KMP_WANT_SEARCH diff --git a/lib/kmp-search.h b/lib/kmp-search.h index c1d540cd..5cfb8ea1 100644 --- a/lib/kmp-search.h +++ b/lib/kmp-search.h @@ -83,7 +83,7 @@ P(search) (struct KP(context) *ctx, P(search_source_t) src s.best = &ctx->null; # endif # ifdef KMPS_ADD_CONTROLS - s.c = KP(control_char)(); + s.c = KP(control)(); s.eof = 0; # else s.c = 0; @@ -139,9 +139,9 @@ start_read: ; if (!KMPS_GET_CHAR(ctx, src, s)) { # ifdef KMPS_ADD_CONTROLS - if (s.c != KP(control_char)()) + if (!KP(is_control)(ctx, s.c)) { - s.c = KP(control_char)(); + s.c = KP(control)(); s.eof = 1; break; } @@ -151,7 +151,7 @@ start_read: ; } while (0 # ifdef KMPS_MERGE_CONTROLS - || (last_c == KP(control_char)() && s.c == KP(control_char)()) + || (KP(is_control)(ctx, last_c) && KP(is_control)(ctx, s.c)) # endif ); } diff --git a/lib/kmp-test.c b/lib/kmp-test.c index 32d95cea..efa29a27 100644 --- a/lib/kmp-test.c +++ b/lib/kmp-test.c @@ -155,16 +155,32 @@ test3(void) 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_context; +struct kmp4_state; + +static inline int +kmp4_eq(struct kmp4_context *ctx UNUSED, byte *a, byte *b) +{ + return (a == b) || (a && b && *a == *b); +} + +static inline uns +kmp4_hash(struct kmp4_context *ctx UNUSED, struct kmp4_state *s, byte *c) +{ + return (c ? (*c << 16) : 0) + (uns)(addr_int_t)s; +} #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_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(ctx,src,s) do{ TRACE("found"); }while(0) #define KMPS_ADD_CONTROLS #define KMPS_MERGE_CONTROLS #include "lib/kmp-new.h" -- 2.39.2