varlena.h File Reference

#include "nodes/pg_list.h"
#include "utils/sortsupport.h"

Include dependency graph for varlena.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	ClosestMatchState

Typedefs
typedef struct ClosestMatchState	ClosestMatchState

Functions
int	varstr_cmp (const char *arg1, int len1, const char *arg2, int len2, Oid collid)
void	varstr_sortsupport (SortSupport ssup, Oid typid, Oid collid)
int	varstr_levenshtein (const char *source, int slen, const char *target, int tlen, int ins_c, int del_c, int sub_c, bool trusted)
int	varstr_levenshtein_less_equal (const char *source, int slen, const char *target, int tlen, int ins_c, int del_c, int sub_c, int max_d, bool trusted)
List *	textToQualifiedNameList (text *textval)
bool	SplitIdentifierString (char *rawstring, char separator, List **namelist)
bool	SplitDirectoriesString (char *rawstring, char separator, List **namelist)
bool	SplitGUCList (char *rawstring, char separator, List **namelist)
text *	replace_text_regexp (text *src_text, text *pattern_text, text *replace_text, int cflags, Oid collation, int search_start, int n)
void	initClosestMatch (ClosestMatchState *state, const char *source, int max_d)
void	updateClosestMatch (ClosestMatchState *state, const char *candidate)
const char *	getClosestMatch (ClosestMatchState *state)

Typedef Documentation

ClosestMatchState

typedef struct ClosestMatchState ClosestMatchState

Function Documentation

getClosestMatch()

const char* getClosestMatch

(

ClosestMatchState *

state

)

Definition at line 6168 of file varlena.c.

{
    Assert(state);
 
    return state->match;
}

References Assert().

Referenced by dblink_fdw_validator(), file_fdw_validator(), postgres_fdw_validator(), and postgresql_fdw_validator().

initClosestMatch()

void initClosestMatch	(	ClosestMatchState *	state,
		const char *	source,
		int	max_d
	)

Definition at line 6113 of file varlena.c.

{
    Assert(state);
    Assert(max_d >= 0);
 
    state->source = source;
    state->min_d = -1;
    state->max_d = max_d;
    state->match = NULL;
}

References Assert(), and source.

Referenced by dblink_fdw_validator(), file_fdw_validator(), postgres_fdw_validator(), and postgresql_fdw_validator().

replace_text_regexp()

text* replace_text_regexp	(	text *	src_text,
		text *	pattern_text,
		text *	replace_text,
		int	cflags,
		Oid	collation,
		int	search_start,
		int	n
	)

Definition at line 4203 of file varlena.c.

{
    text       *ret_text;
    regex_t    *re;
    int         src_text_len = VARSIZE_ANY_EXHDR(src_text);
    int         nmatches = 0;
    StringInfoData buf;
    regmatch_t  pmatch[10];     /* main match, plus \1 to \9 */
    int         nmatch = lengthof(pmatch);
    pg_wchar   *data;
    size_t      data_len;
    int         data_pos;
    char       *start_ptr;
    int         escape_status;
 
    initStringInfo(&buf);
 
    /* Convert data string to wide characters. */
    data = (pg_wchar *) palloc((src_text_len + 1) * sizeof(pg_wchar));
    data_len = pg_mb2wchar_with_len(VARDATA_ANY(src_text), data, src_text_len);
 
    /* Check whether replace_text has escapes, especially regexp submatches. */
    escape_status = check_replace_text_has_escape(replace_text);
 
    /* If no regexp submatches, we can use REG_NOSUB. */
    if (escape_status < 2)
    {
        cflags |= REG_NOSUB;
        /* Also tell pg_regexec we only want the whole-match location. */
        nmatch = 1;
    }
 
    /* Prepare the regexp. */
    re = RE_compile_and_cache(pattern_text, cflags, collation);
 
    /* start_ptr points to the data_pos'th character of src_text */
    start_ptr = (char *) VARDATA_ANY(src_text);
    data_pos = 0;
 
    while (search_start <= data_len)
    {
        int         regexec_result;
 
        CHECK_FOR_INTERRUPTS();
 
        regexec_result = pg_regexec(re,
                                    data,
                                    data_len,
                                    search_start,
                                    NULL,   /* no details */
                                    nmatch,
                                    pmatch,
                                    0);
 
        if (regexec_result == REG_NOMATCH)
            break;
 
        if (regexec_result != REG_OKAY)
        {
            char        errMsg[100];
 
            CHECK_FOR_INTERRUPTS();
            pg_regerror(regexec_result, re, errMsg, sizeof(errMsg));
            ereport(ERROR,
                    (errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
                     errmsg("regular expression failed: %s", errMsg)));
        }
 
        /*
         * Count matches, and decide whether to replace this match.
         */
        nmatches++;
        if (n > 0 && nmatches != n)
        {
            /*
             * No, so advance search_start, but not start_ptr/data_pos. (Thus,
             * we treat the matched text as if it weren't matched, and copy it
             * to the output later.)
             */
            search_start = pmatch[0].rm_eo;
            if (pmatch[0].rm_so == pmatch[0].rm_eo)
                search_start++;
            continue;
        }
 
        /*
         * Copy the text to the left of the match position.  Note we are given
         * character not byte indexes.
         */
        if (pmatch[0].rm_so - data_pos > 0)
        {
            int         chunk_len;
 
            chunk_len = charlen_to_bytelen(start_ptr,
                                           pmatch[0].rm_so - data_pos);
            appendBinaryStringInfo(&buf, start_ptr, chunk_len);
 
            /*
             * Advance start_ptr over that text, to avoid multiple rescans of
             * it if the replace_text contains multiple back-references.
             */
            start_ptr += chunk_len;
            data_pos = pmatch[0].rm_so;
        }
 
        /*
         * Copy the replace_text, processing escapes if any are present.
         */
        if (escape_status > 0)
            appendStringInfoRegexpSubstr(&buf, replace_text, pmatch,
                                         start_ptr, data_pos);
        else
            appendStringInfoText(&buf, replace_text);
 
        /* Advance start_ptr and data_pos over the matched text. */
        start_ptr += charlen_to_bytelen(start_ptr,
                                        pmatch[0].rm_eo - data_pos);
        data_pos = pmatch[0].rm_eo;
 
        /*
         * If we only want to replace one occurrence, we're done.
         */
        if (n > 0)
            break;
 
        /*
         * Advance search position.  Normally we start the next search at the
         * end of the previous match; but if the match was of zero length, we
         * have to advance by one character, or we'd just find the same match
         * again.
         */
        search_start = data_pos;
        if (pmatch[0].rm_so == pmatch[0].rm_eo)
            search_start++;
    }
 
    /*
     * Copy the text to the right of the last match.
     */
    if (data_pos < data_len)
    {
        int         chunk_len;
 
        chunk_len = ((char *) src_text + VARSIZE_ANY(src_text)) - start_ptr;
        appendBinaryStringInfo(&buf, start_ptr, chunk_len);
    }
 
    ret_text = cstring_to_text_with_len(buf.data, buf.len);
    pfree(buf.data);
    pfree(data);
 
    return ret_text;
}

References appendBinaryStringInfo(), appendStringInfoRegexpSubstr(), appendStringInfoText(), buf, charlen_to_bytelen(), CHECK_FOR_INTERRUPTS, check_replace_text_has_escape(), cstring_to_text_with_len(), data, ereport, errcode(), errmsg(), ERROR, initStringInfo(), lengthof, palloc(), pfree(), pg_mb2wchar_with_len(), pg_regerror(), pg_regexec(), RE_compile_and_cache(), REG_NOMATCH, REG_NOSUB, REG_OKAY, replace_text(), regmatch_t::rm_eo, regmatch_t::rm_so, VARDATA_ANY, VARSIZE_ANY, and VARSIZE_ANY_EXHDR.

Referenced by textregexreplace(), textregexreplace_extended(), and textregexreplace_noopt().

SplitDirectoriesString()

bool SplitDirectoriesString	(	char *	rawstring,
		char	separator,
		List **	namelist
	)

Definition at line 3581 of file varlena.c.

{
    char       *nextp = rawstring;
    bool        done = false;
 
    *namelist = NIL;
 
    while (scanner_isspace(*nextp))
        nextp++;                /* skip leading whitespace */
 
    if (*nextp == '\0')
        return true;            /* allow empty string */
 
    /* At the top of the loop, we are at start of a new directory. */
    do
    {
        char       *curname;
        char       *endp;
 
        if (*nextp == '"')
        {
            /* Quoted name --- collapse quote-quote pairs */
            curname = nextp + 1;
            for (;;)
            {
                endp = strchr(nextp + 1, '"');
                if (endp == NULL)
                    return false;   /* mismatched quotes */
                if (endp[1] != '"')
                    break;      /* found end of quoted name */
                /* Collapse adjacent quotes into one quote, and look again */
                memmove(endp, endp + 1, strlen(endp));
                nextp = endp;
            }
            /* endp now points at the terminating quote */
            nextp = endp + 1;
        }
        else
        {
            /* Unquoted name --- extends to separator or end of string */
            curname = endp = nextp;
            while (*nextp && *nextp != separator)
            {
                /* trailing whitespace should not be included in name */
                if (!scanner_isspace(*nextp))
                    endp = nextp + 1;
                nextp++;
            }
            if (curname == endp)
                return false;   /* empty unquoted name not allowed */
        }
 
        while (scanner_isspace(*nextp))
            nextp++;            /* skip trailing whitespace */
 
        if (*nextp == separator)
        {
            nextp++;
            while (scanner_isspace(*nextp))
                nextp++;        /* skip leading whitespace for next */
            /* we expect another name, so done remains false */
        }
        else if (*nextp == '\0')
            done = true;
        else
            return false;       /* invalid syntax */
 
        /* Now safe to overwrite separator with a null */
        *endp = '\0';
 
        /* Truncate path if it's overlength */
        if (strlen(curname) >= MAXPGPATH)
            curname[MAXPGPATH - 1] = '\0';
 
        /*
         * Finished isolating current name --- add it to list
         */
        curname = pstrdup(curname);
        canonicalize_path(curname);
        *namelist = lappend(*namelist, curname);
 
        /* Loop back if we didn't reach end of string */
    } while (!done);
 
    return true;
}

References canonicalize_path(), lappend(), MAXPGPATH, NIL, pstrdup(), and scanner_isspace().

Referenced by load_libraries(), and PostmasterMain().

SplitGUCList()

bool SplitGUCList	(	char *	rawstring,
		char	separator,
		List **	namelist
	)

Definition at line 3702 of file varlena.c.

{
    char       *nextp = rawstring;
    bool        done = false;
 
    *namelist = NIL;
 
    while (scanner_isspace(*nextp))
        nextp++;                /* skip leading whitespace */
 
    if (*nextp == '\0')
        return true;            /* allow empty string */
 
    /* At the top of the loop, we are at start of a new identifier. */
    do
    {
        char       *curname;
        char       *endp;
 
        if (*nextp == '"')
        {
            /* Quoted name --- collapse quote-quote pairs */
            curname = nextp + 1;
            for (;;)
            {
                endp = strchr(nextp + 1, '"');
                if (endp == NULL)
                    return false;   /* mismatched quotes */
                if (endp[1] != '"')
                    break;      /* found end of quoted name */
                /* Collapse adjacent quotes into one quote, and look again */
                memmove(endp, endp + 1, strlen(endp));
                nextp = endp;
            }
            /* endp now points at the terminating quote */
            nextp = endp + 1;
        }
        else
        {
            /* Unquoted name --- extends to separator or whitespace */
            curname = nextp;
            while (*nextp && *nextp != separator &&
                   !scanner_isspace(*nextp))
                nextp++;
            endp = nextp;
            if (curname == nextp)
                return false;   /* empty unquoted name not allowed */
        }
 
        while (scanner_isspace(*nextp))
            nextp++;            /* skip trailing whitespace */
 
        if (*nextp == separator)
        {
            nextp++;
            while (scanner_isspace(*nextp))
                nextp++;        /* skip leading whitespace for next */
            /* we expect another name, so done remains false */
        }
        else if (*nextp == '\0')
            done = true;
        else
            return false;       /* invalid syntax */
 
        /* Now safe to overwrite separator with a null */
        *endp = '\0';
 
        /*
         * Finished isolating current name --- add it to list
         */
        *namelist = lappend(*namelist, curname);
 
        /* Loop back if we didn't reach end of string */
    } while (!done);
 
    return true;
}

References lappend(), NIL, and scanner_isspace().

Referenced by dumpFunc(), parse_hba_auth_opt(), pg_get_functiondef(), and PostmasterMain().

SplitIdentifierString()

bool SplitIdentifierString	(	char *	rawstring,
		char	separator,
		List **	namelist
	)

Definition at line 3454 of file varlena.c.

{
    char       *nextp = rawstring;
    bool        done = false;
 
    *namelist = NIL;
 
    while (scanner_isspace(*nextp))
        nextp++;                /* skip leading whitespace */
 
    if (*nextp == '\0')
        return true;            /* allow empty string */
 
    /* At the top of the loop, we are at start of a new identifier. */
    do
    {
        char       *curname;
        char       *endp;
 
        if (*nextp == '"')
        {
            /* Quoted name --- collapse quote-quote pairs, no downcasing */
            curname = nextp + 1;
            for (;;)
            {
                endp = strchr(nextp + 1, '"');
                if (endp == NULL)
                    return false;   /* mismatched quotes */
                if (endp[1] != '"')
                    break;      /* found end of quoted name */
                /* Collapse adjacent quotes into one quote, and look again */
                memmove(endp, endp + 1, strlen(endp));
                nextp = endp;
            }
            /* endp now points at the terminating quote */
            nextp = endp + 1;
        }
        else
        {
            /* Unquoted name --- extends to separator or whitespace */
            char       *downname;
            int         len;
 
            curname = nextp;
            while (*nextp && *nextp != separator &&
                   !scanner_isspace(*nextp))
                nextp++;
            endp = nextp;
            if (curname == nextp)
                return false;   /* empty unquoted name not allowed */
 
            /*
             * Downcase the identifier, using same code as main lexer does.
             *
             * XXX because we want to overwrite the input in-place, we cannot
             * support a downcasing transformation that increases the string
             * length.  This is not a problem given the current implementation
             * of downcase_truncate_identifier, but we'll probably have to do
             * something about this someday.
             */
            len = endp - curname;
            downname = downcase_truncate_identifier(curname, len, false);
            Assert(strlen(downname) <= len);
            strncpy(curname, downname, len);    /* strncpy is required here */
            pfree(downname);
        }
 
        while (scanner_isspace(*nextp))
            nextp++;            /* skip trailing whitespace */
 
        if (*nextp == separator)
        {
            nextp++;
            while (scanner_isspace(*nextp))
                nextp++;        /* skip leading whitespace for next */
            /* we expect another name, so done remains false */
        }
        else if (*nextp == '\0')
            done = true;
        else
            return false;       /* invalid syntax */
 
        /* Now safe to overwrite separator with a null */
        *endp = '\0';
 
        /* Truncate name if it's overlength */
        truncate_identifier(curname, strlen(curname), false);
 
        /*
         * Finished isolating current name --- add it to list
         */
        *namelist = lappend(*namelist, curname);
 
        /* Loop back if we didn't reach end of string */
    } while (!done);
 
    return true;
}

References Assert(), downcase_truncate_identifier(), lappend(), len, NIL, pfree(), scanner_isspace(), and truncate_identifier().

Referenced by check_createrole_self_grant(), check_datestyle(), check_log_destination(), check_search_path(), check_temp_tablespaces(), check_wal_consistency_checking(), ExtractExtensionList(), parse_extension_control_file(), parse_output_parameters(), parse_publication_options(), plpgsql_extra_checks_check_hook(), PrepareTempTablespaces(), recomputeNamespacePath(), stringToQualifiedNameList(), and textToQualifiedNameList().

textToQualifiedNameList()

List* textToQualifiedNameList

(

text *

textval

)

Definition at line 3396 of file varlena.c.

{
    char       *rawname;
    List       *result = NIL;
    List       *namelist;
    ListCell   *l;
 
    /* Convert to C string (handles possible detoasting). */
    /* Note we rely on being able to modify rawname below. */
    rawname = text_to_cstring(textval);
 
    if (!SplitIdentifierString(rawname, '.', &namelist))
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_NAME),
                 errmsg("invalid name syntax")));
 
    if (namelist == NIL)
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_NAME),
                 errmsg("invalid name syntax")));
 
    foreach(l, namelist)
    {
        char       *curname = (char *) lfirst(l);
 
        result = lappend(result, makeString(pstrdup(curname)));
    }
 
    pfree(rawname);
    list_free(namelist);
 
    return result;
}

References ereport, errcode(), errmsg(), ERROR, lappend(), lfirst, list_free(), makeString(), NIL, pfree(), pstrdup(), SplitIdentifierString(), and text_to_cstring().

Referenced by bt_metap(), bt_multi_page_stats(), bt_page_items_internal(), bt_page_stats_internal(), convert_table_name(), currtid_byrelname(), get_raw_page_internal(), get_rel_from_relname(), nextval(), pg_get_serial_sequence(), pg_get_viewdef_name(), pg_get_viewdef_name_ext(), pg_relpages(), pg_relpages_v1_5(), pgrowlocks(), pgstatindex(), pgstatindex_v1_5(), pgstattuple(), pgstattuple_v1_5(), row_security_active_name(), text_regclass(), ts_parse_byname(), and ts_token_type_byname().

updateClosestMatch()

void updateClosestMatch	(	ClosestMatchState *	state,
		const char *	candidate
	)

Definition at line 6133 of file varlena.c.

{
    int         dist;
 
    Assert(state);
 
    if (state->source == NULL || state->source[0] == '\0' ||
        candidate == NULL || candidate[0] == '\0')
        return;
 
    /*
     * To avoid ERROR-ing, we check the lengths here instead of setting
     * 'trusted' to false in the call to varstr_levenshtein_less_equal().
     */
    if (strlen(state->source) > MAX_LEVENSHTEIN_STRLEN ||
        strlen(candidate) > MAX_LEVENSHTEIN_STRLEN)
        return;
 
    dist = varstr_levenshtein_less_equal(state->source, strlen(state->source),
                                         candidate, strlen(candidate), 1, 1, 1,
                                         state->max_d, true);
    if (dist <= state->max_d &&
        dist <= strlen(state->source) / 2 &&
        (state->min_d == -1 || dist < state->min_d))
    {
        state->min_d = dist;
        state->match = candidate;
    }
}

References Assert(), MAX_LEVENSHTEIN_STRLEN, and varstr_levenshtein_less_equal().

Referenced by dblink_fdw_validator(), file_fdw_validator(), postgres_fdw_validator(), and postgresql_fdw_validator().

varstr_cmp()

int varstr_cmp	(	const char *	arg1,
		int	len1,
		const char *	arg2,
		int	len2,
		Oid	collid
	)

Definition at line 1536 of file varlena.c.

{
    int         result;
 
    check_collation_set(collid);
 
    /*
     * Unfortunately, there is no strncoll(), so in the non-C locale case we
     * have to do some memory copying.  This turns out to be significantly
     * slower, so we optimize the case where LC_COLLATE is C.  We also try to
     * optimize relatively-short strings by avoiding palloc/pfree overhead.
     */
    if (lc_collate_is_c(collid))
    {
        result = memcmp(arg1, arg2, Min(len1, len2));
        if ((result == 0) && (len1 != len2))
            result = (len1 < len2) ? -1 : 1;
    }
    else
    {
        pg_locale_t mylocale;
 
        mylocale = pg_newlocale_from_collation(collid);
 
        /*
         * memcmp() can't tell us which of two unequal strings sorts first,
         * but it's a cheap way to tell if they're equal.  Testing shows that
         * memcmp() followed by strcoll() is only trivially slower than
         * strcoll() by itself, so we don't lose much if this doesn't work out
         * very often, and if it does - for example, because there are many
         * equal strings in the input - then we win big by avoiding expensive
         * collation-aware comparisons.
         */
        if (len1 == len2 && memcmp(arg1, arg2, len1) == 0)
            return 0;
 
        result = pg_strncoll(arg1, len1, arg2, len2, mylocale);
 
        /* Break tie if necessary. */
        if (result == 0 && pg_locale_deterministic(mylocale))
        {
            result = memcmp(arg1, arg2, Min(len1, len2));
            if ((result == 0) && (len1 != len2))
                result = (len1 < len2) ? -1 : 1;
        }
    }
 
    return result;
}

References check_collation_set(), collid, lc_collate_is_c(), Min, pg_locale_deterministic(), pg_newlocale_from_collation(), and pg_strncoll().

Referenced by bpchar_larger(), bpchar_smaller(), bpcharcmp(), bpchareq(), bpcharge(), bpchargt(), bpcharle(), bpcharlt(), bpcharne(), btnametextcmp(), bttextnamecmp(), citextcmp(), compareJsonbScalarValue(), gin_compare_jsonb(), make_greater_string(), namecmp(), nameeqtext(), namenetext(), spg_text_leaf_consistent(), text_cmp(), texteqname(), and textnename().

varstr_levenshtein()

int varstr_levenshtein	(	const char *	source,
		int	slen,
		const char *	target,
		int	tlen,
		int	ins_c,
		int	del_c,
		int	sub_c,
		bool	trusted
	)

Definition at line 73 of file levenshtein.c.

{
    int         m,
                n;
    int        *prev;
    int        *curr;
    int        *s_char_len = NULL;
    int         j;
    const char *y;
 
    /*
     * For varstr_levenshtein_less_equal, we have real variables called
     * start_column and stop_column; otherwise it's just short-hand for 0 and
     * m.
     */
#ifdef LEVENSHTEIN_LESS_EQUAL
    int         start_column,
                stop_column;
 
#undef START_COLUMN
#undef STOP_COLUMN
#define START_COLUMN start_column
#define STOP_COLUMN stop_column
#else
#undef START_COLUMN
#undef STOP_COLUMN
#define START_COLUMN 0
#define STOP_COLUMN m
#endif
 
    /* Convert string lengths (in bytes) to lengths in characters */
    m = pg_mbstrlen_with_len(source, slen);
    n = pg_mbstrlen_with_len(target, tlen);
 
    /*
     * We can transform an empty s into t with n insertions, or a non-empty t
     * into an empty s with m deletions.
     */
    if (!m)
        return n * ins_c;
    if (!n)
        return m * del_c;
 
    /*
     * For security concerns, restrict excessive CPU+RAM usage. (This
     * implementation uses O(m) memory and has O(mn) complexity.)  If
     * "trusted" is true, caller is responsible for not making excessive
     * requests, typically by using a small max_d along with strings that are
     * bounded, though not necessarily to MAX_LEVENSHTEIN_STRLEN exactly.
     */
    if (!trusted &&
        (m > MAX_LEVENSHTEIN_STRLEN ||
         n > MAX_LEVENSHTEIN_STRLEN))
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
                 errmsg("levenshtein argument exceeds maximum length of %d characters",
                        MAX_LEVENSHTEIN_STRLEN)));
 
#ifdef LEVENSHTEIN_LESS_EQUAL
    /* Initialize start and stop columns. */
    start_column = 0;
    stop_column = m + 1;
 
    /*
     * If max_d >= 0, determine whether the bound is impossibly tight.  If so,
     * return max_d + 1 immediately.  Otherwise, determine whether it's tight
     * enough to limit the computation we must perform.  If so, figure out
     * initial stop column.
     */
    if (max_d >= 0)
    {
        int         min_theo_d; /* Theoretical minimum distance. */
        int         max_theo_d; /* Theoretical maximum distance. */
        int         net_inserts = n - m;
 
        min_theo_d = net_inserts < 0 ?
            -net_inserts * del_c : net_inserts * ins_c;
        if (min_theo_d > max_d)
            return max_d + 1;
        if (ins_c + del_c < sub_c)
            sub_c = ins_c + del_c;
        max_theo_d = min_theo_d + sub_c * Min(m, n);
        if (max_d >= max_theo_d)
            max_d = -1;
        else if (ins_c + del_c > 0)
        {
            /*
             * Figure out how much of the first row of the notional matrix we
             * need to fill in.  If the string is growing, the theoretical
             * minimum distance already incorporates the cost of deleting the
             * number of characters necessary to make the two strings equal in
             * length.  Each additional deletion forces another insertion, so
             * the best-case total cost increases by ins_c + del_c. If the
             * string is shrinking, the minimum theoretical cost assumes no
             * excess deletions; that is, we're starting no further right than
             * column n - m.  If we do start further right, the best-case
             * total cost increases by ins_c + del_c for each move right.
             */
            int         slack_d = max_d - min_theo_d;
            int         best_column = net_inserts < 0 ? -net_inserts : 0;
 
            stop_column = best_column + (slack_d / (ins_c + del_c)) + 1;
            if (stop_column > m)
                stop_column = m + 1;
        }
    }
#endif
 
    /*
     * In order to avoid calling pg_mblen() repeatedly on each character in s,
     * we cache all the lengths before starting the main loop -- but if all
     * the characters in both strings are single byte, then we skip this and
     * use a fast-path in the main loop.  If only one string contains
     * multi-byte characters, we still build the array, so that the fast-path
     * needn't deal with the case where the array hasn't been initialized.
     */
    if (m != slen || n != tlen)
    {
        int         i;
        const char *cp = source;
 
        s_char_len = (int *) palloc((m + 1) * sizeof(int));
        for (i = 0; i < m; ++i)
        {
            s_char_len[i] = pg_mblen(cp);
            cp += s_char_len[i];
        }
        s_char_len[i] = 0;
    }
 
    /* One more cell for initialization column and row. */
    ++m;
    ++n;
 
    /* Previous and current rows of notional array. */
    prev = (int *) palloc(2 * m * sizeof(int));
    curr = prev + m;
 
    /*
     * To transform the first i characters of s into the first 0 characters of
     * t, we must perform i deletions.
     */
    for (int i = START_COLUMN; i < STOP_COLUMN; i++)
        prev[i] = i * del_c;
 
    /* Loop through rows of the notional array */
    for (y = target, j = 1; j < n; j++)
    {
        int        *temp;
        const char *x = source;
        int         y_char_len = n != tlen + 1 ? pg_mblen(y) : 1;
        int         i;
 
#ifdef LEVENSHTEIN_LESS_EQUAL
 
        /*
         * In the best case, values percolate down the diagonal unchanged, so
         * we must increment stop_column unless it's already on the right end
         * of the array.  The inner loop will read prev[stop_column], so we
         * have to initialize it even though it shouldn't affect the result.
         */
        if (stop_column < m)
        {
            prev[stop_column] = max_d + 1;
            ++stop_column;
        }
 
        /*
         * The main loop fills in curr, but curr[0] needs a special case: to
         * transform the first 0 characters of s into the first j characters
         * of t, we must perform j insertions.  However, if start_column > 0,
         * this special case does not apply.
         */
        if (start_column == 0)
        {
            curr[0] = j * ins_c;
            i = 1;
        }
        else
            i = start_column;
#else
        curr[0] = j * ins_c;
        i = 1;
#endif
 
        /*
         * This inner loop is critical to performance, so we include a
         * fast-path to handle the (fairly common) case where no multibyte
         * characters are in the mix.  The fast-path is entitled to assume
         * that if s_char_len is not initialized then BOTH strings contain
         * only single-byte characters.
         */
        if (s_char_len != NULL)
        {
            for (; i < STOP_COLUMN; i++)
            {
                int         ins;
                int         del;
                int         sub;
                int         x_char_len = s_char_len[i - 1];
 
                /*
                 * Calculate costs for insertion, deletion, and substitution.
                 *
                 * When calculating cost for substitution, we compare the last
                 * character of each possibly-multibyte character first,
                 * because that's enough to rule out most mis-matches.  If we
                 * get past that test, then we compare the lengths and the
                 * remaining bytes.
                 */
                ins = prev[i] + ins_c;
                del = curr[i - 1] + del_c;
                if (x[x_char_len - 1] == y[y_char_len - 1]
                    && x_char_len == y_char_len &&
                    (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
                    sub = prev[i - 1];
                else
                    sub = prev[i - 1] + sub_c;
 
                /* Take the one with minimum cost. */
                curr[i] = Min(ins, del);
                curr[i] = Min(curr[i], sub);
 
                /* Point to next character. */
                x += x_char_len;
            }
        }
        else
        {
            for (; i < STOP_COLUMN; i++)
            {
                int         ins;
                int         del;
                int         sub;
 
                /* Calculate costs for insertion, deletion, and substitution. */
                ins = prev[i] + ins_c;
                del = curr[i - 1] + del_c;
                sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
 
                /* Take the one with minimum cost. */
                curr[i] = Min(ins, del);
                curr[i] = Min(curr[i], sub);
 
                /* Point to next character. */
                x++;
            }
        }
 
        /* Swap current row with previous row. */
        temp = curr;
        curr = prev;
        prev = temp;
 
        /* Point to next character. */
        y += y_char_len;
 
#ifdef LEVENSHTEIN_LESS_EQUAL
 
        /*
         * This chunk of code represents a significant performance hit if used
         * in the case where there is no max_d bound.  This is probably not
         * because the max_d >= 0 test itself is expensive, but rather because
         * the possibility of needing to execute this code prevents tight
         * optimization of the loop as a whole.
         */
        if (max_d >= 0)
        {
            /*
             * The "zero point" is the column of the current row where the
             * remaining portions of the strings are of equal length.  There
             * are (n - 1) characters in the target string, of which j have
             * been transformed.  There are (m - 1) characters in the source
             * string, so we want to find the value for zp where (n - 1) - j =
             * (m - 1) - zp.
             */
            int         zp = j - (n - m);
 
            /* Check whether the stop column can slide left. */
            while (stop_column > 0)
            {
                int         ii = stop_column - 1;
                int         net_inserts = ii - zp;
 
                if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c :
                                -net_inserts * del_c) <= max_d)
                    break;
                stop_column--;
            }
 
            /* Check whether the start column can slide right. */
            while (start_column < stop_column)
            {
                int         net_inserts = start_column - zp;
 
                if (prev[start_column] +
                    (net_inserts > 0 ? net_inserts * ins_c :
                     -net_inserts * del_c) <= max_d)
                    break;
 
                /*
                 * We'll never again update these values, so we must make sure
                 * there's nothing here that could confuse any future
                 * iteration of the outer loop.
                 */
                prev[start_column] = max_d + 1;
                curr[start_column] = max_d + 1;
                if (start_column != 0)
                    source += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1;
                start_column++;
            }
 
            /* If they cross, we're going to exceed the bound. */
            if (start_column >= stop_column)
                return max_d + 1;
        }
#endif
    }
 
    /*
     * Because the final value was swapped from the previous row to the
     * current row, that's where we'll find it.
     */
    return prev[m - 1];
}

References ereport, errcode(), errmsg(), ERROR, i, j, MAX_LEVENSHTEIN_STRLEN, Min, palloc(), pg_mblen(), pg_mbstrlen_with_len(), rest_of_char_same(), source, START_COLUMN, STOP_COLUMN, x, and y.

Referenced by levenshtein(), and levenshtein_with_costs().

varstr_levenshtein_less_equal()

int varstr_levenshtein_less_equal	(	const char *	source,
		int	slen,
		const char *	target,
		int	tlen,
		int	ins_c,
		int	del_c,
		int	sub_c,
		int	max_d,
		bool	trusted
	)

Referenced by levenshtein_less_equal(), levenshtein_less_equal_with_costs(), searchRangeTableForCol(), updateClosestMatch(), and updateFuzzyAttrMatchState().

varstr_sortsupport()

void varstr_sortsupport	(	SortSupport	ssup,
		Oid	typid,
		Oid	collid
	)

Definition at line 1870 of file varlena.c.

{
    bool        abbreviate = ssup->abbreviate;
    bool        collate_c = false;
    VarStringSortSupport *sss;
    pg_locale_t locale = 0;
 
    check_collation_set(collid);
 
    /*
     * If possible, set ssup->comparator to a function which can be used to
     * directly compare two datums.  If we can do this, we'll avoid the
     * overhead of a trip through the fmgr layer for every comparison, which
     * can be substantial.
     *
     * Most typically, we'll set the comparator to varlenafastcmp_locale,
     * which uses strcoll() to perform comparisons.  We use that for the
     * BpChar case too, but type NAME uses namefastcmp_locale. However, if
     * LC_COLLATE = C, we can make things quite a bit faster with
     * varstrfastcmp_c, bpcharfastcmp_c, or namefastcmp_c, all of which use
     * memcmp() rather than strcoll().
     */
    if (lc_collate_is_c(collid))
    {
        if (typid == BPCHAROID)
            ssup->comparator = bpcharfastcmp_c;
        else if (typid == NAMEOID)
        {
            ssup->comparator = namefastcmp_c;
            /* Not supporting abbreviation with type NAME, for now */
            abbreviate = false;
        }
        else
            ssup->comparator = varstrfastcmp_c;
 
        collate_c = true;
    }
    else
    {
        /*
         * We need a collation-sensitive comparison.  To make things faster,
         * we'll figure out the collation based on the locale id and cache the
         * result.
         */
        locale = pg_newlocale_from_collation(collid);
 
        /*
         * We use varlenafastcmp_locale except for type NAME.
         */
        if (typid == NAMEOID)
        {
            ssup->comparator = namefastcmp_locale;
            /* Not supporting abbreviation with type NAME, for now */
            abbreviate = false;
        }
        else
            ssup->comparator = varlenafastcmp_locale;
    }
 
    /*
     * Unfortunately, it seems that abbreviation for non-C collations is
     * broken on many common platforms; see pg_strxfrm_enabled().
     *
     * Even apart from the risk of broken locales, it's possible that there
     * are platforms where the use of abbreviated keys should be disabled at
     * compile time.  Having only 4 byte datums could make worst-case
     * performance drastically more likely, for example.  Moreover, macOS's
     * strxfrm() implementation is known to not effectively concentrate a
     * significant amount of entropy from the original string in earlier
     * transformed blobs.  It's possible that other supported platforms are
     * similarly encumbered.  So, if we ever get past disabling this
     * categorically, we may still want or need to disable it for particular
     * platforms.
     */
    if (!collate_c && !pg_strxfrm_enabled(locale))
        abbreviate = false;
 
    /*
     * If we're using abbreviated keys, or if we're using a locale-aware
     * comparison, we need to initialize a VarStringSortSupport object. Both
     * cases will make use of the temporary buffers we initialize here for
     * scratch space (and to detect requirement for BpChar semantics from
     * caller), and the abbreviation case requires additional state.
     */
    if (abbreviate || !collate_c)
    {
        sss = palloc(sizeof(VarStringSortSupport));
        sss->buf1 = palloc(TEXTBUFLEN);
        sss->buflen1 = TEXTBUFLEN;
        sss->buf2 = palloc(TEXTBUFLEN);
        sss->buflen2 = TEXTBUFLEN;
        /* Start with invalid values */
        sss->last_len1 = -1;
        sss->last_len2 = -1;
        /* Initialize */
        sss->last_returned = 0;
        sss->locale = locale;
 
        /*
         * To avoid somehow confusing a strxfrm() blob and an original string,
         * constantly keep track of the variety of data that buf1 and buf2
         * currently contain.
         *
         * Comparisons may be interleaved with conversion calls.  Frequently,
         * conversions and comparisons are batched into two distinct phases,
         * but the correctness of caching cannot hinge upon this.  For
         * comparison caching, buffer state is only trusted if cache_blob is
         * found set to false, whereas strxfrm() caching only trusts the state
         * when cache_blob is found set to true.
         *
         * Arbitrarily initialize cache_blob to true.
         */
        sss->cache_blob = true;
        sss->collate_c = collate_c;
        sss->typid = typid;
        ssup->ssup_extra = sss;
 
        /*
         * If possible, plan to use the abbreviated keys optimization.  The
         * core code may switch back to authoritative comparator should
         * abbreviation be aborted.
         */
        if (abbreviate)
        {
            sss->prop_card = 0.20;
            initHyperLogLog(&sss->abbr_card, 10);
            initHyperLogLog(&sss->full_card, 10);
            ssup->abbrev_full_comparator = ssup->comparator;
            ssup->comparator = ssup_datum_unsigned_cmp;
            ssup->abbrev_converter = varstr_abbrev_convert;
            ssup->abbrev_abort = varstr_abbrev_abort;
        }
    }
}

References VarStringSortSupport::abbr_card, SortSupportData::abbrev_abort, SortSupportData::abbrev_converter, SortSupportData::abbrev_full_comparator, SortSupportData::abbreviate, bpcharfastcmp_c(), VarStringSortSupport::buf1, VarStringSortSupport::buf2, VarStringSortSupport::buflen1, VarStringSortSupport::buflen2, VarStringSortSupport::cache_blob, check_collation_set(), VarStringSortSupport::collate_c, collid, SortSupportData::comparator, VarStringSortSupport::full_card, initHyperLogLog(), VarStringSortSupport::last_len1, VarStringSortSupport::last_len2, VarStringSortSupport::last_returned, lc_collate_is_c(), VarStringSortSupport::locale, locale, namefastcmp_c(), namefastcmp_locale(), palloc(), pg_newlocale_from_collation(), pg_strxfrm_enabled(), VarStringSortSupport::prop_card, ssup_datum_unsigned_cmp(), SortSupportData::ssup_extra, TEXTBUFLEN, VarStringSortSupport::typid, varlenafastcmp_locale(), varstr_abbrev_abort(), varstr_abbrev_convert(), and varstrfastcmp_c().

Referenced by bpchar_sortsupport(), btbpchar_pattern_sortsupport(), btnamesortsupport(), bttext_pattern_sortsupport(), bttextsortsupport(), and bytea_sortsupport().