LCOV - code coverage report
Current view: top level - src/backend/utils/adt - tsgistidx.c (source / functions) Hit Total Coverage
Test: PostgreSQL 14devel Lines: 262 334 78.4 %
Date: 2021-01-26 03:06:49 Functions: 19 23 82.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * tsgistidx.c
       4             :  *    GiST support functions for tsvector_ops
       5             :  *
       6             :  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
       7             :  *
       8             :  *
       9             :  * IDENTIFICATION
      10             :  *    src/backend/utils/adt/tsgistidx.c
      11             :  *
      12             :  *-------------------------------------------------------------------------
      13             :  */
      14             : 
      15             : #include "postgres.h"
      16             : 
      17             : #include "access/gist.h"
      18             : #include "access/heaptoast.h"
      19             : #include "access/reloptions.h"
      20             : #include "lib/qunique.h"
      21             : #include "port/pg_bitutils.h"
      22             : #include "tsearch/ts_utils.h"
      23             : #include "utils/builtins.h"
      24             : #include "utils/pg_crc.h"
      25             : 
      26             : 
      27             : /* tsvector_ops opclass options */
      28             : typedef struct
      29             : {
      30             :     int32       vl_len_;        /* varlena header (do not touch directly!) */
      31             :     int         siglen;         /* signature length */
      32             : } GistTsVectorOptions;
      33             : 
      34             : #define SIGLEN_DEFAULT  (31 * 4)
      35             : #define SIGLEN_MAX      GISTMaxIndexKeySize
      36             : #define GET_SIGLEN()    (PG_HAS_OPCLASS_OPTIONS() ? \
      37             :                          ((GistTsVectorOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
      38             :                          SIGLEN_DEFAULT)
      39             : 
      40             : #define SIGLENBIT(siglen) ((siglen) * BITS_PER_BYTE)
      41             : 
      42             : typedef char *BITVECP;
      43             : 
      44             : #define LOOPBYTE(siglen) \
      45             :             for (i = 0; i < siglen; i++)
      46             : 
      47             : #define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
      48             : #define GETBITBYTE(x,i) ( ((char)(x)) >> (i) & 0x01 )
      49             : #define CLRBIT(x,i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )
      50             : #define SETBIT(x,i)   GETBYTE(x,i) |=  ( 0x01 << ( (i) % BITS_PER_BYTE ) )
      51             : #define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )
      52             : 
      53             : #define HASHVAL(val, siglen) (((unsigned int)(val)) % SIGLENBIT(siglen))
      54             : #define HASH(sign, val, siglen) SETBIT((sign), HASHVAL(val, siglen))
      55             : 
      56             : #define GETENTRY(vec,pos) ((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))
      57             : 
      58             : /*
      59             :  * type of GiST index key
      60             :  */
      61             : 
      62             : typedef struct
      63             : {
      64             :     int32       vl_len_;        /* varlena header (do not touch directly!) */
      65             :     int32       flag;
      66             :     char        data[FLEXIBLE_ARRAY_MEMBER];
      67             : } SignTSVector;
      68             : 
      69             : #define ARRKEY      0x01
      70             : #define SIGNKEY     0x02
      71             : #define ALLISTRUE   0x04
      72             : 
      73             : #define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
      74             : #define ISSIGNKEY(x)    ( ((SignTSVector*)(x))->flag & SIGNKEY )
      75             : #define ISALLTRUE(x)    ( ((SignTSVector*)(x))->flag & ALLISTRUE )
      76             : 
      77             : #define GTHDRSIZE   ( VARHDRSZ + sizeof(int32) )
      78             : #define CALCGTSIZE(flag, len) ( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int32)) : (((flag) & ALLISTRUE) ? 0 : (len)) ) )
      79             : 
      80             : #define GETSIGN(x)  ( (BITVECP)( (char*)(x)+GTHDRSIZE ) )
      81             : #define GETSIGLEN(x)( VARSIZE(x) - GTHDRSIZE )
      82             : #define GETARR(x)   ( (int32*)( (char*)(x)+GTHDRSIZE ) )
      83             : #define ARRNELEM(x) ( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int32) )
      84             : 
      85             : static int32 sizebitvec(BITVECP sign, int siglen);
      86             : 
      87             : Datum
      88           0 : gtsvectorin(PG_FUNCTION_ARGS)
      89             : {
      90           0 :     ereport(ERROR,
      91             :             (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
      92             :              errmsg("gtsvector_in not implemented")));
      93             :     PG_RETURN_DATUM(0);
      94             : }
      95             : 
      96             : #define SINGOUTSTR  "%d true bits, %d false bits"
      97             : #define ARROUTSTR   "%d unique words"
      98             : #define EXTRALEN    ( 2*13 )
      99             : 
     100             : static int  outbuf_maxlen = 0;
     101             : 
     102             : Datum
     103           0 : gtsvectorout(PG_FUNCTION_ARGS)
     104             : {
     105           0 :     SignTSVector *key = (SignTSVector *) PG_DETOAST_DATUM(PG_GETARG_POINTER(0));
     106             :     char       *outbuf;
     107             : 
     108           0 :     if (outbuf_maxlen == 0)
     109           0 :         outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
     110           0 :     outbuf = palloc(outbuf_maxlen);
     111             : 
     112           0 :     if (ISARRKEY(key))
     113           0 :         sprintf(outbuf, ARROUTSTR, (int) ARRNELEM(key));
     114             :     else
     115             :     {
     116           0 :         int         siglen = GETSIGLEN(key);
     117           0 :         int         cnttrue = (ISALLTRUE(key)) ? SIGLENBIT(siglen) : sizebitvec(GETSIGN(key), siglen);
     118             : 
     119           0 :         sprintf(outbuf, SINGOUTSTR, cnttrue, (int) SIGLENBIT(siglen) - cnttrue);
     120             :     }
     121             : 
     122           0 :     PG_FREE_IF_COPY(key, 0);
     123           0 :     PG_RETURN_POINTER(outbuf);
     124             : }
     125             : 
     126             : static int
     127     2417424 : compareint(const void *va, const void *vb)
     128             : {
     129     2417424 :     int32       a = *((const int32 *) va);
     130     2417424 :     int32       b = *((const int32 *) vb);
     131             : 
     132     2417424 :     if (a == b)
     133           0 :         return 0;
     134     2417424 :     return (a > b) ? 1 : -1;
     135             : }
     136             : 
     137             : static void
     138       49784 : makesign(BITVECP sign, SignTSVector *a, int siglen)
     139             : {
     140             :     int32       k,
     141       49784 :                 len = ARRNELEM(a);
     142       49784 :     int32      *ptr = GETARR(a);
     143             : 
     144       49784 :     MemSet((void *) sign, 0, siglen);
     145     2787854 :     for (k = 0; k < len; k++)
     146     2738070 :         HASH(sign, ptr[k], siglen);
     147       49784 : }
     148             : 
     149             : static SignTSVector *
     150       12968 : gtsvector_alloc(int flag, int len, BITVECP sign)
     151             : {
     152       12968 :     int         size = CALCGTSIZE(flag, len);
     153       12968 :     SignTSVector *res = palloc(size);
     154             : 
     155       12968 :     SET_VARSIZE(res, size);
     156       12968 :     res->flag = flag;
     157             : 
     158       12968 :     if ((flag & (SIGNKEY | ALLISTRUE)) == SIGNKEY && sign)
     159         540 :         memcpy(GETSIGN(res), sign, len);
     160             : 
     161       12968 :     return res;
     162             : }
     163             : 
     164             : 
     165             : Datum
     166       10446 : gtsvector_compress(PG_FUNCTION_ARGS)
     167             : {
     168       10446 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     169       10446 :     int         siglen = GET_SIGLEN();
     170       10446 :     GISTENTRY  *retval = entry;
     171             : 
     172       10446 :     if (entry->leafkey)
     173             :     {                           /* tsvector */
     174        6096 :         TSVector    val = DatumGetTSVector(entry->key);
     175        6096 :         SignTSVector *res = gtsvector_alloc(ARRKEY, val->size, NULL);
     176             :         int32       len;
     177             :         int32      *arr;
     178        6096 :         WordEntry  *ptr = ARRPTR(val);
     179        6096 :         char       *words = STRPTR(val);
     180             : 
     181        6096 :         arr = GETARR(res);
     182        6096 :         len = val->size;
     183      351696 :         while (len--)
     184             :         {
     185             :             pg_crc32    c;
     186             : 
     187      345600 :             INIT_LEGACY_CRC32(c);
     188     1036800 :             COMP_LEGACY_CRC32(c, words + ptr->pos, ptr->len);
     189      345600 :             FIN_LEGACY_CRC32(c);
     190             : 
     191      345600 :             *arr = *(int32 *) &c;
     192      345600 :             arr++;
     193      345600 :             ptr++;
     194             :         }
     195             : 
     196        6096 :         qsort(GETARR(res), val->size, sizeof(int), compareint);
     197        6096 :         len = qunique(GETARR(res), val->size, sizeof(int), compareint);
     198        6096 :         if (len != val->size)
     199             :         {
     200             :             /*
     201             :              * there is a collision of hash-function; len is always less than
     202             :              * val->size
     203             :              */
     204           0 :             len = CALCGTSIZE(ARRKEY, len);
     205           0 :             res = (SignTSVector *) repalloc((void *) res, len);
     206           0 :             SET_VARSIZE(res, len);
     207             :         }
     208             : 
     209             :         /* make signature, if array is too long */
     210        6096 :         if (VARSIZE(res) > TOAST_INDEX_TARGET)
     211             :         {
     212           0 :             SignTSVector *ressign = gtsvector_alloc(SIGNKEY, siglen, NULL);
     213             : 
     214           0 :             makesign(GETSIGN(ressign), res, siglen);
     215           0 :             res = ressign;
     216             :         }
     217             : 
     218        6096 :         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
     219        6096 :         gistentryinit(*retval, PointerGetDatum(res),
     220             :                       entry->rel, entry->page,
     221             :                       entry->offset, false);
     222             :     }
     223        4350 :     else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
     224        4350 :              !ISALLTRUE(DatumGetPointer(entry->key)))
     225             :     {
     226             :         int32       i;
     227             :         SignTSVector *res;
     228        4350 :         BITVECP     sign = GETSIGN(DatumGetPointer(entry->key));
     229             : 
     230        4602 :         LOOPBYTE(siglen)
     231             :         {
     232        4350 :             if ((sign[i] & 0xff) != 0xff)
     233        4098 :                 PG_RETURN_POINTER(retval);
     234             :         }
     235             : 
     236         252 :         res = gtsvector_alloc(SIGNKEY | ALLISTRUE, siglen, sign);
     237         252 :         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
     238         252 :         gistentryinit(*retval, PointerGetDatum(res),
     239             :                       entry->rel, entry->page,
     240             :                       entry->offset, false);
     241             :     }
     242        6348 :     PG_RETURN_POINTER(retval);
     243             : }
     244             : 
     245             : Datum
     246      270886 : gtsvector_decompress(PG_FUNCTION_ARGS)
     247             : {
     248             :     /*
     249             :      * We need to detoast the stored value, because the other gtsvector
     250             :      * support functions don't cope with toasted values.
     251             :      */
     252      270886 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     253      270886 :     SignTSVector *key = (SignTSVector *) PG_DETOAST_DATUM(entry->key);
     254             : 
     255      270886 :     if (key != (SignTSVector *) DatumGetPointer(entry->key))
     256             :     {
     257           0 :         GISTENTRY  *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
     258             : 
     259           0 :         gistentryinit(*retval, PointerGetDatum(key),
     260             :                       entry->rel, entry->page,
     261             :                       entry->offset, false);
     262             : 
     263           0 :         PG_RETURN_POINTER(retval);
     264             :     }
     265             : 
     266      270886 :     PG_RETURN_POINTER(entry);
     267             : }
     268             : 
     269             : typedef struct
     270             : {
     271             :     int32      *arrb;
     272             :     int32      *arre;
     273             : } CHKVAL;
     274             : 
     275             : /*
     276             :  * TS_execute callback for matching a tsquery operand to GIST leaf-page data
     277             :  */
     278             : static TSTernaryValue
     279      279732 : checkcondition_arr(void *checkval, QueryOperand *val, ExecPhraseData *data)
     280             : {
     281      279732 :     int32      *StopLow = ((CHKVAL *) checkval)->arrb;
     282      279732 :     int32      *StopHigh = ((CHKVAL *) checkval)->arre;
     283             :     int32      *StopMiddle;
     284             : 
     285             :     /* Loop invariant: StopLow <= val < StopHigh */
     286             : 
     287             :     /*
     288             :      * we are not able to find a prefix by hash value
     289             :      */
     290      279732 :     if (val->prefix)
     291       16256 :         return TS_MAYBE;
     292             : 
     293     1694420 :     while (StopLow < StopHigh)
     294             :     {
     295     1463348 :         StopMiddle = StopLow + (StopHigh - StopLow) / 2;
     296     1463348 :         if (*StopMiddle == val->valcrc)
     297       32404 :             return TS_MAYBE;
     298     1430944 :         else if (*StopMiddle < val->valcrc)
     299      608778 :             StopLow = StopMiddle + 1;
     300             :         else
     301      822166 :             StopHigh = StopMiddle;
     302             :     }
     303             : 
     304      231072 :     return TS_NO;
     305             : }
     306             : 
     307             : /*
     308             :  * TS_execute callback for matching a tsquery operand to GIST non-leaf data
     309             :  */
     310             : static TSTernaryValue
     311       10272 : checkcondition_bit(void *checkval, QueryOperand *val, ExecPhraseData *data)
     312             : {
     313       10272 :     void       *key = (SignTSVector *) checkval;
     314             : 
     315             :     /*
     316             :      * we are not able to find a prefix in signature tree
     317             :      */
     318       10272 :     if (val->prefix)
     319         456 :         return TS_MAYBE;
     320             : 
     321        9816 :     if (GETBIT(GETSIGN(key), HASHVAL(val->valcrc, GETSIGLEN(key))))
     322        9392 :         return TS_MAYBE;
     323             :     else
     324         424 :         return TS_NO;
     325             : }
     326             : 
     327             : Datum
     328      202802 : gtsvector_consistent(PG_FUNCTION_ARGS)
     329             : {
     330      202802 :     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
     331      202802 :     TSQuery     query = PG_GETARG_TSQUERY(1);
     332             : 
     333             :     /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
     334             :     /* Oid      subtype = PG_GETARG_OID(3); */
     335      202802 :     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
     336      202802 :     SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
     337             : 
     338             :     /* All cases served by this function are inexact */
     339      202802 :     *recheck = true;
     340             : 
     341      202802 :     if (!query->size)
     342           0 :         PG_RETURN_BOOL(false);
     343             : 
     344      202802 :     if (ISSIGNKEY(key))
     345             :     {
     346        8806 :         if (ISALLTRUE(key))
     347        3250 :             PG_RETURN_BOOL(true);
     348             : 
     349        5556 :         PG_RETURN_BOOL(TS_execute(GETQUERY(query),
     350             :                                   key,
     351             :                                   TS_EXEC_PHRASE_NO_POS,
     352             :                                   checkcondition_bit));
     353             :     }
     354             :     else
     355             :     {                           /* only leaf pages */
     356             :         CHKVAL      chkval;
     357             : 
     358      193996 :         chkval.arrb = GETARR(key);
     359      193996 :         chkval.arre = chkval.arrb + ARRNELEM(key);
     360      193996 :         PG_RETURN_BOOL(TS_execute(GETQUERY(query),
     361             :                                   (void *) &chkval,
     362             :                                   TS_EXEC_PHRASE_NO_POS,
     363             :                                   checkcondition_arr));
     364             :     }
     365             : }
     366             : 
     367             : static int32
     368       10280 : unionkey(BITVECP sbase, SignTSVector *add, int siglen)
     369             : {
     370             :     int32       i;
     371             : 
     372       10280 :     if (ISSIGNKEY(add))
     373             :     {
     374        6080 :         BITVECP     sadd = GETSIGN(add);
     375             : 
     376        6080 :         if (ISALLTRUE(add))
     377        1880 :             return 1;
     378             : 
     379             :         Assert(GETSIGLEN(add) == siglen);
     380             : 
     381     1360200 :         LOOPBYTE(siglen)
     382     1356000 :             sbase[i] |= sadd[i];
     383             :     }
     384             :     else
     385             :     {
     386        4200 :         int32      *ptr = GETARR(add);
     387             : 
     388      246848 :         for (i = 0; i < ARRNELEM(add); i++)
     389      242648 :             HASH(sbase, ptr[i], siglen);
     390             :     }
     391        8400 :     return 0;
     392             : }
     393             : 
     394             : 
     395             : Datum
     396        6080 : gtsvector_union(PG_FUNCTION_ARGS)
     397             : {
     398        6080 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     399        6080 :     int        *size = (int *) PG_GETARG_POINTER(1);
     400        6080 :     int         siglen = GET_SIGLEN();
     401        6080 :     SignTSVector *result = gtsvector_alloc(SIGNKEY, siglen, NULL);
     402        6080 :     BITVECP     base = GETSIGN(result);
     403             :     int32       i;
     404             : 
     405        6080 :     memset(base, 0, siglen);
     406             : 
     407       14480 :     for (i = 0; i < entryvec->n; i++)
     408             :     {
     409       10280 :         if (unionkey(base, GETENTRY(entryvec, i), siglen))
     410             :         {
     411        1880 :             result->flag |= ALLISTRUE;
     412        1880 :             SET_VARSIZE(result, CALCGTSIZE(result->flag, siglen));
     413        1880 :             break;
     414             :         }
     415             :     }
     416             : 
     417        6080 :     *size = VARSIZE(result);
     418             : 
     419        6080 :     PG_RETURN_POINTER(result);
     420             : }
     421             : 
     422             : Datum
     423        6080 : gtsvector_same(PG_FUNCTION_ARGS)
     424             : {
     425        6080 :     SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
     426        6080 :     SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
     427        6080 :     bool       *result = (bool *) PG_GETARG_POINTER(2);
     428        6080 :     int         siglen = GET_SIGLEN();
     429             : 
     430        6080 :     if (ISSIGNKEY(a))
     431             :     {                           /* then b also ISSIGNKEY */
     432        6080 :         if (ISALLTRUE(a) && ISALLTRUE(b))
     433        1880 :             *result = true;
     434        4200 :         else if (ISALLTRUE(a))
     435           0 :             *result = false;
     436        4200 :         else if (ISALLTRUE(b))
     437           0 :             *result = false;
     438             :         else
     439             :         {
     440             :             int32       i;
     441        4200 :             BITVECP     sa = GETSIGN(a),
     442        4200 :                         sb = GETSIGN(b);
     443             : 
     444             :             Assert(GETSIGLEN(a) == siglen && GETSIGLEN(b) == siglen);
     445             : 
     446        4200 :             *result = true;
     447      334126 :             LOOPBYTE(siglen)
     448             :             {
     449      333736 :                 if (sa[i] != sb[i])
     450             :                 {
     451        3810 :                     *result = false;
     452        3810 :                     break;
     453             :                 }
     454             :             }
     455             :         }
     456             :     }
     457             :     else
     458             :     {                           /* a and b ISARRKEY */
     459           0 :         int32       lena = ARRNELEM(a),
     460           0 :                     lenb = ARRNELEM(b);
     461             : 
     462           0 :         if (lena != lenb)
     463           0 :             *result = false;
     464             :         else
     465             :         {
     466           0 :             int32      *ptra = GETARR(a),
     467           0 :                        *ptrb = GETARR(b);
     468             :             int32       i;
     469             : 
     470           0 :             *result = true;
     471           0 :             for (i = 0; i < lena; i++)
     472           0 :                 if (ptra[i] != ptrb[i])
     473             :                 {
     474           0 :                     *result = false;
     475           0 :                     break;
     476             :                 }
     477             :         }
     478             :     }
     479             : 
     480        6080 :     PG_RETURN_POINTER(result);
     481             : }
     482             : 
     483             : static int32
     484        7006 : sizebitvec(BITVECP sign, int siglen)
     485             : {
     486        7006 :     return pg_popcount(sign, siglen);
     487             : }
     488             : 
     489             : static int
     490      186516 : hemdistsign(BITVECP a, BITVECP b, int siglen)
     491             : {
     492             :     int         i,
     493             :                 diff,
     494      186516 :                 dist = 0;
     495             : 
     496    34559940 :     LOOPBYTE(siglen)
     497             :     {
     498    34373424 :         diff = (unsigned char) (a[i] ^ b[i]);
     499             :         /* Using the popcount functions here isn't likely to win */
     500    34373424 :         dist += pg_number_of_ones[diff];
     501             :     }
     502      186516 :     return dist;
     503             : }
     504             : 
     505             : static int
     506           0 : hemdist(SignTSVector *a, SignTSVector *b)
     507             : {
     508           0 :     int         siglena = GETSIGLEN(a);
     509           0 :     int         siglenb = GETSIGLEN(b);
     510             : 
     511           0 :     if (ISALLTRUE(a))
     512             :     {
     513           0 :         if (ISALLTRUE(b))
     514           0 :             return 0;
     515             :         else
     516           0 :             return SIGLENBIT(siglenb) - sizebitvec(GETSIGN(b), siglenb);
     517             :     }
     518           0 :     else if (ISALLTRUE(b))
     519           0 :         return SIGLENBIT(siglena) - sizebitvec(GETSIGN(a), siglena);
     520             : 
     521             :     Assert(siglena == siglenb);
     522             : 
     523           0 :     return hemdistsign(GETSIGN(a), GETSIGN(b), siglena);
     524             : }
     525             : 
     526             : Datum
     527       41456 : gtsvector_penalty(PG_FUNCTION_ARGS)
     528             : {
     529       41456 :     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
     530       41456 :     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
     531       41456 :     float      *penalty = (float *) PG_GETARG_POINTER(2);
     532       41456 :     int         siglen = GET_SIGLEN();
     533       41456 :     SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
     534       41456 :     SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
     535       41456 :     BITVECP     orig = GETSIGN(origval);
     536             : 
     537       41456 :     *penalty = 0.0;
     538             : 
     539       41456 :     if (ISARRKEY(newval))
     540             :     {
     541       41456 :         BITVECP     sign = palloc(siglen);
     542             : 
     543       41456 :         makesign(sign, newval, siglen);
     544             : 
     545       41456 :         if (ISALLTRUE(origval))
     546             :         {
     547        7006 :             int         siglenbit = SIGLENBIT(siglen);
     548             : 
     549        7006 :             *penalty =
     550        7006 :                 (float) (siglenbit - sizebitvec(sign, siglen)) /
     551        7006 :                 (float) (siglenbit + 1);
     552             :         }
     553             :         else
     554       34450 :             *penalty = hemdistsign(sign, orig, siglen);
     555             : 
     556       41456 :         pfree(sign);
     557             :     }
     558             :     else
     559           0 :         *penalty = hemdist(origval, newval);
     560       41456 :     PG_RETURN_POINTER(penalty);
     561             : }
     562             : 
     563             : typedef struct
     564             : {
     565             :     bool        allistrue;
     566             :     BITVECP     sign;
     567             : } CACHESIGN;
     568             : 
     569             : static void
     570        8388 : fillcache(CACHESIGN *item, SignTSVector *key, int siglen)
     571             : {
     572        8388 :     item->allistrue = false;
     573        8388 :     if (ISARRKEY(key))
     574        8328 :         makesign(item->sign, key, siglen);
     575          60 :     else if (ISALLTRUE(key))
     576           0 :         item->allistrue = true;
     577             :     else
     578          60 :         memcpy((void *) item->sign, (void *) GETSIGN(key), siglen);
     579        8388 : }
     580             : 
     581             : #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
     582             : typedef struct
     583             : {
     584             :     OffsetNumber pos;
     585             :     int32       cost;
     586             : } SPLITCOST;
     587             : 
     588             : static int
     589       20950 : comparecost(const void *va, const void *vb)
     590             : {
     591       20950 :     const SPLITCOST *a = (const SPLITCOST *) va;
     592       20950 :     const SPLITCOST *b = (const SPLITCOST *) vb;
     593             : 
     594       20950 :     if (a->cost == b->cost)
     595        9028 :         return 0;
     596             :     else
     597       11922 :         return (a->cost > b->cost) ? 1 : -1;
     598             : }
     599             : 
     600             : 
     601             : static int
     602      136370 : hemdistcache(CACHESIGN *a, CACHESIGN *b, int siglen)
     603             : {
     604      136370 :     if (a->allistrue)
     605             :     {
     606           0 :         if (b->allistrue)
     607           0 :             return 0;
     608             :         else
     609           0 :             return SIGLENBIT(siglen) - sizebitvec(b->sign, siglen);
     610             :     }
     611      136370 :     else if (b->allistrue)
     612           0 :         return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
     613             : 
     614      136370 :     return hemdistsign(a->sign, b->sign, siglen);
     615             : }
     616             : 
     617             : Datum
     618         270 : gtsvector_picksplit(PG_FUNCTION_ARGS)
     619             : {
     620         270 :     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
     621         270 :     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
     622         270 :     int         siglen = GET_SIGLEN();
     623             :     OffsetNumber k,
     624             :                 j;
     625             :     SignTSVector *datum_l,
     626             :                *datum_r;
     627             :     BITVECP     union_l,
     628             :                 union_r;
     629             :     int32       size_alpha,
     630             :                 size_beta;
     631             :     int32       size_waste,
     632         270 :                 waste = -1;
     633             :     int32       nbytes;
     634         270 :     OffsetNumber seed_1 = 0,
     635         270 :                 seed_2 = 0;
     636             :     OffsetNumber *left,
     637             :                *right;
     638             :     OffsetNumber maxoff;
     639             :     BITVECP     ptr;
     640             :     int         i;
     641             :     CACHESIGN  *cache;
     642             :     char       *cache_sign;
     643             :     SPLITCOST  *costvector;
     644             : 
     645         270 :     maxoff = entryvec->n - 2;
     646         270 :     nbytes = (maxoff + 2) * sizeof(OffsetNumber);
     647         270 :     v->spl_left = (OffsetNumber *) palloc(nbytes);
     648         270 :     v->spl_right = (OffsetNumber *) palloc(nbytes);
     649             : 
     650         270 :     cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
     651         270 :     cache_sign = palloc(siglen * (maxoff + 2));
     652             : 
     653        8928 :     for (j = 0; j < maxoff + 2; j++)
     654        8658 :         cache[j].sign = &cache_sign[siglen * j];
     655             : 
     656         270 :     fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber),
     657             :               siglen);
     658             : 
     659        8118 :     for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
     660             :     {
     661      127442 :         for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
     662             :         {
     663      119594 :             if (k == FirstOffsetNumber)
     664        7848 :                 fillcache(&cache[j], GETENTRY(entryvec, j), siglen);
     665             : 
     666      119594 :             size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
     667      119594 :             if (size_waste > waste)
     668             :             {
     669        1630 :                 waste = size_waste;
     670        1630 :                 seed_1 = k;
     671        1630 :                 seed_2 = j;
     672             :             }
     673             :         }
     674             :     }
     675             : 
     676         270 :     left = v->spl_left;
     677         270 :     v->spl_nleft = 0;
     678         270 :     right = v->spl_right;
     679         270 :     v->spl_nright = 0;
     680             : 
     681         270 :     if (seed_1 == 0 || seed_2 == 0)
     682             :     {
     683           0 :         seed_1 = 1;
     684           0 :         seed_2 = 2;
     685             :     }
     686             : 
     687             :     /* form initial .. */
     688         270 :     datum_l = gtsvector_alloc(SIGNKEY | (cache[seed_1].allistrue ? ALLISTRUE : 0),
     689         270 :                               siglen, cache[seed_1].sign);
     690         270 :     datum_r = gtsvector_alloc(SIGNKEY | (cache[seed_2].allistrue ? ALLISTRUE : 0),
     691         270 :                               siglen, cache[seed_2].sign);
     692         270 :     union_l = GETSIGN(datum_l);
     693         270 :     union_r = GETSIGN(datum_r);
     694         270 :     maxoff = OffsetNumberNext(maxoff);
     695         270 :     fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff), siglen);
     696             :     /* sort before ... */
     697         270 :     costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
     698        8658 :     for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
     699             :     {
     700        8388 :         costvector[j - 1].pos = j;
     701        8388 :         size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
     702        8388 :         size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
     703        8388 :         costvector[j - 1].cost = Abs(size_alpha - size_beta);
     704             :     }
     705         270 :     qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
     706             : 
     707        8658 :     for (k = 0; k < maxoff; k++)
     708             :     {
     709        8388 :         j = costvector[k].pos;
     710        8388 :         if (j == seed_1)
     711             :         {
     712         270 :             *left++ = j;
     713         270 :             v->spl_nleft++;
     714         270 :             continue;
     715             :         }
     716        8118 :         else if (j == seed_2)
     717             :         {
     718         270 :             *right++ = j;
     719         270 :             v->spl_nright++;
     720         270 :             continue;
     721             :         }
     722             : 
     723        7848 :         if (ISALLTRUE(datum_l) || cache[j].allistrue)
     724             :         {
     725           0 :             if (ISALLTRUE(datum_l) && cache[j].allistrue)
     726           0 :                 size_alpha = 0;
     727             :             else
     728           0 :                 size_alpha = SIGLENBIT(siglen) -
     729           0 :                     sizebitvec((cache[j].allistrue) ?
     730             :                                GETSIGN(datum_l) :
     731           0 :                                GETSIGN(cache[j].sign),
     732             :                                siglen);
     733             :         }
     734             :         else
     735        7848 :             size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
     736             : 
     737        7848 :         if (ISALLTRUE(datum_r) || cache[j].allistrue)
     738             :         {
     739           0 :             if (ISALLTRUE(datum_r) && cache[j].allistrue)
     740           0 :                 size_beta = 0;
     741             :             else
     742           0 :                 size_beta = SIGLENBIT(siglen) -
     743           0 :                     sizebitvec((cache[j].allistrue) ?
     744             :                                GETSIGN(datum_r) :
     745           0 :                                GETSIGN(cache[j].sign),
     746             :                                siglen);
     747             :         }
     748             :         else
     749        7848 :             size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
     750             : 
     751        7848 :         if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
     752             :         {
     753        3880 :             if (ISALLTRUE(datum_l) || cache[j].allistrue)
     754             :             {
     755           0 :                 if (!ISALLTRUE(datum_l))
     756           0 :                     MemSet((void *) GETSIGN(datum_l), 0xff, siglen);
     757             :             }
     758             :             else
     759             :             {
     760        3880 :                 ptr = cache[j].sign;
     761      636734 :                 LOOPBYTE(siglen)
     762      632854 :                     union_l[i] |= ptr[i];
     763             :             }
     764        3880 :             *left++ = j;
     765        3880 :             v->spl_nleft++;
     766             :         }
     767             :         else
     768             :         {
     769        3968 :             if (ISALLTRUE(datum_r) || cache[j].allistrue)
     770             :             {
     771           0 :                 if (!ISALLTRUE(datum_r))
     772           0 :                     MemSet((void *) GETSIGN(datum_r), 0xff, siglen);
     773             :             }
     774             :             else
     775             :             {
     776        3968 :                 ptr = cache[j].sign;
     777      650926 :                 LOOPBYTE(siglen)
     778      646958 :                     union_r[i] |= ptr[i];
     779             :             }
     780        3968 :             *right++ = j;
     781        3968 :             v->spl_nright++;
     782             :         }
     783             :     }
     784             : 
     785         270 :     *right = *left = FirstOffsetNumber;
     786         270 :     v->spl_ldatum = PointerGetDatum(datum_l);
     787         270 :     v->spl_rdatum = PointerGetDatum(datum_r);
     788             : 
     789         270 :     PG_RETURN_POINTER(v);
     790             : }
     791             : 
     792             : /*
     793             :  * Formerly, gtsvector_consistent was declared in pg_proc.h with arguments
     794             :  * that did not match the documented conventions for GiST support functions.
     795             :  * We fixed that, but we still need a pg_proc entry with the old signature
     796             :  * to support reloading pre-9.6 contrib/tsearch2 opclass declarations.
     797             :  * This compatibility function should go away eventually.
     798             :  */
     799             : Datum
     800           0 : gtsvector_consistent_oldsig(PG_FUNCTION_ARGS)
     801             : {
     802           0 :     return gtsvector_consistent(fcinfo);
     803             : }
     804             : 
     805             : Datum
     806          76 : gtsvector_options(PG_FUNCTION_ARGS)
     807             : {
     808          76 :     local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
     809             : 
     810          76 :     init_local_reloptions(relopts, sizeof(GistTsVectorOptions));
     811          76 :     add_local_int_reloption(relopts, "siglen", "signature length",
     812             :                             SIGLEN_DEFAULT, 1, SIGLEN_MAX,
     813             :                             offsetof(GistTsVectorOptions, siglen));
     814             : 
     815          76 :     PG_RETURN_VOID();
     816             : }

Generated by: LCOV version 1.13