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 277218 : ltree_compare(const ltree *a, const ltree *b)
47 : {
48 277218 : ltree_level *al = LTREE_FIRST(a);
49 277218 : ltree_level *bl = LTREE_FIRST(b);
50 277218 : int an = a->numlevel;
51 277218 : int bn = b->numlevel;
52 :
53 473406 : while (an > 0 && bn > 0)
54 : {
55 : int res;
56 :
57 450076 : if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
58 : {
59 213832 : if (al->len != bl->len)
60 17644 : return (al->len - bl->len) * 10 * (an + 1);
61 : }
62 : else
63 : {
64 236244 : if (res < 0)
65 115366 : res = -1;
66 : else
67 120878 : res = 1;
68 236244 : return res * 10 * (an + 1);
69 : }
70 :
71 196188 : an--;
72 196188 : bn--;
73 196188 : al = LEVEL_NEXT(al);
74 196188 : bl = LEVEL_NEXT(bl);
75 : }
76 :
77 23330 : 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 4278 : ltree_lt(PG_FUNCTION_ARGS)
96 : {
97 4278 : RUNCMP;
98 4278 : PG_RETURN_BOOL(res < 0);
99 : }
100 :
101 : Datum
102 4280 : ltree_le(PG_FUNCTION_ARGS)
103 : {
104 4280 : RUNCMP;
105 4280 : 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 4064 : ltree_ge(PG_FUNCTION_ARGS)
117 : {
118 4064 : RUNCMP;
119 4064 : PG_RETURN_BOOL(res >= 0);
120 : }
121 :
122 : Datum
123 4064 : ltree_gt(PG_FUNCTION_ARGS)
124 : {
125 4064 : RUNCMP;
126 4064 : 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 18 : inner_subltree(ltree *t, int32 startpos, int32 endpos)
263 : {
264 18 : char *start = NULL,
265 18 : *end = NULL;
266 18 : ltree_level *ptr = LTREE_FIRST(t);
267 : ltree *res;
268 : int i;
269 :
270 18 : 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 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 16 : subpath(PG_FUNCTION_ARGS)
312 : {
313 16 : ltree *t = PG_GETARG_LTREE_P(0);
314 16 : int32 start = PG_GETARG_INT32(1);
315 16 : int32 len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
316 : int32 end;
317 : ltree *res;
318 :
319 16 : end = start + len;
320 :
321 16 : if (start < 0)
322 : {
323 2 : start = t->numlevel + start;
324 2 : end = start + len;
325 : }
326 16 : if (start < 0)
327 : { /* start > t->numlevel */
328 0 : start = t->numlevel + start;
329 0 : end = start + len;
330 : }
331 :
332 16 : if (len < 0)
333 4 : end = t->numlevel + len;
334 12 : else if (len == 0)
335 8 : end = (fcinfo->nargs == 3) ? start : 0xffff;
336 :
337 16 : res = inner_subltree(t, start, end);
338 :
339 16 : PG_FREE_IF_COPY(t, 0);
340 16 : PG_RETURN_POINTER(res);
341 : }
342 :
343 : static ltree *
344 12 : ltree_concat(ltree *a, ltree *b)
345 : {
346 : ltree *r;
347 12 : int numlevel = (int) a->numlevel + b->numlevel;
348 :
349 12 : if (numlevel > LTREE_MAX_LEVELS)
350 2 : ereport(ERROR,
351 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
352 : errmsg("number of ltree levels (%d) exceeds the maximum allowed (%d)",
353 : numlevel, LTREE_MAX_LEVELS)));
354 :
355 10 : r = (ltree *) palloc0(VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
356 10 : SET_VARSIZE(r, VARSIZE(a) + VARSIZE(b) - LTREE_HDRSIZE);
357 10 : r->numlevel = (uint16) numlevel;
358 :
359 10 : memcpy(LTREE_FIRST(r), LTREE_FIRST(a), VARSIZE(a) - LTREE_HDRSIZE);
360 10 : memcpy(((char *) LTREE_FIRST(r)) + VARSIZE(a) - LTREE_HDRSIZE,
361 : LTREE_FIRST(b),
362 10 : VARSIZE(b) - LTREE_HDRSIZE);
363 10 : return r;
364 : }
365 :
366 : Datum
367 10 : ltree_addltree(PG_FUNCTION_ARGS)
368 : {
369 10 : ltree *a = PG_GETARG_LTREE_P(0);
370 10 : ltree *b = PG_GETARG_LTREE_P(1);
371 : ltree *r;
372 :
373 10 : r = ltree_concat(a, b);
374 8 : PG_FREE_IF_COPY(a, 0);
375 8 : PG_FREE_IF_COPY(b, 1);
376 8 : PG_RETURN_POINTER(r);
377 : }
378 :
379 : Datum
380 2 : ltree_addtext(PG_FUNCTION_ARGS)
381 : {
382 2 : ltree *a = PG_GETARG_LTREE_P(0);
383 2 : text *b = PG_GETARG_TEXT_PP(1);
384 : char *s;
385 : ltree *r,
386 : *tmp;
387 :
388 2 : s = text_to_cstring(b);
389 :
390 2 : tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
391 : PointerGetDatum(s)));
392 :
393 2 : pfree(s);
394 :
395 2 : r = ltree_concat(a, tmp);
396 :
397 2 : pfree(tmp);
398 :
399 2 : PG_FREE_IF_COPY(a, 0);
400 2 : PG_FREE_IF_COPY(b, 1);
401 2 : PG_RETURN_POINTER(r);
402 : }
403 :
404 : Datum
405 36 : ltree_index(PG_FUNCTION_ARGS)
406 : {
407 36 : ltree *a = PG_GETARG_LTREE_P(0);
408 36 : ltree *b = PG_GETARG_LTREE_P(1);
409 36 : int start = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
410 : int i,
411 : j;
412 : ltree_level *startptr,
413 : *aptr,
414 : *bptr;
415 36 : bool found = false;
416 :
417 36 : if (start < 0)
418 : {
419 10 : if (-start >= a->numlevel)
420 2 : start = 0;
421 : else
422 8 : start = (int) (a->numlevel) + start;
423 : }
424 :
425 36 : if (a->numlevel - start < b->numlevel || a->numlevel == 0 || b->numlevel == 0)
426 : {
427 2 : PG_FREE_IF_COPY(a, 0);
428 2 : PG_FREE_IF_COPY(b, 1);
429 2 : PG_RETURN_INT32(-1);
430 : }
431 :
432 34 : startptr = LTREE_FIRST(a);
433 218 : for (i = 0; i <= a->numlevel - b->numlevel; i++)
434 : {
435 212 : if (i >= start)
436 : {
437 116 : aptr = startptr;
438 116 : bptr = LTREE_FIRST(b);
439 186 : for (j = 0; j < b->numlevel; j++)
440 : {
441 158 : if (!(aptr->len == bptr->len && memcmp(aptr->name, bptr->name, aptr->len) == 0))
442 : break;
443 70 : aptr = LEVEL_NEXT(aptr);
444 70 : bptr = LEVEL_NEXT(bptr);
445 : }
446 :
447 116 : if (j == b->numlevel)
448 : {
449 28 : found = true;
450 28 : break;
451 : }
452 : }
453 184 : startptr = LEVEL_NEXT(startptr);
454 : }
455 :
456 34 : if (!found)
457 6 : i = -1;
458 :
459 34 : PG_FREE_IF_COPY(a, 0);
460 34 : PG_FREE_IF_COPY(b, 1);
461 34 : PG_RETURN_INT32(i);
462 : }
463 :
464 : Datum
465 0 : ltree_textadd(PG_FUNCTION_ARGS)
466 : {
467 0 : ltree *a = PG_GETARG_LTREE_P(1);
468 0 : text *b = PG_GETARG_TEXT_PP(0);
469 : char *s;
470 : ltree *r,
471 : *tmp;
472 :
473 0 : s = text_to_cstring(b);
474 :
475 0 : tmp = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
476 : PointerGetDatum(s)));
477 :
478 0 : pfree(s);
479 :
480 0 : r = ltree_concat(tmp, a);
481 :
482 0 : pfree(tmp);
483 :
484 0 : PG_FREE_IF_COPY(a, 1);
485 0 : PG_FREE_IF_COPY(b, 0);
486 0 : PG_RETURN_POINTER(r);
487 : }
488 :
489 : /*
490 : * Common code for variants of lca(), find longest common ancestor of inputs
491 : *
492 : * Returns NULL if there is no common ancestor, ie, the longest common
493 : * prefix is empty.
494 : */
495 : ltree *
496 28 : lca_inner(ltree **a, int len)
497 : {
498 : int tmp,
499 : num,
500 : i,
501 : reslen;
502 : ltree **ptr;
503 : ltree_level *l1,
504 : *l2;
505 : ltree *res;
506 :
507 28 : if (len <= 0)
508 2 : return NULL; /* no inputs? */
509 26 : if ((*a)->numlevel == 0)
510 2 : return NULL; /* any empty input means NULL result */
511 :
512 : /* num is the length of the longest common ancestor so far */
513 24 : num = (*a)->numlevel - 1;
514 :
515 : /* Compare each additional input to *a */
516 24 : ptr = a + 1;
517 46 : while (ptr - a < len)
518 : {
519 24 : if ((*ptr)->numlevel == 0)
520 2 : return NULL;
521 22 : else if ((*ptr)->numlevel == 1)
522 4 : num = 0;
523 : else
524 : {
525 18 : l1 = LTREE_FIRST(*a);
526 18 : l2 = LTREE_FIRST(*ptr);
527 18 : tmp = Min(num, (*ptr)->numlevel - 1);
528 18 : num = 0;
529 46 : for (i = 0; i < tmp; i++)
530 : {
531 42 : if (l1->len == l2->len &&
532 36 : memcmp(l1->name, l2->name, l1->len) == 0)
533 28 : num = i + 1;
534 : else
535 : break;
536 28 : l1 = LEVEL_NEXT(l1);
537 28 : l2 = LEVEL_NEXT(l2);
538 : }
539 : }
540 22 : ptr++;
541 : }
542 :
543 : /* Now compute size of result ... */
544 22 : reslen = LTREE_HDRSIZE;
545 22 : l1 = LTREE_FIRST(*a);
546 42 : for (i = 0; i < num; i++)
547 : {
548 20 : reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
549 20 : l1 = LEVEL_NEXT(l1);
550 : }
551 :
552 : /* ... and construct it by copying from *a */
553 22 : res = (ltree *) palloc0(reslen);
554 22 : SET_VARSIZE(res, reslen);
555 22 : res->numlevel = num;
556 :
557 22 : l1 = LTREE_FIRST(*a);
558 22 : l2 = LTREE_FIRST(res);
559 :
560 42 : for (i = 0; i < num; i++)
561 : {
562 20 : memcpy(l2, l1, MAXALIGN(l1->len + LEVEL_HDRSIZE));
563 20 : l1 = LEVEL_NEXT(l1);
564 20 : l2 = LEVEL_NEXT(l2);
565 : }
566 :
567 22 : return res;
568 : }
569 :
570 : Datum
571 12 : lca(PG_FUNCTION_ARGS)
572 : {
573 : int i;
574 : ltree **a,
575 : *res;
576 :
577 12 : a = (ltree **) palloc(sizeof(ltree *) * fcinfo->nargs);
578 42 : for (i = 0; i < fcinfo->nargs; i++)
579 30 : a[i] = PG_GETARG_LTREE_P(i);
580 12 : res = lca_inner(a, (int) fcinfo->nargs);
581 42 : for (i = 0; i < fcinfo->nargs; i++)
582 30 : PG_FREE_IF_COPY(a[i], i);
583 12 : pfree(a);
584 :
585 12 : if (res)
586 10 : PG_RETURN_POINTER(res);
587 : else
588 2 : PG_RETURN_NULL();
589 : }
590 :
591 : Datum
592 2 : text2ltree(PG_FUNCTION_ARGS)
593 : {
594 2 : text *in = PG_GETARG_TEXT_PP(0);
595 : char *s;
596 : ltree *out;
597 :
598 2 : s = text_to_cstring(in);
599 :
600 2 : out = (ltree *) DatumGetPointer(DirectFunctionCall1(ltree_in,
601 : PointerGetDatum(s)));
602 2 : pfree(s);
603 2 : PG_FREE_IF_COPY(in, 0);
604 2 : PG_RETURN_POINTER(out);
605 : }
606 :
607 :
608 : Datum
609 2 : ltree2text(PG_FUNCTION_ARGS)
610 : {
611 2 : ltree *in = PG_GETARG_LTREE_P(0);
612 : char *ptr;
613 : int i;
614 : ltree_level *curlevel;
615 : text *out;
616 :
617 2 : out = (text *) palloc(VARSIZE(in) + VARHDRSZ);
618 2 : ptr = VARDATA(out);
619 2 : curlevel = LTREE_FIRST(in);
620 12 : for (i = 0; i < in->numlevel; i++)
621 : {
622 10 : if (i != 0)
623 : {
624 8 : *ptr = '.';
625 8 : ptr++;
626 : }
627 10 : memcpy(ptr, curlevel->name, curlevel->len);
628 10 : ptr += curlevel->len;
629 10 : curlevel = LEVEL_NEXT(curlevel);
630 : }
631 :
632 2 : SET_VARSIZE(out, ptr - ((char *) out));
633 2 : PG_FREE_IF_COPY(in, 0);
634 :
635 2 : PG_RETURN_POINTER(out);
636 : }
637 :
638 :
639 : /*
640 : * ltreeparentsel - Selectivity of parent relationship for ltree data types.
641 : *
642 : * This function is not used anymore, if the ltree extension has been
643 : * updated to 1.2 or later.
644 : */
645 : Datum
646 0 : ltreeparentsel(PG_FUNCTION_ARGS)
647 : {
648 0 : PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
649 0 : Oid operator = PG_GETARG_OID(1);
650 0 : List *args = (List *) PG_GETARG_POINTER(2);
651 0 : int varRelid = PG_GETARG_INT32(3);
652 : double selec;
653 :
654 : /* Use generic restriction selectivity logic, with default 0.001. */
655 0 : selec = generic_restriction_selectivity(root, operator, InvalidOid,
656 : args, varRelid,
657 : 0.001);
658 :
659 0 : PG_RETURN_FLOAT8((float8) selec);
660 : }
|
