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 2 : PG_FUNCTION_INFO_V1(g_intbig_consistent);
18 2 : PG_FUNCTION_INFO_V1(g_intbig_compress);
19 2 : PG_FUNCTION_INFO_V1(g_intbig_decompress);
20 2 : PG_FUNCTION_INFO_V1(g_intbig_penalty);
21 2 : PG_FUNCTION_INFO_V1(g_intbig_picksplit);
22 2 : PG_FUNCTION_INFO_V1(g_intbig_union);
23 2 : PG_FUNCTION_INFO_V1(g_intbig_same);
24 2 : PG_FUNCTION_INFO_V1(g_intbig_options);
25 :
26 1 : PG_FUNCTION_INFO_V1(_intbig_in);
27 1 : 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 87413 : _intbig_alloc(bool allistrue, int siglen, BITVECP sign)
51 : {
52 87413 : int flag = allistrue ? ALLISTRUE : 0;
53 87413 : int size = CALCGTSIZE(flag, siglen);
54 87413 : GISTTYPE *res = (GISTTYPE *) palloc(size);
55 :
56 87413 : SET_VARSIZE(res, size);
57 87413 : res->flag = flag;
58 :
59 87413 : if (!allistrue)
60 : {
61 87413 : if (sign)
62 9060 : memcpy(GETSIGN(res), sign, siglen);
63 : else
64 78353 : memset(GETSIGN(res), 0, siglen);
65 : }
66 :
67 87413 : return res;
68 : }
69 :
70 :
71 : /*********************************************************************
72 : ** intbig functions
73 : *********************************************************************/
74 : static bool
75 7586 : _intbig_overlap(GISTTYPE *a, ArrayType *b, int siglen)
76 : {
77 7586 : int num = ARRNELEMS(b);
78 7586 : int32 *ptr = ARRPTR(b);
79 :
80 7586 : CHECKARRVALID(b);
81 :
82 19404 : while (num--)
83 : {
84 13936 : if (GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
85 2118 : return true;
86 11818 : ptr++;
87 : }
88 :
89 5468 : return false;
90 : }
91 :
92 : static bool
93 9226 : _intbig_contains(GISTTYPE *a, ArrayType *b, int siglen)
94 : {
95 9226 : int num = ARRNELEMS(b);
96 9226 : int32 *ptr = ARRPTR(b);
97 :
98 9226 : CHECKARRVALID(b);
99 :
100 14037 : while (num--)
101 : {
102 12442 : if (!GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
103 7631 : return false;
104 4811 : ptr++;
105 : }
106 :
107 1595 : return true;
108 : }
109 :
110 : Datum
111 63000 : g_intbig_same(PG_FUNCTION_ARGS)
112 : {
113 63000 : GISTTYPE *a = (GISTTYPE *) PG_GETARG_POINTER(0);
114 63000 : GISTTYPE *b = (GISTTYPE *) PG_GETARG_POINTER(1);
115 63000 : bool *result = (bool *) PG_GETARG_POINTER(2);
116 63000 : int siglen = GET_SIGLEN();
117 :
118 63000 : if (ISALLTRUE(a) && ISALLTRUE(b))
119 0 : *result = true;
120 63000 : else if (ISALLTRUE(a))
121 0 : *result = false;
122 63000 : else if (ISALLTRUE(b))
123 0 : *result = false;
124 : else
125 : {
126 : int32 i;
127 63000 : BITVECP sa = GETSIGN(a),
128 63000 : sb = GETSIGN(b);
129 :
130 63000 : *result = true;
131 46561903 : LOOPBYTE(siglen)
132 : {
133 46533491 : if (sa[i] != sb[i])
134 : {
135 34588 : *result = false;
136 34588 : break;
137 : }
138 : }
139 : }
140 63000 : PG_RETURN_POINTER(result);
141 : }
142 :
143 : Datum
144 57170 : g_intbig_compress(PG_FUNCTION_ARGS)
145 : {
146 57170 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
147 57170 : int siglen = GET_SIGLEN();
148 :
149 57170 : if (entry->leafkey)
150 : {
151 : GISTENTRY *retval;
152 13514 : ArrayType *in = DatumGetArrayTypeP(entry->key);
153 : int32 *ptr;
154 : int num;
155 13514 : GISTTYPE *res = _intbig_alloc(false, siglen, NULL);
156 :
157 13514 : CHECKARRVALID(in);
158 13514 : if (ARRISEMPTY(in))
159 : {
160 18 : ptr = NULL;
161 18 : num = 0;
162 : }
163 : else
164 : {
165 13496 : ptr = ARRPTR(in);
166 13496 : num = ARRNELEMS(in);
167 : }
168 :
169 67822 : while (num--)
170 : {
171 54308 : HASH(GETSIGN(res), *ptr, siglen);
172 54308 : ptr++;
173 : }
174 :
175 13514 : retval = palloc_object(GISTENTRY);
176 13514 : gistentryinit(*retval, PointerGetDatum(res),
177 : entry->rel, entry->page,
178 : entry->offset, false);
179 :
180 13514 : PG_RETURN_POINTER(retval);
181 : }
182 43656 : else if (!ISALLTRUE(DatumGetPointer(entry->key)))
183 : {
184 : GISTENTRY *retval;
185 : int i;
186 43656 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
187 : GISTTYPE *res;
188 :
189 63410 : LOOPBYTE(siglen)
190 : {
191 63410 : if ((sign[i] & 0xff) != 0xff)
192 43656 : 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 495018 : hemdistsign(BITVECP a, BITVECP b, int siglen)
216 : {
217 : int i,
218 : diff,
219 495018 : dist = 0;
220 :
221 450325358 : LOOPBYTE(siglen)
222 : {
223 449830340 : diff = (unsigned char) (a[i] ^ b[i]);
224 : /* Using the popcount functions here isn't likely to win */
225 449830340 : dist += pg_number_of_ones[diff];
226 : }
227 495018 : return dist;
228 : }
229 :
230 : static int
231 495018 : hemdist(GISTTYPE *a, GISTTYPE *b, int siglen)
232 : {
233 495018 : 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 495018 : else if (ISALLTRUE(b))
241 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
242 :
243 495018 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
244 : }
245 :
246 : Datum
247 590247 : g_intbig_decompress(PG_FUNCTION_ARGS)
248 : {
249 590247 : PG_RETURN_DATUM(PG_GETARG_DATUM(0));
250 : }
251 :
252 : static int32
253 130050 : unionkey(BITVECP sbase, GISTTYPE *add, int siglen)
254 : {
255 : int32 i;
256 130050 : BITVECP sadd = GETSIGN(add);
257 :
258 130050 : if (ISALLTRUE(add))
259 0 : return 1;
260 217077242 : LOOPBYTE(siglen)
261 216947192 : sbase[i] |= sadd[i];
262 130050 : return 0;
263 : }
264 :
265 : Datum
266 64839 : g_intbig_union(PG_FUNCTION_ARGS)
267 : {
268 64839 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
269 64839 : int *size = (int *) PG_GETARG_POINTER(1);
270 64839 : int siglen = GET_SIGLEN();
271 : int32 i;
272 64839 : GISTTYPE *result = _intbig_alloc(false, siglen, NULL);
273 64839 : BITVECP base = GETSIGN(result);
274 :
275 194889 : for (i = 0; i < entryvec->n; i++)
276 : {
277 130050 : 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 64839 : *size = VARSIZE(result);
286 :
287 64839 : PG_RETURN_POINTER(result);
288 : }
289 :
290 : Datum
291 297780 : g_intbig_penalty(PG_FUNCTION_ARGS)
292 : {
293 297780 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
294 297780 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
295 297780 : float *penalty = (float *) PG_GETARG_POINTER(2);
296 297780 : GISTTYPE *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
297 297780 : GISTTYPE *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
298 297780 : int siglen = GET_SIGLEN();
299 :
300 297780 : *penalty = hemdist(origval, newval, siglen);
301 297780 : PG_RETURN_POINTER(penalty);
302 : }
303 :
304 :
305 : typedef struct
306 : {
307 : OffsetNumber pos;
308 : int32 cost;
309 : } SPLITCOST;
310 :
311 : static int
312 39484 : comparecost(const void *a, const void *b)
313 : {
314 78968 : return pg_cmp_s32(((const SPLITCOST *) a)->cost,
315 39484 : ((const SPLITCOST *) b)->cost);
316 : }
317 :
318 :
319 : Datum
320 4530 : g_intbig_picksplit(PG_FUNCTION_ARGS)
321 : {
322 4530 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
323 4530 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
324 4530 : 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 4530 : waste = -1;
335 : int32 nbytes;
336 4530 : OffsetNumber seed_1 = 0,
337 4530 : 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 4530 : maxoff = entryvec->n - 2;
348 4530 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
349 4530 : v->spl_left = (OffsetNumber *) palloc(nbytes);
350 4530 : v->spl_right = (OffsetNumber *) palloc(nbytes);
351 :
352 20770 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
353 : {
354 16240 : _k = GETENTRY(entryvec, k);
355 130398 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
356 : {
357 114158 : size_waste = hemdist(_k, GETENTRY(entryvec, j), siglen);
358 114158 : if (size_waste > waste)
359 : {
360 8745 : waste = size_waste;
361 8745 : seed_1 = k;
362 8745 : seed_2 = j;
363 : }
364 : }
365 : }
366 :
367 4530 : left = v->spl_left;
368 4530 : v->spl_nleft = 0;
369 4530 : right = v->spl_right;
370 4530 : v->spl_nright = 0;
371 :
372 4530 : if (seed_1 == 0 || seed_2 == 0)
373 : {
374 0 : seed_1 = 1;
375 0 : seed_2 = 2;
376 : }
377 :
378 : /* form initial .. */
379 4530 : datum_l = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_1)), siglen,
380 4530 : GETSIGN(GETENTRY(entryvec, seed_1)));
381 4530 : datum_r = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_2)), siglen,
382 4530 : GETSIGN(GETENTRY(entryvec, seed_2)));
383 :
384 4530 : maxoff = OffsetNumberNext(maxoff);
385 : /* sort before ... */
386 4530 : costvector = palloc_array(SPLITCOST, maxoff);
387 29830 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
388 : {
389 25300 : costvector[j - 1].pos = j;
390 25300 : _j = GETENTRY(entryvec, j);
391 25300 : size_alpha = hemdist(datum_l, _j, siglen);
392 25300 : size_beta = hemdist(datum_r, _j, siglen);
393 25300 : costvector[j - 1].cost = abs(size_alpha - size_beta);
394 : }
395 4530 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
396 :
397 4530 : union_l = GETSIGN(datum_l);
398 4530 : union_r = GETSIGN(datum_r);
399 :
400 29830 : for (k = 0; k < maxoff; k++)
401 : {
402 25300 : j = costvector[k].pos;
403 25300 : if (j == seed_1)
404 : {
405 4530 : *left++ = j;
406 4530 : v->spl_nleft++;
407 4530 : continue;
408 : }
409 20770 : else if (j == seed_2)
410 : {
411 4530 : *right++ = j;
412 4530 : v->spl_nright++;
413 4530 : continue;
414 : }
415 16240 : _j = GETENTRY(entryvec, j);
416 16240 : size_alpha = hemdist(datum_l, _j, siglen);
417 16240 : size_beta = hemdist(datum_r, _j, siglen);
418 :
419 16240 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
420 : {
421 8101 : 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 8101 : ptr = GETSIGN(_j);
429 9366141 : LOOPBYTE(siglen)
430 9358040 : union_l[i] |= ptr[i];
431 : }
432 8101 : *left++ = j;
433 8101 : v->spl_nleft++;
434 : }
435 : else
436 : {
437 8139 : 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 8139 : ptr = GETSIGN(_j);
445 9691171 : LOOPBYTE(siglen)
446 9683032 : union_r[i] |= ptr[i];
447 : }
448 8139 : *right++ = j;
449 8139 : v->spl_nright++;
450 : }
451 : }
452 :
453 4530 : *right = *left = FirstOffsetNumber;
454 4530 : pfree(costvector);
455 :
456 4530 : v->spl_ldatum = PointerGetDatum(datum_l);
457 4530 : v->spl_rdatum = PointerGetDatum(datum_r);
458 :
459 4530 : PG_RETURN_POINTER(v);
460 : }
461 :
462 : Datum
463 68767 : g_intbig_consistent(PG_FUNCTION_ARGS)
464 : {
465 68767 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
466 68767 : ArrayType *query = PG_GETARG_ARRAYTYPE_P(1);
467 68767 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
468 : #ifdef NOT_USED
469 : Oid subtype = PG_GETARG_OID(3);
470 : #endif
471 68767 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
472 68767 : int siglen = GET_SIGLEN();
473 : bool retval;
474 :
475 : /* All cases served by this function are inexact */
476 68767 : *recheck = true;
477 :
478 68767 : if (ISALLTRUE(DatumGetPointer(entry->key)))
479 0 : PG_RETURN_BOOL(true);
480 :
481 68767 : if (strategy == BooleanSearchStrategy)
482 : {
483 51584 : retval = signconsistent((QUERYTYPE *) query,
484 51584 : GETSIGN(DatumGetPointer(entry->key)),
485 : siglen,
486 : false);
487 51584 : PG_FREE_IF_COPY(query, 1);
488 51584 : PG_RETURN_BOOL(retval);
489 : }
490 :
491 17183 : CHECKARRVALID(query);
492 :
493 17183 : switch (strategy)
494 : {
495 7586 : case RTOverlapStrategyNumber:
496 7586 : retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key),
497 : query, siglen);
498 7586 : break;
499 1109 : case RTSameStrategyNumber:
500 1109 : if (GIST_LEAF(entry))
501 : {
502 : int i,
503 371 : num = ARRNELEMS(query);
504 371 : int32 *ptr = ARRPTR(query);
505 371 : BITVECP dq = palloc0(siglen),
506 : de;
507 :
508 1484 : while (num--)
509 : {
510 1113 : HASH(dq, *ptr, siglen);
511 1113 : ptr++;
512 : }
513 :
514 371 : de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
515 371 : retval = true;
516 3153 : LOOPBYTE(siglen)
517 : {
518 3151 : if (de[i] != dq[i])
519 : {
520 369 : retval = false;
521 369 : break;
522 : }
523 : }
524 :
525 371 : pfree(dq);
526 : }
527 : else
528 738 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
529 : query, siglen);
530 1109 : break;
531 8488 : case RTContainsStrategyNumber:
532 : case RTOldContainsStrategyNumber:
533 8488 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
534 : query, siglen);
535 8488 : 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 17183 : PG_FREE_IF_COPY(query, 1);
582 17183 : PG_RETURN_BOOL(retval);
583 : }
584 :
585 : Datum
586 10 : g_intbig_options(PG_FUNCTION_ARGS)
587 : {
588 10 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
589 :
590 10 : init_local_reloptions(relopts, sizeof(GISTIntArrayBigOptions));
591 10 : add_local_int_reloption(relopts, "siglen",
592 : "signature length in bytes",
593 : SIGLEN_DEFAULT, 1, SIGLEN_MAX,
594 : offsetof(GISTIntArrayBigOptions, siglen));
595 :
596 10 : PG_RETURN_VOID();
597 : }
|
