PostgreSQL Source Code  git master
spgtextproc.c
Go to the documentation of this file.
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-2023, 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 "mb/pg_wchar.h"
45 #include "utils/builtins.h"
46 #include "utils/datum.h"
47 #include "utils/pg_locale.h"
48 #include "utils/varlena.h"
49 #include "varatt.h"
50 
51 
52 /*
53  * In the worst case, an inner tuple in a text radix tree could have as many
54  * as 258 nodes (one for each possible byte value, plus the two special
55  * cases). Each node can take 16 bytes on MAXALIGN=8 machines. The inner
56  * tuple must fit on an index page of size BLCKSZ. Rather than assuming we
57  * know the exact amount of overhead imposed by page headers, tuple headers,
58  * etc, we leave 100 bytes for that (the actual overhead should be no more
59  * than 56 bytes at this writing, so there is slop in this number).
60  * So we can safely create prefixes up to BLCKSZ - 258 * 16 - 100 bytes long.
61  * Unfortunately, because 258 * 16 is over 4K, there is no safe prefix length
62  * when BLCKSZ is less than 8K; it is always possible to get "SPGiST inner
63  * tuple size exceeds maximum" if there are too many distinct next-byte values
64  * at a given place in the tree. Since use of nonstandard block sizes appears
65  * to be negligible in the field, we just live with that fact for now,
66  * choosing a max prefix size of 32 bytes when BLCKSZ is configured smaller
67  * than default.
68  */
69 #define SPGIST_MAX_PREFIX_LENGTH Max((int) (BLCKSZ - 258 * 16 - 100), 32)
70 
71 /*
72  * Strategy for collation aware operator on text is equal to btree strategy
73  * plus value of 10.
74  *
75  * Current collation aware strategies and their corresponding btree strategies:
76  * 11 BTLessStrategyNumber
77  * 12 BTLessEqualStrategyNumber
78  * 14 BTGreaterEqualStrategyNumber
79  * 15 BTGreaterStrategyNumber
80  */
81 #define SPG_STRATEGY_ADDITION (10)
82 #define SPG_IS_COLLATION_AWARE_STRATEGY(s) ((s) > SPG_STRATEGY_ADDITION \
83  && (s) != RTPrefixStrategyNumber)
84 
85 /* Struct for sorting values in picksplit */
86 typedef struct spgNodePtr
87 {
89  int i;
92 
93 
94 Datum
96 {
97  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
99 
100  cfg->prefixType = TEXTOID;
101  cfg->labelType = INT2OID;
102  cfg->canReturnData = true;
103  cfg->longValuesOK = true; /* suffixing will shorten long values */
104  PG_RETURN_VOID();
105 }
106 
107 /*
108  * Form a text datum from the given not-necessarily-null-terminated string,
109  * using short varlena header format if possible
110  */
111 static Datum
112 formTextDatum(const char *data, int datalen)
113 {
114  char *p;
115 
116  p = (char *) palloc(datalen + VARHDRSZ);
117 
118  if (datalen + VARHDRSZ_SHORT <= VARATT_SHORT_MAX)
119  {
120  SET_VARSIZE_SHORT(p, datalen + VARHDRSZ_SHORT);
121  if (datalen)
122  memcpy(p + VARHDRSZ_SHORT, data, datalen);
123  }
124  else
125  {
126  SET_VARSIZE(p, datalen + VARHDRSZ);
127  memcpy(p + VARHDRSZ, data, datalen);
128  }
129 
130  return PointerGetDatum(p);
131 }
132 
133 /*
134  * Find the length of the common prefix of a and b
135  */
136 static int
137 commonPrefix(const char *a, const char *b, int lena, int lenb)
138 {
139  int i = 0;
140 
141  while (i < lena && i < lenb && *a == *b)
142  {
143  a++;
144  b++;
145  i++;
146  }
147 
148  return i;
149 }
150 
151 /*
152  * Binary search an array of int16 datums for a match to c
153  *
154  * On success, *i gets the match location; on failure, it gets where to insert
155  */
156 static bool
157 searchChar(Datum *nodeLabels, int nNodes, int16 c, int *i)
158 {
159  int StopLow = 0,
160  StopHigh = nNodes;
161 
162  while (StopLow < StopHigh)
163  {
164  int StopMiddle = (StopLow + StopHigh) >> 1;
165  int16 middle = DatumGetInt16(nodeLabels[StopMiddle]);
166 
167  if (c < middle)
168  StopHigh = StopMiddle;
169  else if (c > middle)
170  StopLow = StopMiddle + 1;
171  else
172  {
173  *i = StopMiddle;
174  return true;
175  }
176  }
177 
178  *i = StopHigh;
179  return false;
180 }
181 
182 Datum
184 {
187  text *inText = DatumGetTextPP(in->datum);
188  char *inStr = VARDATA_ANY(inText);
189  int inSize = VARSIZE_ANY_EXHDR(inText);
190  char *prefixStr = NULL;
191  int prefixSize = 0;
192  int commonLen = 0;
193  int16 nodeChar = 0;
194  int i = 0;
195 
196  /* Check for prefix match, set nodeChar to first byte after prefix */
197  if (in->hasPrefix)
198  {
199  text *prefixText = DatumGetTextPP(in->prefixDatum);
200 
201  prefixStr = VARDATA_ANY(prefixText);
202  prefixSize = VARSIZE_ANY_EXHDR(prefixText);
203 
204  commonLen = commonPrefix(inStr + in->level,
205  prefixStr,
206  inSize - in->level,
207  prefixSize);
208 
209  if (commonLen == prefixSize)
210  {
211  if (inSize - in->level > commonLen)
212  nodeChar = *(unsigned char *) (inStr + in->level + commonLen);
213  else
214  nodeChar = -1;
215  }
216  else
217  {
218  /* Must split tuple because incoming value doesn't match prefix */
219  out->resultType = spgSplitTuple;
220 
221  if (commonLen == 0)
222  {
223  out->result.splitTuple.prefixHasPrefix = false;
224  }
225  else
226  {
227  out->result.splitTuple.prefixHasPrefix = true;
228  out->result.splitTuple.prefixPrefixDatum =
229  formTextDatum(prefixStr, commonLen);
230  }
231  out->result.splitTuple.prefixNNodes = 1;
232  out->result.splitTuple.prefixNodeLabels =
233  (Datum *) palloc(sizeof(Datum));
234  out->result.splitTuple.prefixNodeLabels[0] =
235  Int16GetDatum(*(unsigned char *) (prefixStr + commonLen));
236 
237  out->result.splitTuple.childNodeN = 0;
238 
239  if (prefixSize - commonLen == 1)
240  {
241  out->result.splitTuple.postfixHasPrefix = false;
242  }
243  else
244  {
245  out->result.splitTuple.postfixHasPrefix = true;
246  out->result.splitTuple.postfixPrefixDatum =
247  formTextDatum(prefixStr + commonLen + 1,
248  prefixSize - commonLen - 1);
249  }
250 
251  PG_RETURN_VOID();
252  }
253  }
254  else if (inSize > in->level)
255  {
256  nodeChar = *(unsigned char *) (inStr + in->level);
257  }
258  else
259  {
260  nodeChar = -1;
261  }
262 
263  /* Look up nodeChar in the node label array */
264  if (searchChar(in->nodeLabels, in->nNodes, nodeChar, &i))
265  {
266  /*
267  * Descend to existing node. (If in->allTheSame, the core code will
268  * ignore our nodeN specification here, but that's OK. We still have
269  * to provide the correct levelAdd and restDatum values, and those are
270  * the same regardless of which node gets chosen by core.)
271  */
272  int levelAdd;
273 
274  out->resultType = spgMatchNode;
275  out->result.matchNode.nodeN = i;
276  levelAdd = commonLen;
277  if (nodeChar >= 0)
278  levelAdd++;
279  out->result.matchNode.levelAdd = levelAdd;
280  if (inSize - in->level - levelAdd > 0)
281  out->result.matchNode.restDatum =
282  formTextDatum(inStr + in->level + levelAdd,
283  inSize - in->level - levelAdd);
284  else
285  out->result.matchNode.restDatum =
286  formTextDatum(NULL, 0);
287  }
288  else if (in->allTheSame)
289  {
290  /*
291  * Can't use AddNode action, so split the tuple. The upper tuple has
292  * the same prefix as before and uses a dummy node label -2 for the
293  * lower tuple. The lower tuple has no prefix and the same node
294  * labels as the original tuple.
295  *
296  * Note: it might seem tempting to shorten the upper tuple's prefix,
297  * if it has one, then use its last byte as label for the lower tuple.
298  * But that doesn't win since we know the incoming value matches the
299  * whole prefix: we'd just end up splitting the lower tuple again.
300  */
301  out->resultType = spgSplitTuple;
302  out->result.splitTuple.prefixHasPrefix = in->hasPrefix;
303  out->result.splitTuple.prefixPrefixDatum = in->prefixDatum;
304  out->result.splitTuple.prefixNNodes = 1;
305  out->result.splitTuple.prefixNodeLabels = (Datum *) palloc(sizeof(Datum));
306  out->result.splitTuple.prefixNodeLabels[0] = Int16GetDatum(-2);
307  out->result.splitTuple.childNodeN = 0;
308  out->result.splitTuple.postfixHasPrefix = false;
309  }
310  else
311  {
312  /* Add a node for the not-previously-seen nodeChar value */
313  out->resultType = spgAddNode;
314  out->result.addNode.nodeLabel = Int16GetDatum(nodeChar);
315  out->result.addNode.nodeN = i;
316  }
317 
318  PG_RETURN_VOID();
319 }
320 
321 /* qsort comparator to sort spgNodePtr structs by "c" */
322 static int
323 cmpNodePtr(const void *a, const void *b)
324 {
325  const spgNodePtr *aa = (const spgNodePtr *) a;
326  const spgNodePtr *bb = (const spgNodePtr *) b;
327 
328  return aa->c - bb->c;
329 }
330 
331 Datum
333 {
336  text *text0 = DatumGetTextPP(in->datums[0]);
337  int i,
338  commonLen;
339  spgNodePtr *nodes;
340 
341  /* Identify longest common prefix, if any */
342  commonLen = VARSIZE_ANY_EXHDR(text0);
343  for (i = 1; i < in->nTuples && commonLen > 0; i++)
344  {
345  text *texti = DatumGetTextPP(in->datums[i]);
346  int tmp = commonPrefix(VARDATA_ANY(text0),
347  VARDATA_ANY(texti),
348  VARSIZE_ANY_EXHDR(text0),
349  VARSIZE_ANY_EXHDR(texti));
350 
351  if (tmp < commonLen)
352  commonLen = tmp;
353  }
354 
355  /*
356  * Limit the prefix length, if necessary, to ensure that the resulting
357  * inner tuple will fit on a page.
358  */
359  commonLen = Min(commonLen, SPGIST_MAX_PREFIX_LENGTH);
360 
361  /* Set node prefix to be that string, if it's not empty */
362  if (commonLen == 0)
363  {
364  out->hasPrefix = false;
365  }
366  else
367  {
368  out->hasPrefix = true;
369  out->prefixDatum = formTextDatum(VARDATA_ANY(text0), commonLen);
370  }
371 
372  /* Extract the node label (first non-common byte) from each value */
373  nodes = (spgNodePtr *) palloc(sizeof(spgNodePtr) * in->nTuples);
374 
375  for (i = 0; i < in->nTuples; i++)
376  {
377  text *texti = DatumGetTextPP(in->datums[i]);
378 
379  if (commonLen < VARSIZE_ANY_EXHDR(texti))
380  nodes[i].c = *(unsigned char *) (VARDATA_ANY(texti) + commonLen);
381  else
382  nodes[i].c = -1; /* use -1 if string is all common */
383  nodes[i].i = i;
384  nodes[i].d = in->datums[i];
385  }
386 
387  /*
388  * Sort by label values so that we can group the values into nodes. This
389  * also ensures that the nodes are ordered by label value, allowing the
390  * use of binary search in searchChar.
391  */
392  qsort(nodes, in->nTuples, sizeof(*nodes), cmpNodePtr);
393 
394  /* And emit results */
395  out->nNodes = 0;
396  out->nodeLabels = (Datum *) palloc(sizeof(Datum) * in->nTuples);
397  out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
398  out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
399 
400  for (i = 0; i < in->nTuples; i++)
401  {
402  text *texti = DatumGetTextPP(nodes[i].d);
403  Datum leafD;
404 
405  if (i == 0 || nodes[i].c != nodes[i - 1].c)
406  {
407  out->nodeLabels[out->nNodes] = Int16GetDatum(nodes[i].c);
408  out->nNodes++;
409  }
410 
411  if (commonLen < VARSIZE_ANY_EXHDR(texti))
412  leafD = formTextDatum(VARDATA_ANY(texti) + commonLen + 1,
413  VARSIZE_ANY_EXHDR(texti) - commonLen - 1);
414  else
415  leafD = formTextDatum(NULL, 0);
416 
417  out->leafTupleDatums[nodes[i].i] = leafD;
418  out->mapTuplesToNodes[nodes[i].i] = out->nNodes - 1;
419  }
420 
421  PG_RETURN_VOID();
422 }
423 
424 Datum
426 {
429  bool collate_is_c = lc_collate_is_c(PG_GET_COLLATION());
430  text *reconstructedValue;
431  text *reconstrText;
432  int maxReconstrLen;
433  text *prefixText = NULL;
434  int prefixSize = 0;
435  int i;
436 
437  /*
438  * Reconstruct values represented at this tuple, including parent data,
439  * prefix of this tuple if any, and the node label if it's non-dummy.
440  * in->level should be the length of the previously reconstructed value,
441  * and the number of bytes added here is prefixSize or prefixSize + 1.
442  *
443  * Note: we assume that in->reconstructedValue isn't toasted and doesn't
444  * have a short varlena header. This is okay because it must have been
445  * created by a previous invocation of this routine, and we always emit
446  * long-format reconstructed values.
447  */
448  reconstructedValue = (text *) DatumGetPointer(in->reconstructedValue);
449  Assert(reconstructedValue == NULL ? in->level == 0 :
450  VARSIZE_ANY_EXHDR(reconstructedValue) == in->level);
451 
452  maxReconstrLen = in->level + 1;
453  if (in->hasPrefix)
454  {
455  prefixText = DatumGetTextPP(in->prefixDatum);
456  prefixSize = VARSIZE_ANY_EXHDR(prefixText);
457  maxReconstrLen += prefixSize;
458  }
459 
460  reconstrText = palloc(VARHDRSZ + maxReconstrLen);
461  SET_VARSIZE(reconstrText, VARHDRSZ + maxReconstrLen);
462 
463  if (in->level)
464  memcpy(VARDATA(reconstrText),
465  VARDATA(reconstructedValue),
466  in->level);
467  if (prefixSize)
468  memcpy(((char *) VARDATA(reconstrText)) + in->level,
469  VARDATA_ANY(prefixText),
470  prefixSize);
471  /* last byte of reconstrText will be filled in below */
472 
473  /*
474  * Scan the child nodes. For each one, complete the reconstructed value
475  * and see if it's consistent with the query. If so, emit an entry into
476  * the output arrays.
477  */
478  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
479  out->levelAdds = (int *) palloc(sizeof(int) * in->nNodes);
480  out->reconstructedValues = (Datum *) palloc(sizeof(Datum) * in->nNodes);
481  out->nNodes = 0;
482 
483  for (i = 0; i < in->nNodes; i++)
484  {
485  int16 nodeChar = DatumGetInt16(in->nodeLabels[i]);
486  int thisLen;
487  bool res = true;
488  int j;
489 
490  /* If nodeChar is a dummy value, don't include it in data */
491  if (nodeChar <= 0)
492  thisLen = maxReconstrLen - 1;
493  else
494  {
495  ((unsigned char *) VARDATA(reconstrText))[maxReconstrLen - 1] = nodeChar;
496  thisLen = maxReconstrLen;
497  }
498 
499  for (j = 0; j < in->nkeys; j++)
500  {
501  StrategyNumber strategy = in->scankeys[j].sk_strategy;
502  text *inText;
503  int inSize;
504  int r;
505 
506  /*
507  * If it's a collation-aware operator, but the collation is C, we
508  * can treat it as non-collation-aware. With non-C collation we
509  * need to traverse whole tree :-( so there's no point in making
510  * any check here. (Note also that our reconstructed value may
511  * well end with a partial multibyte character, so that applying
512  * any encoding-sensitive test to it would be risky anyhow.)
513  */
514  if (SPG_IS_COLLATION_AWARE_STRATEGY(strategy))
515  {
516  if (collate_is_c)
517  strategy -= SPG_STRATEGY_ADDITION;
518  else
519  continue;
520  }
521 
522  inText = DatumGetTextPP(in->scankeys[j].sk_argument);
523  inSize = VARSIZE_ANY_EXHDR(inText);
524 
525  r = memcmp(VARDATA(reconstrText), VARDATA_ANY(inText),
526  Min(inSize, thisLen));
527 
528  switch (strategy)
529  {
532  if (r > 0)
533  res = false;
534  break;
536  if (r != 0 || inSize < thisLen)
537  res = false;
538  break;
541  if (r < 0)
542  res = false;
543  break;
545  if (r != 0)
546  res = false;
547  break;
548  default:
549  elog(ERROR, "unrecognized strategy number: %d",
550  in->scankeys[j].sk_strategy);
551  break;
552  }
553 
554  if (!res)
555  break; /* no need to consider remaining conditions */
556  }
557 
558  if (res)
559  {
560  out->nodeNumbers[out->nNodes] = i;
561  out->levelAdds[out->nNodes] = thisLen - in->level;
562  SET_VARSIZE(reconstrText, VARHDRSZ + thisLen);
563  out->reconstructedValues[out->nNodes] =
564  datumCopy(PointerGetDatum(reconstrText), false, -1);
565  out->nNodes++;
566  }
567  }
568 
569  PG_RETURN_VOID();
570 }
571 
572 Datum
574 {
577  int level = in->level;
578  text *leafValue,
579  *reconstrValue = NULL;
580  char *fullValue;
581  int fullLen;
582  bool res;
583  int j;
584 
585  /* all tests are exact */
586  out->recheck = false;
587 
588  leafValue = DatumGetTextPP(in->leafDatum);
589 
590  /* As above, in->reconstructedValue isn't toasted or short. */
592  reconstrValue = (text *) DatumGetPointer(in->reconstructedValue);
593 
594  Assert(reconstrValue == NULL ? level == 0 :
595  VARSIZE_ANY_EXHDR(reconstrValue) == level);
596 
597  /* Reconstruct the full string represented by this leaf tuple */
598  fullLen = level + VARSIZE_ANY_EXHDR(leafValue);
599  if (VARSIZE_ANY_EXHDR(leafValue) == 0 && level > 0)
600  {
601  fullValue = VARDATA(reconstrValue);
602  out->leafValue = PointerGetDatum(reconstrValue);
603  }
604  else
605  {
606  text *fullText = palloc(VARHDRSZ + fullLen);
607 
608  SET_VARSIZE(fullText, VARHDRSZ + fullLen);
609  fullValue = VARDATA(fullText);
610  if (level)
611  memcpy(fullValue, VARDATA(reconstrValue), level);
612  if (VARSIZE_ANY_EXHDR(leafValue) > 0)
613  memcpy(fullValue + level, VARDATA_ANY(leafValue),
614  VARSIZE_ANY_EXHDR(leafValue));
615  out->leafValue = PointerGetDatum(fullText);
616  }
617 
618  /* Perform the required comparison(s) */
619  res = true;
620  for (j = 0; j < in->nkeys; j++)
621  {
622  StrategyNumber strategy = in->scankeys[j].sk_strategy;
623  text *query = DatumGetTextPP(in->scankeys[j].sk_argument);
624  int queryLen = VARSIZE_ANY_EXHDR(query);
625  int r;
626 
627  if (strategy == RTPrefixStrategyNumber)
628  {
629  /*
630  * if level >= length of query then reconstrValue must begin with
631  * query (prefix) string, so we don't need to check it again.
632  */
633  res = (level >= queryLen) ||
636  out->leafValue,
637  PointerGetDatum(query)));
638 
639  if (!res) /* no need to consider remaining conditions */
640  break;
641 
642  continue;
643  }
644 
645  if (SPG_IS_COLLATION_AWARE_STRATEGY(strategy))
646  {
647  /* Collation-aware comparison */
648  strategy -= SPG_STRATEGY_ADDITION;
649 
650  /* If asserts enabled, verify encoding of reconstructed string */
651  Assert(pg_verifymbstr(fullValue, fullLen, false));
652 
653  r = varstr_cmp(fullValue, fullLen,
654  VARDATA_ANY(query), queryLen,
655  PG_GET_COLLATION());
656  }
657  else
658  {
659  /* Non-collation-aware comparison */
660  r = memcmp(fullValue, VARDATA_ANY(query), Min(queryLen, fullLen));
661 
662  if (r == 0)
663  {
664  if (queryLen > fullLen)
665  r = -1;
666  else if (queryLen < fullLen)
667  r = 1;
668  }
669  }
670 
671  switch (strategy)
672  {
674  res = (r < 0);
675  break;
677  res = (r <= 0);
678  break;
680  res = (r == 0);
681  break;
683  res = (r >= 0);
684  break;
686  res = (r > 0);
687  break;
688  default:
689  elog(ERROR, "unrecognized strategy number: %d",
690  in->scankeys[j].sk_strategy);
691  res = false;
692  break;
693  }
694 
695  if (!res)
696  break; /* no need to consider remaining conditions */
697  }
698 
700 }
#define Min(x, y)
Definition: c.h:993
signed short int16
Definition: c.h:482
#define VARHDRSZ
Definition: c.h:681
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:132
#define ERROR
Definition: elog.h:39
Datum DirectFunctionCall2Coll(PGFunction func, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:795
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define DatumGetTextPP(X)
Definition: fmgr.h:292
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_GET_COLLATION()
Definition: fmgr.h:198
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
bool pg_verifymbstr(const char *mbstr, int len, bool noError)
Definition: mbutils.c:1563
void * palloc(Size size)
Definition: mcxt.c:1226
const void * data
bool lc_collate_is_c(Oid collation)
Definition: pg_locale.c:1307
#define qsort(a, b, c, d)
Definition: port.h:445
static bool DatumGetBool(Datum X)
Definition: postgres.h:90
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
static Datum Int16GetDatum(int16 X)
Definition: postgres.h:172
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
static int16 DatumGetInt16(Datum X)
Definition: postgres.h:162
char * c
@ spgMatchNode
Definition: spgist.h:69
@ spgAddNode
Definition: spgist.h:70
@ spgSplitTuple
Definition: spgist.h:71
Datum spg_text_config(PG_FUNCTION_ARGS)
Definition: spgtextproc.c:95
static int commonPrefix(const char *a, const char *b, int lena, int lenb)
Definition: spgtextproc.c:137
#define SPG_IS_COLLATION_AWARE_STRATEGY(s)
Definition: spgtextproc.c:82
static int cmpNodePtr(const void *a, const void *b)
Definition: spgtextproc.c:323
#define SPGIST_MAX_PREFIX_LENGTH
Definition: spgtextproc.c:69
struct spgNodePtr spgNodePtr
#define SPG_STRATEGY_ADDITION
Definition: spgtextproc.c:81
Datum spg_text_leaf_consistent(PG_FUNCTION_ARGS)
Definition: spgtextproc.c:573
Datum spg_text_inner_consistent(PG_FUNCTION_ARGS)
Definition: spgtextproc.c:425
static Datum formTextDatum(const char *data, int datalen)
Definition: spgtextproc.c:112
Datum spg_text_choose(PG_FUNCTION_ARGS)
Definition: spgtextproc.c:183
static bool searchChar(Datum *nodeLabels, int nNodes, int16 c, int *i)
Definition: spgtextproc.c:157
Datum spg_text_picksplit(PG_FUNCTION_ARGS)
Definition: spgtextproc.c:332
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTPrefixStrategyNumber
Definition: stratnum.h:78
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define BTLessStrategyNumber
Definition: stratnum.h:29
#define BTEqualStrategyNumber
Definition: stratnum.h:31
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
Datum sk_argument
Definition: skey.h:72
StrategyNumber sk_strategy
Definition: skey.h:68
Datum * nodeLabels
Definition: spgist.h:64
bool hasPrefix
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:62
int nNodes
Definition: spgist.h:63
Datum datum
Definition: spgist.h:55
int level
Definition: spgist.h:57
bool allTheSame
Definition: spgist.h:60
struct spgChooseOut::@47::@49 addNode
spgChooseResultType resultType
Definition: spgist.h:76
union spgChooseOut::@47 result
struct spgChooseOut::@47::@50 splitTuple
struct spgChooseOut::@47::@48 matchNode
bool longValuesOK
Definition: spgist.h:47
bool canReturnData
Definition: spgist.h:46
Oid labelType
Definition: spgist.h:44
Oid prefixType
Definition: spgist.h:43
Datum reconstructedValue
Definition: spgist.h:140
ScanKey scankeys
Definition: spgist.h:134
Datum * nodeLabels
Definition: spgist.h:151
Datum * reconstructedValues
Definition: spgist.h:159
ScanKey scankeys
Definition: spgist.h:169
Datum reconstructedValue
Definition: spgist.h:175
Datum * datums
Definition: spgist.h:113
bool hasPrefix
Definition: spgist.h:119
int * mapTuplesToNodes
Definition: spgist.h:125
Datum * nodeLabels
Definition: spgist.h:123
Datum * leafTupleDatums
Definition: spgist.h:126
Datum prefixDatum
Definition: spgist.h:120
Definition: c.h:676
#define VARHDRSZ_SHORT
Definition: varatt.h:255
#define SET_VARSIZE_SHORT(PTR, len)
Definition: varatt.h:306
#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 VARATT_SHORT_MAX
Definition: varatt.h:257
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317
int varstr_cmp(const char *arg1, int len1, const char *arg2, int len2, Oid collid)
Definition: varlena.c:1538
Datum text_starts_with(PG_FUNCTION_ARGS)
Definition: varlena.c:1790