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 : }
|
