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

Generated by: LCOV version 1.14