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