Line data Source code
1 : /*
2 : * contrib/intarray/_intbig_gist.c
3 : */
4 : #include "postgres.h"
5 :
6 : #include "_int.h"
7 : #include "access/gist.h"
8 : #include "access/reloptions.h"
9 : #include "access/stratnum.h"
10 : #include "common/int.h"
11 : #include "port/pg_bitutils.h"
12 :
13 : #define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))
14 : /*
15 : ** _intbig methods
16 : */
17 4 : PG_FUNCTION_INFO_V1(g_intbig_consistent);
18 4 : PG_FUNCTION_INFO_V1(g_intbig_compress);
19 4 : PG_FUNCTION_INFO_V1(g_intbig_decompress);
20 4 : PG_FUNCTION_INFO_V1(g_intbig_penalty);
21 4 : PG_FUNCTION_INFO_V1(g_intbig_picksplit);
22 4 : PG_FUNCTION_INFO_V1(g_intbig_union);
23 4 : PG_FUNCTION_INFO_V1(g_intbig_same);
24 4 : PG_FUNCTION_INFO_V1(g_intbig_options);
25 :
26 2 : PG_FUNCTION_INFO_V1(_intbig_in);
27 2 : PG_FUNCTION_INFO_V1(_intbig_out);
28 :
29 : Datum
30 0 : _intbig_in(PG_FUNCTION_ARGS)
31 : {
32 0 : ereport(ERROR,
33 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
34 : errmsg("cannot accept a value of type %s", "intbig_gkey")));
35 :
36 : PG_RETURN_VOID(); /* keep compiler quiet */
37 : }
38 :
39 : Datum
40 0 : _intbig_out(PG_FUNCTION_ARGS)
41 : {
42 0 : ereport(ERROR,
43 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
44 : errmsg("cannot display a value of type %s", "intbig_gkey")));
45 :
46 : PG_RETURN_VOID(); /* keep compiler quiet */
47 : }
48 :
49 : static GISTTYPE *
50 171170 : _intbig_alloc(bool allistrue, int siglen, BITVECP sign)
51 : {
52 171170 : int flag = allistrue ? ALLISTRUE : 0;
53 171170 : int size = CALCGTSIZE(flag, siglen);
54 171170 : GISTTYPE *res = (GISTTYPE *) palloc(size);
55 :
56 171170 : SET_VARSIZE(res, size);
57 171170 : res->flag = flag;
58 :
59 171170 : if (!allistrue)
60 : {
61 171170 : if (sign)
62 18124 : memcpy(GETSIGN(res), sign, siglen);
63 : else
64 153046 : memset(GETSIGN(res), 0, siglen);
65 : }
66 :
67 171170 : return res;
68 : }
69 :
70 :
71 : /*********************************************************************
72 : ** intbig functions
73 : *********************************************************************/
74 : static bool
75 14698 : _intbig_overlap(GISTTYPE *a, ArrayType *b, int siglen)
76 : {
77 14698 : int num = ARRNELEMS(b);
78 14698 : int32 *ptr = ARRPTR(b);
79 :
80 14698 : CHECKARRVALID(b);
81 :
82 37534 : while (num--)
83 : {
84 26960 : if (GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
85 4124 : return true;
86 22836 : ptr++;
87 : }
88 :
89 10574 : return false;
90 : }
91 :
92 : static bool
93 17702 : _intbig_contains(GISTTYPE *a, ArrayType *b, int siglen)
94 : {
95 17702 : int num = ARRNELEMS(b);
96 17702 : int32 *ptr = ARRPTR(b);
97 :
98 17702 : CHECKARRVALID(b);
99 :
100 26506 : while (num--)
101 : {
102 23646 : if (!GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
103 14842 : return false;
104 8804 : ptr++;
105 : }
106 :
107 2860 : return true;
108 : }
109 :
110 : Datum
111 124938 : g_intbig_same(PG_FUNCTION_ARGS)
112 : {
113 124938 : GISTTYPE *a = (GISTTYPE *) PG_GETARG_POINTER(0);
114 124938 : GISTTYPE *b = (GISTTYPE *) PG_GETARG_POINTER(1);
115 124938 : bool *result = (bool *) PG_GETARG_POINTER(2);
116 124938 : int siglen = GET_SIGLEN();
117 :
118 124938 : if (ISALLTRUE(a) && ISALLTRUE(b))
119 0 : *result = true;
120 124938 : else if (ISALLTRUE(a))
121 0 : *result = false;
122 124938 : else if (ISALLTRUE(b))
123 0 : *result = false;
124 : else
125 : {
126 : int32 i;
127 124938 : BITVECP sa = GETSIGN(a),
128 124938 : sb = GETSIGN(b);
129 :
130 124938 : *result = true;
131 92465550 : LOOPBYTE(siglen)
132 : {
133 92409064 : if (sa[i] != sb[i])
134 : {
135 68452 : *result = false;
136 68452 : break;
137 : }
138 : }
139 : }
140 124938 : PG_RETURN_POINTER(result);
141 : }
142 :
143 : Datum
144 113612 : g_intbig_compress(PG_FUNCTION_ARGS)
145 : {
146 113612 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
147 113612 : int siglen = GET_SIGLEN();
148 :
149 113612 : if (entry->leafkey)
150 : {
151 : GISTENTRY *retval;
152 27028 : ArrayType *in = DatumGetArrayTypeP(entry->key);
153 : int32 *ptr;
154 : int num;
155 27028 : GISTTYPE *res = _intbig_alloc(false, siglen, NULL);
156 :
157 27028 : CHECKARRVALID(in);
158 27028 : if (ARRISEMPTY(in))
159 : {
160 36 : ptr = NULL;
161 36 : num = 0;
162 : }
163 : else
164 : {
165 26992 : ptr = ARRPTR(in);
166 26992 : num = ARRNELEMS(in);
167 : }
168 :
169 135644 : while (num--)
170 : {
171 108616 : HASH(GETSIGN(res), *ptr, siglen);
172 108616 : ptr++;
173 : }
174 :
175 27028 : retval = palloc_object(GISTENTRY);
176 27028 : gistentryinit(*retval, PointerGetDatum(res),
177 : entry->rel, entry->page,
178 : entry->offset, false);
179 :
180 27028 : PG_RETURN_POINTER(retval);
181 : }
182 86584 : else if (!ISALLTRUE(DatumGetPointer(entry->key)))
183 : {
184 : GISTENTRY *retval;
185 : int i;
186 86584 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
187 : GISTTYPE *res;
188 :
189 111094 : LOOPBYTE(siglen)
190 : {
191 111094 : if ((sign[i] & 0xff) != 0xff)
192 86584 : PG_RETURN_POINTER(entry);
193 : }
194 :
195 0 : res = _intbig_alloc(true, siglen, sign);
196 0 : retval = palloc_object(GISTENTRY);
197 0 : gistentryinit(*retval, PointerGetDatum(res),
198 : entry->rel, entry->page,
199 : entry->offset, false);
200 :
201 0 : PG_RETURN_POINTER(retval);
202 : }
203 :
204 0 : PG_RETURN_POINTER(entry);
205 : }
206 :
207 :
208 : static int32
209 0 : sizebitvec(BITVECP sign, int siglen)
210 : {
211 0 : return pg_popcount(sign, siglen);
212 : }
213 :
214 : static int
215 990500 : hemdistsign(BITVECP a, BITVECP b, int siglen)
216 : {
217 : int i,
218 : diff,
219 990500 : dist = 0;
220 :
221 901958892 : LOOPBYTE(siglen)
222 : {
223 900968392 : diff = (unsigned char) (a[i] ^ b[i]);
224 : /* Using the popcount functions here isn't likely to win */
225 900968392 : dist += pg_number_of_ones[diff];
226 : }
227 990500 : return dist;
228 : }
229 :
230 : static int
231 990500 : hemdist(GISTTYPE *a, GISTTYPE *b, int siglen)
232 : {
233 990500 : if (ISALLTRUE(a))
234 : {
235 0 : if (ISALLTRUE(b))
236 0 : return 0;
237 : else
238 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(b), siglen);
239 : }
240 990500 : else if (ISALLTRUE(b))
241 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
242 :
243 990500 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
244 : }
245 :
246 : Datum
247 1163028 : g_intbig_decompress(PG_FUNCTION_ARGS)
248 : {
249 1163028 : PG_RETURN_DATUM(PG_GETARG_DATUM(0));
250 : }
251 :
252 : static int32
253 252356 : unionkey(BITVECP sbase, GISTTYPE *add, int siglen)
254 : {
255 : int32 i;
256 252356 : BITVECP sadd = GETSIGN(add);
257 :
258 252356 : if (ISALLTRUE(add))
259 0 : return 1;
260 419224212 : LOOPBYTE(siglen)
261 418971856 : sbase[i] |= sadd[i];
262 252356 : return 0;
263 : }
264 :
265 : Datum
266 126018 : g_intbig_union(PG_FUNCTION_ARGS)
267 : {
268 126018 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
269 126018 : int *size = (int *) PG_GETARG_POINTER(1);
270 126018 : int siglen = GET_SIGLEN();
271 : int32 i;
272 126018 : GISTTYPE *result = _intbig_alloc(false, siglen, NULL);
273 126018 : BITVECP base = GETSIGN(result);
274 :
275 378374 : for (i = 0; i < entryvec->n; i++)
276 : {
277 252356 : if (unionkey(base, GETENTRY(entryvec, i), siglen))
278 : {
279 0 : result->flag |= ALLISTRUE;
280 0 : SET_VARSIZE(result, CALCGTSIZE(ALLISTRUE, siglen));
281 0 : break;
282 : }
283 : }
284 :
285 126018 : *size = VARSIZE(result);
286 :
287 126018 : PG_RETURN_POINTER(result);
288 : }
289 :
290 : Datum
291 593690 : g_intbig_penalty(PG_FUNCTION_ARGS)
292 : {
293 593690 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
294 593690 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
295 593690 : float *penalty = (float *) PG_GETARG_POINTER(2);
296 593690 : GISTTYPE *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
297 593690 : GISTTYPE *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
298 593690 : int siglen = GET_SIGLEN();
299 :
300 593690 : *penalty = hemdist(origval, newval, siglen);
301 593690 : PG_RETURN_POINTER(penalty);
302 : }
303 :
304 :
305 : typedef struct
306 : {
307 : OffsetNumber pos;
308 : int32 cost;
309 : } SPLITCOST;
310 :
311 : static int
312 80094 : comparecost(const void *a, const void *b)
313 : {
314 160188 : return pg_cmp_s32(((const SPLITCOST *) a)->cost,
315 80094 : ((const SPLITCOST *) b)->cost);
316 : }
317 :
318 :
319 : Datum
320 9062 : g_intbig_picksplit(PG_FUNCTION_ARGS)
321 : {
322 9062 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
323 9062 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
324 9062 : int siglen = GET_SIGLEN();
325 : OffsetNumber k,
326 : j;
327 : GISTTYPE *datum_l,
328 : *datum_r;
329 : BITVECP union_l,
330 : union_r;
331 : int32 size_alpha,
332 : size_beta;
333 : int32 size_waste,
334 9062 : waste = -1;
335 : int32 nbytes;
336 9062 : OffsetNumber seed_1 = 0,
337 9062 : seed_2 = 0;
338 : OffsetNumber *left,
339 : *right;
340 : OffsetNumber maxoff;
341 : BITVECP ptr;
342 : int i;
343 : SPLITCOST *costvector;
344 : GISTTYPE *_k,
345 : *_j;
346 :
347 9062 : maxoff = entryvec->n - 2;
348 9062 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
349 9062 : v->spl_left = (OffsetNumber *) palloc(nbytes);
350 9062 : v->spl_right = (OffsetNumber *) palloc(nbytes);
351 :
352 41678 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
353 : {
354 32616 : _k = GETENTRY(entryvec, k);
355 262714 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
356 : {
357 230098 : size_waste = hemdist(_k, GETENTRY(entryvec, j), siglen);
358 230098 : if (size_waste > waste)
359 : {
360 17698 : waste = size_waste;
361 17698 : seed_1 = k;
362 17698 : seed_2 = j;
363 : }
364 : }
365 : }
366 :
367 9062 : left = v->spl_left;
368 9062 : v->spl_nleft = 0;
369 9062 : right = v->spl_right;
370 9062 : v->spl_nright = 0;
371 :
372 9062 : if (seed_1 == 0 || seed_2 == 0)
373 : {
374 0 : seed_1 = 1;
375 0 : seed_2 = 2;
376 : }
377 :
378 : /* form initial .. */
379 9062 : datum_l = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_1)), siglen,
380 9062 : GETSIGN(GETENTRY(entryvec, seed_1)));
381 9062 : datum_r = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_2)), siglen,
382 9062 : GETSIGN(GETENTRY(entryvec, seed_2)));
383 :
384 9062 : maxoff = OffsetNumberNext(maxoff);
385 : /* sort before ... */
386 9062 : costvector = palloc_array(SPLITCOST, maxoff);
387 59802 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
388 : {
389 50740 : costvector[j - 1].pos = j;
390 50740 : _j = GETENTRY(entryvec, j);
391 50740 : size_alpha = hemdist(datum_l, _j, siglen);
392 50740 : size_beta = hemdist(datum_r, _j, siglen);
393 50740 : costvector[j - 1].cost = abs(size_alpha - size_beta);
394 : }
395 9062 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
396 :
397 9062 : union_l = GETSIGN(datum_l);
398 9062 : union_r = GETSIGN(datum_r);
399 :
400 59802 : for (k = 0; k < maxoff; k++)
401 : {
402 50740 : j = costvector[k].pos;
403 50740 : if (j == seed_1)
404 : {
405 9062 : *left++ = j;
406 9062 : v->spl_nleft++;
407 9062 : continue;
408 : }
409 41678 : else if (j == seed_2)
410 : {
411 9062 : *right++ = j;
412 9062 : v->spl_nright++;
413 9062 : continue;
414 : }
415 32616 : _j = GETENTRY(entryvec, j);
416 32616 : size_alpha = hemdist(datum_l, _j, siglen);
417 32616 : size_beta = hemdist(datum_r, _j, siglen);
418 :
419 32616 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
420 : {
421 16156 : if (ISALLTRUE(datum_l) || ISALLTRUE(_j))
422 : {
423 0 : if (!ISALLTRUE(datum_l))
424 0 : memset(union_l, 0xff, siglen);
425 : }
426 : else
427 : {
428 16156 : ptr = GETSIGN(_j);
429 18483196 : LOOPBYTE(siglen)
430 18467040 : union_l[i] |= ptr[i];
431 : }
432 16156 : *left++ = j;
433 16156 : v->spl_nleft++;
434 : }
435 : else
436 : {
437 16460 : if (ISALLTRUE(datum_r) || ISALLTRUE(_j))
438 : {
439 0 : if (!ISALLTRUE(datum_r))
440 0 : memset(union_r, 0xff, siglen);
441 : }
442 : else
443 : {
444 16460 : ptr = GETSIGN(_j);
445 19651660 : LOOPBYTE(siglen)
446 19635200 : union_r[i] |= ptr[i];
447 : }
448 16460 : *right++ = j;
449 16460 : v->spl_nright++;
450 : }
451 : }
452 :
453 9062 : *right = *left = FirstOffsetNumber;
454 9062 : pfree(costvector);
455 :
456 9062 : v->spl_ldatum = PointerGetDatum(datum_l);
457 9062 : v->spl_rdatum = PointerGetDatum(datum_r);
458 :
459 9062 : PG_RETURN_POINTER(v);
460 : }
461 :
462 : Datum
463 135756 : g_intbig_consistent(PG_FUNCTION_ARGS)
464 : {
465 135756 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
466 135756 : ArrayType *query = PG_GETARG_ARRAYTYPE_P(1);
467 135756 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
468 : #ifdef NOT_USED
469 : Oid subtype = PG_GETARG_OID(3);
470 : #endif
471 135756 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
472 135756 : int siglen = GET_SIGLEN();
473 : bool retval;
474 :
475 : /* All cases served by this function are inexact */
476 135756 : *recheck = true;
477 :
478 135756 : if (ISALLTRUE(DatumGetPointer(entry->key)))
479 0 : PG_RETURN_BOOL(true);
480 :
481 135756 : if (strategy == BooleanSearchStrategy)
482 : {
483 102642 : retval = signconsistent((QUERYTYPE *) query,
484 102642 : GETSIGN(DatumGetPointer(entry->key)),
485 : siglen,
486 : false);
487 102642 : PG_FREE_IF_COPY(query, 1);
488 102642 : PG_RETURN_BOOL(retval);
489 : }
490 :
491 33114 : CHECKARRVALID(query);
492 :
493 33114 : switch (strategy)
494 : {
495 14698 : case RTOverlapStrategyNumber:
496 14698 : retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key),
497 : query, siglen);
498 14698 : break;
499 2016 : case RTSameStrategyNumber:
500 2016 : if (GIST_LEAF(entry))
501 : {
502 : int i,
503 714 : num = ARRNELEMS(query);
504 714 : int32 *ptr = ARRPTR(query);
505 714 : BITVECP dq = palloc0(siglen),
506 : de;
507 :
508 2856 : while (num--)
509 : {
510 2142 : HASH(dq, *ptr, siglen);
511 2142 : ptr++;
512 : }
513 :
514 714 : de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
515 714 : retval = true;
516 6246 : LOOPBYTE(siglen)
517 : {
518 6242 : if (de[i] != dq[i])
519 : {
520 710 : retval = false;
521 710 : break;
522 : }
523 : }
524 :
525 714 : pfree(dq);
526 : }
527 : else
528 1302 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
529 : query, siglen);
530 2016 : break;
531 16400 : case RTContainsStrategyNumber:
532 : case RTOldContainsStrategyNumber:
533 16400 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
534 : query, siglen);
535 16400 : break;
536 0 : case RTContainedByStrategyNumber:
537 : case RTOldContainedByStrategyNumber:
538 :
539 : /*
540 : * This code is unreachable as of intarray 1.4, because the <@
541 : * operator has been removed from the opclass. We keep it for now
542 : * to support older versions of the SQL definitions.
543 : */
544 0 : if (GIST_LEAF(entry))
545 : {
546 : int i,
547 0 : num = ARRNELEMS(query);
548 0 : int32 *ptr = ARRPTR(query);
549 0 : BITVECP dq = palloc0(siglen),
550 : de;
551 :
552 0 : while (num--)
553 : {
554 0 : HASH(dq, *ptr, siglen);
555 0 : ptr++;
556 : }
557 :
558 0 : de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
559 0 : retval = true;
560 0 : LOOPBYTE(siglen)
561 : {
562 0 : if (de[i] & ~dq[i])
563 : {
564 0 : retval = false;
565 0 : break;
566 : }
567 : }
568 : }
569 : else
570 : {
571 : /*
572 : * Unfortunately, because empty arrays could be anywhere in
573 : * the index, we must search the whole tree.
574 : */
575 0 : retval = true;
576 : }
577 0 : break;
578 0 : default:
579 0 : retval = false;
580 : }
581 33114 : PG_FREE_IF_COPY(query, 1);
582 33114 : PG_RETURN_BOOL(retval);
583 : }
584 :
585 : Datum
586 20 : g_intbig_options(PG_FUNCTION_ARGS)
587 : {
588 20 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
589 :
590 20 : init_local_reloptions(relopts, sizeof(GISTIntArrayBigOptions));
591 20 : add_local_int_reloption(relopts, "siglen",
592 : "signature length in bytes",
593 : SIGLEN_DEFAULT, 1, SIGLEN_MAX,
594 : offsetof(GISTIntArrayBigOptions, siglen));
595 :
596 20 : PG_RETURN_VOID();
597 : }
|
