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