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