PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
trgm_op.c
Go to the documentation of this file.
1/*
2 * contrib/pg_trgm/trgm_op.c
3 */
4#include "postgres.h"
5
6#include <ctype.h>
7
8#include "catalog/pg_collation_d.h"
9#include "catalog/pg_type.h"
10#include "common/int.h"
11#include "lib/qunique.h"
12#include "miscadmin.h"
13#include "trgm.h"
14#include "tsearch/ts_locale.h"
15#include "utils/formatting.h"
16#include "utils/guc.h"
17#include "utils/lsyscache.h"
18#include "utils/memutils.h"
19#include "utils/pg_crc.h"
20
22
23/* GUC variables */
27
44
45/* Trigram with position */
46typedef struct
47{
49 int index;
50} pos_trgm;
51
52/* Trigram bound type */
54#define TRGM_BOUND_LEFT 0x01 /* trigram is left bound of word */
55#define TRGM_BOUND_RIGHT 0x02 /* trigram is right bound of word */
56
57/* Word similarity flags */
58#define WORD_SIMILARITY_CHECK_ONLY 0x01 /* only check existence of similar
59 * search pattern in text */
60#define WORD_SIMILARITY_STRICT 0x02 /* force bounds of extent to match
61 * word bounds */
62
63/*
64 * Module load callback
65 */
66void
67_PG_init(void)
68{
69 /* Define custom GUC variables. */
70 DefineCustomRealVariable("pg_trgm.similarity_threshold",
71 "Sets the threshold used by the % operator.",
72 "Valid range is 0.0 .. 1.0.",
74 0.3f,
75 0.0,
76 1.0,
78 0,
79 NULL,
80 NULL,
81 NULL);
82 DefineCustomRealVariable("pg_trgm.word_similarity_threshold",
83 "Sets the threshold used by the <% operator.",
84 "Valid range is 0.0 .. 1.0.",
86 0.6f,
87 0.0,
88 1.0,
90 0,
91 NULL,
92 NULL,
93 NULL);
94 DefineCustomRealVariable("pg_trgm.strict_word_similarity_threshold",
95 "Sets the threshold used by the <<% operator.",
96 "Valid range is 0.0 .. 1.0.",
98 0.5f,
99 0.0,
100 1.0,
102 0,
103 NULL,
104 NULL,
105 NULL);
106
107 MarkGUCPrefixReserved("pg_trgm");
108}
109
110/*
111 * Deprecated function.
112 * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
113 */
114Datum
116{
117 float4 nlimit = PG_GETARG_FLOAT4(0);
118 char *nlimit_str;
119 Oid func_out_oid;
120 bool is_varlena;
121
122 getTypeOutputInfo(FLOAT4OID, &func_out_oid, &is_varlena);
123
124 nlimit_str = OidOutputFunctionCall(func_out_oid, Float4GetDatum(nlimit));
125
126 SetConfigOption("pg_trgm.similarity_threshold", nlimit_str,
128
130}
131
132
133/*
134 * Get similarity threshold for given index scan strategy number.
135 */
136double
138{
139 switch (strategy)
140 {
147 default:
148 elog(ERROR, "unrecognized strategy number: %d", strategy);
149 break;
150 }
151
152 return 0.0; /* keep compiler quiet */
153}
154
155/*
156 * Deprecated function.
157 * Use "pg_trgm.similarity_threshold" GUC variable instead of this function.
158 */
159Datum
161{
163}
165static int
166comp_trgm(const void *a, const void *b)
167{
168 return CMPTRGM(a, b);
169}
170
171/*
172 * Finds first word in string, returns pointer to the word,
173 * endword points to the character after word
174 */
175static char *
176find_word(char *str, int lenstr, char **endword, int *charlen)
177{
178 char *beginword = str;
179
180 while (beginword - str < lenstr && !ISWORDCHR(beginword))
181 beginword += pg_mblen(beginword);
182
183 if (beginword - str >= lenstr)
184 return NULL;
185
186 *endword = beginword;
187 *charlen = 0;
188 while (*endword - str < lenstr && ISWORDCHR(*endword))
189 {
190 *endword += pg_mblen(*endword);
191 (*charlen)++;
192 }
193
194 return beginword;
195}
196
197/*
198 * Reduce a trigram (three possibly multi-byte characters) to a trgm,
199 * which is always exactly three bytes. If we have three single-byte
200 * characters, we just use them as-is; otherwise we form a hash value.
201 */
202void
203compact_trigram(trgm *tptr, char *str, int bytelen)
204{
205 if (bytelen == 3)
206 {
207 CPTRGM(tptr, str);
208 }
209 else
210 {
212
214 COMP_LEGACY_CRC32(crc, str, bytelen);
216
217 /*
218 * use only 3 upper bytes from crc, hope, it's good enough hashing
219 */
220 CPTRGM(tptr, &crc);
221 }
222}
223
224/*
225 * Adds trigrams from words (already padded).
226 */
227static trgm *
228make_trigrams(trgm *tptr, char *str, int bytelen, int charlen)
229{
230 char *ptr = str;
231
232 if (charlen < 3)
233 return tptr;
234
235 if (bytelen > charlen)
236 {
237 /* Find multibyte character boundaries and apply compact_trigram */
238 int lenfirst = pg_mblen(str),
239 lenmiddle = pg_mblen(str + lenfirst),
240 lenlast = pg_mblen(str + lenfirst + lenmiddle);
241
242 while ((ptr - str) + lenfirst + lenmiddle + lenlast <= bytelen)
243 {
244 compact_trigram(tptr, ptr, lenfirst + lenmiddle + lenlast);
245
246 ptr += lenfirst;
247 tptr++;
248
249 lenfirst = lenmiddle;
250 lenmiddle = lenlast;
251 lenlast = pg_mblen(ptr + lenfirst + lenmiddle);
252 }
253 }
254 else
255 {
256 /* Fast path when there are no multibyte characters */
257 Assert(bytelen == charlen);
258
259 while (ptr - str < bytelen - 2 /* number of trigrams = strlen - 2 */ )
260 {
261 CPTRGM(tptr, ptr);
262 ptr++;
263 tptr++;
264 }
265 }
266
267 return tptr;
268}
269
270/*
271 * Make array of trigrams without sorting and removing duplicate items.
272 *
273 * trg: where to return the array of trigrams.
274 * str: source string, of length slen bytes.
275 * bounds: where to return bounds of trigrams (if needed).
276 *
277 * Returns length of the generated array.
278 */
279static int
280generate_trgm_only(trgm *trg, char *str, int slen, TrgmBound *bounds)
281{
282 trgm *tptr;
283 char *buf;
284 int charlen,
285 bytelen;
286 char *bword,
287 *eword;
288
289 if (slen + LPADDING + RPADDING < 3 || slen == 0)
290 return 0;
291
292 tptr = trg;
293
294 /* Allocate a buffer for case-folded, blank-padded words */
295 buf = (char *) palloc(slen * pg_database_encoding_max_length() + 4);
296
297 if (LPADDING > 0)
298 {
299 *buf = ' ';
300 if (LPADDING > 1)
301 *(buf + 1) = ' ';
302 }
303
304 eword = str;
305 while ((bword = find_word(eword, slen - (eword - str), &eword, &charlen)) != NULL)
306 {
307#ifdef IGNORECASE
308 bword = str_tolower(bword, eword - bword, DEFAULT_COLLATION_OID);
309 bytelen = strlen(bword);
310#else
311 bytelen = eword - bword;
312#endif
313
314 memcpy(buf + LPADDING, bword, bytelen);
315
316#ifdef IGNORECASE
317 pfree(bword);
318#endif
319
320 buf[LPADDING + bytelen] = ' ';
321 buf[LPADDING + bytelen + 1] = ' ';
322
323 /* Calculate trigrams marking their bounds if needed */
324 if (bounds)
325 bounds[tptr - trg] |= TRGM_BOUND_LEFT;
326 tptr = make_trigrams(tptr, buf, bytelen + LPADDING + RPADDING,
327 charlen + LPADDING + RPADDING);
328 if (bounds)
329 bounds[tptr - trg - 1] |= TRGM_BOUND_RIGHT;
330 }
331
332 pfree(buf);
333
334 return tptr - trg;
335}
336
337/*
338 * Guard against possible overflow in the palloc requests below. (We
339 * don't worry about the additive constants, since palloc can detect
340 * requests that are a little above MaxAllocSize --- we just need to
341 * prevent integer overflow in the multiplications.)
342 */
343static void
344protect_out_of_mem(int slen)
345{
346 if ((Size) (slen / 2) >= (MaxAllocSize / (sizeof(trgm) * 3)) ||
349 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
350 errmsg("out of memory")));
351}
352
353/*
354 * Make array of trigrams with sorting and removing duplicate items.
355 *
356 * str: source string, of length slen bytes.
357 *
358 * Returns the sorted array of unique trigrams.
359 */
360TRGM *
361generate_trgm(char *str, int slen)
362{
363 TRGM *trg;
364 int len;
365
366 protect_out_of_mem(slen);
367
368 trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) * 3);
369 trg->flag = ARRKEY;
370
371 len = generate_trgm_only(GETARR(trg), str, slen, NULL);
373
374 if (len == 0)
375 return trg;
376
377 /*
378 * Make trigrams unique.
379 */
380 if (len > 1)
381 {
382 qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
383 len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
384 }
385
387
388 return trg;
389}
390
391/*
392 * Make array of positional trigrams from two trigram arrays trg1 and trg2.
393 *
394 * trg1: trigram array of search pattern, of length len1. trg1 is required
395 * word which positions don't matter and replaced with -1.
396 * trg2: trigram array of text, of length len2. trg2 is haystack where we
397 * search and have to store its positions.
398 *
399 * Returns concatenated trigram array.
400 */
401static pos_trgm *
402make_positional_trgm(trgm *trg1, int len1, trgm *trg2, int len2)
403{
404 pos_trgm *result;
405 int i,
406 len = len1 + len2;
407
408 result = (pos_trgm *) palloc(sizeof(pos_trgm) * len);
409
410 for (i = 0; i < len1; i++)
411 {
412 memcpy(&result[i].trg, &trg1[i], sizeof(trgm));
413 result[i].index = -1;
414 }
415
416 for (i = 0; i < len2; i++)
417 {
418 memcpy(&result[i + len1].trg, &trg2[i], sizeof(trgm));
419 result[i + len1].index = i;
420 }
421
422 return result;
423}
424
425/*
426 * Compare position trigrams: compare trigrams first and position second.
427 */
428static int
429comp_ptrgm(const void *v1, const void *v2)
430{
431 const pos_trgm *p1 = (const pos_trgm *) v1;
432 const pos_trgm *p2 = (const pos_trgm *) v2;
433 int cmp;
434
435 cmp = CMPTRGM(p1->trg, p2->trg);
436 if (cmp != 0)
437 return cmp;
438
439 return pg_cmp_s32(p1->index, p2->index);
440}
441
442/*
443 * Iterative search function which calculates maximum similarity with word in
444 * the string. Maximum similarity is only calculated only if the flag
445 * WORD_SIMILARITY_CHECK_ONLY isn't set.
446 *
447 * trg2indexes: array which stores indexes of the array "found".
448 * found: array which stores true of false values.
449 * ulen1: count of unique trigrams of array "trg1".
450 * len2: length of array "trg2" and array "trg2indexes".
451 * len: length of the array "found".
452 * flags: set of boolean flags parameterizing similarity calculation.
453 * bounds: whether each trigram is left/right bound of word.
454 *
455 * Returns word similarity.
456 */
457static float4
458iterate_word_similarity(int *trg2indexes,
459 bool *found,
460 int ulen1,
461 int len2,
462 int len,
463 uint8 flags,
464 TrgmBound *bounds)
465{
466 int *lastpos,
467 i,
468 ulen2 = 0,
469 count = 0,
470 upper = -1,
471 lower;
472 float4 smlr_cur,
473 smlr_max = 0.0f;
474 double threshold;
475
476 Assert(bounds || !(flags & WORD_SIMILARITY_STRICT));
477
478 /* Select appropriate threshold */
479 threshold = (flags & WORD_SIMILARITY_STRICT) ?
482
483 /*
484 * Consider first trigram as initial lower bound for strict word
485 * similarity, or initialize it later with first trigram present for plain
486 * word similarity.
487 */
488 lower = (flags & WORD_SIMILARITY_STRICT) ? 0 : -1;
489
490 /* Memorise last position of each trigram */
491 lastpos = (int *) palloc(sizeof(int) * len);
492 memset(lastpos, -1, sizeof(int) * len);
493
494 for (i = 0; i < len2; i++)
495 {
496 int trgindex;
497
499
500 /* Get index of next trigram */
501 trgindex = trg2indexes[i];
502
503 /* Update last position of this trigram */
504 if (lower >= 0 || found[trgindex])
505 {
506 if (lastpos[trgindex] < 0)
507 {
508 ulen2++;
509 if (found[trgindex])
510 count++;
511 }
512 lastpos[trgindex] = i;
513 }
514
515 /*
516 * Adjust upper bound if trigram is upper bound of word for strict
517 * word similarity, or if trigram is present in required substring for
518 * plain word similarity
519 */
520 if ((flags & WORD_SIMILARITY_STRICT) ? (bounds[i] & TRGM_BOUND_RIGHT)
521 : found[trgindex])
522 {
523 int prev_lower,
524 tmp_ulen2,
525 tmp_lower,
526 tmp_count;
527
528 upper = i;
529 if (lower == -1)
530 {
531 lower = i;
532 ulen2 = 1;
533 }
534
535 smlr_cur = CALCSML(count, ulen1, ulen2);
536
537 /* Also try to adjust lower bound for greater similarity */
538 tmp_count = count;
539 tmp_ulen2 = ulen2;
540 prev_lower = lower;
541 for (tmp_lower = lower; tmp_lower <= upper; tmp_lower++)
542 {
543 float smlr_tmp;
544 int tmp_trgindex;
545
546 /*
547 * Adjust lower bound only if trigram is lower bound of word
548 * for strict word similarity, or consider every trigram as
549 * lower bound for plain word similarity.
550 */
551 if (!(flags & WORD_SIMILARITY_STRICT)
552 || (bounds[tmp_lower] & TRGM_BOUND_LEFT))
553 {
554 smlr_tmp = CALCSML(tmp_count, ulen1, tmp_ulen2);
555 if (smlr_tmp > smlr_cur)
556 {
557 smlr_cur = smlr_tmp;
558 ulen2 = tmp_ulen2;
559 lower = tmp_lower;
560 count = tmp_count;
561 }
562
563 /*
564 * If we only check that word similarity is greater than
565 * threshold we do not need to calculate a maximum
566 * similarity.
567 */
568 if ((flags & WORD_SIMILARITY_CHECK_ONLY)
569 && smlr_cur >= threshold)
570 break;
571 }
572
573 tmp_trgindex = trg2indexes[tmp_lower];
574 if (lastpos[tmp_trgindex] == tmp_lower)
575 {
576 tmp_ulen2--;
577 if (found[tmp_trgindex])
578 tmp_count--;
579 }
580 }
581
582 smlr_max = Max(smlr_max, smlr_cur);
583
584 /*
585 * if we only check that word similarity is greater than threshold
586 * we do not need to calculate a maximum similarity.
587 */
588 if ((flags & WORD_SIMILARITY_CHECK_ONLY) && smlr_max >= threshold)
589 break;
590
591 for (tmp_lower = prev_lower; tmp_lower < lower; tmp_lower++)
592 {
593 int tmp_trgindex;
594
595 tmp_trgindex = trg2indexes[tmp_lower];
596 if (lastpos[tmp_trgindex] == tmp_lower)
597 lastpos[tmp_trgindex] = -1;
598 }
599 }
600 }
601
602 pfree(lastpos);
603
604 return smlr_max;
605}
606
607/*
608 * Calculate word similarity.
609 * This function prepare two arrays: "trg2indexes" and "found". Then this arrays
610 * are used to calculate word similarity using iterate_word_similarity().
611 *
612 * "trg2indexes" is array which stores indexes of the array "found".
613 * In other words:
614 * trg2indexes[j] = i;
615 * found[i] = true (or false);
616 * If found[i] == true then there is trigram trg2[j] in array "trg1".
617 * If found[i] == false then there is not trigram trg2[j] in array "trg1".
618 *
619 * str1: search pattern string, of length slen1 bytes.
620 * str2: text in which we are looking for a word, of length slen2 bytes.
621 * flags: set of boolean flags parameterizing similarity calculation.
622 *
623 * Returns word similarity.
624 */
625static float4
626calc_word_similarity(char *str1, int slen1, char *str2, int slen2,
627 uint8 flags)
628{
629 bool *found;
630 pos_trgm *ptrg;
631 trgm *trg1;
632 trgm *trg2;
633 int len1,
634 len2,
635 len,
636 i,
637 j,
638 ulen1;
639 int *trg2indexes;
640 float4 result;
641 TrgmBound *bounds;
642
643 protect_out_of_mem(slen1 + slen2);
644
645 /* Make positional trigrams */
646 trg1 = (trgm *) palloc(sizeof(trgm) * (slen1 / 2 + 1) * 3);
647 trg2 = (trgm *) palloc(sizeof(trgm) * (slen2 / 2 + 1) * 3);
648 if (flags & WORD_SIMILARITY_STRICT)
649 bounds = (TrgmBound *) palloc0(sizeof(TrgmBound) * (slen2 / 2 + 1) * 3);
650 else
651 bounds = NULL;
652
653 len1 = generate_trgm_only(trg1, str1, slen1, NULL);
654 len2 = generate_trgm_only(trg2, str2, slen2, bounds);
655
656 ptrg = make_positional_trgm(trg1, len1, trg2, len2);
657 len = len1 + len2;
658 qsort(ptrg, len, sizeof(pos_trgm), comp_ptrgm);
659
660 pfree(trg1);
661 pfree(trg2);
662
663 /*
664 * Merge positional trigrams array: enumerate each trigram and find its
665 * presence in required word.
666 */
667 trg2indexes = (int *) palloc(sizeof(int) * len2);
668 found = (bool *) palloc0(sizeof(bool) * len);
669
670 ulen1 = 0;
671 j = 0;
672 for (i = 0; i < len; i++)
673 {
674 if (i > 0)
675 {
676 int cmp = CMPTRGM(ptrg[i - 1].trg, ptrg[i].trg);
677
678 if (cmp != 0)
679 {
680 if (found[j])
681 ulen1++;
682 j++;
683 }
684 }
685
686 if (ptrg[i].index >= 0)
687 {
688 trg2indexes[ptrg[i].index] = j;
689 }
690 else
691 {
692 found[j] = true;
693 }
694 }
695 if (found[j])
696 ulen1++;
697
698 /* Run iterative procedure to find maximum similarity with word */
699 result = iterate_word_similarity(trg2indexes, found, ulen1, len2, len,
700 flags, bounds);
701
702 pfree(trg2indexes);
703 pfree(found);
704 pfree(ptrg);
705
706 return result;
707}
708
709
710/*
711 * Extract the next non-wildcard part of a search string, i.e. a word bounded
712 * by '_' or '%' meta-characters, non-word characters or string end.
713 *
714 * str: source string, of length lenstr bytes (need not be null-terminated)
715 * buf: where to return the substring (must be long enough)
716 * *bytelen: receives byte length of the found substring
717 * *charlen: receives character length of the found substring
718 *
719 * Returns pointer to end+1 of the found substring in the source string.
720 * Returns NULL if no word found (in which case buf, bytelen, charlen not set)
721 *
722 * If the found word is bounded by non-word characters or string boundaries
723 * then this function will include corresponding padding spaces into buf.
724 */
725static const char *
726get_wildcard_part(const char *str, int lenstr,
727 char *buf, int *bytelen, int *charlen)
728{
729 const char *beginword = str;
730 const char *endword;
731 char *s = buf;
732 bool in_leading_wildcard_meta = false;
733 bool in_trailing_wildcard_meta = false;
734 bool in_escape = false;
735 int clen;
736
737 /*
738 * Find the first word character, remembering whether preceding character
739 * was wildcard meta-character. Note that the in_escape state persists
740 * from this loop to the next one, since we may exit at a word character
741 * that is in_escape.
742 */
743 while (beginword - str < lenstr)
744 {
745 if (in_escape)
746 {
747 if (ISWORDCHR(beginword))
748 break;
749 in_escape = false;
750 in_leading_wildcard_meta = false;
751 }
752 else
753 {
754 if (ISESCAPECHAR(beginword))
755 in_escape = true;
756 else if (ISWILDCARDCHAR(beginword))
757 in_leading_wildcard_meta = true;
758 else if (ISWORDCHR(beginword))
759 break;
760 else
761 in_leading_wildcard_meta = false;
762 }
763 beginword += pg_mblen(beginword);
764 }
765
766 /*
767 * Handle string end.
768 */
769 if (beginword - str >= lenstr)
770 return NULL;
771
772 /*
773 * Add left padding spaces if preceding character wasn't wildcard
774 * meta-character.
775 */
776 *charlen = 0;
777 if (!in_leading_wildcard_meta)
778 {
779 if (LPADDING > 0)
780 {
781 *s++ = ' ';
782 (*charlen)++;
783 if (LPADDING > 1)
784 {
785 *s++ = ' ';
786 (*charlen)++;
787 }
788 }
789 }
790
791 /*
792 * Copy data into buf until wildcard meta-character, non-word character or
793 * string boundary. Strip escapes during copy.
794 */
795 endword = beginword;
796 while (endword - str < lenstr)
797 {
798 clen = pg_mblen(endword);
799 if (in_escape)
800 {
801 if (ISWORDCHR(endword))
802 {
803 memcpy(s, endword, clen);
804 (*charlen)++;
805 s += clen;
806 }
807 else
808 {
809 /*
810 * Back up endword to the escape character when stopping at an
811 * escaped char, so that subsequent get_wildcard_part will
812 * restart from the escape character. We assume here that
813 * escape chars are single-byte.
814 */
815 endword--;
816 break;
817 }
818 in_escape = false;
819 }
820 else
821 {
822 if (ISESCAPECHAR(endword))
823 in_escape = true;
824 else if (ISWILDCARDCHAR(endword))
825 {
826 in_trailing_wildcard_meta = true;
827 break;
828 }
829 else if (ISWORDCHR(endword))
830 {
831 memcpy(s, endword, clen);
832 (*charlen)++;
833 s += clen;
834 }
835 else
836 break;
837 }
838 endword += clen;
839 }
840
841 /*
842 * Add right padding spaces if next character isn't wildcard
843 * meta-character.
844 */
845 if (!in_trailing_wildcard_meta)
846 {
847 if (RPADDING > 0)
848 {
849 *s++ = ' ';
850 (*charlen)++;
851 if (RPADDING > 1)
852 {
853 *s++ = ' ';
854 (*charlen)++;
855 }
856 }
857 }
858
859 *bytelen = s - buf;
860 return endword;
861}
862
863/*
864 * Generates trigrams for wildcard search string.
865 *
866 * Returns array of trigrams that must occur in any string that matches the
867 * wildcard string. For example, given pattern "a%bcd%" the trigrams
868 * " a", "bcd" would be extracted.
869 */
870TRGM *
871generate_wildcard_trgm(const char *str, int slen)
872{
873 TRGM *trg;
874 char *buf,
875 *buf2;
876 trgm *tptr;
877 int len,
878 charlen,
879 bytelen;
880 const char *eword;
881
882 protect_out_of_mem(slen);
883
884 trg = (TRGM *) palloc(TRGMHDRSIZE + sizeof(trgm) * (slen / 2 + 1) * 3);
885 trg->flag = ARRKEY;
887
888 if (slen + LPADDING + RPADDING < 3 || slen == 0)
889 return trg;
890
891 tptr = GETARR(trg);
892
893 /* Allocate a buffer for blank-padded, but not yet case-folded, words */
894 buf = palloc(sizeof(char) * (slen + 4));
895
896 /*
897 * Extract trigrams from each substring extracted by get_wildcard_part.
898 */
899 eword = str;
900 while ((eword = get_wildcard_part(eword, slen - (eword - str),
901 buf, &bytelen, &charlen)) != NULL)
902 {
903#ifdef IGNORECASE
904 buf2 = str_tolower(buf, bytelen, DEFAULT_COLLATION_OID);
905 bytelen = strlen(buf2);
906#else
907 buf2 = buf;
908#endif
909
910 /*
911 * count trigrams
912 */
913 tptr = make_trigrams(tptr, buf2, bytelen, charlen);
914
915#ifdef IGNORECASE
916 pfree(buf2);
917#endif
918 }
919
920 pfree(buf);
921
922 if ((len = tptr - GETARR(trg)) == 0)
923 return trg;
924
925 /*
926 * Make trigrams unique.
927 */
928 if (len > 1)
929 {
930 qsort(GETARR(trg), len, sizeof(trgm), comp_trgm);
931 len = qunique(GETARR(trg), len, sizeof(trgm), comp_trgm);
932 }
933
935
936 return trg;
937}
939uint32
940trgm2int(trgm *ptr)
941{
942 uint32 val = 0;
943
944 val |= *(((unsigned char *) ptr));
945 val <<= 8;
946 val |= *(((unsigned char *) ptr) + 1);
947 val <<= 8;
948 val |= *(((unsigned char *) ptr) + 2);
949
950 return val;
951}
953Datum
955{
956 text *in = PG_GETARG_TEXT_PP(0);
957 TRGM *trg;
958 Datum *d;
959 ArrayType *a;
960 trgm *ptr;
961 int i;
962
964 d = (Datum *) palloc(sizeof(Datum) * (1 + ARRNELEM(trg)));
965
966 for (i = 0, ptr = GETARR(trg); i < ARRNELEM(trg); i++, ptr++)
967 {
969
971 {
972 snprintf(VARDATA(item), 12, "0x%06x", trgm2int(ptr));
973 SET_VARSIZE(item, VARHDRSZ + strlen(VARDATA(item)));
974 }
975 else
976 {
977 SET_VARSIZE(item, VARHDRSZ + 3);
978 CPTRGM(VARDATA(item), ptr);
979 }
980 d[i] = PointerGetDatum(item);
981 }
982
983 a = construct_array_builtin(d, ARRNELEM(trg), TEXTOID);
984
985 for (i = 0; i < ARRNELEM(trg); i++)
987
988 pfree(d);
989 pfree(trg);
990 PG_FREE_IF_COPY(in, 0);
991
993}
995float4
996cnt_sml(TRGM *trg1, TRGM *trg2, bool inexact)
997{
998 trgm *ptr1,
999 *ptr2;
1000 int count = 0;
1001 int len1,
1002 len2;
1003
1004 ptr1 = GETARR(trg1);
1005 ptr2 = GETARR(trg2);
1006
1007 len1 = ARRNELEM(trg1);
1008 len2 = ARRNELEM(trg2);
1009
1010 /* explicit test is needed to avoid 0/0 division when both lengths are 0 */
1011 if (len1 <= 0 || len2 <= 0)
1012 return (float4) 0.0;
1013
1014 while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
1015 {
1016 int res = CMPTRGM(ptr1, ptr2);
1017
1018 if (res < 0)
1019 ptr1++;
1020 else if (res > 0)
1021 ptr2++;
1022 else
1023 {
1024 ptr1++;
1025 ptr2++;
1026 count++;
1027 }
1028 }
1029
1030 /*
1031 * If inexact then len2 is equal to count, because we don't know actual
1032 * length of second string in inexact search and we can assume that count
1033 * is a lower bound of len2.
1034 */
1035 return CALCSML(count, len1, inexact ? count : len2);
1036}
1037
1038
1039/*
1040 * Returns whether trg2 contains all trigrams in trg1.
1041 * This relies on the trigram arrays being sorted.
1043bool
1044trgm_contained_by(TRGM *trg1, TRGM *trg2)
1045{
1046 trgm *ptr1,
1047 *ptr2;
1048 int len1,
1049 len2;
1050
1051 ptr1 = GETARR(trg1);
1052 ptr2 = GETARR(trg2);
1053
1054 len1 = ARRNELEM(trg1);
1055 len2 = ARRNELEM(trg2);
1056
1057 while (ptr1 - GETARR(trg1) < len1 && ptr2 - GETARR(trg2) < len2)
1058 {
1059 int res = CMPTRGM(ptr1, ptr2);
1060
1061 if (res < 0)
1062 return false;
1063 else if (res > 0)
1064 ptr2++;
1065 else
1066 {
1067 ptr1++;
1068 ptr2++;
1069 }
1070 }
1071 if (ptr1 - GETARR(trg1) < len1)
1072 return false;
1073 else
1074 return true;
1075}
1076
1077/*
1078 * Return a palloc'd boolean array showing, for each trigram in "query",
1079 * whether it is present in the trigram array "key".
1080 * This relies on the "key" array being sorted, but "query" need not be.
1082bool *
1084{
1085 bool *result;
1086 trgm *ptrq = GETARR(query),
1087 *ptrk = GETARR(key);
1088 int lenq = ARRNELEM(query),
1089 lenk = ARRNELEM(key),
1090 i;
1091
1092 result = (bool *) palloc0(lenq * sizeof(bool));
1093
1094 /* for each query trigram, do a binary search in the key array */
1095 for (i = 0; i < lenq; i++)
1096 {
1097 int lo = 0;
1098 int hi = lenk;
1099
1100 while (lo < hi)
1101 {
1102 int mid = (lo + hi) / 2;
1103 int res = CMPTRGM(ptrq, ptrk + mid);
1104
1105 if (res < 0)
1106 hi = mid;
1107 else if (res > 0)
1108 lo = mid + 1;
1109 else
1110 {
1111 result[i] = true;
1112 break;
1113 }
1114 }
1115 ptrq++;
1116 }
1117
1118 return result;
1119}
1121Datum
1123{
1124 text *in1 = PG_GETARG_TEXT_PP(0);
1125 text *in2 = PG_GETARG_TEXT_PP(1);
1126 TRGM *trg1,
1127 *trg2;
1128 float4 res;
1129
1130 trg1 = generate_trgm(VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1));
1131 trg2 = generate_trgm(VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2));
1132
1133 res = cnt_sml(trg1, trg2, false);
1134
1135 pfree(trg1);
1136 pfree(trg2);
1137 PG_FREE_IF_COPY(in1, 0);
1138 PG_FREE_IF_COPY(in2, 1);
1139
1141}
1143Datum
1145{
1146 text *in1 = PG_GETARG_TEXT_PP(0);
1147 text *in2 = PG_GETARG_TEXT_PP(1);
1148 float4 res;
1149
1151 VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
1152 0);
1153
1154 PG_FREE_IF_COPY(in1, 0);
1155 PG_FREE_IF_COPY(in2, 1);
1157}
1159Datum
1161{
1162 text *in1 = PG_GETARG_TEXT_PP(0);
1163 text *in2 = PG_GETARG_TEXT_PP(1);
1164 float4 res;
1165
1167 VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
1169
1170 PG_FREE_IF_COPY(in1, 0);
1171 PG_FREE_IF_COPY(in2, 1);
1173}
1175Datum
1177{
1179 PG_GETARG_DATUM(0),
1180 PG_GETARG_DATUM(1)));
1181
1182 PG_RETURN_FLOAT4(1.0 - res);
1183}
1185Datum
1187{
1189 PG_GETARG_DATUM(0),
1190 PG_GETARG_DATUM(1)));
1191
1193}
1195Datum
1197{
1198 text *in1 = PG_GETARG_TEXT_PP(0);
1199 text *in2 = PG_GETARG_TEXT_PP(1);
1200 float4 res;
1201
1203 VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
1205
1206 PG_FREE_IF_COPY(in1, 0);
1207 PG_FREE_IF_COPY(in2, 1);
1209}
1211Datum
1213{
1214 text *in1 = PG_GETARG_TEXT_PP(0);
1215 text *in2 = PG_GETARG_TEXT_PP(1);
1216 float4 res;
1217
1219 VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
1221
1222 PG_FREE_IF_COPY(in1, 0);
1223 PG_FREE_IF_COPY(in2, 1);
1225}
1227Datum
1229{
1230 text *in1 = PG_GETARG_TEXT_PP(0);
1231 text *in2 = PG_GETARG_TEXT_PP(1);
1232 float4 res;
1233
1235 VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
1236 0);
1237
1238 PG_FREE_IF_COPY(in1, 0);
1239 PG_FREE_IF_COPY(in2, 1);
1240 PG_RETURN_FLOAT4(1.0 - res);
1241}
1243Datum
1245{
1246 text *in1 = PG_GETARG_TEXT_PP(0);
1247 text *in2 = PG_GETARG_TEXT_PP(1);
1248 float4 res;
1249
1251 VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
1252 0);
1253
1254 PG_FREE_IF_COPY(in1, 0);
1255 PG_FREE_IF_COPY(in2, 1);
1256 PG_RETURN_FLOAT4(1.0 - res);
1257}
1259Datum
1261{
1262 text *in1 = PG_GETARG_TEXT_PP(0);
1263 text *in2 = PG_GETARG_TEXT_PP(1);
1264 float4 res;
1265
1267 VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
1269
1270 PG_FREE_IF_COPY(in1, 0);
1271 PG_FREE_IF_COPY(in2, 1);
1273}
1275Datum
1277{
1278 text *in1 = PG_GETARG_TEXT_PP(0);
1279 text *in2 = PG_GETARG_TEXT_PP(1);
1280 float4 res;
1281
1283 VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
1285
1286 PG_FREE_IF_COPY(in1, 0);
1287 PG_FREE_IF_COPY(in2, 1);
1289}
1291Datum
1293{
1294 text *in1 = PG_GETARG_TEXT_PP(0);
1295 text *in2 = PG_GETARG_TEXT_PP(1);
1296 float4 res;
1297
1299 VARDATA_ANY(in2), VARSIZE_ANY_EXHDR(in2),
1301
1302 PG_FREE_IF_COPY(in1, 0);
1303 PG_FREE_IF_COPY(in2, 1);
1304 PG_RETURN_FLOAT4(1.0 - res);
1305}
1307Datum
1309{
1310 text *in1 = PG_GETARG_TEXT_PP(0);
1311 text *in2 = PG_GETARG_TEXT_PP(1);
1312 float4 res;
1313
1315 VARDATA_ANY(in1), VARSIZE_ANY_EXHDR(in1),
1317
1318 PG_FREE_IF_COPY(in1, 0);
1319 PG_FREE_IF_COPY(in2, 1);
1320 PG_RETURN_FLOAT4(1.0 - res);
1321}
ArrayType * construct_array_builtin(Datum *elems, int nelems, Oid elmtype)
Definition: arrayfuncs.c:3381
uint8_t uint8
Definition: c.h:483
#define Max(x, y)
Definition: c.h:952
#define VARHDRSZ
Definition: c.h:646
#define Assert(condition)
Definition: c.h:812
uint32_t uint32
Definition: c.h:485
float float4
Definition: c.h:583
size_t Size
Definition: c.h:559
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
#define MaxAllocSize
Definition: fe_memutils.h:22
char * OidOutputFunctionCall(Oid functionId, Datum val)
Definition: fmgr.c:1763
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:309
#define DirectFunctionCall2(func, arg1, arg2)
Definition: fmgr.h:643
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_GETARG_FLOAT4(n)
Definition: fmgr.h:281
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define PG_RETURN_FLOAT4(x)
Definition: fmgr.h:366
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
char * str_tolower(const char *buff, size_t nbytes, Oid collid)
Definition: formatting.c:1591
void DefineCustomRealVariable(const char *name, const char *short_desc, const char *long_desc, double *valueAddr, double bootValue, double minValue, double maxValue, GucContext context, int flags, GucRealCheckHook check_hook, GucRealAssignHook assign_hook, GucShowHook show_hook)
Definition: guc.c:5188
void SetConfigOption(const char *name, const char *value, GucContext context, GucSource source)
Definition: guc.c:4332
void MarkGUCPrefixReserved(const char *className)
Definition: guc.c:5279
@ PGC_S_SESSION
Definition: guc.h:122
@ PGC_USERSET
Definition: guc.h:75
const char * str
#define CALCGTSIZE(flag, siglen)
Definition: hstore_gist.c:60
long val
Definition: informix.c:689
static int pg_cmp_s32(int32 a, int32 b)
Definition: int.h:646
int b
Definition: isn.c:69
int a
Definition: isn.c:68
int j
Definition: isn.c:73
int i
Definition: isn.c:72
void getTypeOutputInfo(Oid type, Oid *typOutput, bool *typIsVarlena)
Definition: lsyscache.c:2907
int pg_database_encoding_max_length(void)
Definition: mbutils.c:1546
int pg_mblen(const char *mbstr)
Definition: mbutils.c:1023
void pfree(void *pointer)
Definition: mcxt.c:1521
void * palloc0(Size size)
Definition: mcxt.c:1347
void * palloc(Size size)
Definition: mcxt.c:1317
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:49
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:80
const void size_t len
return crc
uint32 pg_crc32
Definition: pg_crc.h:37
#define INIT_LEGACY_CRC32(crc)
Definition: pg_crc.h:79
#define COMP_LEGACY_CRC32(crc, data, len)
Definition: pg_crc.h:81
#define FIN_LEGACY_CRC32(crc)
Definition: pg_crc.h:80
static char * buf
Definition: pg_test_fsync.c:72
#define snprintf
Definition: port.h:238
#define qsort(a, b, c, d)
Definition: port.h:447
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
static Datum Float4GetDatum(float4 X)
Definition: postgres.h:475
uintptr_t Datum
Definition: postgres.h:64
static float4 DatumGetFloat4(Datum X)
Definition: postgres.h:458
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
unsigned int Oid
Definition: postgres_ext.h:31
static size_t qunique(void *array, size_t elements, size_t width, int(*compare)(const void *, const void *))
Definition: qunique.h:21
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
uint16 StrategyNumber
Definition: stratnum.h:22
Definition: trgm.h:61
uint8 flag
Definition: trgm.h:63
Definition: type.h:96
int index
Definition: trgm_op.c:49
trgm trg
Definition: trgm_op.c:48
Definition: c.h:641
#define CALCSML(count, len1, len2)
Definition: trgm.h:110
#define ISWORDCHR(c)
Definition: trgm.h:53
#define WordSimilarityStrategyNumber
Definition: trgm.h:35
#define StrictWordSimilarityStrategyNumber
Definition: trgm.h:37
#define ISESCAPECHAR(x)
Definition: trgm.h:57
#define ARRNELEM(x)
Definition: trgm.h:101
#define RPADDING
Definition: trgm.h:17
#define LPADDING
Definition: trgm.h:16
#define SimilarityStrategyNumber
Definition: trgm.h:29
#define ISWILDCARDCHAR(x)
Definition: trgm.h:58
#define CMPTRGM(a, b)
Definition: trgm.h:45
char trgm[3]
Definition: trgm.h:41
#define CPTRGM(a, b)
Definition: trgm.h:47
#define ISPRINTABLETRGM(t)
Definition: trgm.h:55
#define GETARR(x)
Definition: trgm.h:100
#define ARRKEY
Definition: trgm.h:90
#define TRGMHDRSIZE
Definition: trgm.h:67
static float4 iterate_word_similarity(int *trg2indexes, bool *found, int ulen1, int len2, int len, uint8 flags, TrgmBound *bounds)
Definition: trgm_op.c:456
uint8 TrgmBound
Definition: trgm_op.c:53
Datum strict_word_similarity_commutator_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1274
void _PG_init(void)
Definition: trgm_op.c:65
Datum set_limit(PG_FUNCTION_ARGS)
Definition: trgm_op.c:113
static int comp_trgm(const void *a, const void *b)
Definition: trgm_op.c:164
double strict_word_similarity_threshold
Definition: trgm_op.c:26
TRGM * generate_trgm(char *str, int slen)
Definition: trgm_op.c:359
PG_MODULE_MAGIC
Definition: trgm_op.c:21
uint32 trgm2int(trgm *ptr)
Definition: trgm_op.c:938
#define WORD_SIMILARITY_CHECK_ONLY
Definition: trgm_op.c:58
static void protect_out_of_mem(int slen)
Definition: trgm_op.c:342
Datum word_similarity(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1142
Datum strict_word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1306
void compact_trigram(trgm *tptr, char *str, int bytelen)
Definition: trgm_op.c:201
bool * trgm_presence_map(TRGM *query, TRGM *key)
Definition: trgm_op.c:1081
PG_FUNCTION_INFO_V1(set_limit)
static float4 calc_word_similarity(char *str1, int slen1, char *str2, int slen2, uint8 flags)
Definition: trgm_op.c:624
double word_similarity_threshold
Definition: trgm_op.c:25
Datum word_similarity_dist_commutator_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1242
double index_strategy_get_limit(StrategyNumber strategy)
Definition: trgm_op.c:135
Datum similarity(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1120
static pos_trgm * make_positional_trgm(trgm *trg1, int len1, trgm *trg2, int len2)
Definition: trgm_op.c:400
double similarity_threshold
Definition: trgm_op.c:24
static int comp_ptrgm(const void *v1, const void *v2)
Definition: trgm_op.c:427
static char * find_word(char *str, int lenstr, char **endword, int *charlen)
Definition: trgm_op.c:174
Datum show_trgm(PG_FUNCTION_ARGS)
Definition: trgm_op.c:952
bool trgm_contained_by(TRGM *trg1, TRGM *trg2)
Definition: trgm_op.c:1042
#define TRGM_BOUND_RIGHT
Definition: trgm_op.c:55
Datum show_limit(PG_FUNCTION_ARGS)
Definition: trgm_op.c:158
Datum strict_word_similarity_dist_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1290
Datum word_similarity_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1194
Datum word_similarity_commutator_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1210
#define WORD_SIMILARITY_STRICT
Definition: trgm_op.c:59
#define TRGM_BOUND_LEFT
Definition: trgm_op.c:54
TRGM * generate_wildcard_trgm(const char *str, int slen)
Definition: trgm_op.c:869
static trgm * make_trigrams(trgm *tptr, char *str, int bytelen, int charlen)
Definition: trgm_op.c:226
float4 cnt_sml(TRGM *trg1, TRGM *trg2, bool inexact)
Definition: trgm_op.c:994
static int generate_trgm_only(trgm *trg, char *str, int slen, TrgmBound *bounds)
Definition: trgm_op.c:278
Datum similarity_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1184
Datum word_similarity_dist_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1226
static const char * get_wildcard_part(const char *str, int lenstr, char *buf, int *bytelen, int *charlen)
Definition: trgm_op.c:724
Datum strict_word_similarity(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1158
Datum similarity_dist(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1174
Datum strict_word_similarity_op(PG_FUNCTION_ARGS)
Definition: trgm_op.c:1258
#define VARDATA(PTR)
Definition: varatt.h:278
#define VARDATA_ANY(PTR)
Definition: varatt.h:324
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317