granicus.if.org Git - postgresql/blob - src/backend/access/gist/gistproc.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gistproc.c
   4  *        Support procedures for GiSTs over 2-D objects (boxes, polygons, circles).
   5  *
   6  * This gives R-tree behavior, with Guttman's poly-time split algorithm.
   7  *
   8  *
   9  * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
  10  * Portions Copyright (c) 1994, Regents of the University of California
  11  *
  12  * IDENTIFICATION
  13  *      src/backend/access/gist/gistproc.c
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include "access/gist.h"
  20 #include "access/skey.h"
  21 #include "utils/geo_decls.h"
  22
  23
  24 static bool gist_box_leaf_consistent(BOX *key, BOX *query,
  25                                                  StrategyNumber strategy);
  26 static double size_box(Datum dbox);
  27 static bool rtree_internal_consistent(BOX *key, BOX *query,
  28                                                   StrategyNumber strategy);
  29
  30
  31 /**************************************************
  32  * Box ops
  33  **************************************************/
  34
  35 static Datum
  36 rt_box_union(PG_FUNCTION_ARGS)
  37 {
  38         BOX                *a = PG_GETARG_BOX_P(0);
  39         BOX                *b = PG_GETARG_BOX_P(1);
  40         BOX                *n;
  41
  42         n = (BOX *) palloc(sizeof(BOX));
  43
  44         n->high.x = Max(a->high.x, b->high.x);
  45         n->high.y = Max(a->high.y, b->high.y);
  46         n->low.x = Min(a->low.x, b->low.x);
  47         n->low.y = Min(a->low.y, b->low.y);
  48
  49         PG_RETURN_BOX_P(n);
  50 }
  51
  52 static Datum
  53 rt_box_inter(PG_FUNCTION_ARGS)
  54 {
  55         BOX                *a = PG_GETARG_BOX_P(0);
  56         BOX                *b = PG_GETARG_BOX_P(1);
  57         BOX                *n;
  58
  59         n = (BOX *) palloc(sizeof(BOX));
  60
  61         n->high.x = Min(a->high.x, b->high.x);
  62         n->high.y = Min(a->high.y, b->high.y);
  63         n->low.x = Max(a->low.x, b->low.x);
  64         n->low.y = Max(a->low.y, b->low.y);
  65
  66         if (n->high.x < n->low.x || n->high.y < n->low.y)
  67         {
  68                 pfree(n);
  69                 /* Indicate "no intersection" by returning NULL pointer */
  70                 n = NULL;
  71         }
  72
  73         PG_RETURN_BOX_P(n);
  74 }
  75
  76 /*
  77  * The GiST Consistent method for boxes
  78  *
  79  * Should return false if for all data items x below entry,
  80  * the predicate x op query must be FALSE, where op is the oper
  81  * corresponding to strategy in the pg_amop table.
  82  */
  83 Datum
  84 gist_box_consistent(PG_FUNCTION_ARGS)
  85 {
  86         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
  87         BOX                *query = PG_GETARG_BOX_P(1);
  88         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
  89
  90         /* Oid          subtype = PG_GETARG_OID(3); */
  91         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
  92
  93         /* All cases served by this function are exact */
  94         *recheck = false;
  95
  96         if (DatumGetBoxP(entry->key) == NULL || query == NULL)
  97                 PG_RETURN_BOOL(FALSE);
  98
  99         /*
 100          * if entry is not leaf, use rtree_internal_consistent, else use
 101          * gist_box_leaf_consistent
 102          */
 103         if (GIST_LEAF(entry))
 104                 PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
 105                                                                                                 query,
 106                                                                                                 strategy));
 107         else
 108                 PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
 109                                                                                                  query,
 110                                                                                                  strategy));
 111 }
 112
 113 static void
 114 adjustBox(BOX *b, BOX *addon)
 115 {
 116         if (b->high.x < addon->high.x)
 117                 b->high.x = addon->high.x;
 118         if (b->low.x > addon->low.x)
 119                 b->low.x = addon->low.x;
 120         if (b->high.y < addon->high.y)
 121                 b->high.y = addon->high.y;
 122         if (b->low.y > addon->low.y)
 123                 b->low.y = addon->low.y;
 124 }
 125
 126 /*
 127  * The GiST Union method for boxes
 128  *
 129  * returns the minimal bounding box that encloses all the entries in entryvec
 130  */
 131 Datum
 132 gist_box_union(PG_FUNCTION_ARGS)
 133 {
 134         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 135         int                *sizep = (int *) PG_GETARG_POINTER(1);
 136         int                     numranges,
 137                                 i;
 138         BOX                *cur,
 139                            *pageunion;
 140
 141         numranges = entryvec->n;
 142         pageunion = (BOX *) palloc(sizeof(BOX));
 143         cur = DatumGetBoxP(entryvec->vector[0].key);
 144         memcpy((void *) pageunion, (void *) cur, sizeof(BOX));
 145
 146         for (i = 1; i < numranges; i++)
 147         {
 148                 cur = DatumGetBoxP(entryvec->vector[i].key);
 149                 adjustBox(pageunion, cur);
 150         }
 151         *sizep = sizeof(BOX);
 152
 153         PG_RETURN_POINTER(pageunion);
 154 }
 155
 156 /*
 157  * GiST Compress methods for boxes
 158  *
 159  * do not do anything.
 160  */
 161 Datum
 162 gist_box_compress(PG_FUNCTION_ARGS)
 163 {
 164         PG_RETURN_POINTER(PG_GETARG_POINTER(0));
 165 }
 166
 167 /*
 168  * GiST DeCompress method for boxes (also used for points, polygons
 169  * and circles)
 170  *
 171  * do not do anything --- we just use the stored box as is.
 172  */
 173 Datum
 174 gist_box_decompress(PG_FUNCTION_ARGS)
 175 {
 176         PG_RETURN_POINTER(PG_GETARG_POINTER(0));
 177 }
 178
 179 /*
 180  * The GiST Penalty method for boxes (also used for points)
 181  *
 182  * As in the R-tree paper, we use change in area as our penalty metric
 183  */
 184 Datum
 185 gist_box_penalty(PG_FUNCTION_ARGS)
 186 {
 187         GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
 188         GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 189         float      *result = (float *) PG_GETARG_POINTER(2);
 190         Datum           ud;
 191
 192         ud = DirectFunctionCall2(rt_box_union, origentry->key, newentry->key);
 193         *result = (float) (size_box(ud) - size_box(origentry->key));
 194         PG_RETURN_POINTER(result);
 195 }
 196
 197 static void
 198 chooseLR(GIST_SPLITVEC *v,
 199                  OffsetNumber *list1, int nlist1, BOX *union1,
 200                  OffsetNumber *list2, int nlist2, BOX *union2)
 201 {
 202         bool            firstToLeft = true;
 203
 204         if (v->spl_ldatum_exists || v->spl_rdatum_exists)
 205         {
 206                 if (v->spl_ldatum_exists && v->spl_rdatum_exists)
 207                 {
 208                         BOX                     LRl = *union1,
 209                                                 LRr = *union2;
 210                         BOX                     RLl = *union2,
 211                                                 RLr = *union1;
 212                         double          sizeLR,
 213                                                 sizeRL;
 214
 215                         adjustBox(&LRl, DatumGetBoxP(v->spl_ldatum));
 216                         adjustBox(&LRr, DatumGetBoxP(v->spl_rdatum));
 217                         adjustBox(&RLl, DatumGetBoxP(v->spl_ldatum));
 218                         adjustBox(&RLr, DatumGetBoxP(v->spl_rdatum));
 219
 220                         sizeLR = size_box(DirectFunctionCall2(rt_box_inter, BoxPGetDatum(&LRl), BoxPGetDatum(&LRr)));
 221                         sizeRL = size_box(DirectFunctionCall2(rt_box_inter, BoxPGetDatum(&RLl), BoxPGetDatum(&RLr)));
 222
 223                         if (sizeLR > sizeRL)
 224                                 firstToLeft = false;
 225
 226                 }
 227                 else
 228                 {
 229                         float           p1,
 230                                                 p2;
 231                         GISTENTRY       oldUnion,
 232                                                 addon;
 233
 234                         gistentryinit(oldUnion, (v->spl_ldatum_exists) ? v->spl_ldatum : v->spl_rdatum,
 235                                                   NULL, NULL, InvalidOffsetNumber, FALSE);
 236
 237                         gistentryinit(addon, BoxPGetDatum(union1), NULL, NULL, InvalidOffsetNumber, FALSE);
 238                         DirectFunctionCall3(gist_box_penalty, PointerGetDatum(&oldUnion), PointerGetDatum(&addon), PointerGetDatum(&p1));
 239                         gistentryinit(addon, BoxPGetDatum(union2), NULL, NULL, InvalidOffsetNumber, FALSE);
 240                         DirectFunctionCall3(gist_box_penalty, PointerGetDatum(&oldUnion), PointerGetDatum(&addon), PointerGetDatum(&p2));
 241
 242                         if ((v->spl_ldatum_exists && p1 > p2) || (v->spl_rdatum_exists && p1 < p2))
 243                                 firstToLeft = false;
 244                 }
 245         }
 246
 247         if (firstToLeft)
 248         {
 249                 v->spl_left = list1;
 250                 v->spl_right = list2;
 251                 v->spl_nleft = nlist1;
 252                 v->spl_nright = nlist2;
 253                 if (v->spl_ldatum_exists)
 254                         adjustBox(union1, DatumGetBoxP(v->spl_ldatum));
 255                 v->spl_ldatum = BoxPGetDatum(union1);
 256                 if (v->spl_rdatum_exists)
 257                         adjustBox(union2, DatumGetBoxP(v->spl_rdatum));
 258                 v->spl_rdatum = BoxPGetDatum(union2);
 259         }
 260         else
 261         {
 262                 v->spl_left = list2;
 263                 v->spl_right = list1;
 264                 v->spl_nleft = nlist2;
 265                 v->spl_nright = nlist1;
 266                 if (v->spl_ldatum_exists)
 267                         adjustBox(union2, DatumGetBoxP(v->spl_ldatum));
 268                 v->spl_ldatum = BoxPGetDatum(union2);
 269                 if (v->spl_rdatum_exists)
 270                         adjustBox(union1, DatumGetBoxP(v->spl_rdatum));
 271                 v->spl_rdatum = BoxPGetDatum(union1);
 272         }
 273
 274         v->spl_ldatum_exists = v->spl_rdatum_exists = false;
 275 }
 276
 277 /*
 278  * Trivial split: half of entries will be placed on one page
 279  * and another half - to another
 280  */
 281 static void
 282 fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
 283 {
 284         OffsetNumber i,
 285                                 maxoff;
 286         BOX                *unionL = NULL,
 287                            *unionR = NULL;
 288         int                     nbytes;
 289
 290         maxoff = entryvec->n - 1;
 291
 292         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 293         v->spl_left = (OffsetNumber *) palloc(nbytes);
 294         v->spl_right = (OffsetNumber *) palloc(nbytes);
 295         v->spl_nleft = v->spl_nright = 0;
 296
 297         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 298         {
 299                 BOX                *cur = DatumGetBoxP(entryvec->vector[i].key);
 300
 301                 if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
 302                 {
 303                         v->spl_left[v->spl_nleft] = i;
 304                         if (unionL == NULL)
 305                         {
 306                                 unionL = (BOX *) palloc(sizeof(BOX));
 307                                 *unionL = *cur;
 308                         }
 309                         else
 310                                 adjustBox(unionL, cur);
 311
 312                         v->spl_nleft++;
 313                 }
 314                 else
 315                 {
 316                         v->spl_right[v->spl_nright] = i;
 317                         if (unionR == NULL)
 318                         {
 319                                 unionR = (BOX *) palloc(sizeof(BOX));
 320                                 *unionR = *cur;
 321                         }
 322                         else
 323                                 adjustBox(unionR, cur);
 324
 325                         v->spl_nright++;
 326                 }
 327         }
 328
 329         if (v->spl_ldatum_exists)
 330                 adjustBox(unionL, DatumGetBoxP(v->spl_ldatum));
 331         v->spl_ldatum = BoxPGetDatum(unionL);
 332
 333         if (v->spl_rdatum_exists)
 334                 adjustBox(unionR, DatumGetBoxP(v->spl_rdatum));
 335         v->spl_rdatum = BoxPGetDatum(unionR);
 336
 337         v->spl_ldatum_exists = v->spl_rdatum_exists = false;
 338 }
 339
 340 /*
 341  * The GiST PickSplit method
 342  *
 343  * New linear algorithm, see 'New Linear Node Splitting Algorithm for R-tree',
 344  * C.H.Ang and T.C.Tan
 345  *
 346  * This is used for both boxes and points.
 347  */
 348 Datum
 349 gist_box_picksplit(PG_FUNCTION_ARGS)
 350 {
 351         GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 352         GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 353         OffsetNumber i;
 354         OffsetNumber *listL,
 355                            *listR,
 356                            *listB,
 357                            *listT;
 358         BOX                *unionL,
 359                            *unionR,
 360                            *unionB,
 361                            *unionT;
 362         int                     posL,
 363                                 posR,
 364                                 posB,
 365                                 posT;
 366         BOX                     pageunion;
 367         BOX                *cur;
 368         char            direction = ' ';
 369         bool            allisequal = true;
 370         OffsetNumber maxoff;
 371         int                     nbytes;
 372
 373         posL = posR = posB = posT = 0;
 374         maxoff = entryvec->n - 1;
 375
 376         cur = DatumGetBoxP(entryvec->vector[FirstOffsetNumber].key);
 377         memcpy((void *) &pageunion, (void *) cur, sizeof(BOX));
 378
 379         /* find MBR */
 380         for (i = OffsetNumberNext(FirstOffsetNumber); i <= maxoff; i = OffsetNumberNext(i))
 381         {
 382                 cur = DatumGetBoxP(entryvec->vector[i].key);
 383                 if (allisequal && (
 384                                                    pageunion.high.x != cur->high.x ||
 385                                                    pageunion.high.y != cur->high.y ||
 386                                                    pageunion.low.x != cur->low.x ||
 387                                                    pageunion.low.y != cur->low.y
 388                                                    ))
 389                         allisequal = false;
 390
 391                 adjustBox(&pageunion, cur);
 392         }
 393
 394         if (allisequal)
 395         {
 396                 /*
 397                  * All entries are the same
 398                  */
 399                 fallbackSplit(entryvec, v);
 400                 PG_RETURN_POINTER(v);
 401         }
 402
 403         nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 404         listL = (OffsetNumber *) palloc(nbytes);
 405         listR = (OffsetNumber *) palloc(nbytes);
 406         listB = (OffsetNumber *) palloc(nbytes);
 407         listT = (OffsetNumber *) palloc(nbytes);
 408         unionL = (BOX *) palloc(sizeof(BOX));
 409         unionR = (BOX *) palloc(sizeof(BOX));
 410         unionB = (BOX *) palloc(sizeof(BOX));
 411         unionT = (BOX *) palloc(sizeof(BOX));
 412
 413 #define ADDLIST( list, unionD, pos, num ) do { \
 414         if ( pos ) { \
 415                 if ( (unionD)->high.x < cur->high.x ) (unionD)->high.x  = cur->high.x; \
 416                 if ( (unionD)->low.x  > cur->low.x      ) (unionD)->low.x       = cur->low.x; \
 417                 if ( (unionD)->high.y < cur->high.y ) (unionD)->high.y  = cur->high.y; \
 418                 if ( (unionD)->low.y  > cur->low.y      ) (unionD)->low.y       = cur->low.y; \
 419         } else { \
 420                         memcpy( (void*)(unionD), (void*) cur, sizeof( BOX ) );  \
 421         } \
 422         (list)[pos] = num; \
 423         (pos)++; \
 424 } while(0)
 425
 426         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 427         {
 428                 cur = DatumGetBoxP(entryvec->vector[i].key);
 429                 if (cur->low.x - pageunion.low.x < pageunion.high.x - cur->high.x)
 430                         ADDLIST(listL, unionL, posL, i);
 431                 else
 432                         ADDLIST(listR, unionR, posR, i);
 433                 if (cur->low.y - pageunion.low.y < pageunion.high.y - cur->high.y)
 434                         ADDLIST(listB, unionB, posB, i);
 435                 else
 436                         ADDLIST(listT, unionT, posT, i);
 437         }
 438
 439 #define LIMIT_RATIO 0.1
 440 #define _IS_BADRATIO(x,y)       ( (y) == 0 || (float)(x)/(float)(y) < LIMIT_RATIO )
 441 #define IS_BADRATIO(x,y) ( _IS_BADRATIO((x),(y)) || _IS_BADRATIO((y),(x)) )
 442         /* bad disposition, try to split by centers of boxes  */
 443         if (IS_BADRATIO(posR, posL) && IS_BADRATIO(posT, posB))
 444         {
 445                 double          avgCenterX = 0.0,
 446                                         avgCenterY = 0.0;
 447                 double          CenterX,
 448                                         CenterY;
 449
 450                 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 451                 {
 452                         cur = DatumGetBoxP(entryvec->vector[i].key);
 453                         avgCenterX += ((double) cur->high.x + (double) cur->low.x) / 2.0;
 454                         avgCenterY += ((double) cur->high.y + (double) cur->low.y) / 2.0;
 455                 }
 456
 457                 avgCenterX /= maxoff;
 458                 avgCenterY /= maxoff;
 459
 460                 posL = posR = posB = posT = 0;
 461                 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 462                 {
 463                         cur = DatumGetBoxP(entryvec->vector[i].key);
 464
 465                         CenterX = ((double) cur->high.x + (double) cur->low.x) / 2.0;
 466                         CenterY = ((double) cur->high.y + (double) cur->low.y) / 2.0;
 467
 468                         if (CenterX < avgCenterX)
 469                                 ADDLIST(listL, unionL, posL, i);
 470                         else if (CenterX == avgCenterX)
 471                         {
 472                                 if (posL > posR)
 473                                         ADDLIST(listR, unionR, posR, i);
 474                                 else
 475                                         ADDLIST(listL, unionL, posL, i);
 476                         }
 477                         else
 478                                 ADDLIST(listR, unionR, posR, i);
 479
 480                         if (CenterY < avgCenterY)
 481                                 ADDLIST(listB, unionB, posB, i);
 482                         else if (CenterY == avgCenterY)
 483                         {
 484                                 if (posB > posT)
 485                                         ADDLIST(listT, unionT, posT, i);
 486                                 else
 487                                         ADDLIST(listB, unionB, posB, i);
 488                         }
 489                         else
 490                                 ADDLIST(listT, unionT, posT, i);
 491                 }
 492
 493                 if (IS_BADRATIO(posR, posL) && IS_BADRATIO(posT, posB))
 494                 {
 495                         fallbackSplit(entryvec, v);
 496                         PG_RETURN_POINTER(v);
 497                 }
 498         }
 499
 500         /* which split more optimal? */
 501         if (Max(posL, posR) < Max(posB, posT))
 502                 direction = 'x';
 503         else if (Max(posL, posR) > Max(posB, posT))
 504                 direction = 'y';
 505         else
 506         {
 507                 Datum           interLR = DirectFunctionCall2(rt_box_inter,
 508                                                                                                   BoxPGetDatum(unionL),
 509                                                                                                   BoxPGetDatum(unionR));
 510                 Datum           interBT = DirectFunctionCall2(rt_box_inter,
 511                                                                                                   BoxPGetDatum(unionB),
 512                                                                                                   BoxPGetDatum(unionT));
 513                 double          sizeLR,
 514                                         sizeBT;
 515
 516                 sizeLR = size_box(interLR);
 517                 sizeBT = size_box(interBT);
 518
 519                 if (sizeLR < sizeBT)
 520                         direction = 'x';
 521                 else
 522                         direction = 'y';
 523         }
 524
 525         if (direction == 'x')
 526                 chooseLR(v,
 527                                  listL, posL, unionL,
 528                                  listR, posR, unionR);
 529         else
 530                 chooseLR(v,
 531                                  listB, posB, unionB,
 532                                  listT, posT, unionT);
 533
 534         PG_RETURN_POINTER(v);
 535 }
 536
 537 /*
 538  * Equality method
 539  *
 540  * This is used for both boxes and points.
 541  */
 542 Datum
 543 gist_box_same(PG_FUNCTION_ARGS)
 544 {
 545         BOX                *b1 = PG_GETARG_BOX_P(0);
 546         BOX                *b2 = PG_GETARG_BOX_P(1);
 547         bool       *result = (bool *) PG_GETARG_POINTER(2);
 548
 549         if (b1 && b2)
 550                 *result = DatumGetBool(DirectFunctionCall2(box_same,
 551                                                                                                    PointerGetDatum(b1),
 552                                                                                                    PointerGetDatum(b2)));
 553         else
 554                 *result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE;
 555         PG_RETURN_POINTER(result);
 556 }
 557
 558 /*
 559  * Leaf-level consistency for boxes: just apply the query operator
 560  */
 561 static bool
 562 gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
 563 {
 564         bool            retval;
 565
 566         switch (strategy)
 567         {
 568                 case RTLeftStrategyNumber:
 569                         retval = DatumGetBool(DirectFunctionCall2(box_left,
 570                                                                                                           PointerGetDatum(key),
 571                                                                                                         PointerGetDatum(query)));
 572                         break;
 573                 case RTOverLeftStrategyNumber:
 574                         retval = DatumGetBool(DirectFunctionCall2(box_overleft,
 575                                                                                                           PointerGetDatum(key),
 576                                                                                                         PointerGetDatum(query)));
 577                         break;
 578                 case RTOverlapStrategyNumber:
 579                         retval = DatumGetBool(DirectFunctionCall2(box_overlap,
 580                                                                                                           PointerGetDatum(key),
 581                                                                                                         PointerGetDatum(query)));
 582                         break;
 583                 case RTOverRightStrategyNumber:
 584                         retval = DatumGetBool(DirectFunctionCall2(box_overright,
 585                                                                                                           PointerGetDatum(key),
 586                                                                                                         PointerGetDatum(query)));
 587                         break;
 588                 case RTRightStrategyNumber:
 589                         retval = DatumGetBool(DirectFunctionCall2(box_right,
 590                                                                                                           PointerGetDatum(key),
 591                                                                                                         PointerGetDatum(query)));
 592                         break;
 593                 case RTSameStrategyNumber:
 594                         retval = DatumGetBool(DirectFunctionCall2(box_same,
 595                                                                                                           PointerGetDatum(key),
 596                                                                                                         PointerGetDatum(query)));
 597                         break;
 598                 case RTContainsStrategyNumber:
 599                 case RTOldContainsStrategyNumber:
 600                         retval = DatumGetBool(DirectFunctionCall2(box_contain,
 601                                                                                                           PointerGetDatum(key),
 602                                                                                                         PointerGetDatum(query)));
 603                         break;
 604                 case RTContainedByStrategyNumber:
 605                 case RTOldContainedByStrategyNumber:
 606                         retval = DatumGetBool(DirectFunctionCall2(box_contained,
 607                                                                                                           PointerGetDatum(key),
 608                                                                                                         PointerGetDatum(query)));
 609                         break;
 610                 case RTOverBelowStrategyNumber:
 611                         retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
 612                                                                                                           PointerGetDatum(key),
 613                                                                                                         PointerGetDatum(query)));
 614                         break;
 615                 case RTBelowStrategyNumber:
 616                         retval = DatumGetBool(DirectFunctionCall2(box_below,
 617                                                                                                           PointerGetDatum(key),
 618                                                                                                         PointerGetDatum(query)));
 619                         break;
 620                 case RTAboveStrategyNumber:
 621                         retval = DatumGetBool(DirectFunctionCall2(box_above,
 622                                                                                                           PointerGetDatum(key),
 623                                                                                                         PointerGetDatum(query)));
 624                         break;
 625                 case RTOverAboveStrategyNumber:
 626                         retval = DatumGetBool(DirectFunctionCall2(box_overabove,
 627                                                                                                           PointerGetDatum(key),
 628                                                                                                         PointerGetDatum(query)));
 629                         break;
 630                 default:
 631                         retval = FALSE;
 632         }
 633         return retval;
 634 }
 635
 636 static double
 637 size_box(Datum dbox)
 638 {
 639         BOX                *box = DatumGetBoxP(dbox);
 640
 641         if (box == NULL || box->high.x <= box->low.x || box->high.y <= box->low.y)
 642                 return 0.0;
 643         return (box->high.x - box->low.x) * (box->high.y - box->low.y);
 644 }
 645
 646 /*****************************************
 647  * Common rtree functions (for boxes, polygons, and circles)
 648  *****************************************/
 649
 650 /*
 651  * Internal-page consistency for all these types
 652  *
 653  * We can use the same function since all types use bounding boxes as the
 654  * internal-page representation.
 655  */
 656 static bool
 657 rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
 658 {
 659         bool            retval;
 660
 661         switch (strategy)
 662         {
 663                 case RTLeftStrategyNumber:
 664                         retval = !DatumGetBool(DirectFunctionCall2(box_overright,
 665                                                                                                            PointerGetDatum(key),
 666                                                                                                         PointerGetDatum(query)));
 667                         break;
 668                 case RTOverLeftStrategyNumber:
 669                         retval = !DatumGetBool(DirectFunctionCall2(box_right,
 670                                                                                                            PointerGetDatum(key),
 671                                                                                                         PointerGetDatum(query)));
 672                         break;
 673                 case RTOverlapStrategyNumber:
 674                         retval = DatumGetBool(DirectFunctionCall2(box_overlap,
 675                                                                                                           PointerGetDatum(key),
 676                                                                                                         PointerGetDatum(query)));
 677                         break;
 678                 case RTOverRightStrategyNumber:
 679                         retval = !DatumGetBool(DirectFunctionCall2(box_left,
 680                                                                                                            PointerGetDatum(key),
 681                                                                                                         PointerGetDatum(query)));
 682                         break;
 683                 case RTRightStrategyNumber:
 684                         retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
 685                                                                                                            PointerGetDatum(key),
 686                                                                                                         PointerGetDatum(query)));
 687                         break;
 688                 case RTSameStrategyNumber:
 689                 case RTContainsStrategyNumber:
 690                 case RTOldContainsStrategyNumber:
 691                         retval = DatumGetBool(DirectFunctionCall2(box_contain,
 692                                                                                                           PointerGetDatum(key),
 693                                                                                                         PointerGetDatum(query)));
 694                         break;
 695                 case RTContainedByStrategyNumber:
 696                 case RTOldContainedByStrategyNumber:
 697                         retval = DatumGetBool(DirectFunctionCall2(box_overlap,
 698                                                                                                           PointerGetDatum(key),
 699                                                                                                         PointerGetDatum(query)));
 700                         break;
 701                 case RTOverBelowStrategyNumber:
 702                         retval = !DatumGetBool(DirectFunctionCall2(box_above,
 703                                                                                                            PointerGetDatum(key),
 704                                                                                                         PointerGetDatum(query)));
 705                         break;
 706                 case RTBelowStrategyNumber:
 707                         retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
 708                                                                                                            PointerGetDatum(key),
 709                                                                                                         PointerGetDatum(query)));
 710                         break;
 711                 case RTAboveStrategyNumber:
 712                         retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
 713                                                                                                            PointerGetDatum(key),
 714                                                                                                         PointerGetDatum(query)));
 715                         break;
 716                 case RTOverAboveStrategyNumber:
 717                         retval = !DatumGetBool(DirectFunctionCall2(box_below,
 718                                                                                                            PointerGetDatum(key),
 719                                                                                                         PointerGetDatum(query)));
 720                         break;
 721                 default:
 722                         retval = FALSE;
 723         }
 724         return retval;
 725 }
 726
 727 /**************************************************
 728  * Polygon ops
 729  **************************************************/
 730
 731 /*
 732  * GiST compress for polygons: represent a polygon by its bounding box
 733  */
 734 Datum
 735 gist_poly_compress(PG_FUNCTION_ARGS)
 736 {
 737         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 738         GISTENTRY  *retval;
 739
 740         if (entry->leafkey)
 741         {
 742                 retval = palloc(sizeof(GISTENTRY));
 743                 if (DatumGetPointer(entry->key) != NULL)
 744                 {
 745                         POLYGON    *in = DatumGetPolygonP(entry->key);
 746                         BOX                *r;
 747
 748                         r = (BOX *) palloc(sizeof(BOX));
 749                         memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
 750                         gistentryinit(*retval, PointerGetDatum(r),
 751                                                   entry->rel, entry->page,
 752                                                   entry->offset, FALSE);
 753
 754                 }
 755                 else
 756                 {
 757                         gistentryinit(*retval, (Datum) 0,
 758                                                   entry->rel, entry->page,
 759                                                   entry->offset, FALSE);
 760                 }
 761         }
 762         else
 763                 retval = entry;
 764         PG_RETURN_POINTER(retval);
 765 }
 766
 767 /*
 768  * The GiST Consistent method for polygons
 769  */
 770 Datum
 771 gist_poly_consistent(PG_FUNCTION_ARGS)
 772 {
 773         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 774         POLYGON    *query = PG_GETARG_POLYGON_P(1);
 775         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 776
 777         /* Oid          subtype = PG_GETARG_OID(3); */
 778         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 779         bool            result;
 780
 781         /* All cases served by this function are inexact */
 782         *recheck = true;
 783
 784         if (DatumGetBoxP(entry->key) == NULL || query == NULL)
 785                 PG_RETURN_BOOL(FALSE);
 786
 787         /*
 788          * Since the operators require recheck anyway, we can just use
 789          * rtree_internal_consistent even at leaf nodes.  (This works in part
 790          * because the index entries are bounding boxes not polygons.)
 791          */
 792         result = rtree_internal_consistent(DatumGetBoxP(entry->key),
 793                                                                            &(query->boundbox), strategy);
 794
 795         /* Avoid memory leak if supplied poly is toasted */
 796         PG_FREE_IF_COPY(query, 1);
 797
 798         PG_RETURN_BOOL(result);
 799 }
 800
 801 /**************************************************
 802  * Circle ops
 803  **************************************************/
 804
 805 /*
 806  * GiST compress for circles: represent a circle by its bounding box
 807  */
 808 Datum
 809 gist_circle_compress(PG_FUNCTION_ARGS)
 810 {
 811         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 812         GISTENTRY  *retval;
 813
 814         if (entry->leafkey)
 815         {
 816                 retval = palloc(sizeof(GISTENTRY));
 817                 if (DatumGetCircleP(entry->key) != NULL)
 818                 {
 819                         CIRCLE     *in = DatumGetCircleP(entry->key);
 820                         BOX                *r;
 821
 822                         r = (BOX *) palloc(sizeof(BOX));
 823                         r->high.x = in->center.x + in->radius;
 824                         r->low.x = in->center.x - in->radius;
 825                         r->high.y = in->center.y + in->radius;
 826                         r->low.y = in->center.y - in->radius;
 827                         gistentryinit(*retval, PointerGetDatum(r),
 828                                                   entry->rel, entry->page,
 829                                                   entry->offset, FALSE);
 830
 831                 }
 832                 else
 833                 {
 834                         gistentryinit(*retval, (Datum) 0,
 835                                                   entry->rel, entry->page,
 836                                                   entry->offset, FALSE);
 837                 }
 838         }
 839         else
 840                 retval = entry;
 841         PG_RETURN_POINTER(retval);
 842 }
 843
 844 /*
 845  * The GiST Consistent method for circles
 846  */
 847 Datum
 848 gist_circle_consistent(PG_FUNCTION_ARGS)
 849 {
 850         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 851         CIRCLE     *query = PG_GETARG_CIRCLE_P(1);
 852         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 853
 854         /* Oid          subtype = PG_GETARG_OID(3); */
 855         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 856         BOX                     bbox;
 857         bool            result;
 858
 859         /* All cases served by this function are inexact */
 860         *recheck = true;
 861
 862         if (DatumGetBoxP(entry->key) == NULL || query == NULL)
 863                 PG_RETURN_BOOL(FALSE);
 864
 865         /*
 866          * Since the operators require recheck anyway, we can just use
 867          * rtree_internal_consistent even at leaf nodes.  (This works in part
 868          * because the index entries are bounding boxes not circles.)
 869          */
 870         bbox.high.x = query->center.x + query->radius;
 871         bbox.low.x = query->center.x - query->radius;
 872         bbox.high.y = query->center.y + query->radius;
 873         bbox.low.y = query->center.y - query->radius;
 874
 875         result = rtree_internal_consistent(DatumGetBoxP(entry->key),
 876                                                                            &bbox, strategy);
 877
 878         PG_RETURN_BOOL(result);
 879 }
 880
 881 /**************************************************
 882  * Point ops
 883  **************************************************/
 884
 885 Datum
 886 gist_point_compress(PG_FUNCTION_ARGS)
 887 {
 888         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 889
 890         if (entry->leafkey)                     /* Point, actually */
 891         {
 892                 BOX                *box = palloc(sizeof(BOX));
 893                 Point      *point = DatumGetPointP(entry->key);
 894                 GISTENTRY  *retval = palloc(sizeof(GISTENTRY));
 895
 896                 box->high = box->low = *point;
 897
 898                 gistentryinit(*retval, BoxPGetDatum(box),
 899                                           entry->rel, entry->page, entry->offset, FALSE);
 900
 901                 PG_RETURN_POINTER(retval);
 902         }
 903
 904         PG_RETURN_POINTER(entry);
 905 }
 906
 907 #define point_point_distance(p1,p2)     \
 908         DatumGetFloat8(DirectFunctionCall2(point_distance, \
 909                                                                            PointPGetDatum(p1), PointPGetDatum(p2)))
 910
 911 static double
 912 computeDistance(bool isLeaf, BOX *box, Point *point)
 913 {
 914         double          result = 0.0;
 915
 916         if (isLeaf)
 917         {
 918                 /* simple point to point distance */
 919                 result = point_point_distance(point, &box->low);
 920         }
 921         else if (point->x <= box->high.x && point->x >= box->low.x &&
 922                          point->y <= box->high.y && point->y >= box->low.y)
 923         {
 924                 /* point inside the box */
 925                 result = 0.0;
 926         }
 927         else if (point->x <= box->high.x && point->x >= box->low.x)
 928         {
 929                 /* point is over or below box */
 930                 Assert(box->low.y <= box->high.y);
 931                 if (point->y > box->high.y)
 932                         result = point->y - box->high.y;
 933                 else if (point->y < box->low.y)
 934                         result = box->low.y - point->y;
 935                 else
 936                         elog(ERROR, "inconsistent point values");
 937         }
 938         else if (point->y <= box->high.y && point->y >= box->low.y)
 939         {
 940                 /* point is to left or right of box */
 941                 Assert(box->low.x <= box->high.x);
 942                 if (point->x > box->high.x)
 943                         result = point->x - box->high.x;
 944                 else if (point->x < box->low.x)
 945                         result = box->low.x - point->x;
 946                 else
 947                         elog(ERROR, "inconsistent point values");
 948         }
 949         else
 950         {
 951                 /* closest point will be a vertex */
 952                 Point   p;
 953                 double  subresult;
 954
 955                 result = point_point_distance(point, &box->low);
 956
 957                 subresult = point_point_distance(point, &box->high);
 958                 if (result > subresult)
 959                         result = subresult;
 960
 961                 p.x = box->low.x;
 962                 p.y = box->high.y;
 963                 subresult = point_point_distance(point, &p);
 964                 if (result > subresult)
 965                         result = subresult;
 966
 967                 p.x = box->high.x;
 968                 p.y = box->low.y;
 969                 subresult = point_point_distance(point, &p);
 970                 if (result > subresult)
 971                         result = subresult;
 972         }
 973
 974         return result;
 975 }
 976
 977 static bool
 978 gist_point_consistent_internal(StrategyNumber strategy,
 979                                                            bool isLeaf, BOX *key, Point *query)
 980 {
 981         bool            result = false;
 982
 983         switch (strategy)
 984         {
 985                 case RTLeftStrategyNumber:
 986                         result = FPlt(key->low.x, query->x);
 987                         break;
 988                 case RTRightStrategyNumber:
 989                         result = FPgt(key->high.x, query->x);
 990                         break;
 991                 case RTAboveStrategyNumber:
 992                         result = FPgt(key->high.y, query->y);
 993                         break;
 994                 case RTBelowStrategyNumber:
 995                         result = FPlt(key->low.y, query->y);
 996                         break;
 997                 case RTSameStrategyNumber:
 998                         if (isLeaf)
 999                         {
1000                                 result = FPeq(key->low.x, query->x)
1001                                         && FPeq(key->low.y, query->y);
1002                         }
1003                         else
1004                         {
1005                                 result = (query->x <= key->high.x && query->x >= key->low.x &&
1006                                                   query->y <= key->high.y && query->y >= key->low.y);
1007                         }
1008                         break;
1009                 default:
1010                         elog(ERROR, "unknown strategy number: %d", strategy);
1011         }
1012
1013         return result;
1014 }
1015
1016 #define GeoStrategyNumberOffset         20
1017 #define PointStrategyNumberGroup        0
1018 #define BoxStrategyNumberGroup          1
1019 #define PolygonStrategyNumberGroup      2
1020 #define CircleStrategyNumberGroup       3
1021
1022 Datum
1023 gist_point_consistent(PG_FUNCTION_ARGS)
1024 {
1025         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1026         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1027         bool       *recheck = (bool *) PG_GETARG_POINTER(4);
1028         bool            result;
1029         StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1030
1031         switch (strategyGroup)
1032         {
1033                 case PointStrategyNumberGroup:
1034                         result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset,
1035                                                                                                         GIST_LEAF(entry),
1036                                                                                                         DatumGetBoxP(entry->key),
1037                                                                                                         PG_GETARG_POINT_P(1));
1038                         *recheck = false;
1039                         break;
1040                 case BoxStrategyNumberGroup:
1041                         result = DatumGetBool(DirectFunctionCall5(
1042                                                                                                           gist_box_consistent,
1043                                                                                                           PointerGetDatum(entry),
1044                                                                                                           PG_GETARG_DATUM(1),
1045                                                                           Int16GetDatum(RTOverlapStrategyNumber),
1046                                                                                            0, PointerGetDatum(recheck)));
1047                         break;
1048                 case PolygonStrategyNumberGroup:
1049                         {
1050                                 POLYGON    *query = PG_GETARG_POLYGON_P(1);
1051
1052                                 result = DatumGetBool(DirectFunctionCall5(
1053                                                                                                                 gist_poly_consistent,
1054                                                                                                           PointerGetDatum(entry),
1055                                                                                                          PolygonPGetDatum(query),
1056                                                                           Int16GetDatum(RTOverlapStrategyNumber),
1057                                                                                            0, PointerGetDatum(recheck)));
1058
1059                                 if (GIST_LEAF(entry) && result)
1060                                 {
1061                                         /*
1062                                          * We are on leaf page and quick check shows overlapping
1063                                          * of polygon's bounding box and point
1064                                          */
1065                                         BOX                *box = DatumGetBoxP(entry->key);
1066
1067                                         Assert(box->high.x == box->low.x
1068                                                    && box->high.y == box->low.y);
1069                                         result = DatumGetBool(DirectFunctionCall2(
1070                                                                                                                           poly_contain_pt,
1071                                                                                                          PolygonPGetDatum(query),
1072                                                                                                 PointPGetDatum(&box->high)));
1073                                         *recheck = false;
1074                                 }
1075                         }
1076                         break;
1077                 case CircleStrategyNumberGroup:
1078                         {
1079                                 CIRCLE     *query = PG_GETARG_CIRCLE_P(1);
1080
1081                                 result = DatumGetBool(DirectFunctionCall5(
1082                                                                                                           gist_circle_consistent,
1083                                                                                                           PointerGetDatum(entry),
1084                                                                                                           CirclePGetDatum(query),
1085                                                                           Int16GetDatum(RTOverlapStrategyNumber),
1086                                                                                            0, PointerGetDatum(recheck)));
1087
1088                                 if (GIST_LEAF(entry) && result)
1089                                 {
1090                                         /*
1091                                          * We are on leaf page and quick check shows overlapping
1092                                          * of polygon's bounding box and point
1093                                          */
1094                                         BOX                *box = DatumGetBoxP(entry->key);
1095
1096                                         Assert(box->high.x == box->low.x
1097                                                    && box->high.y == box->low.y);
1098                                         result = DatumGetBool(DirectFunctionCall2(
1099                                                                                                                    circle_contain_pt,
1100                                                                                                           CirclePGetDatum(query),
1101                                                                                                 PointPGetDatum(&box->high)));
1102                                         *recheck = false;
1103                                 }
1104                         }
1105                         break;
1106                 default:
1107                         elog(ERROR, "unknown strategy number: %d", strategy);
1108                         result = false;         /* keep compiler quiet */
1109         }
1110
1111         PG_RETURN_BOOL(result);
1112 }
1113
1114 Datum
1115 gist_point_distance(PG_FUNCTION_ARGS)
1116 {
1117         GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
1118         StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1119         double          distance;
1120         StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
1121
1122         switch (strategyGroup)
1123         {
1124                 case PointStrategyNumberGroup:
1125                         distance = computeDistance(GIST_LEAF(entry),
1126                                                                            DatumGetBoxP(entry->key),
1127                                                                            PG_GETARG_POINT_P(1));
1128                         break;
1129                 default:
1130                         elog(ERROR, "unknown strategy number: %d", strategy);
1131                         distance = 0.0;         /* keep compiler quiet */
1132         }
1133
1134         PG_RETURN_FLOAT8(distance);
1135 }