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

Generated by: LCOV version 1.13