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