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