Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * spgtextproc.c
4 : : * implementation of radix tree (compressed trie) over text
5 : : *
6 : : * In a text_ops SPGiST index, inner tuples can have a prefix which is the
7 : : * common prefix of all strings indexed under that tuple. The node labels
8 : : * represent the next byte of the string(s) after the prefix. Assuming we
9 : : * always use the longest possible prefix, we will get more than one node
10 : : * label unless the prefix length is restricted by SPGIST_MAX_PREFIX_LENGTH.
11 : : *
12 : : * To reconstruct the indexed string for any index entry, concatenate the
13 : : * inner-tuple prefixes and node labels starting at the root and working
14 : : * down to the leaf entry, then append the datum in the leaf entry.
15 : : * (While descending the tree, "level" is the number of bytes reconstructed
16 : : * so far.)
17 : : *
18 : : * However, there are two special cases for node labels: -1 indicates that
19 : : * there are no more bytes after the prefix-so-far, and -2 indicates that we
20 : : * had to split an existing allTheSame tuple (in such a case we have to create
21 : : * a node label that doesn't correspond to any string byte). In either case,
22 : : * the node label does not contribute anything to the reconstructed string.
23 : : *
24 : : * Previously, we used a node label of zero for both special cases, but
25 : : * this was problematic because one can't tell whether a string ending at
26 : : * the current level can be pushed down into such a child node. For
27 : : * backwards compatibility, we still support such node labels for reading;
28 : : * but no new entries will ever be pushed down into a zero-labeled child.
29 : : * No new entries ever get pushed into a -2-labeled child, either.
30 : : *
31 : : *
32 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
33 : : * Portions Copyright (c) 1994, Regents of the University of California
34 : : *
35 : : * IDENTIFICATION
36 : : * src/backend/access/spgist/spgtextproc.c
37 : : *
38 : : *-------------------------------------------------------------------------
39 : : */
40 : : #include "postgres.h"
41 : :
42 : : #include "access/spgist.h"
43 : : #include "catalog/pg_type.h"
44 : : #include "common/int.h"
45 : : #include "mb/pg_wchar.h"
46 : : #include "utils/datum.h"
47 : : #include "utils/fmgrprotos.h"
48 : : #include "utils/pg_locale.h"
49 : : #include "utils/varlena.h"
50 : : #include "varatt.h"
51 : :
52 : :
53 : : /*
54 : : * In the worst case, an inner tuple in a text radix tree could have as many
55 : : * as 258 nodes (one for each possible byte value, plus the two special
56 : : * cases). Each node can take 16 bytes on MAXALIGN=8 machines. The inner
57 : : * tuple must fit on an index page of size BLCKSZ. Rather than assuming we
58 : : * know the exact amount of overhead imposed by page headers, tuple headers,
59 : : * etc, we leave 100 bytes for that (the actual overhead should be no more
60 : : * than 56 bytes at this writing, so there is slop in this number).
61 : : * So we can safely create prefixes up to BLCKSZ - 258 * 16 - 100 bytes long.
62 : : * Unfortunately, because 258 * 16 is over 4K, there is no safe prefix length
63 : : * when BLCKSZ is less than 8K; it is always possible to get "SPGiST inner
64 : : * tuple size exceeds maximum" if there are too many distinct next-byte values
65 : : * at a given place in the tree. Since use of nonstandard block sizes appears
66 : : * to be negligible in the field, we just live with that fact for now,
67 : : * choosing a max prefix size of 32 bytes when BLCKSZ is configured smaller
68 : : * than default.
69 : : */
70 : : #define SPGIST_MAX_PREFIX_LENGTH Max((int) (BLCKSZ - 258 * 16 - 100), 32)
71 : :
72 : : /*
73 : : * Strategy for collation aware operator on text is equal to btree strategy
74 : : * plus value of 10.
75 : : *
76 : : * Current collation aware strategies and their corresponding btree strategies:
77 : : * 11 BTLessStrategyNumber
78 : : * 12 BTLessEqualStrategyNumber
79 : : * 14 BTGreaterEqualStrategyNumber
80 : : * 15 BTGreaterStrategyNumber
81 : : */
82 : : #define SPG_STRATEGY_ADDITION (10)
83 : : #define SPG_IS_COLLATION_AWARE_STRATEGY(s) ((s) > SPG_STRATEGY_ADDITION \
84 : : && (s) != RTPrefixStrategyNumber)
85 : :
86 : : /* Struct for sorting values in picksplit */
87 : : typedef struct spgNodePtr
88 : : {
89 : : Datum d;
90 : : int i;
91 : : int16 c;
92 : : } spgNodePtr;
93 : :
94 : :
95 : : Datum
5253 tgl@sss.pgh.pa.us 96 :CBC 55 : spg_text_config(PG_FUNCTION_ARGS)
97 : : {
98 : : #ifdef NOT_USED
99 : : spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0);
100 : : #endif
101 : 55 : spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
102 : :
103 : 55 : cfg->prefixType = TEXTOID;
4348 104 : 55 : cfg->labelType = INT2OID;
5251 105 : 55 : cfg->canReturnData = true;
5253 106 : 55 : cfg->longValuesOK = true; /* suffixing will shorten long values */
107 : 55 : PG_RETURN_VOID();
108 : : }
109 : :
110 : : /*
111 : : * Form a text datum from the given not-necessarily-null-terminated string,
112 : : * using short varlena header format if possible
113 : : */
114 : : static Datum
115 : 170662 : formTextDatum(const char *data, int datalen)
116 : : {
117 : : char *p;
118 : :
119 : 170662 : p = (char *) palloc(datalen + VARHDRSZ);
120 : :
121 [ + - ]: 170662 : if (datalen + VARHDRSZ_SHORT <= VARATT_SHORT_MAX)
122 : : {
123 : 170662 : SET_VARSIZE_SHORT(p, datalen + VARHDRSZ_SHORT);
124 [ + + ]: 170662 : if (datalen)
125 : 160183 : memcpy(p + VARHDRSZ_SHORT, data, datalen);
126 : : }
127 : : else
128 : : {
5253 tgl@sss.pgh.pa.us 129 :UBC 0 : SET_VARSIZE(p, datalen + VARHDRSZ);
130 : 0 : memcpy(p + VARHDRSZ, data, datalen);
131 : : }
132 : :
5253 tgl@sss.pgh.pa.us 133 :CBC 170662 : return PointerGetDatum(p);
134 : : }
135 : :
136 : : /*
137 : : * Find the length of the common prefix of a and b
138 : : */
139 : : static int
140 : 63234 : commonPrefix(const char *a, const char *b, int lena, int lenb)
141 : : {
142 : 63234 : int i = 0;
143 : :
144 [ + + + + : 4424666 : while (i < lena && i < lenb && *a == *b)
+ + ]
145 : : {
146 : 4361432 : a++;
147 : 4361432 : b++;
148 : 4361432 : i++;
149 : : }
150 : :
151 : 63234 : return i;
152 : : }
153 : :
154 : : /*
155 : : * Binary search an array of int16 datums for a match to c
156 : : *
157 : : * On success, *i gets the match location; on failure, it gets where to insert
158 : : */
159 : : static bool
186 peter@eisentraut.org 160 :GNC 139172 : searchChar(const Datum *nodeLabels, int nNodes, int16 c, int *i)
161 : : {
5253 tgl@sss.pgh.pa.us 162 :CBC 139172 : int StopLow = 0,
163 : 139172 : StopHigh = nNodes;
164 : :
165 [ + + ]: 382030 : while (StopLow < StopHigh)
166 : : {
167 : 381118 : int StopMiddle = (StopLow + StopHigh) >> 1;
4348 168 : 381118 : int16 middle = DatumGetInt16(nodeLabels[StopMiddle]);
169 : :
5253 170 [ + + ]: 381118 : if (c < middle)
171 : 120835 : StopHigh = StopMiddle;
172 [ + + ]: 260283 : else if (c > middle)
173 : 122023 : StopLow = StopMiddle + 1;
174 : : else
175 : : {
176 : 138260 : *i = StopMiddle;
177 : 138260 : return true;
178 : : }
179 : : }
180 : :
181 : 912 : *i = StopHigh;
182 : 912 : return false;
183 : : }
184 : :
185 : : Datum
186 : 139591 : spg_text_choose(PG_FUNCTION_ARGS)
187 : : {
188 : 139591 : spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
189 : 139591 : spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
190 : 139591 : text *inText = DatumGetTextPP(in->datum);
191 [ + - ]: 139591 : char *inStr = VARDATA_ANY(inText);
192 [ - + - - : 139591 : int inSize = VARSIZE_ANY_EXHDR(inText);
- - - - +
- ]
4348 193 : 139591 : char *prefixStr = NULL;
194 : 139591 : int prefixSize = 0;
5253 195 : 139591 : int commonLen = 0;
4348 196 : 139591 : int16 nodeChar = 0;
197 : 139591 : int i = 0;
198 : :
199 : : /* Check for prefix match, set nodeChar to first byte after prefix */
5253 200 [ + + ]: 139591 : if (in->hasPrefix)
201 : : {
202 : 55240 : text *prefixText = DatumGetTextPP(in->prefixDatum);
203 : :
4348 204 [ + - ]: 55240 : prefixStr = VARDATA_ANY(prefixText);
205 [ - + - - : 55240 : prefixSize = VARSIZE_ANY_EXHDR(prefixText);
- - - - +
- ]
206 : :
5253 207 : 55240 : commonLen = commonPrefix(inStr + in->level,
208 : : prefixStr,
209 : 55240 : inSize - in->level,
210 : : prefixSize);
211 : :
212 [ + + ]: 55240 : if (commonLen == prefixSize)
213 : : {
214 [ + + ]: 54821 : if (inSize - in->level > commonLen)
4348 215 : 50717 : nodeChar = *(unsigned char *) (inStr + in->level + commonLen);
216 : : else
217 : 4104 : nodeChar = -1;
218 : : }
219 : : else
220 : : {
221 : : /* Must split tuple because incoming value doesn't match prefix */
5253 222 : 419 : out->resultType = spgSplitTuple;
223 : :
224 [ + + ]: 419 : if (commonLen == 0)
225 : : {
226 : 15 : out->result.splitTuple.prefixHasPrefix = false;
227 : : }
228 : : else
229 : : {
230 : 404 : out->result.splitTuple.prefixHasPrefix = true;
231 : 404 : out->result.splitTuple.prefixPrefixDatum =
232 : 404 : formTextDatum(prefixStr, commonLen);
233 : : }
3542 234 : 419 : out->result.splitTuple.prefixNNodes = 1;
146 michael@paquier.xyz 235 :GNC 419 : out->result.splitTuple.prefixNodeLabels = palloc_object(Datum);
3542 tgl@sss.pgh.pa.us 236 :CBC 838 : out->result.splitTuple.prefixNodeLabels[0] =
4348 237 : 419 : Int16GetDatum(*(unsigned char *) (prefixStr + commonLen));
238 : :
3542 239 : 419 : out->result.splitTuple.childNodeN = 0;
240 : :
5253 241 [ + + ]: 419 : if (prefixSize - commonLen == 1)
242 : : {
243 : 411 : out->result.splitTuple.postfixHasPrefix = false;
244 : : }
245 : : else
246 : : {
247 : 8 : out->result.splitTuple.postfixHasPrefix = true;
248 : 8 : out->result.splitTuple.postfixPrefixDatum =
249 : 8 : formTextDatum(prefixStr + commonLen + 1,
250 : 8 : prefixSize - commonLen - 1);
251 : : }
252 : :
253 : 419 : PG_RETURN_VOID();
254 : : }
255 : : }
256 [ + + ]: 84351 : else if (inSize > in->level)
257 : : {
4348 258 : 83676 : nodeChar = *(unsigned char *) (inStr + in->level);
259 : : }
260 : : else
261 : : {
262 : 675 : nodeChar = -1;
263 : : }
264 : :
265 : : /* Look up nodeChar in the node label array */
5253 266 [ + + ]: 139172 : if (searchChar(in->nodeLabels, in->nNodes, nodeChar, &i))
267 : : {
268 : : /*
269 : : * Descend to existing node. (If in->allTheSame, the core code will
270 : : * ignore our nodeN specification here, but that's OK. We still have
271 : : * to provide the correct levelAdd and restDatum values, and those are
272 : : * the same regardless of which node gets chosen by core.)
273 : : */
274 : : int levelAdd;
275 : :
276 : 138260 : out->resultType = spgMatchNode;
277 : 138260 : out->result.matchNode.nodeN = i;
4348 278 : 138260 : levelAdd = commonLen;
279 [ + + ]: 138260 : if (nodeChar >= 0)
280 : 133485 : levelAdd++;
281 : 138260 : out->result.matchNode.levelAdd = levelAdd;
282 [ + + ]: 138260 : if (inSize - in->level - levelAdd > 0)
5253 283 : 133481 : out->result.matchNode.restDatum =
4348 284 : 133481 : formTextDatum(inStr + in->level + levelAdd,
285 : 133481 : inSize - in->level - levelAdd);
286 : : else
5253 287 : 4779 : out->result.matchNode.restDatum =
288 : 4779 : formTextDatum(NULL, 0);
289 : : }
290 [ + + ]: 912 : else if (in->allTheSame)
291 : : {
292 : : /*
293 : : * Can't use AddNode action, so split the tuple. The upper tuple has
294 : : * the same prefix as before and uses a dummy node label -2 for the
295 : : * lower tuple. The lower tuple has no prefix and the same node
296 : : * labels as the original tuple.
297 : : *
298 : : * Note: it might seem tempting to shorten the upper tuple's prefix,
299 : : * if it has one, then use its last byte as label for the lower tuple.
300 : : * But that doesn't win since we know the incoming value matches the
301 : : * whole prefix: we'd just end up splitting the lower tuple again.
302 : : */
303 : 4 : out->resultType = spgSplitTuple;
304 : 4 : out->result.splitTuple.prefixHasPrefix = in->hasPrefix;
305 : 4 : out->result.splitTuple.prefixPrefixDatum = in->prefixDatum;
3542 306 : 4 : out->result.splitTuple.prefixNNodes = 1;
146 michael@paquier.xyz 307 :GNC 4 : out->result.splitTuple.prefixNodeLabels = palloc_object(Datum);
3542 tgl@sss.pgh.pa.us 308 :CBC 4 : out->result.splitTuple.prefixNodeLabels[0] = Int16GetDatum(-2);
309 : 4 : out->result.splitTuple.childNodeN = 0;
5253 310 : 4 : out->result.splitTuple.postfixHasPrefix = false;
311 : : }
312 : : else
313 : : {
314 : : /* Add a node for the not-previously-seen nodeChar value */
315 : 908 : out->resultType = spgAddNode;
4348 316 : 908 : out->result.addNode.nodeLabel = Int16GetDatum(nodeChar);
5253 317 : 908 : out->result.addNode.nodeN = i;
318 : : }
319 : :
320 : 139172 : PG_RETURN_VOID();
321 : : }
322 : :
323 : : /* qsort comparator to sort spgNodePtr structs by "c" */
324 : : static int
325 : 73246 : cmpNodePtr(const void *a, const void *b)
326 : : {
327 : 73246 : const spgNodePtr *aa = (const spgNodePtr *) a;
328 : 73246 : const spgNodePtr *bb = (const spgNodePtr *) b;
329 : :
809 nathan@postgresql.or 330 : 73246 : return pg_cmp_s16(aa->c, bb->c);
331 : : }
332 : :
333 : : Datum
5253 tgl@sss.pgh.pa.us 334 : 321 : spg_text_picksplit(PG_FUNCTION_ARGS)
335 : : {
336 : 321 : spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
337 : 321 : spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
338 : 321 : text *text0 = DatumGetTextPP(in->datums[0]);
339 : : int i,
340 : : commonLen;
341 : : spgNodePtr *nodes;
342 : :
343 : : /* Identify longest common prefix, if any */
344 [ - + - - : 321 : commonLen = VARSIZE_ANY_EXHDR(text0);
- - - - +
- ]
345 [ + + + + ]: 8315 : for (i = 1; i < in->nTuples && commonLen > 0; i++)
346 : : {
347 : 7994 : text *texti = DatumGetTextPP(in->datums[i]);
348 [ + - ]: 7994 : int tmp = commonPrefix(VARDATA_ANY(text0),
349 [ + - ]: 7994 : VARDATA_ANY(texti),
350 [ - + - - : 7994 : VARSIZE_ANY_EXHDR(text0),
- - - - +
- ]
351 [ - + - - : 7994 : VARSIZE_ANY_EXHDR(texti));
- - - - +
- ]
352 : :
353 [ + + ]: 7994 : if (tmp < commonLen)
354 : 254 : commonLen = tmp;
355 : : }
356 : :
357 : : /*
358 : : * Limit the prefix length, if necessary, to ensure that the resulting
359 : : * inner tuple will fit on a page.
360 : : */
361 : 321 : commonLen = Min(commonLen, SPGIST_MAX_PREFIX_LENGTH);
362 : :
363 : : /* Set node prefix to be that string, if it's not empty */
364 [ + + ]: 321 : if (commonLen == 0)
365 : : {
366 : 262 : out->hasPrefix = false;
367 : : }
368 : : else
369 : : {
370 : 59 : out->hasPrefix = true;
371 [ + - ]: 59 : out->prefixDatum = formTextDatum(VARDATA_ANY(text0), commonLen);
372 : : }
373 : :
374 : : /* Extract the node label (first non-common byte) from each value */
146 michael@paquier.xyz 375 :GNC 321 : nodes = palloc_array(spgNodePtr, in->nTuples);
376 : :
5253 tgl@sss.pgh.pa.us 377 [ + + ]:CBC 32252 : for (i = 0; i < in->nTuples; i++)
378 : : {
379 : 31931 : text *texti = DatumGetTextPP(in->datums[i]);
380 : :
381 [ + + - - : 31931 : if (commonLen < VARSIZE_ANY_EXHDR(texti))
- - - - +
- + + ]
4348 382 [ + - ]: 27377 : nodes[i].c = *(unsigned char *) (VARDATA_ANY(texti) + commonLen);
383 : : else
384 : 4554 : nodes[i].c = -1; /* use -1 if string is all common */
5253 385 : 31931 : nodes[i].i = i;
386 : 31931 : nodes[i].d = in->datums[i];
387 : : }
388 : :
389 : : /*
390 : : * Sort by label values so that we can group the values into nodes. This
391 : : * also ensures that the nodes are ordered by label value, allowing the
392 : : * use of binary search in searchChar.
393 : : */
394 : 321 : qsort(nodes, in->nTuples, sizeof(*nodes), cmpNodePtr);
395 : :
396 : : /* And emit results */
397 : 321 : out->nNodes = 0;
146 michael@paquier.xyz 398 :GNC 321 : out->nodeLabels = palloc_array(Datum, in->nTuples);
399 : 321 : out->mapTuplesToNodes = palloc_array(int, in->nTuples);
400 : 321 : out->leafTupleDatums = palloc_array(Datum, in->nTuples);
401 : :
5253 tgl@sss.pgh.pa.us 402 [ + + ]:CBC 32252 : for (i = 0; i < in->nTuples; i++)
403 : : {
404 : 31931 : text *texti = DatumGetTextPP(nodes[i].d);
405 : : Datum leafD;
406 : :
407 [ + + + + ]: 31931 : if (i == 0 || nodes[i].c != nodes[i - 1].c)
408 : : {
4348 409 : 2007 : out->nodeLabels[out->nNodes] = Int16GetDatum(nodes[i].c);
5253 410 : 2007 : out->nNodes++;
411 : : }
412 : :
413 [ + + - - : 31931 : if (commonLen < VARSIZE_ANY_EXHDR(texti))
- - - - +
- + + ]
414 : 27377 : leafD = formTextDatum(VARDATA_ANY(texti) + commonLen + 1,
415 [ - + - - : 27377 : VARSIZE_ANY_EXHDR(texti) - commonLen - 1);
- - - - +
- + - ]
416 : : else
417 : 4554 : leafD = formTextDatum(NULL, 0);
418 : :
419 : 31931 : out->leafTupleDatums[nodes[i].i] = leafD;
420 : 31931 : out->mapTuplesToNodes[nodes[i].i] = out->nNodes - 1;
421 : : }
422 : :
423 : 321 : PG_RETURN_VOID();
424 : : }
425 : :
426 : : Datum
427 : 1292 : spg_text_inner_consistent(PG_FUNCTION_ARGS)
428 : : {
429 : 1292 : spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
430 : 1292 : spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
608 jdavis@postgresql.or 431 : 1292 : bool collate_is_c = pg_newlocale_from_collation(PG_GET_COLLATION())->collate_is_c;
432 : : text *reconstructedValue;
433 : : text *reconstrText;
434 : : int maxReconstrLen;
5253 tgl@sss.pgh.pa.us 435 : 1292 : text *prefixText = NULL;
436 : 1292 : int prefixSize = 0;
437 : : int i;
438 : :
439 : : /*
440 : : * Reconstruct values represented at this tuple, including parent data,
441 : : * prefix of this tuple if any, and the node label if it's non-dummy.
442 : : * in->level should be the length of the previously reconstructed value,
443 : : * and the number of bytes added here is prefixSize or prefixSize + 1.
444 : : *
445 : : * Note: we assume that in->reconstructedValue isn't toasted and doesn't
446 : : * have a short varlena header. This is okay because it must have been
447 : : * created by a previous invocation of this routine, and we always emit
448 : : * long-format reconstructed values.
449 : : */
3776 450 : 1292 : reconstructedValue = (text *) DatumGetPointer(in->reconstructedValue);
451 [ + + - + : 1292 : Assert(reconstructedValue == NULL ? in->level == 0 :
- - - - -
- - + -
+ ]
452 : : VARSIZE_ANY_EXHDR(reconstructedValue) == in->level);
453 : :
5253 454 : 1292 : maxReconstrLen = in->level + 1;
455 [ + + ]: 1292 : if (in->hasPrefix)
456 : : {
457 : 240 : prefixText = DatumGetTextPP(in->prefixDatum);
458 [ - + - - : 240 : prefixSize = VARSIZE_ANY_EXHDR(prefixText);
- - - - +
- ]
459 : 240 : maxReconstrLen += prefixSize;
460 : : }
461 : :
462 : 1292 : reconstrText = palloc(VARHDRSZ + maxReconstrLen);
463 : 1292 : SET_VARSIZE(reconstrText, VARHDRSZ + maxReconstrLen);
464 : :
465 [ + + ]: 1292 : if (in->level)
466 : 1172 : memcpy(VARDATA(reconstrText),
3776 467 : 1172 : VARDATA(reconstructedValue),
5253 468 : 1172 : in->level);
469 [ + + ]: 1292 : if (prefixSize)
470 : 240 : memcpy(((char *) VARDATA(reconstrText)) + in->level,
471 [ + - ]: 240 : VARDATA_ANY(prefixText),
472 : : prefixSize);
473 : : /* last byte of reconstrText will be filled in below */
474 : :
475 : : /*
476 : : * Scan the child nodes. For each one, complete the reconstructed value
477 : : * and see if it's consistent with the query. If so, emit an entry into
478 : : * the output arrays.
479 : : */
146 michael@paquier.xyz 480 :GNC 1292 : out->nodeNumbers = palloc_array(int, in->nNodes);
481 : 1292 : out->levelAdds = palloc_array(int, in->nNodes);
482 : 1292 : out->reconstructedValues = palloc_array(Datum, in->nNodes);
5253 tgl@sss.pgh.pa.us 483 :CBC 1292 : out->nNodes = 0;
484 : :
485 [ + + ]: 13380 : for (i = 0; i < in->nNodes; i++)
486 : : {
4348 487 : 12088 : int16 nodeChar = DatumGetInt16(in->nodeLabels[i]);
488 : : int thisLen;
5169 489 : 12088 : bool res = true;
490 : : int j;
491 : :
492 : : /* If nodeChar is a dummy value, don't include it in data */
4348 493 [ + + ]: 12088 : if (nodeChar <= 0)
5253 494 : 2680 : thisLen = maxReconstrLen - 1;
495 : : else
496 : : {
4348 497 : 9408 : ((unsigned char *) VARDATA(reconstrText))[maxReconstrLen - 1] = nodeChar;
5253 498 : 9408 : thisLen = maxReconstrLen;
499 : : }
500 : :
5169 501 [ + + ]: 21244 : for (j = 0; j < in->nkeys; j++)
502 : : {
503 : 12088 : StrategyNumber strategy = in->scankeys[j].sk_strategy;
504 : : text *inText;
505 : : int inSize;
506 : : int r;
507 : :
508 : : /*
509 : : * If it's a collation-aware operator, but the collation is C, we
510 : : * can treat it as non-collation-aware. With non-C collation we
511 : : * need to traverse whole tree :-( so there's no point in making
512 : : * any check here. (Note also that our reconstructed value may
513 : : * well end with a partial multibyte character, so that applying
514 : : * any encoding-sensitive test to it would be risky anyhow.)
515 : : */
2954 teodor@sigaev.ru 516 [ + + + + ]: 12088 : if (SPG_IS_COLLATION_AWARE_STRATEGY(strategy))
517 : : {
5169 tgl@sss.pgh.pa.us 518 [ + + ]: 7888 : if (collate_is_c)
2954 teodor@sigaev.ru 519 : 312 : strategy -= SPG_STRATEGY_ADDITION;
520 : : else
5169 tgl@sss.pgh.pa.us 521 : 7576 : continue;
522 : : }
523 : :
524 : 4512 : inText = DatumGetTextPP(in->scankeys[j].sk_argument);
525 [ - + - - : 4512 : inSize = VARSIZE_ANY_EXHDR(inText);
- - - - -
+ ]
526 : :
527 : 4512 : r = memcmp(VARDATA(reconstrText), VARDATA_ANY(inText),
528 [ - + ]: 4512 : Min(inSize, thisLen));
529 : :
530 [ + + + + : 4512 : switch (strategy)
- ]
531 : : {
532 : 880 : case BTLessStrategyNumber:
533 : : case BTLessEqualStrategyNumber:
534 [ + + ]: 880 : if (r > 0)
535 : 500 : res = false;
536 : 880 : break;
537 : 2408 : case BTEqualStrategyNumber:
538 [ + + + + ]: 2408 : if (r != 0 || inSize < thisLen)
539 : 1400 : res = false;
540 : 2408 : break;
541 : 680 : case BTGreaterEqualStrategyNumber:
542 : : case BTGreaterStrategyNumber:
543 [ + + ]: 680 : if (r < 0)
544 : 520 : res = false;
545 : 680 : break;
2954 teodor@sigaev.ru 546 : 544 : case RTPrefixStrategyNumber:
547 [ + + ]: 544 : if (r != 0)
548 : 512 : res = false;
549 : 544 : break;
5169 tgl@sss.pgh.pa.us 550 :UBC 0 : default:
551 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
552 : : in->scankeys[j].sk_strategy);
553 : : break;
554 : : }
555 : :
5169 tgl@sss.pgh.pa.us 556 [ + + ]:CBC 4512 : if (!res)
557 : 2932 : break; /* no need to consider remaining conditions */
558 : : }
559 : :
5253 560 [ + + ]: 12088 : if (res)
561 : : {
562 : 9156 : out->nodeNumbers[out->nNodes] = i;
563 : 9156 : out->levelAdds[out->nNodes] = thisLen - in->level;
564 : 9156 : SET_VARSIZE(reconstrText, VARHDRSZ + thisLen);
565 : 18312 : out->reconstructedValues[out->nNodes] =
566 : 9156 : datumCopy(PointerGetDatum(reconstrText), false, -1);
567 : 9156 : out->nNodes++;
568 : : }
569 : : }
570 : :
571 : 1292 : PG_RETURN_VOID();
572 : : }
573 : :
574 : : Datum
575 : 173220 : spg_text_leaf_consistent(PG_FUNCTION_ARGS)
576 : : {
577 : 173220 : spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
578 : 173220 : spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
579 : 173220 : int level = in->level;
580 : : text *leafValue,
581 : 173220 : *reconstrValue = NULL;
582 : : char *fullValue;
583 : : int fullLen;
584 : : bool res;
585 : : int j;
586 : :
587 : : /* all tests are exact */
588 : 173220 : out->recheck = false;
589 : :
590 : 173220 : leafValue = DatumGetTextPP(in->leafDatum);
591 : :
592 : : /* As above, in->reconstructedValue isn't toasted or short. */
593 [ + + ]: 173220 : if (DatumGetPointer(in->reconstructedValue))
3341 noah@leadboat.com 594 : 173204 : reconstrValue = (text *) DatumGetPointer(in->reconstructedValue);
595 : :
3776 tgl@sss.pgh.pa.us 596 [ + + - + : 173220 : Assert(reconstrValue == NULL ? level == 0 :
- - - - -
- - + -
+ ]
597 : : VARSIZE_ANY_EXHDR(reconstrValue) == level);
598 : :
599 : : /* Reconstruct the full string represented by this leaf tuple */
5253 600 [ - + - - : 173220 : fullLen = level + VARSIZE_ANY_EXHDR(leafValue);
- - - - +
- ]
601 [ + + + - : 173220 : if (VARSIZE_ANY_EXHDR(leafValue) == 0 && level > 0)
- - - - +
- + + - -
+ - ]
602 : : {
603 : 53760 : fullValue = VARDATA(reconstrValue);
5251 604 : 53760 : out->leafValue = PointerGetDatum(reconstrValue);
605 : : }
606 : : else
607 : : {
5077 bruce@momjian.us 608 : 119460 : text *fullText = palloc(VARHDRSZ + fullLen);
609 : :
5251 tgl@sss.pgh.pa.us 610 : 119460 : SET_VARSIZE(fullText, VARHDRSZ + fullLen);
611 : 119460 : fullValue = VARDATA(fullText);
5253 612 [ + + ]: 119460 : if (level)
613 : 119444 : memcpy(fullValue, VARDATA(reconstrValue), level);
614 [ + - - - : 119460 : if (VARSIZE_ANY_EXHDR(leafValue) > 0)
- - - - +
- + - ]
615 [ + - ]: 119460 : memcpy(fullValue + level, VARDATA_ANY(leafValue),
5253 tgl@sss.pgh.pa.us 616 [ - + - - :ECB (80574) : VARSIZE_ANY_EXHDR(leafValue));
- - - - +
- ]
5251 tgl@sss.pgh.pa.us 617 :CBC 119460 : out->leafValue = PointerGetDatum(fullText);
618 : : }
619 : :
620 : : /* Perform the required comparison(s) */
5169 621 : 173220 : res = true;
622 [ + + ]: 191584 : for (j = 0; j < in->nkeys; j++)
623 : : {
624 : 173220 : StrategyNumber strategy = in->scankeys[j].sk_strategy;
625 : 173220 : text *query = DatumGetTextPP(in->scankeys[j].sk_argument);
626 [ - + - - : 173220 : int queryLen = VARSIZE_ANY_EXHDR(query);
- - - - -
+ ]
627 : : int r;
628 : :
2954 teodor@sigaev.ru 629 [ + + ]: 173220 : if (strategy == RTPrefixStrategyNumber)
630 : : {
631 : : /*
632 : : * if level >= length of query then reconstrValue must begin with
633 : : * query (prefix) string, so we don't need to check it again.
634 : : */
635 [ + - + + ]: 512 : res = (level >= queryLen) ||
2601 peter@eisentraut.org 636 : 256 : DatumGetBool(DirectFunctionCall2Coll(text_starts_with,
637 : : PG_GET_COLLATION(),
638 : : out->leafValue,
639 : : PointerGetDatum(query)));
640 : :
2941 tgl@sss.pgh.pa.us 641 [ + + ]: 256 : if (!res) /* no need to consider remaining conditions */
2954 teodor@sigaev.ru 642 : 224 : break;
643 : :
644 : 32 : continue;
645 : : }
646 : :
647 [ + + + - ]: 172964 : if (SPG_IS_COLLATION_AWARE_STRATEGY(strategy))
648 : : {
649 : : /* Collation-aware comparison */
650 : 151372 : strategy -= SPG_STRATEGY_ADDITION;
651 : :
652 : : /* If asserts enabled, verify encoding of reconstructed string */
5169 tgl@sss.pgh.pa.us 653 [ - + ]: 151372 : Assert(pg_verifymbstr(fullValue, fullLen, false));
654 : :
2941 655 : 151372 : r = varstr_cmp(fullValue, fullLen,
656 [ - + ]: 151372 : VARDATA_ANY(query), queryLen,
657 : : PG_GET_COLLATION());
658 : : }
659 : : else
660 : : {
661 : : /* Non-collation-aware comparison */
5169 662 [ - + ]: 21592 : r = memcmp(fullValue, VARDATA_ANY(query), Min(queryLen, fullLen));
663 : :
2941 664 [ + + ]: 21592 : if (r == 0)
665 : : {
666 [ + + ]: 16108 : if (queryLen > fullLen)
667 : 8016 : r = -1;
668 [ - + ]: 8092 : else if (queryLen < fullLen)
2941 tgl@sss.pgh.pa.us 669 :UBC 0 : r = 1;
670 : : }
671 : : }
672 : :
5169 tgl@sss.pgh.pa.us 673 [ + + + + :CBC 172964 : switch (strategy)
+ - ]
674 : : {
675 : 40236 : case BTLessStrategyNumber:
676 : 40236 : res = (r < 0);
677 : 40236 : break;
678 : 40236 : case BTLessEqualStrategyNumber:
679 : 40236 : res = (r <= 0);
680 : 40236 : break;
681 : 16200 : case BTEqualStrategyNumber:
682 : 16200 : res = (r == 0);
683 : 16200 : break;
684 : 38146 : case BTGreaterEqualStrategyNumber:
685 : 38146 : res = (r >= 0);
686 : 38146 : break;
687 : 38146 : case BTGreaterStrategyNumber:
688 : 38146 : res = (r > 0);
689 : 38146 : break;
5169 tgl@sss.pgh.pa.us 690 :UBC 0 : default:
691 [ # # ]: 0 : elog(ERROR, "unrecognized strategy number: %d",
692 : : in->scankeys[j].sk_strategy);
693 : : res = false;
694 : : break;
695 : : }
696 : :
5169 tgl@sss.pgh.pa.us 697 [ + + ]:CBC 172964 : if (!res)
698 : 154632 : break; /* no need to consider remaining conditions */
699 : : }
700 : :
5253 701 : 173220 : PG_RETURN_BOOL(res);
702 : : }
|
