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