LCOV - code coverage report
Current view: top level - contrib/pg_trgm - trgm_gist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 346 434 79.7 %
Date: 2020-06-01 09:07:10 Functions: 28 32 87.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13