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