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