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 171494 : _intbig_alloc(bool allistrue, int siglen, BITVECP sign)
53 : {
54 171494 : int flag = allistrue ? ALLISTRUE : 0;
55 171494 : int size = CALCGTSIZE(flag, siglen);
56 171494 : GISTTYPE *res = (GISTTYPE *) palloc(size);
57 :
58 171494 : SET_VARSIZE(res, size);
59 171494 : res->flag = flag;
60 :
61 171494 : if (!allistrue)
62 : {
63 171494 : if (sign)
64 18196 : memcpy(GETSIGN(res), sign, siglen);
65 : else
66 153298 : memset(GETSIGN(res), 0, siglen);
67 : }
68 :
69 171494 : return res;
70 : }
71 :
72 :
73 : /*********************************************************************
74 : ** intbig functions
75 : *********************************************************************/
76 : static bool
77 15034 : _intbig_overlap(GISTTYPE *a, ArrayType *b, int siglen)
78 : {
79 15034 : int num = ARRNELEMS(b);
80 15034 : int32 *ptr = ARRPTR(b);
81 :
82 15034 : CHECKARRVALID(b);
83 :
84 38618 : while (num--)
85 : {
86 27706 : if (GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
87 4122 : return true;
88 23584 : ptr++;
89 : }
90 :
91 10912 : return false;
92 : }
93 :
94 : static bool
95 17980 : _intbig_contains(GISTTYPE *a, ArrayType *b, int siglen)
96 : {
97 17980 : int num = ARRNELEMS(b);
98 17980 : int32 *ptr = ARRPTR(b);
99 :
100 17980 : CHECKARRVALID(b);
101 :
102 26972 : while (num--)
103 : {
104 24024 : if (!GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
105 15032 : return false;
106 8992 : ptr++;
107 : }
108 :
109 2948 : return true;
110 : }
111 :
112 : Datum
113 125428 : g_intbig_same(PG_FUNCTION_ARGS)
114 : {
115 125428 : GISTTYPE *a = (GISTTYPE *) PG_GETARG_POINTER(0);
116 125428 : GISTTYPE *b = (GISTTYPE *) PG_GETARG_POINTER(1);
117 125428 : bool *result = (bool *) PG_GETARG_POINTER(2);
118 125428 : int siglen = GET_SIGLEN();
119 :
120 125428 : if (ISALLTRUE(a) && ISALLTRUE(b))
121 0 : *result = true;
122 125428 : else if (ISALLTRUE(a))
123 0 : *result = false;
124 125428 : else if (ISALLTRUE(b))
125 0 : *result = false;
126 : else
127 : {
128 : int32 i;
129 125428 : BITVECP sa = GETSIGN(a),
130 125428 : sb = GETSIGN(b);
131 :
132 125428 : *result = true;
133 92902418 : LOOPBYTE(siglen)
134 : {
135 92845640 : if (sa[i] != sb[i])
136 : {
137 68650 : *result = false;
138 68650 : break;
139 : }
140 : }
141 : }
142 125428 : PG_RETURN_POINTER(result);
143 : }
144 :
145 : Datum
146 113878 : g_intbig_compress(PG_FUNCTION_ARGS)
147 : {
148 113878 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
149 113878 : int siglen = GET_SIGLEN();
150 :
151 113878 : 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 86850 : else if (!ISALLTRUE(DatumGetPointer(entry->key)))
185 : {
186 : GISTENTRY *retval;
187 : int i;
188 86850 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
189 : GISTTYPE *res;
190 :
191 110956 : LOOPBYTE(siglen)
192 : {
193 110956 : if ((sign[i] & 0xff) != 0xff)
194 86850 : 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 990198 : hemdistsign(BITVECP a, BITVECP b, int siglen)
218 : {
219 : int i,
220 : diff,
221 990198 : dist = 0;
222 :
223 902896070 : LOOPBYTE(siglen)
224 : {
225 901905872 : diff = (unsigned char) (a[i] ^ b[i]);
226 : /* Using the popcount functions here isn't likely to win */
227 901905872 : dist += pg_number_of_ones[diff];
228 : }
229 990198 : return dist;
230 : }
231 :
232 : static int
233 990198 : hemdist(GISTTYPE *a, GISTTYPE *b, int siglen)
234 : {
235 990198 : 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 990198 : else if (ISALLTRUE(b))
243 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
244 :
245 990198 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
246 : }
247 :
248 : Datum
249 1164782 : g_intbig_decompress(PG_FUNCTION_ARGS)
250 : {
251 1164782 : PG_RETURN_DATUM(PG_GETARG_DATUM(0));
252 : }
253 :
254 : static int32
255 252780 : unionkey(BITVECP sbase, GISTTYPE *add, int siglen)
256 : {
257 : int32 i;
258 252780 : BITVECP sadd = GETSIGN(add);
259 :
260 252780 : if (ISALLTRUE(add))
261 0 : return 1;
262 420401772 : LOOPBYTE(siglen)
263 420148992 : sbase[i] |= sadd[i];
264 252780 : return 0;
265 : }
266 :
267 : Datum
268 126270 : g_intbig_union(PG_FUNCTION_ARGS)
269 : {
270 126270 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
271 126270 : int *size = (int *) PG_GETARG_POINTER(1);
272 126270 : int siglen = GET_SIGLEN();
273 : int32 i;
274 126270 : GISTTYPE *result = _intbig_alloc(false, siglen, NULL);
275 126270 : BITVECP base = GETSIGN(result);
276 :
277 379050 : for (i = 0; i < entryvec->n; i++)
278 : {
279 252780 : 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 126270 : *size = VARSIZE(result);
288 :
289 126270 : PG_RETURN_POINTER(result);
290 : }
291 :
292 : Datum
293 595332 : g_intbig_penalty(PG_FUNCTION_ARGS)
294 : {
295 595332 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
296 595332 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
297 595332 : float *penalty = (float *) PG_GETARG_POINTER(2);
298 595332 : GISTTYPE *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
299 595332 : GISTTYPE *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
300 595332 : int siglen = GET_SIGLEN();
301 :
302 595332 : *penalty = hemdist(origval, newval, siglen);
303 595332 : PG_RETURN_POINTER(penalty);
304 : }
305 :
306 :
307 : typedef struct
308 : {
309 : OffsetNumber pos;
310 : int32 cost;
311 : } SPLITCOST;
312 :
313 : static int
314 79702 : comparecost(const void *a, const void *b)
315 : {
316 79702 : return pg_cmp_s32(((const SPLITCOST *) a)->cost,
317 : ((const SPLITCOST *) b)->cost);
318 : }
319 :
320 :
321 : Datum
322 9098 : g_intbig_picksplit(PG_FUNCTION_ARGS)
323 : {
324 9098 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
325 9098 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
326 9098 : 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 9098 : waste = -1;
337 : int32 nbytes;
338 9098 : OffsetNumber seed_1 = 0,
339 9098 : 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 9098 : maxoff = entryvec->n - 2;
350 9098 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
351 9098 : v->spl_left = (OffsetNumber *) palloc(nbytes);
352 9098 : v->spl_right = (OffsetNumber *) palloc(nbytes);
353 :
354 41648 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
355 : {
356 32550 : _k = GETENTRY(entryvec, k);
357 260824 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
358 : {
359 228274 : size_waste = hemdist(_k, GETENTRY(entryvec, j), siglen);
360 228274 : if (size_waste > waste)
361 : {
362 17586 : waste = size_waste;
363 17586 : seed_1 = k;
364 17586 : seed_2 = j;
365 : }
366 : }
367 : }
368 :
369 9098 : left = v->spl_left;
370 9098 : v->spl_nleft = 0;
371 9098 : right = v->spl_right;
372 9098 : v->spl_nright = 0;
373 :
374 9098 : if (seed_1 == 0 || seed_2 == 0)
375 : {
376 0 : seed_1 = 1;
377 0 : seed_2 = 2;
378 : }
379 :
380 : /* form initial .. */
381 9098 : datum_l = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_1)), siglen,
382 9098 : GETSIGN(GETENTRY(entryvec, seed_1)));
383 9098 : datum_r = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_2)), siglen,
384 9098 : GETSIGN(GETENTRY(entryvec, seed_2)));
385 :
386 9098 : maxoff = OffsetNumberNext(maxoff);
387 : /* sort before ... */
388 9098 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
389 59844 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
390 : {
391 50746 : costvector[j - 1].pos = j;
392 50746 : _j = GETENTRY(entryvec, j);
393 50746 : size_alpha = hemdist(datum_l, _j, siglen);
394 50746 : size_beta = hemdist(datum_r, _j, siglen);
395 50746 : costvector[j - 1].cost = abs(size_alpha - size_beta);
396 : }
397 9098 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
398 :
399 9098 : union_l = GETSIGN(datum_l);
400 9098 : union_r = GETSIGN(datum_r);
401 :
402 59844 : for (k = 0; k < maxoff; k++)
403 : {
404 50746 : j = costvector[k].pos;
405 50746 : if (j == seed_1)
406 : {
407 9098 : *left++ = j;
408 9098 : v->spl_nleft++;
409 9098 : continue;
410 : }
411 41648 : else if (j == seed_2)
412 : {
413 9098 : *right++ = j;
414 9098 : v->spl_nright++;
415 9098 : continue;
416 : }
417 32550 : _j = GETENTRY(entryvec, j);
418 32550 : size_alpha = hemdist(datum_l, _j, siglen);
419 32550 : size_beta = hemdist(datum_r, _j, siglen);
420 :
421 32550 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
422 : {
423 16028 : 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 16028 : ptr = GETSIGN(_j);
431 18450812 : LOOPBYTE(siglen)
432 18434784 : union_l[i] |= ptr[i];
433 : }
434 16028 : *left++ = j;
435 16028 : v->spl_nleft++;
436 : }
437 : else
438 : {
439 16522 : 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 16522 : ptr = GETSIGN(_j);
447 19816194 : LOOPBYTE(siglen)
448 19799672 : union_r[i] |= ptr[i];
449 : }
450 16522 : *right++ = j;
451 16522 : v->spl_nright++;
452 : }
453 : }
454 :
455 9098 : *right = *left = FirstOffsetNumber;
456 9098 : pfree(costvector);
457 :
458 9098 : v->spl_ldatum = PointerGetDatum(datum_l);
459 9098 : v->spl_rdatum = PointerGetDatum(datum_r);
460 :
461 9098 : PG_RETURN_POINTER(v);
462 : }
463 :
464 : Datum
465 136208 : g_intbig_consistent(PG_FUNCTION_ARGS)
466 : {
467 136208 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
468 136208 : ArrayType *query = PG_GETARG_ARRAYTYPE_P(1);
469 136208 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
470 :
471 : /* Oid subtype = PG_GETARG_OID(3); */
472 136208 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
473 136208 : int siglen = GET_SIGLEN();
474 : bool retval;
475 :
476 : /* All cases served by this function are inexact */
477 136208 : *recheck = true;
478 :
479 136208 : if (ISALLTRUE(DatumGetPointer(entry->key)))
480 0 : PG_RETURN_BOOL(true);
481 :
482 136208 : if (strategy == BooleanSearchStrategy)
483 : {
484 101776 : retval = signconsistent((QUERYTYPE *) query,
485 101776 : GETSIGN(DatumGetPointer(entry->key)),
486 : siglen,
487 : false);
488 101776 : PG_FREE_IF_COPY(query, 1);
489 101776 : PG_RETURN_BOOL(retval);
490 : }
491 :
492 34432 : CHECKARRVALID(query);
493 :
494 34432 : switch (strategy)
495 : {
496 15034 : case RTOverlapStrategyNumber:
497 15034 : retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key),
498 : query, siglen);
499 15034 : break;
500 2730 : case RTSameStrategyNumber:
501 2730 : if (GIST_LEAF(entry))
502 : {
503 : int i,
504 1418 : num = ARRNELEMS(query);
505 1418 : int32 *ptr = ARRPTR(query);
506 1418 : BITVECP dq = palloc0(siglen),
507 : de;
508 :
509 5672 : while (num--)
510 : {
511 4254 : HASH(dq, *ptr, siglen);
512 4254 : ptr++;
513 : }
514 :
515 1418 : de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
516 1418 : retval = true;
517 7924 : LOOPBYTE(siglen)
518 : {
519 7920 : if (de[i] != dq[i])
520 : {
521 1414 : retval = false;
522 1414 : break;
523 : }
524 : }
525 :
526 1418 : pfree(dq);
527 : }
528 : else
529 1312 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
530 : query, siglen);
531 2730 : break;
532 16668 : case RTContainsStrategyNumber:
533 : case RTOldContainsStrategyNumber:
534 16668 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
535 : query, siglen);
536 16668 : 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 34432 : PG_FREE_IF_COPY(query, 1);
583 34432 : 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 : }
|
