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