PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
trgm.h File Reference
#include "access/gist.h"
#include "access/itup.h"
#include "storage/bufpage.h"
Include dependency graph for trgm.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  TRGM
 

Macros

#define LPADDING   2
 
#define RPADDING   1
 
#define KEEPONLYALNUM
 
#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 CMPCHAR(a, b)   ( ((a)==(b)) ? 0 : ( ((a)<(b)) ? -1 : 1 ) )
 
#define CMPPCHAR(a, b, i)   CMPCHAR( *(((const char*)(a))+i), *(((const char*)(b))+i) )
 
#define CMPTRGM(a, b)   ( CMPPCHAR(a,b,0) ? CMPPCHAR(a,b,0) : ( CMPPCHAR(a,b,1) ? CMPPCHAR(a,b,1) : CMPPCHAR(a,b,2) ) )
 
#define CPTRGM(a, b)
 
#define ISWORDCHR(c)   (t_isalpha(c) || t_isdigit(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 BITBYTE   8
 
#define SIGLENINT   3 /* >122 => key will toast, so very slow!!! */
 
#define SIGLEN   ( sizeof(int)*SIGLENINT )
 
#define SIGLENBIT   (SIGLEN*BITBYTE - 1) /* see makesign */
 
#define LOOPBYTE   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)   (((unsigned int)(val)) % SIGLENBIT)
 
#define HASH(sign, val)   SETBIT((sign), HASHVAL(val))
 
#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 : SIGLEN) ) )
 
#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 BITVEC [SIGLEN]
 
typedef char * BITVECP
 
typedef struct TrgmPackedGraph TrgmPackedGraph
 

Functions

uint32 trgm2int (trgm *ptr)
 
void compact_trigram (trgm *tptr, char *str, int bytelen)
 
TRGMgenerate_trgm (char *str, int slen)
 
TRGMgenerate_wildcard_trgm (const char *str, int slen)
 
float4 cnt_sml (TRGM *trg1, TRGM *trg2, bool inexact)
 
bool trgm_contained_by (TRGM *trg1, TRGM *trg2)
 
booltrgm_presence_map (TRGM *query, TRGM *key)
 
TRGMcreateTrgmNFA (text *text_re, Oid collation, TrgmPackedGraph **graph, MemoryContext rcontext)
 
bool trigramsMatchGraph (TrgmPackedGraph *graph, bool *check)
 

Variables

double similarity_threshold
 
double word_similarity_threshold
 

Macro Definition Documentation

#define ALLISTRUE   0x04

Definition at line 96 of file trgm.h.

#define ARRKEY   0x01

Definition at line 94 of file trgm.h.

Referenced by expandColorTrigrams(), generate_trgm(), and generate_wildcard_trgm().

#define BITBYTE   8

Definition at line 73 of file trgm.h.

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

Definition at line 102 of file trgm.h.

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

Definition at line 114 of file trgm.h.

Referenced by cnt_sml(), and iterate_word_similarity().

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

Definition at line 87 of file trgm.h.

#define CMPCHAR (   a,
 
)    ( ((a)==(b)) ? 0 : ( ((a)<(b)) ? -1 : 1 ) )

Definition at line 40 of file trgm.h.

#define CMPPCHAR (   a,
  b,
  i 
)    CMPCHAR( *(((const char*)(a))+i), *(((const char*)(b))+i) )

Definition at line 41 of file trgm.h.

#define CMPTRGM (   a,
 
)    ( CMPPCHAR(a,b,0) ? CMPPCHAR(a,b,0) : ( CMPPCHAR(a,b,1) ? CMPPCHAR(a,b,1) : CMPPCHAR(a,b,2) ) )
#define CPTRGM (   a,
 
)
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 44 of file trgm.h.

Referenced by cnt_sml_sign_common(), compact_trigram(), gtrgm_consistent(), make_trigrams(), makesign(), show_trgm(), unionkey(), and unique_array().

#define DistanceStrategyNumber   2

Definition at line 30 of file trgm.h.

Referenced by gtrgm_distance().

#define DIVUNION

Definition at line 26 of file trgm.h.

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

Definition at line 89 of file trgm.h.

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

Definition at line 86 of file trgm.h.

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

Definition at line 85 of file trgm.h.

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

Definition at line 103 of file trgm.h.

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

Definition at line 92 of file trgm.h.

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

Definition at line 91 of file trgm.h.

#define IGNORECASE

Definition at line 25 of file trgm.h.

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

Definition at line 100 of file trgm.h.

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

Definition at line 98 of file trgm.h.

Referenced by fillcache(), and gtrgm_penalty().

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

Definition at line 59 of file trgm.h.

Referenced by get_wildcard_part().

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

Definition at line 52 of file trgm.h.

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

Definition at line 57 of file trgm.h.

Referenced by show_trgm().

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

Definition at line 99 of file trgm.h.

Referenced by gtrgm_compress(), gtrgm_same(), and unionkey().

#define ISWILDCARDCHAR (   x)
Value:
(*(x) == '_' || *(x) == '%') /* Wildcard
* meta-character */

Definition at line 60 of file trgm.h.

Referenced by get_wildcard_part().

#define ISWORDCHR (   c)    (t_isalpha(c) || t_isdigit(c))

Definition at line 51 of file trgm.h.

Referenced by find_word(), get_wildcard_part(), and getColorInfo().

#define KEEPONLYALNUM

Definition at line 17 of file trgm.h.

#define LikeStrategyNumber   3
#define LOOPBYTE   for(i=0;i<SIGLEN;i++)

Definition at line 82 of file trgm.h.

#define LPADDING   2

Definition at line 15 of file trgm.h.

Referenced by generate_trgm_only(), generate_wildcard_trgm(), and get_wildcard_part().

#define RegExpICaseStrategyNumber   6
#define RegExpStrategyNumber   5
#define RPADDING   1

Definition at line 16 of file trgm.h.

Referenced by generate_trgm_only(), generate_wildcard_trgm(), and get_wildcard_part().

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

Definition at line 88 of file trgm.h.

#define SIGLEN   ( sizeof(int)*SIGLENINT )

Definition at line 75 of file trgm.h.

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

Definition at line 77 of file trgm.h.

#define SIGLENINT   3 /* >122 => key will toast, so very slow!!! */

Definition at line 74 of file trgm.h.

#define SIGNKEY   0x02

Definition at line 95 of file trgm.h.

Referenced by gtrgm_compress(), gtrgm_picksplit(), and gtrgm_union().

#define SimilarityStrategyNumber   1
#define TRGMHDRSIZE   (VARHDRSZ + sizeof(uint8))

Definition at line 70 of file trgm.h.

Referenced by expandColorTrigrams(), generate_trgm(), and generate_wildcard_trgm().

#define WordDistanceStrategyNumber   8

Definition at line 36 of file trgm.h.

Referenced by gtrgm_distance().

#define WordSimilarityStrategyNumber   7

Typedef Documentation

typedef char BITVEC[SIGLEN]

Definition at line 79 of file trgm.h.

Definition at line 80 of file trgm.h.

typedef char trgm[3]

Definition at line 38 of file trgm.h.

Definition at line 119 of file trgm.h.

Function Documentation

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

Definition at line 928 of file trgm_op.c.

References ARRNELEM, CALCSML, CMPTRGM, and GETARR.

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

929 {
930  trgm *ptr1,
931  *ptr2;
932  int count = 0;
933  int len1,
934  len2;
935 
936  ptr1 = GETARR(trg1);
937  ptr2 = GETARR(trg2);
938 
939  len1 = ARRNELEM(trg1);
940  len2 = ARRNELEM(trg2);
941 
942  /* explicit test is needed to avoid 0/0 division when both lengths are 0 */
943  if (len1 <= 0 || len2 <= 0)
944  return (float4) 0.0;
945 
946  while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
947  {
948  int res = CMPTRGM(ptr1, ptr2);
949 
950  if (res < 0)
951  ptr1++;
952  else if (res > 0)
953  ptr2++;
954  else
955  {
956  ptr1++;
957  ptr2++;
958  count++;
959  }
960  }
961 
962  /*
963  * If inexact then len2 is equal to count, because we don't know actual
964  * length of second string in inexact search and we can assume that count
965  * is a lower bound of len2.
966  */
967  return CALCSML(count, len1, inexact ? count : len2);
968 }
#define CMPTRGM(a, b)
Definition: trgm.h:42
#define ARRNELEM(x)
Definition: trgm.h:105
#define GETARR(x)
Definition: trgm.h:104
float float4
Definition: c.h:380
char trgm[3]
Definition: trgm.h:38
#define CALCSML(count, len1, len2)
Definition: trgm.h:114
void compact_trigram ( trgm tptr,
char *  str,
int  bytelen 
)

Definition at line 166 of file trgm_op.c.

References COMP_LEGACY_CRC32, CPTRGM, FIN_LEGACY_CRC32, and INIT_LEGACY_CRC32.

Referenced by fillTrgm(), and make_trigrams().

167 {
168  if (bytelen == 3)
169  {
170  CPTRGM(tptr, str);
171  }
172  else
173  {
174  pg_crc32 crc;
175 
176  INIT_LEGACY_CRC32(crc);
177  COMP_LEGACY_CRC32(crc, str, bytelen);
178  FIN_LEGACY_CRC32(crc);
179 
180  /*
181  * use only 3 upper bytes from crc, hope, it's good enough hashing
182  */
183  CPTRGM(tptr, &crc);
184  }
185 }
#define INIT_LEGACY_CRC32(crc)
Definition: pg_crc.h:79
#define FIN_LEGACY_CRC32(crc)
Definition: pg_crc.h:80
#define COMP_LEGACY_CRC32(crc, data, len)
Definition: pg_crc.h:81
uint32 pg_crc32
Definition: pg_crc.h:37
#define CPTRGM(a, b)
Definition: trgm.h:44
TRGM* createTrgmNFA ( text text_re,
Oid  collation,
TrgmPackedGraph **  graph,
MemoryContext  rcontext 
)

Definition at line 523 of file trgm_regexp.c.

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate(), createTrgmNFAInternal(), CurrentMemoryContext, MemoryContextDelete(), MemoryContextSwitchTo(), PG_CATCH, PG_END_TRY, PG_RE_THROW, pg_regfree(), PG_TRY, RE_compile(), REG_ADVANCED, and REG_ICASE.

Referenced by gin_extract_query_trgm(), and gtrgm_consistent().

525 {
526  TRGM *trg;
527  regex_t regex;
528  MemoryContext tmpcontext;
529  MemoryContext oldcontext;
530 
531  /*
532  * This processing generates a great deal of cruft, which we'd like to
533  * clean up before returning (since this function may be called in a
534  * query-lifespan memory context). Make a temp context we can work in so
535  * that cleanup is easy.
536  */
538  "createTrgmNFA temporary context",
540  oldcontext = MemoryContextSwitchTo(tmpcontext);
541 
542  /*
543  * Stage 1: Compile the regexp into a NFA, using the regexp library.
544  */
545 #ifdef IGNORECASE
546  RE_compile(&regex, text_re, REG_ADVANCED | REG_ICASE, collation);
547 #else
548  RE_compile(&regex, text_re, REG_ADVANCED, collation);
549 #endif
550 
551  /*
552  * Since the regexp library allocates its internal data structures with
553  * malloc, we need to use a PG_TRY block to ensure that pg_regfree() gets
554  * done even if there's an error.
555  */
556  PG_TRY();
557  {
558  trg = createTrgmNFAInternal(&regex, graph, rcontext);
559  }
560  PG_CATCH();
561  {
562  pg_regfree(&regex);
563  PG_RE_THROW();
564  }
565  PG_END_TRY();
566 
567  pg_regfree(&regex);
568 
569  /* Clean up all the cruft we created */
570  MemoryContextSwitchTo(oldcontext);
571  MemoryContextDelete(tmpcontext);
572 
573  return trg;
574 }
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:200
static TRGM * createTrgmNFAInternal(regex_t *regex, TrgmPackedGraph **graph, MemoryContext rcontext)
Definition: trgm_regexp.c:580
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define REG_ICASE
Definition: regex.h:106
Definition: trgm.h:63
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:165
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define REG_ADVANCED
Definition: regex.h:103
MemoryContext AllocSetContextCreate(MemoryContext parent, const char *name, Size minContextSize, Size initBlockSize, Size maxBlockSize)
Definition: aset.c:322
#define PG_CATCH()
Definition: elog.h:293
static void RE_compile(regex_t *regex, text *text_re, int cflags, Oid collation)
Definition: trgm_regexp.c:734
#define PG_RE_THROW()
Definition: elog.h:314
#define PG_TRY()
Definition: elog.h:284
void pg_regfree(regex_t *re)
Definition: regfree.c:49
Definition: regex.h:55
#define PG_END_TRY()
Definition: elog.h:300
TRGM* generate_trgm ( char *  str,
int  slen 
)

Definition at line 321 of file trgm_op.c.

References ARRKEY, CALCGTSIZE, comp_trgm(), TRGM::flag, generate_trgm_only(), GETARR, palloc(), protect_out_of_mem(), qsort, SET_VARSIZE, TRGMHDRSIZE, and unique_array().

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

322 {
323  TRGM *trg;
324  int len;
325 
326  protect_out_of_mem(slen);
327 
328  trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) *3);
329  trg->flag = ARRKEY;
330 
331  len = generate_trgm_only(GETARR(trg), str, slen);
332  SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
333 
334  if (len == 0)
335  return trg;
336 
337  /*
338  * Make trigrams unique.
339  */
340  if (len > 1)
341  {
342  qsort((void *) GETARR(trg), len, sizeof(trgm), comp_trgm);
343  len = unique_array(GETARR(trg), len);
344  }
345 
346  SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
347 
348  return trg;
349 }
#define ARRKEY
Definition: trgm.h:94
static void protect_out_of_mem(int slen)
Definition: trgm_op.c:304
#define GETARR(x)
Definition: trgm.h:104
Definition: trgm.h:63
#define TRGMHDRSIZE
Definition: trgm.h:70
uint8 flag
Definition: trgm.h:66
char trgm[3]
Definition: trgm.h:38
#define CALCGTSIZE(flag)
Definition: hstore_gist.c:52
static int unique_array(trgm *a, int len)
Definition: trgm_op.c:115
void * palloc(Size size)
Definition: mcxt.c:849
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:328
#define qsort(a, b, c, d)
Definition: port.h:440
static int generate_trgm_only(trgm *trg, char *str, int slen)
Definition: trgm_op.c:242
static int comp_trgm(const void *a, const void *b)
Definition: trgm_op.c:109
TRGM* generate_wildcard_trgm ( const char *  str,
int  slen 
)

Definition at line 796 of file trgm_op.c.

References ARRKEY, buf, CALCGTSIZE, comp_trgm(), TRGM::flag, get_wildcard_part(), GETARR, lowerstr_with_len(), LPADDING, make_trigrams(), NULL, palloc(), pfree(), protect_out_of_mem(), qsort, RPADDING, SET_VARSIZE, TRGMHDRSIZE, and unique_array().

Referenced by gin_extract_query_trgm(), and gtrgm_consistent().

797 {
798  TRGM *trg;
799  char *buf,
800  *buf2;
801  trgm *tptr;
802  int len,
803  charlen,
804  bytelen;
805  const char *eword;
806 
807  protect_out_of_mem(slen);
808 
809  trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) *3);
810  trg->flag = ARRKEY;
811  SET_VARSIZE(trg, TRGMHDRSIZE);
812 
813  if (slen + LPADDING + RPADDING < 3 || slen == 0)
814  return trg;
815 
816  tptr = GETARR(trg);
817 
818  /* Allocate a buffer for blank-padded, but not yet case-folded, words */
819  buf = palloc(sizeof(char) * (slen + 4));
820 
821  /*
822  * Extract trigrams from each substring extracted by get_wildcard_part.
823  */
824  eword = str;
825  while ((eword = get_wildcard_part(eword, slen - (eword - str),
826  buf, &bytelen, &charlen)) != NULL)
827  {
828 #ifdef IGNORECASE
829  buf2 = lowerstr_with_len(buf, bytelen);
830  bytelen = strlen(buf2);
831 #else
832  buf2 = buf;
833 #endif
834 
835  /*
836  * count trigrams
837  */
838  tptr = make_trigrams(tptr, buf2, bytelen, charlen);
839 
840 #ifdef IGNORECASE
841  pfree(buf2);
842 #endif
843  }
844 
845  pfree(buf);
846 
847  if ((len = tptr - GETARR(trg)) == 0)
848  return trg;
849 
850  /*
851  * Make trigrams unique.
852  */
853  if (len > 1)
854  {
855  qsort((void *) GETARR(trg), len, sizeof(trgm), comp_trgm);
856  len = unique_array(GETARR(trg), len);
857  }
858 
859  SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, len));
860 
861  return trg;
862 }
char * lowerstr_with_len(const char *str, int len)
Definition: ts_locale.c:244
#define ARRKEY
Definition: trgm.h:94
static void protect_out_of_mem(int slen)
Definition: trgm_op.c:304
static trgm * make_trigrams(trgm *tptr, char *str, int bytelen, int charlen)
Definition: trgm_op.c:191
#define GETARR(x)
Definition: trgm.h:104
void pfree(void *pointer)
Definition: mcxt.c:950
Definition: trgm.h:63
static char * buf
Definition: pg_test_fsync.c:66
#define TRGMHDRSIZE
Definition: trgm.h:70
uint8 flag
Definition: trgm.h:66
char trgm[3]
Definition: trgm.h:38
#define CALCGTSIZE(flag)
Definition: hstore_gist.c:52
#define NULL
Definition: c.h:229
#define RPADDING
Definition: trgm.h:16
static int unique_array(trgm *a, int len)
Definition: trgm_op.c:115
void * palloc(Size size)
Definition: mcxt.c:849
#define LPADDING
Definition: trgm.h:15
static const char * get_wildcard_part(const char *str, int lenstr, char *buf, int *bytelen, int *charlen)
Definition: trgm_op.c:651
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:328
#define qsort(a, b, c, d)
Definition: port.h:440
static int comp_trgm(const void *a, const void *b)
Definition: trgm_op.c:109
uint32 trgm2int ( trgm ptr)

Definition at line 865 of file trgm_op.c.

References val.

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

866 {
867  uint32 val = 0;
868 
869  val |= *(((unsigned char *) ptr));
870  val <<= 8;
871  val |= *(((unsigned char *) ptr) + 1);
872  val <<= 8;
873  val |= *(((unsigned char *) ptr) + 2);
874 
875  return val;
876 }
unsigned int uint32
Definition: c.h:268
long val
Definition: informix.c:689
bool trgm_contained_by ( TRGM trg1,
TRGM trg2 
)

Definition at line 976 of file trgm_op.c.

References ARRNELEM, CMPTRGM, and GETARR.

Referenced by gtrgm_consistent().

977 {
978  trgm *ptr1,
979  *ptr2;
980  int len1,
981  len2;
982 
983  ptr1 = GETARR(trg1);
984  ptr2 = GETARR(trg2);
985 
986  len1 = ARRNELEM(trg1);
987  len2 = ARRNELEM(trg2);
988 
989  while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
990  {
991  int res = CMPTRGM(ptr1, ptr2);
992 
993  if (res < 0)
994  return false;
995  else if (res > 0)
996  ptr2++;
997  else
998  {
999  ptr1++;
1000  ptr2++;
1001  }
1002  }
1003  if (ptr1 - GETARR(trg1) < len1)
1004  return false;
1005  else
1006  return true;
1007 }
#define CMPTRGM(a, b)
Definition: trgm.h:42
#define ARRNELEM(x)
Definition: trgm.h:105
#define GETARR(x)
Definition: trgm.h:104
char trgm[3]
Definition: trgm.h:38
bool* trgm_presence_map ( TRGM query,
TRGM key 
)

Definition at line 1015 of file trgm_op.c.

References ARRNELEM, CMPTRGM, GETARR, i, palloc0(), and result.

Referenced by gtrgm_consistent().

1016 {
1017  bool *result;
1018  trgm *ptrq = GETARR(query),
1019  *ptrk = GETARR(key);
1020  int lenq = ARRNELEM(query),
1021  lenk = ARRNELEM(key),
1022  i;
1023 
1024  result = (bool *) palloc0(lenq * sizeof(bool));
1025 
1026  /* for each query trigram, do a binary search in the key array */
1027  for (i = 0; i < lenq; i++)
1028  {
1029  int lo = 0;
1030  int hi = lenk;
1031 
1032  while (lo < hi)
1033  {
1034  int mid = (lo + hi) / 2;
1035  int res = CMPTRGM(ptrq, ptrk + mid);
1036 
1037  if (res < 0)
1038  hi = mid;
1039  else if (res > 0)
1040  lo = mid + 1;
1041  else
1042  {
1043  result[i] = true;
1044  break;
1045  }
1046  }
1047  ptrq++;
1048  }
1049 
1050  return result;
1051 }
#define CMPTRGM(a, b)
Definition: trgm.h:42
return result
Definition: formatting.c:1632
#define ARRNELEM(x)
Definition: trgm.h:105
#define GETARR(x)
Definition: trgm.h:104
void * palloc0(Size size)
Definition: mcxt.c:878
char trgm[3]
Definition: trgm.h:38
int i
bool trigramsMatchGraph ( TrgmPackedGraph graph,
bool check 
)

Definition at line 641 of file trgm_regexp.c.

References TrgmPackedState::arcs, TrgmPackedState::arcsCount, TrgmPackedArc::colorTrgm, TrgmPackedGraph::colorTrigramGroups, TrgmPackedGraph::colorTrigramsActive, TrgmPackedGraph::colorTrigramsCount, i, TrgmPackedGraph::states, TrgmPackedGraph::statesActive, TrgmPackedGraph::statesCount, TrgmPackedGraph::statesQueue, and TrgmPackedArc::targetState.

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

642 {
643  int i,
644  j,
645  k,
646  queueIn,
647  queueOut;
648 
649  /*
650  * Reset temporary working areas.
651  */
652  memset(graph->colorTrigramsActive, 0,
653  sizeof(bool) * graph->colorTrigramsCount);
654  memset(graph->statesActive, 0, sizeof(bool) * graph->statesCount);
655 
656  /*
657  * Check which color trigrams were matched. A match for any simple
658  * trigram associated with a color trigram counts as a match of the color
659  * trigram.
660  */
661  j = 0;
662  for (i = 0; i < graph->colorTrigramsCount; i++)
663  {
664  int cnt = graph->colorTrigramGroups[i];
665 
666  for (k = j; k < j + cnt; k++)
667  {
668  if (check[k])
669  {
670  /*
671  * Found one matched trigram in the group. Can skip the rest
672  * of them and go to the next group.
673  */
674  graph->colorTrigramsActive[i] = true;
675  break;
676  }
677  }
678  j = j + cnt;
679  }
680 
681  /*
682  * Initialize the statesQueue to hold just the initial state. Note:
683  * statesQueue has room for statesCount entries, which is certainly enough
684  * since no state will be put in the queue more than once. The
685  * statesActive array marks which states have been queued.
686  */
687  graph->statesActive[0] = true;
688  graph->statesQueue[0] = 0;
689  queueIn = 0;
690  queueOut = 1;
691 
692  /* Process queued states as long as there are any. */
693  while (queueIn < queueOut)
694  {
695  int stateno = graph->statesQueue[queueIn++];
696  TrgmPackedState *state = &graph->states[stateno];
697  int cnt = state->arcsCount;
698 
699  /* Loop over state's out-arcs */
700  for (i = 0; i < cnt; i++)
701  {
702  TrgmPackedArc *arc = &state->arcs[i];
703 
704  /*
705  * If corresponding color trigram is present then activate the
706  * corresponding state. We're done if that's the final state,
707  * otherwise queue the state if it's not been queued already.
708  */
709  if (graph->colorTrigramsActive[arc->colorTrgm])
710  {
711  int nextstate = arc->targetState;
712 
713  if (nextstate == 1)
714  return true; /* success: final state is reachable */
715 
716  if (!graph->statesActive[nextstate])
717  {
718  graph->statesActive[nextstate] = true;
719  graph->statesQueue[queueOut++] = nextstate;
720  }
721  }
722  }
723  }
724 
725  /* Queue is empty, so match fails. */
726  return false;
727 }
bool * colorTrigramsActive
Definition: trgm_regexp.c:463
Definition: regguts.h:276
TrgmPackedState * states
Definition: trgm_regexp.c:460
TrgmPackedArc * arcs
Definition: trgm_regexp.c:437
bool * statesActive
Definition: trgm_regexp.c:464
Definition: regguts.h:298
int i
int * colorTrigramGroups
Definition: trgm_regexp.c:453

Variable Documentation

double similarity_threshold