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 "ltree.h"
13 #include "utils/builtins.h"
14 #include "utils/lsyscache.h"
15 #include "utils/selfuncs.h"
16 
18 
19 /* compare functions */
40 
41 int
42 ltree_compare(const ltree *a, const ltree *b)
43 {
44  ltree_level *al = LTREE_FIRST(a);
45  ltree_level *bl = LTREE_FIRST(b);
46  int an = a->numlevel;
47  int bn = b->numlevel;
48 
49  while (an > 0 && bn > 0)
50  {
51  int res;
52 
53  if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
54  {
55  if (al->len != bl->len)
56  return (al->len - bl->len) * 10 * (an + 1);
57  }
58  else
59  {
60  if (res < 0)
61  res = -1;
62  else
63  res = 1;
64  return res * 10 * (an + 1);
65  }
66 
67  an--;
68  bn--;
69  al = LEVEL_NEXT(al);
70  bl = LEVEL_NEXT(bl);
71  }
72 
73  return (a->numlevel - b->numlevel) * 10 * (an + 1);
74 }
75 
76 #define RUNCMP \
77 ltree *a = PG_GETARG_LTREE_P(0); \
78 ltree *b = PG_GETARG_LTREE_P(1); \
79 int res = ltree_compare(a,b); \
80 PG_FREE_IF_COPY(a,0); \
81 PG_FREE_IF_COPY(b,1)
82 
83 Datum
85 {
86  RUNCMP;
87  PG_RETURN_INT32(res);
88 }
89 
90 Datum
92 {
93  RUNCMP;
94  PG_RETURN_BOOL((res < 0) ? true : false);
95 }
96 
97 Datum
99 {
100  RUNCMP;
101  PG_RETURN_BOOL((res <= 0) ? true : false);
102 }
103 
104 Datum
106 {
107  RUNCMP;
108  PG_RETURN_BOOL((res == 0) ? true : false);
109 }
110 
111 Datum
113 {
114  RUNCMP;
115  PG_RETURN_BOOL((res >= 0) ? true : false);
116 }
117 
118 Datum
120 {
121  RUNCMP;
122  PG_RETURN_BOOL((res > 0) ? true : false);
123 }
124 
125 Datum
127 {
128  RUNCMP;
129  PG_RETURN_BOOL((res != 0) ? true : false);
130 }
131 
132 Datum
134 {
135  ltree *a = PG_GETARG_LTREE_P(0);
136  int res = a->numlevel;
137 
138  PG_FREE_IF_COPY(a, 0);
139  PG_RETURN_INT32(res);
140 }
141 
142 bool
143 inner_isparent(const ltree *c, const ltree *p)
144 {
145  ltree_level *cl = LTREE_FIRST(c);
146  ltree_level *pl = LTREE_FIRST(p);
147  int pn = p->numlevel;
148 
149  if (pn > c->numlevel)
150  return false;
151 
152  while (pn > 0)
153  {
154  if (cl->len != pl->len)
155  return false;
156  if (memcmp(cl->name, pl->name, cl->len) != 0)
157  return false;
158 
159  pn--;
160  cl = LEVEL_NEXT(cl);
161  pl = LEVEL_NEXT(pl);
162  }
163  return true;
164 }
165 
166 Datum
168 {
169  ltree *c = PG_GETARG_LTREE_P(1);
170  ltree *p = PG_GETARG_LTREE_P(0);
171  bool res = inner_isparent(c, p);
172 
173  PG_FREE_IF_COPY(c, 1);
174  PG_FREE_IF_COPY(p, 0);
175  PG_RETURN_BOOL(res);
176 }
177 
178 Datum
180 {
181  ltree *c = PG_GETARG_LTREE_P(0);
182  ltree *p = PG_GETARG_LTREE_P(1);
183  bool res = inner_isparent(c, p);
184 
185  PG_FREE_IF_COPY(c, 0);
186  PG_FREE_IF_COPY(p, 1);
187  PG_RETURN_BOOL(res);
188 }
189 
190 
191 static ltree *
193 {
194  char *start = NULL,
195  *end = NULL;
196  ltree_level *ptr = LTREE_FIRST(t);
197  ltree *res;
198  int i;
199 
200  if (startpos < 0 || endpos < 0 || startpos >= t->numlevel || startpos > endpos)
201  ereport(ERROR,
202  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
203  errmsg("invalid positions")));
204 
205  if (endpos > t->numlevel)
206  endpos = t->numlevel;
207 
208  start = end = (char *) ptr;
209  for (i = 0; i < endpos; i++)
210  {
211  if (i == startpos)
212  start = (char *) ptr;
213  if (i == endpos - 1)
214  {
215  end = (char *) LEVEL_NEXT(ptr);
216  break;
217  }
218  ptr = LEVEL_NEXT(ptr);
219  }
220 
221  res = (ltree *) palloc0(LTREE_HDRSIZE + (end - start));
222  SET_VARSIZE(res, LTREE_HDRSIZE + (end - start));
223  res->numlevel = endpos - startpos;
224 
225  memcpy(LTREE_FIRST(res), start, end - start);
226 
227  return res;
228 }
229 
230 Datum
232 {
233  ltree *t = PG_GETARG_LTREE_P(0);
235 
236  PG_FREE_IF_COPY(t, 0);
237  PG_RETURN_POINTER(res);
238 }
239 
240 Datum
242 {
243  ltree *t = PG_GETARG_LTREE_P(0);
244  int32 start = PG_GETARG_INT32(1);
245  int32 len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
246  int32 end;
247  ltree *res;
248 
249  end = start + len;
250 
251  if (start < 0)
252  {
253  start = t->numlevel + start;
254  end = start + len;
255  }
256  if (start < 0)
257  { /* start > t->numlevel */
258  start = t->numlevel + start;
259  end = start + len;
260  }
261 
262  if (len < 0)
263  end = t->numlevel + len;
264  else if (len == 0)
265  end = (fcinfo->nargs == 3) ? start : 0xffff;
266 
267  res = inner_subltree(t, start, end);
268 
269  PG_FREE_IF_COPY(t, 0);
270  PG_RETURN_POINTER(res);
271 }
272 
273 static ltree *
275 {
276  ltree *r;
277  int numlevel = (int) a->numlevel + b->numlevel;
278 
279  if (numlevel > LTREE_MAX_LEVELS)
280  ereport(ERROR,
281  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
282  errmsg("number of ltree levels (%d) exceeds the maximum allowed (%d)",
283  numlevel, LTREE_MAX_LEVELS)));
284 
285  r = (ltree *) palloc0(VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
287  r->numlevel = (uint16) numlevel;
288 
289  memcpy(LTREE_FIRST(r), LTREE_FIRST(a), VARSIZE(a) - LTREE_HDRSIZE);
290  memcpy(((char *) LTREE_FIRST(r)) + VARSIZE(a) - LTREE_HDRSIZE,
291  LTREE_FIRST(b),
292  VARSIZE(b) - LTREE_HDRSIZE);
293  return r;
294 }
295 
296 Datum
298 {
299  ltree *a = PG_GETARG_LTREE_P(0);
300  ltree *b = PG_GETARG_LTREE_P(1);
301  ltree *r;
302 
303  r = ltree_concat(a, b);
304  PG_FREE_IF_COPY(a, 0);
305  PG_FREE_IF_COPY(b, 1);
307 }
308 
309 Datum
311 {
312  ltree *a = PG_GETARG_LTREE_P(0);
313  text *b = PG_GETARG_TEXT_PP(1);
314  char *s;
315  ltree *r,
316  *tmp;
317 
318  s = text_to_cstring(b);
319 
321  PointerGetDatum(s)));
322 
323  pfree(s);
324 
325  r = ltree_concat(a, tmp);
326 
327  pfree(tmp);
328 
329  PG_FREE_IF_COPY(a, 0);
330  PG_FREE_IF_COPY(b, 1);
332 }
333 
334 Datum
336 {
337  ltree *a = PG_GETARG_LTREE_P(0);
338  ltree *b = PG_GETARG_LTREE_P(1);
339  int start = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
340  int i,
341  j;
343  *aptr,
344  *bptr;
345  bool found = false;
346 
347  if (start < 0)
348  {
349  if (-start >= a->numlevel)
350  start = 0;
351  else
352  start = (int) (a->numlevel) + start;
353  }
354 
355  if (a->numlevel - start < b->numlevel || a->numlevel == 0 || b->numlevel == 0)
356  {
357  PG_FREE_IF_COPY(a, 0);
358  PG_FREE_IF_COPY(b, 1);
359  PG_RETURN_INT32(-1);
360  }
361 
362  startptr = LTREE_FIRST(a);
363  for (i = 0; i <= a->numlevel - b->numlevel; i++)
364  {
365  if (i >= start)
366  {
367  aptr = startptr;
368  bptr = LTREE_FIRST(b);
369  for (j = 0; j < b->numlevel; j++)
370  {
371  if (!(aptr->len == bptr->len && memcmp(aptr->name, bptr->name, aptr->len) == 0))
372  break;
373  aptr = LEVEL_NEXT(aptr);
374  bptr = LEVEL_NEXT(bptr);
375  }
376 
377  if (j == b->numlevel)
378  {
379  found = true;
380  break;
381  }
382  }
383  startptr = LEVEL_NEXT(startptr);
384  }
385 
386  if (!found)
387  i = -1;
388 
389  PG_FREE_IF_COPY(a, 0);
390  PG_FREE_IF_COPY(b, 1);
391  PG_RETURN_INT32(i);
392 }
393 
394 Datum
396 {
397  ltree *a = PG_GETARG_LTREE_P(1);
398  text *b = PG_GETARG_TEXT_PP(0);
399  char *s;
400  ltree *r,
401  *tmp;
402 
403  s = text_to_cstring(b);
404 
406  PointerGetDatum(s)));
407 
408  pfree(s);
409 
410  r = ltree_concat(tmp, a);
411 
412  pfree(tmp);
413 
414  PG_FREE_IF_COPY(a, 1);
415  PG_FREE_IF_COPY(b, 0);
417 }
418 
419 /*
420  * Common code for variants of lca(), find longest common ancestor of inputs
421  *
422  * Returns NULL if there is no common ancestor, ie, the longest common
423  * prefix is empty.
424  */
425 ltree *
426 lca_inner(ltree **a, int len)
427 {
428  int tmp,
429  num,
430  i,
431  reslen;
432  ltree **ptr;
433  ltree_level *l1,
434  *l2;
435  ltree *res;
436 
437  if (len <= 0)
438  return NULL; /* no inputs? */
439  if ((*a)->numlevel == 0)
440  return NULL; /* any empty input means NULL result */
441 
442  /* num is the length of the longest common ancestor so far */
443  num = (*a)->numlevel - 1;
444 
445  /* Compare each additional input to *a */
446  ptr = a + 1;
447  while (ptr - a < len)
448  {
449  if ((*ptr)->numlevel == 0)
450  return NULL;
451  else if ((*ptr)->numlevel == 1)
452  num = 0;
453  else
454  {
455  l1 = LTREE_FIRST(*a);
456  l2 = LTREE_FIRST(*ptr);
457  tmp = Min(num, (*ptr)->numlevel - 1);
458  num = 0;
459  for (i = 0; i < tmp; i++)
460  {
461  if (l1->len == l2->len &&
462  memcmp(l1->name, l2->name, l1->len) == 0)
463  num = i + 1;
464  else
465  break;
466  l1 = LEVEL_NEXT(l1);
467  l2 = LEVEL_NEXT(l2);
468  }
469  }
470  ptr++;
471  }
472 
473  /* Now compute size of result ... */
474  reslen = LTREE_HDRSIZE;
475  l1 = LTREE_FIRST(*a);
476  for (i = 0; i < num; i++)
477  {
478  reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
479  l1 = LEVEL_NEXT(l1);
480  }
481 
482  /* ... and construct it by copying from *a */
483  res = (ltree *) palloc0(reslen);
484  SET_VARSIZE(res, reslen);
485  res->numlevel = num;
486 
487  l1 = LTREE_FIRST(*a);
488  l2 = LTREE_FIRST(res);
489 
490  for (i = 0; i < num; i++)
491  {
492  memcpy(l2, l1, MAXALIGN(l1->len + LEVEL_HDRSIZE));
493  l1 = LEVEL_NEXT(l1);
494  l2 = LEVEL_NEXT(l2);
495  }
496 
497  return res;
498 }
499 
500 Datum
502 {
503  int i;
504  ltree **a,
505  *res;
506 
507  a = (ltree **) palloc(sizeof(ltree *) * fcinfo->nargs);
508  for (i = 0; i < fcinfo->nargs; i++)
509  a[i] = PG_GETARG_LTREE_P(i);
510  res = lca_inner(a, (int) fcinfo->nargs);
511  for (i = 0; i < fcinfo->nargs; i++)
512  PG_FREE_IF_COPY(a[i], i);
513  pfree(a);
514 
515  if (res)
516  PG_RETURN_POINTER(res);
517  else
518  PG_RETURN_NULL();
519 }
520 
521 Datum
523 {
524  text *in = PG_GETARG_TEXT_PP(0);
525  char *s;
526  ltree *out;
527 
528  s = text_to_cstring(in);
529 
531  PointerGetDatum(s)));
532  pfree(s);
533  PG_FREE_IF_COPY(in, 0);
534  PG_RETURN_POINTER(out);
535 }
536 
537 
538 Datum
540 {
541  ltree *in = PG_GETARG_LTREE_P(0);
542  char *ptr;
543  int i;
544  ltree_level *curlevel;
545  text *out;
546 
547  out = (text *) palloc(VARSIZE(in) + VARHDRSZ);
548  ptr = VARDATA(out);
549  curlevel = LTREE_FIRST(in);
550  for (i = 0; i < in->numlevel; i++)
551  {
552  if (i != 0)
553  {
554  *ptr = '.';
555  ptr++;
556  }
557  memcpy(ptr, curlevel->name, curlevel->len);
558  ptr += curlevel->len;
559  curlevel = LEVEL_NEXT(curlevel);
560  }
561 
562  SET_VARSIZE(out, ptr - ((char *) out));
563  PG_FREE_IF_COPY(in, 0);
564 
565  PG_RETURN_POINTER(out);
566 }
567 
568 
569 /*
570  * ltreeparentsel - Selectivity of parent relationship for ltree data types.
571  *
572  * This function is not used anymore, if the ltree extension has been
573  * updated to 1.2 or later.
574  */
575 Datum
577 {
579  Oid operator = PG_GETARG_OID(1);
580  List *args = (List *) PG_GETARG_POINTER(2);
581  int varRelid = PG_GETARG_INT32(3);
582  double selec;
583 
584  /* Use generic restriction selectivity logic, with default 0.001. */
585  selec = generic_restriction_selectivity(root, operator, InvalidOid,
586  args, varRelid,
587  0.001);
588 
589  PG_RETURN_FLOAT8((float8) selec);
590 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:360
char name[FLEXIBLE_ARRAY_MEMBER]
Definition: ltree.h:23
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define VARDATA(PTR)
Definition: postgres.h:302
Datum ltree_cmp(PG_FUNCTION_ARGS)
Definition: ltree_op.c:84
uint16 len
Definition: ltree.h:22
#define VARSIZE(PTR)
Definition: postgres.h:303
#define PointerGetDatum(X)
Definition: postgres.h:556
#define VARHDRSZ
Definition: c.h:568
Datum nlevel(PG_FUNCTION_ARGS)
Definition: ltree_op.c:133
Datum ltree_le(PG_FUNCTION_ARGS)
Definition: ltree_op.c:98
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:365
#define Min(x, y)
Definition: c.h:927
Datum ltree_index(PG_FUNCTION_ARGS)
Definition: ltree_op.c:335
#define PG_RETURN_INT32(x)
Definition: fmgr.h:353
ltree * lca_inner(ltree **a, int len)
Definition: ltree_op.c:426
#define LTREE_HDRSIZE
Definition: ltree.h:37
int errcode(int sqlerrcode)
Definition: elog.c:610
#define PG_GETARG_LTREE_P(n)
Definition: ltree.h:204
bool inner_isparent(const ltree *c, const ltree *p)
Definition: ltree_op.c:143
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define DirectFunctionCall1(func, arg1)
Definition: fmgr.h:624
PG_FUNCTION_INFO_V1(ltree_cmp)
unsigned int Oid
Definition: postgres_ext.h:31
Datum ltree_in(PG_FUNCTION_ARGS)
Definition: ltree_io.c:172
double generic_restriction_selectivity(PlannerInfo *root, Oid oproid, Oid collation, List *args, int varRelid, double default_selectivity)
Definition: selfuncs.c:911
signed int int32
Definition: c.h:362
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:308
Datum ltree2text(PG_FUNCTION_ARGS)
Definition: ltree_op.c:539
Datum ltree_risparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:179
unsigned short uint16
Definition: c.h:373
void pfree(void *pointer)
Definition: mcxt.c:1057
PG_MODULE_MAGIC
Definition: ltree_op.c:17
#define ERROR
Definition: elog.h:43
double float8
Definition: c.h:498
static ltree * ltree_concat(ltree *a, ltree *b)
Definition: ltree_op.c:274
static XLogRecPtr endpos
Definition: pg_receivewal.c:46
char * c
#define RUNCMP
Definition: ltree_op.c:76
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
#define LEVEL_NEXT(x)
Definition: ltree.h:27
Definition: ltree.h:29
Datum text2ltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:522
uint16 numlevel
Definition: ltree.h:32
void * palloc0(Size size)
Definition: mcxt.c:981
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:358
uintptr_t Datum
Definition: postgres.h:367
Datum ltree_ne(PG_FUNCTION_ARGS)
Definition: ltree_op.c:126
int ltree_compare(const ltree *a, const ltree *b)
Definition: ltree_op.c:42
Datum ltree_eq(PG_FUNCTION_ARGS)
Definition: ltree_op.c:105
#define InvalidOid
Definition: postgres_ext.h:36
#define ereport(elevel,...)
Definition: elog.h:144
Datum lca(PG_FUNCTION_ARGS)
Definition: ltree_op.c:501
Datum ltree_addtext(PG_FUNCTION_ARGS)
Definition: ltree_op.c:310
#define MAXALIGN(LEN)
Definition: c.h:698
static XLogRecPtr startpos
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
Datum ltree_isparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:167
#define DatumGetPointer(X)
Definition: postgres.h:549
char * text_to_cstring(const text *t)
Definition: varlena.c:221
Datum ltree_ge(PG_FUNCTION_ARGS)
Definition: ltree_op.c:112
void * palloc(Size size)
Definition: mcxt.c:950
int errmsg(const char *fmt,...)
Definition: elog.c:824
static ltree * inner_subltree(ltree *t, int32 startpos, int32 endpos)
Definition: ltree_op.c:192
#define LTREE_FIRST(x)
Definition: ltree.h:38
int i
Datum ltree_gt(PG_FUNCTION_ARGS)
Definition: ltree_op.c:119
Definition: c.h:562
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:329
Datum ltree_textadd(PG_FUNCTION_ARGS)
Definition: ltree_op.c:395
#define LTREE_MAX_LEVELS
Definition: ltree.h:39
Datum ltreeparentsel(PG_FUNCTION_ARGS)
Definition: ltree_op.c:576
Datum subltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:231
Definition: pg_list.h:50
#define PG_RETURN_NULL()
Definition: fmgr.h:344
Datum ltree_addltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:297
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
Datum ltree_lt(PG_FUNCTION_ARGS)
Definition: ltree_op.c:91
static XLogRecPtr startptr
Definition: basebackup.c:116
#define LEVEL_HDRSIZE
Definition: ltree.h:26