]> mj.ucw.cz Git - libucw.git/blobdiff - lib/kmp-search.h
More changes in KMP:
[libucw.git] / lib / kmp-search.h
index 0c572b65d43b3a9a3a84be08e6f848c100480ad6..ab276b5a3916b3934a3e97b3a93894a917e8a4a7 100644 (file)
  *  This is not a normal header file, it's a generator of KMP algorithm.
  *  Each time you include it with parameters set in the corresponding
  *  preprocessor macros, it generates KMP structures and functions
- *  with the parameters given.
+ *  with the parameters given. Macros marked with [*] are mandatory.
  *
  *  [*]        KMPS_PREFIX(x)          macro to add a name prefix (used on all global names
- *                             defined by the KMP search generator).
+ *                             defined by the KMP search generator)
  *  [*]        KMPS_KMP_PREFIX(x)      prefix used for lib/kmp.h;
  *                             more variants of kmp-search can be used for single lib/kmp.h
  *
  *  KMPS_SOURCE                        user-defined search input (together with KMPS_GET_CHAR);
  *                             if unset, the one from lib/kmp.h is used
- *  KMPS_GET_CHAR(ctx,src,s)
+ *  KMPS_GET_CHAR(kmp,src,s)
  *
- *  KMPS_ADD_CONTROLS          adds control characters to start and the end
- *  KMPS_MERGE_CONTROLS        merges adjacent control characterss to a single one
+ *  KMPS_ADD_CONTROLS          add control characters at both ends of the input string
+ *  KMPS_MERGE_CONTROLS        merge adjacent control characters to a single one
  *
  *  KMPS_EXTRA_ARGS            extra arguments to the search routine
  *  KMPS_EXTRA_VAR             extra user-defined structure in search structures
- *  KMPS_INIT(ctx,src,s)
- *  KMPS_EXIT(ctx,src,s)
- *  KMPS_FOUND(ctx,src,s)
- *  KMPS_FOUND_CHAIN(ctx,src,s)
- *  KMPS_STEP(ctx,src,s)
+ *  KMPS_INIT(kmp,src,s)
+ *  KMPS_EXIT(kmp,src,s)
+ *  KMPS_FOUND(kmp,src,s)
+ *  KMPS_FOUND_CHAIN(kmp,src,s)
+ *  KMPS_STEP(kmp,src,s)
  *  KMPS_T
  *
  *  KMPS_WANT_BEST
@@ -48,14 +48,14 @@ typedef KP(source_t) P(search_source_t);
 #endif
 
 #ifndef KMPS_GET_CHAR
-#define KMPS_GET_CHAR(ctx,src,s) ({ KP(get_char)(ctx, &src, &s.c); })
+#define KMPS_GET_CHAR(kmp,src,s) ({ KP(get_char)(kmp, &src, &s.c); })
 #endif
 
 struct P(search) {
   struct KP(state) *s;         /* current state */
   struct KP(state) *out;       /* output state */
 # ifdef KMPS_WANT_BEST
-  struct KP(state) *best;      /* largest match */
+  struct KP(state) *best;      /* longest match */
 # endif
   KP(char_t) c;                        /* last character */
 # ifdef KMPS_EXTRA_VAR
@@ -71,36 +71,36 @@ static KMPS_T
 #else
 static void
 #endif
-P(search) (struct KP(context) *ctx, P(search_source_t) src
+P(search) (struct KP(struct) *kmp, P(search_source_t) src
 #   ifdef KMPS_EXTRA_ARGS
     , KMPS_EXTRA_ARGS
 #   endif
 )
 {
   struct P(search) s;
-  s.s = &ctx->null;
+  s.s = &kmp->null;
 # ifdef KMPS_WANT_BEST
-  s.best = &ctx->null;
+  s.best = &kmp->null;
 # endif
 # ifdef KMPS_ADD_CONTROLS 
-  s.c = KP(control_char)();
+  s.c = KP(control)();
   s.eof = 0;
 # else
   s.c = 0;
 # endif  
 # ifdef KMPS_INIT
-  { KMPS_INIT(ctx, src, s); }
+  { KMPS_INIT(kmp, src, s); }
 # endif
 # ifndef KMPS_ADD_CONTROLS  
   goto start_read;
 #endif  
   for (;;)
   {
-    for (struct KP(state) *t = s.s; t && !(s.s = KP(hash_find)(&ctx->hash, t, s.c)); t = t->back);
-    s.s = s.s ? : &ctx->null;
+    for (struct KP(state) *t = s.s; t && !(s.s = KP(hash_find)(&kmp->hash, t, s.c)); t = t->back);
+    s.s = s.s ? : &kmp->null;
 
 #   ifdef KMPS_STEP
-    { KMPS_STEP(ctx, src, s); }
+    { KMPS_STEP(kmp, src, s); }
 #   endif
 
 #   if defined(KMPS_FOUND) || defined(KMPS_FOUND_CHAIN) || defined(KMPS_WANT_BEST)
@@ -112,18 +112,18 @@ P(search) (struct KP(context) *ctx, P(search_source_t) src
          s.best = s.out;
 #       endif  
         #ifdef KMPS_FOUND_CHAIN
-       { KMPS_FOUND_CHAIN(ctx, src, s); }
+       { KMPS_FOUND_CHAIN(kmp, src, s); }
 #       endif
 #       ifdef KMPS_FOUND
        do
-          { KMPS_FOUND(ctx, src, s); }
+          { KMPS_FOUND(kmp, src, s); }
        while (s.out = s.out->next);
 #       endif  
       }
-#     endif
+#   endif
 
 #   ifdef KMPS_ADD_CONTROLS    
-    if (unlikely(s.eof))
+    if (s.eof)
       break;
 #   endif    
 
@@ -136,12 +136,12 @@ start_read: ;
 
     do
       {
-       if (unlikely(!KMPS_GET_CHAR(ctx, src, s)))
+       if (!KMPS_GET_CHAR(kmp, src, s))
          {
 #           ifdef KMPS_ADD_CONTROLS
-           if (s.c != KP(control_char)())
+           if (!KP(is_control)(kmp, s.c))
              {
-                s.c = KP(control_char)();
+                s.c = KP(control)();
                 s.eof = 1;
                break;
              }
@@ -151,13 +151,13 @@ start_read: ;
       }
     while (0
 #     ifdef KMPS_MERGE_CONTROLS
-      || (last_c == KP(control_char)() && s.c == KP(control_char)())
+      || (KP(is_control)(kmp, last_c) && KP(is_control)(kmp, s.c))
 #     endif
       );
   }
 exit: ;
 # ifdef KMPS_EXIT
-  { KMPS_EXIT(ctx, src, s); }
+  { KMPS_EXIT(kmp, src, s); }
 # endif
 }