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 one
  28  *
  29  *  KMPS_EXTRA_ARGS             extra arguments to the search routine
  30  *  KMPS_EXTRA_VAR              extra user-defined structure in search structures
  31  *  KMPS_INIT(kmp,src,s)
  32  *  KMPS_EXIT(kmp,src,s)
  33  *  KMPS_FOUND(kmp,src,s)
  34  *  KMPS_FOUND_CHAIN(kmp,src,s)
  35  *  KMPS_STEP(kmp,src,s)
  36  *  KMPS_T
  37  *
  38  *  KMPS_WANT_BEST
  39  */
  40
  41 #define P(x) KMPS_PREFIX(x)
  42 #define KP(x) KMPS_KMP_PREFIX(x)
  43
  44 #ifdef KMPS_SOURCE
  45 typedef KMPS_SOURCE P(search_source_t);
  46 #else
  47 typedef KP(source_t) P(search_source_t);
  48 #endif
  49
  50 #ifndef KMPS_GET_CHAR
  51 #define KMPS_GET_CHAR(kmp,src,s) ({ KP(get_char)(kmp, &src, &s.c); })
  52 #endif
  53
  54 struct P(search) {
  55   struct KP(state) *s;          /* current state */
  56   struct KP(state) *out;        /* output state */
  57 # ifdef KMPS_WANT_BEST
  58   struct KP(state) *best;       /* longest match */
  59 # endif
  60   KP(char_t) c;                 /* last character */
  61 # ifdef KMPS_EXTRA_VAR
  62   KMPS_EXTRA_VAR v;             /* user-defined */
  63 # endif
  64 # ifdef KMPS_ADD_CONTROLS
  65   uns eof;
  66 # endif
  67 };
  68
  69 #ifdef KMPS_T
  70 static KMPS_T
  71 #else
  72 static void
  73 #endif
  74 P(search) (struct KP(struct) *kmp, P(search_source_t) src
  75 #   ifdef KMPS_EXTRA_ARGS
  76     , KMPS_EXTRA_ARGS
  77 #   endif
  78 )
  79 {
  80   struct P(search) s;
  81   s.s = &kmp->null;
  82 # ifdef KMPS_WANT_BEST
  83   s.best = &kmp->null;
  84 # endif
  85 # ifdef KMPS_ADD_CONTROLS
  86   s.c = KP(control)();
  87   s.eof = 0;
  88 # else
  89   s.c = 0;
  90 # endif
  91 # ifdef KMPS_INIT
  92   { KMPS_INIT(kmp, src, s); }
  93 # endif
  94 # ifndef KMPS_ADD_CONTROLS
  95   goto start_read;
  96 #endif
  97   for (;;)
  98   {
  99     for (struct KP(state) *t = s.s; t && !(s.s = KP(hash_find)(&kmp->hash, t, s.c)); t = t->back);
 100     s.s = s.s ? : &kmp->null;
 101
 102 #   ifdef KMPS_STEP
 103     { KMPS_STEP(kmp, src, s); }
 104 #   endif
 105
 106 #   if defined(KMPS_FOUND) || defined(KMPS_FOUND_CHAIN) || defined(KMPS_WANT_BEST)
 107     s.out = s.s->len ? s.s : s.s->next;
 108     if (s.out)
 109       {
 110 #       ifdef KMPS_WANT_BEST
 111         if (s.out->len > s.best->len)
 112           s.best = s.out;
 113 #       endif
 114         #ifdef KMPS_FOUND_CHAIN
 115         { KMPS_FOUND_CHAIN(kmp, src, s); }
 116 #       endif
 117 #       ifdef KMPS_FOUND
 118         do
 119           { KMPS_FOUND(kmp, src, s); }
 120         while (s.out = s.out->next);
 121 #       endif
 122       }
 123 #   endif
 124
 125 #   ifdef KMPS_ADD_CONTROLS
 126     if (s.eof)
 127       break;
 128 #   endif
 129
 130 #   ifndef KMPS_ADD_CONTROLS
 131 start_read: ;
 132 #   endif
 133 #   ifdef KMPS_MERGE_CONTROLS
 134     KP(char_t) last_c = s.c;
 135 #   endif
 136
 137     do
 138       {
 139         if (!KMPS_GET_CHAR(kmp, src, s))
 140           {
 141 #           ifdef KMPS_ADD_CONTROLS
 142             if (!KP(is_control)(kmp, s.c))
 143               {
 144                 s.c = KP(control)();
 145                 s.eof = 1;
 146                 break;
 147               }
 148 #           endif
 149             goto exit;
 150           }
 151       }
 152     while (0
 153 #     ifdef KMPS_MERGE_CONTROLS
 154       || (KP(is_control)(kmp, last_c) && KP(is_control)(kmp, s.c))
 155 #     endif
 156       );
 157   }
 158 exit: ;
 159 # ifdef KMPS_EXIT
 160   { KMPS_EXIT(kmp, src, s); }
 161 # endif
 162 }
 163
 164 #undef P
 165 #undef KMPS_PREFIX
 166 #undef KMPS_KMP_PREFIX
 167 #undef KMPS_SOURCE
 168 #undef KMPS_GET_CHAR
 169 #undef KMPS_ADD_CONTROLS
 170 #undef KMPS_MERGE_CONTROLS
 171 #undef KMPS_EXTRA_ARGS
 172 #undef KMPS_EXTRA_VAR
 173 #undef KMPS_INIT
 174 #undef KMPS_EXIT
 175 #undef KMPS_FOUND
 176 #undef KMPS_FOUND_CHAIN
 177 #undef KMPS_STEP
 178 #undef KMPS_T
 179 #undef KMPS_WANT_BEST