#include "access/gist.h"
#include "access/itup.h"
#include "access/stratnum.h"
#include "storage/bufpage.h"

Include dependency graph for trgm.h:

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

Data Structures
struct	TRGM

Macros
#define	LPADDING 2

#define	RPADDING 1

#define	IGNORECASE

#define	DIVUNION

#define	SimilarityStrategyNumber 1

#define	DistanceStrategyNumber 2

#define	LikeStrategyNumber 3

#define	ILikeStrategyNumber 4

#define	RegExpStrategyNumber 5

#define	RegExpICaseStrategyNumber 6

#define	WordSimilarityStrategyNumber 7

#define	WordDistanceStrategyNumber 8

#define	StrictWordSimilarityStrategyNumber 9

#define	StrictWordDistanceStrategyNumber 10

#define	EqualStrategyNumber 11

#define	CPTRGM(a, b)

#define	ISWORDCHR(c) (t_isalnum(c))

#define	ISPRINTABLECHAR(a) ( isascii( (unsigned char)(a) ) && (isalnum( (unsigned char)(a) ) \|\| (unsigned char)(a)==' ') )

#define	ISPRINTABLETRGM(t) ( ISPRINTABLECHAR( ((char)(t)) ) && ISPRINTABLECHAR( ((char)(t))+1 ) && ISPRINTABLECHAR( ((char*)(t))+2 ) )

#define	ISESCAPECHAR(x) ((x) == '\\') / Wildcard escape character */

#define	ISWILDCARDCHAR(x)

#define	TRGMHDRSIZE (VARHDRSZ + sizeof(uint8))

#define	SIGLEN_DEFAULT (sizeof(int) * 3)

#define	SIGLEN_MAX GISTMaxIndexKeySize

#define	BITBYTE 8

#define	SIGLENBIT(siglen) ((siglen) * BITBYTE - 1) /* see makesign */

#define	LOOPBYTE(siglen) for (i = 0; i < (siglen); i++)

#define	GETBYTE(x, i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )

#define	GETBITBYTE(x, i) ( (((char)(x)) >> (i)) & 0x01 )

#define	CLRBIT(x, i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )

#define	SETBIT(x, i) GETBYTE(x,i) \|= ( 0x01 << ( (i) % BITBYTE ) )

#define	GETBIT(x, i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )

#define	HASHVAL(val, siglen) (((unsigned int)(val)) % SIGLENBIT(siglen))

#define	HASH(sign, val, siglen) SETBIT((sign), HASHVAL(val, siglen))

#define	ARRKEY 0x01

#define	SIGNKEY 0x02

#define	ALLISTRUE 0x04

#define	ISARRKEY(x) ( ((TRGM*)x)->flag & ARRKEY )

#define	ISSIGNKEY(x) ( ((TRGM*)x)->flag & SIGNKEY )

#define	ISALLTRUE(x) ( ((TRGM*)x)->flag & ALLISTRUE )

#define	CALCGTSIZE(flag, len) ( TRGMHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(trgm)) : (((flag) & ALLISTRUE) ? 0 : (len)) ) )

#define	GETSIGN(x) ( (BITVECP)( (char*)x+TRGMHDRSIZE ) )

#define	GETARR(x) ( (trgm)( (char)x+TRGMHDRSIZE ) )

#define	ARRNELEM(x) ( ( VARSIZE(x) - TRGMHDRSIZE )/sizeof(trgm) )

#define	CALCSML(count, len1, len2) ((float4) (count)) / ((float4) ((len1) + (len2) - (count)))

Typedefs
typedef char	trgm[3]

typedef char *	BITVECP

typedef struct TrgmPackedGraph	TrgmPackedGraph

Functions
double	index_strategy_get_limit (StrategyNumber strategy)

uint32	trgm2int (trgm *ptr)

void	compact_trigram (trgm tptr, char str, int bytelen)

TRGM *	generate_trgm (char *str, int slen)

TRGM *	generate_wildcard_trgm (const char *str, int slen)

float4	cnt_sml (TRGM trg1, TRGM trg2, bool inexact)

bool	trgm_contained_by (TRGM trg1, TRGM trg2)

bool *	trgm_presence_map (TRGM query, TRGM key)

TRGM *	createTrgmNFA (text text_re, Oid collation, TrgmPackedGraph *graph, MemoryContext rcontext)

bool	trigramsMatchGraph (TrgmPackedGraph graph, bool check)

Variables
int(*	CMPTRGM )(const void a, const void b)

double	similarity_threshold

double	word_similarity_threshold

double	strict_word_similarity_threshold

Macro Definition Documentation

◆ ALLISTRUE

#define ALLISTRUE 0x04

Definition at line 89 of file trgm.h.

◆ ARRKEY

#define ARRKEY 0x01

Definition at line 87 of file trgm.h.

◆ ARRNELEM

#define ARRNELEM ( x ) ( ( VARSIZE(x) - TRGMHDRSIZE )/sizeof(trgm) )

Definition at line 98 of file trgm.h.

◆ BITBYTE

#define BITBYTE 8

Definition at line 69 of file trgm.h.

◆ CALCGTSIZE

#define CALCGTSIZE	(	flag,
		len
	)	( TRGMHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(trgm)) : (((flag) & ALLISTRUE) ? 0 : (len)) ) )

Definition at line 95 of file trgm.h.

◆ CALCSML

#define CALCSML	(	count,
		len1,
		len2
	)	((float4) (count)) / ((float4) ((len1) + (len2) - (count)))

Definition at line 107 of file trgm.h.

◆ CLRBIT

#define CLRBIT	(	x,
		i
	)	GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )

Definition at line 80 of file trgm.h.

◆ CPTRGM

#define CPTRGM	(	a,
		b
	)

Value:

    do {                \
    *(((char*)(a))+0) = *(((char*)(b))+0);  \
    *(((char*)(a))+1) = *(((char*)(b))+1);  \
    *(((char*)(a))+2) = *(((char*)(b))+2);  \
} while(0)

Definition at line 43 of file trgm.h.

                       {                \
    *(((char*)(a))+0) = *(((char*)(b))+0);  \
    *(((char*)(a))+1) = *(((char*)(b))+1);  \
    *(((char*)(a))+2) = *(((char*)(b))+2);  \
} while(0)

◆ DistanceStrategyNumber

#define DistanceStrategyNumber 2

Definition at line 30 of file trgm.h.

◆ DIVUNION

#define DIVUNION

Definition at line 26 of file trgm.h.

◆ EqualStrategyNumber

#define EqualStrategyNumber 11

Definition at line 39 of file trgm.h.

◆ GETARR

#define GETARR ( x ) ( (trgm*)( (char*)x+TRGMHDRSIZE ) )

Definition at line 97 of file trgm.h.

◆ GETBIT

#define GETBIT	(	x,
		i
	)	( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )

Definition at line 82 of file trgm.h.

◆ GETBITBYTE

#define GETBITBYTE	(	x,
		i
	)	( (((char)(x)) >> (i)) & 0x01 )

Definition at line 79 of file trgm.h.

◆ GETBYTE

#define GETBYTE	(	x,
		i
	)	( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )

Definition at line 78 of file trgm.h.

◆ GETSIGN

#define GETSIGN ( x ) ( (BITVECP)( (char*)x+TRGMHDRSIZE ) )

Definition at line 96 of file trgm.h.

◆ HASH

#define HASH	(	sign,
		val,
		siglen
	)	SETBIT((sign), HASHVAL(val, siglen))

Definition at line 85 of file trgm.h.

◆ HASHVAL

#define HASHVAL	(	val,
		siglen
	)	(((unsigned int)(val)) % SIGLENBIT(siglen))

Definition at line 84 of file trgm.h.

◆ IGNORECASE

#define IGNORECASE

Definition at line 25 of file trgm.h.

◆ ILikeStrategyNumber

#define ILikeStrategyNumber 4

Definition at line 32 of file trgm.h.

◆ ISALLTRUE

#define ISALLTRUE ( x ) ( ((TRGM*)x)->flag & ALLISTRUE )

Definition at line 93 of file trgm.h.

◆ ISARRKEY

#define ISARRKEY ( x ) ( ((TRGM*)x)->flag & ARRKEY )

Definition at line 91 of file trgm.h.

◆ ISESCAPECHAR

#define ISESCAPECHAR ( x ) (*(x) == '\\') /* Wildcard escape character */

Definition at line 54 of file trgm.h.

◆ ISPRINTABLECHAR

#define ISPRINTABLECHAR ( a ) ( isascii( *(unsigned char*)(a) ) && (isalnum( *(unsigned char*)(a) ) || *(unsigned char*)(a)==' ') )

Definition at line 51 of file trgm.h.

◆ ISPRINTABLETRGM

#define ISPRINTABLETRGM ( t ) ( ISPRINTABLECHAR( ((char*)(t)) ) && ISPRINTABLECHAR( ((char*)(t))+1 ) && ISPRINTABLECHAR( ((char*)(t))+2 ) )

Definition at line 52 of file trgm.h.

◆ ISSIGNKEY

#define ISSIGNKEY ( x ) ( ((TRGM*)x)->flag & SIGNKEY )

Definition at line 92 of file trgm.h.

◆ ISWILDCARDCHAR

#define ISWILDCARDCHAR ( x )

Value:

(*(x) == '_' || *(x) == '%') /* Wildcard

* meta-character */

x

int x

Definition isn.c:75

Definition at line 55 of file trgm.h.

◆ ISWORDCHR

#define ISWORDCHR ( c ) (t_isalnum(c))

Definition at line 50 of file trgm.h.

◆ LikeStrategyNumber

#define LikeStrategyNumber 3

Definition at line 31 of file trgm.h.

◆ LOOPBYTE

#define LOOPBYTE ( siglen ) for (i = 0; i < (siglen); i++)

Definition at line 75 of file trgm.h.

◆ LPADDING

#define LPADDING 2

Definition at line 16 of file trgm.h.

◆ RegExpICaseStrategyNumber

#define RegExpICaseStrategyNumber 6

Definition at line 34 of file trgm.h.

◆ RegExpStrategyNumber

#define RegExpStrategyNumber 5

Definition at line 33 of file trgm.h.

◆ RPADDING

#define RPADDING 1

Definition at line 17 of file trgm.h.

◆ SETBIT

#define SETBIT	(	x,
		i
	)	GETBYTE(x,i) \|= ( 0x01 << ( (i) % BITBYTE ) )

Definition at line 81 of file trgm.h.

◆ SIGLEN_DEFAULT

#define SIGLEN_DEFAULT (sizeof(int) * 3)

Definition at line 67 of file trgm.h.

◆ SIGLEN_MAX

#define SIGLEN_MAX GISTMaxIndexKeySize

Definition at line 68 of file trgm.h.

◆ SIGLENBIT

#define SIGLENBIT ( siglen ) ((siglen) * BITBYTE - 1) /* see makesign */

Definition at line 71 of file trgm.h.

◆ SIGNKEY

#define SIGNKEY 0x02

Definition at line 88 of file trgm.h.

◆ SimilarityStrategyNumber

#define SimilarityStrategyNumber 1

Definition at line 29 of file trgm.h.

◆ StrictWordDistanceStrategyNumber

#define StrictWordDistanceStrategyNumber 10

Definition at line 38 of file trgm.h.

◆ StrictWordSimilarityStrategyNumber

#define StrictWordSimilarityStrategyNumber 9

Definition at line 37 of file trgm.h.

◆ TRGMHDRSIZE

#define TRGMHDRSIZE (VARHDRSZ + sizeof(uint8))

Definition at line 64 of file trgm.h.

◆ WordDistanceStrategyNumber

#define WordDistanceStrategyNumber 8

Definition at line 36 of file trgm.h.

◆ WordSimilarityStrategyNumber

#define WordSimilarityStrategyNumber 7

Definition at line 35 of file trgm.h.

Typedef Documentation

◆ BITVECP

typedef char* BITVECP

Definition at line 73 of file trgm.h.

◆ trgm

typedef char trgm[3]

Definition at line 41 of file trgm.h.

◆ TrgmPackedGraph

typedef struct TrgmPackedGraph TrgmPackedGraph

Definition at line 112 of file trgm.h.

Function Documentation

◆ cnt_sml()

float4 cnt_sml	(	TRGM *	trg1,
		TRGM *	trg2,
		bool	inexact
	)

extern

Definition at line 1041 of file trgm_op.c.

{
    trgm       *ptr1,
               *ptr2;
    int         count = 0;
    int         len1,
                len2;
 
    ptr1 = GETARR(trg1);
    ptr2 = GETARR(trg2);
 
    len1 = ARRNELEM(trg1);
    len2 = ARRNELEM(trg2);
 
    /* explicit test is needed to avoid 0/0 division when both lengths are 0 */
    if (len1 <= 0 || len2 <= 0)
        return (float4) 0.0;
 
    while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
    {
        int         res = CMPTRGM(ptr1, ptr2);
 
        if (res < 0)
            ptr1++;
        else if (res > 0)
            ptr2++;
        else
        {
            ptr1++;
            ptr2++;
            count++;
        }
    }
 
    /*
     * If inexact then len2 is equal to count, because we don't know actual
     * length of second string in inexact search and we can assume that count
     * is a lower bound of len2.
     */

References ARRNELEM, CALCSML, CMPTRGM, fb(), and GETARR.

Referenced by gtrgm_consistent(), gtrgm_distance(), and similarity().

◆ compact_trigram()

void compact_trigram	(	trgm *	tptr,
		char *	str,
		int	bytelen
	)

extern

Definition at line 248 of file trgm_op.c.

{
    if (bytelen == 3)
    {
        CPTRGM(tptr, str);
    }
    else
    {
        pg_crc32    crc;
 
        INIT_LEGACY_CRC32(crc);
        COMP_LEGACY_CRC32(crc, str, bytelen);
        FIN_LEGACY_CRC32(crc);
 
        /*
         * use only 3 upper bytes from crc, hope, it's good enough hashing
         */
        CPTRGM(tptr, &crc);

References COMP_LEGACY_CRC32, CPTRGM, crc, fb(), FIN_LEGACY_CRC32, INIT_LEGACY_CRC32, and str.

Referenced by fillTrgm(), and make_trigrams().

◆ createTrgmNFA()

TRGM * createTrgmNFA	(	text *	text_re,
		Oid	collation,
		TrgmPackedGraph **	graph,
		MemoryContext	rcontext
	)

extern

Definition at line 524 of file trgm_regexp.c.

{
    TRGM       *trg;
    regex_t     regex;
    MemoryContext tmpcontext;
    MemoryContext oldcontext;
 
    /*
     * This processing generates a great deal of cruft, which we'd like to
     * clean up before returning (since this function may be called in a
     * query-lifespan memory context).  Make a temp context we can work in so
     * that cleanup is easy.
     */
    tmpcontext = AllocSetContextCreate(CurrentMemoryContext,
                                       "createTrgmNFA temporary context",
                                       ALLOCSET_DEFAULT_SIZES);
    oldcontext = MemoryContextSwitchTo(tmpcontext);
 
    /*
     * Stage 1: Compile the regexp into a NFA, using the regexp library.
     */
#ifdef IGNORECASE
    RE_compile(&regex, text_re,
               REG_ADVANCED | REG_NOSUB | REG_ICASE, collation);
#else
    RE_compile(&regex, text_re,
               REG_ADVANCED | REG_NOSUB, collation);
#endif
 
    trg = createTrgmNFAInternal(&regex, graph, rcontext);
 
    /* Clean up all the cruft we created (including regex) */
    MemoryContextSwitchTo(oldcontext);
    MemoryContextDelete(tmpcontext);
 
    return trg;
}

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, createTrgmNFAInternal(), CurrentMemoryContext, fb(), MemoryContextDelete(), MemoryContextSwitchTo(), RE_compile(), REG_ADVANCED, REG_ICASE, REG_NOSUB, and regex_t.

Referenced by gin_extract_query_trgm(), and gtrgm_consistent().

◆ generate_trgm()

TRGM * generate_trgm	(	char *	str,
		int	slen
	)

extern

Definition at line 406 of file trgm_op.c.

{
    TRGM       *trg;
    int         len;
 
    protect_out_of_mem(slen);
 
    trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) * 3);
    trg->flag = ARRKEY;
 
    len = generate_trgm_only(GETARR(trg), str, slen, NULL);
    SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
 
    if (len == 0)
        return trg;
 
    /*
     * Make trigrams unique.
     */
    if (len > 1)
    {
        qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
        len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
    }
 
    SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
 

References ARRKEY, CALCGTSIZE, comp_trgm(), fb(), TRGM::flag, generate_trgm_only(), GETARR, len, palloc(), protect_out_of_mem(), qsort, qunique(), SET_VARSIZE(), str, and TRGMHDRSIZE.

Referenced by gin_extract_query_trgm(), gin_extract_value_trgm(), gtrgm_compress(), gtrgm_consistent(), gtrgm_distance(), show_trgm(), and similarity().

◆ generate_wildcard_trgm()

TRGM * generate_wildcard_trgm	(	const char *	str,
		int	slen
	)

extern

Definition at line 916 of file trgm_op.c.

{
    TRGM       *trg;
    char       *buf,
               *buf2;
    trgm       *tptr;
    int         len,
                charlen,
                bytelen;
    const char *eword;
 
    protect_out_of_mem(slen);
 
    trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) * 3);
    trg->flag = ARRKEY;
    SET_VARSIZE(trg, TRGMHDRSIZE);
 
    if (slen + LPADDING + RPADDING < 3 || slen == 0)
        return trg;
 
    tptr = GETARR(trg);
 
    /* Allocate a buffer for blank-padded, but not yet case-folded, words */
    buf = palloc_array(char, slen + 4);
 
    /*
     * Extract trigrams from each substring extracted by get_wildcard_part.
     */
    eword = str;
    while ((eword = get_wildcard_part(eword, slen - (eword - str),
                                      buf, &bytelen, &charlen)) != NULL)
    {
#ifdef IGNORECASE
        buf2 = str_tolower(buf, bytelen, DEFAULT_COLLATION_OID);
        bytelen = strlen(buf2);
#else
        buf2 = buf;
#endif
 
        /*
         * count trigrams
         */
        tptr = make_trigrams(tptr, buf2, bytelen, charlen);
 
#ifdef IGNORECASE
        pfree(buf2);
#endif
    }
 
    pfree(buf);
 
    if ((len = tptr - GETARR(trg)) == 0)
        return trg;
 
    /*
     * Make trigrams unique.
     */
    if (len > 1)
    {
        qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
        len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
    }
 
    SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
 

References ARRKEY, buf, CALCGTSIZE, comp_trgm(), fb(), TRGM::flag, get_wildcard_part(), GETARR, len, LPADDING, make_trigrams(), palloc(), palloc_array, pfree(), protect_out_of_mem(), qsort, qunique(), RPADDING, SET_VARSIZE(), str, str_tolower(), and TRGMHDRSIZE.

Referenced by gin_extract_query_trgm(), and gtrgm_consistent().

◆ index_strategy_get_limit()

double index_strategy_get_limit ( StrategyNumber strategy )

extern

Definition at line 182 of file trgm_op.c.

{
    switch (strategy)
    {
        case SimilarityStrategyNumber:
            return similarity_threshold;
        case WordSimilarityStrategyNumber:
            return word_similarity_threshold;
        case StrictWordSimilarityStrategyNumber:
            return strict_word_similarity_threshold;
        default:
            elog(ERROR, "unrecognized strategy number: %d", strategy);
            break;
    }
 

References elog, ERROR, similarity_threshold, SimilarityStrategyNumber, strict_word_similarity_threshold, StrictWordSimilarityStrategyNumber, word_similarity_threshold, and WordSimilarityStrategyNumber.

Referenced by gin_trgm_consistent(), gin_trgm_triconsistent(), and gtrgm_consistent().

◆ trgm2int()

uint32 trgm2int ( trgm * ptr )

extern

Definition at line 985 of file trgm_op.c.

{
    uint32      val = 0;
 
    val |= *(((unsigned char *) ptr));
    val <<= 8;
    val |= *(((unsigned char *) ptr) + 1);
    val <<= 8;
    val |= *(((unsigned char *) ptr) + 2);
 

References val.

Referenced by gin_extract_query_trgm(), gin_extract_value_trgm(), and show_trgm().

◆ trgm_contained_by()

bool trgm_contained_by	(	TRGM *	trg1,
		TRGM *	trg2
	)

extern

Definition at line 1089 of file trgm_op.c.

{
    trgm       *ptr1,
               *ptr2;
    int         len1,
                len2;
 
    ptr1 = GETARR(trg1);
    ptr2 = GETARR(trg2);
 
    len1 = ARRNELEM(trg1);
    len2 = ARRNELEM(trg2);
 
    while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
    {
        int         res = CMPTRGM(ptr1, ptr2);
 
        if (res < 0)
            return false;
        else if (res > 0)
            ptr2++;
        else
        {
            ptr1++;
            ptr2++;
        }
    }
    if (ptr1 - GETARR(trg1) < len1)
        return false;
    else

References ARRNELEM, CMPTRGM, fb(), and GETARR.

Referenced by gtrgm_consistent().

◆ trgm_presence_map()

bool * trgm_presence_map	(	TRGM *	query,
		TRGM *	key
	)

extern

Definition at line 1128 of file trgm_op.c.

{
    bool       *result;
    trgm       *ptrq = GETARR(query),
               *ptrk = GETARR(key);
    int         lenq = ARRNELEM(query),
                lenk = ARRNELEM(key),
                i;
 
    result = palloc0_array(bool, lenq);
 
    /* for each query trigram, do a binary search in the key array */
    for (i = 0; i < lenq; i++)
    {
        int         lo = 0;
        int         hi = lenk;
 
        while (lo < hi)
        {
            int         mid = (lo + hi) / 2;
            int         res = CMPTRGM(ptrq, ptrk + mid);
 
            if (res < 0)
                hi = mid;
            else if (res > 0)
                lo = mid + 1;
            else
            {
                result[i] = true;
                break;
            }
        }
        ptrq++;
    }
 

References ARRNELEM, CMPTRGM, fb(), GETARR, i, and palloc0_array.

Referenced by gtrgm_consistent().

◆ trigramsMatchGraph()

bool trigramsMatchGraph	(	TrgmPackedGraph *	graph,
		bool *	check
	)

extern

Definition at line 628 of file trgm_regexp.c.

{
    int         i,
                j,
                k,
                queueIn,
                queueOut;
 
    /*
     * Reset temporary working areas.
     */
    memset(graph->colorTrigramsActive, 0,
           sizeof(bool) * graph->colorTrigramsCount);
    memset(graph->statesActive, 0, sizeof(bool) * graph->statesCount);
 
    /*
     * Check which color trigrams were matched.  A match for any simple
     * trigram associated with a color trigram counts as a match of the color
     * trigram.
     */
    j = 0;
    for (i = 0; i < graph->colorTrigramsCount; i++)
    {
        int         cnt = graph->colorTrigramGroups[i];
 
        for (k = j; k < j + cnt; k++)
        {
            if (check[k])
            {
                /*
                 * Found one matched trigram in the group. Can skip the rest
                 * of them and go to the next group.
                 */
                graph->colorTrigramsActive[i] = true;
                break;
            }
        }
        j = j + cnt;
    }
 
    /*
     * Initialize the statesQueue to hold just the initial state.  Note:
     * statesQueue has room for statesCount entries, which is certainly enough
     * since no state will be put in the queue more than once. The
     * statesActive array marks which states have been queued.
     */
    graph->statesActive[0] = true;
    graph->statesQueue[0] = 0;
    queueIn = 0;
    queueOut = 1;
 
    /* Process queued states as long as there are any. */
    while (queueIn < queueOut)
    {
        int         stateno = graph->statesQueue[queueIn++];
        TrgmPackedState *state = &graph->states[stateno];
        int         cnt = state->arcsCount;
 
        /* Loop over state's out-arcs */
        for (i = 0; i < cnt; i++)
        {
            TrgmPackedArc *arc = &state->arcs[i];
 
            /*
             * If corresponding color trigram is present then activate the
             * corresponding state.  We're done if that's the final state,
             * otherwise queue the state if it's not been queued already.
             */
            if (graph->colorTrigramsActive[arc->colorTrgm])
            {
                int         nextstate = arc->targetState;
 
                if (nextstate == 1)
                    return true;    /* success: final state is reachable */
 
                if (!graph->statesActive[nextstate])
                {
                    graph->statesActive[nextstate] = true;
                    graph->statesQueue[queueOut++] = nextstate;
                }
            }
        }
    }
 
    /* Queue is empty, so match fails. */
    return false;
}

References TrgmPackedGraph::colorTrigramGroups, TrgmPackedGraph::colorTrigramsActive, TrgmPackedGraph::colorTrigramsCount, fb(), i, j, TrgmPackedGraph::states, TrgmPackedGraph::statesActive, TrgmPackedGraph::statesCount, and TrgmPackedGraph::statesQueue.

Referenced by gin_trgm_consistent(), gin_trgm_triconsistent(), and gtrgm_consistent().

Variable Documentation

◆ CMPTRGM

int(* CMPTRGM) (const void a, const void b)	(	const void *	a,
		const void *	b
	)

extern

Definition at line 49 of file trgm_op.c.

Referenced by calc_word_similarity(), CMPTRGM_CHOOSE(), cnt_sml(), comp_ptrgm(), comp_trgm(), gtrgm_same(), trgm_contained_by(), and trgm_presence_map().

◆ similarity_threshold

double similarity_threshold

extern

Definition at line 27 of file trgm_op.c.

Referenced by _PG_init(), index_strategy_get_limit(), set_limit(), show_limit(), and similarity_op().

◆ strict_word_similarity_threshold

double strict_word_similarity_threshold

extern

Definition at line 29 of file trgm_op.c.

Referenced by _PG_init(), index_strategy_get_limit(), iterate_word_similarity(), strict_word_similarity_commutator_op(), and strict_word_similarity_op().

◆ word_similarity_threshold

double word_similarity_threshold

extern

Definition at line 28 of file trgm_op.c.

Referenced by _PG_init(), index_strategy_get_limit(), iterate_word_similarity(), word_similarity_commutator_op(), and word_similarity_op().

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ ALLISTRUE

◆ ARRKEY

◆ ARRNELEM

◆ BITBYTE

◆ CALCGTSIZE

◆ CALCSML

◆ CLRBIT

◆ CPTRGM

◆ DistanceStrategyNumber

◆ DIVUNION

◆ EqualStrategyNumber

◆ GETARR

◆ GETBIT

◆ GETBITBYTE

◆ GETBYTE

◆ GETSIGN

◆ HASH

◆ HASHVAL

◆ IGNORECASE

◆ ILikeStrategyNumber

◆ ISALLTRUE

◆ ISARRKEY

◆ ISESCAPECHAR

◆ ISPRINTABLECHAR

◆ ISPRINTABLETRGM

◆ ISSIGNKEY

◆ ISWILDCARDCHAR

◆ ISWORDCHR

◆ LikeStrategyNumber

◆ LOOPBYTE

◆ LPADDING

◆ RegExpICaseStrategyNumber

◆ RegExpStrategyNumber

◆ RPADDING

◆ SETBIT

◆ SIGLEN_DEFAULT

◆ SIGLEN_MAX

◆ SIGLENBIT

◆ SIGNKEY

◆ SimilarityStrategyNumber

◆ StrictWordDistanceStrategyNumber

◆ StrictWordSimilarityStrategyNumber

◆ TRGMHDRSIZE

◆ WordDistanceStrategyNumber

◆ WordSimilarityStrategyNumber

Typedef Documentation

◆ BITVECP

◆ trgm

◆ TrgmPackedGraph

Function Documentation

◆ cnt_sml()

◆ compact_trigram()

◆ createTrgmNFA()

◆ generate_trgm()

◆ generate_wildcard_trgm()

◆ index_strategy_get_limit()

◆ trgm2int()

◆ trgm_contained_by()

◆ trgm_presence_map()

◆ trigramsMatchGraph()

Variable Documentation

◆ CMPTRGM

◆ similarity_threshold

◆ strict_word_similarity_threshold

◆ word_similarity_threshold