/*
 * frost_str.c
 *
 *  Created on: Jul 1, 2012
 *      Author: ergino
 */

#include "frost_str.h"
#include "frost_mem.h"
#include <stdio.h>

#define frost_warning   printf

/* This is not a macro, because I dont want to put _GNU_SOURCE in the glib.h header */
char *
frost_strndup (const char *str, frost_ulong n)
{
#ifdef HAVE_STRNDUP
    return strndup (str, n);
#else
    if (str) {
        char *retval = frost_malloc(n+1);
        if (retval) {
            strncpy(retval, str, n)[n] = 0;
        }
        return retval;
    }
    return NULL;
#endif
}

void
frost_strfreev (char **str_array)
{
    char **orig = str_array;
    if (str_array == NULL)
        return;
    while (*str_array != NULL){
        frost_free (*str_array);
        str_array++;
    }
    frost_free (orig);
}

char **
frost_strdupv (char **str_array)
{
    frost_uint length;
    char **ret;
    frost_uint i;

    if (!str_array)
        return NULL;

    length = frost_strv_length(str_array);
    ret = frost_new0(char *, length + 1);
    for (i = 0; str_array[i]; i++) {
        ret[i] = frost_strdup(str_array[i]);
    }
    ret[length] = NULL;
    return ret;
}

frost_uint
frost_strv_length(char **str_array)
{
    frost_int length = 0;
    frost_return_val_if_fail(str_array != NULL, 0);
    for(length = 0; str_array[length] != NULL; length++);
    return length;
}

frost_bool
frost_str_has_suffix(const char *str, const char *suffix)
{
    size_t str_length;
    size_t suffix_length;

    frost_return_val_if_fail(str != NULL, frost_false);
    frost_return_val_if_fail(suffix != NULL, frost_false);

    str_length = strlen(str);
    suffix_length = strlen(suffix);

    return suffix_length <= str_length ?
        strncmp(str + str_length - suffix_length, suffix, suffix_length) == 0 :
        frost_false;
}

frost_bool
frost_str_has_prefix(const char *str, const char *prefix)
{
    size_t str_length;
    size_t prefix_length;

    frost_return_val_if_fail(str != NULL, frost_false);
    frost_return_val_if_fail(prefix != NULL, frost_false);

    str_length = strlen(str);
    prefix_length = strlen(prefix);

    return prefix_length <= str_length ?
        strncmp(str, prefix, prefix_length) == 0 :
        frost_false;
}

char *
frost_strdup_vprintf (const char *format, va_list args)
{
    int n;
    char *ret;

    n = vasprintf (&ret, format, args);
    if (n == -1)
        return NULL;

    return ret;
}

char *
frost_strdup_printf (const char *format, ...)
{
    char *ret;
    va_list args;
    int n;

    va_start (args, format);
    n = vasprintf (&ret, format, args);
    va_end (args);
    if (n == -1)
        return NULL;

    return ret;
}

const char *
frost_strerror (frost_int errnum)
{
    return strerror (errnum);
}

char *
frost_strconcat (const char *first, ...)
{
    va_list args;
    size_t total = 0;
    char *s, *ret;
    frost_return_val_if_fail (first != NULL, NULL);

    total += strlen (first);
    va_start (args, first);
    for (s = va_arg (args, char *); s != NULL; s = va_arg(args, char *)){
        total += strlen (s);
    }
    va_end (args);

    ret = frost_malloc (total + 1);
    if (ret == NULL)
        return NULL;

    ret [total] = 0;
    strcpy (ret, first);
    va_start (args, first);
    for (s = va_arg (args, char *); s != NULL; s = va_arg(args, char *)){
        strcat (ret, s);
    }
    va_end (args);

    return ret;
}

static void
add_to_vector (char ***vector, int size, char *token)
{
    *vector = *vector == NULL ?
        (char **)frost_malloc(2 * sizeof(*vector)) :
        (char **)frost_realloc(*vector, (size + 1) * sizeof(*vector));

    (*vector)[size - 1] = token;
}

char **
frost_strsplit (const char *string, const char *delimiter, frost_int max_tokens)
{
    const char *c;
    char *token, **vector;
    frost_int size = 1;

    frost_return_val_if_fail (string != NULL, NULL);
    frost_return_val_if_fail (delimiter != NULL, NULL);
    frost_return_val_if_fail (delimiter[0] != 0, NULL);

    if (strncmp (string, delimiter, strlen (delimiter)) == 0) {
        vector = (char **)frost_malloc (2 * sizeof(vector));
        vector[0] = frost_strdup ("");
        size++;
        string += strlen (delimiter);
    } else {
        vector = NULL;
    }

    while (*string && !(max_tokens > 0 && size >= max_tokens)) {
        c = string;
        if (strncmp (string, delimiter, strlen (delimiter)) == 0) {
            token = frost_strdup ("");
            string += strlen (delimiter);
        } else {
            while (*string && strncmp (string, delimiter, strlen (delimiter)) != 0) {
                string++;
            }

            if (*string) {
                frost_ulong toklen = (string - c);
                token = frost_strndup (c, toklen);

                /* Need to leave a trailing empty
                 * token if the delimiter is the last
                 * part of the string
                 */
                if (strcmp (string, delimiter) != 0) {
                    string += strlen (delimiter);
                }
            } else {
                token = frost_strdup (c);
            }
        }

        add_to_vector (&vector, size, token);
        size++;
    }

    if (*string) {
        /* Add the rest of the string as the last element */
        add_to_vector (&vector, size, frost_strdup (string));
        size++;
    }

    if (vector == NULL) {
        vector = (char **) frost_malloc (2 * sizeof (vector));
        vector [0] = NULL;
    } else if (size > 0) {
        vector[size - 1] = NULL;
    }

    return vector;
}

static frost_bool
charcmp (char testchar, const char *compare)
{
    while(*compare) {
        if (*compare == testchar) {
            return frost_true;
        }
        compare++;
    }

    return frost_false;
}

char **
frost_strsplit_set (const char *string, const char *delimiter, frost_int max_tokens)
{
    const char *c;
    char *token, **vector;
    frost_int size = 1;

    frost_return_val_if_fail (string != NULL, NULL);
    frost_return_val_if_fail (delimiter != NULL, NULL);
    frost_return_val_if_fail (delimiter[0] != 0, NULL);

    if (charcmp (*string, delimiter)) {
        vector = (char **)frost_malloc (2 * sizeof(vector));
        vector[0] = frost_strdup ("");
        size++;
        string++;
    } else {
        vector = NULL;
    }

    c = string;
    while (*string && !(max_tokens > 0 && size >= max_tokens)) {
        if (charcmp (*string, delimiter)) {
            frost_ulong toklen = (string - c);
            if (toklen == 0) {
                token = frost_strdup ("");
            } else {
                token = frost_strndup (c, toklen);
            }

            c = string + 1;

            add_to_vector (&vector, size, token);
            size++;
        }

        string++;
    }

    if (max_tokens > 0 && size >= max_tokens) {
        if (*string) {
            /* Add the rest of the string as the last element */
            add_to_vector (&vector, size, frost_strdup (string));
            size++;
        }
    } else {
        if (*c) {
            /* Fill in the trailing last token */
            add_to_vector (&vector, size, frost_strdup (c));
            size++;
        } else {
            /* Need to leave a trailing empty token if the
             * delimiter is the last part of the string
             */
            add_to_vector (&vector, size, frost_strdup (""));
            size++;
        }
    }

    if (vector == NULL) {
        vector = (char **) frost_malloc (2 * sizeof (vector));
        vector [0] = NULL;
    } else if (size > 0) {
        vector[size - 1] = NULL;
    }

    return vector;
}

char *
frost_strreverse (char *str)
{
    size_t i, j;
    char c;

    if (str == NULL)
        return NULL;

    for (i = 0, j = strlen (str) - 1; i < j; i++, j--) {
        c = str [i];
        str [i] = str [j];
        str [j] = c;
    }

    return str;
}

char *
frost_strjoin (const char *separator, ...)
{
    va_list args;
    char *res, *s, *r;
    size_t len, slen;

    if (separator != NULL)
        slen = strlen (separator);
    else
        slen = 0;

    len = 0;
    va_start (args, separator);
    for (s = va_arg (args, char *); s != NULL; s = va_arg (args, char *)){
        len += strlen (s);
        len += slen;
    }
    va_end (args);

    if (len == 0)
        return frost_strdup ("");

    /* Remove the last separator */
    if (slen > 0 && len > 0)
        len -= slen;

    res = frost_malloc (len + 1);
    va_start (args, separator);
    s = va_arg (args, char *);
    r = frost_stpcpy (res, s);
    for (s = va_arg (args, char *); s != NULL; s = va_arg (args, char *)){
        if (separator != NULL)
            r = frost_stpcpy (r, separator);
        r = frost_stpcpy (r, s);
    }
    va_end (args);

    return res;
}

char *
frost_strjoinv (const char *separator, char **str_array)
{
    char *res, *r;
    size_t slen, len, i;

    if (separator != NULL)
        slen = strlen (separator);
    else
        slen = 0;

    len = 0;
    for (i = 0; str_array [i] != NULL; i++){
        len += strlen (str_array [i]);
        len += slen;
    }

    if (len == 0)
        return frost_strdup ("");

    if (slen > 0 && len > 0)
        len -= slen;

    res = frost_malloc (len + 1);
    r = frost_stpcpy (res, str_array [0]);
    for (i = 1; str_array [i] != NULL; i++){
        if (separator != NULL)
            r = frost_stpcpy (r, separator);
        r = frost_stpcpy (r, str_array [i]);
    }

    return res;
}

char *
frost_strchug (char *str)
{
    size_t len;
    char *tmp;

    if (str == NULL)
        return NULL;

    tmp = str;
    while (*tmp && isspace (*tmp)) tmp++;
    if (str != tmp) {
        len = strlen (str) - (tmp - str - 1);
        memmove (str, tmp, len);
    }
    return str;
}

char *
frost_strchomp (char *str)
{
    char *tmp;

    if (str == NULL)
        return NULL;

    tmp = str + strlen (str) - 1;
    while (*tmp && isspace (*tmp)) tmp--;
    *(tmp + 1) = '\0';
    return str;
}

frost_int
frost_printf(char const *format, ...)
{
    va_list args;
    frost_int ret;

    va_start(args, format);
    ret = vprintf(format, args);
    va_end(args);

    return ret;
}

frost_int
frost_fprintf(FILE *file, char const *format, ...)
{
    va_list args;
    frost_int ret;

    va_start(args, format);
    ret = vfprintf(file, format, args);
    va_end(args);

    return ret;
}

frost_int
frost_sprintf(char *string, char const *format, ...)
{
    va_list args;
    frost_int ret;

    va_start(args, format);
    ret = vsprintf(string, format, args);
    va_end(args);

    return ret;
}

frost_int
frost_snprintf(char *string, frost_ulong n, char const *format, ...)
{
    va_list args;
    frost_int ret;

    va_start(args, format);
    ret = vsnprintf(string, n, format, args);
    va_end(args);

    return ret;
}

static const char hx [] = { '0', '1', '2', '3', '4', '5', '6', '7',
                  '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };

static frost_bool
char_needs_encoding (char c)
{
    if (((unsigned char)c) >= 0x80)
        return frost_true;

    if ((c >= '@' && c <= 'Z') ||
        (c >= 'a' && c <= 'z') ||
        (c >= '&' && c < 0x3b) ||
        (c == '!') || (c == '$') || (c == '_') || (c == '=') || (c == '~'))
        return frost_false;
    return frost_true;
}

#define ICE_DIR_SEPARATOR '/'
#define ICE_DIR_SEPARATOR_S "/"
#define ICE_IS_DIR_SEPARATOR(c) ((c) == ICE_DIR_SEPARATOR)

frost_bool
frost_path_is_absolute (const char *file_name)
{
  frost_return_val_if_fail (file_name != NULL, frost_false);

  if (ICE_IS_DIR_SEPARATOR (file_name[0]))
    return frost_true;

  return frost_false;
}

char *
frost_filename_to_uri (const char *filename, const char *hostname, ice_error_code_t **error)
{
    size_t n;
    char *ret, *rp;
    const char *p;
#ifdef G_OS_WIN32
    const char *uriPrefix = "file:///";
#else
    const char *uriPrefix = "file://";
#endif

    frost_return_val_if_fail (filename != NULL, NULL);

    if (hostname != NULL)
        frost_warning ("%s", "eglib: frost_filename_to_uri: hostname not handled");

    if (!frost_path_is_absolute (filename)){
        if (error != NULL)
            *error = ICE_ERROR_GENERIC; // frost_error_new (NULL, 2, "Not an absolute filename");

        return NULL;
    }

    n = strlen (uriPrefix) + 1;
    for (p = filename; *p; p++){
#ifdef G_OS_WIN32
        if (*p == '\\') {
            n++;
            continue;
        }
#endif
        if (char_needs_encoding (*p))
            n += 3;
        else
            n++;
    }
    ret = frost_malloc (n);
    strcpy (ret, uriPrefix);
    for (p = filename, rp = ret + strlen (ret); *p; p++){
#ifdef G_OS_WIN32
        if (*p == '\\') {
            *rp++ = '/';
            continue;
        }
#endif
        if (char_needs_encoding (*p)){
            *rp++ = '%';
            *rp++ = hx [((unsigned char)(*p)) >> 4];
            *rp++ = hx [((unsigned char)(*p)) & 0xf];
        } else
            *rp++ = *p;
    }
    *rp = 0;
    return ret;
}

static int
decode (char p)
{
    if (p >= '0' && p <= '9')
        return p - '0';
    if (p >= 'A' && p <= 'F')
        return p - 'A';
    if (p >= 'a' && p <= 'f')
        return p - 'a';
    return 0;
}

char *
frost_filename_from_uri (const char *uri, char **hostname, ice_error_code_t **error)
{
    const char *p;
    char *r, *result;
    int flen = 0;

    frost_return_val_if_fail (uri != NULL, NULL);

    if (hostname != NULL)
        frost_warning ("%s", "eglib: frost_filename_from_uri: hostname not handled");

    if (strncmp (uri, "file:///", 8) != 0){
        if (error != NULL)
            **error = ICE_ERROR_GENERIC;//frost_error_new (NULL, 2, "URI does not start with the file: scheme");
        return NULL;
    }

    for (p = uri + 8; *p; p++){
        if (*p == '%'){
            if (p [1] && p [2] && isxdigit (p [1]) && isxdigit (p [2])){
                p += 2;
            } else {
                if (error != NULL)
                    **error = ICE_ERROR_GENERIC ;//frost_error_new (NULL, 2, "URI contains an invalid escape sequence");
                return NULL;
            }
        }
        flen++;
    }
#ifndef G_OS_WIN32
    flen++;
#endif

    result = frost_malloc (flen + 1);
    result [flen] = 0;

#ifndef G_OS_WIN32
    *result = '/';
    r = result + 1;
#else
    r = result;
#endif

    for (p = uri + 8; *p; p++){
        if (*p == '%'){
            *r++ = (char)((decode (p [1]) << 4) | decode (p [2]));
            p += 2;
        } else
            *r++ = *p;
        flen++;
    }
    return result;
}

void
frost_strdown (char *string)
{
    frost_return_if_fail (string != NULL);

    while (*string){
        *string = (char)tolower (*string);
        string++;
    }
}

char
frost_ascii_tolower (char c)
{
    return c >= 'A' && c <= 'Z' ? c + ('a' - 'A') : c;
}

char *
frost_ascii_strdown (const char *str, frost_long len)
{
    char *ret;
    int i;

    frost_return_val_if_fail  (str != NULL, NULL);

    if (len == -1)
        len = strlen (str);

    ret = frost_malloc (len + 1);
    for (i = 0; i < len; i++)
        ret [i] = (unsigned char) frost_ascii_tolower (str [i]);
    ret [i] = 0;

    return ret;
}

char
frost_ascii_toupper (char c)
{
    return c >= 'a' && c <= 'z' ? c + ('A' - 'a') : c;
}

char *
frost_ascii_strup (const char *str, frost_long len)
{
    char *ret;
    int i;

    frost_return_val_if_fail  (str != NULL, NULL);

    if (len == -1)
        len = strlen (str);

    ret = frost_malloc (len + 1);
    for (i = 0; i < len; i++)
        ret [i] = (unsigned char) frost_ascii_toupper (str [i]);
    ret [i] = 0;

    return ret;
}

frost_int
frost_ascii_strncasecmp (const char *s1, const char *s2, frost_ulong n)
{
    frost_ulong i;

    frost_return_val_if_fail (s1 != NULL, 0);
    frost_return_val_if_fail (s2 != NULL, 0);

    for (i = 0; i < n; i++) {
        char c1 = frost_ascii_tolower (*s1++);
        char c2 = frost_ascii_tolower (*s2++);

        if (c1 != c2)
            return c1 - c2;
    }

    return 0;
}

frost_int
frost_ascii_strcasecmp (const char *s1, const char *s2)
{
    const char *sp1 = s1;
    const char *sp2 = s2;

    frost_return_val_if_fail (s1 != NULL, 0);
    frost_return_val_if_fail (s2 != NULL, 0);

    while (*sp1 != '\0') {
        char c1 = frost_ascii_tolower (*sp1++);
        char c2 = frost_ascii_tolower (*sp2++);

        if (c1 != c2)
            return c1 - c2;
    }

    return (*sp1) - (*sp2);
}

char *
frost_strdelimit (char *string, const char *delimiters, char new_delimiter)
{
    char *ptr;

    frost_return_val_if_fail (string != NULL, NULL);

    if (delimiters == NULL)
        delimiters = FROST_STR_DELIMITERS;

    for (ptr = string; *ptr; ptr++) {
        if (strchr (delimiters, *ptr))
            *ptr = new_delimiter;
    }

    return string;
}

frost_ulong
frost_strlcpy (char *dest, const char *src, frost_ulong dest_size)
{
#ifdef HAVE_STRLCPY
    return strlcpy (dest, src, dest_size);
#else
    char *d;
    const char *s;
    char c;
    frost_ulong len;

    frost_return_val_if_fail (src != NULL, 0);
    frost_return_val_if_fail (dest != NULL, 0);

    len = dest_size;
    if (len == 0)
        return 0;

    s = src;
    d = dest;
    while (--len) {
        c = *s++;
        *d++ = c;
        if (c == '\0')
            return (dest_size - len - 1);
    }

    /* len is 0 i we get here */
    *d = '\0';
    /* we need to return the length of src here */
    while (*s++) ; /* instead of a plain strlen, we use 's' */
    return s - src - 1;
#endif
}

char *
frost_stpcpy (char *dest, const char *src)
{
    frost_return_val_if_fail (dest != NULL, dest);
    frost_return_val_if_fail (src != NULL, dest);

#if HAVE_STPCPY
    return stpcpy (dest, src);
#else
    while (*src)
        *dest++ = *src++;

    *dest = '\0';

    return dest;
#endif
}

static const char escaped_dflt [256] = {
    1, 1, 1, 1, 1, 1, 1, 1, 'b', 't', 'n', 1, 'f', 'r', 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, '"', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, '\\', 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};

char *
frost_strescape (const char *source, const char *exceptions)
{
    char escaped [256];
    const char *ptr;
    char c;
    char op;
    char *result;
    char *res_ptr;

    frost_return_val_if_fail (source != NULL, NULL);

    memcpy (escaped, escaped_dflt, 256);
    if (exceptions != NULL) {
        for (ptr = exceptions; *ptr; ptr++)
            escaped [(int) *ptr] = 0;
    }
    result = frost_malloc (strlen (source) * 4 + 1); /* Worst case: everything octal. */
    res_ptr = result;
    for (ptr = source; *ptr; ptr++) {
        c = *ptr;
        op = escaped [(int) c];
        if (op == 0) {
            *res_ptr++ = c;
        } else {
            *res_ptr++ = '\\';
            if (op != 1) {
                *res_ptr++ = op;
            } else {
                *res_ptr++ = '0' + ((c >> 6) & 3);
                *res_ptr++ = '0' + ((c >> 3) & 7);
                *res_ptr++ = '0' + (c & 7);
            }
        }
    }
    *res_ptr = '\0';
    return result;
}

frost_int
frost_ascii_xdigit_value (char c)
{
    return ((isxdigit (c) == 0) ? -1 :
        ((c >= '0' && c <= '9') ? (c - '0') :
         ((c >= 'a' && c <= 'f') ? (c - 'a' + 10) :
          (c - 'A' + 10))));
}

char *
frost_strnfill (frost_ulong length, char fill_char)
{
    char *ret = frost_new (char, length + 1);

    memset (ret, fill_char, length);
    ret [length] = 0;
    return ret;
}

#include <string.h>
#include "frost_mem.h"

/* keep enum and structure of gpattern.c and patterntest.c in sync */
typedef enum
{
  ICE_MATCH_ALL,       /* "*A?A*" */
  ICE_MATCH_ALL_TAIL,  /* "*A?AA" */
  ICE_MATCH_HEAD,      /* "AAAA*" */
  ICE_MATCH_TAIL,      /* "*AAAA" */
  ICE_MATCH_EXACT,     /* "AAAAA" */
  ICE_MATCH_LAST
} FROSTMatchType;

struct _FROSTPatternSpec
{
    FROSTMatchType match_type;
  frost_uint      pattern_length;
  frost_uint      min_length;
  frost_uint      max_length;
  char     *pattern;
};


static const char utf8_skip_data[256] = {
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,6,6,1,1
};

static frost_bool
utf8_validate (const unsigned char *inptr, size_t len)
{
    const unsigned char *ptr = inptr + len;
    unsigned char c;

    /* Everything falls through when frost_true... */
    switch (len) {
    default:
        return frost_false;
    case 4:
        if ((c = (*--ptr)) < 0x80 || c > 0xBF)
            return frost_false;

        if ((c == 0xBF || c == 0xBE) && ptr[-1] == 0xBF) {
            if (ptr[-2] == 0x8F || ptr[-2] == 0x9F ||
                ptr[-2] == 0xAF || ptr[-2] == 0xBF)
                return frost_false;
        }
    case 3:
        if ((c = (*--ptr)) < 0x80 || c > 0xBF)
            return frost_false;
    case 2:
        if ((c = (*--ptr)) < 0x80 || c > 0xBF)
            return frost_false;

        /* no fall-through in this inner switch */
        switch (*inptr) {
        case 0xE0: if (c < 0xA0) return frost_false; break;
        case 0xED: if (c > 0x9F) return frost_false; break;
        case 0xEF: if (c == 0xB7 && (ptr[1] > 0x8F && ptr[1] < 0xB0)) return frost_false;
            if (c == 0xBF && (ptr[1] == 0xBE || ptr[1] == 0xBF)) return frost_false;
            break;
        case 0xF0: if (c < 0x90) return frost_false; break;
        case 0xF4: if (c > 0x8F) return frost_false; break;
        default:   if (c < 0x80) return frost_false; break;
        }
    case 1: if (*inptr >= 0x80 && *inptr < 0xC2) return frost_false;
    }

    if (*inptr > 0xF4)
        return frost_false;

    return frost_true;
}

frost_bool
frost_utf8_validate (const char *str, frost_long max_len, const char **end)
{
    unsigned char  *inptr = (unsigned char  *) str;
    frost_bool valid = frost_true;
    frost_uint length, min;
    frost_long n = 0;

    if (max_len == 0)
        return frost_false;

    if (max_len < 0) {
        while (*inptr != 0) {
            length = utf8_skip_data[*inptr];
            if (!utf8_validate (inptr, length)) {
                valid = frost_false;
                break;
            }

            inptr += length;
        }
    } else {
        while (n < max_len) {
            if (*inptr == 0) {
                /* Note: return frost_false if we encounter nul-byte
                 * before max_len is reached. */
                valid = frost_false;
                break;
            }

            length = utf8_skip_data[*inptr];
            min = MIN (length, max_len - n);

            if (!utf8_validate (inptr, min)) {
                valid = frost_false;
                break;
            }

            if (min < length) {
                valid = frost_false;
                break;
            }

            inptr += length;
            n += length;
        }
    }

    if (end != NULL)
        *end = (char *) inptr;

    return valid;
}


const char * const frost_utf8_skip = utf8_skip_data;

#define frost_utf8_next_char(p) (char *)((p) + frost_utf8_skip[*(const unsigned char *)(p)])

char *
frost_utf8_strreverse (const char *str,
           frost_uint       len)
{
  char *r, *result;
  const char *p;

  if (len < 0)
    len = strlen (str);

  result = frost_new (char, len + 1);
  r = result + len;
  p = str;
  while (r > result)
    {
      char *m, skip = frost_utf8_skip[*(const unsigned char *) p];
      r -= skip;
      for (m = r; skip; skip--)
        *m++ = *p++;
    }
  result[len] = 0;

  return result;
}


/* --- functions --- */
static inline frost_bool
frost_pattern_ph_match (const char *match_pattern,
            const char *match_string,
            frost_bool    *wildcard_reached_p)
{
  register const char *pattern, *string;
  register char ch;

  pattern = match_pattern;
  string = match_string;

  ch = *pattern;
  pattern++;
  while (ch)
    {
      switch (ch)
    {
    case '?':
      if (!*string)
        return frost_false;
      string = frost_utf8_next_char (string);
      break;

    case '*':
      *wildcard_reached_p = frost_true;
      do
        {
          ch = *pattern;
          pattern++;
          if (ch == '?')
        {
          if (!*string)
            return frost_false;
          string = frost_utf8_next_char (string);
        }
        }
      while (ch == '*' || ch == '?');
      if (!ch)
        return frost_true;
      do
        {
              frost_bool next_wildcard_reached = frost_false;
          while (ch != *string)
        {
          if (!*string)
            return frost_false;
          string = frost_utf8_next_char (string);
        }
          string++;
          if (frost_pattern_ph_match (pattern, string, &next_wildcard_reached))
        return frost_true;
              if (next_wildcard_reached)
                /* the forthcoming pattern substring up to the next wildcard has
                 * been matched, but a mismatch occoured for the rest of the
                 * pattern, following the next wildcard.
                 * there's no need to advance the current match position any
                 * further if the rest pattern will not match.
                 */
        return frost_false;
        }
      while (*string);
      break;

    default:
      if (ch == *string)
        string++;
      else
        return frost_false;
      break;
    }

      ch = *pattern;
      pattern++;
    }

  return *string == 0;
}

frost_bool
frost_pattern_match (FROSTPatternSpec *pspec,
         frost_uint         string_length,
         const char  *string,
         const char  *string_reversed)
{
  frost_return_val_if_fail (pspec != NULL, frost_false);
  frost_return_val_if_fail (string != NULL, frost_false);

  if (string_length < pspec->min_length ||
      string_length > pspec->max_length)
    return frost_false;

  switch (pspec->match_type)
    {
      frost_bool dummy;
    case ICE_MATCH_ALL:
      return frost_pattern_ph_match (pspec->pattern, string, &dummy);
    case ICE_MATCH_ALL_TAIL:
      if (string_reversed)
    return frost_pattern_ph_match (pspec->pattern, string_reversed, &dummy);
      else
    {
          frost_bool result;
          char *tmp;
      tmp = frost_utf8_strreverse (string, string_length);
      result = frost_pattern_ph_match (pspec->pattern, tmp, &dummy);
      frost_free (tmp);
      return result;
    }
    case ICE_MATCH_HEAD:
      if (pspec->pattern_length == string_length)
    return strcmp (pspec->pattern, string) == 0;
      else if (pspec->pattern_length)
    return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
      else
    return frost_true;
    case ICE_MATCH_TAIL:
      if (pspec->pattern_length)
        return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0;
      else
    return frost_true;
    case ICE_MATCH_EXACT:
      if (pspec->pattern_length != string_length)
        return frost_false;
      else
        return strcmp (pspec->pattern, string) == 0;
    default:
      frost_return_val_if_fail (pspec->match_type < ICE_MATCH_LAST, frost_false);
      return frost_false;
    }
}

FROSTPatternSpec*
frost_pattern_spec_new (const char *pattern)
{
  FROSTPatternSpec *pspec;
  frost_bool seen_joker = frost_false, seen_wildcard = frost_false, more_wildcards = frost_false;
  frost_int hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1;
  frost_bool follows_wildcard = frost_false;
  frost_uint pending_jokers = 0;
  const char *s;
  char *d;
  frost_uint i;

  frost_return_val_if_fail (pattern != NULL, NULL);

  /* canonicalize pattern and collect necessary stats */
  pspec = frost_new (FROSTPatternSpec, 1);
  pspec->pattern_length = strlen (pattern);
  pspec->min_length = 0;
  pspec->max_length = 0;
  pspec->pattern = frost_new (char, pspec->pattern_length + 1);
  d = pspec->pattern;
  for (i = 0, s = pattern; *s != 0; s++)
    {
      switch (*s)
    {
    case '*':
      if (follows_wildcard) /* compress multiple wildcards */
        {
          pspec->pattern_length--;
          continue;
        }
      follows_wildcard = frost_true;
      if (hw_pos < 0)
        hw_pos = i;
      tw_pos = i;
      break;
    case '?':
      pending_jokers++;
      pspec->min_length++;
      pspec->max_length += 4; /* maximum UTF-8 character length */
      continue;
    default:
      for (; pending_jokers; pending_jokers--, i++) {
        *d++ = '?';
        if (hj_pos < 0)
         hj_pos = i;
        tj_pos = i;
      }
      follows_wildcard = frost_false;
      pspec->min_length++;
      pspec->max_length++;
      break;
    }
      *d++ = *s;
      i++;
    }
  for (; pending_jokers; pending_jokers--) {
    *d++ = '?';
    if (hj_pos < 0)
      hj_pos = i;
    tj_pos = i;
  }
  *d++ = 0;
  seen_joker = hj_pos >= 0;
  seen_wildcard = hw_pos >= 0;
  more_wildcards = seen_wildcard && hw_pos != tw_pos;
  if (seen_wildcard)
    pspec->max_length = FROST_MAXUINT;

  /* special case sole head/tail wildcard or exact matches */
  if (!seen_joker && !more_wildcards)
    {
      if (pspec->pattern[0] == '*')
    {
      pspec->match_type = ICE_MATCH_TAIL;
          memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length);
      pspec->pattern[pspec->pattern_length] = 0;
      return pspec;
    }
      if (pspec->pattern_length > 0 &&
      pspec->pattern[pspec->pattern_length - 1] == '*')
    {
      pspec->match_type = ICE_MATCH_HEAD;
      pspec->pattern[--pspec->pattern_length] = 0;
      return pspec;
    }
      if (!seen_wildcard)
    {
      pspec->match_type = ICE_MATCH_EXACT;
      return pspec;
    }
    }

  /* now just need to distinguish between head or tail match start */
  tw_pos = pspec->pattern_length - 1 - tw_pos;  /* last pos to tail distance */
  tj_pos = pspec->pattern_length - 1 - tj_pos;  /* last pos to tail distance */
  if (seen_wildcard)
    pspec->match_type = tw_pos > hw_pos ? ICE_MATCH_ALL_TAIL : ICE_MATCH_ALL;
  else /* seen_joker */
    pspec->match_type = tj_pos > hj_pos ? ICE_MATCH_ALL_TAIL : ICE_MATCH_ALL;
  if (pspec->match_type == ICE_MATCH_ALL_TAIL) {
    char *tmp = pspec->pattern;
    pspec->pattern = frost_utf8_strreverse (pspec->pattern, pspec->pattern_length);
    frost_free (tmp);
  }
  return pspec;
}

void
frost_pattern_spec_free (FROSTPatternSpec *pspec)
{
  frost_return_if_fail (pspec != NULL);

  frost_free (pspec->pattern);
  frost_free (pspec);
}

frost_bool
frost_pattern_spec_equal (FROSTPatternSpec *pspec1,
              FROSTPatternSpec *pspec2)
{
  frost_return_val_if_fail (pspec1 != NULL, frost_false);
  frost_return_val_if_fail (pspec2 != NULL, frost_false);

  return (pspec1->pattern_length == pspec2->pattern_length &&
      pspec1->match_type == pspec2->match_type &&
      strcmp (pspec1->pattern, pspec2->pattern) == 0);
}

frost_bool
frost_pattern_match_string (FROSTPatternSpec *pspec,
            const char  *string)
{
  frost_return_val_if_fail (pspec != NULL, frost_false);
  frost_return_val_if_fail (string != NULL, frost_false);

  return frost_pattern_match (pspec, strlen (string), string, NULL);
}

frost_bool
frost_pattern_match_simple (const char *pattern,
            const char *string)
{
  FROSTPatternSpec *pspec;
  frost_bool ergo;

  frost_return_val_if_fail (pattern != NULL, frost_false);
  frost_return_val_if_fail (string != NULL, frost_false);

  pspec = frost_pattern_spec_new (pattern);
  ergo = frost_pattern_match (pspec, strlen (string), string, NULL);
  frost_pattern_spec_free (pspec);

  return ergo;
}

