lib/kmp-new.h

   1 /*
   2  *      Knuth-Morris-Pratt's Substring Search for N given strings
   3  *
   4  *      (c) 1999--2005, Robert Spalek <robert@ucw.cz>
   5  *      (c) 2006, Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      (In fact, the algorithm is usually referred to as Aho-McCorasick,
   8  *      but that's just an extension of KMP to multiple strings.)
   9  */
  10
  11 /*
  12  *  This is not a normal header file, it's a generator of KMP algorithm.
  13  *  Each time you include it with parameters set in the corresponding
  14  *  preprocessor macros, it generates KMP structures and functions
  15  *  with the parameters given.
  16  *
  17  *
  18  *    Basic parameters:
  19  *      KMP_PREFIX(x)           macro to add a name prefix (used on all global names
  20  *                              defined by the KMP generator); mandatory
  21  *
  22  *      KMP_CHAR                alphabet type, the default is u16
  23  *
  24  *      KMP_SOURCE              user-defined text source; KMP_GET_CHAR must
  25  *      KMP_GET_CHAR(ctx,src,c) return next character from the input or zero at the end;
  26  *                              if not defined, zero-terminated array of bytes is used as the input
  27  *
  28  *      KMP_NODE                user-defined data in each state of the automaton
  29  *      KMP_CONTEXT             user-defined data in struct context (a structure describing
  30  *                              the whole automaton)
  31  *
  32  *    Parameters which select how the input is interpreted (if KMP_SOURCE is unset):
  33  *      KMP_USE_ASCII           reads single bytes from the input (default)
  34  *      KMP_USE_UTF8            reads UTF-8 characters from the input (valid UTF-8 needed)
  35  *      KMP_TOLOWER             converts all to lowercase
  36  *      KMP_UNACCENT            removes accents
  37  *      KMP_ONLYALPHA           converts non-alphas to KMP_CONTROL_CHAR
  38  *      KMP_CONTROL_CHAR        special control character (default is ':')
  39  *
  40  *    Parameters controlling add():
  41  *      KMP_ADD_EXTRA_ARGS      extra arguments
  42  *      KMP_ADD_EXTRA_VAR       structure with extra local variables
  43  *      KMP_ADD_INIT(ctx,src,v)
  44  *      KMP_ADD_NEW(ctx,src,v,s)
  45  *      KMP_ADD_DUP(ctx,src,v,s)
  46  *      KMP_NO_DUPS             no support for duplicates
  47  *
  48  *    Parameters to build():
  49  *      KMP_BUILD_STATE(ctx,s)  called for all states (including null) in order of non-decreasing tree depth
  50  *
  51  *    Other parameters:
  52  *      KMP_WANT_CLEANUP        define cleanup()
  53  *      KMP_WANT_SEARCH         includes lib/kmp-search.h with the same prefix;
  54  *                              there can be multiple search variants for a single KMP structure
  55  *
  56  *      KMP_USE_POOL            allocates in a given pool
  57  */
  58
  59 #ifndef KMP_PREFIX
  60 #error Missing KMP_PREFIX
  61 #endif
  62
  63 #include "lib/mempool.h"
  64 #include <alloca.h>
  65 #include <string.h>
  66
  67 #define P(x) KMP_PREFIX(x)
  68
  69 #ifdef KMP_CHAR
  70 typedef KMP_CHAR P(char_t);
  71 #else
  72 typedef u16 P(char_t);
  73 #endif
  74
  75 typedef u32 P(len_t);
  76
  77 #ifdef KMP_NODE
  78 typedef KMP_NODE P(node_t);
  79 #else
  80 typedef struct {} P(node_t);
  81 #endif
  82
  83 struct P(state) {
  84   struct P(state) *from;        /* state with previous character */
  85   struct P(state) *back;        /* backwards edge to the largest shorter state */
  86   struct P(state) *next;        /* largest shorter match */
  87   P(len_t) len;                 /* largest match, zero otherwise */
  88   P(char_t) c;                  /* last character */
  89   P(node_t) n;                  /* user-defined data */
  90 };
  91
  92 /* Control char */
  93 static inline P(char_t)
  94 P(control_char) (void)
  95 {
  96 #ifdef KMP_CONTROL_CHAR
  97   return KMP_CONTROL_CHAR;
  98 #else
  99   return ':';
 100 #endif
 101 }
 102
 103 /* User-defined source */
 104 struct P(hash_table);
 105
 106 static inline uns
 107 P(hash_hash) (struct P(hash_table) *t UNUSED, struct P(state) *f, P(char_t) c)
 108 {
 109   return (((uns)c) << 16) + (uns)(addr_int_t)f;
 110 }
 111
 112 static inline int
 113 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)
 114 {
 115   return f1 == f2 && c1 == c2;
 116 }
 117
 118 static inline void
 119 P(hash_init_key) (struct P(hash_table) *t UNUSED, struct P(state) *s, struct P(state) *f, P(char_t) c)
 120 {
 121   bzero(s, sizeof(*s));
 122   s->from = f;
 123   s->c = c;
 124   s->next = f->back; /* the pointers hold the link-list of sons... changed in build() */
 125   f->back = s;
 126 }
 127
 128 #undef P
 129 #define HASH_PREFIX(x) KMP_PREFIX(GLUE(hash_,x))
 130 #define HASH_NODE struct KMP_PREFIX(state)
 131 #define HASH_KEY_COMPLEX(x) x from, x c
 132 #define HASH_KEY_DECL struct KMP_PREFIX(state) *from, KMP_PREFIX(char_t) c
 133 #define HASH_WANT_NEW
 134 #define HASH_WANT_FIND
 135 #ifdef KMP_WANT_CLEANUP
 136 #define HASH_WANT_CLEANUP
 137 #endif
 138 #define HASH_GIVE_HASHFN
 139 #define HASH_GIVE_EQ
 140 #define HASH_GIVE_INIT_KEY
 141 #if defined(KMP_USE_POOL)
 142 #define HASH_USE_POOL KMP_USE_POOL
 143 #elif defined(KMP_PARAM_POOL)
 144 #define HASH_PARAM_POOL
 145 #else
 146 #define HASH_AUTO_POOL 4096
 147 #endif
 148 #define HASH_CONSERVE_SPACE
 149 #define HASH_TABLE_DYNAMIC
 150 #include "lib/hashtable.h"
 151 #define P(x) KMP_PREFIX(x)
 152
 153 struct P(context) {
 154   struct P(hash_table) hash;            /* hash table of state transitions */
 155   struct P(state) null;                 /* null state */
 156 # ifdef KMP_CONTEXT
 157   KMP_CONTEXT v;                        /* user defined data */
 158 # endif
 159 };
 160
 161 #ifdef KMP_SOURCE
 162 typedef KMP_SOURCE P(source_t);
 163 #else
 164 typedef byte *P(source_t);
 165 #endif
 166
 167 #ifdef KMP_GET_CHAR
 168 static inline int
 169 P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src UNUSED, P(char_t) *c UNUSED)
 170 {
 171   return KMP_GET_CHAR(ctx, (*src), (*c));
 172 }
 173 #else
 174 #  if defined(KMP_USE_UTF8)
 175 #    include "lib/unicode.h"
 176 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER) || defined(KMP_UNACCENT)
 177 #      include "charset/unicat.h"
 178 #    endif
 179 #  elif defined(KMP_USE_ASCII)
 180 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER)
 181 #      include "lib/chartype.h"
 182 #    endif
 183 #  endif
 184 static inline int
 185 P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c)
 186 {
 187 # ifdef KMP_USE_UTF8
 188   uns cc;
 189   *src = (byte *)utf8_get(*src, &cc);
 190 # ifdef KMP_ONLYALPHA
 191   if (!cc) {}
 192   else if (!Ualpha(cc))
 193     cc = P(control_char)();
 194   else
 195 # endif
 196     {
 197 #     ifdef KMP_TOLOWER
 198       cc = Utolower(cc);
 199 #     endif
 200 #     ifdef KMP_UNACCENT
 201       cc = Uunaccent(cc);
 202 #     endif
 203     }
 204 # else
 205   uns cc = *(*src)++;
 206 # ifdef KMP_ONLYALPHA
 207   if (!cc) {}
 208   else if (!Calpha(cc))
 209     cc = P(control_char)();
 210   else
 211 # endif
 212 #   ifdef KMP_TOLOWER
 213     cc = Clocase(cc);
 214 #   endif
 215 #   ifdef KMP_UNACCENT
 216 #   error Do not know how to unaccent ASCII characters
 217 #   endif
 218 # endif
 219   *c = cc;
 220   return !!cc;
 221 }
 222 #endif
 223
 224 static struct P(state) *
 225 P(add) (struct P(context) *ctx, P(source_t) src
 226 #   ifdef KMP_ADD_EXTRA_ARGS
 227     , KMP_ADD_EXTRA_ARGS
 228 #   endif
 229 )
 230 {
 231 # ifdef KMP_ADD_EXTRA_VAR
 232   KMP_ADD_EXTRA_VAR v;
 233 # endif
 234 # ifdef KMP_ADD_INIT
 235   { KMP_ADD_INIT(ctx, src, v); }
 236 # endif
 237
 238   P(char_t) c;
 239   if (!P(get_char)(ctx, &src, &c))
 240     return NULL;
 241   struct P(state) *p = &ctx->null, *s;
 242   uns len = 0;
 243   do
 244     {
 245       s = P(hash_find)(&ctx->hash, p, c);
 246       if (!s)
 247         for (;;)
 248           {
 249             s = P(hash_new)(&ctx->hash, p, c);
 250             len++;
 251             if (!(P(get_char)(ctx, &src, &c)))
 252               goto enter_new;
 253             p = s;
 254           }
 255       p = s;
 256       len++;
 257     }
 258   while (P(get_char)(ctx, &src, &c));
 259 # ifdef KMP_NO_DUPS
 260   ASSERT(!s->len);
 261 # else
 262   if (s->len)
 263     {
 264 #     ifdef KMP_ADD_DUP
 265       { KMP_ADD_DUP(ctx, src, v, s); }
 266 #     endif
 267       return s;
 268     }
 269 # endif
 270 enter_new:
 271   s->len = len;
 272 # ifdef KMP_ADD_NEW
 273   { KMP_ADD_NEW(ctx, src, v, s); }
 274 # endif
 275   return s;
 276 }
 277
 278 static void
 279 P(init) (struct P(context) *ctx
 280 #   ifdef KMP_PARAM_POOL
 281     , struct mempool *pool
 282 #   endif
 283     )
 284 {
 285   bzero(ctx, sizeof(*ctx));
 286   P(hash_init)(&ctx->hash
 287 #     ifdef KMP_PARAM_POOL
 288       , pool
 289 #     endif
 290       );
 291 }
 292
 293 #ifdef KMP_WANT_CLEANUP
 294 static inline void
 295 P(cleanup) (struct P(context) *ctx)
 296 {
 297   P(hash_cleanup)(&ctx->hash);
 298 }
 299 #endif
 300
 301 static inline int
 302 P(empty) (struct P(context) *ctx)
 303 {
 304   return !ctx->hash.hash_count;
 305 }
 306
 307 static inline struct P(state) *
 308 P(chain_start) (struct P(state) *s)
 309 {
 310   return s->len ? s : s->next;
 311 }
 312
 313 static void
 314 P(build) (struct P(context) *ctx)
 315 {
 316   if (P(empty)(ctx))
 317     return;
 318   uns read = 0, write = 0;
 319   struct P(state) *fifo[ctx->hash.hash_count], *null = &ctx->null;
 320   for (struct P(state) *s = null->back; s; s = s->next)
 321     fifo[write++] = s;
 322   null->back = NULL;
 323 # ifdef KMP_BUILD_STATE
 324   { KMP_BUILD_STATE(ctx, null); }
 325 # endif
 326   while (read != write)
 327     {
 328       struct P(state) *s = fifo[read++], *t;
 329       for (t = s->back; t; t = t->next)
 330         fifo[write++] = t;
 331       for (t = s->from->back; 1; t = t->back)
 332         {
 333           if (!t)
 334             {
 335               s->back = null;
 336               s->next = NULL;
 337               break;
 338             }
 339           s->back = P(hash_find)(&ctx->hash, t, s->c);
 340           if (s->back)
 341             {
 342               s->next = s->back->len ? s->back : s->back->next;
 343               break;
 344             }
 345         }
 346 #     ifdef KMP_BUILD_STATE
 347       { KMP_BUILD_STATE(ctx, s); }
 348 #     endif
 349     }
 350 }
 351
 352 #undef P
 353 #undef KMP_CHAR
 354 #undef KMP_SOURCE
 355 #undef KMP_GET_CHAR
 356 #undef KMP_NODE
 357 #undef KMP_CONTEXT
 358 #undef KMP_USE_ASCII
 359 #undef KMP_USE_UTF8
 360 #undef KMP_TOLOWER
 361 #undef KMP_UNACCENT
 362 #undef KMP_ONLYALPHA
 363 #undef KMP_CONTROL_CHAR
 364 #undef KMP_ADD_EXTRA_ARGS
 365 #undef KMP_ADD_EXTRA_VAR
 366 #undef KMP_ADD_INIT
 367 #undef KMP_ADD_NEW
 368 #undef KMP_ADD_DUP
 369 #undef KMP_NO_DUPS
 370 #undef KMP_BUILD_STATE
 371 #undef KMP_USE_POOL
 372 #undef KMP_PARAM_POOL
 373
 374 #ifdef KMP_WANT_SEARCH
 375 #  undef KMP_WANT_SEARCH
 376 #  define KMPS_PREFIX(x) KMP_PREFIX(x)
 377 #  define KMPS_KMP_PREFIX(x) KMP_PREFIX(x)
 378 #  include "lib/kmp-search.h"
 379 #endif
 380
 381 #undef KMP_PREFIX