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

Generated by: LCOV version 1.13