PostgreSQL Source Code  git master
ltree_op.c
Go to the documentation of this file.
1 /*
2  * op function for ltree
3  * Teodor Sigaev <teodor@stack.net>
4  * contrib/ltree/ltree_op.c
5  */
6 #include "postgres.h"
7 
8 #include <ctype.h>
9 
10 #include "access/htup_details.h"
11 #include "catalog/pg_statistic.h"
12 #include "common/hashfn.h"
13 #include "ltree.h"
14 #include "utils/builtins.h"
15 #include "utils/lsyscache.h"
16 #include "utils/selfuncs.h"
17 
19 
20 /* compare functions */
43 
44 int
45 ltree_compare(const ltree *a, const ltree *b)
46 {
47  ltree_level *al = LTREE_FIRST(a);
48  ltree_level *bl = LTREE_FIRST(b);
49  int an = a->numlevel;
50  int bn = b->numlevel;
51 
52  while (an > 0 && bn > 0)
53  {
54  int res;
55 
56  if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
57  {
58  if (al->len != bl->len)
59  return (al->len - bl->len) * 10 * (an + 1);
60  }
61  else
62  {
63  if (res < 0)
64  res = -1;
65  else
66  res = 1;
67  return res * 10 * (an + 1);
68  }
69 
70  an--;
71  bn--;
72  al = LEVEL_NEXT(al);
73  bl = LEVEL_NEXT(bl);
74  }
75 
76  return (a->numlevel - b->numlevel) * 10 * (an + 1);
77 }
78 
79 #define RUNCMP \
80 ltree *a = PG_GETARG_LTREE_P(0); \
81 ltree *b = PG_GETARG_LTREE_P(1); \
82 int res = ltree_compare(a,b); \
83 PG_FREE_IF_COPY(a,0); \
84 PG_FREE_IF_COPY(b,1)
85 
86 Datum
88 {
89  RUNCMP;
91 }
92 
93 Datum
95 {
96  RUNCMP;
97  PG_RETURN_BOOL(res < 0);
98 }
99 
100 Datum
102 {
103  RUNCMP;
104  PG_RETURN_BOOL(res <= 0);
105 }
106 
107 Datum
109 {
110  RUNCMP;
111  PG_RETURN_BOOL(res == 0);
112 }
113 
114 Datum
116 {
117  RUNCMP;
118  PG_RETURN_BOOL(res >= 0);
119 }
120 
121 Datum
123 {
124  RUNCMP;
125  PG_RETURN_BOOL(res > 0);
126 }
127 
128 Datum
130 {
131  RUNCMP;
132  PG_RETURN_BOOL(res != 0);
133 }
134 
135 /* Compute a hash for the ltree */
136 Datum
138 {
139  ltree *a = PG_GETARG_LTREE_P(0);
140  uint32 result = 1;
141  int an = a->numlevel;
142  ltree_level *al = LTREE_FIRST(a);
143 
144  while (an > 0)
145  {
146  uint32 levelHash = DatumGetUInt32(hash_any((unsigned char *) al->name, al->len));
147 
148  /*
149  * Combine hash values of successive elements by multiplying the
150  * current value by 31 and adding on the new element's hash value.
151  *
152  * This method is borrowed from hash_array(), which see for further
153  * commentary.
154  */
155  result = (result << 5) - result + levelHash;
156 
157  an--;
158  al = LEVEL_NEXT(al);
159  }
160 
161  PG_FREE_IF_COPY(a, 0);
162  PG_RETURN_UINT32(result);
163 }
164 
165 /* Compute an extended hash for the ltree */
166 Datum
168 {
169  ltree *a = PG_GETARG_LTREE_P(0);
170  const uint64 seed = PG_GETARG_INT64(1);
171  uint64 result = 1;
172  int an = a->numlevel;
173  ltree_level *al = LTREE_FIRST(a);
174 
175  /*
176  * If the path has length zero, return 1 + seed to ensure that the low 32
177  * bits of the result match hash_ltree when the seed is 0, as required by
178  * the hash index support functions, but to also return a different value
179  * when there is a seed.
180  */
181  if (an == 0)
182  {
183  PG_FREE_IF_COPY(a, 0);
184  PG_RETURN_UINT64(result + seed);
185  }
186 
187  while (an > 0)
188  {
189  uint64 levelHash = DatumGetUInt64(hash_any_extended((unsigned char *) al->name, al->len, seed));
190 
191  result = (result << 5) - result + levelHash;
192 
193  an--;
194  al = LEVEL_NEXT(al);
195  }
196 
197  PG_FREE_IF_COPY(a, 0);
198  PG_RETURN_UINT64(result);
199 }
200 
201 Datum
203 {
204  ltree *a = PG_GETARG_LTREE_P(0);
205  int res = a->numlevel;
206 
207  PG_FREE_IF_COPY(a, 0);
209 }
210 
211 bool
212 inner_isparent(const ltree *c, const ltree *p)
213 {
214  ltree_level *cl = LTREE_FIRST(c);
215  ltree_level *pl = LTREE_FIRST(p);
216  int pn = p->numlevel;
217 
218  if (pn > c->numlevel)
219  return false;
220 
221  while (pn > 0)
222  {
223  if (cl->len != pl->len)
224  return false;
225  if (memcmp(cl->name, pl->name, cl->len) != 0)
226  return false;
227 
228  pn--;
229  cl = LEVEL_NEXT(cl);
230  pl = LEVEL_NEXT(pl);
231  }
232  return true;
233 }
234 
235 Datum
237 {
238  ltree *c = PG_GETARG_LTREE_P(1);
239  ltree *p = PG_GETARG_LTREE_P(0);
240  bool res = inner_isparent(c, p);
241 
242  PG_FREE_IF_COPY(c, 1);
243  PG_FREE_IF_COPY(p, 0);
245 }
246 
247 Datum
249 {
250  ltree *c = PG_GETARG_LTREE_P(0);
251  ltree *p = PG_GETARG_LTREE_P(1);
252  bool res = inner_isparent(c, p);
253 
254  PG_FREE_IF_COPY(c, 0);
255  PG_FREE_IF_COPY(p, 1);
257 }
258 
259 
260 static ltree *
262 {
263  char *start = NULL,
264  *end = NULL;
265  ltree_level *ptr = LTREE_FIRST(t);
266  ltree *res;
267  int i;
268 
269  if (startpos < 0 || endpos < 0 || startpos >= t->numlevel || startpos > endpos)
270  ereport(ERROR,
271  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
272  errmsg("invalid positions")));
273 
274  if (endpos > t->numlevel)
275  endpos = t->numlevel;
276 
277  start = end = (char *) ptr;
278  for (i = 0; i < endpos; i++)
279  {
280  if (i == startpos)
281  start = (char *) ptr;
282  if (i == endpos - 1)
283  {
284  end = (char *) LEVEL_NEXT(ptr);
285  break;
286  }
287  ptr = LEVEL_NEXT(ptr);
288  }
289 
290  res = (ltree *) palloc0(LTREE_HDRSIZE + (end - start));
291  SET_VARSIZE(res, LTREE_HDRSIZE + (end - start));
292  res->numlevel = endpos - startpos;
293 
294  memcpy(LTREE_FIRST(res), start, end - start);
295 
296  return res;
297 }
298 
299 Datum
301 {
302  ltree *t = PG_GETARG_LTREE_P(0);
304 
305  PG_FREE_IF_COPY(t, 0);
307 }
308 
309 Datum
311 {
312  ltree *t = PG_GETARG_LTREE_P(0);
314  int32 len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
315  int32 end;
316  ltree *res;
317 
318  end = start + len;
319 
320  if (start < 0)
321  {
322  start = t->numlevel + start;
323  end = start + len;
324  }
325  if (start < 0)
326  { /* start > t->numlevel */
327  start = t->numlevel + start;
328  end = start + len;
329  }
330 
331  if (len < 0)
332  end = t->numlevel + len;
333  else if (len == 0)
334  end = (fcinfo->nargs == 3) ? start : 0xffff;
335 
336  res = inner_subltree(t, start, end);
337 
338  PG_FREE_IF_COPY(t, 0);
340 }
341 
342 static ltree *
344 {
345  ltree *r;
346  int numlevel = (int) a->numlevel + b->numlevel;
347 
348  if (numlevel > LTREE_MAX_LEVELS)
349  ereport(ERROR,
350  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
351  errmsg("number of ltree levels (%d) exceeds the maximum allowed (%d)",
352  numlevel, LTREE_MAX_LEVELS)));
353 
354  r = (ltree *) palloc0(VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
356  r->numlevel = (uint16) numlevel;
357 
358  memcpy(LTREE_FIRST(r), LTREE_FIRST(a), VARSIZE(a) - LTREE_HDRSIZE);
359  memcpy(((char *) LTREE_FIRST(r)) + VARSIZE(a) - LTREE_HDRSIZE,
360  LTREE_FIRST(b),
361  VARSIZE(b) - LTREE_HDRSIZE);
362  return r;
363 }
364 
365 Datum
367 {
368  ltree *a = PG_GETARG_LTREE_P(0);
369  ltree *b = PG_GETARG_LTREE_P(1);
370  ltree *r;
371 
372  r = ltree_concat(a, b);
373  PG_FREE_IF_COPY(a, 0);
374  PG_FREE_IF_COPY(b, 1);
376 }
377 
378 Datum
380 {
381  ltree *a = PG_GETARG_LTREE_P(0);
382  text *b = PG_GETARG_TEXT_PP(1);
383  char *s;
384  ltree *r,
385  *tmp;
386 
387  s = text_to_cstring(b);
388 
390  PointerGetDatum(s)));
391 
392  pfree(s);
393 
394  r = ltree_concat(a, tmp);
395 
396  pfree(tmp);
397 
398  PG_FREE_IF_COPY(a, 0);
399  PG_FREE_IF_COPY(b, 1);
401 }
402 
403 Datum
405 {
406  ltree *a = PG_GETARG_LTREE_P(0);
407  ltree *b = PG_GETARG_LTREE_P(1);
408  int start = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
409  int i,
410  j;
411  ltree_level *startptr,
412  *aptr,
413  *bptr;
414  bool found = false;
415 
416  if (start < 0)
417  {
418  if (-start >= a->numlevel)
419  start = 0;
420  else
421  start = (int) (a->numlevel) + start;
422  }
423 
424  if (a->numlevel - start < b->numlevel || a->numlevel == 0 || b->numlevel == 0)
425  {
426  PG_FREE_IF_COPY(a, 0);
427  PG_FREE_IF_COPY(b, 1);
428  PG_RETURN_INT32(-1);
429  }
430 
431  startptr = LTREE_FIRST(a);
432  for (i = 0; i <= a->numlevel - b->numlevel; i++)
433  {
434  if (i >= start)
435  {
436  aptr = startptr;
437  bptr = LTREE_FIRST(b);
438  for (j = 0; j < b->numlevel; j++)
439  {
440  if (!(aptr->len == bptr->len && memcmp(aptr->name, bptr->name, aptr->len) == 0))
441  break;
442  aptr = LEVEL_NEXT(aptr);
443  bptr = LEVEL_NEXT(bptr);
444  }
445 
446  if (j == b->numlevel)
447  {
448  found = true;
449  break;
450  }
451  }
452  startptr = LEVEL_NEXT(startptr);
453  }
454 
455  if (!found)
456  i = -1;
457 
458  PG_FREE_IF_COPY(a, 0);
459  PG_FREE_IF_COPY(b, 1);
461 }
462 
463 Datum
465 {
466  ltree *a = PG_GETARG_LTREE_P(1);
467  text *b = PG_GETARG_TEXT_PP(0);
468  char *s;
469  ltree *r,
470  *tmp;
471 
472  s = text_to_cstring(b);
473 
475  PointerGetDatum(s)));
476 
477  pfree(s);
478 
479  r = ltree_concat(tmp, a);
480 
481  pfree(tmp);
482 
483  PG_FREE_IF_COPY(a, 1);
484  PG_FREE_IF_COPY(b, 0);
486 }
487 
488 /*
489  * Common code for variants of lca(), find longest common ancestor of inputs
490  *
491  * Returns NULL if there is no common ancestor, ie, the longest common
492  * prefix is empty.
493  */
494 ltree *
496 {
497  int tmp,
498  num,
499  i,
500  reslen;
501  ltree **ptr;
502  ltree_level *l1,
503  *l2;
504  ltree *res;
505 
506  if (len <= 0)
507  return NULL; /* no inputs? */
508  if ((*a)->numlevel == 0)
509  return NULL; /* any empty input means NULL result */
510 
511  /* num is the length of the longest common ancestor so far */
512  num = (*a)->numlevel - 1;
513 
514  /* Compare each additional input to *a */
515  ptr = a + 1;
516  while (ptr - a < len)
517  {
518  if ((*ptr)->numlevel == 0)
519  return NULL;
520  else if ((*ptr)->numlevel == 1)
521  num = 0;
522  else
523  {
524  l1 = LTREE_FIRST(*a);
525  l2 = LTREE_FIRST(*ptr);
526  tmp = Min(num, (*ptr)->numlevel - 1);
527  num = 0;
528  for (i = 0; i < tmp; i++)
529  {
530  if (l1->len == l2->len &&
531  memcmp(l1->name, l2->name, l1->len) == 0)
532  num = i + 1;
533  else
534  break;
535  l1 = LEVEL_NEXT(l1);
536  l2 = LEVEL_NEXT(l2);
537  }
538  }
539  ptr++;
540  }
541 
542  /* Now compute size of result ... */
543  reslen = LTREE_HDRSIZE;
544  l1 = LTREE_FIRST(*a);
545  for (i = 0; i < num; i++)
546  {
547  reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
548  l1 = LEVEL_NEXT(l1);
549  }
550 
551  /* ... and construct it by copying from *a */
552  res = (ltree *) palloc0(reslen);
553  SET_VARSIZE(res, reslen);
554  res->numlevel = num;
555 
556  l1 = LTREE_FIRST(*a);
557  l2 = LTREE_FIRST(res);
558 
559  for (i = 0; i < num; i++)
560  {
561  memcpy(l2, l1, MAXALIGN(l1->len + LEVEL_HDRSIZE));
562  l1 = LEVEL_NEXT(l1);
563  l2 = LEVEL_NEXT(l2);
564  }
565 
566  return res;
567 }
568 
569 Datum
571 {
572  int i;
573  ltree **a,
574  *res;
575 
576  a = (ltree **) palloc(sizeof(ltree *) * fcinfo->nargs);
577  for (i = 0; i < fcinfo->nargs; i++)
578  a[i] = PG_GETARG_LTREE_P(i);
579  res = lca_inner(a, (int) fcinfo->nargs);
580  for (i = 0; i < fcinfo->nargs; i++)
581  PG_FREE_IF_COPY(a[i], i);
582  pfree(a);
583 
584  if (res)
586  else
587  PG_RETURN_NULL();
588 }
589 
590 Datum
592 {
593  text *in = PG_GETARG_TEXT_PP(0);
594  char *s;
595  ltree *out;
596 
597  s = text_to_cstring(in);
598 
600  PointerGetDatum(s)));
601  pfree(s);
602  PG_FREE_IF_COPY(in, 0);
603  PG_RETURN_POINTER(out);
604 }
605 
606 
607 Datum
609 {
610  ltree *in = PG_GETARG_LTREE_P(0);
611  char *ptr;
612  int i;
613  ltree_level *curlevel;
614  text *out;
615 
616  out = (text *) palloc(VARSIZE(in) + VARHDRSZ);
617  ptr = VARDATA(out);
618  curlevel = LTREE_FIRST(in);
619  for (i = 0; i < in->numlevel; i++)
620  {
621  if (i != 0)
622  {
623  *ptr = '.';
624  ptr++;
625  }
626  memcpy(ptr, curlevel->name, curlevel->len);
627  ptr += curlevel->len;
628  curlevel = LEVEL_NEXT(curlevel);
629  }
630 
631  SET_VARSIZE(out, ptr - ((char *) out));
632  PG_FREE_IF_COPY(in, 0);
633 
634  PG_RETURN_POINTER(out);
635 }
636 
637 
638 /*
639  * ltreeparentsel - Selectivity of parent relationship for ltree data types.
640  *
641  * This function is not used anymore, if the ltree extension has been
642  * updated to 1.2 or later.
643  */
644 Datum
646 {
648  Oid operator = PG_GETARG_OID(1);
649  List *args = (List *) PG_GETARG_POINTER(2);
650  int varRelid = PG_GETARG_INT32(3);
651  double selec;
652 
653  /* Use generic restriction selectivity logic, with default 0.001. */
655  args, varRelid,
656  0.001);
657 
658  PG_RETURN_FLOAT8((float8) selec);
659 }
unsigned short uint16
Definition: c.h:505
unsigned int uint32
Definition: c.h:506
#define Min(x, y)
Definition: c.h:1004
#define MAXALIGN(LEN)
Definition: c.h:811
signed int int32
Definition: c.h:494
#define VARHDRSZ
Definition: c.h:692
double float8
Definition: c.h:630
int errcode(int sqlerrcode)
Definition: elog.c:857
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
#define PG_RETURN_UINT32(x)
Definition: fmgr.h:355
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:309
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define DirectFunctionCall1(func, arg1)
Definition: fmgr.h:642
#define PG_RETURN_NULL()
Definition: fmgr.h:345
#define PG_GETARG_INT64(n)
Definition: fmgr.h:283
#define PG_RETURN_UINT64(x)
Definition: fmgr.h:369
#define PG_RETURN_INT32(x)
Definition: fmgr.h:354
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
static Datum hash_any_extended(const unsigned char *k, int keylen, uint64 seed)
Definition: hashfn.h:37
static Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.h:31
return str start
int b
Definition: isn.c:70
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
#define LEVEL_HDRSIZE
Definition: ltree.h:39
#define LTREE_MAX_LEVELS
Definition: ltree.h:52
#define LTREE_FIRST(x)
Definition: ltree.h:51
#define LEVEL_NEXT(x)
Definition: ltree.h:40
#define LTREE_HDRSIZE
Definition: ltree.h:50
#define PG_GETARG_LTREE_P(n)
Definition: ltree.h:218
PGDLLEXPORT Datum ltree_in(PG_FUNCTION_ARGS)
Definition: ltree_io.c:175
static ltree * inner_subltree(ltree *t, int32 startpos, int32 endpos)
Definition: ltree_op.c:261
Datum lca(PG_FUNCTION_ARGS)
Definition: ltree_op.c:570
bool inner_isparent(const ltree *c, const ltree *p)
Definition: ltree_op.c:212
Datum hash_ltree_extended(PG_FUNCTION_ARGS)
Definition: ltree_op.c:167
Datum ltree_index(PG_FUNCTION_ARGS)
Definition: ltree_op.c:404
Datum ltree_cmp(PG_FUNCTION_ARGS)
Definition: ltree_op.c:87
Datum subltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:300
PG_FUNCTION_INFO_V1(ltree_cmp)
Datum ltree_gt(PG_FUNCTION_ARGS)
Definition: ltree_op.c:122
PG_MODULE_MAGIC
Definition: ltree_op.c:18
Datum nlevel(PG_FUNCTION_ARGS)
Definition: ltree_op.c:202
Datum ltree_textadd(PG_FUNCTION_ARGS)
Definition: ltree_op.c:464
int ltree_compare(const ltree *a, const ltree *b)
Definition: ltree_op.c:45
Datum ltreeparentsel(PG_FUNCTION_ARGS)
Definition: ltree_op.c:645
Datum ltree_eq(PG_FUNCTION_ARGS)
Definition: ltree_op.c:108
static ltree * ltree_concat(ltree *a, ltree *b)
Definition: ltree_op.c:343
Datum ltree_ge(PG_FUNCTION_ARGS)
Definition: ltree_op.c:115
Datum ltree_isparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:236
Datum ltree_addtext(PG_FUNCTION_ARGS)
Definition: ltree_op.c:379
Datum ltree_ne(PG_FUNCTION_ARGS)
Definition: ltree_op.c:129
#define RUNCMP
Definition: ltree_op.c:79
Datum text2ltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:591
Datum ltree_risparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:248
Datum ltree2text(PG_FUNCTION_ARGS)
Definition: ltree_op.c:608
Datum hash_ltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:137
Datum ltree_le(PG_FUNCTION_ARGS)
Definition: ltree_op.c:101
Datum ltree_lt(PG_FUNCTION_ARGS)
Definition: ltree_op.c:94
Datum ltree_addltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:366
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:310
ltree * lca_inner(ltree **a, int len)
Definition: ltree_op.c:495
void pfree(void *pointer)
Definition: mcxt.c:1520
void * palloc0(Size size)
Definition: mcxt.c:1346
void * palloc(Size size)
Definition: mcxt.c:1316
const void size_t len
static XLogRecPtr endpos
Definition: pg_receivewal.c:56
static XLogRecPtr startpos
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:222
static uint64 DatumGetUInt64(Datum X)
Definition: postgres.h:419
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
static Pointer DatumGetPointer(Datum X)
Definition: postgres.h:312
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
char * c
tree ctl root
Definition: radixtree.h:1884
double generic_restriction_selectivity(PlannerInfo *root, Oid oproid, Oid collation, List *args, int varRelid, double default_selectivity)
Definition: selfuncs.c:914
Definition: pg_list.h:54
char name[FLEXIBLE_ARRAY_MEMBER]
Definition: ltree.h:36
uint16 len
Definition: ltree.h:35
Definition: ltree.h:43
uint16 numlevel
Definition: ltree.h:45
Definition: c.h:687
#define VARDATA(PTR)
Definition: varatt.h:278
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305
#define VARSIZE(PTR)
Definition: varatt.h:279
char * text_to_cstring(const text *t)
Definition: varlena.c:217