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