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-03-19 08:10:50 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       53224 : gtrgm_alloc(bool isalltrue, int siglen, BITVECP sign)
      78             : {
      79       53224 :     int         flag = SIGNKEY | (isalltrue ? ALLISTRUE : 0);
      80       53224 :     int         size = CALCGTSIZE(flag, siglen);
      81       53224 :     TRGM       *res = palloc(size);
      82             : 
      83       53224 :     SET_VARSIZE(res, size);
      84       53224 :     res->flag = flag;
      85             : 
      86       53224 :     if (!isalltrue)
      87             :     {
      88       53224 :         if (sign)
      89        1076 :             memcpy(GETSIGN(res), sign, siglen);
      90             :         else
      91       52148 :             memset(GETSIGN(res), 0, siglen);
      92             :     }
      93             : 
      94       53224 :     return res;
      95             : }
      96             : 
      97             : static void
      98       91830 : makesign(BITVECP sign, TRGM *a, int siglen)
      99             : {
     100             :     int32       k,
     101       91830 :                 len = ARRNELEM(a);
     102       91830 :     trgm       *ptr = GETARR(a);
     103       91830 :     int32       tmp = 0;
     104             : 
     105       91830 :     MemSet(sign, 0, siglen);
     106       91830 :     SETBIT(sign, SIGLENBIT(siglen));    /* set last unused bit */
     107      891490 :     for (k = 0; k < len; k++)
     108             :     {
     109      799660 :         CPTRGM(((char *) &tmp), ptr + k);
     110      799660 :         HASH(sign, tmp, siglen);
     111             :     }
     112       91830 : }
     113             : 
     114             : Datum
     115       50996 : gtrgm_compress(PG_FUNCTION_ARGS)
     116             : {
     117       50996 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     118       50996 :     int         siglen = GET_SIGLEN();
     119       50996 :     GISTENTRY  *retval = entry;
     120             : 
     121       50996 :     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        4192 :     else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
     133        4192 :              !ISALLTRUE(DatumGetPointer(entry->key)))
     134             :     {
     135             :         int32       i;
     136             :         TRGM       *res;
     137        4192 :         BITVECP     sign = GETSIGN(DatumGetPointer(entry->key));
     138             : 
     139        4558 :         LOOPBYTE(siglen)
     140             :         {
     141        4558 :             if ((sign[i] & 0xff) != 0xff)
     142        4192 :                 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     2708972 : gtrgm_decompress(PG_FUNCTION_ARGS)
     156             : {
     157     2708972 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     158             :     GISTENTRY  *retval;
     159             :     text       *key;
     160             : 
     161     2708972 :     key = DatumGetTextPP(entry->key);
     162             : 
     163     2708972 :     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     2708972 :         PG_RETURN_POINTER(entry);
     175             :     }
     176             : }
     177             : 
     178             : static int32
     179        1294 : cnt_sml_sign_common(TRGM *qtrg, BITVECP sign, int siglen)
     180             : {
     181        1294 :     int32       count = 0;
     182             :     int32       k,
     183        1294 :                 len = ARRNELEM(qtrg);
     184        1294 :     trgm       *ptr = GETARR(qtrg);
     185        1294 :     int32       tmp = 0;
     186             : 
     187       11830 :     for (k = 0; k < len; k++)
     188             :     {
     189       10536 :         CPTRGM(((char *) &tmp), ptr + k);
     190       10536 :         count += GETBIT(sign, HASHVAL(tmp, siglen));
     191             :     }
     192             : 
     193        1294 :     return count;
     194             : }
     195             : 
     196             : Datum
     197       75308 : gtrgm_consistent(PG_FUNCTION_ARGS)
     198             : {
     199       75308 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     200       75308 :     text       *query = PG_GETARG_TEXT_P(1);
     201       75308 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     202             : 
     203             :     /* Oid      subtype = PG_GETARG_OID(3); */
     204       75308 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     205       75308 :     int         siglen = GET_SIGLEN();
     206       75308 :     TRGM       *key = (TRGM *) DatumGetPointer(entry->key);
     207             :     TRGM       *qtrg;
     208             :     bool        res;
     209       75308 :     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       75308 :     cache = (gtrgm_consistent_cache *) fcinfo->flinfo->fn_extra;
     228       75308 :     if (cache == NULL ||
     229       75196 :         cache->strategy != strategy ||
     230       75196 :         VARSIZE(cache->query) != querysize ||
     231       75196 :         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       75308 :     qtrg = cache->trigrams;
     307             : 
     308       75308 :     switch (strategy)
     309             :     {
     310       70504 :         case SimilarityStrategyNumber:
     311             :         case WordSimilarityStrategyNumber:
     312             :         case StrictWordSimilarityStrategyNumber:
     313             : 
     314             :             /*
     315             :              * Similarity search is exact. (Strict) word similarity search is
     316             :              * inexact
     317             :              */
     318       70504 :             *recheck = (strategy != SimilarityStrategyNumber);
     319             : 
     320       70504 :             nlimit = index_strategy_get_limit(strategy);
     321             : 
     322       70504 :             if (GIST_LEAF(entry))
     323             :             {                   /* all leafs contains orig trgm */
     324       69288 :                 double      tmpsml = cnt_sml(qtrg, key, *recheck);
     325             : 
     326       69288 :                 res = (tmpsml >= nlimit);
     327             :             }
     328        1216 :             else if (ISALLTRUE(key))
     329             :             {                   /* non-leaf contains signature */
     330           0 :                 res = true;
     331             :             }
     332             :             else
     333             :             {                   /* non-leaf contains signature */
     334        1216 :                 int32       count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
     335        1216 :                 int32       len = ARRNELEM(qtrg);
     336             : 
     337        1216 :                 if (len == 0)
     338           0 :                     res = false;
     339             :                 else
     340        1216 :                     res = (((((float8) count) / ((float8) len))) >= nlimit);
     341             :             }
     342       70504 :             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        4424 :         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        4424 :             *recheck = true;
     393             : 
     394             :             /* Check regex match as much as we can with available info */
     395        4424 :             if (qtrg)
     396             :             {
     397        4344 :                 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          44 :                 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          44 :                                 tmp = 0,
     413          44 :                                 len = ARRNELEM(qtrg);
     414          44 :                     trgm       *ptr = GETARR(qtrg);
     415          44 :                     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          44 :                     check = (bool *) palloc(len * sizeof(bool));
     427       11132 :                     for (k = 0; k < len; k++)
     428             :                     {
     429       11088 :                         CPTRGM(((char *) &tmp), ptr + k);
     430       11088 :                         check[k] = GETBIT(sign, HASHVAL(tmp, siglen));
     431             :                     }
     432          44 :                     res = trigramsMatchGraph(cache->graph, check);
     433          44 :                     pfree(check);
     434             :                 }
     435             :             }
     436             :             else
     437             :             {
     438             :                 /* trigram-free query must be rechecked everywhere */
     439          80 :                 res = true;
     440             :             }
     441        4424 :             break;
     442           0 :         default:
     443           0 :             elog(ERROR, "unrecognized strategy number: %d", strategy);
     444             :             res = false;        /* keep compiler quiet */
     445             :             break;
     446             :     }
     447             : 
     448       75308 :     PG_RETURN_BOOL(res);
     449             : }
     450             : 
     451             : Datum
     452        6218 : gtrgm_distance(PG_FUNCTION_ARGS)
     453             : {
     454        6218 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     455        6218 :     text       *query = PG_GETARG_TEXT_P(1);
     456        6218 :     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
     457             : 
     458             :     /* Oid      subtype = PG_GETARG_OID(3); */
     459        6218 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     460        6218 :     int         siglen = GET_SIGLEN();
     461        6218 :     TRGM       *key = (TRGM *) DatumGetPointer(entry->key);
     462             :     TRGM       *qtrg;
     463             :     float8      res;
     464        6218 :     Size        querysize = VARSIZE(query);
     465        6218 :     char       *cache = (char *) fcinfo->flinfo->fn_extra;
     466             : 
     467             :     /*
     468             :      * Cache the generated trigrams across multiple calls with the same query.
     469             :      */
     470        6218 :     if (cache == NULL ||
     471        6210 :         VARSIZE(cache) != querysize ||
     472        6210 :         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        6218 :     qtrg = (TRGM *) (cache + MAXALIGN(querysize));
     492             : 
     493        6218 :     switch (strategy)
     494             :     {
     495        6218 :         case DistanceStrategyNumber:
     496             :         case WordDistanceStrategyNumber:
     497             :         case StrictWordDistanceStrategyNumber:
     498             :             /* Only plain trigram distance is exact */
     499        6218 :             *recheck = (strategy != DistanceStrategyNumber);
     500        6218 :             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        6140 :                 float4 volatile sml = cnt_sml(qtrg, key, *recheck);
     509             : 
     510        6140 :                 res = 1.0 - sml;
     511             :             }
     512          78 :             else if (ISALLTRUE(key))
     513             :             {                   /* all leafs contains orig trgm */
     514           0 :                 res = 0.0;
     515             :             }
     516             :             else
     517             :             {                   /* non-leaf contains signature */
     518          78 :                 int32       count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
     519          78 :                 int32       len = ARRNELEM(qtrg);
     520             : 
     521          78 :                 res = (len == 0) ? -1.0 : 1.0 - ((float8) count) / ((float8) len);
     522             :             }
     523        6218 :             break;
     524           0 :         default:
     525           0 :             elog(ERROR, "unrecognized strategy number: %d", strategy);
     526             :             res = 0;            /* keep compiler quiet */
     527             :             break;
     528             :     }
     529             : 
     530        6218 :     PG_RETURN_FLOAT8(res);
     531             : }
     532             : 
     533             : static int32
     534      104296 : unionkey(BITVECP sbase, TRGM *add, int siglen)
     535             : {
     536             :     int32       i;
     537             : 
     538      104296 :     if (ISSIGNKEY(add))
     539             :     {
     540       52148 :         BITVECP     sadd = GETSIGN(add);
     541             : 
     542       52148 :         if (ISALLTRUE(add))
     543           0 :             return 1;
     544             : 
     545     6850740 :         LOOPBYTE(siglen)
     546     6798592 :             sbase[i] |= sadd[i];
     547             :     }
     548             :     else
     549             :     {
     550       52148 :         trgm       *ptr = GETARR(add);
     551       52148 :         int32       tmp = 0;
     552             : 
     553      512378 :         for (i = 0; i < ARRNELEM(add); i++)
     554             :         {
     555      460230 :             CPTRGM(((char *) &tmp), ptr + i);
     556      460230 :             HASH(sbase, tmp, siglen);
     557             :         }
     558             :     }
     559      104296 :     return 0;
     560             : }
     561             : 
     562             : 
     563             : Datum
     564       52148 : gtrgm_union(PG_FUNCTION_ARGS)
     565             : {
     566       52148 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     567       52148 :     int32       len = entryvec->n;
     568       52148 :     int        *size = (int *) PG_GETARG_POINTER(1);
     569       52148 :     int         siglen = GET_SIGLEN();
     570             :     int32       i;
     571       52148 :     TRGM       *result = gtrgm_alloc(false, siglen, NULL);
     572       52148 :     BITVECP     base = GETSIGN(result);
     573             : 
     574      156444 :     for (i = 0; i < len; i++)
     575             :     {
     576      104296 :         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       52148 :     *size = VARSIZE(result);
     585             : 
     586       52148 :     PG_RETURN_POINTER(result);
     587             : }
     588             : 
     589             : Datum
     590       52148 : gtrgm_same(PG_FUNCTION_ARGS)
     591             : {
     592       52148 :     TRGM       *a = (TRGM *) PG_GETARG_POINTER(0);
     593       52148 :     TRGM       *b = (TRGM *) PG_GETARG_POINTER(1);
     594       52148 :     bool       *result = (bool *) PG_GETARG_POINTER(2);
     595       52148 :     int         siglen = GET_SIGLEN();
     596             : 
     597       52148 :     if (ISSIGNKEY(a))
     598             :     {                           /* then b also ISSIGNKEY */
     599       52148 :         if (ISALLTRUE(a) && ISALLTRUE(b))
     600           0 :             *result = true;
     601       52148 :         else if (ISALLTRUE(a))
     602           0 :             *result = false;
     603       52148 :         else if (ISALLTRUE(b))
     604           0 :             *result = false;
     605             :         else
     606             :         {
     607             :             int32       i;
     608       52148 :             BITVECP     sa = GETSIGN(a),
     609       52148 :                         sb = GETSIGN(b);
     610             : 
     611       52148 :             *result = true;
     612     3505388 :             LOOPBYTE(siglen)
     613             :             {
     614     3456356 :                 if (sa[i] != sb[i])
     615             :                 {
     616        3116 :                     *result = false;
     617        3116 :                     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       52148 :     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     9741572 : hemdistsign(BITVECP a, BITVECP b, int siglen)
     656             : {
     657             :     int         i,
     658             :                 diff,
     659     9741572 :                 dist = 0;
     660             : 
     661   399596404 :     LOOPBYTE(siglen)
     662             :     {
     663   389854832 :         diff = (unsigned char) (a[i] ^ b[i]);
     664             :         /* Using the popcount functions here isn't likely to win */
     665   389854832 :         dist += pg_number_of_ones[diff];
     666             :     }
     667     9741572 :     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     2384520 : gtrgm_penalty(PG_FUNCTION_ARGS)
     688             : {
     689     2384520 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
     690     2384520 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     691     2384520 :     float      *penalty = (float *) PG_GETARG_POINTER(2);
     692     2384520 :     int         siglen = GET_SIGLEN();
     693     2384520 :     TRGM       *origval = (TRGM *) DatumGetPointer(origentry->key);
     694     2384520 :     TRGM       *newval = (TRGM *) DatumGetPointer(newentry->key);
     695     2384520 :     BITVECP     orig = GETSIGN(origval);
     696             : 
     697     2384520 :     *penalty = 0.0;
     698             : 
     699     2384520 :     if (ISARRKEY(newval))
     700             :     {
     701     2384520 :         char       *cache = (char *) fcinfo->flinfo->fn_extra;
     702     2384520 :         TRGM       *cachedVal = (TRGM *) (cache + MAXALIGN(siglen));
     703     2384520 :         Size        newvalsize = VARSIZE(newval);
     704             :         BITVECP     sign;
     705             : 
     706             :         /*
     707             :          * Cache the sign data across multiple calls with the same newval.
     708             :          */
     709     2384520 :         if (cache == NULL ||
     710     2384510 :             VARSIZE(cachedVal) != newvalsize ||
     711     2382456 :             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     2384520 :         sign = (BITVECP) cache;
     731             : 
     732     2384520 :         if (ISALLTRUE(origval))
     733           0 :             *penalty = ((float) (SIGLENBIT(siglen) - sizebitvec(sign, siglen))) / (float) (SIGLENBIT(siglen) + 1);
     734             :         else
     735     2384520 :             *penalty = hemdistsign(sign, orig, siglen);
     736             :     }
     737             :     else
     738           0 :         *penalty = hemdist(origval, newval, siglen);
     739     2384520 :     PG_RETURN_POINTER(penalty);
     740             : }
     741             : 
     742             : typedef struct
     743             : {
     744             :     bool        allistrue;
     745             :     BITVECP     sign;
     746             : } CACHESIGN;
     747             : 
     748             : static void
     749       86482 : fillcache(CACHESIGN *item, TRGM *key, BITVECP sign, int siglen)
     750             : {
     751       86482 :     item->allistrue = false;
     752       86482 :     item->sign = sign;
     753       86482 :     if (ISARRKEY(key))
     754       86058 :         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       86482 : }
     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       96234 : comparecost(const void *a, const void *b)
     770             : {
     771       96234 :     if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
     772       86664 :         return 0;
     773             :     else
     774        9570 :         return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
     775             : }
     776             : 
     777             : 
     778             : static int
     779     7186240 : hemdistcache(CACHESIGN *a, CACHESIGN *b, int siglen)
     780             : {
     781     7186240 :     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     7186240 :     else if (b->allistrue)
     789           0 :         return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
     790             : 
     791     7186240 :     return hemdistsign(a->sign, b->sign, siglen);
     792             : }
     793             : 
     794             : Datum
     795         538 : gtrgm_picksplit(PG_FUNCTION_ARGS)
     796             : {
     797         538 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     798         538 :     OffsetNumber maxoff = entryvec->n - 1;
     799         538 :     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
     800         538 :     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         538 :                 waste = -1;
     811             :     int32       nbytes;
     812         538 :     OffsetNumber seed_1 = 0,
     813         538 :                 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         538 :     cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 1));
     824         538 :     cache_sign = palloc(siglen * (maxoff + 1));
     825             : 
     826       87020 :     for (k = FirstOffsetNumber; k <= maxoff; k = OffsetNumberNext(k))
     827       86482 :         fillcache(&cache[k], GETENTRY(entryvec, k), &cache_sign[siglen * k],
     828             :                   siglen);
     829             : 
     830             :     /* now find the two furthest-apart items */
     831       86482 :     for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
     832             :     {
     833     7099220 :         for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
     834             :         {
     835     7013276 :             size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
     836     7013276 :             if (size_waste > waste)
     837             :             {
     838         902 :                 waste = size_waste;
     839         902 :                 seed_1 = k;
     840         902 :                 seed_2 = j;
     841             :             }
     842             :         }
     843             :     }
     844             : 
     845             :     /* just in case we didn't make a selection ... */
     846         538 :     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         538 :     nbytes = maxoff * sizeof(OffsetNumber);
     854         538 :     v->spl_left = left = (OffsetNumber *) palloc(nbytes);
     855         538 :     v->spl_right = right = (OffsetNumber *) palloc(nbytes);
     856         538 :     v->spl_nleft = 0;
     857         538 :     v->spl_nright = 0;
     858             : 
     859             :     /* form initial .. */
     860         538 :     datum_l = gtrgm_alloc(cache[seed_1].allistrue, siglen, cache[seed_1].sign);
     861         538 :     datum_r = gtrgm_alloc(cache[seed_2].allistrue, siglen, cache[seed_2].sign);
     862             : 
     863         538 :     union_l = GETSIGN(datum_l);
     864         538 :     union_r = GETSIGN(datum_r);
     865             : 
     866             :     /* sort before ... */
     867         538 :     costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
     868       87020 :     for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
     869             :     {
     870       86482 :         costvector[j - 1].pos = j;
     871       86482 :         size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
     872       86482 :         size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
     873       86482 :         costvector[j - 1].cost = abs(size_alpha - size_beta);
     874             :     }
     875         538 :     qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
     876             : 
     877       87020 :     for (k = 0; k < maxoff; k++)
     878             :     {
     879       86482 :         j = costvector[k].pos;
     880       86482 :         if (j == seed_1)
     881             :         {
     882         538 :             *left++ = j;
     883         538 :             v->spl_nleft++;
     884         538 :             continue;
     885             :         }
     886       85944 :         else if (j == seed_2)
     887             :         {
     888         538 :             *right++ = j;
     889         538 :             v->spl_nright++;
     890         538 :             continue;
     891             :         }
     892             : 
     893       85406 :         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       85406 :             size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
     905             : 
     906       85406 :         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       85406 :             size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
     918             : 
     919       85406 :         if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
     920             :         {
     921       42462 :             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       42462 :                 ptr = cache[j].sign;
     929     2519742 :                 LOOPBYTE(siglen)
     930     2477280 :                     union_l[i] |= ptr[i];
     931             :             }
     932       42462 :             *left++ = j;
     933       42462 :             v->spl_nleft++;
     934             :         }
     935             :         else
     936             :         {
     937       42944 :             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       42944 :                 ptr = cache[j].sign;
     945     2501864 :                 LOOPBYTE(siglen)
     946     2458920 :                     union_r[i] |= ptr[i];
     947             :             }
     948       42944 :             *right++ = j;
     949       42944 :             v->spl_nright++;
     950             :         }
     951             :     }
     952             : 
     953         538 :     v->spl_ldatum = PointerGetDatum(datum_l);
     954         538 :     v->spl_rdatum = PointerGetDatum(datum_r);
     955             : 
     956         538 :     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