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 :
17 CBC 3 : PG_MODULE_MAGIC;
18 :
19 : /* compare functions */
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);
32 6 : PG_FUNCTION_INFO_V1(ltree_index);
33 3 : PG_FUNCTION_INFO_V1(ltree_addltree);
34 3 : PG_FUNCTION_INFO_V1(ltree_addtext);
35 2 : PG_FUNCTION_INFO_V1(ltree_textadd);
36 16 : PG_FUNCTION_INFO_V1(lca);
37 3 : PG_FUNCTION_INFO_V1(ltree2text);
38 3 : PG_FUNCTION_INFO_V1(text2ltree);
39 2 : PG_FUNCTION_INFO_V1(ltreeparentsel);
40 :
41 : int
42 135974 : ltree_compare(const ltree *a, const ltree *b)
43 : {
44 135974 : ltree_level *al = LTREE_FIRST(a);
45 135974 : ltree_level *bl = LTREE_FIRST(b);
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 :
53 214887 : if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
54 : {
55 98104 : if (al->len != bl->len)
56 8553 : return (al->len - bl->len) * 10 * (an + 1);
57 : }
58 : else
59 : {
60 116783 : if (res < 0)
61 58656 : res = -1;
62 : else
63 58127 : res = 1;
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 : {
86 71218 : RUNCMP;
87 71218 : PG_RETURN_INT32(res);
88 : }
89 :
90 : Datum
91 1132 : ltree_lt(PG_FUNCTION_ARGS)
92 : {
93 1132 : RUNCMP;
94 1132 : PG_RETURN_BOOL(res < 0);
95 : }
96 :
97 : Datum
98 1133 : ltree_le(PG_FUNCTION_ARGS)
99 : {
100 1133 : RUNCMP;
101 1133 : PG_RETURN_BOOL(res <= 0);
102 : }
103 :
104 : Datum
105 1009 : ltree_eq(PG_FUNCTION_ARGS)
106 : {
107 1009 : RUNCMP;
108 1009 : PG_RETURN_BOOL(res == 0);
109 : }
110 :
111 : Datum
112 1899 : ltree_ge(PG_FUNCTION_ARGS)
113 : {
114 1899 : RUNCMP;
115 1899 : PG_RETURN_BOOL(res >= 0);
116 : }
117 :
118 : Datum
119 1898 : ltree_gt(PG_FUNCTION_ARGS)
120 : {
121 1898 : RUNCMP;
122 1898 : PG_RETURN_BOOL(res > 0);
123 : }
124 :
125 : Datum
126 UBC 0 : ltree_ne(PG_FUNCTION_ARGS)
127 : {
128 0 : RUNCMP;
129 0 : PG_RETURN_BOOL(res != 0);
130 : }
131 :
132 : Datum
133 CBC 2 : nlevel(PG_FUNCTION_ARGS)
134 : {
135 2 : ltree *a = PG_GETARG_LTREE_P(0);
136 2 : int res = a->numlevel;
137 :
138 2 : PG_FREE_IF_COPY(a, 0);
139 2 : PG_RETURN_INT32(res);
140 : }
141 :
142 : bool
143 21188 : inner_isparent(const ltree *c, const ltree *p)
144 : {
145 21188 : ltree_level *cl = LTREE_FIRST(c);
146 21188 : ltree_level *pl = LTREE_FIRST(p);
147 21188 : int pn = p->numlevel;
148 :
149 21188 : if (pn > c->numlevel)
150 10166 : return false;
151 :
152 12019 : while (pn > 0)
153 : {
154 11883 : if (cl->len != pl->len)
155 7960 : return false;
156 3923 : if (memcmp(cl->name, pl->name, cl->len) != 0)
157 2926 : return false;
158 :
159 997 : pn--;
160 997 : cl = LEVEL_NEXT(cl);
161 997 : pl = LEVEL_NEXT(pl);
162 : }
163 136 : return true;
164 : }
165 :
166 : Datum
167 11538 : ltree_isparent(PG_FUNCTION_ARGS)
168 : {
169 11538 : ltree *c = PG_GETARG_LTREE_P(1);
170 11538 : ltree *p = PG_GETARG_LTREE_P(0);
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 : {
181 9320 : ltree *c = PG_GETARG_LTREE_P(0);
182 9320 : ltree *p = PG_GETARG_LTREE_P(1);
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 *
192 9 : inner_subltree(ltree *t, int32 startpos, int32 endpos)
193 : {
194 9 : char *start = NULL,
195 9 : *end = NULL;
196 9 : ltree_level *ptr = LTREE_FIRST(t);
197 : ltree *res;
198 : int i;
199 :
200 9 : if (startpos < 0 || endpos < 0 || startpos >= t->numlevel || startpos > endpos)
201 UBC 0 : ereport(ERROR,
202 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
203 : errmsg("invalid positions")));
204 :
205 CBC 9 : if (endpos > t->numlevel)
206 2 : endpos = t->numlevel;
207 :
208 9 : start = end = (char *) ptr;
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);
216 8 : break;
217 : }
218 10 : ptr = LEVEL_NEXT(ptr);
219 : }
220 :
221 9 : res = (ltree *) palloc0(LTREE_HDRSIZE + (end - start));
222 9 : SET_VARSIZE(res, LTREE_HDRSIZE + (end - start));
223 9 : res->numlevel = endpos - startpos;
224 :
225 9 : memcpy(LTREE_FIRST(res), start, end - start);
226 :
227 9 : return res;
228 : }
229 :
230 : Datum
231 1 : subltree(PG_FUNCTION_ARGS)
232 : {
233 1 : ltree *t = PG_GETARG_LTREE_P(0);
234 1 : ltree *res = inner_subltree(t, PG_GETARG_INT32(1), PG_GETARG_INT32(2));
235 :
236 1 : PG_FREE_IF_COPY(t, 0);
237 1 : PG_RETURN_POINTER(res);
238 : }
239 :
240 : Datum
241 8 : subpath(PG_FUNCTION_ARGS)
242 : {
243 8 : ltree *t = PG_GETARG_LTREE_P(0);
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 :
249 8 : end = start + len;
250 :
251 8 : if (start < 0)
252 : {
253 1 : start = t->numlevel + start;
254 1 : end = start + len;
255 : }
256 8 : if (start < 0)
257 : { /* start > t->numlevel */
258 UBC 0 : start = t->numlevel + start;
259 0 : end = start + len;
260 : }
261 :
262 CBC 8 : if (len < 0)
263 2 : end = t->numlevel + len;
264 6 : else if (len == 0)
265 4 : end = (fcinfo->nargs == 3) ? start : 0xffff;
266 :
267 8 : res = inner_subltree(t, start, end);
268 :
269 8 : PG_FREE_IF_COPY(t, 0);
270 8 : PG_RETURN_POINTER(res);
271 : }
272 :
273 : static ltree *
274 6 : ltree_concat(ltree *a, ltree *b)
275 : {
276 : ltree *r;
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 :
285 5 : r = (ltree *) palloc0(VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
286 5 : SET_VARSIZE(r, VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
287 5 : r->numlevel = (uint16) numlevel;
288 :
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);
293 5 : return r;
294 : }
295 :
296 : Datum
297 5 : ltree_addltree(PG_FUNCTION_ARGS)
298 : {
299 5 : ltree *a = PG_GETARG_LTREE_P(0);
300 5 : ltree *b = PG_GETARG_LTREE_P(1);
301 : ltree *r;
302 :
303 5 : r = ltree_concat(a, b);
304 4 : PG_FREE_IF_COPY(a, 0);
305 4 : PG_FREE_IF_COPY(b, 1);
306 4 : PG_RETURN_POINTER(r);
307 : }
308 :
309 : Datum
310 1 : ltree_addtext(PG_FUNCTION_ARGS)
311 : {
312 1 : ltree *a = PG_GETARG_LTREE_P(0);
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 :
323 1 : pfree(s);
324 :
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);
331 1 : PG_RETURN_POINTER(r);
332 : }
333 :
334 : Datum
335 18 : ltree_index(PG_FUNCTION_ARGS)
336 : {
337 18 : ltree *a = PG_GETARG_LTREE_P(0);
338 18 : ltree *b = PG_GETARG_LTREE_P(1);
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 : {
357 1 : PG_FREE_IF_COPY(a, 0);
358 1 : PG_FREE_IF_COPY(b, 1);
359 1 : PG_RETURN_INT32(-1);
360 : }
361 :
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 : {
371 79 : if (!(aptr->len == bptr->len && memcmp(aptr->name, bptr->name, aptr->len) == 0))
372 : break;
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;
380 14 : break;
381 : }
382 : }
383 92 : startptr = LEVEL_NEXT(startptr);
384 : }
385 :
386 17 : if (!found)
387 3 : i = -1;
388 :
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
395 UBC 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 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 :
437 14 : if (len <= 0)
438 1 : return NULL; /* no inputs? */
439 13 : if ((*a)->numlevel == 0)
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;
447 23 : while (ptr - a < len)
448 : {
449 12 : if ((*ptr)->numlevel == 0)
450 1 : return NULL;
451 11 : else if ((*ptr)->numlevel == 1)
452 2 : num = 0;
453 : else
454 : {
455 9 : l1 = LTREE_FIRST(*a);
456 9 : l2 = LTREE_FIRST(*ptr);
457 9 : tmp = Min(num, (*ptr)->numlevel - 1);
458 9 : num = 0;
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)
463 14 : num = i + 1;
464 : else
465 : break;
466 14 : l1 = LEVEL_NEXT(l1);
467 14 : l2 = LEVEL_NEXT(l2);
468 : }
469 : }
470 11 : ptr++;
471 : }
472 :
473 : /* Now compute size of result ... */
474 11 : reslen = LTREE_HDRSIZE;
475 11 : l1 = LTREE_FIRST(*a);
476 21 : for (i = 0; i < num; i++)
477 : {
478 10 : reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
479 10 : l1 = LEVEL_NEXT(l1);
480 : }
481 :
482 : /* ... and construct it by copying from *a */
483 11 : res = (ltree *) palloc0(reslen);
484 11 : SET_VARSIZE(res, reslen);
485 11 : res->numlevel = num;
486 :
487 11 : l1 = LTREE_FIRST(*a);
488 11 : l2 = LTREE_FIRST(res);
489 :
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 :
497 11 : return res;
498 : }
499 :
500 : Datum
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++)
509 15 : a[i] = PG_GETARG_LTREE_P(i);
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);
513 6 : pfree(a);
514 :
515 6 : if (res)
516 5 : PG_RETURN_POINTER(res);
517 : else
518 1 : PG_RETURN_NULL();
519 : }
520 :
521 : Datum
522 1 : text2ltree(PG_FUNCTION_ARGS)
523 : {
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)));
532 1 : pfree(s);
533 1 : PG_FREE_IF_COPY(in, 0);
534 1 : PG_RETURN_POINTER(out);
535 : }
536 :
537 :
538 : Datum
539 1 : ltree2text(PG_FUNCTION_ARGS)
540 : {
541 1 : ltree *in = PG_GETARG_LTREE_P(0);
542 : char *ptr;
543 : int i;
544 : ltree_level *curlevel;
545 : text *out;
546 :
547 1 : out = (text *) palloc(VARSIZE(in) + VARHDRSZ);
548 1 : ptr = VARDATA(out);
549 1 : curlevel = LTREE_FIRST(in);
550 6 : for (i = 0; i < in->numlevel; i++)
551 : {
552 5 : if (i != 0)
553 : {
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 :
562 1 : SET_VARSIZE(out, ptr - ((char *) out));
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
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. */
585 0 : selec = generic_restriction_selectivity(root, operator, InvalidOid,
586 : args, varRelid,
587 : 0.001);
588 :
589 0 : PG_RETURN_FLOAT8((float8) selec);
590 : }
|
