LCOV - code coverage report
Current view: top level - contrib/pg_trgm - trgm_gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 342 430 79.5 %
Date: 2020-12-05 17:06:23 Functions: 28 32 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * contrib/pg_trgm/trgm_gist.c
       3             :  */
       4             : #include "postgres.h"
       5             : 
       6             : #include "access/reloptions.h"
       7             : #include "access/stratnum.h"
       8             : #include "fmgr.h"
       9             : #include "port/pg_bitutils.h"
      10             : #include "trgm.h"
      11             : 
      12             : /* gist_trgm_ops opclass options */
      13             : typedef struct
      14             : {
      15             :     int32       vl_len_;        /* varlena header (do not touch directly!) */
      16             :     int         siglen;         /* signature length in bytes */
      17             : } TrgmGistOptions;
      18             : 
      19             : #define GET_SIGLEN()            (PG_HAS_OPCLASS_OPTIONS() ? \
      20             :                                  ((TrgmGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
      21             :                                  SIGLEN_DEFAULT)
      22             : 
      23             : typedef struct
      24             : {
      25             :     /* most recent inputs to gtrgm_consistent */
      26             :     StrategyNumber strategy;
      27             :     text       *query;
      28             :     /* extracted trigrams for query */
      29             :     TRGM       *trigrams;
      30             :     /* if a regex operator, the extracted graph */
      31             :     TrgmPackedGraph *graph;
      32             : 
      33             :     /*
      34             :      * The "query" and "trigrams" are stored in the same palloc block as this
      35             :      * cache struct, at MAXALIGN'ed offsets.  The graph however isn't.
      36             :      */
      37             : } gtrgm_consistent_cache;
      38             : 
      39             : #define GETENTRY(vec,pos) ((TRGM *) DatumGetPointer((vec)->vector[(pos)].key))
      40             : 
      41             : 
      42           2 : PG_FUNCTION_INFO_V1(gtrgm_in);
      43           2 : PG_FUNCTION_INFO_V1(gtrgm_out);
      44           8 : PG_FUNCTION_INFO_V1(gtrgm_compress);
      45           8 : PG_FUNCTION_INFO_V1(gtrgm_decompress);
      46           8 : PG_FUNCTION_INFO_V1(gtrgm_consistent);
      47           8 : PG_FUNCTION_INFO_V1(gtrgm_distance);
      48           8 : PG_FUNCTION_INFO_V1(gtrgm_union);
      49           8 : PG_FUNCTION_INFO_V1(gtrgm_same);
      50           8 : PG_FUNCTION_INFO_V1(gtrgm_penalty);
      51           8 : PG_FUNCTION_INFO_V1(gtrgm_picksplit);
      52           8 : PG_FUNCTION_INFO_V1(gtrgm_options);
      53             : 
      54             : 
      55             : Datum
      56           0 : gtrgm_in(PG_FUNCTION_ARGS)
      57             : {
      58           0 :     elog(ERROR, "not implemented");
      59             :     PG_RETURN_DATUM(0);
      60             : }
      61             : 
      62             : Datum
      63           0 : gtrgm_out(PG_FUNCTION_ARGS)
      64             : {
      65           0 :     elog(ERROR, "not implemented");
      66             :     PG_RETURN_DATUM(0);
      67             : }
      68             : 
      69             : static TRGM *
      70       53304 : gtrgm_alloc(bool isalltrue, int siglen, BITVECP sign)
      71             : {
      72       53304 :     int         flag = SIGNKEY | (isalltrue ? ALLISTRUE : 0);
      73       53304 :     int         size = CALCGTSIZE(flag, siglen);
      74       53304 :     TRGM       *res = palloc(size);
      75             : 
      76       53304 :     SET_VARSIZE(res, size);
      77       53304 :     res->flag = flag;
      78             : 
      79       53304 :     if (!isalltrue)
      80             :     {
      81       53304 :         if (sign)
      82        1084 :             memcpy(GETSIGN(res), sign, siglen);
      83             :         else
      84       52220 :             memset(GETSIGN(res), 0, siglen);
      85             :     }
      86             : 
      87       53304 :     return res;
      88             : }
      89             : 
      90             : static void
      91       91794 : makesign(BITVECP sign, TRGM *a, int siglen)
      92             : {
      93             :     int32       k,
      94       91794 :                 len = ARRNELEM(a);
      95       91794 :     trgm       *ptr = GETARR(a);
      96       91794 :     int32       tmp = 0;
      97             : 
      98       91794 :     MemSet((void *) sign, 0, siglen);
      99       91794 :     SETBIT(sign, SIGLENBIT(siglen));    /* set last unused bit */
     100      892060 :     for (k = 0; k < len; k++)
     101             :     {
     102      800266 :         CPTRGM(((char *) &tmp), ptr + k);
     103      800266 :         HASH(sign, tmp, siglen);
     104             :     }
     105       91794 : }
     106             : 
     107             : Datum
     108       51052 : gtrgm_compress(PG_FUNCTION_ARGS)
     109             : {
     110       51052 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     111       51052 :     int         siglen = GET_SIGLEN();
     112       51052 :     GISTENTRY  *retval = entry;
     113             : 
     114       51052 :     if (entry->leafkey)
     115             :     {                           /* trgm */
     116             :         TRGM       *res;
     117       46804 :         text       *val = DatumGetTextPP(entry->key);
     118             : 
     119       46804 :         res = generate_trgm(VARDATA_ANY(val), VARSIZE_ANY_EXHDR(val));
     120       46804 :         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
     121       46804 :         gistentryinit(*retval, PointerGetDatum(res),
     122             :                       entry->rel, entry->page,
     123             :                       entry->offset, false);
     124             :     }
     125        4248 :     else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
     126        4248 :              !ISALLTRUE(DatumGetPointer(entry->key)))
     127             :     {
     128             :         int32       i;
     129             :         TRGM       *res;
     130        4248 :         BITVECP     sign = GETSIGN(DatumGetPointer(entry->key));
     131             : 
     132        4702 :         LOOPBYTE(siglen)
     133             :         {
     134        4702 :             if ((sign[i] & 0xff) != 0xff)
     135        4248 :                 PG_RETURN_POINTER(retval);
     136             :         }
     137             : 
     138           0 :         res = gtrgm_alloc(true, siglen, sign);
     139           0 :         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
     140           0 :         gistentryinit(*retval, PointerGetDatum(res),
     141             :                       entry->rel, entry->page,
     142             :                       entry->offset, false);
     143             :     }
     144       46804 :     PG_RETURN_POINTER(retval);
     145             : }
     146             : 
     147             : Datum
     148     2676230 : gtrgm_decompress(PG_FUNCTION_ARGS)
     149             : {
     150     2676230 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     151             :     GISTENTRY  *retval;
     152             :     text       *key;
     153             : 
     154     2676230 :     key = DatumGetTextPP(entry->key);
     155             : 
     156     2676230 :     if (key != (text *) DatumGetPointer(entry->key))
     157             :     {
     158             :         /* need to pass back the decompressed item */
     159           0 :         retval = palloc(sizeof(GISTENTRY));
     160           0 :         gistentryinit(*retval, PointerGetDatum(key),
     161             :                       entry->rel, entry->page, entry->offset, entry->leafkey);
     162           0 :         PG_RETURN_POINTER(retval);
     163             :     }
     164             :     else
     165             :     {
     166             :         /* we can return the entry as-is */
     167     2676230 :         PG_RETURN_POINTER(entry);
     168             :     }
     169             : }
     170             : 
     171             : static int32
     172        1312 : cnt_sml_sign_common(TRGM *qtrg, BITVECP sign, int siglen)
     173             : {
     174        1312 :     int32       count = 0;
     175             :     int32       k,
     176        1312 :                 len = ARRNELEM(qtrg);
     177        1312 :     trgm       *ptr = GETARR(qtrg);
     178        1312 :     int32       tmp = 0;
     179             : 
     180       12084 :     for (k = 0; k < len; k++)
     181             :     {
     182       10772 :         CPTRGM(((char *) &tmp), ptr + k);
     183       10772 :         count += GETBIT(sign, HASHVAL(tmp, siglen));
     184             :     }
     185             : 
     186        1312 :     return count;
     187             : }
     188             : 
     189             : Datum
     190       74272 : gtrgm_consistent(PG_FUNCTION_ARGS)
     191             : {
     192       74272 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     193       74272 :     text       *query = PG_GETARG_TEXT_P(1);
     194       74272 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     195             : 
     196             :     /* Oid      subtype = PG_GETARG_OID(3); */
     197       74272 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     198       74272 :     int         siglen = GET_SIGLEN();
     199       74272 :     TRGM       *key = (TRGM *) DatumGetPointer(entry->key);
     200             :     TRGM       *qtrg;
     201             :     bool        res;
     202       74272 :     Size        querysize = VARSIZE(query);
     203             :     gtrgm_consistent_cache *cache;
     204             :     double      nlimit;
     205             : 
     206             :     /*
     207             :      * We keep the extracted trigrams in cache, because trigram extraction is
     208             :      * relatively CPU-expensive.  When trying to reuse a cached value, check
     209             :      * strategy number not just query itself, because trigram extraction
     210             :      * depends on strategy.
     211             :      *
     212             :      * The cached structure is a single palloc chunk containing the
     213             :      * gtrgm_consistent_cache header, then the input query (4-byte length
     214             :      * word, uncompressed, starting at a MAXALIGN boundary), then the TRGM
     215             :      * value (also starting at a MAXALIGN boundary).  However we don't try to
     216             :      * include the regex graph (if any) in that struct.  (XXX currently, this
     217             :      * approach can leak regex graphs across index rescans.  Not clear if
     218             :      * that's worth fixing.)
     219             :      */
     220       74272 :     cache = (gtrgm_consistent_cache *) fcinfo->flinfo->fn_extra;
     221       74272 :     if (cache == NULL ||
     222       74160 :         cache->strategy != strategy ||
     223       74160 :         VARSIZE(cache->query) != querysize ||
     224       74160 :         memcmp((char *) cache->query, (char *) query, querysize) != 0)
     225             :     {
     226             :         gtrgm_consistent_cache *newcache;
     227         112 :         TrgmPackedGraph *graph = NULL;
     228             :         Size        qtrgsize;
     229             : 
     230         112 :         switch (strategy)
     231             :         {
     232          56 :             case SimilarityStrategyNumber:
     233             :             case WordSimilarityStrategyNumber:
     234             :             case StrictWordSimilarityStrategyNumber:
     235             :             case EqualStrategyNumber:
     236          56 :                 qtrg = generate_trgm(VARDATA(query),
     237          56 :                                      querysize - VARHDRSZ);
     238          56 :                 break;
     239          14 :             case ILikeStrategyNumber:
     240             : #ifndef IGNORECASE
     241             :                 elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
     242             : #endif
     243             :                 /* FALL THRU */
     244             :             case LikeStrategyNumber:
     245          14 :                 qtrg = generate_wildcard_trgm(VARDATA(query),
     246          14 :                                               querysize - VARHDRSZ);
     247          14 :                 break;
     248          42 :             case RegExpICaseStrategyNumber:
     249             : #ifndef IGNORECASE
     250             :                 elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
     251             : #endif
     252             :                 /* FALL THRU */
     253             :             case RegExpStrategyNumber:
     254          42 :                 qtrg = createTrgmNFA(query, PG_GET_COLLATION(),
     255          42 :                                      &graph, fcinfo->flinfo->fn_mcxt);
     256             :                 /* just in case an empty array is returned ... */
     257          42 :                 if (qtrg && ARRNELEM(qtrg) <= 0)
     258             :                 {
     259           0 :                     pfree(qtrg);
     260           0 :                     qtrg = NULL;
     261             :                 }
     262          42 :                 break;
     263           0 :             default:
     264           0 :                 elog(ERROR, "unrecognized strategy number: %d", strategy);
     265             :                 qtrg = NULL;    /* keep compiler quiet */
     266             :                 break;
     267             :         }
     268             : 
     269         112 :         qtrgsize = qtrg ? VARSIZE(qtrg) : 0;
     270             : 
     271             :         newcache = (gtrgm_consistent_cache *)
     272         112 :             MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
     273             :                                MAXALIGN(sizeof(gtrgm_consistent_cache)) +
     274         112 :                                MAXALIGN(querysize) +
     275             :                                qtrgsize);
     276             : 
     277         112 :         newcache->strategy = strategy;
     278         112 :         newcache->query = (text *)
     279             :             ((char *) newcache + MAXALIGN(sizeof(gtrgm_consistent_cache)));
     280         112 :         memcpy((char *) newcache->query, (char *) query, querysize);
     281         112 :         if (qtrg)
     282             :         {
     283         104 :             newcache->trigrams = (TRGM *)
     284         104 :                 ((char *) newcache->query + MAXALIGN(querysize));
     285         104 :             memcpy((char *) newcache->trigrams, (char *) qtrg, qtrgsize);
     286             :             /* release qtrg in case it was made in fn_mcxt */
     287         104 :             pfree(qtrg);
     288             :         }
     289             :         else
     290           8 :             newcache->trigrams = NULL;
     291         112 :         newcache->graph = graph;
     292             : 
     293         112 :         if (cache)
     294           0 :             pfree(cache);
     295         112 :         fcinfo->flinfo->fn_extra = (void *) newcache;
     296         112 :         cache = newcache;
     297             :     }
     298             : 
     299       74272 :     qtrg = cache->trigrams;
     300             : 
     301       74272 :     switch (strategy)
     302             :     {
     303       69462 :         case SimilarityStrategyNumber:
     304             :         case WordSimilarityStrategyNumber:
     305             :         case StrictWordSimilarityStrategyNumber:
     306             : 
     307             :             /*
     308             :              * Similarity search is exact. (Strict) word similarity search is
     309             :              * inexact
     310             :              */
     311       69462 :             *recheck = (strategy != SimilarityStrategyNumber);
     312             : 
     313       69462 :             nlimit = index_strategy_get_limit(strategy);
     314             : 
     315       69462 :             if (GIST_LEAF(entry))
     316             :             {                   /* all leafs contains orig trgm */
     317       68228 :                 double      tmpsml = cnt_sml(qtrg, key, *recheck);
     318             : 
     319       68228 :                 res = (tmpsml >= nlimit);
     320             :             }
     321        1234 :             else if (ISALLTRUE(key))
     322             :             {                   /* non-leaf contains signature */
     323           0 :                 res = true;
     324             :             }
     325             :             else
     326             :             {                   /* non-leaf contains signature */
     327        1234 :                 int32       count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
     328        1234 :                 int32       len = ARRNELEM(qtrg);
     329             : 
     330        1234 :                 if (len == 0)
     331           0 :                     res = false;
     332             :                 else
     333        1234 :                     res = (((((float8) count) / ((float8) len))) >= nlimit);
     334             :             }
     335       69462 :             break;
     336         380 :         case ILikeStrategyNumber:
     337             : #ifndef IGNORECASE
     338             :             elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
     339             : #endif
     340             :             /* FALL THRU */
     341             :         case LikeStrategyNumber:
     342             :         case EqualStrategyNumber:
     343             :             /* Wildcard and equal search are inexact */
     344         380 :             *recheck = true;
     345             : 
     346             :             /*
     347             :              * Check if all the extracted trigrams can be present in child
     348             :              * nodes.
     349             :              */
     350         380 :             if (GIST_LEAF(entry))
     351             :             {                   /* all leafs contains orig trgm */
     352         380 :                 res = trgm_contained_by(qtrg, key);
     353             :             }
     354           0 :             else if (ISALLTRUE(key))
     355             :             {                   /* non-leaf contains signature */
     356           0 :                 res = true;
     357             :             }
     358             :             else
     359           0 :             {                   /* non-leaf contains signature */
     360             :                 int32       k,
     361           0 :                             tmp = 0,
     362           0 :                             len = ARRNELEM(qtrg);
     363           0 :                 trgm       *ptr = GETARR(qtrg);
     364           0 :                 BITVECP     sign = GETSIGN(key);
     365             : 
     366           0 :                 res = true;
     367           0 :                 for (k = 0; k < len; k++)
     368             :                 {
     369           0 :                     CPTRGM(((char *) &tmp), ptr + k);
     370           0 :                     if (!GETBIT(sign, HASHVAL(tmp, siglen)))
     371             :                     {
     372           0 :                         res = false;
     373           0 :                         break;
     374             :                     }
     375             :                 }
     376             :             }
     377         380 :             break;
     378        4430 :         case RegExpICaseStrategyNumber:
     379             : #ifndef IGNORECASE
     380             :             elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
     381             : #endif
     382             :             /* FALL THRU */
     383             :         case RegExpStrategyNumber:
     384             :             /* Regexp search is inexact */
     385        4430 :             *recheck = true;
     386             : 
     387             :             /* Check regex match as much as we can with available info */
     388        4430 :             if (qtrg)
     389             :             {
     390        4350 :                 if (GIST_LEAF(entry))
     391             :                 {               /* all leafs contains orig trgm */
     392             :                     bool       *check;
     393             : 
     394        4300 :                     check = trgm_presence_map(qtrg, key);
     395        4300 :                     res = trigramsMatchGraph(cache->graph, check);
     396        4300 :                     pfree(check);
     397             :                 }
     398          50 :                 else if (ISALLTRUE(key))
     399             :                 {               /* non-leaf contains signature */
     400           0 :                     res = true;
     401             :                 }
     402             :                 else
     403             :                 {               /* non-leaf contains signature */
     404             :                     int32       k,
     405          50 :                                 tmp = 0,
     406          50 :                                 len = ARRNELEM(qtrg);
     407          50 :                     trgm       *ptr = GETARR(qtrg);
     408          50 :                     BITVECP     sign = GETSIGN(key);
     409             :                     bool       *check;
     410             : 
     411             :                     /*
     412             :                      * GETBIT() tests may give false positives, due to limited
     413             :                      * size of the sign array.  But since trigramsMatchGraph()
     414             :                      * implements a monotone boolean function, false positives
     415             :                      * in the check array can't lead to false negative answer.
     416             :                      * So we can apply trigramsMatchGraph despite uncertainty,
     417             :                      * and that usefully improves the quality of the search.
     418             :                      */
     419          50 :                     check = (bool *) palloc(len * sizeof(bool));
     420       12650 :                     for (k = 0; k < len; k++)
     421             :                     {
     422       12600 :                         CPTRGM(((char *) &tmp), ptr + k);
     423       12600 :                         check[k] = GETBIT(sign, HASHVAL(tmp, siglen));
     424             :                     }
     425          50 :                     res = trigramsMatchGraph(cache->graph, check);
     426          50 :                     pfree(check);
     427             :                 }
     428             :             }
     429             :             else
     430             :             {
     431             :                 /* trigram-free query must be rechecked everywhere */
     432          80 :                 res = true;
     433             :             }
     434        4430 :             break;
     435           0 :         default:
     436           0 :             elog(ERROR, "unrecognized strategy number: %d", strategy);
     437             :             res = false;        /* keep compiler quiet */
     438             :             break;
     439             :     }
     440             : 
     441       74272 :     PG_RETURN_BOOL(res);
     442             : }
     443             : 
     444             : Datum
     445        5778 : gtrgm_distance(PG_FUNCTION_ARGS)
     446             : {
     447        5778 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     448        5778 :     text       *query = PG_GETARG_TEXT_P(1);
     449        5778 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     450             : 
     451             :     /* Oid      subtype = PG_GETARG_OID(3); */
     452        5778 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     453        5778 :     int         siglen = GET_SIGLEN();
     454        5778 :     TRGM       *key = (TRGM *) DatumGetPointer(entry->key);
     455             :     TRGM       *qtrg;
     456             :     float8      res;
     457        5778 :     Size        querysize = VARSIZE(query);
     458        5778 :     char       *cache = (char *) fcinfo->flinfo->fn_extra;
     459             : 
     460             :     /*
     461             :      * Cache the generated trigrams across multiple calls with the same query.
     462             :      */
     463        5778 :     if (cache == NULL ||
     464        5770 :         VARSIZE(cache) != querysize ||
     465        5770 :         memcmp(cache, query, querysize) != 0)
     466             :     {
     467             :         char       *newcache;
     468             : 
     469           8 :         qtrg = generate_trgm(VARDATA(query), querysize - VARHDRSZ);
     470             : 
     471           8 :         newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
     472           8 :                                       MAXALIGN(querysize) +
     473           8 :                                       VARSIZE(qtrg));
     474             : 
     475           8 :         memcpy(newcache, query, querysize);
     476           8 :         memcpy(newcache + MAXALIGN(querysize), qtrg, VARSIZE(qtrg));
     477             : 
     478           8 :         if (cache)
     479           0 :             pfree(cache);
     480           8 :         fcinfo->flinfo->fn_extra = newcache;
     481           8 :         cache = newcache;
     482             :     }
     483             : 
     484        5778 :     qtrg = (TRGM *) (cache + MAXALIGN(querysize));
     485             : 
     486        5778 :     switch (strategy)
     487             :     {
     488        5778 :         case DistanceStrategyNumber:
     489             :         case WordDistanceStrategyNumber:
     490             :         case StrictWordDistanceStrategyNumber:
     491             :             /* Only plain trigram distance is exact */
     492        5778 :             *recheck = (strategy != DistanceStrategyNumber);
     493        5778 :             if (GIST_LEAF(entry))
     494             :             {                   /* all leafs contains orig trgm */
     495             : 
     496             :                 /*
     497             :                  * Prevent gcc optimizing the sml variable using volatile
     498             :                  * keyword. Otherwise res can differ from the
     499             :                  * word_similarity_dist_op() function.
     500             :                  */
     501        5700 :                 float4 volatile sml = cnt_sml(qtrg, key, *recheck);
     502             : 
     503        5700 :                 res = 1.0 - sml;
     504             :             }
     505          78 :             else if (ISALLTRUE(key))
     506             :             {                   /* all leafs contains orig trgm */
     507           0 :                 res = 0.0;
     508             :             }
     509             :             else
     510             :             {                   /* non-leaf contains signature */
     511          78 :                 int32       count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
     512          78 :                 int32       len = ARRNELEM(qtrg);
     513             : 
     514          78 :                 res = (len == 0) ? -1.0 : 1.0 - ((float8) count) / ((float8) len);
     515             :             }
     516        5778 :             break;
     517           0 :         default:
     518           0 :             elog(ERROR, "unrecognized strategy number: %d", strategy);
     519             :             res = 0;            /* keep compiler quiet */
     520             :             break;
     521             :     }
     522             : 
     523        5778 :     PG_RETURN_FLOAT8(res);
     524             : }
     525             : 
     526             : static int32
     527      104440 : unionkey(BITVECP sbase, TRGM *add, int siglen)
     528             : {
     529             :     int32       i;
     530             : 
     531      104440 :     if (ISSIGNKEY(add))
     532             :     {
     533       52220 :         BITVECP     sadd = GETSIGN(add);
     534             : 
     535       52220 :         if (ISALLTRUE(add))
     536           0 :             return 1;
     537             : 
     538     6992516 :         LOOPBYTE(siglen)
     539     6940296 :             sbase[i] |= sadd[i];
     540             :     }
     541             :     else
     542             :     {
     543       52220 :         trgm       *ptr = GETARR(add);
     544       52220 :         int32       tmp = 0;
     545             : 
     546      513308 :         for (i = 0; i < ARRNELEM(add); i++)
     547             :         {
     548      461088 :             CPTRGM(((char *) &tmp), ptr + i);
     549      461088 :             HASH(sbase, tmp, siglen);
     550             :         }
     551             :     }
     552      104440 :     return 0;
     553             : }
     554             : 
     555             : 
     556             : Datum
     557       52220 : gtrgm_union(PG_FUNCTION_ARGS)
     558             : {
     559       52220 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     560       52220 :     int32       len = entryvec->n;
     561       52220 :     int        *size = (int *) PG_GETARG_POINTER(1);
     562       52220 :     int         siglen = GET_SIGLEN();
     563             :     int32       i;
     564       52220 :     TRGM       *result = gtrgm_alloc(false, siglen, NULL);
     565       52220 :     BITVECP     base = GETSIGN(result);
     566             : 
     567      156660 :     for (i = 0; i < len; i++)
     568             :     {
     569      104440 :         if (unionkey(base, GETENTRY(entryvec, i), siglen))
     570             :         {
     571           0 :             result->flag = ALLISTRUE;
     572           0 :             SET_VARSIZE(result, CALCGTSIZE(ALLISTRUE, siglen));
     573           0 :             break;
     574             :         }
     575             :     }
     576             : 
     577       52220 :     *size = VARSIZE(result);
     578             : 
     579       52220 :     PG_RETURN_POINTER(result);
     580             : }
     581             : 
     582             : Datum
     583       52220 : gtrgm_same(PG_FUNCTION_ARGS)
     584             : {
     585       52220 :     TRGM       *a = (TRGM *) PG_GETARG_POINTER(0);
     586       52220 :     TRGM       *b = (TRGM *) PG_GETARG_POINTER(1);
     587       52220 :     bool       *result = (bool *) PG_GETARG_POINTER(2);
     588       52220 :     int         siglen = GET_SIGLEN();
     589             : 
     590       52220 :     if (ISSIGNKEY(a))
     591             :     {                           /* then b also ISSIGNKEY */
     592       52220 :         if (ISALLTRUE(a) && ISALLTRUE(b))
     593           0 :             *result = true;
     594       52220 :         else if (ISALLTRUE(a))
     595           0 :             *result = false;
     596       52220 :         else if (ISALLTRUE(b))
     597           0 :             *result = false;
     598             :         else
     599             :         {
     600             :             int32       i;
     601       52220 :             BITVECP     sa = GETSIGN(a),
     602       52220 :                         sb = GETSIGN(b);
     603             : 
     604       52220 :             *result = true;
     605     3537824 :             LOOPBYTE(siglen)
     606             :             {
     607     3488768 :                 if (sa[i] != sb[i])
     608             :                 {
     609        3164 :                     *result = false;
     610        3164 :                     break;
     611             :                 }
     612             :             }
     613             :         }
     614             :     }
     615             :     else
     616             :     {                           /* a and b ISARRKEY */
     617           0 :         int32       lena = ARRNELEM(a),
     618           0 :                     lenb = ARRNELEM(b);
     619             : 
     620           0 :         if (lena != lenb)
     621           0 :             *result = false;
     622             :         else
     623             :         {
     624           0 :             trgm       *ptra = GETARR(a),
     625           0 :                        *ptrb = GETARR(b);
     626             :             int32       i;
     627             : 
     628           0 :             *result = true;
     629           0 :             for (i = 0; i < lena; i++)
     630           0 :                 if (CMPTRGM(ptra + i, ptrb + i))
     631             :                 {
     632           0 :                     *result = false;
     633           0 :                     break;
     634             :                 }
     635             :         }
     636             :     }
     637             : 
     638       52220 :     PG_RETURN_POINTER(result);
     639             : }
     640             : 
     641             : static int32
     642           0 : sizebitvec(BITVECP sign, int siglen)
     643             : {
     644           0 :     return pg_popcount(sign, siglen);
     645             : }
     646             : 
     647             : static int
     648     9706496 : hemdistsign(BITVECP a, BITVECP b, int siglen)
     649             : {
     650             :     int         i,
     651             :                 diff,
     652     9706496 :                 dist = 0;
     653             : 
     654   431433016 :     LOOPBYTE(siglen)
     655             :     {
     656   421726520 :         diff = (unsigned char) (a[i] ^ b[i]);
     657             :         /* Using the popcount functions here isn't likely to win */
     658   421726520 :         dist += pg_number_of_ones[diff];
     659             :     }
     660     9706496 :     return dist;
     661             : }
     662             : 
     663             : static int
     664           0 : hemdist(TRGM *a, TRGM *b, int siglen)
     665             : {
     666           0 :     if (ISALLTRUE(a))
     667             :     {
     668           0 :         if (ISALLTRUE(b))
     669           0 :             return 0;
     670             :         else
     671           0 :             return SIGLENBIT(siglen) - sizebitvec(GETSIGN(b), siglen);
     672             :     }
     673           0 :     else if (ISALLTRUE(b))
     674           0 :         return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
     675             : 
     676           0 :     return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
     677             : }
     678             : 
     679             : Datum
     680     2353058 : gtrgm_penalty(PG_FUNCTION_ARGS)
     681             : {
     682     2353058 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
     683     2353058 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     684     2353058 :     float      *penalty = (float *) PG_GETARG_POINTER(2);
     685     2353058 :     int         siglen = GET_SIGLEN();
     686     2353058 :     TRGM       *origval = (TRGM *) DatumGetPointer(origentry->key);
     687     2353058 :     TRGM       *newval = (TRGM *) DatumGetPointer(newentry->key);
     688     2353058 :     BITVECP     orig = GETSIGN(origval);
     689             : 
     690     2353058 :     *penalty = 0.0;
     691             : 
     692     2353058 :     if (ISARRKEY(newval))
     693             :     {
     694     2353058 :         char       *cache = (char *) fcinfo->flinfo->fn_extra;
     695     2353058 :         TRGM       *cachedVal = (TRGM *) (cache + MAXALIGN(siglen));
     696     2353058 :         Size        newvalsize = VARSIZE(newval);
     697             :         BITVECP     sign;
     698             : 
     699             :         /*
     700             :          * Cache the sign data across multiple calls with the same newval.
     701             :          */
     702     2353058 :         if (cache == NULL ||
     703     2353048 :             VARSIZE(cachedVal) != newvalsize ||
     704     2350994 :             memcmp(cachedVal, newval, newvalsize) != 0)
     705             :         {
     706             :             char       *newcache;
     707             : 
     708        5772 :             newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
     709        5772 :                                           MAXALIGN(siglen) +
     710             :                                           newvalsize);
     711             : 
     712        5772 :             makesign((BITVECP) newcache, newval, siglen);
     713             : 
     714        5772 :             cachedVal = (TRGM *) (newcache + MAXALIGN(siglen));
     715        5772 :             memcpy(cachedVal, newval, newvalsize);
     716             : 
     717        5772 :             if (cache)
     718        5762 :                 pfree(cache);
     719        5772 :             fcinfo->flinfo->fn_extra = newcache;
     720        5772 :             cache = newcache;
     721             :         }
     722             : 
     723     2353058 :         sign = (BITVECP) cache;
     724             : 
     725     2353058 :         if (ISALLTRUE(origval))
     726           0 :             *penalty = ((float) (SIGLENBIT(siglen) - sizebitvec(sign, siglen))) / (float) (SIGLENBIT(siglen) + 1);
     727             :         else
     728     2353058 :             *penalty = hemdistsign(sign, orig, siglen);
     729             :     }
     730             :     else
     731           0 :         *penalty = hemdist(origval, newval, siglen);
     732     2353058 :     PG_RETURN_POINTER(penalty);
     733             : }
     734             : 
     735             : typedef struct
     736             : {
     737             :     bool        allistrue;
     738             :     BITVECP     sign;
     739             : } CACHESIGN;
     740             : 
     741             : static void
     742       86462 : fillcache(CACHESIGN *item, TRGM *key, BITVECP sign, int siglen)
     743             : {
     744       86462 :     item->allistrue = false;
     745       86462 :     item->sign = sign;
     746       86462 :     if (ISARRKEY(key))
     747       86022 :         makesign(item->sign, key, siglen);
     748         440 :     else if (ISALLTRUE(key))
     749           0 :         item->allistrue = true;
     750             :     else
     751         440 :         memcpy((void *) item->sign, (void *) GETSIGN(key), siglen);
     752       86462 : }
     753             : 
     754             : #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
     755             : typedef struct
     756             : {
     757             :     OffsetNumber pos;
     758             :     int32       cost;
     759             : } SPLITCOST;
     760             : 
     761             : static int
     762       95988 : comparecost(const void *a, const void *b)
     763             : {
     764       95988 :     if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
     765       86508 :         return 0;
     766             :     else
     767        9480 :         return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
     768             : }
     769             : 
     770             : 
     771             : static int
     772     7182682 : hemdistcache(CACHESIGN *a, CACHESIGN *b, int siglen)
     773             : {
     774     7182682 :     if (a->allistrue)
     775             :     {
     776           0 :         if (b->allistrue)
     777           0 :             return 0;
     778             :         else
     779           0 :             return SIGLENBIT(siglen) - sizebitvec(b->sign, siglen);
     780             :     }
     781     7182682 :     else if (b->allistrue)
     782           0 :         return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
     783             : 
     784     7182682 :     return hemdistsign(a->sign, b->sign, siglen);
     785             : }
     786             : 
     787             : Datum
     788         542 : gtrgm_picksplit(PG_FUNCTION_ARGS)
     789             : {
     790         542 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     791         542 :     OffsetNumber maxoff = entryvec->n - 1;
     792         542 :     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
     793         542 :     int         siglen = GET_SIGLEN();
     794             :     OffsetNumber k,
     795             :                 j;
     796             :     TRGM       *datum_l,
     797             :                *datum_r;
     798             :     BITVECP     union_l,
     799             :                 union_r;
     800             :     int32       size_alpha,
     801             :                 size_beta;
     802             :     int32       size_waste,
     803         542 :                 waste = -1;
     804             :     int32       nbytes;
     805         542 :     OffsetNumber seed_1 = 0,
     806         542 :                 seed_2 = 0;
     807             :     OffsetNumber *left,
     808             :                *right;
     809             :     BITVECP     ptr;
     810             :     int         i;
     811             :     CACHESIGN  *cache;
     812             :     char       *cache_sign;
     813             :     SPLITCOST  *costvector;
     814             : 
     815             :     /* cache the sign data for each existing item */
     816         542 :     cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 1));
     817         542 :     cache_sign = palloc(siglen * (maxoff + 1));
     818             : 
     819       87004 :     for (k = FirstOffsetNumber; k <= maxoff; k = OffsetNumberNext(k))
     820       86462 :         fillcache(&cache[k], GETENTRY(entryvec, k), &cache_sign[siglen * k],
     821             :                   siglen);
     822             : 
     823             :     /* now find the two furthest-apart items */
     824       86462 :     for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
     825             :     {
     826     7095678 :         for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
     827             :         {
     828     7009758 :             size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
     829     7009758 :             if (size_waste > waste)
     830             :             {
     831         912 :                 waste = size_waste;
     832         912 :                 seed_1 = k;
     833         912 :                 seed_2 = j;
     834             :             }
     835             :         }
     836             :     }
     837             : 
     838             :     /* just in case we didn't make a selection ... */
     839         542 :     if (seed_1 == 0 || seed_2 == 0)
     840             :     {
     841           0 :         seed_1 = 1;
     842           0 :         seed_2 = 2;
     843             :     }
     844             : 
     845             :     /* initialize the result vectors */
     846         542 :     nbytes = maxoff * sizeof(OffsetNumber);
     847         542 :     v->spl_left = left = (OffsetNumber *) palloc(nbytes);
     848         542 :     v->spl_right = right = (OffsetNumber *) palloc(nbytes);
     849         542 :     v->spl_nleft = 0;
     850         542 :     v->spl_nright = 0;
     851             : 
     852             :     /* form initial .. */
     853         542 :     datum_l = gtrgm_alloc(cache[seed_1].allistrue, siglen, cache[seed_1].sign);
     854         542 :     datum_r = gtrgm_alloc(cache[seed_2].allistrue, siglen, cache[seed_2].sign);
     855             : 
     856         542 :     union_l = GETSIGN(datum_l);
     857         542 :     union_r = GETSIGN(datum_r);
     858             : 
     859             :     /* sort before ... */
     860         542 :     costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
     861       87004 :     for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
     862             :     {
     863       86462 :         costvector[j - 1].pos = j;
     864       86462 :         size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
     865       86462 :         size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
     866       86462 :         costvector[j - 1].cost = abs(size_alpha - size_beta);
     867             :     }
     868         542 :     qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
     869             : 
     870       87004 :     for (k = 0; k < maxoff; k++)
     871             :     {
     872       86462 :         j = costvector[k].pos;
     873       86462 :         if (j == seed_1)
     874             :         {
     875         542 :             *left++ = j;
     876         542 :             v->spl_nleft++;
     877         542 :             continue;
     878             :         }
     879       85920 :         else if (j == seed_2)
     880             :         {
     881         542 :             *right++ = j;
     882         542 :             v->spl_nright++;
     883         542 :             continue;
     884             :         }
     885             : 
     886       85378 :         if (ISALLTRUE(datum_l) || cache[j].allistrue)
     887             :         {
     888           0 :             if (ISALLTRUE(datum_l) && cache[j].allistrue)
     889           0 :                 size_alpha = 0;
     890             :             else
     891           0 :                 size_alpha = SIGLENBIT(siglen) -
     892           0 :                     sizebitvec((cache[j].allistrue) ? GETSIGN(datum_l) :
     893           0 :                                GETSIGN(cache[j].sign),
     894             :                                siglen);
     895             :         }
     896             :         else
     897       85378 :             size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
     898             : 
     899       85378 :         if (ISALLTRUE(datum_r) || cache[j].allistrue)
     900             :         {
     901           0 :             if (ISALLTRUE(datum_r) && cache[j].allistrue)
     902           0 :                 size_beta = 0;
     903             :             else
     904           0 :                 size_beta = SIGLENBIT(siglen) -
     905           0 :                     sizebitvec((cache[j].allistrue) ? GETSIGN(datum_r) :
     906           0 :                                GETSIGN(cache[j].sign),
     907             :                                siglen);
     908             :         }
     909             :         else
     910       85378 :             size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
     911             : 
     912       85378 :         if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
     913             :         {
     914       42458 :             if (ISALLTRUE(datum_l) || cache[j].allistrue)
     915             :             {
     916           0 :                 if (!ISALLTRUE(datum_l))
     917           0 :                     MemSet((void *) GETSIGN(datum_l), 0xff, siglen);
     918             :             }
     919             :             else
     920             :             {
     921       42458 :                 ptr = cache[j].sign;
     922     2765154 :                 LOOPBYTE(siglen)
     923     2722696 :                     union_l[i] |= ptr[i];
     924             :             }
     925       42458 :             *left++ = j;
     926       42458 :             v->spl_nleft++;
     927             :         }
     928             :         else
     929             :         {
     930       42920 :             if (ISALLTRUE(datum_r) || cache[j].allistrue)
     931             :             {
     932           0 :                 if (!ISALLTRUE(datum_r))
     933           0 :                     MemSet((void *) GETSIGN(datum_r), 0xff, siglen);
     934             :             }
     935             :             else
     936             :             {
     937       42920 :                 ptr = cache[j].sign;
     938     2759088 :                 LOOPBYTE(siglen)
     939     2716168 :                     union_r[i] |= ptr[i];
     940             :             }
     941       42920 :             *right++ = j;
     942       42920 :             v->spl_nright++;
     943             :         }
     944             :     }
     945             : 
     946         542 :     v->spl_ldatum = PointerGetDatum(datum_l);
     947         542 :     v->spl_rdatum = PointerGetDatum(datum_r);
     948             : 
     949         542 :     PG_RETURN_POINTER(v);
     950             : }
     951             : 
     952             : Datum
     953          34 : gtrgm_options(PG_FUNCTION_ARGS)
     954             : {
     955          34 :     local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
     956             : 
     957          34 :     init_local_reloptions(relopts, sizeof(TrgmGistOptions));
     958          34 :     add_local_int_reloption(relopts, "siglen",
     959             :                             "signature length in bytes",
     960             :                             SIGLEN_DEFAULT, 1, SIGLEN_MAX,
     961             :                             offsetof(TrgmGistOptions, siglen));
     962             : 
     963          34 :     PG_RETURN_VOID();
     964             : }

Generated by: LCOV version 1.13