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