contrib/ltree/ltree_op.c

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