lib/kmp-search.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. Macros marked with [*] are mandatory.
  16  *
  17  *  [*] KMPS_PREFIX(x)          macro to add a name prefix (used on all global names
  18  *                              defined by the KMP search generator)
  19  *  [*] KMPS_KMP_PREFIX(x)      prefix used for lib/kmp.h;
  20  *                              more variants of kmp-search can be used for single lib/kmp.h
  21  *
  22  *  KMPS_SOURCE                 user-defined search input (together with KMPS_GET_CHAR);
  23  *                              if unset, the one from lib/kmp.h is used
  24  *  KMPS_GET_CHAR(kmp,src,s)
  25  *
  26  *  KMPS_ADD_CONTROLS           add control characters at both ends of the input string
  27  *  KMPS_MERGE_CONTROLS         merge adjacent control characters to a single onei
  28  *
  29  *  KMPS_VARS
  30  *
  31  *  KMPS_INIT(kmp,src,s)
  32  *  KMPS_EXIT(kmp,src,s)
  33  *  KMPS_STEP(kmp,src,s)
  34  *  KMPS_FOUND(kmp,src,s)
  35  *  KMPS_FOUND_CHAIN(kmp,src,s)
  36  *
  37  *  KMPS_WANT_BEST
  38  */
  39
  40 #define P(x) KMPS_PREFIX(x)
  41 #define KP(x) KMPS_KMP_PREFIX(x)
  42
  43 #ifdef KMPS_SOURCE
  44 typedef KMPS_SOURCE P(search_source_t);
  45 #else
  46 typedef KP(source_t) P(search_source_t);
  47 #endif
  48
  49 #ifndef KMPS_GET_CHAR
  50 #define KMPS_GET_CHAR(kmp,src,s) ({ KP(get_char)(kmp, &src, &s->c); })
  51 #endif
  52
  53 struct P(search) {
  54   struct KP(state) *s;          /* current state */
  55   struct KP(state) *out;        /* output state */
  56 # ifdef KMPS_WANT_BEST
  57   struct KP(state) *best;       /* longest match */
  58 # endif
  59   KP(char_t) c;                 /* last character */
  60 # ifdef KMPS_ADD_CONTROLS
  61   uns eof;
  62 # endif
  63 # ifdef KMPS_VARS
  64   struct {
  65     KMPS_VARS
  66   } u;                          /* user-defined */
  67 # endif
  68 };
  69
  70 static void
  71 P(search) (struct KP(struct) *kmp, struct P(search) *s, P(search_source_t) src)
  72 {
  73   s->s = &kmp->null;
  74 # ifdef KMPS_WANT_BEST
  75   s->best = &kmp->null;
  76 # endif
  77 # ifdef KMPS_ADD_CONTROLS
  78   s->c = KP(control)();
  79   s->eof = 0;
  80 # else
  81   s->c = 0;
  82 # endif
  83 # ifdef KMPS_INIT
  84   { KMPS_INIT(kmp, src, s); }
  85 # endif
  86 # ifndef KMPS_ADD_CONTROLS
  87   goto start_read;
  88 #endif
  89   for (;;)
  90   {
  91     for (struct KP(state) *t = s->s; t && !(s->s = KP(hash_find)(&kmp->hash, t, s->c)); t = t->back);
  92     s->s = s->s ? : &kmp->null;
  93
  94 #   ifdef KMPS_STEP
  95     { KMPS_STEP(kmp, src, s); }
  96 #   endif
  97
  98 #   if defined(KMPS_FOUND) || defined(KMPS_FOUND_CHAIN) || defined(KMPS_WANT_BEST)
  99     s->out = s->s->len ? s->s : s->s->next;
 100     if (s->out)
 101       {
 102 #       ifdef KMPS_WANT_BEST
 103         if (s->out->len > s->best->len)
 104           s->best = s->out;
 105 #       endif
 106         #ifdef KMPS_FOUND_CHAIN
 107         { KMPS_FOUND_CHAIN(kmp, src, s); }
 108 #       endif
 109 #       ifdef KMPS_FOUND
 110         do
 111           { KMPS_FOUND(kmp, src, s); }
 112         while (s->out = s->out->next);
 113 #       endif
 114       }
 115 #   endif
 116
 117 #   ifdef KMPS_ADD_CONTROLS
 118     if (s->eof)
 119       break;
 120 #   endif
 121
 122 #   ifndef KMPS_ADD_CONTROLS
 123 start_read: ;
 124 #   endif
 125 #   ifdef KMPS_MERGE_CONTROLS
 126     KP(char_t) last_c = s->c;
 127 #   endif
 128
 129     do
 130       {
 131         if (!KMPS_GET_CHAR(kmp, src, s))
 132           {
 133 #           ifdef KMPS_ADD_CONTROLS
 134             if (!KP(is_control)(kmp, s->c))
 135               {
 136                 s->c = KP(control)();
 137                 s->eof = 1;
 138                 break;
 139               }
 140 #           endif
 141             goto exit;
 142           }
 143       }
 144     while (0
 145 #     ifdef KMPS_MERGE_CONTROLS
 146       || (KP(is_control)(kmp, last_c) && KP(is_control)(kmp, s->c))
 147 #     endif
 148       );
 149   }
 150 exit: ;
 151 # ifdef KMPS_EXIT
 152   { KMPS_EXIT(kmp, src, s); }
 153 # endif
 154 }
 155
 156 static inline void
 157 P(run) (struct KP(struct) *kmp, P(search_source_t) src)
 158 {
 159   struct P(search) search;
 160   P(search)(kmp, &search, src);
 161 }
 162
 163 #undef P
 164 #undef KMPS_PREFIX
 165 #undef KMPS_KMP_PREFIX
 166 #undef KMPS_SOURCE
 167 #undef KMPS_GET_CHAR
 168 #undef KMPS_ADD_CONTROLS
 169 #undef KMPS_MERGE_CONTROLS
 170 #undef KMPS_VARS
 171 #undef KMPS_INIT
 172 #undef KMPS_EXIT
 173 #undef KMPS_FOUND
 174 #undef KMPS_FOUND_CHAIN
 175 #undef KMPS_STEP
 176 #undef KMPS_WANT_BEST