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