TLA Line data Source code
1 : /*
2 : * contrib/pg_trgm/trgm_gist.c
3 : */
4 : #include "postgres.h"
5 :
6 : #include "access/reloptions.h"
7 : #include "access/stratnum.h"
8 : #include "fmgr.h"
9 : #include "port/pg_bitutils.h"
10 : #include "trgm.h"
11 : #include "varatt.h"
12 :
13 : /* gist_trgm_ops opclass options */
14 : typedef struct
15 : {
16 : int32 vl_len_; /* varlena header (do not touch directly!) */
17 : int siglen; /* signature length in bytes */
18 : } TrgmGistOptions;
19 :
20 : #define GET_SIGLEN() (PG_HAS_OPCLASS_OPTIONS() ? \
21 : ((TrgmGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
22 : SIGLEN_DEFAULT)
23 :
24 : typedef struct
25 : {
26 : /* most recent inputs to gtrgm_consistent */
27 : StrategyNumber strategy;
28 : text *query;
29 : /* extracted trigrams for query */
30 : TRGM *trigrams;
31 : /* if a regex operator, the extracted graph */
32 : TrgmPackedGraph *graph;
33 :
34 : /*
35 : * The "query" and "trigrams" are stored in the same palloc block as this
36 : * cache struct, at MAXALIGN'ed offsets. The graph however isn't.
37 : */
38 : } gtrgm_consistent_cache;
39 :
40 : #define GETENTRY(vec,pos) ((TRGM *) DatumGetPointer((vec)->vector[(pos)].key))
41 :
42 :
43 GIC 1 : PG_FUNCTION_INFO_V1(gtrgm_in);
44 CBC 1 : PG_FUNCTION_INFO_V1(gtrgm_out);
45 4 : PG_FUNCTION_INFO_V1(gtrgm_compress);
46 4 : PG_FUNCTION_INFO_V1(gtrgm_decompress);
47 4 : PG_FUNCTION_INFO_V1(gtrgm_consistent);
48 4 : PG_FUNCTION_INFO_V1(gtrgm_distance);
49 4 : PG_FUNCTION_INFO_V1(gtrgm_union);
50 4 : PG_FUNCTION_INFO_V1(gtrgm_same);
51 4 : PG_FUNCTION_INFO_V1(gtrgm_penalty);
52 4 : PG_FUNCTION_INFO_V1(gtrgm_picksplit);
53 4 : PG_FUNCTION_INFO_V1(gtrgm_options);
54 ECB :
55 :
56 : Datum
57 UIC 0 : gtrgm_in(PG_FUNCTION_ARGS)
58 EUB : {
59 UNC 0 : ereport(ERROR,
60 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
61 : errmsg("cannot accept a value of type %s", "gtrgm")));
62 :
63 : PG_RETURN_VOID(); /* keep compiler quiet */
64 : }
65 :
66 : Datum
67 UIC 0 : gtrgm_out(PG_FUNCTION_ARGS)
68 : {
69 UNC 0 : ereport(ERROR,
70 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
71 : errmsg("cannot display a value of type %s", "gtrgm")));
72 :
73 : PG_RETURN_VOID(); /* keep compiler quiet */
74 EUB : }
75 :
76 : static TRGM *
77 GIC 26625 : gtrgm_alloc(bool isalltrue, int siglen, BITVECP sign)
78 : {
79 26625 : int flag = SIGNKEY | (isalltrue ? ALLISTRUE : 0);
80 26625 : int size = CALCGTSIZE(flag, siglen);
81 26625 : TRGM *res = palloc(size);
82 :
83 26625 : SET_VARSIZE(res, size);
84 CBC 26625 : res->flag = flag;
85 :
86 26625 : if (!isalltrue)
87 ECB : {
88 CBC 26625 : if (sign)
89 GIC 536 : memcpy(GETSIGN(res), sign, siglen);
90 ECB : else
91 CBC 26089 : memset(GETSIGN(res), 0, siglen);
92 : }
93 ECB :
94 GIC 26625 : return res;
95 ECB : }
96 :
97 : static void
98 CBC 45790 : makesign(BITVECP sign, TRGM *a, int siglen)
99 : {
100 : int32 k,
101 45790 : len = ARRNELEM(a);
102 GIC 45790 : trgm *ptr = GETARR(a);
103 45790 : int32 tmp = 0;
104 :
105 GNC 45790 : MemSet(sign, 0, siglen);
106 GIC 45790 : SETBIT(sign, SIGLENBIT(siglen)); /* set last unused bit */
107 443775 : for (k = 0; k < len; k++)
108 ECB : {
109 CBC 397985 : CPTRGM(((char *) &tmp), ptr + k);
110 397985 : HASH(sign, tmp, siglen);
111 : }
112 45790 : }
113 ECB :
114 : Datum
115 GIC 25533 : gtrgm_compress(PG_FUNCTION_ARGS)
116 ECB : {
117 CBC 25533 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
118 GIC 25533 : int siglen = GET_SIGLEN();
119 CBC 25533 : GISTENTRY *retval = entry;
120 :
121 GIC 25533 : if (entry->leafkey)
122 ECB : { /* trgm */
123 : TRGM *res;
124 CBC 23402 : text *val = DatumGetTextPP(entry->key);
125 ECB :
126 CBC 23402 : res = generate_trgm(VARDATA_ANY(val), VARSIZE_ANY_EXHDR(val));
127 GIC 23402 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
128 CBC 23402 : gistentryinit(*retval, PointerGetDatum(res),
129 : entry->rel, entry->page,
130 : entry->offset, false);
131 ECB : }
132 GIC 2131 : else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
133 CBC 2131 : !ISALLTRUE(DatumGetPointer(entry->key)))
134 ECB : {
135 : int32 i;
136 : TRGM *res;
137 GIC 2131 : BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
138 :
139 CBC 2288 : LOOPBYTE(siglen)
140 ECB : {
141 GIC 2288 : if ((sign[i] & 0xff) != 0xff)
142 2131 : PG_RETURN_POINTER(retval);
143 : }
144 ECB :
145 UIC 0 : res = gtrgm_alloc(true, siglen, sign);
146 LBC 0 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
147 UIC 0 : gistentryinit(*retval, PointerGetDatum(res),
148 ECB : entry->rel, entry->page,
149 : entry->offset, false);
150 : }
151 GIC 23402 : PG_RETURN_POINTER(retval);
152 EUB : }
153 :
154 : Datum
155 GIC 1374372 : gtrgm_decompress(PG_FUNCTION_ARGS)
156 : {
157 1374372 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
158 ECB : GISTENTRY *retval;
159 : text *key;
160 :
161 GIC 1374372 : key = DatumGetTextPP(entry->key);
162 ECB :
163 GIC 1374372 : if (key != (text *) DatumGetPointer(entry->key))
164 ECB : {
165 : /* need to pass back the decompressed item */
166 UIC 0 : retval = palloc(sizeof(GISTENTRY));
167 0 : gistentryinit(*retval, PointerGetDatum(key),
168 ECB : entry->rel, entry->page, entry->offset, entry->leafkey);
169 UIC 0 : PG_RETURN_POINTER(retval);
170 ECB : }
171 : else
172 : {
173 EUB : /* we can return the entry as-is */
174 GBC 1374372 : PG_RETURN_POINTER(entry);
175 : }
176 EUB : }
177 :
178 : static int32
179 GIC 643 : cnt_sml_sign_common(TRGM *qtrg, BITVECP sign, int siglen)
180 : {
181 CBC 643 : int32 count = 0;
182 : int32 k,
183 GIC 643 : len = ARRNELEM(qtrg);
184 643 : trgm *ptr = GETARR(qtrg);
185 643 : int32 tmp = 0;
186 ECB :
187 GIC 5860 : for (k = 0; k < len; k++)
188 ECB : {
189 GIC 5217 : CPTRGM(((char *) &tmp), ptr + k);
190 CBC 5217 : count += GETBIT(sign, HASHVAL(tmp, siglen));
191 ECB : }
192 :
193 GIC 643 : return count;
194 ECB : }
195 :
196 : Datum
197 CBC 38288 : gtrgm_consistent(PG_FUNCTION_ARGS)
198 : {
199 GIC 38288 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
200 CBC 38288 : text *query = PG_GETARG_TEXT_P(1);
201 GIC 38288 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
202 :
203 : /* Oid subtype = PG_GETARG_OID(3); */
204 CBC 38288 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
205 GIC 38288 : int siglen = GET_SIGLEN();
206 CBC 38288 : TRGM *key = (TRGM *) DatumGetPointer(entry->key);
207 ECB : TRGM *qtrg;
208 : bool res;
209 GIC 38288 : Size querysize = VARSIZE(query);
210 : gtrgm_consistent_cache *cache;
211 ECB : double nlimit;
212 :
213 : /*
214 : * We keep the extracted trigrams in cache, because trigram extraction is
215 : * relatively CPU-expensive. When trying to reuse a cached value, check
216 : * strategy number not just query itself, because trigram extraction
217 : * depends on strategy.
218 : *
219 : * The cached structure is a single palloc chunk containing the
220 : * gtrgm_consistent_cache header, then the input query (4-byte length
221 : * word, uncompressed, starting at a MAXALIGN boundary), then the TRGM
222 : * value (also starting at a MAXALIGN boundary). However we don't try to
223 : * include the regex graph (if any) in that struct. (XXX currently, this
224 : * approach can leak regex graphs across index rescans. Not clear if
225 : * that's worth fixing.)
226 : */
227 GIC 38288 : cache = (gtrgm_consistent_cache *) fcinfo->flinfo->fn_extra;
228 38288 : if (cache == NULL ||
229 38232 : cache->strategy != strategy ||
230 38232 : VARSIZE(cache->query) != querysize ||
231 38232 : memcmp((char *) cache->query, (char *) query, querysize) != 0)
232 : {
233 : gtrgm_consistent_cache *newcache;
234 CBC 56 : TrgmPackedGraph *graph = NULL;
235 ECB : Size qtrgsize;
236 :
237 CBC 56 : switch (strategy)
238 ECB : {
239 GIC 28 : case SimilarityStrategyNumber:
240 : case WordSimilarityStrategyNumber:
241 ECB : case StrictWordSimilarityStrategyNumber:
242 : case EqualStrategyNumber:
243 GIC 28 : qtrg = generate_trgm(VARDATA(query),
244 CBC 28 : querysize - VARHDRSZ);
245 GIC 28 : break;
246 CBC 7 : case ILikeStrategyNumber:
247 : #ifndef IGNORECASE
248 : elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
249 : #endif
250 ECB : /* FALL THRU */
251 : case LikeStrategyNumber:
252 CBC 7 : qtrg = generate_wildcard_trgm(VARDATA(query),
253 7 : querysize - VARHDRSZ);
254 GIC 7 : break;
255 21 : case RegExpICaseStrategyNumber:
256 : #ifndef IGNORECASE
257 : elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
258 : #endif
259 ECB : /* FALL THRU */
260 : case RegExpStrategyNumber:
261 CBC 21 : qtrg = createTrgmNFA(query, PG_GET_COLLATION(),
262 21 : &graph, fcinfo->flinfo->fn_mcxt);
263 : /* just in case an empty array is returned ... */
264 GIC 21 : if (qtrg && ARRNELEM(qtrg) <= 0)
265 : {
266 UIC 0 : pfree(qtrg);
267 0 : qtrg = NULL;
268 ECB : }
269 CBC 21 : break;
270 UIC 0 : default:
271 LBC 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
272 : qtrg = NULL; /* keep compiler quiet */
273 EUB : break;
274 : }
275 :
276 CBC 56 : qtrgsize = qtrg ? VARSIZE(qtrg) : 0;
277 EUB :
278 : newcache = (gtrgm_consistent_cache *)
279 GIC 56 : MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
280 : MAXALIGN(sizeof(gtrgm_consistent_cache)) +
281 56 : MAXALIGN(querysize) +
282 : qtrgsize);
283 ECB :
284 GIC 56 : newcache->strategy = strategy;
285 56 : newcache->query = (text *)
286 ECB : ((char *) newcache + MAXALIGN(sizeof(gtrgm_consistent_cache)));
287 GIC 56 : memcpy((char *) newcache->query, (char *) query, querysize);
288 CBC 56 : if (qtrg)
289 : {
290 GIC 52 : newcache->trigrams = (TRGM *)
291 CBC 52 : ((char *) newcache->query + MAXALIGN(querysize));
292 52 : memcpy((char *) newcache->trigrams, (char *) qtrg, qtrgsize);
293 : /* release qtrg in case it was made in fn_mcxt */
294 52 : pfree(qtrg);
295 ECB : }
296 : else
297 CBC 4 : newcache->trigrams = NULL;
298 56 : newcache->graph = graph;
299 ECB :
300 GIC 56 : if (cache)
301 LBC 0 : pfree(cache);
302 GIC 56 : fcinfo->flinfo->fn_extra = (void *) newcache;
303 56 : cache = newcache;
304 ECB : }
305 :
306 GIC 38288 : qtrg = cache->trigrams;
307 ECB :
308 GBC 38288 : switch (strategy)
309 ECB : {
310 CBC 35887 : case SimilarityStrategyNumber:
311 : case WordSimilarityStrategyNumber:
312 : case StrictWordSimilarityStrategyNumber:
313 ECB :
314 : /*
315 : * Similarity search is exact. (Strict) word similarity search is
316 : * inexact
317 : */
318 GIC 35887 : *recheck = (strategy != SimilarityStrategyNumber);
319 :
320 35887 : nlimit = index_strategy_get_limit(strategy);
321 :
322 35887 : if (GIST_LEAF(entry))
323 : { /* all leafs contains orig trgm */
324 35282 : double tmpsml = cnt_sml(qtrg, key, *recheck);
325 ECB :
326 GIC 35282 : res = (tmpsml >= nlimit);
327 ECB : }
328 GIC 605 : else if (ISALLTRUE(key))
329 ECB : { /* non-leaf contains signature */
330 UIC 0 : res = true;
331 ECB : }
332 : else
333 : { /* non-leaf contains signature */
334 GIC 605 : int32 count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
335 CBC 605 : int32 len = ARRNELEM(qtrg);
336 :
337 GBC 605 : if (len == 0)
338 UIC 0 : res = false;
339 : else
340 GIC 605 : res = (((((float8) count) / ((float8) len))) >= nlimit);
341 ECB : }
342 CBC 35887 : break;
343 GIC 190 : case ILikeStrategyNumber:
344 ECB : #ifndef IGNORECASE
345 EUB : elog(ERROR, "cannot handle ~~* with case-sensitive trigrams");
346 : #endif
347 ECB : /* FALL THRU */
348 : case LikeStrategyNumber:
349 : case EqualStrategyNumber:
350 : /* Wildcard and equal search are inexact */
351 GIC 190 : *recheck = true;
352 :
353 : /*
354 : * Check if all the extracted trigrams can be present in child
355 : * nodes.
356 : */
357 190 : if (GIST_LEAF(entry))
358 ECB : { /* all leafs contains orig trgm */
359 GIC 190 : res = trgm_contained_by(qtrg, key);
360 : }
361 UIC 0 : else if (ISALLTRUE(key))
362 : { /* non-leaf contains signature */
363 0 : res = true;
364 ECB : }
365 : else
366 : { /* non-leaf contains signature */
367 : int32 k,
368 UBC 0 : tmp = 0,
369 UIC 0 : len = ARRNELEM(qtrg);
370 UBC 0 : trgm *ptr = GETARR(qtrg);
371 UIC 0 : BITVECP sign = GETSIGN(key);
372 :
373 0 : res = true;
374 0 : for (k = 0; k < len; k++)
375 EUB : {
376 UBC 0 : CPTRGM(((char *) &tmp), ptr + k);
377 0 : if (!GETBIT(sign, HASHVAL(tmp, siglen)))
378 EUB : {
379 UIC 0 : res = false;
380 UBC 0 : break;
381 EUB : }
382 : }
383 : }
384 GBC 190 : break;
385 GIC 2211 : case RegExpICaseStrategyNumber:
386 EUB : #ifndef IGNORECASE
387 : elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
388 : #endif
389 : /* FALL THRU */
390 : case RegExpStrategyNumber:
391 ECB : /* Regexp search is inexact */
392 CBC 2211 : *recheck = true;
393 :
394 : /* Check regex match as much as we can with available info */
395 GIC 2211 : if (qtrg)
396 : {
397 2171 : if (GIST_LEAF(entry))
398 : { /* all leafs contains orig trgm */
399 ECB : bool *check;
400 :
401 GIC 2150 : check = trgm_presence_map(qtrg, key);
402 CBC 2150 : res = trigramsMatchGraph(cache->graph, check);
403 GIC 2150 : pfree(check);
404 ECB : }
405 GIC 21 : else if (ISALLTRUE(key))
406 : { /* non-leaf contains signature */
407 UIC 0 : res = true;
408 ECB : }
409 : else
410 : { /* non-leaf contains signature */
411 : int32 k,
412 CBC 21 : tmp = 0,
413 GIC 21 : len = ARRNELEM(qtrg);
414 GBC 21 : trgm *ptr = GETARR(qtrg);
415 GIC 21 : BITVECP sign = GETSIGN(key);
416 : bool *check;
417 :
418 : /*
419 ECB : * GETBIT() tests may give false positives, due to limited
420 : * size of the sign array. But since trigramsMatchGraph()
421 : * implements a monotone boolean function, false positives
422 : * in the check array can't lead to false negative answer.
423 : * So we can apply trigramsMatchGraph despite uncertainty,
424 : * and that usefully improves the quality of the search.
425 : */
426 GIC 21 : check = (bool *) palloc(len * sizeof(bool));
427 5313 : for (k = 0; k < len; k++)
428 : {
429 5292 : CPTRGM(((char *) &tmp), ptr + k);
430 5292 : check[k] = GETBIT(sign, HASHVAL(tmp, siglen));
431 : }
432 21 : res = trigramsMatchGraph(cache->graph, check);
433 CBC 21 : pfree(check);
434 ECB : }
435 : }
436 : else
437 : {
438 : /* trigram-free query must be rechecked everywhere */
439 CBC 40 : res = true;
440 ECB : }
441 GIC 2211 : break;
442 UIC 0 : default:
443 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
444 : res = false; /* keep compiler quiet */
445 : break;
446 ECB : }
447 :
448 CBC 38288 : PG_RETURN_BOOL(res);
449 EUB : }
450 :
451 : Datum
452 GIC 3095 : gtrgm_distance(PG_FUNCTION_ARGS)
453 : {
454 3095 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
455 CBC 3095 : text *query = PG_GETARG_TEXT_P(1);
456 GIC 3095 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
457 :
458 : /* Oid subtype = PG_GETARG_OID(3); */
459 CBC 3095 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
460 GIC 3095 : int siglen = GET_SIGLEN();
461 CBC 3095 : TRGM *key = (TRGM *) DatumGetPointer(entry->key);
462 ECB : TRGM *qtrg;
463 : float8 res;
464 GIC 3095 : Size querysize = VARSIZE(query);
465 3095 : char *cache = (char *) fcinfo->flinfo->fn_extra;
466 ECB :
467 : /*
468 : * Cache the generated trigrams across multiple calls with the same query.
469 : */
470 GIC 3095 : if (cache == NULL ||
471 CBC 3091 : VARSIZE(cache) != querysize ||
472 3091 : memcmp(cache, query, querysize) != 0)
473 : {
474 : char *newcache;
475 :
476 GIC 4 : qtrg = generate_trgm(VARDATA(query), querysize - VARHDRSZ);
477 ECB :
478 CBC 4 : newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
479 4 : MAXALIGN(querysize) +
480 GIC 4 : VARSIZE(qtrg));
481 :
482 4 : memcpy(newcache, query, querysize);
483 CBC 4 : memcpy(newcache + MAXALIGN(querysize), qtrg, VARSIZE(qtrg));
484 :
485 4 : if (cache)
486 LBC 0 : pfree(cache);
487 CBC 4 : fcinfo->flinfo->fn_extra = newcache;
488 GIC 4 : cache = newcache;
489 ECB : }
490 :
491 GIC 3095 : qtrg = (TRGM *) (cache + MAXALIGN(querysize));
492 ECB :
493 GBC 3095 : switch (strategy)
494 ECB : {
495 CBC 3095 : case DistanceStrategyNumber:
496 : case WordDistanceStrategyNumber:
497 : case StrictWordDistanceStrategyNumber:
498 ECB : /* Only plain trigram distance is exact */
499 GIC 3095 : *recheck = (strategy != DistanceStrategyNumber);
500 CBC 3095 : if (GIST_LEAF(entry))
501 : { /* all leafs contains orig trgm */
502 ECB :
503 : /*
504 : * Prevent gcc optimizing the sml variable using volatile
505 : * keyword. Otherwise res can differ from the
506 : * word_similarity_dist_op() function.
507 : */
508 GIC 3057 : float4 volatile sml = cnt_sml(qtrg, key, *recheck);
509 :
510 3057 : res = 1.0 - sml;
511 : }
512 38 : else if (ISALLTRUE(key))
513 : { /* all leafs contains orig trgm */
514 UIC 0 : res = 0.0;
515 ECB : }
516 : else
517 : { /* non-leaf contains signature */
518 GIC 38 : int32 count = cnt_sml_sign_common(qtrg, GETSIGN(key), siglen);
519 CBC 38 : int32 len = ARRNELEM(qtrg);
520 :
521 GBC 38 : res = (len == 0) ? -1.0 : 1.0 - ((float8) count) / ((float8) len);
522 : }
523 GIC 3095 : break;
524 UIC 0 : default:
525 LBC 0 : elog(ERROR, "unrecognized strategy number: %d", strategy);
526 ECB : res = 0; /* keep compiler quiet */
527 : break;
528 : }
529 :
530 CBC 3095 : PG_RETURN_FLOAT8(res);
531 EUB : }
532 :
533 : static int32
534 GIC 52178 : unionkey(BITVECP sbase, TRGM *add, int siglen)
535 : {
536 : int32 i;
537 ECB :
538 GIC 52178 : if (ISSIGNKEY(add))
539 : {
540 26089 : BITVECP sadd = GETSIGN(add);
541 ECB :
542 GIC 26089 : if (ISALLTRUE(add))
543 UIC 0 : return 1;
544 :
545 CBC 3411481 : LOOPBYTE(siglen)
546 GIC 3385392 : sbase[i] |= sadd[i];
547 ECB : }
548 : else
549 : {
550 GBC 26089 : trgm *ptr = GETARR(add);
551 GIC 26089 : int32 tmp = 0;
552 ECB :
553 CBC 256318 : for (i = 0; i < ARRNELEM(add); i++)
554 : {
555 GIC 230229 : CPTRGM(((char *) &tmp), ptr + i);
556 230229 : HASH(sbase, tmp, siglen);
557 ECB : }
558 : }
559 GIC 52178 : return 0;
560 ECB : }
561 :
562 :
563 : Datum
564 GIC 26089 : gtrgm_union(PG_FUNCTION_ARGS)
565 : {
566 CBC 26089 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
567 GIC 26089 : int32 len = entryvec->n;
568 26089 : int *size = (int *) PG_GETARG_POINTER(1);
569 26089 : int siglen = GET_SIGLEN();
570 : int32 i;
571 CBC 26089 : TRGM *result = gtrgm_alloc(false, siglen, NULL);
572 GIC 26089 : BITVECP base = GETSIGN(result);
573 ECB :
574 CBC 78267 : for (i = 0; i < len; i++)
575 ECB : {
576 CBC 52178 : if (unionkey(base, GETENTRY(entryvec, i), siglen))
577 : {
578 LBC 0 : result->flag = ALLISTRUE;
579 0 : SET_VARSIZE(result, CALCGTSIZE(ALLISTRUE, siglen));
580 UIC 0 : break;
581 ECB : }
582 : }
583 :
584 GIC 26089 : *size = VARSIZE(result);
585 EUB :
586 GBC 26089 : PG_RETURN_POINTER(result);
587 EUB : }
588 :
589 : Datum
590 GIC 26089 : gtrgm_same(PG_FUNCTION_ARGS)
591 ECB : {
592 GIC 26089 : TRGM *a = (TRGM *) PG_GETARG_POINTER(0);
593 CBC 26089 : TRGM *b = (TRGM *) PG_GETARG_POINTER(1);
594 GIC 26089 : bool *result = (bool *) PG_GETARG_POINTER(2);
595 26089 : int siglen = GET_SIGLEN();
596 :
597 CBC 26089 : if (ISSIGNKEY(a))
598 : { /* then b also ISSIGNKEY */
599 26089 : if (ISALLTRUE(a) && ISALLTRUE(b))
600 LBC 0 : *result = true;
601 CBC 26089 : else if (ISALLTRUE(a))
602 LBC 0 : *result = false;
603 GIC 26089 : else if (ISALLTRUE(b))
604 LBC 0 : *result = false;
605 : else
606 ECB : {
607 EUB : int32 i;
608 CBC 26089 : BITVECP sa = GETSIGN(a),
609 GBC 26089 : sb = GETSIGN(b);
610 ECB :
611 GBC 26089 : *result = true;
612 GIC 1736581 : LOOPBYTE(siglen)
613 : {
614 1712087 : if (sa[i] != sb[i])
615 ECB : {
616 CBC 1595 : *result = false;
617 GIC 1595 : break;
618 ECB : }
619 : }
620 : }
621 : }
622 : else
623 : { /* a and b ISARRKEY */
624 LBC 0 : int32 lena = ARRNELEM(a),
625 UIC 0 : lenb = ARRNELEM(b);
626 :
627 0 : if (lena != lenb)
628 0 : *result = false;
629 : else
630 : {
631 UBC 0 : trgm *ptra = GETARR(a),
632 0 : *ptrb = GETARR(b);
633 : int32 i;
634 EUB :
635 UBC 0 : *result = true;
636 UIC 0 : for (i = 0; i < lena; i++)
637 0 : if (CMPTRGM(ptra + i, ptrb + i))
638 EUB : {
639 UBC 0 : *result = false;
640 UIC 0 : break;
641 : }
642 EUB : }
643 : }
644 :
645 GIC 26089 : PG_RETURN_POINTER(result);
646 EUB : }
647 :
648 : static int32
649 UIC 0 : sizebitvec(BITVECP sign, int siglen)
650 : {
651 0 : return pg_popcount(sign, siglen);
652 ECB : }
653 :
654 : static int
655 GIC 4881920 : hemdistsign(BITVECP a, BITVECP b, int siglen)
656 EUB : {
657 : int i,
658 : diff,
659 GIC 4881920 : dist = 0;
660 :
661 200037508 : LOOPBYTE(siglen)
662 ECB : {
663 GIC 195155588 : diff = (unsigned char) (a[i] ^ b[i]);
664 : /* Using the popcount functions here isn't likely to win */
665 195155588 : dist += pg_number_of_ones[diff];
666 ECB : }
667 GIC 4881920 : return dist;
668 ECB : }
669 :
670 : static int
671 UIC 0 : hemdist(TRGM *a, TRGM *b, int siglen)
672 ECB : {
673 UIC 0 : if (ISALLTRUE(a))
674 ECB : {
675 UIC 0 : if (ISALLTRUE(b))
676 0 : return 0;
677 : else
678 UBC 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(b), siglen);
679 : }
680 0 : else if (ISALLTRUE(b))
681 UIC 0 : return SIGLENBIT(siglen) - sizebitvec(GETSIGN(a), siglen);
682 EUB :
683 UBC 0 : return hemdistsign(GETSIGN(a), GETSIGN(b), siglen);
684 : }
685 EUB :
686 : Datum
687 GBC 1211606 : gtrgm_penalty(PG_FUNCTION_ARGS)
688 EUB : {
689 GIC 1211606 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
690 GBC 1211606 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
691 GIC 1211606 : float *penalty = (float *) PG_GETARG_POINTER(2);
692 1211606 : int siglen = GET_SIGLEN();
693 1211606 : TRGM *origval = (TRGM *) DatumGetPointer(origentry->key);
694 CBC 1211606 : TRGM *newval = (TRGM *) DatumGetPointer(newentry->key);
695 GIC 1211606 : BITVECP orig = GETSIGN(origval);
696 ECB :
697 CBC 1211606 : *penalty = 0.0;
698 ECB :
699 CBC 1211606 : if (ISARRKEY(newval))
700 ECB : {
701 CBC 1211606 : char *cache = (char *) fcinfo->flinfo->fn_extra;
702 1211606 : TRGM *cachedVal = (TRGM *) (cache + MAXALIGN(siglen));
703 GIC 1211606 : Size newvalsize = VARSIZE(newval);
704 ECB : BITVECP sign;
705 :
706 : /*
707 : * Cache the sign data across multiple calls with the same newval.
708 : */
709 CBC 1211606 : if (cache == NULL ||
710 1211601 : VARSIZE(cachedVal) != newvalsize ||
711 GIC 1210574 : memcmp(cachedVal, newval, newvalsize) != 0)
712 : {
713 : char *newcache;
714 :
715 2886 : newcache = MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
716 CBC 2886 : MAXALIGN(siglen) +
717 ECB : newvalsize);
718 :
719 GIC 2886 : makesign((BITVECP) newcache, newval, siglen);
720 :
721 2886 : cachedVal = (TRGM *) (newcache + MAXALIGN(siglen));
722 CBC 2886 : memcpy(cachedVal, newval, newvalsize);
723 ECB :
724 GIC 2886 : if (cache)
725 2881 : pfree(cache);
726 CBC 2886 : fcinfo->flinfo->fn_extra = newcache;
727 GIC 2886 : cache = newcache;
728 ECB : }
729 :
730 GIC 1211606 : sign = (BITVECP) cache;
731 ECB :
732 CBC 1211606 : if (ISALLTRUE(origval))
733 LBC 0 : *penalty = ((float) (SIGLENBIT(siglen) - sizebitvec(sign, siglen))) / (float) (SIGLENBIT(siglen) + 1);
734 ECB : else
735 GIC 1211606 : *penalty = hemdistsign(sign, orig, siglen);
736 : }
737 ECB : else
738 UIC 0 : *penalty = hemdist(origval, newval, siglen);
739 CBC 1211606 : PG_RETURN_POINTER(penalty);
740 EUB : }
741 :
742 ECB : typedef struct
743 : {
744 : bool allistrue;
745 EUB : BITVECP sign;
746 ECB : } CACHESIGN;
747 :
748 : static void
749 GIC 43116 : fillcache(CACHESIGN *item, TRGM *key, BITVECP sign, int siglen)
750 : {
751 43116 : item->allistrue = false;
752 43116 : item->sign = sign;
753 43116 : if (ISARRKEY(key))
754 42904 : makesign(item->sign, key, siglen);
755 212 : else if (ISALLTRUE(key))
756 LBC 0 : item->allistrue = true;
757 : else
758 GNC 212 : memcpy(item->sign, GETSIGN(key), siglen);
759 CBC 43116 : }
760 ECB :
761 : #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
762 : typedef struct
763 EUB : {
764 : OffsetNumber pos;
765 ECB : int32 cost;
766 : } SPLITCOST;
767 :
768 : static int
769 GIC 47803 : comparecost(const void *a, const void *b)
770 : {
771 47803 : if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
772 43155 : return 0;
773 : else
774 4648 : return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
775 : }
776 ECB :
777 :
778 : static int
779 CBC 3585154 : hemdistcache(CACHESIGN *a, CACHESIGN *b, int siglen)
780 : {
781 3585154 : if (a->allistrue)
782 : {
783 UIC 0 : if (b->allistrue)
784 0 : return 0;
785 : else
786 LBC 0 : return SIGLENBIT(siglen) - sizebitvec(b->sign, siglen);
787 : }
788 CBC 3585154 : else if (b->allistrue)
789 UIC 0 : return SIGLENBIT(siglen) - sizebitvec(a->sign, siglen);
790 EUB :
791 GBC 3585154 : return hemdistsign(a->sign, b->sign, siglen);
792 : }
793 EUB :
794 : Datum
795 CBC 268 : gtrgm_picksplit(PG_FUNCTION_ARGS)
796 EUB : {
797 GIC 268 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
798 CBC 268 : OffsetNumber maxoff = entryvec->n - 1;
799 GIC 268 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
800 268 : int siglen = GET_SIGLEN();
801 : OffsetNumber k,
802 ECB : j;
803 : TRGM *datum_l,
804 : *datum_r;
805 : BITVECP union_l,
806 : union_r;
807 : int32 size_alpha,
808 : size_beta;
809 : int32 size_waste,
810 GIC 268 : waste = -1;
811 : int32 nbytes;
812 268 : OffsetNumber seed_1 = 0,
813 268 : seed_2 = 0;
814 : OffsetNumber *left,
815 : *right;
816 : BITVECP ptr;
817 ECB : int i;
818 : CACHESIGN *cache;
819 : char *cache_sign;
820 : SPLITCOST *costvector;
821 :
822 : /* cache the sign data for each existing item */
823 GIC 268 : cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 1));
824 268 : cache_sign = palloc(siglen * (maxoff + 1));
825 :
826 43384 : for (k = FirstOffsetNumber; k <= maxoff; k = OffsetNumberNext(k))
827 43116 : fillcache(&cache[k], GETENTRY(entryvec, k), &cache_sign[siglen * k],
828 : siglen);
829 :
830 ECB : /* now find the two furthest-apart items */
831 CBC 43116 : for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
832 : {
833 3541770 : for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
834 ECB : {
835 GIC 3498922 : size_waste = hemdistcache(&(cache[j]), &(cache[k]), siglen);
836 3498922 : if (size_waste > waste)
837 : {
838 CBC 463 : waste = size_waste;
839 GIC 463 : seed_1 = k;
840 CBC 463 : seed_2 = j;
841 : }
842 ECB : }
843 : }
844 :
845 : /* just in case we didn't make a selection ... */
846 CBC 268 : if (seed_1 == 0 || seed_2 == 0)
847 ECB : {
848 UIC 0 : seed_1 = 1;
849 0 : seed_2 = 2;
850 : }
851 :
852 : /* initialize the result vectors */
853 CBC 268 : nbytes = maxoff * sizeof(OffsetNumber);
854 GIC 268 : v->spl_left = left = (OffsetNumber *) palloc(nbytes);
855 GBC 268 : v->spl_right = right = (OffsetNumber *) palloc(nbytes);
856 268 : v->spl_nleft = 0;
857 GIC 268 : v->spl_nright = 0;
858 :
859 : /* form initial .. */
860 CBC 268 : datum_l = gtrgm_alloc(cache[seed_1].allistrue, siglen, cache[seed_1].sign);
861 268 : datum_r = gtrgm_alloc(cache[seed_2].allistrue, siglen, cache[seed_2].sign);
862 ECB :
863 CBC 268 : union_l = GETSIGN(datum_l);
864 268 : union_r = GETSIGN(datum_r);
865 :
866 : /* sort before ... */
867 268 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
868 43384 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
869 : {
870 43116 : costvector[j - 1].pos = j;
871 43116 : size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]), siglen);
872 GIC 43116 : size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]), siglen);
873 43116 : costvector[j - 1].cost = abs(size_alpha - size_beta);
874 ECB : }
875 GNC 268 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
876 :
877 CBC 43384 : for (k = 0; k < maxoff; k++)
878 ECB : {
879 CBC 43116 : j = costvector[k].pos;
880 43116 : if (j == seed_1)
881 : {
882 268 : *left++ = j;
883 GIC 268 : v->spl_nleft++;
884 CBC 268 : continue;
885 : }
886 42848 : else if (j == seed_2)
887 ECB : {
888 GIC 268 : *right++ = j;
889 CBC 268 : v->spl_nright++;
890 268 : continue;
891 ECB : }
892 :
893 CBC 42580 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
894 : {
895 LBC 0 : if (ISALLTRUE(datum_l) && cache[j].allistrue)
896 0 : size_alpha = 0;
897 ECB : else
898 UIC 0 : size_alpha = SIGLENBIT(siglen) -
899 0 : sizebitvec((cache[j].allistrue) ? GETSIGN(datum_l) :
900 LBC 0 : GETSIGN(cache[j].sign),
901 : siglen);
902 EUB : }
903 : else
904 GIC 42580 : size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l), siglen);
905 EUB :
906 GBC 42580 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
907 EUB : {
908 UIC 0 : if (ISALLTRUE(datum_r) && cache[j].allistrue)
909 0 : size_beta = 0;
910 : else
911 LBC 0 : size_beta = SIGLENBIT(siglen) -
912 UIC 0 : sizebitvec((cache[j].allistrue) ? GETSIGN(datum_r) :
913 LBC 0 : GETSIGN(cache[j].sign),
914 : siglen);
915 EUB : }
916 : else
917 GIC 42580 : size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r), siglen);
918 EUB :
919 GBC 42580 : if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
920 EUB : {
921 GIC 21175 : if (ISALLTRUE(datum_l) || cache[j].allistrue)
922 : {
923 UIC 0 : if (!ISALLTRUE(datum_l))
924 UNC 0 : memset(GETSIGN(datum_l), 0xff, siglen);
925 : }
926 ECB : else
927 : {
928 CBC 21175 : ptr = cache[j].sign;
929 GIC 1271215 : LOOPBYTE(siglen)
930 GBC 1250040 : union_l[i] |= ptr[i];
931 EUB : }
932 GIC 21175 : *left++ = j;
933 21175 : v->spl_nleft++;
934 : }
935 ECB : else
936 : {
937 CBC 21405 : if (ISALLTRUE(datum_r) || cache[j].allistrue)
938 : {
939 LBC 0 : if (!ISALLTRUE(datum_r))
940 UNC 0 : memset(GETSIGN(datum_r), 0xff, siglen);
941 : }
942 : else
943 : {
944 CBC 21405 : ptr = cache[j].sign;
945 GIC 1237989 : LOOPBYTE(siglen)
946 GBC 1216584 : union_r[i] |= ptr[i];
947 EUB : }
948 GIC 21405 : *right++ = j;
949 21405 : v->spl_nright++;
950 : }
951 ECB : }
952 :
953 CBC 268 : v->spl_ldatum = PointerGetDatum(datum_l);
954 GIC 268 : v->spl_rdatum = PointerGetDatum(datum_r);
955 ECB :
956 CBC 268 : PG_RETURN_POINTER(v);
957 : }
958 :
959 : Datum
960 17 : gtrgm_options(PG_FUNCTION_ARGS)
961 ECB : {
962 GIC 17 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
963 ECB :
964 GIC 17 : init_local_reloptions(relopts, sizeof(TrgmGistOptions));
965 17 : add_local_int_reloption(relopts, "siglen",
966 : "signature length in bytes",
967 ECB : SIGLEN_DEFAULT, 1, SIGLEN_MAX,
968 : offsetof(TrgmGistOptions, siglen));
969 :
970 GIC 17 : PG_RETURN_VOID();
971 ECB : }
|
