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