tsgistidx.c File Reference

#include "postgres.h"
#include "access/gist.h"
#include "access/heaptoast.h"
#include "access/reloptions.h"
#include "lib/qunique.h"
#include "port/pg_bitutils.h"
#include "tsearch/ts_utils.h"
#include "utils/builtins.h"
#include "utils/pg_crc.h"

Include dependency graph for tsgistidx.c:

Go to the source code of this file.

Data Structures
struct	GistTsVectorOptions
struct	SignTSVector
struct	CHKVAL
struct	CACHESIGN
struct	SPLITCOST

Macros
#define	SIGLEN_DEFAULT   (31 * 4)
#define	SIGLEN_MAX   GISTMaxIndexKeySize
#define	GET_SIGLEN()
#define	SIGLENBIT(siglen)   ((siglen) * BITS_PER_BYTE)
#define	LOOPBYTE(siglen)    for (i = 0; i < siglen; i++)
#define	GETBYTE(x, i)   ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
#define	GETBITBYTE(x, i)   ( ((char)(x)) >> (i) & 0x01 )
#define	CLRBIT(x, i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )
#define	SETBIT(x, i)   GETBYTE(x,i) |= ( 0x01 << ( (i) % BITS_PER_BYTE ) )
#define	GETBIT(x, i)   ( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )
#define	HASHVAL(val, siglen)   (((unsigned int)(val)) % SIGLENBIT(siglen))
#define	HASH(sign, val, siglen)   SETBIT((sign), HASHVAL(val, siglen))
#define	GETENTRY(vec, pos)   ((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))
#define	ARRKEY   0x01
#define	SIGNKEY   0x02
#define	ALLISTRUE   0x04
#define	ISARRKEY(x)   ( ((SignTSVector*)(x))->flag & ARRKEY )
#define	ISSIGNKEY(x)   ( ((SignTSVector*)(x))->flag & SIGNKEY )
#define	ISALLTRUE(x)   ( ((SignTSVector*)(x))->flag & ALLISTRUE )
#define	GTHDRSIZE   ( VARHDRSZ + sizeof(int32) )
#define	CALCGTSIZE(flag, len)   ( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int32)) : (((flag) & ALLISTRUE) ? 0 : (len)) ) )
#define	GETSIGN(x)   ( (BITVECP)( (char*)(x)+GTHDRSIZE ) )
#define	GETSIGLEN(x)   ( VARSIZE(x) - GTHDRSIZE )
#define	GETARR(x)   ( (int32*)( (char*)(x)+GTHDRSIZE ) )
#define	ARRNELEM(x)   ( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int32) )
#define	SINGOUTSTR   "%d true bits, %d false bits"
#define	ARROUTSTR   "%d unique words"
#define	EXTRALEN   ( 2*13 )
#define	WISH_F(a, b, c)   (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )

Typedefs
typedef char *	BITVECP

Functions
static int32	sizebitvec (BITVECP sign, int siglen)
Datum	gtsvectorin (PG_FUNCTION_ARGS)
Datum	gtsvectorout (PG_FUNCTION_ARGS)
static int	compareint (const void *va, const void *vb)
static void	makesign (BITVECP sign, SignTSVector *a, int siglen)
static SignTSVector *	gtsvector_alloc (int flag, int len, BITVECP sign)
Datum	gtsvector_compress (PG_FUNCTION_ARGS)
Datum	gtsvector_decompress (PG_FUNCTION_ARGS)
static TSTernaryValue	checkcondition_arr (void *checkval, QueryOperand *val, ExecPhraseData *data)
static TSTernaryValue	checkcondition_bit (void *checkval, QueryOperand *val, ExecPhraseData *data)
Datum	gtsvector_consistent (PG_FUNCTION_ARGS)
static int32	unionkey (BITVECP sbase, SignTSVector *add, int siglen)
Datum	gtsvector_union (PG_FUNCTION_ARGS)
Datum	gtsvector_same (PG_FUNCTION_ARGS)
static int	hemdistsign (BITVECP a, BITVECP b, int siglen)
static int	hemdist (SignTSVector *a, SignTSVector *b)
Datum	gtsvector_penalty (PG_FUNCTION_ARGS)
static void	fillcache (CACHESIGN *item, SignTSVector *key, int siglen)
static int	comparecost (const void *va, const void *vb)
static int	hemdistcache (CACHESIGN *a, CACHESIGN *b, int siglen)
Datum	gtsvector_picksplit (PG_FUNCTION_ARGS)
Datum	gtsvector_consistent_oldsig (PG_FUNCTION_ARGS)
Datum	gtsvector_options (PG_FUNCTION_ARGS)

Variables
static int	outbuf_maxlen = 0

Macro Definition Documentation

ALLISTRUE

#define ALLISTRUE   0x04

Definition at line 71 of file tsgistidx.c.

ARRKEY

#define ARRKEY   0x01

Definition at line 69 of file tsgistidx.c.

ARRNELEM

#define ARRNELEM

(

x

)

( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int32) )

Definition at line 83 of file tsgistidx.c.

ARROUTSTR

#define ARROUTSTR   "%d unique words"

Definition at line 99 of file tsgistidx.c.

CALCGTSIZE

#define CALCGTSIZE	(		flag,
			len
	)		( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int32)) : (((flag) & ALLISTRUE) ? 0 : (len)) ) )

Definition at line 78 of file tsgistidx.c.

CLRBIT

#define CLRBIT	(		x,
			i
	)		GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )

Definition at line 49 of file tsgistidx.c.

EXTRALEN

#define EXTRALEN   ( 2*13 )

Definition at line 100 of file tsgistidx.c.

GET_SIGLEN

#define GET_SIGLEN

(

)

Value:

                         (PG_HAS_OPCLASS_OPTIONS() ? \
                         ((GistTsVectorOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
                         SIGLEN_DEFAULT)

Definition at line 36 of file tsgistidx.c.

GETARR

#define GETARR

(

x

)

( (int32*)( (char*)(x)+GTHDRSIZE ) )

Definition at line 82 of file tsgistidx.c.

GETBIT

#define GETBIT	(		x,
			i
	)		( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )

Definition at line 51 of file tsgistidx.c.

GETBITBYTE

#define GETBITBYTE	(		x,
			i
	)		( ((char)(x)) >> (i) & 0x01 )

Definition at line 48 of file tsgistidx.c.

GETBYTE

#define GETBYTE	(		x,
			i
	)		( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )

Definition at line 47 of file tsgistidx.c.

GETENTRY

#define GETENTRY	(		vec,
			pos
	)		((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))

Definition at line 56 of file tsgistidx.c.

GETSIGLEN

#define GETSIGLEN

(

x

)

( VARSIZE(x) - GTHDRSIZE )

Definition at line 81 of file tsgistidx.c.

GETSIGN

#define GETSIGN

(

x

)

( (BITVECP)( (char*)(x)+GTHDRSIZE ) )

Definition at line 80 of file tsgistidx.c.

GTHDRSIZE

#define GTHDRSIZE   ( VARHDRSZ + sizeof(int32) )

Definition at line 77 of file tsgistidx.c.

HASH

#define HASH	(		sign,
			val,
			siglen
	)		SETBIT((sign), HASHVAL(val, siglen))

Definition at line 54 of file tsgistidx.c.

HASHVAL

#define HASHVAL	(		val,
			siglen
	)		(((unsigned int)(val)) % SIGLENBIT(siglen))

Definition at line 53 of file tsgistidx.c.

ISALLTRUE

#define ISALLTRUE

(

x

)

( ((SignTSVector*)(x))->flag & ALLISTRUE )

Definition at line 75 of file tsgistidx.c.

ISARRKEY

#define ISARRKEY

(

x

)

( ((SignTSVector*)(x))->flag & ARRKEY )

Definition at line 73 of file tsgistidx.c.

ISSIGNKEY

#define ISSIGNKEY

(

x

)

( ((SignTSVector*)(x))->flag & SIGNKEY )

Definition at line 74 of file tsgistidx.c.

LOOPBYTE

#define LOOPBYTE

(

siglen

)

for (i = 0; i < siglen; i++)

Definition at line 44 of file tsgistidx.c.

SETBIT

#define SETBIT	(		x,
			i
	)		GETBYTE(x,i) |= ( 0x01 << ( (i) % BITS_PER_BYTE ) )

Definition at line 50 of file tsgistidx.c.

SIGLEN_DEFAULT

#define SIGLEN_DEFAULT   (31 * 4)

Definition at line 34 of file tsgistidx.c.

SIGLEN_MAX

#define SIGLEN_MAX   GISTMaxIndexKeySize

Definition at line 35 of file tsgistidx.c.

SIGLENBIT

#define SIGLENBIT

(

siglen

)

((siglen) * BITS_PER_BYTE)

Definition at line 40 of file tsgistidx.c.

SIGNKEY

#define SIGNKEY   0x02

Definition at line 70 of file tsgistidx.c.

SINGOUTSTR

#define SINGOUTSTR   "%d true bits, %d false bits"

Definition at line 98 of file tsgistidx.c.

WISH_F

#define WISH_F	(		a,
			b,
			c
	)		(double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )

Definition at line 588 of file tsgistidx.c.

Typedef Documentation

BITVECP

typedef char* BITVECP

Definition at line 42 of file tsgistidx.c.

Function Documentation

checkcondition_arr()

static TSTernaryValue checkcondition_arr ( void *  checkval, QueryOperand *  val, ExecPhraseData *  data  )

static

Definition at line 286 of file tsgistidx.c.

{
    int32      *StopLow = ((CHKVAL *) checkval)->arrb;
    int32      *StopHigh = ((CHKVAL *) checkval)->arre;
    int32      *StopMiddle;
 
    /* Loop invariant: StopLow <= val < StopHigh */
 
    /*
     * we are not able to find a prefix by hash value
     */
    if (val->prefix)
        return TS_MAYBE;
 
    while (StopLow < StopHigh)
    {
        StopMiddle = StopLow + (StopHigh - StopLow) / 2;
        if (*StopMiddle == val->valcrc)
            return TS_MAYBE;
        else if (*StopMiddle < val->valcrc)
            StopLow = StopMiddle + 1;
        else
            StopHigh = StopMiddle;
    }
 
    return TS_NO;
}

References TS_MAYBE, TS_NO, and val.

Referenced by gtsvector_consistent().

checkcondition_bit()

static TSTernaryValue checkcondition_bit ( void *  checkval, QueryOperand *  val, ExecPhraseData *  data  )

static

Definition at line 318 of file tsgistidx.c.

{
    void       *key = (SignTSVector *) checkval;
 
    /*
     * we are not able to find a prefix in signature tree
     */
    if (val->prefix)
        return TS_MAYBE;
 
    if (GETBIT(GETSIGN(key), HASHVAL(val->valcrc, GETSIGLEN(key))))
        return TS_MAYBE;
    else
        return TS_NO;
}

References GETBIT, GETSIGLEN, GETSIGN, HASHVAL, sort-test::key, TS_MAYBE, TS_NO, and val.

Referenced by gtsvector_consistent().

comparecost()

static int comparecost ( const void *  va, const void *  vb  )

static

Definition at line 596 of file tsgistidx.c.

{
    const SPLITCOST *a = (const SPLITCOST *) va;
    const SPLITCOST *b = (const SPLITCOST *) vb;
 
    if (a->cost == b->cost)
        return 0;
    else
        return (a->cost > b->cost) ? 1 : -1;
}

References a, and b.

Referenced by gtsvector_picksplit().

compareint()

static int compareint ( const void *  va, const void *  vb  )

static

Definition at line 134 of file tsgistidx.c.

{
    int32       a = *((const int32 *) va);
    int32       b = *((const int32 *) vb);
 
    if (a == b)
        return 0;
    return (a > b) ? 1 : -1;
}

References a, and b.

Referenced by gtsvector_compress().

fillcache()

static void fillcache ( CACHESIGN *  item, SignTSVector *  key, int  siglen  )

static

Definition at line 577 of file tsgistidx.c.

{
    item->allistrue = false;
    if (ISARRKEY(key))
        makesign(item->sign, key, siglen);
    else if (ISALLTRUE(key))
        item->allistrue = true;
    else
        memcpy(item->sign, GETSIGN(key), siglen);
}

References CACHESIGN::allistrue, GETSIGN, ISALLTRUE, ISARRKEY, sort-test::key, makesign(), and CACHESIGN::sign.

Referenced by gtsvector_picksplit().

gtsvector_alloc()

static SignTSVector* gtsvector_alloc ( int  flag, int  len, BITVECP  sign  )

static

Definition at line 157 of file tsgistidx.c.

{
    int         size = CALCGTSIZE(flag, len);
    SignTSVector *res = palloc(size);
 
    SET_VARSIZE(res, size);
    res->flag = flag;
 
    if ((flag & (SIGNKEY | ALLISTRUE)) == SIGNKEY && sign)
        memcpy(GETSIGN(res), sign, len);
 
    return res;
}

References ALLISTRUE, CALCGTSIZE, flag(), GETSIGN, len, palloc(), res, SET_VARSIZE, sign, and SIGNKEY.

Referenced by gtsvector_compress(), gtsvector_picksplit(), and gtsvector_union().

gtsvector_compress()

Datum gtsvector_compress

(

PG_FUNCTION_ARGS

)

Definition at line 173 of file tsgistidx.c.

{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    int         siglen = GET_SIGLEN();
    GISTENTRY  *retval = entry;
 
    if (entry->leafkey)
    {                           /* tsvector */
        TSVector    val = DatumGetTSVector(entry->key);
        SignTSVector *res = gtsvector_alloc(ARRKEY, val->size, NULL);
        int32       len;
        int32      *arr;
        WordEntry  *ptr = ARRPTR(val);
        char       *words = STRPTR(val);
 
        arr = GETARR(res);
        len = val->size;
        while (len--)
        {
            pg_crc32    c;
 
            INIT_LEGACY_CRC32(c);
            COMP_LEGACY_CRC32(c, words + ptr->pos, ptr->len);
            FIN_LEGACY_CRC32(c);
 
            *arr = *(int32 *) &c;
            arr++;
            ptr++;
        }
 
        qsort(GETARR(res), val->size, sizeof(int), compareint);
        len = qunique(GETARR(res), val->size, sizeof(int), compareint);
        if (len != val->size)
        {
            /*
             * there is a collision of hash-function; len is always less than
             * val->size
             */
            len = CALCGTSIZE(ARRKEY, len);
            res = (SignTSVector *) repalloc(res, len);
            SET_VARSIZE(res, len);
        }
 
        /* make signature, if array is too long */
        if (VARSIZE(res) > TOAST_INDEX_TARGET)
        {
            SignTSVector *ressign = gtsvector_alloc(SIGNKEY, siglen, NULL);
 
            makesign(GETSIGN(ressign), res, siglen);
            res = ressign;
        }
 
        retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
        gistentryinit(*retval, PointerGetDatum(res),
                      entry->rel, entry->page,
                      entry->offset, false);
    }
    else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
             !ISALLTRUE(DatumGetPointer(entry->key)))
    {
        int32       i;
        SignTSVector *res;
        BITVECP     sign = GETSIGN(DatumGetPointer(entry->key));
 
        LOOPBYTE(siglen)
        {
            if ((sign[i] & 0xff) != 0xff)
                PG_RETURN_POINTER(retval);
        }
 
        res = gtsvector_alloc(SIGNKEY | ALLISTRUE, siglen, sign);
        retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
        gistentryinit(*retval, PointerGetDatum(res),
                      entry->rel, entry->page,
                      entry->offset, false);
    }
    PG_RETURN_POINTER(retval);
}

References ALLISTRUE, ARRKEY, ARRPTR, CALCGTSIZE, COMP_LEGACY_CRC32, compareint(), DatumGetPointer(), DatumGetTSVector(), FIN_LEGACY_CRC32, GET_SIGLEN, GETARR, GETSIGN, gistentryinit, gtsvector_alloc(), i, INIT_LEGACY_CRC32, ISALLTRUE, ISSIGNKEY, GISTENTRY::key, GISTENTRY::leafkey, WordEntry::len, len, LOOPBYTE, makesign(), GISTENTRY::offset, GISTENTRY::page, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, PointerGetDatum(), WordEntry::pos, qsort, qunique(), GISTENTRY::rel, repalloc(), res, SET_VARSIZE, sign, SIGNKEY, STRPTR, TOAST_INDEX_TARGET, val, and VARSIZE.

gtsvector_consistent()

Datum gtsvector_consistent

(

PG_FUNCTION_ARGS

)

Definition at line 335 of file tsgistidx.c.

{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    TSQuery     query = PG_GETARG_TSQUERY(1);
 
    /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
    /* Oid      subtype = PG_GETARG_OID(3); */
    bool       *recheck = (bool *) PG_GETARG_POINTER(4);
    SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
 
    /* All cases served by this function are inexact */
    *recheck = true;
 
    if (!query->size)
        PG_RETURN_BOOL(false);
 
    if (ISSIGNKEY(key))
    {
        if (ISALLTRUE(key))
            PG_RETURN_BOOL(true);
 
        PG_RETURN_BOOL(TS_execute(GETQUERY(query),
                                  key,
                                  TS_EXEC_PHRASE_NO_POS,
                                  checkcondition_bit));
    }
    else
    {                           /* only leaf pages */
        CHKVAL      chkval;
 
        chkval.arrb = GETARR(key);
        chkval.arre = chkval.arrb + ARRNELEM(key);
        PG_RETURN_BOOL(TS_execute(GETQUERY(query),
                                  (void *) &chkval,
                                  TS_EXEC_PHRASE_NO_POS,
                                  checkcondition_arr));
    }
}

References CHKVAL::arrb, CHKVAL::arre, ARRNELEM, checkcondition_arr(), checkcondition_bit(), DatumGetPointer(), GETARR, GETQUERY, ISALLTRUE, ISSIGNKEY, GISTENTRY::key, sort-test::key, PG_GETARG_POINTER, PG_GETARG_TSQUERY, PG_RETURN_BOOL, TSQueryData::size, TS_EXEC_PHRASE_NO_POS, and TS_execute().

Referenced by gtsvector_consistent_oldsig().

gtsvector_consistent_oldsig()

Datum gtsvector_consistent_oldsig

(

PG_FUNCTION_ARGS

)

Definition at line 807 of file tsgistidx.c.

{
    return gtsvector_consistent(fcinfo);
}

References gtsvector_consistent().

gtsvector_decompress()

Datum gtsvector_decompress

(

PG_FUNCTION_ARGS

)

Definition at line 253 of file tsgistidx.c.

{
    /*
     * We need to detoast the stored value, because the other gtsvector
     * support functions don't cope with toasted values.
     */
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    SignTSVector *key = (SignTSVector *) PG_DETOAST_DATUM(entry->key);
 
    if (key != (SignTSVector *) DatumGetPointer(entry->key))
    {
        GISTENTRY  *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 
        gistentryinit(*retval, PointerGetDatum(key),
                      entry->rel, entry->page,
                      entry->offset, false);
 
        PG_RETURN_POINTER(retval);
    }
 
    PG_RETURN_POINTER(entry);
}

References DatumGetPointer(), gistentryinit, GISTENTRY::key, sort-test::key, GISTENTRY::offset, GISTENTRY::page, palloc(), PG_DETOAST_DATUM, PG_GETARG_POINTER, PG_RETURN_POINTER, PointerGetDatum(), and GISTENTRY::rel.

gtsvector_options()

Datum gtsvector_options

(

PG_FUNCTION_ARGS

)

Definition at line 813 of file tsgistidx.c.

{
    local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
 
    init_local_reloptions(relopts, sizeof(GistTsVectorOptions));
    add_local_int_reloption(relopts, "siglen", "signature length",
                            SIGLEN_DEFAULT, 1, SIGLEN_MAX,
                            offsetof(GistTsVectorOptions, siglen));
 
    PG_RETURN_VOID();
}

References add_local_int_reloption(), init_local_reloptions(), PG_GETARG_POINTER, PG_RETURN_VOID, SIGLEN_DEFAULT, and SIGLEN_MAX.

gtsvector_penalty()

Datum gtsvector_penalty

(

PG_FUNCTION_ARGS

)

Definition at line 534 of file tsgistidx.c.

{
    GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
    GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
    float      *penalty = (float *) PG_GETARG_POINTER(2);
    int         siglen = GET_SIGLEN();
    SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
    SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
    BITVECP     orig = GETSIGN(origval);
 
    *penalty = 0.0;
 
    if (ISARRKEY(newval))
    {
        BITVECP     sign = palloc(siglen);
 
        makesign(sign, newval, siglen);
 
        if (ISALLTRUE(origval))
        {
            int         siglenbit = SIGLENBIT(siglen);
 
            *penalty =
                (float) (siglenbit - sizebitvec(sign, siglen)) /
                (float) (siglenbit + 1);
        }
        else
            *penalty = hemdistsign(sign, orig, siglen);
 
        pfree(sign);
    }
    else
        *penalty = hemdist(origval, newval);
    PG_RETURN_POINTER(penalty);
}

References DatumGetPointer(), GET_SIGLEN, GETSIGN, hemdist(), hemdistsign(), ISALLTRUE, ISARRKEY, GISTENTRY::key, makesign(), newval, palloc(), pfree(), PG_GETARG_POINTER, PG_RETURN_POINTER, SIGLENBIT, sign, and sizebitvec().

gtsvector_picksplit()

Datum gtsvector_picksplit

(

PG_FUNCTION_ARGS

)

Definition at line 625 of file tsgistidx.c.

{
    GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
    GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
    int         siglen = GET_SIGLEN();
    OffsetNumber k,
                j;
    SignTSVector *datum_l,
               *datum_r;
    BITVECP     union_l,
                union_r;
    int32       size_alpha,
                size_beta;
    int32       size_waste,
                waste = -1;
    int32       nbytes;
    OffsetNumber seed_1 = 0,
                seed_2 = 0;
    OffsetNumber *left,
               *right;
    OffsetNumber maxoff;
    BITVECP     ptr;
    int         i;
    CACHESIGN  *cache;
    char       *cache_sign;
    SPLITCOST  *costvector;
 
    maxoff = entryvec->n - 2;
    nbytes = (maxoff + 2) * sizeof(OffsetNumber);
    v->spl_left = (OffsetNumber *) palloc(nbytes);
    v->spl_right = (OffsetNumber *) palloc(nbytes);
 
    cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
    cache_sign = palloc(siglen * (maxoff + 2));
 
    for (j = 0; j < maxoff + 2; j++)
        cache[j].sign = &cache_sign[siglen * j];
 
    fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber),
              siglen);
 
    for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
    {
        for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
        {
            if (k == FirstOffsetNumber)
                fillcache(&cache[j], GETENTRY(entryvec, j), siglen);
 
            size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
            if (size_waste > waste)
            {
                waste = size_waste;
                seed_1 = k;
                seed_2 = j;
            }
        }
    }
 
    left = v->spl_left;
    v->spl_nleft = 0;
    right = v->spl_right;
    v->spl_nright = 0;
 
    if (seed_1 == 0 || seed_2 == 0)
    {
        seed_1 = 1;
        seed_2 = 2;
    }
 
    /* form initial .. */
    datum_l = gtsvector_alloc(SIGNKEY | (cache[seed_1].allistrue ? ALLISTRUE : 0),
                              siglen, cache[seed_1].sign);
    datum_r = gtsvector_alloc(SIGNKEY | (cache[seed_2].allistrue ? ALLISTRUE : 0),
                              siglen, cache[seed_2].sign);
    union_l = GETSIGN(datum_l);
    union_r = GETSIGN(datum_r);
    maxoff = OffsetNumberNext(maxoff);
    fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff), siglen);
    /* sort before ... */
    costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
    for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
    {
        costvector[j - 1].pos = j;
        size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
        size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
        costvector[j - 1].cost = abs(size_alpha - size_beta);
    }
    qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
 
    for (k = 0; k < maxoff; k++)
    {
        j = costvector[k].pos;
        if (j == seed_1)
        {
            *left++ = j;
            v->spl_nleft++;
            continue;
        }
        else if (j == seed_2)
        {
            *right++ = j;
            v->spl_nright++;
            continue;
        }
 
        if (ISALLTRUE(datum_l) || cache[j].allistrue)
        {
            if (ISALLTRUE(datum_l) && cache[j].allistrue)
                size_alpha = 0;
            else
                size_alpha = SIGLENBIT(siglen) -
                    sizebitvec((cache[j].allistrue) ?
                               GETSIGN(datum_l) :
                               cache[j].sign,
                               siglen);
        }
        else
            size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
 
        if (ISALLTRUE(datum_r) || cache[j].allistrue)
        {
            if (ISALLTRUE(datum_r) && cache[j].allistrue)
                size_beta = 0;
            else
                size_beta = SIGLENBIT(siglen) -
                    sizebitvec((cache[j].allistrue) ?
                               GETSIGN(datum_r) :
                               cache[j].sign,
                               siglen);
        }
        else
            size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
 
        if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
        {
            if (ISALLTRUE(datum_l) || cache[j].allistrue)
            {
                if (!ISALLTRUE(datum_l))
                    memset(GETSIGN(datum_l), 0xff, siglen);
            }
            else
            {
                ptr = cache[j].sign;
                LOOPBYTE(siglen)
                    union_l[i] |= ptr[i];
            }
            *left++ = j;
            v->spl_nleft++;
        }
        else
        {
            if (ISALLTRUE(datum_r) || cache[j].allistrue)
            {
                if (!ISALLTRUE(datum_r))
                    memset(GETSIGN(datum_r), 0xff, siglen);
            }
            else
            {
                ptr = cache[j].sign;
                LOOPBYTE(siglen)
                    union_r[i] |= ptr[i];
            }
            *right++ = j;
            v->spl_nright++;
        }
    }
 
    *right = *left = FirstOffsetNumber;
    v->spl_ldatum = PointerGetDatum(datum_l);
    v->spl_rdatum = PointerGetDatum(datum_r);
 
    PG_RETURN_POINTER(v);
}

References ALLISTRUE, comparecost(), SPLITCOST::cost, fillcache(), FirstOffsetNumber, GET_SIGLEN, GETENTRY, GETSIGN, gtsvector_alloc(), hemdistcache(), hemdistsign(), i, ISALLTRUE, j, LOOPBYTE, GistEntryVector::n, OffsetNumberNext, palloc(), PG_GETARG_POINTER, PG_RETURN_POINTER, PointerGetDatum(), SPLITCOST::pos, qsort, SIGLENBIT, CACHESIGN::sign, sign, SIGNKEY, sizebitvec(), GIST_SPLITVEC::spl_ldatum, GIST_SPLITVEC::spl_left, GIST_SPLITVEC::spl_nleft, GIST_SPLITVEC::spl_nright, GIST_SPLITVEC::spl_rdatum, GIST_SPLITVEC::spl_right, and WISH_F.

gtsvector_same()

Datum gtsvector_same

(

PG_FUNCTION_ARGS

)

Definition at line 430 of file tsgistidx.c.

{
    SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
    SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
    bool       *result = (bool *) PG_GETARG_POINTER(2);
    int         siglen = GET_SIGLEN();
 
    if (ISSIGNKEY(a))
    {                           /* then b also ISSIGNKEY */
        if (ISALLTRUE(a) && ISALLTRUE(b))
            *result = true;
        else if (ISALLTRUE(a))
            *result = false;
        else if (ISALLTRUE(b))
            *result = false;
        else
        {
            int32       i;
            BITVECP     sa = GETSIGN(a),
                        sb = GETSIGN(b);
 
            Assert(GETSIGLEN(a) == siglen && GETSIGLEN(b) == siglen);
 
            *result = true;
            LOOPBYTE(siglen)
            {
                if (sa[i] != sb[i])
                {
                    *result = false;
                    break;
                }
            }
        }
    }
    else
    {                           /* a and b ISARRKEY */
        int32       lena = ARRNELEM(a),
                    lenb = ARRNELEM(b);
 
        if (lena != lenb)
            *result = false;
        else
        {
            int32      *ptra = GETARR(a),
                       *ptrb = GETARR(b);
            int32       i;
 
            *result = true;
            for (i = 0; i < lena; i++)
                if (ptra[i] != ptrb[i])
                {
                    *result = false;
                    break;
                }
        }
    }
 
    PG_RETURN_POINTER(result);
}

References a, ARRNELEM, Assert(), b, GET_SIGLEN, GETARR, GETSIGLEN, GETSIGN, i, ISALLTRUE, ISSIGNKEY, LOOPBYTE, PG_GETARG_POINTER, and PG_RETURN_POINTER.

gtsvector_union()

Datum gtsvector_union

(

PG_FUNCTION_ARGS

)

Definition at line 403 of file tsgistidx.c.

{
    GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
    int        *size = (int *) PG_GETARG_POINTER(1);
    int         siglen = GET_SIGLEN();
    SignTSVector *result = gtsvector_alloc(SIGNKEY, siglen, NULL);
    BITVECP     base = GETSIGN(result);
    int32       i;
 
    memset(base, 0, siglen);
 
    for (i = 0; i < entryvec->n; i++)
    {
        if (unionkey(base, GETENTRY(entryvec, i), siglen))
        {
            result->flag |= ALLISTRUE;
            SET_VARSIZE(result, CALCGTSIZE(result->flag, siglen));
            break;
        }
    }
 
    *size = VARSIZE(result);
 
    PG_RETURN_POINTER(result);
}

References ALLISTRUE, CALCGTSIZE, SignTSVector::flag, GET_SIGLEN, GETENTRY, GETSIGN, gtsvector_alloc(), i, GistEntryVector::n, PG_GETARG_POINTER, PG_RETURN_POINTER, SET_VARSIZE, SIGNKEY, unionkey(), and VARSIZE.

gtsvectorin()

Datum gtsvectorin

(

PG_FUNCTION_ARGS

)

Definition at line 88 of file tsgistidx.c.

{
    /* There's no need to support input of gtsvectors */
    ereport(ERROR,
            (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
             errmsg("cannot accept a value of type %s", "gtsvector")));
 
    PG_RETURN_VOID();           /* keep compiler quiet */
}

References ereport, errcode(), errmsg(), ERROR, and PG_RETURN_VOID.

gtsvectorout()

Datum gtsvectorout

(

PG_FUNCTION_ARGS

)

Definition at line 105 of file tsgistidx.c.

{
    SignTSVector *key = (SignTSVector *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
    char       *outbuf;
 
    if (outbuf_maxlen == 0)
        outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
    outbuf = palloc(outbuf_maxlen);
 
    if (ISARRKEY(key))
        sprintf(outbuf, ARROUTSTR, (int) ARRNELEM(key));
    else
    {
        if (ISALLTRUE(key))
            sprintf(outbuf, "all true bits");
        else
        {
            int         siglen = GETSIGLEN(key);
            int         cnttrue = sizebitvec(GETSIGN(key), siglen);
 
            sprintf(outbuf, SINGOUTSTR, cnttrue, (int) SIGLENBIT(siglen) - cnttrue);
        }
    }
 
    PG_FREE_IF_COPY(key, 0);
    PG_RETURN_POINTER(outbuf);
}

References ARRNELEM, ARROUTSTR, EXTRALEN, GETSIGLEN, GETSIGN, ISALLTRUE, ISARRKEY, sort-test::key, Max, outbuf_maxlen, palloc(), PG_DETOAST_DATUM, PG_FREE_IF_COPY, PG_GETARG_DATUM, PG_RETURN_POINTER, SIGLENBIT, SINGOUTSTR, sizebitvec(), and sprintf.

hemdist()

static int hemdist ( SignTSVector *  a, SignTSVector *  b  )

static

Definition at line 513 of file tsgistidx.c.

{
    int         siglena = GETSIGLEN(a);
    int         siglenb = GETSIGLEN(b);
 
    if (ISALLTRUE(a))
    {
        if (ISALLTRUE(b))
            return 0;
        else
            return SIGLENBIT(siglenb) - sizebitvec(GETSIGN(b), siglenb);
    }
    else if (ISALLTRUE(b))
        return SIGLENBIT(siglena) - sizebitvec(GETSIGN(a), siglena);
 
    Assert(siglena == siglenb);
 
    return hemdistsign(GETSIGN(a), GETSIGN(b), siglena);
}

References a, Assert(), b, GETSIGLEN, GETSIGN, hemdistsign(), ISALLTRUE, SIGLENBIT, and sizebitvec().

Referenced by gtsvector_penalty().

hemdistcache()

static int hemdistcache ( CACHESIGN *  a, CACHESIGN *  b, int  siglen  )

static

Definition at line 609 of file tsgistidx.c.

{
    if (a->allistrue)
    {
        if (b->allistrue)
            return 0;
        else
            return SIGLENBIT(siglen) - sizebitvec(b->sign, siglen);
    }
    else if (b->allistrue)
        return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
 
    return hemdistsign(a->sign, b->sign, siglen);
}

References a, b, hemdistsign(), SIGLENBIT, and sizebitvec().

Referenced by gtsvector_picksplit().

hemdistsign()

static int hemdistsign ( BITVECP  a, BITVECP  b, int  siglen  )

static

Definition at line 497 of file tsgistidx.c.

{
    int         i,
                diff,
                dist = 0;
 
    LOOPBYTE(siglen)
    {
        diff = (unsigned char) (a[i] ^ b[i]);
        /* Using the popcount functions here isn't likely to win */
        dist += pg_number_of_ones[diff];
    }
    return dist;
}

References a, b, i, LOOPBYTE, and pg_number_of_ones.

Referenced by gtsvector_penalty(), gtsvector_picksplit(), hemdist(), and hemdistcache().

makesign()

static void makesign ( BITVECP  sign, SignTSVector *  a, int  siglen  )

static

Definition at line 145 of file tsgistidx.c.

{
    int32       k,
                len = ARRNELEM(a);
    int32      *ptr = GETARR(a);
 
    MemSet(sign, 0, siglen);
    for (k = 0; k < len; k++)
        HASH(sign, ptr[k], siglen);
}

References a, ARRNELEM, GETARR, HASH, len, MemSet, and sign.

Referenced by fillcache(), gtsvector_compress(), and gtsvector_penalty().

sizebitvec()

static int32 sizebitvec ( BITVECP  sign, int  siglen  )

static

Definition at line 491 of file tsgistidx.c.

{
    return pg_popcount(sign, siglen);
}

References pg_popcount(), and sign.

Referenced by gtsvector_penalty(), gtsvector_picksplit(), gtsvectorout(), hemdist(), and hemdistcache().

unionkey()

static int32 unionkey ( BITVECP  sbase, SignTSVector *  add, int  siglen  )

static

Definition at line 375 of file tsgistidx.c.

{
    int32       i;
 
    if (ISSIGNKEY(add))
    {
        BITVECP     sadd = GETSIGN(add);
 
        if (ISALLTRUE(add))
            return 1;
 
        Assert(GETSIGLEN(add) == siglen);
 
        LOOPBYTE(siglen)
            sbase[i] |= sadd[i];
    }
    else
    {
        int32      *ptr = GETARR(add);
 
        for (i = 0; i < ARRNELEM(add); i++)
            HASH(sbase, ptr[i], siglen);
    }
    return 0;
}

References ARRNELEM, Assert(), GETARR, GETSIGLEN, GETSIGN, HASH, i, ISALLTRUE, ISSIGNKEY, and LOOPBYTE.

Referenced by gtsvector_union().

Variable Documentation

outbuf_maxlen

int outbuf_maxlen = 0

static

Definition at line 102 of file tsgistidx.c.

Referenced by gtsvectorout().