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