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 85956 : _intbig_alloc(bool allistrue, int siglen, BITVECP sign)
51 : {
52 85956 : int flag = allistrue ? ALLISTRUE : 0;
53 85956 : int size = CALCGTSIZE(flag, siglen);
54 85956 : GISTTYPE *res = (GISTTYPE *) palloc(size);
55 :
56 85956 : SET_VARSIZE(res, size);
57 85956 : res->flag = flag;
58 :
59 85956 : if (!allistrue)
60 : {
61 85956 : if (sign)
62 9046 : memcpy(GETSIGN(res), sign, siglen);
63 : else
64 76910 : memset(GETSIGN(res), 0, siglen);
65 : }
66 :
67 85956 : return res;
68 : }
69 :
70 :
71 : /*********************************************************************
72 : ** intbig functions
73 : *********************************************************************/
74 : static bool
75 7461 : _intbig_overlap(GISTTYPE *a, ArrayType *b, int siglen)
76 : {
77 7461 : int num = ARRNELEMS(b);
78 7461 : int32 *ptr = ARRPTR(b);
79 :
80 7461 : CHECKARRVALID(b);
81 :
82 19117 : while (num--)
83 : {
84 13736 : if (GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
85 2080 : return true;
86 11656 : ptr++;
87 : }
88 :
89 5381 : return false;
90 : }
91 :
92 : static bool
93 9635 : _intbig_contains(GISTTYPE *a, ArrayType *b, int siglen)
94 : {
95 9635 : int num = ARRNELEMS(b);
96 9635 : int32 *ptr = ARRPTR(b);
97 :
98 9635 : CHECKARRVALID(b);
99 :
100 14167 : while (num--)
101 : {
102 12680 : if (!GETBIT(GETSIGN(a), HASHVAL(*ptr, siglen)))
103 8148 : return false;
104 4532 : ptr++;
105 : }
106 :
107 1487 : return true;
108 : }
109 :
110 : Datum
111 62810 : g_intbig_same(PG_FUNCTION_ARGS)
112 : {
113 62810 : GISTTYPE *a = (GISTTYPE *) PG_GETARG_POINTER(0);
114 62810 : GISTTYPE *b = (GISTTYPE *) PG_GETARG_POINTER(1);
115 62810 : bool *result = (bool *) PG_GETARG_POINTER(2);
116 62810 : int siglen = GET_SIGLEN();
117 :
118 62810 : if (ISALLTRUE(a) && ISALLTRUE(b))
119 0 : *result = true;
120 62810 : else if (ISALLTRUE(a))
121 0 : *result = false;
122 62810 : else if (ISALLTRUE(b))
123 0 : *result = false;
124 : else
125 : {
126 : int32 i;
127 62810 : BITVECP sa = GETSIGN(a),
128 62810 : sb = GETSIGN(b);
129 :
130 62810 : *result = true;
131 46251779 : LOOPBYTE(siglen)
132 : {
133 46223540 : if (sa[i] != sb[i])
134 : {
135 34571 : *result = false;
136 34571 : break;
137 : }
138 : }
139 : }
140 62810 : PG_RETURN_POINTER(result);
141 : }
142 :
143 : Datum
144 57138 : g_intbig_compress(PG_FUNCTION_ARGS)
145 : {
146 57138 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
147 57138 : int siglen = GET_SIGLEN();
148 :
149 57138 : 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 43624 : else if (!ISALLTRUE(DatumGetPointer(entry->key)))
183 : {
184 : GISTENTRY *retval;
185 : int i;
186 43624 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
187 : GISTTYPE *res;
188 :
189 57570 : LOOPBYTE(siglen)
190 : {
191 57570 : if ((sign[i] & 0xff) != 0xff)
192 43624 : 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 498808 : hemdistsign(BITVECP a, BITVECP b, int siglen)
216 : {
217 : int i,
218 : diff,
219 498808 : dist = 0;
220 :
221 451663436 : LOOPBYTE(siglen)
222 : {
223 451164628 : diff = (unsigned char) (a[i] ^ b[i]);
224 : /* Using the popcount functions here isn't likely to win */
225 451164628 : dist += pg_number_of_ones[diff];
226 : }
227 498808 : return dist;
228 : }
229 :
230 : static int
231 498808 : hemdist(GISTTYPE *a, GISTTYPE *b, int siglen)
232 : {
233 498808 : 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 498808 : else if (ISALLTRUE(b))
241 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
242 :
243 498808 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
244 : }
245 :
246 : Datum
247 588702 : g_intbig_decompress(PG_FUNCTION_ARGS)
248 : {
249 588702 : PG_RETURN_DATUM(PG_GETARG_DATUM(0));
250 : }
251 :
252 : static int32
253 127048 : unionkey(BITVECP sbase, GISTTYPE *add, int siglen)
254 : {
255 : int32 i;
256 127048 : BITVECP sadd = GETSIGN(add);
257 :
258 127048 : if (ISALLTRUE(add))
259 0 : return 1;
260 210909592 : LOOPBYTE(siglen)
261 210782544 : sbase[i] |= sadd[i];
262 127048 : return 0;
263 : }
264 :
265 : Datum
266 63396 : g_intbig_union(PG_FUNCTION_ARGS)
267 : {
268 63396 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
269 63396 : int *size = (int *) PG_GETARG_POINTER(1);
270 63396 : int siglen = GET_SIGLEN();
271 : int32 i;
272 63396 : GISTTYPE *result = _intbig_alloc(false, siglen, NULL);
273 63396 : BITVECP base = GETSIGN(result);
274 :
275 190444 : for (i = 0; i < entryvec->n; i++)
276 : {
277 127048 : 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 63396 : *size = VARSIZE(result);
286 :
287 63396 : PG_RETURN_POINTER(result);
288 : }
289 :
290 : Datum
291 300433 : g_intbig_penalty(PG_FUNCTION_ARGS)
292 : {
293 300433 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
294 300433 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
295 300433 : float *penalty = (float *) PG_GETARG_POINTER(2);
296 300433 : GISTTYPE *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
297 300433 : GISTTYPE *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
298 300433 : int siglen = GET_SIGLEN();
299 :
300 300433 : *penalty = hemdist(origval, newval, siglen);
301 300433 : PG_RETURN_POINTER(penalty);
302 : }
303 :
304 :
305 : typedef struct
306 : {
307 : OffsetNumber pos;
308 : int32 cost;
309 : } SPLITCOST;
310 :
311 : static int
312 39891 : comparecost(const void *a, const void *b)
313 : {
314 79782 : return pg_cmp_s32(((const SPLITCOST *) a)->cost,
315 39891 : ((const SPLITCOST *) b)->cost);
316 : }
317 :
318 :
319 : Datum
320 4523 : g_intbig_picksplit(PG_FUNCTION_ARGS)
321 : {
322 4523 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
323 4523 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
324 4523 : 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 4523 : waste = -1;
335 : int32 nbytes;
336 4523 : OffsetNumber seed_1 = 0,
337 4523 : 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 4523 : maxoff = entryvec->n - 2;
348 4523 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
349 4523 : v->spl_left = (OffsetNumber *) palloc(nbytes);
350 4523 : v->spl_right = (OffsetNumber *) palloc(nbytes);
351 :
352 20818 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
353 : {
354 16295 : _k = GETENTRY(entryvec, k);
355 131398 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
356 : {
357 115103 : size_waste = hemdist(_k, GETENTRY(entryvec, j), siglen);
358 115103 : if (size_waste > waste)
359 : {
360 8830 : waste = size_waste;
361 8830 : seed_1 = k;
362 8830 : seed_2 = j;
363 : }
364 : }
365 : }
366 :
367 4523 : left = v->spl_left;
368 4523 : v->spl_nleft = 0;
369 4523 : right = v->spl_right;
370 4523 : v->spl_nright = 0;
371 :
372 4523 : if (seed_1 == 0 || seed_2 == 0)
373 : {
374 0 : seed_1 = 1;
375 0 : seed_2 = 2;
376 : }
377 :
378 : /* form initial .. */
379 4523 : datum_l = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_1)), siglen,
380 4523 : GETSIGN(GETENTRY(entryvec, seed_1)));
381 4523 : datum_r = _intbig_alloc(ISALLTRUE(GETENTRY(entryvec, seed_2)), siglen,
382 4523 : GETSIGN(GETENTRY(entryvec, seed_2)));
383 :
384 4523 : maxoff = OffsetNumberNext(maxoff);
385 : /* sort before ... */
386 4523 : costvector = palloc_array(SPLITCOST, maxoff);
387 29864 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
388 : {
389 25341 : costvector[j - 1].pos = j;
390 25341 : _j = GETENTRY(entryvec, j);
391 25341 : size_alpha = hemdist(datum_l, _j, siglen);
392 25341 : size_beta = hemdist(datum_r, _j, siglen);
393 25341 : costvector[j - 1].cost = abs(size_alpha - size_beta);
394 : }
395 4523 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
396 :
397 4523 : union_l = GETSIGN(datum_l);
398 4523 : union_r = GETSIGN(datum_r);
399 :
400 29864 : for (k = 0; k < maxoff; k++)
401 : {
402 25341 : j = costvector[k].pos;
403 25341 : if (j == seed_1)
404 : {
405 4523 : *left++ = j;
406 4523 : v->spl_nleft++;
407 4523 : continue;
408 : }
409 20818 : else if (j == seed_2)
410 : {
411 4523 : *right++ = j;
412 4523 : v->spl_nright++;
413 4523 : continue;
414 : }
415 16295 : _j = GETENTRY(entryvec, j);
416 16295 : size_alpha = hemdist(datum_l, _j, siglen);
417 16295 : size_beta = hemdist(datum_r, _j, siglen);
418 :
419 16295 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
420 : {
421 8134 : 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 8134 : ptr = GETSIGN(_j);
429 9390438 : LOOPBYTE(siglen)
430 9382304 : union_l[i] |= ptr[i];
431 : }
432 8134 : *left++ = j;
433 8134 : v->spl_nleft++;
434 : }
435 : else
436 : {
437 8161 : 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 8161 : ptr = GETSIGN(_j);
445 9645349 : LOOPBYTE(siglen)
446 9637188 : union_r[i] |= ptr[i];
447 : }
448 8161 : *right++ = j;
449 8161 : v->spl_nright++;
450 : }
451 : }
452 :
453 4523 : *right = *left = FirstOffsetNumber;
454 4523 : pfree(costvector);
455 :
456 4523 : v->spl_ldatum = PointerGetDatum(datum_l);
457 4523 : v->spl_rdatum = PointerGetDatum(datum_r);
458 :
459 4523 : PG_RETURN_POINTER(v);
460 : }
461 :
462 : Datum
463 69421 : g_intbig_consistent(PG_FUNCTION_ARGS)
464 : {
465 69421 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
466 69421 : ArrayType *query = PG_GETARG_ARRAYTYPE_P(1);
467 69421 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
468 : #ifdef NOT_USED
469 : Oid subtype = PG_GETARG_OID(3);
470 : #endif
471 69421 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
472 69421 : int siglen = GET_SIGLEN();
473 : bool retval;
474 :
475 : /* All cases served by this function are inexact */
476 69421 : *recheck = true;
477 :
478 69421 : if (ISALLTRUE(DatumGetPointer(entry->key)))
479 0 : PG_RETURN_BOOL(true);
480 :
481 69421 : if (strategy == BooleanSearchStrategy)
482 : {
483 51706 : retval = signconsistent((QUERYTYPE *) query,
484 51706 : GETSIGN(DatumGetPointer(entry->key)),
485 : siglen,
486 : false);
487 51706 : PG_FREE_IF_COPY(query, 1);
488 51706 : PG_RETURN_BOOL(retval);
489 : }
490 :
491 17715 : CHECKARRVALID(query);
492 :
493 17715 : switch (strategy)
494 : {
495 7461 : case RTOverlapStrategyNumber:
496 7461 : retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key),
497 : query, siglen);
498 7461 : break;
499 1314 : case RTSameStrategyNumber:
500 1314 : if (GIST_LEAF(entry))
501 : {
502 : int i,
503 619 : num = ARRNELEMS(query);
504 619 : int32 *ptr = ARRPTR(query);
505 619 : BITVECP dq = palloc0(siglen),
506 : de;
507 :
508 2476 : while (num--)
509 : {
510 1857 : HASH(dq, *ptr, siglen);
511 1857 : ptr++;
512 : }
513 :
514 619 : de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
515 619 : retval = true;
516 3734 : LOOPBYTE(siglen)
517 : {
518 3732 : if (de[i] != dq[i])
519 : {
520 617 : retval = false;
521 617 : break;
522 : }
523 : }
524 :
525 619 : pfree(dq);
526 : }
527 : else
528 695 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
529 : query, siglen);
530 1314 : break;
531 8940 : case RTContainsStrategyNumber:
532 : case RTOldContainsStrategyNumber:
533 8940 : retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key),
534 : query, siglen);
535 8940 : 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 17715 : PG_FREE_IF_COPY(query, 1);
582 17715 : 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 : }
|
