lib/kmp.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  *      KMP_GIVE_ALLOC
  59  *      KMP_GIVE_HASHFN
  60  *      KMP_GIVE_EQ
  61  */
  62
  63 #ifndef KMP_PREFIX
  64 #error Missing KMP_PREFIX
  65 #endif
  66
  67 #include "lib/mempool.h"
  68 #include <alloca.h>
  69 #include <string.h>
  70
  71 #define P(x) KMP_PREFIX(x)
  72
  73 #ifdef KMP_CHAR
  74 typedef KMP_CHAR P(char_t);
  75 #else
  76 typedef u16 P(char_t);
  77 #endif
  78
  79 typedef u32 P(len_t);
  80
  81 #ifdef KMP_NODE
  82 typedef KMP_NODE P(node_t);
  83 #else
  84 typedef struct {} P(node_t);
  85 #endif
  86
  87 struct P(context);
  88
  89 struct P(state) {
  90   struct P(state) *from;        /* state with previous character */
  91   struct P(state) *back;        /* backwards edge to the largest shorter state */
  92   struct P(state) *next;        /* largest shorter match */
  93   P(len_t) len;                 /* largest match, zero otherwise */
  94   P(char_t) c;                  /* last character */
  95   P(node_t) n;                  /* user-defined data */
  96 };
  97
  98 /* Control char */
  99 static inline P(char_t)
 100 P(control) (void)
 101 {
 102 #ifdef KMP_CONTROL_CHAR
 103   return KMP_CONTROL_CHAR;
 104 #else
 105   return ':';
 106 #endif
 107 }
 108
 109 /* User-defined source */
 110 struct P(hash_table);
 111
 112 #define HASH_GIVE_HASHFN
 113 #ifdef KMP_GIVE_HASHFN
 114 static inline uns
 115 P(hash_hash) (struct P(hash_table) *t, struct P(state) *f, P(char_t) c)
 116 {
 117   return P(hash) ((struct P(context) *) t, f, c);
 118 }
 119 #else
 120 static inline uns
 121 P(hash_hash) (struct P(hash_table) *t UNUSED, struct P(state) *f, P(char_t) c)
 122 {
 123   return (((uns)c) << 16) + (uns)(addr_int_t)f;
 124 }
 125 #endif
 126
 127 #ifndef KMP_GIVE_EQ
 128 static inline int
 129 P(eq) (struct P(context) *ctx UNUSED, P(char_t) c1, P(char_t) c2)
 130 {
 131   return c1 == c2;
 132 }
 133 #endif
 134
 135 static inline int
 136 P(is_control) (struct P(context) *ctx, P(char_t) c)
 137 {
 138   return P(eq) (ctx, c, P(control)());
 139 }
 140
 141 #define HASH_GIVE_EQ
 142 static inline int
 143 P(hash_eq) (struct P(hash_table) *t, struct P(state) *f1, P(char_t) c1, struct P(state) *f2, P(char_t) c2)
 144 {
 145   return f1 == f2 && P(eq)((struct P(context) *) t, c1, c2);
 146 }
 147
 148 #ifdef KMP_GIVE_ALLOC
 149 #define HASH_GIVE_ALLOC
 150 static inline void *
 151 P(hash_alloc) (struct P(hash_table) *t, uns size)
 152 {
 153   return P(alloc) ((struct P(context) *) t, size);
 154 }
 155
 156 static inline void
 157 P(hash_free) (struct P(hash_table) *t, void *ptr)
 158 {
 159   P(free) ((struct P(context) *) t, ptr);
 160 }
 161 #endif
 162
 163 #define HASH_GIVE_INIT_KEY
 164 static inline void
 165 P(hash_init_key) (struct P(hash_table) *t UNUSED, struct P(state) *s, struct P(state) *f, P(char_t) c)
 166 {
 167   bzero(s, sizeof(*s));
 168   s->from = f;
 169   s->c = c;
 170   s->next = f->back; /* the pointers hold the link-list of sons... changed in build() */
 171   f->back = s;
 172 }
 173
 174 #undef P
 175 #define HASH_PREFIX(x) KMP_PREFIX(GLUE(hash_,x))
 176 #define HASH_NODE struct KMP_PREFIX(state)
 177 #define HASH_KEY_COMPLEX(x) x from, x c
 178 #define HASH_KEY_DECL struct KMP_PREFIX(state) *from, KMP_PREFIX(char_t) c
 179 #define HASH_WANT_NEW
 180 #define HASH_WANT_FIND
 181 #ifdef KMP_WANT_CLEANUP
 182 #define HASH_WANT_CLEANUP
 183 #endif
 184 #if defined(KMP_USE_POOL)
 185 #define HASH_USE_POOL KMP_USE_POOL
 186 #else
 187 #define HASH_AUTO_POOL 4096
 188 #endif
 189 #define HASH_CONSERVE_SPACE
 190 #define HASH_TABLE_DYNAMIC
 191 #include "lib/hashtable.h"
 192 #define P(x) KMP_PREFIX(x)
 193
 194 struct P(context) {
 195   struct P(hash_table) hash;            /* hash table of state transitions */
 196   struct P(state) null;                 /* null state */
 197 # ifdef KMP_CONTEXT
 198   KMP_CONTEXT v;                        /* user defined data */
 199 # endif
 200 };
 201
 202 #ifdef KMP_SOURCE
 203 typedef KMP_SOURCE P(source_t);
 204 #else
 205 typedef byte *P(source_t);
 206 #endif
 207
 208 #ifdef KMP_GET_CHAR
 209 static inline int
 210 P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src UNUSED, P(char_t) *c UNUSED)
 211 {
 212   return KMP_GET_CHAR(ctx, (*src), (*c));
 213 }
 214 #else
 215 #  if defined(KMP_USE_UTF8)
 216 #    include "lib/unicode.h"
 217 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER) || defined(KMP_UNACCENT)
 218 #      include "charset/unicat.h"
 219 #    endif
 220 #  elif defined(KMP_USE_ASCII)
 221 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER)
 222 #      include "lib/chartype.h"
 223 #    endif
 224 #  endif
 225 static inline int
 226 P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c)
 227 {
 228 # ifdef KMP_USE_UTF8
 229   uns cc;
 230   *src = (byte *)utf8_get(*src, &cc);
 231 # ifdef KMP_ONLYALPHA
 232   if (!cc) {}
 233   else if (!Ualpha(cc))
 234     cc = P(control)();
 235   else
 236 # endif
 237     {
 238 #     ifdef KMP_TOLOWER
 239       cc = Utolower(cc);
 240 #     endif
 241 #     ifdef KMP_UNACCENT
 242       cc = Uunaccent(cc);
 243 #     endif
 244     }
 245 # else
 246   uns cc = *(*src)++;
 247 # ifdef KMP_ONLYALPHA
 248   if (!cc) {}
 249   else if (!Calpha(cc))
 250     cc = P(control)();
 251   else
 252 # endif
 253 #   ifdef KMP_TOLOWER
 254     cc = Clocase(cc);
 255 #   endif
 256 #   ifdef KMP_UNACCENT
 257 #   error Do not know how to unaccent ASCII characters
 258 #   endif
 259 # endif
 260   *c = cc;
 261   return !!cc;
 262 }
 263 #endif
 264
 265 static struct P(state) *
 266 P(add) (struct P(context) *ctx, P(source_t) src
 267 #   ifdef KMP_ADD_EXTRA_ARGS
 268     , KMP_ADD_EXTRA_ARGS
 269 #   endif
 270 )
 271 {
 272 # ifdef KMP_ADD_EXTRA_VAR
 273   KMP_ADD_EXTRA_VAR v;
 274 # endif
 275 # ifdef KMP_ADD_INIT
 276   { KMP_ADD_INIT(ctx, src, v); }
 277 # endif
 278
 279   P(char_t) c;
 280   if (!P(get_char)(ctx, &src, &c))
 281     return NULL;
 282   struct P(state) *p = &ctx->null, *s;
 283   uns len = 0;
 284   do
 285     {
 286       s = P(hash_find)(&ctx->hash, p, c);
 287       if (!s)
 288         for (;;)
 289           {
 290             s = P(hash_new)(&ctx->hash, p, c);
 291             len++;
 292             if (!(P(get_char)(ctx, &src, &c)))
 293               goto enter_new;
 294             p = s;
 295           }
 296       p = s;
 297       len++;
 298     }
 299   while (P(get_char)(ctx, &src, &c));
 300 # ifdef KMP_NO_DUPS
 301   ASSERT(!s->len);
 302 # else
 303   if (s->len)
 304     {
 305 #     ifdef KMP_ADD_DUP
 306       { KMP_ADD_DUP(ctx, src, v, s); }
 307 #     endif
 308       return s;
 309     }
 310 # endif
 311 enter_new:
 312   s->len = len;
 313 # ifdef KMP_ADD_NEW
 314   { KMP_ADD_NEW(ctx, src, v, s); }
 315 # endif
 316   return s;
 317 }
 318
 319 static void
 320 P(init) (struct P(context) *ctx)
 321 {
 322   bzero(&ctx->null, sizeof(struct P(state)));
 323   P(hash_init)(&ctx->hash);
 324 }
 325
 326 #ifdef KMP_WANT_CLEANUP
 327 static inline void
 328 P(cleanup) (struct P(context) *ctx)
 329 {
 330   P(hash_cleanup)(&ctx->hash);
 331 }
 332 #endif
 333
 334 static inline int
 335 P(empty) (struct P(context) *ctx)
 336 {
 337   return !ctx->hash.hash_count;
 338 }
 339
 340 static inline struct P(state) *
 341 P(chain_start) (struct P(state) *s)
 342 {
 343   return s->len ? s : s->next;
 344 }
 345
 346 static void
 347 P(build) (struct P(context) *ctx)
 348 {
 349   if (P(empty)(ctx))
 350     return;
 351   uns read = 0, write = 0;
 352   struct P(state) *fifo[ctx->hash.hash_count], *null = &ctx->null;
 353   for (struct P(state) *s = null->back; s; s = s->next)
 354     fifo[write++] = s;
 355   null->back = NULL;
 356 # ifdef KMP_BUILD_STATE
 357   { KMP_BUILD_STATE(ctx, null); }
 358 # endif
 359   while (read != write)
 360     {
 361       struct P(state) *s = fifo[read++], *t;
 362       for (t = s->back; t; t = t->next)
 363         fifo[write++] = t;
 364       for (t = s->from->back; 1; t = t->back)
 365         {
 366           if (!t)
 367             {
 368               s->back = null;
 369               s->next = NULL;
 370               break;
 371             }
 372           s->back = P(hash_find)(&ctx->hash, t, s->c);
 373           if (s->back)
 374             {
 375               s->next = s->back->len ? s->back : s->back->next;
 376               break;
 377             }
 378         }
 379 #     ifdef KMP_BUILD_STATE
 380       { KMP_BUILD_STATE(ctx, s); }
 381 #     endif
 382     }
 383 }
 384
 385 #undef P
 386 #undef KMP_CHAR
 387 #undef KMP_SOURCE
 388 #undef KMP_GET_CHAR
 389 #undef KMP_NODE
 390 #undef KMP_CONTEXT
 391 #undef KMP_USE_ASCII
 392 #undef KMP_USE_UTF8
 393 #undef KMP_TOLOWER
 394 #undef KMP_UNACCENT
 395 #undef KMP_ONLYALPHA
 396 #undef KMP_CONTROL_CHAR
 397 #undef KMP_ADD_EXTRA_ARGS
 398 #undef KMP_ADD_EXTRA_VAR
 399 #undef KMP_ADD_INIT
 400 #undef KMP_ADD_NEW
 401 #undef KMP_ADD_DUP
 402 #undef KMP_NO_DUPS
 403 #undef KMP_BUILD_STATE
 404 #undef KMP_USE_POOL
 405 #undef KMP_GIVE_ALLOC
 406 #undef KMP_GIVE_HASHFN
 407 #undef KMP_GIVE_EQ
 408
 409 #ifdef KMP_WANT_SEARCH
 410 #  undef KMP_WANT_SEARCH
 411 #  define KMPS_PREFIX(x) KMP_PREFIX(x)
 412 #  define KMPS_KMP_PREFIX(x) KMP_PREFIX(x)
 413 #  include "lib/kmp-search.h"
 414 #endif
 415
 416 #undef KMP_PREFIX