Fix the comparison of the first byte when using gperf_case_strcmp.

5 files changed, 359 insertions, 70 deletions

diff --git a/ChangeLog b/ChangeLog
index 3dc748e..93df3b8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2003-01-01  Bruno Haible  <bruno@clisp.org>
+
+	* src/output.c (Output_Compare::output_firstchar_comparison): New
+	method.
+	(Output_Compare_Strcmp::output_comparison,
+	Output_Compare_Strncmp::output_comparison,
+	Output_Compare_Memcmp::output_comparison): Use it.
+	* tests/permutc2.exp: Update.
+
+	* tests/smtp.gperf: New file, based on a contribution by Bruce Lilly.
+	* tests/Makefile.in (check-smtp): New rule.
+	(check): Depend on it.
+	(clean): Update.
+
 2002-12-12  Bruno Haible  <bruno@clisp.org>
 
 	* src/search.h (Search::init_selchars_tuple,
diff --git a/src/output.cc b/src/output.cc
index f1bd0d0..23363f4 100644
--- a/src/output.cc
+++ b/src/output.cc
@@ -1,5 +1,5 @@
 /* Output routines.
-   Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
+   Copyright (C) 1989-1998, 2000, 2002-2003 Free Software Foundation, Inc.
    Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
    and Bruno Haible <bruno@clisp.org>.
 
@@ -144,22 +144,22 @@ Output::num_hash_values () const
 
 struct Output_Constants
 {
-  virtual void output_start () = 0;
-  virtual void output_item (const char *name, int value) = 0;
-  virtual void output_end () = 0;
-  Output_Constants () {}
-  virtual ~Output_Constants () {}
+  virtual void          output_start () = 0;
+  virtual void          output_item (const char *name, int value) = 0;
+  virtual void          output_end () = 0;
+                        Output_Constants () {}
+  virtual               ~Output_Constants () {}
 };
 
 /* This class outputs an enumeration in #define syntax.  */
 
 struct Output_Defines : public Output_Constants
 {
-  virtual void output_start ();
-  virtual void output_item (const char *name, int value);
-  virtual void output_end ();
-  Output_Defines () {}
-  virtual ~Output_Defines () {}
+  virtual void          output_start ();
+  virtual void          output_item (const char *name, int value);
+  virtual void          output_end ();
+                        Output_Defines () {}
+  virtual               ~Output_Defines () {}
 };
 
 void Output_Defines::output_start ()
@@ -180,11 +180,12 @@ void Output_Defines::output_end ()
 
 struct Output_Enum : public Output_Constants
 {
-  virtual void output_start ();
-  virtual void output_item (const char *name, int value);
-  virtual void output_end ();
-  Output_Enum (const char *indent) : _indentation (indent) {}
-  virtual ~Output_Enum () {}
+  virtual void          output_start ();
+  virtual void          output_item (const char *name, int value);
+  virtual void          output_end ();
+                        Output_Enum (const char *indent)
+                          : _indentation (indent) {}
+  virtual               ~Output_Enum () {}
 private:
   const char *_indentation;
   bool _pending_comma;
@@ -407,18 +408,18 @@ output_const_type (const char *const_string, const char *type_string)
 
 struct Output_Expr
 {
-  virtual void output_expr () const = 0;
-  Output_Expr () {}
-  virtual ~Output_Expr () {}
+  virtual void          output_expr () const = 0;
+                        Output_Expr () {}
+  virtual               ~Output_Expr () {}
 };
 
 /* This class outputs an expression formed by a single string.  */
 
 struct Output_Expr1 : public Output_Expr
 {
-  virtual void output_expr () const;
-  Output_Expr1 (const char *piece1) : _p1 (piece1) {}
-  virtual ~Output_Expr1 () {}
+  virtual void          output_expr () const;
+                        Output_Expr1 (const char *piece1) : _p1 (piece1) {}
+  virtual               ~Output_Expr1 () {}
 private:
   const char *_p1;
 };
@@ -435,10 +436,10 @@ void Output_Expr1::output_expr () const
 
 struct Output_Expr2 : public Output_Expr
 {
-  virtual void output_expr () const;
-  Output_Expr2 (const char *piece1, const char *piece2)
-    : _p1 (piece1), _p2 (piece2) {}
-  virtual ~Output_Expr2 () {}
+  virtual void          output_expr () const;
+                        Output_Expr2 (const char *piece1, const char *piece2)
+                          : _p1 (piece1), _p2 (piece2) {}
+  virtual               ~Output_Expr2 () {}
 private:
   const char *_p1;
   const char *_p2;
@@ -462,37 +463,76 @@ struct Output_Compare
      the string being looked up.  expr2 outputs a simple expression of type
      'const char *' referring to the constant string stored in the gperf
      generated hash table.  */
-  virtual void output_comparison (const Output_Expr& expr1,
-                                  const Output_Expr& expr2) const = 0;
-  Output_Compare () {}
-  virtual ~Output_Compare () {}
+  virtual void          output_comparison (const Output_Expr& expr1,
+                                           const Output_Expr& expr2) const = 0;
+  /* Outputs the comparison expression for the first byte.
+     Returns true if the this comparison is complete.  */
+  bool                  output_firstchar_comparison (const Output_Expr& expr1,
+                                                     const Output_Expr& expr2) const;
+                        Output_Compare () {}
+  virtual               ~Output_Compare () {}
 };
 
+bool Output_Compare::output_firstchar_comparison (const Output_Expr& expr1,
+                                                  const Output_Expr& expr2) const
+{
+  /* First, we emit a comparison of the first byte of the two strings.
+     This catches most cases where the string being looked up is not in the
+     hash table but happens to have the same hash code as an element of the
+     hash table.  */
+  if (option[UPPERLOWER])
+    {
+      /* Incomplete comparison, just for speedup.  */
+      printf ("(((unsigned char)*");
+      expr1.output_expr ();
+      printf (" ^ (unsigned char)*");
+      expr2.output_expr ();
+      printf (") & ~32) == 0");
+      return false;
+    }
+  else
+    {
+      /* Complete comparison.  */
+      printf ("*");
+      expr1.output_expr ();
+      printf (" == *");
+      expr2.output_expr ();
+      return true;
+    }
+}
+
 /* This class outputs a comparison using strcmp.  */
 
 struct Output_Compare_Strcmp : public Output_Compare
 {
-  virtual void output_comparison (const Output_Expr& expr1,
-                                  const Output_Expr& expr2) const;
-  Output_Compare_Strcmp () {}
-  virtual ~Output_Compare_Strcmp () {}
+  virtual void          output_comparison (const Output_Expr& expr1,
+                                           const Output_Expr& expr2) const;
+                        Output_Compare_Strcmp () {}
+  virtual               ~Output_Compare_Strcmp () {}
 };
 
 void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
                                                const Output_Expr& expr2) const
 {
-  printf ("*");
-  expr1.output_expr ();
-  printf (" == *");
-  expr2.output_expr ();
+  bool firstchar_done = output_firstchar_comparison (expr1, expr2);
   printf (" && !");
   if (option[UPPERLOWER])
     printf ("gperf_case_");
   printf ("strcmp (");
-  expr1.output_expr ();
-  printf (" + 1, ");
-  expr2.output_expr ();
-  printf (" + 1)");
+  if (firstchar_done)
+    {
+      expr1.output_expr ();
+      printf (" + 1, ");
+      expr2.output_expr ();
+      printf (" + 1");
+    }
+  else
+    {
+      expr1.output_expr ();
+      printf (", ");
+      expr2.output_expr ();
+    }
+  printf (")");
 }
 
 /* This class outputs a comparison using strncmp.
@@ -501,27 +541,35 @@ void Output_Compare_Strcmp::output_comparison (const Output_Expr& expr1,
 
 struct Output_Compare_Strncmp : public Output_Compare
 {
-  virtual void output_comparison (const Output_Expr& expr1,
-                                  const Output_Expr& expr2) const;
-  Output_Compare_Strncmp () {}
-  virtual ~Output_Compare_Strncmp () {}
+  virtual void          output_comparison (const Output_Expr& expr1,
+                                           const Output_Expr& expr2) const;
+                        Output_Compare_Strncmp () {}
+  virtual               ~Output_Compare_Strncmp () {}
 };
 
 void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
                                                 const Output_Expr& expr2) const
 {
-  printf ("*");
-  expr1.output_expr ();
-  printf (" == *");
-  expr2.output_expr ();
+  bool firstchar_done = output_firstchar_comparison (expr1, expr2);
   printf (" && !");
   if (option[UPPERLOWER])
     printf ("gperf_case_");
   printf ("strncmp (");
-  expr1.output_expr ();
-  printf (" + 1, ");
-  expr2.output_expr ();
-  printf (" + 1, len - 1) && ");
+  if (firstchar_done)
+    {
+      expr1.output_expr ();
+      printf (" + 1, ");
+      expr2.output_expr ();
+      printf (" + 1, len - 1");
+    }
+  else
+    {
+      expr1.output_expr ();
+      printf (", ");
+      expr2.output_expr ();
+      printf (", len");
+    }
+  printf (") && ");
   expr2.output_expr ();
   printf ("[len] == '\\0'");
 }
@@ -533,27 +581,35 @@ void Output_Compare_Strncmp::output_comparison (const Output_Expr& expr1,
 
 struct Output_Compare_Memcmp : public Output_Compare
 {
-  virtual void output_comparison (const Output_Expr& expr1,
-                                  const Output_Expr& expr2) const;
-  Output_Compare_Memcmp () {}
-  virtual ~Output_Compare_Memcmp () {}
+  virtual void          output_comparison (const Output_Expr& expr1,
+                                           const Output_Expr& expr2) const;
+                        Output_Compare_Memcmp () {}
+  virtual               ~Output_Compare_Memcmp () {}
 };
 
 void Output_Compare_Memcmp::output_comparison (const Output_Expr& expr1,
                                                const Output_Expr& expr2) const
 {
-  printf ("*");
-  expr1.output_expr ();
-  printf (" == *");
-  expr2.output_expr ();
+  bool firstchar_done = output_firstchar_comparison (expr1, expr2);
   printf (" && !");
   if (option[UPPERLOWER])
     printf ("gperf_case_");
   printf ("memcmp (");
-  expr1.output_expr ();
-  printf (" + 1, ");
-  expr2.output_expr ();
-  printf (" + 1, len - 1)");
+  if (firstchar_done)
+    {
+      expr1.output_expr ();
+      printf (" + 1, ");
+      expr2.output_expr ();
+      printf (" + 1, len - 1");
+    }
+  else
+    {
+      expr1.output_expr ();
+      printf (", ");
+      expr2.output_expr ();
+      printf (", len");
+    }
+  printf (")");
 }
 
 /* ------------------------------------------------------------------------- */
diff --git a/tests/Makefile.in b/tests/Makefile.in
index c7c3c37..0e670b5 100644
--- a/tests/Makefile.in
+++ b/tests/Makefile.in
@@ -1,6 +1,6 @@
 # Makefile for gperf/tests
 
-# Copyright (C) 1989, 1992, 1993, 1995, 1998, 2000, 2002 Free Software Foundation, Inc.
+# Copyright (C) 1989, 1992, 1993, 1995, 1998, 2000, 2002, 2003 Free Software Foundation, Inc.
 # Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
 # and Bruno Haible <bruno@clisp.org>.
 #
@@ -58,7 +58,7 @@ installdirs :
 
 uninstall :
 
-check : check-link-c check-link-c++ check-c check-ada check-modula3 check-pascal check-lang-utf8 check-lang-ucs2 check-test
+check : check-link-c check-link-c++ check-c check-ada check-modula3 check-pascal check-lang-utf8 check-lang-ucs2 check-smtp check-test
 	@true
 
 extracheck : @CHECK_LANG_SYNTAX@
@@ -121,6 +121,19 @@ check-lang-ucs2:
 	./lu2out -v < $(srcdir)/lang-ucs2.in > lang-ucs2.out
 	diff $(srcdir)/lang-ucs2.exp lang-ucs2.out
 
+# check case-insensitive lookup
+check-smtp:
+	@echo "testing SMTP keywords, case-insensitive"
+	$(GPERF) --struct-type --readonly-table --enum --global -K field_name -N header_entry --ignore-case $(srcdir)/smtp.gperf > smtp.c
+	$(CC) $(CFLAGS) -o smtp smtp.c
+	./smtp
+	$(GPERF) --struct-type --readonly-table --enum --global -K field_name -N header_entry --ignore-case --compare-strncmp $(srcdir)/smtp.gperf > smtp.c
+	$(CC) $(CFLAGS) -o smtp smtp.c
+	./smtp
+	$(GPERF) --struct-type --readonly-table --enum --global -K field_name -N header_entry --ignore-case --compare-lengths $(srcdir)/smtp.gperf > smtp.c
+	$(CC) $(CFLAGS) -o smtp smtp.c
+	./smtp
+
 # these next 5 are demos that show off the generated code
 check-test:
 	$(GPERF) -L C -F ', 0, 0' -p -j1 -i 1 -g -o -t -G -N is_reserved_word -k1,3,'$$' < $(srcdir)/c-parse.gperf > c-parse.out
@@ -273,7 +286,7 @@ check-lang-syntax : force
 mostlyclean : clean
 
 clean : force
-	$(RM) *.o core *inset.c output.* *.out aout cout lu2out lu8out m3out pout preout tmp-* valitest*
+	$(RM) *.o core *inset.c output.* *.out aout cout lu2out lu8out m3out pout preout smtp.c smtp tmp-* valitest*
 
 distclean : clean
 	$(RM) config.status config.log config.cache Makefile
diff --git a/tests/permutc2.exp b/tests/permutc2.exp
index 02632d5..30eb911 100644
--- a/tests/permutc2.exp
+++ b/tests/permutc2.exp
@@ -108,7 +108,7 @@ in_word_set (str, len)
         {
           register const char *s = wordlist[key];
 
-          if (*str == *s && !gperf_case_strcmp (str + 1, s + 1))
+          if ((((unsigned char)*str ^ (unsigned char)*s) & ~32) == 0 && !gperf_case_strcmp (str, s))
             return s;
         }
     }
diff --git a/tests/smtp.gperf b/tests/smtp.gperf
new file mode 100644
index 0000000..33137b9
--- /dev/null
+++ b/tests/smtp.gperf
@@ -0,0 +1,206 @@
+%{
+/* gperf --struct-type --readonly-table --enum --global -K field_name -N header_entry --ignore-case */
+/* Contributed by Bruce Lilly
+   derived from http://users.erols.com/blilly/mailparse/fields.gperf */
+
+#include <string.h>
+
+%}
+struct header_state { const char *field_name; };
+%%
+Accept-Language
+Action
+Alternate-Recipient
+Approved
+Archive
+Arrival-Date
+Autoforwarded
+Autosubmitted
+Bcc
+Cc
+Comments
+Complaints-To
+Content-alternative
+Content-Base
+Content-Description
+Content-Disposition
+Content-Duration
+Content-Features
+Content-ID
+Content-Language
+Content-Location
+Content-MD5
+Content-Transfer-Encoding
+Content-Type
+Control
+Conversion
+Conversion-With-Loss
+DL-Expansion-History
+DSN-Gateway
+Date
+Deferred-Delivery
+Delivery-Date
+Diagnostic-Code
+Discarded-X400-IPMS-Extensions
+Discarded-X400-MTS-Extensions
+Disclose-Recipients
+Disposition
+Disposition-Notification-Options
+Disposition-Notification-To
+Distribution
+Encrypted
+Error
+Expires
+Failure
+Final-Log-ID
+Final-Recipient
+Followup-To
+From
+Generate-Delivery-Report
+Importance
+In-Reply-To
+Incomplete-Copy
+Injector-Info
+Keywords
+Last-Attempt-Date
+Latest-Delivery-Time
+Lines
+List-Archive
+List-Help
+List-ID
+List-Post
+List-Owner
+List-Subscribe
+List-Unsubscribe
+MDN-Gateway
+Media-Accept-Features
+MIME-Version
+Mail-Copies-To
+Message-ID
+Message-Type
+Newsgroups
+Organization
+Original-Encoded-Information-Types
+Original-Envelope-ID
+Original-Message-ID
+Original-Recipient
+Originator-Return-Address
+Path
+Posted-And-Mailed
+Prevent-Nondelivery-Report
+Priority
+Received
+Received-content-MIC
+Received-From-MTA
+References
+Remote-MTA
+Reply-By
+Reply-To
+Reporting-MTA
+Reporting-UA
+Return-Path
+Sender
+Sensitivity
+Status
+Subject
+Summary
+Supersedes
+To
+User-Agent
+Warning
+Will-Retry-Until
+X400-Content-Identifier
+X400-Content-Return
+X400-Content-Type
+X400-MTS-Identifier
+X400-Originator
+X400-Received
+X400-Recipients
+Xref
+%%
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+static int
+my_case_strcmp (s1, s2)
+     register const char *s1;
+     register const char *s2;
+{
+  for (;;)
+    {
+      unsigned char c1 = *s1++;
+      unsigned char c2 = *s2++;
+      if (c1 >= 'A' && c1 <= 'Z')
+        c1 += 'a' - 'A';
+      if (c2 >= 'A' && c2 <= 'Z')
+        c2 += 'a' - 'A';
+      if (c1 != 0 && c1 == c2)
+        continue;
+      return (int)c1 - (int)c2;
+    }
+}
+
+int
+main (argc, argv)
+     int argc;
+     char *argv[];
+{
+  int i, j, k, n, exitcode;
+  unsigned int len;
+  const struct header_state *hs;
+
+  n = 1;
+  if (argc > 1)
+    n = atoi (argv[1]);
+  if (n < 1)
+    n = 1;
+
+  exitcode = 0;
+  for (i = 0; i < n; i++)
+    {
+      for (j = 0; j <= MAX_HASH_VALUE; j++)
+        {
+          const char *s = wordlist[j].field_name;
+          len = strlen (s);
+          if (len)
+            {
+              hs = header_entry (s, len);
+              if (!(hs && strcmp (hs->field_name, s) == 0))
+                {
+                  fprintf (stderr, "%s != %s\n", s, hs ? hs->field_name : "(null)");
+                  exitcode = 1;
+                }
+            }
+        }
+      for (j = 0; j <= MAX_HASH_VALUE; j++)
+        {
+          char s[MAX_WORD_LENGTH+1];
+          /* expensive copy with case conversion (for testing) */
+          strcpy (s, wordlist[j].field_name);
+          len = strlen (s);
+          if (len)
+            {
+              for (k = 0; k < len; k++)
+                if (isupper (s[k]))
+                  s[k] = tolower (s[k]);
+                else if (islower (s[k]))
+                  s[k] = toupper (s[k]);
+              hs = header_entry (s, len);
+              if (!(hs && my_case_strcmp (hs->field_name, s) == 0))
+                {
+                  fprintf (stderr, "%s != %s\n", s, hs ? hs->field_name : "(null)");
+                  exitcode = 1;
+                }
+            }
+        }
+      hs = header_entry ("Dave", 4);
+      if (hs)
+        {
+          fprintf (stderr, "Dave == %s\n", hs->field_name);
+          exitcode = 1;
+        }
+    }
+  return exitcode;
+}