Age Owner TLA Line data Source code
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 :
6158 tgl 17 CBC 3 : PG_MODULE_MAGIC;
18 :
19 : /* compare functions */
7558 bruce 20 3 : PG_FUNCTION_INFO_V1(ltree_cmp);
21 3 : PG_FUNCTION_INFO_V1(ltree_lt);
22 3 : PG_FUNCTION_INFO_V1(ltree_le);
23 3 : PG_FUNCTION_INFO_V1(ltree_eq);
24 2 : PG_FUNCTION_INFO_V1(ltree_ne);
25 3 : PG_FUNCTION_INFO_V1(ltree_ge);
26 3 : PG_FUNCTION_INFO_V1(ltree_gt);
27 3 : PG_FUNCTION_INFO_V1(nlevel);
28 3 : PG_FUNCTION_INFO_V1(ltree_isparent);
29 3 : PG_FUNCTION_INFO_V1(ltree_risparent);
30 3 : PG_FUNCTION_INFO_V1(subltree);
31 6 : PG_FUNCTION_INFO_V1(subpath);
7314 32 6 : PG_FUNCTION_INFO_V1(ltree_index);
7558 33 3 : PG_FUNCTION_INFO_V1(ltree_addltree);
34 3 : PG_FUNCTION_INFO_V1(ltree_addtext);
35 2 : PG_FUNCTION_INFO_V1(ltree_textadd);
7553 36 16 : PG_FUNCTION_INFO_V1(lca);
7314 37 3 : PG_FUNCTION_INFO_V1(ltree2text);
38 3 : PG_FUNCTION_INFO_V1(text2ltree);
6191 tgl 39 2 : PG_FUNCTION_INFO_V1(ltreeparentsel);
40 :
41 : int
5050 bruce 42 135974 : ltree_compare(const ltree *a, const ltree *b)
43 : {
7558 44 135974 : ltree_level *al = LTREE_FIRST(a);
45 135974 : ltree_level *bl = LTREE_FIRST(b);
7522 46 135974 : int an = a->numlevel;
47 135974 : int bn = b->numlevel;
48 :
49 225525 : while (an > 0 && bn > 0)
50 : {
51 : int res;
52 :
4492 rhaas 53 214887 : if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
54 : {
7522 bruce 55 98104 : if (al->len != bl->len)
56 8553 : return (al->len - bl->len) * 10 * (an + 1);
57 : }
58 : else
59 : {
1647 tgl 60 116783 : if (res < 0)
61 58656 : res = -1;
62 : else
63 58127 : res = 1;
7522 bruce 64 116783 : return res * 10 * (an + 1);
65 : }
66 :
67 89551 : an--;
68 89551 : bn--;
69 89551 : al = LEVEL_NEXT(al);
70 89551 : bl = LEVEL_NEXT(bl);
71 : }
72 :
73 10638 : 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
84 71218 : ltree_cmp(PG_FUNCTION_ARGS)
85 : {
2029 tgl 86 71218 : RUNCMP;
87 71218 : PG_RETURN_INT32(res);
88 : }
89 :
90 : Datum
7522 bruce 91 1132 : ltree_lt(PG_FUNCTION_ARGS)
92 : {
2029 tgl 93 1132 : RUNCMP;
545 michael 94 1132 : PG_RETURN_BOOL(res < 0);
95 : }
96 :
97 : Datum
7522 bruce 98 1133 : ltree_le(PG_FUNCTION_ARGS)
99 : {
2029 tgl 100 1133 : RUNCMP;
545 michael 101 1133 : PG_RETURN_BOOL(res <= 0);
102 : }
103 :
104 : Datum
7522 bruce 105 1009 : ltree_eq(PG_FUNCTION_ARGS)
106 : {
2029 tgl 107 1009 : RUNCMP;
545 michael 108 1009 : PG_RETURN_BOOL(res == 0);
109 : }
110 :
111 : Datum
7522 bruce 112 1899 : ltree_ge(PG_FUNCTION_ARGS)
113 : {
2029 tgl 114 1899 : RUNCMP;
545 michael 115 1899 : PG_RETURN_BOOL(res >= 0);
116 : }
117 :
118 : Datum
7522 bruce 119 1898 : ltree_gt(PG_FUNCTION_ARGS)
120 : {
2029 tgl 121 1898 : RUNCMP;
545 michael 122 1898 : PG_RETURN_BOOL(res > 0);
123 : }
124 :
125 : Datum
7522 bruce 126 UBC 0 : ltree_ne(PG_FUNCTION_ARGS)
127 : {
2029 tgl 128 0 : RUNCMP;
545 michael 129 0 : PG_RETURN_BOOL(res != 0);
130 : }
131 :
132 : Datum
7522 bruce 133 CBC 2 : nlevel(PG_FUNCTION_ARGS)
134 : {
2029 tgl 135 2 : ltree *a = PG_GETARG_LTREE_P(0);
7522 bruce 136 2 : int res = a->numlevel;
137 :
138 2 : PG_FREE_IF_COPY(a, 0);
7558 139 2 : PG_RETURN_INT32(res);
140 : }
141 :
142 : bool
5050 143 21188 : inner_isparent(const ltree *c, const ltree *p)
144 : {
7558 145 21188 : ltree_level *cl = LTREE_FIRST(c);
146 21188 : ltree_level *pl = LTREE_FIRST(p);
7522 147 21188 : int pn = p->numlevel;
148 :
149 21188 : if (pn > c->numlevel)
7558 150 10166 : return false;
151 :
7522 152 12019 : while (pn > 0)
153 : {
154 11883 : if (cl->len != pl->len)
7558 155 7960 : return false;
1647 tgl 156 3923 : if (memcmp(cl->name, pl->name, cl->len) != 0)
7558 bruce 157 2926 : return false;
158 :
159 997 : pn--;
7522 160 997 : cl = LEVEL_NEXT(cl);
161 997 : pl = LEVEL_NEXT(pl);
162 : }
7558 163 136 : return true;
164 : }
165 :
166 : Datum
7522 167 11538 : ltree_isparent(PG_FUNCTION_ARGS)
168 : {
2029 tgl 169 11538 : ltree *c = PG_GETARG_LTREE_P(1);
170 11538 : ltree *p = PG_GETARG_LTREE_P(0);
7522 bruce 171 11538 : bool res = inner_isparent(c, p);
172 :
173 11538 : PG_FREE_IF_COPY(c, 1);
174 11538 : PG_FREE_IF_COPY(p, 0);
175 11538 : PG_RETURN_BOOL(res);
176 : }
177 :
178 : Datum
179 9320 : ltree_risparent(PG_FUNCTION_ARGS)
180 : {
2029 tgl 181 9320 : ltree *c = PG_GETARG_LTREE_P(0);
182 9320 : ltree *p = PG_GETARG_LTREE_P(1);
7522 bruce 183 9320 : bool res = inner_isparent(c, p);
184 :
185 9320 : PG_FREE_IF_COPY(c, 0);
186 9320 : PG_FREE_IF_COPY(p, 1);
187 9320 : PG_RETURN_BOOL(res);
188 : }
189 :
190 :
191 : static ltree *
3940 peter_e 192 9 : inner_subltree(ltree *t, int32 startpos, int32 endpos)
193 : {
7522 bruce 194 9 : char *start = NULL,
195 9 : *end = NULL;
7558 196 9 : ltree_level *ptr = LTREE_FIRST(t);
197 : ltree *res;
198 : int i;
199 :
7205 teodor 200 9 : if (startpos < 0 || endpos < 0 || startpos >= t->numlevel || startpos > endpos)
7199 tgl 201 UBC 0 : ereport(ERROR,
202 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
203 : errmsg("invalid positions")));
204 :
7522 bruce 205 CBC 9 : if (endpos > t->numlevel)
7558 206 2 : endpos = t->numlevel;
207 :
7205 teodor 208 9 : start = end = (char *) ptr;
7522 bruce 209 19 : for (i = 0; i < endpos; i++)
210 : {
211 18 : if (i == startpos)
212 7 : start = (char *) ptr;
213 18 : if (i == endpos - 1)
214 : {
215 8 : end = (char *) LEVEL_NEXT(ptr);
7558 216 8 : break;
217 : }
7522 218 10 : ptr = LEVEL_NEXT(ptr);
219 : }
220 :
2588 andres 221 9 : res = (ltree *) palloc0(LTREE_HDRSIZE + (end - start));
5884 tgl 222 9 : SET_VARSIZE(res, LTREE_HDRSIZE + (end - start));
7522 bruce 223 9 : res->numlevel = endpos - startpos;
224 :
225 9 : memcpy(LTREE_FIRST(res), start, end - start);
226 :
7558 227 9 : return res;
228 : }
229 :
230 : Datum
7522 231 1 : subltree(PG_FUNCTION_ARGS)
232 : {
2029 tgl 233 1 : ltree *t = PG_GETARG_LTREE_P(0);
7522 bruce 234 1 : ltree *res = inner_subltree(t, PG_GETARG_INT32(1), PG_GETARG_INT32(2));
235 :
236 1 : PG_FREE_IF_COPY(t, 0);
7558 237 1 : PG_RETURN_POINTER(res);
238 : }
239 :
240 : Datum
7522 241 8 : subpath(PG_FUNCTION_ARGS)
242 : {
2029 tgl 243 8 : ltree *t = PG_GETARG_LTREE_P(0);
3940 peter_e 244 8 : int32 start = PG_GETARG_INT32(1);
245 8 : int32 len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
246 : int32 end;
247 : ltree *res;
248 :
7522 bruce 249 8 : end = start + len;
250 :
251 8 : if (start < 0)
252 : {
7558 253 1 : start = t->numlevel + start;
7522 254 1 : end = start + len;
255 : }
256 8 : if (start < 0)
257 : { /* start > t->numlevel */
7558 bruce 258 UBC 0 : start = t->numlevel + start;
7522 259 0 : end = start + len;
260 : }
261 :
7522 bruce 262 CBC 8 : if (len < 0)
7558 263 2 : end = t->numlevel + len;
7522 264 6 : else if (len == 0)
7205 teodor 265 4 : end = (fcinfo->nargs == 3) ? start : 0xffff;
266 :
7522 bruce 267 8 : res = inner_subltree(t, start, end);
268 :
269 8 : PG_FREE_IF_COPY(t, 0);
7558 270 8 : PG_RETURN_POINTER(res);
271 : }
272 :
273 : static ltree *
5050 274 6 : ltree_concat(ltree *a, ltree *b)
275 : {
276 : ltree *r;
1107 tgl 277 6 : int numlevel = (int) a->numlevel + b->numlevel;
278 :
279 6 : if (numlevel > LTREE_MAX_LEVELS)
280 1 : 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 :
2588 andres 285 5 : r = (ltree *) palloc0(VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
5884 tgl 286 5 : SET_VARSIZE(r, VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
1107 287 5 : r->numlevel = (uint16) numlevel;
288 :
5884 289 5 : memcpy(LTREE_FIRST(r), LTREE_FIRST(a), VARSIZE(a) - LTREE_HDRSIZE);
290 5 : memcpy(((char *) LTREE_FIRST(r)) + VARSIZE(a) - LTREE_HDRSIZE,
291 : LTREE_FIRST(b),
292 5 : VARSIZE(b) - LTREE_HDRSIZE);
7522 bruce 293 5 : return r;
294 : }
295 :
296 : Datum
297 5 : ltree_addltree(PG_FUNCTION_ARGS)
298 : {
2029 tgl 299 5 : ltree *a = PG_GETARG_LTREE_P(0);
300 5 : ltree *b = PG_GETARG_LTREE_P(1);
301 : ltree *r;
302 :
7558 bruce 303 5 : r = ltree_concat(a, b);
7522 304 4 : PG_FREE_IF_COPY(a, 0);
305 4 : PG_FREE_IF_COPY(b, 1);
7558 306 4 : PG_RETURN_POINTER(r);
307 : }
308 :
309 : Datum
7522 310 1 : ltree_addtext(PG_FUNCTION_ARGS)
311 : {
2029 tgl 312 1 : ltree *a = PG_GETARG_LTREE_P(0);
5493 313 1 : text *b = PG_GETARG_TEXT_PP(1);
314 : char *s;
315 : ltree *r,
316 : *tmp;
317 :
318 1 : s = text_to_cstring(b);
319 :
320 1 : tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
321 : PointerGetDatum(s)));
322 :
7558 bruce 323 1 : pfree(s);
324 :
7522 325 1 : r = ltree_concat(a, tmp);
326 :
327 1 : pfree(tmp);
328 :
329 1 : PG_FREE_IF_COPY(a, 0);
330 1 : PG_FREE_IF_COPY(b, 1);
7558 331 1 : PG_RETURN_POINTER(r);
332 : }
333 :
334 : Datum
7314 335 18 : ltree_index(PG_FUNCTION_ARGS)
336 : {
2029 tgl 337 18 : ltree *a = PG_GETARG_LTREE_P(0);
338 18 : ltree *b = PG_GETARG_LTREE_P(1);
7188 bruce 339 18 : int start = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
340 : int i,
341 : j;
342 : ltree_level *startptr,
343 : *aptr,
344 : *bptr;
345 18 : bool found = false;
346 :
347 18 : if (start < 0)
348 : {
349 5 : if (-start >= a->numlevel)
350 1 : start = 0;
351 : else
352 4 : start = (int) (a->numlevel) + start;
353 : }
354 :
355 18 : if (a->numlevel - start < b->numlevel || a->numlevel == 0 || b->numlevel == 0)
356 : {
7314 357 1 : PG_FREE_IF_COPY(a, 0);
358 1 : PG_FREE_IF_COPY(b, 1);
359 1 : PG_RETURN_INT32(-1);
360 : }
361 :
7188 362 17 : startptr = LTREE_FIRST(a);
363 109 : for (i = 0; i <= a->numlevel - b->numlevel; i++)
364 : {
365 106 : if (i >= start)
366 : {
367 58 : aptr = startptr;
368 58 : bptr = LTREE_FIRST(b);
369 93 : for (j = 0; j < b->numlevel; j++)
370 : {
4492 rhaas 371 79 : if (!(aptr->len == bptr->len && memcmp(aptr->name, bptr->name, aptr->len) == 0))
372 : break;
7188 bruce 373 35 : aptr = LEVEL_NEXT(aptr);
374 35 : bptr = LEVEL_NEXT(bptr);
375 : }
376 :
377 58 : if (j == b->numlevel)
378 : {
379 14 : found = true;
7314 380 14 : break;
381 : }
382 : }
7188 383 92 : startptr = LEVEL_NEXT(startptr);
384 : }
385 :
386 17 : if (!found)
387 3 : i = -1;
388 :
7314 389 17 : PG_FREE_IF_COPY(a, 0);
390 17 : PG_FREE_IF_COPY(b, 1);
391 17 : PG_RETURN_INT32(i);
392 : }
393 :
394 : Datum
7522 bruce 395 UBC 0 : ltree_textadd(PG_FUNCTION_ARGS)
396 : {
2029 tgl 397 0 : ltree *a = PG_GETARG_LTREE_P(1);
5493 398 0 : text *b = PG_GETARG_TEXT_PP(0);
399 : char *s;
400 : ltree *r,
401 : *tmp;
402 :
403 0 : s = text_to_cstring(b);
404 :
405 0 : tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
406 : PointerGetDatum(s)));
407 :
7522 bruce 408 0 : pfree(s);
409 :
410 0 : r = ltree_concat(tmp, a);
411 :
412 0 : pfree(tmp);
413 :
414 0 : PG_FREE_IF_COPY(a, 1);
415 0 : PG_FREE_IF_COPY(b, 0);
416 0 : PG_RETURN_POINTER(r);
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 *
5050 bruce 426 CBC 14 : 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 :
1731 tgl 437 14 : if (len <= 0)
438 1 : return NULL; /* no inputs? */
7522 bruce 439 13 : if ((*a)->numlevel == 0)
1731 tgl 440 1 : return NULL; /* any empty input means NULL result */
441 :
442 : /* num is the length of the longest common ancestor so far */
443 12 : num = (*a)->numlevel - 1;
444 :
445 : /* Compare each additional input to *a */
446 12 : ptr = a + 1;
7522 bruce 447 23 : while (ptr - a < len)
448 : {
449 12 : if ((*ptr)->numlevel == 0)
7553 450 1 : return NULL;
7522 451 11 : else if ((*ptr)->numlevel == 1)
452 2 : num = 0;
453 : else
454 : {
7553 455 9 : l1 = LTREE_FIRST(*a);
456 9 : l2 = LTREE_FIRST(*ptr);
1731 tgl 457 9 : tmp = Min(num, (*ptr)->numlevel - 1);
7522 bruce 458 9 : num = 0;
1731 tgl 459 23 : for (i = 0; i < tmp; i++)
460 : {
461 21 : if (l1->len == l2->len &&
462 18 : memcmp(l1->name, l2->name, l1->len) == 0)
7522 bruce 463 14 : num = i + 1;
464 : else
465 : break;
466 14 : l1 = LEVEL_NEXT(l1);
467 14 : l2 = LEVEL_NEXT(l2);
468 : }
469 : }
7553 470 11 : ptr++;
471 : }
472 :
473 : /* Now compute size of result ... */
1731 tgl 474 11 : reslen = LTREE_HDRSIZE;
7553 bruce 475 11 : l1 = LTREE_FIRST(*a);
7522 476 21 : for (i = 0; i < num; i++)
477 : {
7553 478 10 : reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
7522 479 10 : l1 = LEVEL_NEXT(l1);
480 : }
481 :
482 : /* ... and construct it by copying from *a */
2588 andres 483 11 : res = (ltree *) palloc0(reslen);
5884 tgl 484 11 : SET_VARSIZE(res, reslen);
7553 bruce 485 11 : res->numlevel = num;
486 :
487 11 : l1 = LTREE_FIRST(*a);
488 11 : l2 = LTREE_FIRST(res);
489 :
7522 490 21 : for (i = 0; i < num; i++)
491 : {
492 10 : memcpy(l2, l1, MAXALIGN(l1->len + LEVEL_HDRSIZE));
493 10 : l1 = LEVEL_NEXT(l1);
494 10 : l2 = LEVEL_NEXT(l2);
495 : }
496 :
7553 497 11 : return res;
498 : }
499 :
500 : Datum
7522 501 6 : lca(PG_FUNCTION_ARGS)
502 : {
503 : int i;
504 : ltree **a,
505 : *res;
506 :
507 6 : a = (ltree **) palloc(sizeof(ltree *) * fcinfo->nargs);
508 21 : for (i = 0; i < fcinfo->nargs; i++)
2029 tgl 509 15 : a[i] = PG_GETARG_LTREE_P(i);
7522 bruce 510 6 : res = lca_inner(a, (int) fcinfo->nargs);
511 21 : for (i = 0; i < fcinfo->nargs; i++)
512 15 : PG_FREE_IF_COPY(a[i], i);
7553 513 6 : pfree(a);
514 :
7522 515 6 : if (res)
7553 516 5 : PG_RETURN_POINTER(res);
517 : else
518 1 : PG_RETURN_NULL();
519 : }
520 :
521 : Datum
7314 522 1 : text2ltree(PG_FUNCTION_ARGS)
523 : {
5493 tgl 524 1 : text *in = PG_GETARG_TEXT_PP(0);
525 : char *s;
526 : ltree *out;
527 :
528 1 : s = text_to_cstring(in);
529 :
530 1 : out = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
531 : PointerGetDatum(s)));
7314 bruce 532 1 : pfree(s);
7188 533 1 : PG_FREE_IF_COPY(in, 0);
7314 534 1 : PG_RETURN_POINTER(out);
535 : }
536 :
537 :
538 : Datum
539 1 : ltree2text(PG_FUNCTION_ARGS)
540 : {
2029 tgl 541 1 : ltree *in = PG_GETARG_LTREE_P(0);
542 : char *ptr;
543 : int i;
544 : ltree_level *curlevel;
545 : text *out;
546 :
5884 547 1 : out = (text *) palloc(VARSIZE(in) + VARHDRSZ);
7188 bruce 548 1 : ptr = VARDATA(out);
7314 549 1 : curlevel = LTREE_FIRST(in);
7188 550 6 : for (i = 0; i < in->numlevel; i++)
551 : {
552 5 : if (i != 0)
553 : {
7314 554 4 : *ptr = '.';
555 4 : ptr++;
556 : }
557 5 : memcpy(ptr, curlevel->name, curlevel->len);
558 5 : ptr += curlevel->len;
559 5 : curlevel = LEVEL_NEXT(curlevel);
560 : }
561 :
5885 tgl 562 1 : SET_VARSIZE(out, ptr - ((char *) out));
7314 bruce 563 1 : PG_FREE_IF_COPY(in, 0);
564 :
565 1 : 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
6192 bruce 576 UBC 0 : ltreeparentsel(PG_FUNCTION_ARGS)
577 : {
578 0 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
579 0 : Oid operator = PG_GETARG_OID(1);
580 0 : List *args = (List *) PG_GETARG_POINTER(2);
581 0 : int varRelid = PG_GETARG_INT32(3);
582 : double selec;
583 :
584 : /* Use generic restriction selectivity logic, with default 0.001. */
1038 tgl 585 0 : selec = generic_restriction_selectivity(root, operator, InvalidOid,
586 : args, varRelid,
587 : 0.001);
588 :
6192 bruce 589 0 : PG_RETURN_FLOAT8((float8) selec);
590 : }
|
