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 (including 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   memset(s, 0, sizeof(*s));
 118   s->from = f;
 119   s->c = c;
 120   s->next = f->back; /* the pointers hold the link-list of sons... change in build() */
 121   f->back = s;
 122 }
 123
 124 #undef P
 125 #define HASH_PREFIX(x) KMP_PREFIX(GLUE(hash_,x))
 126 #define HASH_NODE struct KMP_PREFIX(state)
 127 #define HASH_KEY_COMPLEX(x) x from, x c
 128 #define HASH_KEY_DECL struct KMP_PREFIX(state) *from, KMP_PREFIX(char_t) c
 129 #define HASH_WANT_NEW
 130 #define HASH_WANT_FIND
 131 #ifdef KMP_WANT_CLEANUP
 132 #define HASH_WANT_CLEANUP
 133 #endif
 134 #define HASH_GIVE_HASHFN
 135 #define HASH_GIVE_EQ
 136 #define HASH_GIVE_INIT_KEY
 137 #ifdef KMP_USE_POOL
 138 #define HASH_USE_POOL KMP_USE_POOL
 139 #else
 140 #define HASH_AUTO_POOL 4096
 141 #endif
 142 #define HASH_CONSERVE_SPACE
 143 #define HASH_TABLE_DYNAMIC
 144 #include "lib/hashtable.h"
 145 #define P(x) KMP_PREFIX(x)
 146
 147 struct P(context) {
 148   struct P(hash_table) hash;            /* hash table*/
 149   struct P(state) null;                 /* null state */
 150 };
 151
 152 #ifdef KMP_SOURCE
 153 typedef KMP_SOURCE P(source_t);
 154 #else
 155 typedef byte *P(source_t);
 156 #endif
 157
 158 #ifdef KMP_GET_CHAR
 159 static inline int
 160 P(get_char) (struct P(context) *ctx, P(source_t) *src, P(char_t) *c)
 161 {
 162   return KMP_GET_CHAR(ctx, *src, *c);
 163 }
 164 #else
 165 #  if defined(KMP_USE_UTF8)
 166 #    include "lib/unicode.h"
 167 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER) || defined(KMP_UNACCENT)
 168 #      include "charset/unicat.h"
 169 #    endif
 170 #  elif defined(KMP_USE_ASCII)
 171 #    if defined(KMP_ONLYALPHA) || defined(KMP_TOLOWER)
 172 #      include "lib/chartype.h"
 173 #    endif
 174 #  endif
 175 static inline int
 176 P(get_char) (struct P(context) *ctx UNUSED, P(source_t) *src, P(char_t) *c)
 177 {
 178 # ifdef KMP_USE_UTF8
 179   uns cc;
 180   *src = (byte *)utf8_get(*src, &cc);
 181 # ifdef KMP_ONLYALPHA
 182   if (unlikely(!cc)) {}
 183   else if (!Ualpha(cc))
 184     cc = P(control_char)();
 185   else
 186 # endif
 187     {
 188 #     ifdef KMP_TOLOWER
 189       cc = Utolower(cc);
 190 #     endif
 191 #     ifdef KMP_UNACCENT
 192       cc = Uunaccent(cc);
 193 #     endif
 194     }
 195 # else
 196   uns cc = *(*src)++;
 197 # ifdef KMP_ONLYALPHA
 198   if (unlikely(!cc)) {}
 199   else if (!Calpha(cc))
 200     cc = P(control_char)();
 201   else
 202 # endif
 203 #   ifdef KMP_TOLOWER
 204     cc = Clocase(c);
 205 #   endif
 206 # endif
 207   *c = cc;
 208   return !!cc;
 209 }
 210 #endif
 211
 212 static struct P(state) *
 213 P(add) (struct P(context) *ctx, P(source_t) src
 214 #   ifdef KMP_ADD_EXTRA_ARGS
 215     , KMP_ADD_EXTRA_ARGS
 216 #   endif
 217 )
 218 {
 219 # ifdef KMP_ADD_EXTRA_VAR
 220   KMP_ADD_EXTRA_VAR v;
 221 # endif
 222 # ifdef KMP_ADD_INIT
 223   { KMP_ADD_INIT(ctx, src, v); }
 224 # endif
 225
 226   P(char_t) c;
 227   if (unlikely(!P(get_char)(ctx, &src, &c)))
 228     return NULL;
 229   struct P(state) *p = &ctx->null, *s;
 230   uns len = 0;
 231   do
 232     {
 233       s = P(hash_find)(&ctx->hash, p, c);
 234       if (!s)
 235         for (;;)
 236           {
 237             s = P(hash_new)(&ctx->hash, p, c);
 238             len++;
 239             if (unlikely(!(P(get_char)(ctx, &src, &c))))
 240               goto enter_new;
 241             p = s;
 242           }
 243       p = s;
 244       len++;
 245     }
 246   while (P(get_char)(ctx, &src, &c));
 247 # ifdef KMP_NO_DUPS
 248   ASSERT(!s->len);
 249 # else
 250   if (s->len)
 251     {
 252 #     ifdef KMP_ADD_DUP
 253       { KMP_ADD_DUP(ctx, src, v, s); }
 254 #     endif
 255       return s;
 256     }
 257 # endif
 258 enter_new:
 259   s->len = len;
 260 # ifdef KMP_ADD_NEW
 261   { KMP_ADD_NEW(ctx, src, v, s); }
 262 # endif
 263   return s;
 264 }
 265
 266 static void
 267 P(init) (struct P(context) *ctx)
 268 {
 269   memset(ctx, 0, sizeof(*ctx));
 270   P(hash_init)(&ctx->hash);
 271 }
 272
 273 #ifdef KMP_WANT_CLEANUP
 274 static inline void
 275 P(cleanup) (struct P(context) *ctx)
 276 {
 277   P(hash_cleanup)(&ctx->hash);
 278 }
 279 #endif
 280
 281 static inline int
 282 P(empty) (struct P(context) *ctx)
 283 {
 284   return !ctx->hash.hash_count;
 285 }
 286
 287 static void
 288 P(build) (struct P(context) *ctx)
 289 {
 290   if (P(empty)(ctx))
 291     return;
 292   uns read = 0, write = 0;
 293   struct P(state) *fifo[ctx->hash.hash_count], *null = &ctx->null;
 294   for (struct P(state) *s = null->back; s; s = s->next)
 295     fifo[write++] = s;
 296   null->back = NULL;
 297 # ifdef KMP_BUILD_STATE
 298   { KMP_BUILD_STATE(ctx, null); }
 299 # endif
 300   while (read != write)
 301     {
 302       struct P(state) *s = fifo[read++], *t;
 303       for (t = s->back; t; t = t->next)
 304         fifo[write++] = t;
 305       for (t = s->from->back; 1; t = t->back)
 306         {
 307           if (!t)
 308             {
 309               s->back = null;
 310               s->next = NULL;
 311               break;
 312             }
 313           s->back = P(hash_find)(&ctx->hash, t, s->c);
 314           if (s->back)
 315             {
 316               s->next = s->back->len ? s->back : s->back->next;
 317               break;
 318             }
 319         }
 320 #     ifdef KMP_BUILD_STATE
 321       { KMP_BUILD_STATE(ctx, s); }
 322 #     endif
 323     }
 324 }
 325
 326 #undef P
 327 #undef KMP_CHAR
 328 #undef KMP_SOURCE
 329 #undef KMP_GET_CHAR
 330 #undef KMP_NODE
 331 #undef KMP_USE_ASCII
 332 #undef KMP_USE_UTF8
 333 #undef KMP_TOLOWER
 334 #undef KMP_UNACCENT
 335 #undef KMP_ONLYALPHA
 336 #undef KMP_CONTROL_CHAR
 337 #undef KMP_ADD_EXTRA_ARGS
 338 #undef KMP_ADD_EXTRA_VAR
 339 #undef KMP_ADD_INIT
 340 #undef KMP_ADD_NEW
 341 #undef KMP_ADD_DUP
 342 #undef KMP_NO_DUPS
 343 #undef KMP_BUILD_STATE
 344 #undef KMP_USE_POOL
 345
 346 #ifdef KMP_WANT_SEARCH
 347 #  undef KMP_WANT_SEARCH
 348 #  define KMPS_PREFIX(x) KMP_PREFIX(x)
 349 #  define KMPS_KMP_PREFIX(x) KMP_PREFIX(x)
 350 #  include "lib/kmp-search.h"
 351 #endif
 352
 353 #undef KMP_PREFIX