(struct xlfdpat_block, struct xlfdpat): New structs.

(xlfdpat_destroy, xlfdpat_create, xlfdpat_exact_p)
(xlfdpat_block_match_1, xlfdpat_match): New functions.
(xlfdpat_block_match): New macro.
(mac_to_x_fontname): Don't use tolower for non-ASCII characters.
(x_font_name_to_mac_font_name): Set coding.dst_multibyte to 0.
(add_font_name_table_entry): Increase font_name_table_size more
rapidly.
(mac_c_string_match): Remove function.
(mac_do_list_fonts): Use XLFD pattern match instead of regular
expression match.

1 files changed, 357 insertions, 88 deletions

diff --git a/src/macterm.c b/src/macterm.c
index 3c7af5f1cef..362da7f77c7 100644
--- a/src/macterm.c
+++ b/src/macterm.c
@@ -6084,6 +6084,335 @@ x_wm_set_icon_position (f, icon_x, icon_y)
 
 
 /***********************************************************************
+                          XLFD Pattern Match
+ ***********************************************************************/
+
+/* An XLFD pattern is divided into blocks delimited by '*'.  This
+   structure holds information for each block.  */
+struct xlfdpat_block
+{
+  /* Length of the pattern string in this block.  Non-zero except for
+     the first and the last blocks.  */
+  int len;
+
+  /* Pattern string except the last character in this block.  The last
+     character is replaced with NUL in order to use it as a
+     sentinel.  */
+  unsigned char *pattern;
+
+  /* Last character of the pattern string.  Must not be '?'.  */
+  unsigned char last_char;
+
+  /* One of the tables for the Boyer-Moore string search.  It
+     specifies the number of positions to proceed for each character
+     with which the match fails.  */
+  int skip[256];
+
+  /* The skip value for the last character in the above `skip' is
+     assigned to `infinity' in order to simplify a loop condition.
+     The original value is saved here.  */
+  int last_char_skip;
+};
+
+struct xlfdpat
+{
+  /* Normalized pattern string.  "Normalized" means that capital
+     letters are lowered, blocks are not empty except the first and
+     the last ones, and trailing '?'s in a block that is not the last
+     one are moved to the next one.  The last character in each block
+     is replaced with NUL.  */
+  unsigned char *buf;
+
+  /* Number of characters except '*'s and trailing '?'s in the
+     normalized pattern string.  */
+  int nchars;
+
+  /* Number of trailing '?'s in the normalized pattern string.  */
+  int trailing_anychars;
+
+  /* Number of blocks and information for each block.  The latter is
+     NULL if the pattern is exact (no '*' or '?' in it).  */
+  int nblocks;
+  struct xlfdpat_block *blocks;
+};
+
+static void
+xlfdpat_destroy (pat)
+     struct xlfdpat *pat;
+{
+  if (pat)
+    {
+      if (pat->buf)
+        {
+          if (pat->blocks)
+            xfree (pat->blocks);
+          xfree (pat->buf);
+        }
+      xfree (pat);
+    }
+}
+
+static struct xlfdpat *
+xlfdpat_create (pattern)
+     char *pattern;
+{
+  struct xlfdpat *pat;
+  int nblocks, i, skip;
+  unsigned char last_char, *p, *q, *anychar_head;
+  struct xlfdpat_block *blk;
+
+  pat = xmalloc (sizeof (struct xlfdpat));
+  if (pat == NULL)
+    goto error;
+
+  pat->buf = xmalloc (strlen (pattern) + 1);
+  if (pat->buf == NULL)
+    goto error;
+
+  /* Normalize the pattern string and store it to `pat->buf'.  */
+  nblocks = 0;
+  anychar_head = NULL;
+  q = pat->buf;
+  last_char = '\0';
+  for (p = pattern; *p; p++)
+    {
+      unsigned char c = *p;
+
+      if (c == '*')
+        if (last_char == '*')
+          /*  ...a** -> ...a*  */
+          continue;
+        else
+          {
+            if (last_char == '?')
+              if (anychar_head > pat->buf && *(anychar_head - 1) == '*')
+                /*  ...*??* -> ...*??  */
+                continue;
+              else
+                /*  ...a??* -> ...a*??  */
+                {
+                  *anychar_head++ = '*';
+                  c = '?';
+                }
+            nblocks++;
+          }
+      else if (c == '?')
+        {
+          if (last_char != '?')
+            anychar_head = q;
+        }
+      else
+        /* On Mac OS X 10.3, tolower also converts non-ASCII
+           characters for some locales.  */
+        if (isascii (c))
+          c = tolower (c);
+
+      *q++ = last_char = c;
+    }
+  *q = '\0';
+  nblocks++;
+  pat->nblocks = nblocks;
+  if (last_char != '?')
+    pat->trailing_anychars = 0;
+  else
+    {
+      pat->trailing_anychars = q - anychar_head;
+      q = anychar_head;
+    }
+  pat->nchars = q - pat->buf - (nblocks - 1);
+
+  if (anychar_head == NULL && nblocks == 1)
+    {
+      /* The pattern is exact.  */
+      pat->blocks = NULL;
+      return pat;
+    }
+
+  pat->blocks = xmalloc (sizeof (struct xlfdpat_block) * nblocks);
+  if (pat->blocks == NULL)
+    goto error;
+
+  /* Divide the normalized pattern into blocks.  */
+  p = pat->buf;
+  for (blk = pat->blocks; blk < pat->blocks + nblocks - 1; blk++)
+    {
+      blk->pattern = p;
+      while (*p != '*')
+        p++;
+      blk->len = p - blk->pattern;
+      p++;
+    }
+  blk->pattern = p;
+  blk->len = q - blk->pattern;
+
+  /* Setup a table for the Boyer-Moore string search.  */
+  for (blk = pat->blocks; blk < pat->blocks + nblocks; blk++)
+    if (blk->len != 0)
+      {
+        blk->last_char = blk->pattern[blk->len - 1];
+        blk->pattern[blk->len - 1] = '\0';
+
+        for (skip = 1; skip < blk->len; skip++)
+          if (blk->pattern[blk->len - skip - 1] == '?')
+            break;
+
+        for (i = 0; i < 256; i++)
+          blk->skip[i] = skip;
+
+        p = blk->pattern + (blk->len - skip);
+        while (--skip > 0)
+          blk->skip[*p++] = skip;
+
+        blk->last_char_skip = blk->skip[blk->last_char];
+      }
+
+  return pat;
+
+ error:
+  xlfdpat_destroy (pat);
+  return NULL;
+}
+
+static INLINE int
+xlfdpat_exact_p (pat)
+     struct xlfdpat *pat;
+{
+  return (pat)->blocks == NULL;
+}
+
+/* Return the first string in STRING + 0, ..., STRING + START_MAX such
+   that the pattern in *BLK matches with its prefix.  Return NULL
+   there is no such strings.  STRING must be lowered in advance.  */
+
+static char *
+xlfdpat_block_match_1 (blk, string, start_max)
+     struct xlfdpat_block *blk;
+     unsigned char *string;
+     int start_max;
+{
+  int start, infinity;
+  unsigned char *p, *s;
+
+  xassert (blk->len > 0);
+  xassert (start_max + blk->len <= strlen (string));
+  xassert (blk->pattern[blk->len - 1] != '?');
+
+  /* See the comments in the function `boyer_moore' (search.c) for the
+     use of `infinity'.  */
+  infinity = start_max + blk->len + 1;
+  blk->skip[blk->last_char] = infinity;
+
+  start = 0;
+  do
+    {
+      /* Check the last character of the pattern. */
+      s = string + blk->len - 1;
+      do
+        {
+          start += blk->skip[*(s + start)];
+        }
+      while (start <= start_max);
+
+      if (start < infinity)
+        /* Couldn't find the last character.  */
+        return NULL;
+
+      /* No less than `infinity' means we could find the last
+         character at `s[start - infinity]'.  */
+      start -= infinity;
+
+      /* Check the remaining characters.  We prefer making no-'?'
+         cases faster because the use of '?' is really rare.  */
+      p = blk->pattern;
+      s = string + start;
+      do
+        {
+          while (*p++ == *s++)
+            ;
+        }
+      while (*(p - 1) == '?');
+
+      if (*(p - 1) == '\0')
+        /* Matched.  */
+        return string + start;
+
+      /* Didn't match.  */
+      start += blk->last_char_skip;
+    }
+  while (start <= start_max);
+
+  return NULL;
+}
+
+#define xlfdpat_block_match(b, s, m) \
+  ((b)->len == 1 ? memchr ((s), (b)->last_char, (m) + 1) \
+   : xlfdpat_block_match_1 (b, s, m))
+
+/* Check if XLFD pattern PAT, which is generated by `xfldpat_create',
+   matches with STRING.  STRING must be lowered in advance.  */
+
+static int
+xlfdpat_match (pat, string)
+     struct xlfdpat *pat;
+     unsigned char *string;
+{
+  int str_len, nblocks, i, start_max;
+  struct xlfdpat_block *blk;
+  unsigned char *s;
+
+  xassert (pat->nblocks > 0);
+
+  if (xlfdpat_exact_p (pat))
+    return strcmp (pat->buf, string) == 0;
+
+  /* The number of the characters in the string must not be smaller
+     than that in the pattern.  */
+  str_len = strlen (string);
+  if (str_len < pat->nchars + pat->trailing_anychars)
+    return 0;
+
+  /* Chop off the trailing '?'s.  */
+  str_len -= pat->trailing_anychars;
+
+  /* The last block.  When it is non-empty, it must match at the end
+     of the string.  */
+  nblocks = pat->nblocks;
+  blk = pat->blocks + (nblocks - 1);
+  if (nblocks == 1)
+    /* The last block is also the first one.  */
+    return (str_len == blk->len
+            && (blk->len == 0 || xlfdpat_block_match (blk, string, 0)));
+  else if (blk->len != 0)
+    if (!xlfdpat_block_match (blk, string + (str_len - blk->len), 0))
+      return 0;
+
+  /* The first block.  When it is non-empty, it must match at the
+     beginning of the string.  */
+  blk = pat->blocks;
+  if (blk->len != 0)
+    {
+      s = xlfdpat_block_match (blk, string, 0);
+      if (s == NULL)
+        return 0;
+      string = s + blk->len;
+    }
+
+  /* The rest of the blocks.  */
+  start_max = str_len - pat->nchars;
+  for (i = 1, blk++; i < nblocks - 1; i++, blk++)
+    {
+      s = xlfdpat_block_match (blk, string, start_max);
+      if (s == NULL)
+        return 0;
+      start_max -= s - string;
+      string = s + blk->len;
+    }
+
+  return 1;
+}
+
+
+/***********************************************************************
                                 Fonts
  ***********************************************************************/
 
@@ -6178,7 +6507,8 @@ mac_to_x_fontname (name, size, style, charset)
 {
   Str31 foundry, cs;
   Str255 family;
-  char xf[256], *result, *p;
+  char xf[256], *result;
+  unsigned char *p;
 
   if (sscanf (name, "%31[^-]-%255[^-]-%31s", foundry, family, cs) == 3)
     charset = cs;
@@ -6195,7 +6525,10 @@ mac_to_x_fontname (name, size, style, charset)
   result = xmalloc (strlen (foundry) + strlen (family) + strlen (xf) + 3 + 1);
   sprintf (result, "-%s-%s-%s", foundry, family, xf);
   for (p = result; *p; p++)
-    *p = tolower(*p);
+    /* On Mac OS X 10.3, tolower also converts non-ASCII characters
+       for some locales.  */
+    if (isascii (*p))
+      *p = tolower (*p);
   return result;
 }
 
@@ -6253,7 +6586,7 @@ x_font_name_to_mac_font_name (xf, mf, mf_decoded, style, cs)
     {
       setup_coding_system (coding_system, &coding);
       coding.src_multibyte = 1;
-      coding.dst_multibyte = 1;
+      coding.dst_multibyte = 0;
       coding.mode |= CODING_MODE_LAST_BLOCK;
       encode_coding (&coding, mf_decoded, mf,
                      strlen (mf_decoded), sizeof (Str255) - 1);
@@ -6267,13 +6600,13 @@ add_font_name_table_entry (char *font_name)
 {
   if (font_name_table_size == 0)
     {
-      font_name_table_size = 16;
+      font_name_table_size = 256;
       font_name_table = (char **)
         xmalloc (font_name_table_size * sizeof (char *));
     }
   else if (font_name_count + 1 >= font_name_table_size)
     {
-      font_name_table_size += 16;
+      font_name_table_size *= 2;
       font_name_table = (char **)
         xrealloc (font_name_table,
                   font_name_table_size * sizeof (char *));
@@ -6498,39 +6831,16 @@ static int xlfd_scalable_fields[] =
   };
 
 static Lisp_Object
-mac_c_string_match (regexp, string, nonspecial, exact)
-     Lisp_Object regexp;
-     const char *string, *nonspecial;
-     int exact;
-{
-  if (exact)
-    {
-      if (strcmp (string, nonspecial) == 0)
-        return build_string (string);
-    }
-  else if (strstr (string, nonspecial))
-    {
-      Lisp_Object str = build_string (string);
-
-      if (fast_string_match (regexp, str) >= 0)
-        return str;
-    }
-
-  return Qnil;
-}
-
-static Lisp_Object
 mac_do_list_fonts (pattern, maxnames)
      char *pattern;
      int maxnames;
 {
   int i, n_fonts = 0;
-  Lisp_Object font_list = Qnil, pattern_regex, fontname;
-  char *regex = (char *) alloca (strlen (pattern) * 2 + 3);
+  Lisp_Object font_list = Qnil;
+  struct xlfdpat *pat;
   char *scaled, *ptr;
   int scl_val[XLFD_SCL_LAST], *field, *val;
-  char *longest_start, *cur_start, *nonspecial;
-  int longest_len, exact;
+  int exact;
 
   if (font_name_table == NULL)  /* Initialize when first used.  */
     init_font_name_table ();
@@ -6588,61 +6898,17 @@ mac_do_list_fonts (pattern, maxnames)
   else
     scl_val[XLFD_SCL_PIXEL_SIZE] = -1;
 
-  ptr = regex;
-  *ptr++ = '^';
-
-  longest_start = cur_start = ptr;
-  longest_len = 0;
-  exact = 1;
-
-  /* Turn pattern into a regexp and do a regexp match.  Also find the
-     longest substring containing no special characters.  */
-  for (; *pattern; pattern++)
-    {
-      if (*pattern == '?' || *pattern == '*')
-        {
-          if (ptr - cur_start > longest_len)
-            {
-              longest_start = cur_start;
-              longest_len = ptr - cur_start;
-            }
-          exact = 0;
-
-          if (*pattern == '?')
-            *ptr++ = '.';
-          else /* if (*pattern == '*') */
-            {
-              *ptr++ = '.';
-              *ptr++ = '*';
-            }
-          cur_start = ptr;
-        }
-      else
-        *ptr++ = tolower (*pattern);
-    }
-
-  if (ptr - cur_start > longest_len)
-    {
-      longest_start = cur_start;
-      longest_len = ptr - cur_start;
-    }
-
-  *ptr = '$';
-  *(ptr + 1) = '\0';
-
-  nonspecial = xmalloc (longest_len + 1);
-  strncpy (nonspecial, longest_start, longest_len);
-  nonspecial[longest_len] = '\0';
+  pat = xlfdpat_create (pattern);
+  if (pat == NULL)
+    return Qnil;
 
-  pattern_regex = build_string (regex);
+  exact = xlfdpat_exact_p (pat);
 
   for (i = 0; i < font_name_count; i++)
     {
-      fontname = mac_c_string_match (pattern_regex, font_name_table[i],
-                                     nonspecial, exact);
-      if (!NILP (fontname))
+      if (xlfdpat_match (pat, font_name_table[i]))
         {
-          font_list = Fcons (fontname, font_list);
+          font_list = Fcons (build_string (font_name_table[i]), font_list);
           if (exact || maxnames > 0 && ++n_fonts >= maxnames)
             break;
         }
@@ -6652,6 +6918,8 @@ mac_do_list_fonts (pattern, maxnames)
           int former_len = ptr - font_name_table[i];
 
           scaled = xmalloc (strlen (font_name_table[i]) + 20 + 1);
+          if (scaled == NULL)
+            continue;
           memcpy (scaled, font_name_table[i], former_len);
           sprintf (scaled + former_len,
                    "-%d-%d-75-75-m-%d-%s",
@@ -6659,19 +6927,20 @@ mac_do_list_fonts (pattern, maxnames)
                    scl_val[XLFD_SCL_POINT_SIZE],
                    scl_val[XLFD_SCL_AVGWIDTH],
                    ptr + sizeof ("-0-0-0-0-m-0-") - 1);
-          fontname = mac_c_string_match (pattern_regex, scaled,
-                                         nonspecial, exact);
-          xfree (scaled);
-          if (!NILP (fontname))
+
+          if (xlfdpat_match (pat, scaled))
             {
-              font_list = Fcons (fontname, font_list);
+              font_list = Fcons (build_string (scaled), font_list);
+              xfree (scaled);
               if (exact || maxnames > 0 && ++n_fonts >= maxnames)
-                break;
+                  break;
             }
+          else
+            xfree (scaled);
         }
     }
 
-  xfree (nonspecial);
+  xlfdpat_destroy (pat);
 
   return font_list;
 }