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