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