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_EXTRA_VAR       structure with extra local variables
  43  *      KMP_ADD_INIT(kmp,src,v)
  44  *      KMP_ADD_NEW(kmp,src,v,s)
  45  *      KMP_ADD_DUP(kmp,src,v,s)
  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   s->from = f;
 172   s->c = c;
 173   s->next = f->back; /* the pointers hold the link-list of sons... changed in build() */
 174   f->back = s;
 175 }
 176
 177 #undef P
 178 #define HASH_PREFIX(x) KMP_PREFIX(GLUE(hash_,x))
 179 #define HASH_NODE struct KMP_PREFIX(state)
 180 #define HASH_KEY_COMPLEX(x) x from, x c
 181 #define HASH_KEY_DECL struct KMP_PREFIX(state) *from, KMP_PREFIX(char_t) c
 182 #define HASH_WANT_NEW
 183 #define HASH_WANT_FIND
 184 #ifdef KMP_WANT_CLEANUP
 185 #define HASH_WANT_CLEANUP
 186 #endif
 187 #if defined(KMP_USE_POOL)
 188 #define HASH_USE_POOL KMP_USE_POOL
 189 #else
 190 #define HASH_AUTO_POOL 4096
 191 #endif
 192 #define HASH_CONSERVE_SPACE
 193 #define HASH_TABLE_DYNAMIC
 194 #include "lib/hashtable.h"
 195 #define P(x) KMP_PREFIX(x)
 196
 197 struct P(struct) {
 198   struct P(hash_table) hash;            /* hash table of state transitions */
 199   struct P(state) null;                 /* null state */
 200   struct {
 201 #   ifdef KMP_VARS
 202     KMP_VARS
 203 #   endif
 204   } u;                                  /* user-defined data */
 205 };
 206
 207 #ifdef KMP_SOURCE
 208 typedef KMP_SOURCE P(source_t);
 209 #else
 210 typedef byte *P(source_t);
 211 #endif
 212
 213 #ifdef KMP_GET_CHAR
 214 static inline int
 215 P(get_char) (struct P(struct) *kmp UNUSED, P(source_t) *src UNUSED, P(char_t) *c UNUSED)
 216 {
 217   return KMP_GET_CHAR(kmp, (*src), (*c));
 218 }
 219 #else
 220 #  if defined(KMP_USE_UTF8)
 221 #    include "lib/unicode.h"
 222 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER) || defined(KMP_UNACCENT)
 223 #      include "charset/unicat.h"
 224 #    endif
 225 #  elif defined(KMP_USE_ASCII)
 226 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER)
 227 #      include "lib/chartype.h"
 228 #    endif
 229 #  endif
 230 static inline int
 231 P(get_char) (struct P(struct) *kmp UNUSED, P(source_t) *src, P(char_t) *c)
 232 {
 233 # ifdef KMP_USE_UTF8
 234   uns cc;
 235   *src = (byte *)utf8_get(*src, &cc);
 236 # ifdef KMP_ONLYALPHA
 237   if (!cc) {}
 238   else if (!Ualpha(cc))
 239     cc = P(control)();
 240   else
 241 # endif
 242     {
 243 #     ifdef KMP_TOLOWER
 244       cc = Utolower(cc);
 245 #     endif
 246 #     ifdef KMP_UNACCENT
 247       cc = Uunaccent(cc);
 248 #     endif
 249     }
 250 # else
 251   uns cc = *(*src)++;
 252 # ifdef KMP_ONLYALPHA
 253   if (!cc) {}
 254   else if (!Calpha(cc))
 255     cc = P(control)();
 256   else
 257 # endif
 258 #   ifdef KMP_TOLOWER
 259     cc = Clocase(cc);
 260 #   endif
 261 #   ifdef KMP_UNACCENT
 262 #   error Do not know how to unaccent ASCII characters
 263 #   endif
 264 # endif
 265   *c = cc;
 266   return !!cc;
 267 }
 268 #endif
 269
 270 static struct P(state) *
 271 P(add) (struct P(struct) *kmp, P(source_t) src
 272 #   ifdef KMP_ADD_EXTRA_ARGS
 273     , KMP_ADD_EXTRA_ARGS
 274 #   endif
 275 )
 276 {
 277 # ifdef KMP_ADD_EXTRA_VAR
 278   KMP_ADD_EXTRA_VAR v;
 279 # endif
 280 # ifdef KMP_ADD_INIT
 281   { KMP_ADD_INIT(kmp, src, v); }
 282 # endif
 283
 284   P(char_t) c;
 285   if (!P(get_char)(kmp, &src, &c))
 286     return NULL;
 287   struct P(state) *p = &kmp->null, *s;
 288   uns len = 0;
 289   do
 290     {
 291       s = P(hash_find)(&kmp->hash, p, c);
 292       if (!s)
 293         for (;;)
 294           {
 295             s = P(hash_new)(&kmp->hash, p, c);
 296             len++;
 297             if (!(P(get_char)(kmp, &src, &c)))
 298               goto enter_new;
 299             p = s;
 300           }
 301       p = s;
 302       len++;
 303     }
 304   while (P(get_char)(kmp, &src, &c));
 305 # ifdef KMP_NO_DUPS
 306   ASSERT(!s->len);
 307 # else
 308   if (s->len)
 309     {
 310 #     ifdef KMP_ADD_DUP
 311       { KMP_ADD_DUP(kmp, src, v, s); }
 312 #     endif
 313       return s;
 314     }
 315 # endif
 316 enter_new:
 317   s->len = len;
 318 # ifdef KMP_ADD_NEW
 319   { KMP_ADD_NEW(kmp, src, v, s); }
 320 # endif
 321   return s;
 322 }
 323
 324 static void
 325 P(init) (struct P(struct) *kmp)
 326 {
 327   bzero(&kmp->null, sizeof(struct P(state)));
 328   P(hash_init)(&kmp->hash);
 329 }
 330
 331 #ifdef KMP_WANT_CLEANUP
 332 static inline void
 333 P(cleanup) (struct P(struct) *kmp)
 334 {
 335   P(hash_cleanup)(&kmp->hash);
 336 }
 337 #endif
 338
 339 static inline int
 340 P(empty) (struct P(struct) *kmp)
 341 {
 342   return !kmp->hash.hash_count;
 343 }
 344
 345 static inline struct P(state) *
 346 P(chain_start) (struct P(state) *s)
 347 {
 348   return s->len ? s : s->next;
 349 }
 350
 351 static void
 352 P(build) (struct P(struct) *kmp)
 353 {
 354   if (P(empty)(kmp))
 355     return;
 356   uns read = 0, write = 0;
 357   struct P(state) *fifo[kmp->hash.hash_count], *null = &kmp->null;
 358   for (struct P(state) *s = null->back; s; s = s->next)
 359     fifo[write++] = s;
 360   null->back = NULL;
 361 # ifdef KMP_BUILD_STATE
 362   { KMP_BUILD_STATE(kmp, null); }
 363 # endif
 364   while (read != write)
 365     {
 366       struct P(state) *s = fifo[read++], *t;
 367       for (t = s->back; t; t = t->next)
 368         fifo[write++] = t;
 369       for (t = s->from->back; 1; t = t->back)
 370         {
 371           if (!t)
 372             {
 373               s->back = null;
 374               s->next = NULL;
 375               break;
 376             }
 377           s->back = P(hash_find)(&kmp->hash, t, s->c);
 378           if (s->back)
 379             {
 380               s->next = s->back->len ? s->back : s->back->next;
 381               break;
 382             }
 383         }
 384 #     ifdef KMP_BUILD_STATE
 385       { KMP_BUILD_STATE(kmp, s); }
 386 #     endif
 387     }
 388 }
 389
 390 #undef P
 391 #undef KMP_CHAR
 392 #undef KMP_SOURCE
 393 #undef KMP_GET_CHAR
 394 #undef KMP_VARS
 395 #undef KMP_STATE_VARS
 396 #undef KMP_CONTEXT
 397 #undef KMP_USE_ASCII
 398 #undef KMP_USE_UTF8
 399 #undef KMP_TOLOWER
 400 #undef KMP_UNACCENT
 401 #undef KMP_ONLYALPHA
 402 #undef KMP_CONTROL_CHAR
 403 #undef KMP_ADD_EXTRA_ARGS
 404 #undef KMP_ADD_EXTRA_VAR
 405 #undef KMP_ADD_INIT
 406 #undef KMP_ADD_NEW
 407 #undef KMP_ADD_DUP
 408 #undef KMP_BUILD_STATE
 409 #undef KMP_USE_POOL
 410 #undef KMP_GIVE_ALLOC
 411 #undef KMP_GIVE_HASHFN
 412 #undef KMP_GIVE_EQ
 413
 414 #ifdef KMP_WANT_SEARCH
 415 #  undef KMP_WANT_SEARCH
 416 #  define KMPS_PREFIX(x) KMP_PREFIX(x)
 417 #  define KMPS_KMP_PREFIX(x) KMP_PREFIX(x)
 418 #  include "lib/kmp-search.h"
 419 #endif
 420
 421 #undef KMP_PREFIX