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