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 6 : PG_MODULE_MAGIC_EXT(
17 : .name = "ltree",
18 : .version = PG_VERSION
19 : );
20 :
21 : /* compare functions */
22 6 : PG_FUNCTION_INFO_V1(ltree_cmp);
23 6 : PG_FUNCTION_INFO_V1(ltree_lt);
24 6 : PG_FUNCTION_INFO_V1(ltree_le);
25 6 : PG_FUNCTION_INFO_V1(ltree_eq);
26 4 : PG_FUNCTION_INFO_V1(ltree_ne);
27 6 : PG_FUNCTION_INFO_V1(ltree_ge);
28 6 : PG_FUNCTION_INFO_V1(ltree_gt);
29 6 : PG_FUNCTION_INFO_V1(hash_ltree);
30 6 : PG_FUNCTION_INFO_V1(hash_ltree_extended);
31 6 : PG_FUNCTION_INFO_V1(nlevel);
32 6 : PG_FUNCTION_INFO_V1(ltree_isparent);
33 6 : PG_FUNCTION_INFO_V1(ltree_risparent);
34 6 : PG_FUNCTION_INFO_V1(subltree);
35 12 : PG_FUNCTION_INFO_V1(subpath);
36 12 : PG_FUNCTION_INFO_V1(ltree_index);
37 6 : PG_FUNCTION_INFO_V1(ltree_addltree);
38 6 : PG_FUNCTION_INFO_V1(ltree_addtext);
39 4 : PG_FUNCTION_INFO_V1(ltree_textadd);
40 32 : PG_FUNCTION_INFO_V1(lca);
41 6 : PG_FUNCTION_INFO_V1(ltree2text);
42 6 : PG_FUNCTION_INFO_V1(text2ltree);
43 4 : PG_FUNCTION_INFO_V1(ltreeparentsel);
44 :
45 : int
46 275896 : ltree_compare(const ltree *a, const ltree *b)
47 : {
48 275896 : ltree_level *al = LTREE_FIRST(a);
49 275896 : ltree_level *bl = LTREE_FIRST(b);
50 275896 : int an = a->numlevel;
51 275896 : int bn = b->numlevel;
52 :
53 474030 : while (an > 0 && bn > 0)
54 : {
55 : int res;
56 :
57 450746 : if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
58 : {
59 215804 : if (al->len != bl->len)
60 17670 : return (al->len - bl->len) * 10 * (an + 1);
61 : }
62 : else
63 : {
64 234942 : if (res < 0)
65 114432 : res = -1;
66 : else
67 120510 : res = 1;
68 234942 : return res * 10 * (an + 1);
69 : }
70 :
71 198134 : an--;
72 198134 : bn--;
73 198134 : al = LEVEL_NEXT(al);
74 198134 : bl = LEVEL_NEXT(bl);
75 : }
76 :
77 23284 : 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 142436 : ltree_cmp(PG_FUNCTION_ARGS)
89 : {
90 142436 : RUNCMP;
91 142436 : PG_RETURN_INT32(res);
92 : }
93 :
94 : Datum
95 4280 : ltree_lt(PG_FUNCTION_ARGS)
96 : {
97 4280 : RUNCMP;
98 4280 : PG_RETURN_BOOL(res < 0);
99 : }
100 :
101 : Datum
102 4282 : ltree_le(PG_FUNCTION_ARGS)
103 : {
104 4282 : RUNCMP;
105 4282 : PG_RETURN_BOOL(res <= 0);
106 : }
107 :
108 : Datum
109 4032 : ltree_eq(PG_FUNCTION_ARGS)
110 : {
111 4032 : RUNCMP;
112 4032 : PG_RETURN_BOOL(res == 0);
113 : }
114 :
115 : Datum
116 4236 : ltree_ge(PG_FUNCTION_ARGS)
117 : {
118 4236 : RUNCMP;
119 4236 : PG_RETURN_BOOL(res >= 0);
120 : }
121 :
122 : Datum
123 4234 : ltree_gt(PG_FUNCTION_ARGS)
124 : {
125 4234 : RUNCMP;
126 4234 : 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 6062 : hash_ltree(PG_FUNCTION_ARGS)
139 : {
140 6062 : ltree *a = PG_GETARG_LTREE_P(0);
141 6062 : uint32 result = 1;
142 6062 : int an = a->numlevel;
143 6062 : ltree_level *al = LTREE_FIRST(a);
144 :
145 45744 : while (an > 0)
146 : {
147 39682 : 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 39682 : result = (result << 5) - result + levelHash;
157 :
158 39682 : an--;
159 39682 : al = LEVEL_NEXT(al);
160 : }
161 :
162 6062 : PG_FREE_IF_COPY(a, 0);
163 6062 : PG_RETURN_UINT32(result);
164 : }
165 :
166 : /* Compute an extended hash for the ltree */
167 : Datum
168 24 : hash_ltree_extended(PG_FUNCTION_ARGS)
169 : {
170 24 : ltree *a = PG_GETARG_LTREE_P(0);
171 24 : const uint64 seed = PG_GETARG_INT64(1);
172 24 : uint64 result = 1;
173 24 : int an = a->numlevel;
174 24 : 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 24 : if (an == 0)
183 : {
184 4 : PG_FREE_IF_COPY(a, 0);
185 4 : PG_RETURN_UINT64(result + seed);
186 : }
187 :
188 56 : while (an > 0)
189 : {
190 36 : uint64 levelHash = DatumGetUInt64(hash_any_extended((unsigned char *) al->name, al->len, seed));
191 :
192 36 : result = (result << 5) - result + levelHash;
193 :
194 36 : an--;
195 36 : al = LEVEL_NEXT(al);
196 : }
197 :
198 20 : PG_FREE_IF_COPY(a, 0);
199 20 : PG_RETURN_UINT64(result);
200 : }
201 :
202 : Datum
203 4 : nlevel(PG_FUNCTION_ARGS)
204 : {
205 4 : ltree *a = PG_GETARG_LTREE_P(0);
206 4 : int res = a->numlevel;
207 :
208 4 : PG_FREE_IF_COPY(a, 0);
209 4 : PG_RETURN_INT32(res);
210 : }
211 :
212 : bool
213 42376 : inner_isparent(const ltree *c, const ltree *p)
214 : {
215 42376 : ltree_level *cl = LTREE_FIRST(c);
216 42376 : ltree_level *pl = LTREE_FIRST(p);
217 42376 : int pn = p->numlevel;
218 :
219 42376 : if (pn > c->numlevel)
220 20332 : return false;
221 :
222 24038 : while (pn > 0)
223 : {
224 23766 : if (cl->len != pl->len)
225 15920 : return false;
226 7846 : if (memcmp(cl->name, pl->name, cl->len) != 0)
227 5852 : return false;
228 :
229 1994 : pn--;
230 1994 : cl = LEVEL_NEXT(cl);
231 1994 : pl = LEVEL_NEXT(pl);
232 : }
233 272 : return true;
234 : }
235 :
236 : Datum
237 23076 : ltree_isparent(PG_FUNCTION_ARGS)
238 : {
239 23076 : ltree *c = PG_GETARG_LTREE_P(1);
240 23076 : ltree *p = PG_GETARG_LTREE_P(0);
241 23076 : bool res = inner_isparent(c, p);
242 :
243 23076 : PG_FREE_IF_COPY(c, 1);
244 23076 : PG_FREE_IF_COPY(p, 0);
245 23076 : PG_RETURN_BOOL(res);
246 : }
247 :
248 : Datum
249 18640 : ltree_risparent(PG_FUNCTION_ARGS)
250 : {
251 18640 : ltree *c = PG_GETARG_LTREE_P(0);
252 18640 : ltree *p = PG_GETARG_LTREE_P(1);
253 18640 : bool res = inner_isparent(c, p);
254 :
255 18640 : PG_FREE_IF_COPY(c, 0);
256 18640 : PG_FREE_IF_COPY(p, 1);
257 18640 : PG_RETURN_BOOL(res);
258 : }
259 :
260 :
261 : static ltree *
262 20 : inner_subltree(ltree *t, int32 startpos, int32 endpos)
263 : {
264 20 : char *start = NULL,
265 20 : *end = NULL;
266 20 : ltree_level *ptr = LTREE_FIRST(t);
267 : ltree *res;
268 : int i;
269 :
270 20 : if (startpos < 0 || endpos < 0 || startpos >= t->numlevel || startpos > endpos)
271 2 : ereport(ERROR,
272 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
273 : errmsg("invalid positions")));
274 :
275 18 : if (endpos > t->numlevel)
276 4 : endpos = t->numlevel;
277 :
278 18 : start = end = (char *) ptr;
279 38 : for (i = 0; i < endpos; i++)
280 : {
281 36 : if (i == startpos)
282 14 : start = (char *) ptr;
283 36 : if (i == endpos - 1)
284 : {
285 16 : end = (char *) LEVEL_NEXT(ptr);
286 16 : break;
287 : }
288 20 : ptr = LEVEL_NEXT(ptr);
289 : }
290 :
291 18 : res = (ltree *) palloc0(LTREE_HDRSIZE + (end - start));
292 18 : SET_VARSIZE(res, LTREE_HDRSIZE + (end - start));
293 18 : res->numlevel = endpos - startpos;
294 :
295 18 : memcpy(LTREE_FIRST(res), start, end - start);
296 :
297 18 : return res;
298 : }
299 :
300 : Datum
301 2 : subltree(PG_FUNCTION_ARGS)
302 : {
303 2 : ltree *t = PG_GETARG_LTREE_P(0);
304 2 : ltree *res = inner_subltree(t, PG_GETARG_INT32(1), PG_GETARG_INT32(2));
305 :
306 2 : PG_FREE_IF_COPY(t, 0);
307 2 : PG_RETURN_POINTER(res);
308 : }
309 :
310 : Datum
311 18 : subpath(PG_FUNCTION_ARGS)
312 : {
313 18 : ltree *t = PG_GETARG_LTREE_P(0);
314 18 : int32 start = PG_GETARG_INT32(1);
315 18 : int32 len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
316 : int32 end;
317 : ltree *res;
318 :
319 18 : if (start < 0)
320 4 : start = t->numlevel + start;
321 :
322 18 : if (len < 0)
323 4 : end = t->numlevel + len;
324 14 : else if (len == 0)
325 10 : end = (fcinfo->nargs == 3) ? start : LTREE_MAX_LEVELS;
326 : else
327 4 : end = start + len;
328 :
329 18 : res = inner_subltree(t, start, end);
330 :
331 16 : PG_FREE_IF_COPY(t, 0);
332 16 : PG_RETURN_POINTER(res);
333 : }
334 :
335 : static ltree *
336 12 : ltree_concat(ltree *a, ltree *b)
337 : {
338 : ltree *r;
339 12 : int numlevel = (int) a->numlevel + b->numlevel;
340 :
341 12 : if (numlevel > LTREE_MAX_LEVELS)
342 2 : 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 10 : r = (ltree *) palloc0(VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
348 10 : SET_VARSIZE(r, VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
349 10 : r->numlevel = (uint16) numlevel;
350 :
351 10 : memcpy(LTREE_FIRST(r), LTREE_FIRST(a), VARSIZE(a) - LTREE_HDRSIZE);
352 10 : memcpy(((char *) LTREE_FIRST(r)) + VARSIZE(a) - LTREE_HDRSIZE,
353 : LTREE_FIRST(b),
354 10 : VARSIZE(b) - LTREE_HDRSIZE);
355 10 : return r;
356 : }
357 :
358 : Datum
359 10 : ltree_addltree(PG_FUNCTION_ARGS)
360 : {
361 10 : ltree *a = PG_GETARG_LTREE_P(0);
362 10 : ltree *b = PG_GETARG_LTREE_P(1);
363 : ltree *r;
364 :
365 10 : r = ltree_concat(a, b);
366 8 : PG_FREE_IF_COPY(a, 0);
367 8 : PG_FREE_IF_COPY(b, 1);
368 8 : PG_RETURN_POINTER(r);
369 : }
370 :
371 : Datum
372 2 : ltree_addtext(PG_FUNCTION_ARGS)
373 : {
374 2 : ltree *a = PG_GETARG_LTREE_P(0);
375 2 : text *b = PG_GETARG_TEXT_PP(1);
376 : char *s;
377 : ltree *r,
378 : *tmp;
379 :
380 2 : s = text_to_cstring(b);
381 :
382 2 : tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
383 : PointerGetDatum(s)));
384 :
385 2 : pfree(s);
386 :
387 2 : r = ltree_concat(a, tmp);
388 :
389 2 : pfree(tmp);
390 :
391 2 : PG_FREE_IF_COPY(a, 0);
392 2 : PG_FREE_IF_COPY(b, 1);
393 2 : PG_RETURN_POINTER(r);
394 : }
395 :
396 : Datum
397 36 : ltree_index(PG_FUNCTION_ARGS)
398 : {
399 36 : ltree *a = PG_GETARG_LTREE_P(0);
400 36 : ltree *b = PG_GETARG_LTREE_P(1);
401 36 : int start = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
402 : int i,
403 : j;
404 : ltree_level *startptr,
405 : *aptr,
406 : *bptr;
407 36 : bool found = false;
408 :
409 36 : if (start < 0)
410 : {
411 10 : if (-start >= a->numlevel)
412 2 : start = 0;
413 : else
414 8 : start = (int) (a->numlevel) + start;
415 : }
416 :
417 36 : if (a->numlevel - start < b->numlevel || a->numlevel == 0 || b->numlevel == 0)
418 : {
419 2 : PG_FREE_IF_COPY(a, 0);
420 2 : PG_FREE_IF_COPY(b, 1);
421 2 : PG_RETURN_INT32(-1);
422 : }
423 :
424 34 : startptr = LTREE_FIRST(a);
425 218 : for (i = 0; i <= a->numlevel - b->numlevel; i++)
426 : {
427 212 : if (i >= start)
428 : {
429 116 : aptr = startptr;
430 116 : bptr = LTREE_FIRST(b);
431 186 : for (j = 0; j < b->numlevel; j++)
432 : {
433 158 : if (!(aptr->len == bptr->len && memcmp(aptr->name, bptr->name, aptr->len) == 0))
434 : break;
435 70 : aptr = LEVEL_NEXT(aptr);
436 70 : bptr = LEVEL_NEXT(bptr);
437 : }
438 :
439 116 : if (j == b->numlevel)
440 : {
441 28 : found = true;
442 28 : break;
443 : }
444 : }
445 184 : startptr = LEVEL_NEXT(startptr);
446 : }
447 :
448 34 : if (!found)
449 6 : i = -1;
450 :
451 34 : PG_FREE_IF_COPY(a, 0);
452 34 : PG_FREE_IF_COPY(b, 1);
453 34 : 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 28 : 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 28 : if (len <= 0)
500 2 : return NULL; /* no inputs? */
501 26 : if ((*a)->numlevel == 0)
502 2 : return NULL; /* any empty input means NULL result */
503 :
504 : /* num is the length of the longest common ancestor so far */
505 24 : num = (*a)->numlevel - 1;
506 :
507 : /* Compare each additional input to *a */
508 24 : ptr = a + 1;
509 46 : while (ptr - a < len)
510 : {
511 24 : if ((*ptr)->numlevel == 0)
512 2 : return NULL;
513 22 : else if ((*ptr)->numlevel == 1)
514 4 : num = 0;
515 : else
516 : {
517 18 : l1 = LTREE_FIRST(*a);
518 18 : l2 = LTREE_FIRST(*ptr);
519 18 : tmp = Min(num, (*ptr)->numlevel - 1);
520 18 : num = 0;
521 46 : for (i = 0; i < tmp; i++)
522 : {
523 42 : if (l1->len == l2->len &&
524 36 : memcmp(l1->name, l2->name, l1->len) == 0)
525 28 : num = i + 1;
526 : else
527 : break;
528 28 : l1 = LEVEL_NEXT(l1);
529 28 : l2 = LEVEL_NEXT(l2);
530 : }
531 : }
532 22 : ptr++;
533 : }
534 :
535 : /* Now compute size of result ... */
536 22 : reslen = LTREE_HDRSIZE;
537 22 : l1 = LTREE_FIRST(*a);
538 42 : for (i = 0; i < num; i++)
539 : {
540 20 : reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
541 20 : l1 = LEVEL_NEXT(l1);
542 : }
543 :
544 : /* ... and construct it by copying from *a */
545 22 : res = (ltree *) palloc0(reslen);
546 22 : SET_VARSIZE(res, reslen);
547 22 : res->numlevel = num;
548 :
549 22 : l1 = LTREE_FIRST(*a);
550 22 : l2 = LTREE_FIRST(res);
551 :
552 42 : for (i = 0; i < num; i++)
553 : {
554 20 : memcpy(l2, l1, MAXALIGN(l1->len + LEVEL_HDRSIZE));
555 20 : l1 = LEVEL_NEXT(l1);
556 20 : l2 = LEVEL_NEXT(l2);
557 : }
558 :
559 22 : return res;
560 : }
561 :
562 : Datum
563 12 : lca(PG_FUNCTION_ARGS)
564 : {
565 : int i;
566 : ltree **a,
567 : *res;
568 :
569 12 : a = (ltree **) palloc(sizeof(ltree *) * fcinfo->nargs);
570 42 : for (i = 0; i < fcinfo->nargs; i++)
571 30 : a[i] = PG_GETARG_LTREE_P(i);
572 12 : res = lca_inner(a, (int) fcinfo->nargs);
573 42 : for (i = 0; i < fcinfo->nargs; i++)
574 30 : PG_FREE_IF_COPY(a[i], i);
575 12 : pfree(a);
576 :
577 12 : if (res)
578 10 : PG_RETURN_POINTER(res);
579 : else
580 2 : PG_RETURN_NULL();
581 : }
582 :
583 : Datum
584 2 : text2ltree(PG_FUNCTION_ARGS)
585 : {
586 2 : text *in = PG_GETARG_TEXT_PP(0);
587 : char *s;
588 : ltree *out;
589 :
590 2 : s = text_to_cstring(in);
591 :
592 2 : out = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
593 : PointerGetDatum(s)));
594 2 : pfree(s);
595 2 : PG_FREE_IF_COPY(in, 0);
596 2 : PG_RETURN_POINTER(out);
597 : }
598 :
599 :
600 : Datum
601 2 : ltree2text(PG_FUNCTION_ARGS)
602 : {
603 2 : ltree *in = PG_GETARG_LTREE_P(0);
604 : char *ptr;
605 : int i;
606 : ltree_level *curlevel;
607 : text *out;
608 :
609 2 : out = (text *) palloc(VARSIZE(in) + VARHDRSZ);
610 2 : ptr = VARDATA(out);
611 2 : curlevel = LTREE_FIRST(in);
612 12 : for (i = 0; i < in->numlevel; i++)
613 : {
614 10 : if (i != 0)
615 : {
616 8 : *ptr = '.';
617 8 : ptr++;
618 : }
619 10 : memcpy(ptr, curlevel->name, curlevel->len);
620 10 : ptr += curlevel->len;
621 10 : curlevel = LEVEL_NEXT(curlevel);
622 : }
623 :
624 2 : SET_VARSIZE(out, ptr - ((char *) out));
625 2 : PG_FREE_IF_COPY(in, 0);
626 :
627 2 : 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 : }
|
