+/***********************************************************************
+ 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->last_char != '?');
+
+ /* 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;
+}
+
+\f