|

# gistproc.c

Go to the documentation of this file.
```00001 /*-------------------------------------------------------------------------
00002  *
00003  * gistproc.c
00004  *    Support procedures for GiSTs over 2-D objects (boxes, polygons, circles,
00005  *    points).
00006  *
00007  * This gives R-tree behavior, with Guttman's poly-time split algorithm.
00008  *
00009  *
00010  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00011  * Portions Copyright (c) 1994, Regents of the University of California
00012  *
00013  * IDENTIFICATION
00014  *  src/backend/access/gist/gistproc.c
00015  *
00016  *-------------------------------------------------------------------------
00017  */
00018 #include "postgres.h"
00019
00020 #include "access/gist.h"
00021 #include "access/skey.h"
00022 #include "utils/geo_decls.h"
00023
00024
00025 static bool gist_box_leaf_consistent(BOX *key, BOX *query,
00026                          StrategyNumber strategy);
00027 static double size_box(BOX *box);
00028 static bool rtree_internal_consistent(BOX *key, BOX *query,
00029                           StrategyNumber strategy);
00030
00031 /* Minimum accepted ratio of split */
00032 #define LIMIT_RATIO 0.3
00033
00034
00035 /**************************************************
00036  * Box ops
00037  **************************************************/
00038
00039 /*
00040  * Calculates union of two boxes, a and b. The result is stored in *n.
00041  */
00042 static void
00043 rt_box_union(BOX *n, BOX *a, BOX *b)
00044 {
00045     n->high.x = Max(a->high.x, b->high.x);
00046     n->high.y = Max(a->high.y, b->high.y);
00047     n->low.x = Min(a->low.x, b->low.x);
00048     n->low.y = Min(a->low.y, b->low.y);
00049 }
00050
00051 /*
00052  * The GiST Consistent method for boxes
00053  *
00054  * Should return false if for all data items x below entry,
00055  * the predicate x op query must be FALSE, where op is the oper
00056  * corresponding to strategy in the pg_amop table.
00057  */
00058 Datum
00059 gist_box_consistent(PG_FUNCTION_ARGS)
00060 {
00061     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
00062     BOX        *query = PG_GETARG_BOX_P(1);
00063     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
00064
00065     /* Oid      subtype = PG_GETARG_OID(3); */
00066     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
00067
00068     /* All cases served by this function are exact */
00069     *recheck = false;
00070
00071     if (DatumGetBoxP(entry->key) == NULL || query == NULL)
00072         PG_RETURN_BOOL(FALSE);
00073
00074     /*
00075      * if entry is not leaf, use rtree_internal_consistent, else use
00076      * gist_box_leaf_consistent
00077      */
00078     if (GIST_LEAF(entry))
00079         PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key),
00080                                                 query,
00081                                                 strategy));
00082     else
00083         PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key),
00084                                                  query,
00085                                                  strategy));
00086 }
00087
00088 static void
00090 {
00099 }
00100
00101 /*
00102  * The GiST Union method for boxes
00103  *
00104  * returns the minimal bounding box that encloses all the entries in entryvec
00105  */
00106 Datum
00107 gist_box_union(PG_FUNCTION_ARGS)
00108 {
00109     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
00110     int        *sizep = (int *) PG_GETARG_POINTER(1);
00111     int         numranges,
00112                 i;
00113     BOX        *cur,
00114                *pageunion;
00115
00116     numranges = entryvec->n;
00117     pageunion = (BOX *) palloc(sizeof(BOX));
00118     cur = DatumGetBoxP(entryvec->vector[0].key);
00119     memcpy((void *) pageunion, (void *) cur, sizeof(BOX));
00120
00121     for (i = 1; i < numranges; i++)
00122     {
00123         cur = DatumGetBoxP(entryvec->vector[i].key);
00125     }
00126     *sizep = sizeof(BOX);
00127
00128     PG_RETURN_POINTER(pageunion);
00129 }
00130
00131 /*
00132  * GiST Compress methods for boxes
00133  *
00134  * do not do anything.
00135  */
00136 Datum
00137 gist_box_compress(PG_FUNCTION_ARGS)
00138 {
00139     PG_RETURN_POINTER(PG_GETARG_POINTER(0));
00140 }
00141
00142 /*
00143  * GiST DeCompress method for boxes (also used for points, polygons
00144  * and circles)
00145  *
00146  * do not do anything --- we just use the stored box as is.
00147  */
00148 Datum
00149 gist_box_decompress(PG_FUNCTION_ARGS)
00150 {
00151     PG_RETURN_POINTER(PG_GETARG_POINTER(0));
00152 }
00153
00154 /*
00155  * The GiST Penalty method for boxes (also used for points)
00156  *
00157  * As in the R-tree paper, we use change in area as our penalty metric
00158  */
00159 Datum
00160 gist_box_penalty(PG_FUNCTION_ARGS)
00161 {
00162     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
00163     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
00164     float      *result = (float *) PG_GETARG_POINTER(2);
00165     BOX        *origbox = DatumGetBoxP(origentry->key);
00166     BOX        *newbox = DatumGetBoxP(newentry->key);
00167     BOX         unionbox;
00168
00169     rt_box_union(&unionbox, origbox, newbox);
00170     *result = (float) (size_box(&unionbox) - size_box(origbox));
00171     PG_RETURN_POINTER(result);
00172 }
00173
00174 /*
00175  * Trivial split: half of entries will be placed on one page
00176  * and another half - to another
00177  */
00178 static void
00179 fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
00180 {
00181     OffsetNumber i,
00182                 maxoff;
00183     BOX        *unionL = NULL,
00184                *unionR = NULL;
00185     int         nbytes;
00186
00187     maxoff = entryvec->n - 1;
00188
00189     nbytes = (maxoff + 2) * sizeof(OffsetNumber);
00190     v->spl_left = (OffsetNumber *) palloc(nbytes);
00191     v->spl_right = (OffsetNumber *) palloc(nbytes);
00192     v->spl_nleft = v->spl_nright = 0;
00193
00194     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
00195     {
00196         BOX        *cur = DatumGetBoxP(entryvec->vector[i].key);
00197
00198         if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
00199         {
00200             v->spl_left[v->spl_nleft] = i;
00201             if (unionL == NULL)
00202             {
00203                 unionL = (BOX *) palloc(sizeof(BOX));
00204                 *unionL = *cur;
00205             }
00206             else
00208
00209             v->spl_nleft++;
00210         }
00211         else
00212         {
00213             v->spl_right[v->spl_nright] = i;
00214             if (unionR == NULL)
00215             {
00216                 unionR = (BOX *) palloc(sizeof(BOX));
00217                 *unionR = *cur;
00218             }
00219             else
00221
00222             v->spl_nright++;
00223         }
00224     }
00225
00226     v->spl_ldatum = BoxPGetDatum(unionL);
00227     v->spl_rdatum = BoxPGetDatum(unionR);
00228 }
00229
00230 /*
00231  * Represents information about an entry that can be placed to either group
00232  * without affecting overlap over selected axis ("common entry").
00233  */
00234 typedef struct
00235 {
00236     /* Index of entry in the initial array */
00237     int         index;
00238     /* Delta between penalties of entry insertion into different groups */
00239     double      delta;
00240 } CommonEntry;
00241
00242 /*
00243  * Context for g_box_consider_split. Contains information about currently
00244  * selected split and some general information.
00245  */
00246 typedef struct
00247 {
00248     int         entriesCount;   /* total number of entries being split */
00249     BOX         boundingBox;    /* minimum bounding box across all entries */
00250
00251     /* Information about currently selected split follows */
00252
00253     bool        first;          /* true if no split was selected yet */
00254
00255     double      leftUpper;      /* upper bound of left interval */
00256     double      rightLower;     /* lower bound of right interval */
00257
00258     float4      ratio;
00259     float4      overlap;
00260     int         dim;            /* axis of this split */
00261     double      range;          /* width of general MBR projection to the
00262                                  * selected axis */
00263 } ConsiderSplitContext;
00264
00265 /*
00266  * Interval represents projection of box to axis.
00267  */
00268 typedef struct
00269 {
00270     double      lower,
00271                 upper;
00272 } SplitInterval;
00273
00274 /*
00275  * Interval comparison function by lower bound of the interval;
00276  */
00277 static int
00278 interval_cmp_lower(const void *i1, const void *i2)
00279 {
00280     double      lower1 = ((const SplitInterval *) i1)->lower,
00281                 lower2 = ((const SplitInterval *) i2)->lower;
00282
00283     if (lower1 < lower2)
00284         return -1;
00285     else if (lower1 > lower2)
00286         return 1;
00287     else
00288         return 0;
00289 }
00290
00291 /*
00292  * Interval comparison function by upper bound of the interval;
00293  */
00294 static int
00295 interval_cmp_upper(const void *i1, const void *i2)
00296 {
00297     double      upper1 = ((const SplitInterval *) i1)->upper,
00298                 upper2 = ((const SplitInterval *) i2)->upper;
00299
00300     if (upper1 < upper2)
00301         return -1;
00302     else if (upper1 > upper2)
00303         return 1;
00304     else
00305         return 0;
00306 }
00307
00308 /*
00309  * Replace negative value with zero.
00310  */
00311 static inline float
00312 non_negative(float val)
00313 {
00314     if (val >= 0.0f)
00315         return val;
00316     else
00317         return 0.0f;
00318 }
00319
00320 /*
00321  * Consider replacement of currently selected split with the better one.
00322  */
00323 static inline void
00324 g_box_consider_split(ConsiderSplitContext *context, int dimNum,
00325                      double rightLower, int minLeftCount,
00326                      double leftUpper, int maxLeftCount)
00327 {
00328     int         leftCount,
00329                 rightCount;
00330     float4      ratio,
00331                 overlap;
00332     double      range;
00333
00334     /*
00335      * Calculate entries distribution ratio assuming most uniform distribution
00336      * of common entries.
00337      */
00338     if (minLeftCount >= (context->entriesCount + 1) / 2)
00339     {
00340         leftCount = minLeftCount;
00341     }
00342     else
00343     {
00344         if (maxLeftCount <= context->entriesCount / 2)
00345             leftCount = maxLeftCount;
00346         else
00347             leftCount = context->entriesCount / 2;
00348     }
00349     rightCount = context->entriesCount - leftCount;
00350
00351     /*
00352      * Ratio of split - quotient between size of lesser group and total
00353      * entries count.
00354      */
00355     ratio = ((float4) Min(leftCount, rightCount)) /
00356         ((float4) context->entriesCount);
00357
00358     if (ratio > LIMIT_RATIO)
00359     {
00360         bool        selectthis = false;
00361
00362         /*
00363          * The ratio is acceptable, so compare current split with previously
00364          * selected one. Between splits of one dimension we search for minimal
00365          * overlap (allowing negative values) and minimal ration (between same
00366          * overlaps. We switch dimension if find less overlap (non-negative)
00367          * or less range with same overlap.
00368          */
00369         if (dimNum == 0)
00370             range = context->boundingBox.high.x - context->boundingBox.low.x;
00371         else
00372             range = context->boundingBox.high.y - context->boundingBox.low.y;
00373
00374         overlap = (leftUpper - rightLower) / range;
00375
00376         /* If there is no previous selection, select this */
00377         if (context->first)
00378             selectthis = true;
00379         else if (context->dim == dimNum)
00380         {
00381             /*
00382              * Within the same dimension, choose the new split if it has a
00383              * smaller overlap, or same overlap but better ratio.
00384              */
00385             if (overlap < context->overlap ||
00386                 (overlap == context->overlap && ratio > context->ratio))
00387                 selectthis = true;
00388         }
00389         else
00390         {
00391             /*
00392              * Across dimensions, choose the new split if it has a smaller
00393              * *non-negative* overlap, or same *non-negative* overlap but
00394              * bigger range. This condition differs from the one described in
00395              * the article. On the datasets where leaf MBRs don't overlap
00396              * themselves, non-overlapping splits (i.e. splits which have zero
00397              * *non-negative* overlap) are frequently possible. In this case
00398              * splits tends to be along one dimension, because most distant
00399              * non-overlapping splits (i.e. having lowest negative overlap)
00400              * appears to be in the same dimension as in the previous split.
00401              * Therefore MBRs appear to be very prolonged along another
00403              * as the second split criteria makes MBRs more quadratic. Using
00404              * *non-negative* overlap instead of overlap as the first split
00405              * criteria gives to range criteria a chance to matter, because
00406              * non-overlapping splits are equivalent in this criteria.
00407              */
00408             if (non_negative(overlap) < non_negative(context->overlap) ||
00409                 (range > context->range &&
00410                  non_negative(overlap) <= non_negative(context->overlap)))
00411                 selectthis = true;
00412         }
00413
00414         if (selectthis)
00415         {
00416             /* save information about selected split */
00417             context->first = false;
00418             context->ratio = ratio;
00419             context->range = range;
00420             context->overlap = overlap;
00421             context->rightLower = rightLower;
00422             context->leftUpper = leftUpper;
00423             context->dim = dimNum;
00424         }
00425     }
00426 }
00427
00428 /*
00429  * Return increase of original BOX area by new BOX area insertion.
00430  */
00431 static double
00432 box_penalty(BOX *original, BOX *new)
00433 {
00434     double      union_width,
00435                 union_height;
00436
00437     union_width = Max(original->high.x, new->high.x) -
00438         Min(original->low.x, new->low.x);
00439     union_height = Max(original->high.y, new->high.y) -
00440         Min(original->low.y, new->low.y);
00441     return union_width * union_height - (original->high.x - original->low.x) *
00442         (original->high.y - original->low.y);
00443 }
00444
00445 /*
00446  * Compare common entries by their deltas.
00447  */
00448 static int
00449 common_entry_cmp(const void *i1, const void *i2)
00450 {
00451     double      delta1 = ((const CommonEntry *) i1)->delta,
00452                 delta2 = ((const CommonEntry *) i2)->delta;
00453
00454     if (delta1 < delta2)
00455         return -1;
00456     else if (delta1 > delta2)
00457         return 1;
00458     else
00459         return 0;
00460 }
00461
00462 /*
00463  * --------------------------------------------------------------------------
00464  * Double sorting split algorithm. This is used for both boxes and points.
00465  *
00466  * The algorithm finds split of boxes by considering splits along each axis.
00467  * Each entry is first projected as an interval on the X-axis, and different
00468  * ways to split the intervals into two groups are considered, trying to
00469  * minimize the overlap of the groups. Then the same is repeated for the
00470  * Y-axis, and the overall best split is chosen. The quality of a split is
00471  * determined by overlap along that axis and some other criteria (see
00472  * g_box_consider_split).
00473  *
00474  * After that, all the entries are divided into three groups:
00475  *
00476  * 1) Entries which should be placed to the left group
00477  * 2) Entries which should be placed to the right group
00478  * 3) "Common entries" which can be placed to any of groups without affecting
00479  *    of overlap along selected axis.
00480  *
00481  * The common entries are distributed by minimizing penalty.
00482  *
00483  * For details see:
00484  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
00485  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
00486  * --------------------------------------------------------------------------
00487  */
00488 Datum
00489 gist_box_picksplit(PG_FUNCTION_ARGS)
00490 {
00491     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
00492     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
00493     OffsetNumber i,
00494                 maxoff;
00495     ConsiderSplitContext context;
00496     BOX        *box,
00497                *leftBox,
00498                *rightBox;
00499     int         dim,
00500                 commonEntriesCount;
00501     SplitInterval *intervalsLower,
00502                *intervalsUpper;
00503     CommonEntry *commonEntries;
00504     int         nentries;
00505
00506     memset(&context, 0, sizeof(ConsiderSplitContext));
00507
00508     maxoff = entryvec->n - 1;
00509     nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
00510
00511     /* Allocate arrays for intervals along axes */
00512     intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
00513     intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
00514
00515     /*
00516      * Calculate the overall minimum bounding box over all the entries.
00517      */
00518     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
00519     {
00520         box = DatumGetBoxP(entryvec->vector[i].key);
00521         if (i == FirstOffsetNumber)
00522             context.boundingBox = *box;
00523         else
00525     }
00526
00527     /*
00528      * Iterate over axes for optimal split searching.
00529      */
00530     context.first = true;       /* nothing selected yet */
00531     for (dim = 0; dim < 2; dim++)
00532     {
00533         double      leftUpper,
00534                     rightLower;
00535         int         i1,
00536                     i2;
00537
00538         /* Project each entry as an interval on the selected axis. */
00539         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
00540         {
00541             box = DatumGetBoxP(entryvec->vector[i].key);
00542             if (dim == 0)
00543             {
00544                 intervalsLower[i - FirstOffsetNumber].lower = box->low.x;
00545                 intervalsLower[i - FirstOffsetNumber].upper = box->high.x;
00546             }
00547             else
00548             {
00549                 intervalsLower[i - FirstOffsetNumber].lower = box->low.y;
00550                 intervalsLower[i - FirstOffsetNumber].upper = box->high.y;
00551             }
00552         }
00553
00554         /*
00555          * Make two arrays of intervals: one sorted by lower bound and another
00556          * sorted by upper bound.
00557          */
00558         memcpy(intervalsUpper, intervalsLower,
00559                sizeof(SplitInterval) * nentries);
00560         qsort(intervalsLower, nentries, sizeof(SplitInterval),
00561               interval_cmp_lower);
00562         qsort(intervalsUpper, nentries, sizeof(SplitInterval),
00563               interval_cmp_upper);
00564
00565         /*----
00566          * The goal is to form a left and right interval, so that every entry
00567          * interval is contained by either left or right interval (or both).
00568          *
00569          * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
00570          *
00571          * 0 1 2 3 4
00572          * +-+
00573          *   +---+
00574          *     +-+
00575          *     +---+
00576          *
00577          * The left and right intervals are of the form (0,a) and (b,4).
00578          * We first consider splits where b is the lower bound of an entry.
00579          * We iterate through all entries, and for each b, calculate the
00580          * smallest possible a. Then we consider splits where a is the
00581          * uppper bound of an entry, and for each a, calculate the greatest
00582          * possible b.
00583          *
00584          * In the above example, the first loop would consider splits:
00585          * b=0: (0,1)-(0,4)
00586          * b=1: (0,1)-(1,4)
00587          * b=2: (0,3)-(2,4)
00588          *
00589          * And the second loop:
00590          * a=1: (0,1)-(1,4)
00591          * a=3: (0,3)-(2,4)
00592          * a=4: (0,4)-(2,4)
00593          */
00594
00595         /*
00596          * Iterate over lower bound of right group, finding smallest possible
00597          * upper bound of left group.
00598          */
00599         i1 = 0;
00600         i2 = 0;
00601         rightLower = intervalsLower[i1].lower;
00602         leftUpper = intervalsUpper[i2].lower;
00603         while (true)
00604         {
00605             /*
00606              * Find next lower bound of right group.
00607              */
00608             while (i1 < nentries && rightLower == intervalsLower[i1].lower)
00609             {
00610                 leftUpper = Max(leftUpper, intervalsLower[i1].upper);
00611                 i1++;
00612             }
00613             if (i1 >= nentries)
00614                 break;
00615             rightLower = intervalsLower[i1].lower;
00616
00617             /*
00618              * Find count of intervals which anyway should be placed to the
00619              * left group.
00620              */
00621             while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
00622                 i2++;
00623
00624             /*
00625              * Consider found split.
00626              */
00627             g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
00628         }
00629
00630         /*
00631          * Iterate over upper bound of left group finding greates possible
00632          * lower bound of right group.
00633          */
00634         i1 = nentries - 1;
00635         i2 = nentries - 1;
00636         rightLower = intervalsLower[i1].upper;
00637         leftUpper = intervalsUpper[i2].upper;
00638         while (true)
00639         {
00640             /*
00641              * Find next upper bound of left group.
00642              */
00643             while (i2 >= 0 && leftUpper == intervalsUpper[i2].upper)
00644             {
00645                 rightLower = Min(rightLower, intervalsUpper[i2].lower);
00646                 i2--;
00647             }
00648             if (i2 < 0)
00649                 break;
00650             leftUpper = intervalsUpper[i2].upper;
00651
00652             /*
00653              * Find count of intervals which anyway should be placed to the
00654              * right group.
00655              */
00656             while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
00657                 i1--;
00658
00659             /*
00660              * Consider found split.
00661              */
00662             g_box_consider_split(&context, dim,
00663                                  rightLower, i1 + 1, leftUpper, i2 + 1);
00664         }
00665     }
00666
00667     /*
00668      * If we failed to find any acceptable splits, use trivial split.
00669      */
00670     if (context.first)
00671     {
00672         fallbackSplit(entryvec, v);
00673         PG_RETURN_POINTER(v);
00674     }
00675
00676     /*
00677      * Ok, we have now selected the split across one axis.
00678      *
00679      * While considering the splits, we already determined that there will be
00680      * enough entries in both groups to reach the desired ratio, but we did
00681      * not memorize which entries go to which group. So determine that now.
00682      */
00683
00684     /* Allocate vectors for results */
00685     v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
00686     v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
00687     v->spl_nleft = 0;
00688     v->spl_nright = 0;
00689
00690     /* Allocate bounding boxes of left and right groups */
00691     leftBox = palloc0(sizeof(BOX));
00692     rightBox = palloc0(sizeof(BOX));
00693
00694     /*
00695      * Allocate an array for "common entries" - entries which can be placed to
00696      * either group without affecting overlap along selected axis.
00697      */
00698     commonEntriesCount = 0;
00699     commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
00700
00701     /* Helper macros to place an entry in the left or right group */
00702 #define PLACE_LEFT(box, off)                    \
00703     do {                                        \
00704         if (v->spl_nleft > 0)                   \
00706         else                                    \
00707             *leftBox = *(box);                  \
00708         v->spl_left[v->spl_nleft++] = off;      \
00709     } while(0)
00710
00711 #define PLACE_RIGHT(box, off)                   \
00712     do {                                        \
00713         if (v->spl_nright > 0)                  \
00715         else                                    \
00716             *rightBox = *(box);                 \
00717         v->spl_right[v->spl_nright++] = off;    \
00718     } while(0)
00719
00720     /*
00721      * Distribute entries which can be distributed unambiguously, and collect
00722      * common entries.
00723      */
00724     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
00725     {
00726         double      lower,
00727                     upper;
00728
00729         /*
00730          * Get upper and lower bounds along selected axis.
00731          */
00732         box = DatumGetBoxP(entryvec->vector[i].key);
00733         if (context.dim == 0)
00734         {
00735             lower = box->low.x;
00736             upper = box->high.x;
00737         }
00738         else
00739         {
00740             lower = box->low.y;
00741             upper = box->high.y;
00742         }
00743
00744         if (upper <= context.leftUpper)
00745         {
00746             /* Fits to the left group */
00747             if (lower >= context.rightLower)
00748             {
00749                 /* Fits also to the right group, so "common entry" */
00750                 commonEntries[commonEntriesCount++].index = i;
00751             }
00752             else
00753             {
00754                 /* Doesn't fit to the right group, so join to the left group */
00755                 PLACE_LEFT(box, i);
00756             }
00757         }
00758         else
00759         {
00760             /*
00761              * Each entry should fit on either left or right group. Since this
00762              * entry didn't fit on the left group, it better fit in the right
00763              * group.
00764              */
00765             Assert(lower >= context.rightLower);
00766
00767             /* Doesn't fit to the left group, so join to the right group */
00768             PLACE_RIGHT(box, i);
00769         }
00770     }
00771
00772     /*
00773      * Distribute "common entries", if any.
00774      */
00775     if (commonEntriesCount > 0)
00776     {
00777         /*
00778          * Calculate minimum number of entries that must be placed in both
00779          * groups, to reach LIMIT_RATIO.
00780          */
00781         int         m = ceil(LIMIT_RATIO * (double) nentries);
00782
00783         /*
00784          * Calculate delta between penalties of join "common entries" to
00785          * different groups.
00786          */
00787         for (i = 0; i < commonEntriesCount; i++)
00788         {
00789             box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
00790             commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
00791                                          box_penalty(rightBox, box));
00792         }
00793
00794         /*
00795          * Sort "common entries" by calculated deltas in order to distribute
00796          * the most ambiguous entries first.
00797          */
00798         qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
00799
00800         /*
00801          * Distribute "common entries" between groups.
00802          */
00803         for (i = 0; i < commonEntriesCount; i++)
00804         {
00805             box = DatumGetBoxP(entryvec->vector[commonEntries[i].index].key);
00806
00807             /*
00808              * Check if we have to place this entry in either group to achieve
00809              * LIMIT_RATIO.
00810              */
00811             if (v->spl_nleft + (commonEntriesCount - i) <= m)
00812                 PLACE_LEFT(box, commonEntries[i].index);
00813             else if (v->spl_nright + (commonEntriesCount - i) <= m)
00814                 PLACE_RIGHT(box, commonEntries[i].index);
00815             else
00816             {
00817                 /* Otherwise select the group by minimal penalty */
00818                 if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
00819                     PLACE_LEFT(box, commonEntries[i].index);
00820                 else
00821                     PLACE_RIGHT(box, commonEntries[i].index);
00822             }
00823         }
00824     }
00825
00826     v->spl_ldatum = PointerGetDatum(leftBox);
00827     v->spl_rdatum = PointerGetDatum(rightBox);
00828     PG_RETURN_POINTER(v);
00829 }
00830
00831 /*
00832  * Equality method
00833  *
00834  * This is used for boxes, points, circles, and polygons, all of which store
00835  * boxes as GiST index entries.
00836  *
00837  * Returns true only when boxes are exactly the same.  We can't use fuzzy
00838  * comparisons here without breaking index consistency; therefore, this isn't
00839  * equivalent to box_same().
00840  */
00841 Datum
00842 gist_box_same(PG_FUNCTION_ARGS)
00843 {
00844     BOX        *b1 = PG_GETARG_BOX_P(0);
00845     BOX        *b2 = PG_GETARG_BOX_P(1);
00846     bool       *result = (bool *) PG_GETARG_POINTER(2);
00847
00848     if (b1 && b2)
00849         *result = (b1->low.x == b2->low.x && b1->low.y == b2->low.y &&
00850                    b1->high.x == b2->high.x && b1->high.y == b2->high.y);
00851     else
00852         *result = (b1 == NULL && b2 == NULL);
00853     PG_RETURN_POINTER(result);
00854 }
00855
00856 /*
00857  * Leaf-level consistency for boxes: just apply the query operator
00858  */
00859 static bool
00860 gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy)
00861 {
00862     bool        retval;
00863
00864     switch (strategy)
00865     {
00866         case RTLeftStrategyNumber:
00867             retval = DatumGetBool(DirectFunctionCall2(box_left,
00868                                                       PointerGetDatum(key),
00869                                                     PointerGetDatum(query)));
00870             break;
00871         case RTOverLeftStrategyNumber:
00872             retval = DatumGetBool(DirectFunctionCall2(box_overleft,
00873                                                       PointerGetDatum(key),
00874                                                     PointerGetDatum(query)));
00875             break;
00876         case RTOverlapStrategyNumber:
00877             retval = DatumGetBool(DirectFunctionCall2(box_overlap,
00878                                                       PointerGetDatum(key),
00879                                                     PointerGetDatum(query)));
00880             break;
00881         case RTOverRightStrategyNumber:
00882             retval = DatumGetBool(DirectFunctionCall2(box_overright,
00883                                                       PointerGetDatum(key),
00884                                                     PointerGetDatum(query)));
00885             break;
00886         case RTRightStrategyNumber:
00887             retval = DatumGetBool(DirectFunctionCall2(box_right,
00888                                                       PointerGetDatum(key),
00889                                                     PointerGetDatum(query)));
00890             break;
00891         case RTSameStrategyNumber:
00892             retval = DatumGetBool(DirectFunctionCall2(box_same,
00893                                                       PointerGetDatum(key),
00894                                                     PointerGetDatum(query)));
00895             break;
00896         case RTContainsStrategyNumber:
00897         case RTOldContainsStrategyNumber:
00898             retval = DatumGetBool(DirectFunctionCall2(box_contain,
00899                                                       PointerGetDatum(key),
00900                                                     PointerGetDatum(query)));
00901             break;
00902         case RTContainedByStrategyNumber:
00903         case RTOldContainedByStrategyNumber:
00904             retval = DatumGetBool(DirectFunctionCall2(box_contained,
00905                                                       PointerGetDatum(key),
00906                                                     PointerGetDatum(query)));
00907             break;
00908         case RTOverBelowStrategyNumber:
00909             retval = DatumGetBool(DirectFunctionCall2(box_overbelow,
00910                                                       PointerGetDatum(key),
00911                                                     PointerGetDatum(query)));
00912             break;
00913         case RTBelowStrategyNumber:
00914             retval = DatumGetBool(DirectFunctionCall2(box_below,
00915                                                       PointerGetDatum(key),
00916                                                     PointerGetDatum(query)));
00917             break;
00918         case RTAboveStrategyNumber:
00919             retval = DatumGetBool(DirectFunctionCall2(box_above,
00920                                                       PointerGetDatum(key),
00921                                                     PointerGetDatum(query)));
00922             break;
00923         case RTOverAboveStrategyNumber:
00924             retval = DatumGetBool(DirectFunctionCall2(box_overabove,
00925                                                       PointerGetDatum(key),
00926                                                     PointerGetDatum(query)));
00927             break;
00928         default:
00929             retval = FALSE;
00930     }
00931     return retval;
00932 }
00933
00934 static double
00935 size_box(BOX *box)
00936 {
00937     if (box->high.x <= box->low.x || box->high.y <= box->low.y)
00938         return 0.0;
00939     return (box->high.x - box->low.x) * (box->high.y - box->low.y);
00940 }
00941
00942 /*****************************************
00943  * Common rtree functions (for boxes, polygons, and circles)
00944  *****************************************/
00945
00946 /*
00947  * Internal-page consistency for all these types
00948  *
00949  * We can use the same function since all types use bounding boxes as the
00950  * internal-page representation.
00951  */
00952 static bool
00953 rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy)
00954 {
00955     bool        retval;
00956
00957     switch (strategy)
00958     {
00959         case RTLeftStrategyNumber:
00960             retval = !DatumGetBool(DirectFunctionCall2(box_overright,
00961                                                        PointerGetDatum(key),
00962                                                     PointerGetDatum(query)));
00963             break;
00964         case RTOverLeftStrategyNumber:
00965             retval = !DatumGetBool(DirectFunctionCall2(box_right,
00966                                                        PointerGetDatum(key),
00967                                                     PointerGetDatum(query)));
00968             break;
00969         case RTOverlapStrategyNumber:
00970             retval = DatumGetBool(DirectFunctionCall2(box_overlap,
00971                                                       PointerGetDatum(key),
00972                                                     PointerGetDatum(query)));
00973             break;
00974         case RTOverRightStrategyNumber:
00975             retval = !DatumGetBool(DirectFunctionCall2(box_left,
00976                                                        PointerGetDatum(key),
00977                                                     PointerGetDatum(query)));
00978             break;
00979         case RTRightStrategyNumber:
00980             retval = !DatumGetBool(DirectFunctionCall2(box_overleft,
00981                                                        PointerGetDatum(key),
00982                                                     PointerGetDatum(query)));
00983             break;
00984         case RTSameStrategyNumber:
00985         case RTContainsStrategyNumber:
00986         case RTOldContainsStrategyNumber:
00987             retval = DatumGetBool(DirectFunctionCall2(box_contain,
00988                                                       PointerGetDatum(key),
00989                                                     PointerGetDatum(query)));
00990             break;
00991         case RTContainedByStrategyNumber:
00992         case RTOldContainedByStrategyNumber:
00993             retval = DatumGetBool(DirectFunctionCall2(box_overlap,
00994                                                       PointerGetDatum(key),
00995                                                     PointerGetDatum(query)));
00996             break;
00997         case RTOverBelowStrategyNumber:
00998             retval = !DatumGetBool(DirectFunctionCall2(box_above,
00999                                                        PointerGetDatum(key),
01000                                                     PointerGetDatum(query)));
01001             break;
01002         case RTBelowStrategyNumber:
01003             retval = !DatumGetBool(DirectFunctionCall2(box_overabove,
01004                                                        PointerGetDatum(key),
01005                                                     PointerGetDatum(query)));
01006             break;
01007         case RTAboveStrategyNumber:
01008             retval = !DatumGetBool(DirectFunctionCall2(box_overbelow,
01009                                                        PointerGetDatum(key),
01010                                                     PointerGetDatum(query)));
01011             break;
01012         case RTOverAboveStrategyNumber:
01013             retval = !DatumGetBool(DirectFunctionCall2(box_below,
01014                                                        PointerGetDatum(key),
01015                                                     PointerGetDatum(query)));
01016             break;
01017         default:
01018             retval = FALSE;
01019     }
01020     return retval;
01021 }
01022
01023 /**************************************************
01024  * Polygon ops
01025  **************************************************/
01026
01027 /*
01028  * GiST compress for polygons: represent a polygon by its bounding box
01029  */
01030 Datum
01031 gist_poly_compress(PG_FUNCTION_ARGS)
01032 {
01033     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01034     GISTENTRY  *retval;
01035
01036     if (entry->leafkey)
01037     {
01038         retval = palloc(sizeof(GISTENTRY));
01039         if (DatumGetPointer(entry->key) != NULL)
01040         {
01041             POLYGON    *in = DatumGetPolygonP(entry->key);
01042             BOX        *r;
01043
01044             r = (BOX *) palloc(sizeof(BOX));
01045             memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX));
01046             gistentryinit(*retval, PointerGetDatum(r),
01047                           entry->rel, entry->page,
01048                           entry->offset, FALSE);
01049
01050         }
01051         else
01052         {
01053             gistentryinit(*retval, (Datum) 0,
01054                           entry->rel, entry->page,
01055                           entry->offset, FALSE);
01056         }
01057     }
01058     else
01059         retval = entry;
01060     PG_RETURN_POINTER(retval);
01061 }
01062
01063 /*
01064  * The GiST Consistent method for polygons
01065  */
01066 Datum
01067 gist_poly_consistent(PG_FUNCTION_ARGS)
01068 {
01069     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01070     POLYGON    *query = PG_GETARG_POLYGON_P(1);
01071     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
01072
01073     /* Oid      subtype = PG_GETARG_OID(3); */
01074     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
01075     bool        result;
01076
01077     /* All cases served by this function are inexact */
01078     *recheck = true;
01079
01080     if (DatumGetBoxP(entry->key) == NULL || query == NULL)
01081         PG_RETURN_BOOL(FALSE);
01082
01083     /*
01084      * Since the operators require recheck anyway, we can just use
01085      * rtree_internal_consistent even at leaf nodes.  (This works in part
01086      * because the index entries are bounding boxes not polygons.)
01087      */
01088     result = rtree_internal_consistent(DatumGetBoxP(entry->key),
01089                                        &(query->boundbox), strategy);
01090
01091     /* Avoid memory leak if supplied poly is toasted */
01092     PG_FREE_IF_COPY(query, 1);
01093
01094     PG_RETURN_BOOL(result);
01095 }
01096
01097 /**************************************************
01098  * Circle ops
01099  **************************************************/
01100
01101 /*
01102  * GiST compress for circles: represent a circle by its bounding box
01103  */
01104 Datum
01105 gist_circle_compress(PG_FUNCTION_ARGS)
01106 {
01107     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01108     GISTENTRY  *retval;
01109
01110     if (entry->leafkey)
01111     {
01112         retval = palloc(sizeof(GISTENTRY));
01113         if (DatumGetCircleP(entry->key) != NULL)
01114         {
01115             CIRCLE     *in = DatumGetCircleP(entry->key);
01116             BOX        *r;
01117
01118             r = (BOX *) palloc(sizeof(BOX));
01119             r->high.x = in->center.x + in->radius;
01120             r->low.x = in->center.x - in->radius;
01121             r->high.y = in->center.y + in->radius;
01122             r->low.y = in->center.y - in->radius;
01123             gistentryinit(*retval, PointerGetDatum(r),
01124                           entry->rel, entry->page,
01125                           entry->offset, FALSE);
01126
01127         }
01128         else
01129         {
01130             gistentryinit(*retval, (Datum) 0,
01131                           entry->rel, entry->page,
01132                           entry->offset, FALSE);
01133         }
01134     }
01135     else
01136         retval = entry;
01137     PG_RETURN_POINTER(retval);
01138 }
01139
01140 /*
01141  * The GiST Consistent method for circles
01142  */
01143 Datum
01144 gist_circle_consistent(PG_FUNCTION_ARGS)
01145 {
01146     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01147     CIRCLE     *query = PG_GETARG_CIRCLE_P(1);
01148     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
01149
01150     /* Oid      subtype = PG_GETARG_OID(3); */
01151     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
01152     BOX         bbox;
01153     bool        result;
01154
01155     /* All cases served by this function are inexact */
01156     *recheck = true;
01157
01158     if (DatumGetBoxP(entry->key) == NULL || query == NULL)
01159         PG_RETURN_BOOL(FALSE);
01160
01161     /*
01162      * Since the operators require recheck anyway, we can just use
01163      * rtree_internal_consistent even at leaf nodes.  (This works in part
01164      * because the index entries are bounding boxes not circles.)
01165      */
01166     bbox.high.x = query->center.x + query->radius;
01167     bbox.low.x = query->center.x - query->radius;
01168     bbox.high.y = query->center.y + query->radius;
01169     bbox.low.y = query->center.y - query->radius;
01170
01171     result = rtree_internal_consistent(DatumGetBoxP(entry->key),
01172                                        &bbox, strategy);
01173
01174     PG_RETURN_BOOL(result);
01175 }
01176
01177 /**************************************************
01178  * Point ops
01179  **************************************************/
01180
01181 Datum
01182 gist_point_compress(PG_FUNCTION_ARGS)
01183 {
01184     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01185
01186     if (entry->leafkey)         /* Point, actually */
01187     {
01188         BOX        *box = palloc(sizeof(BOX));
01189         Point      *point = DatumGetPointP(entry->key);
01190         GISTENTRY  *retval = palloc(sizeof(GISTENTRY));
01191
01192         box->high = box->low = *point;
01193
01194         gistentryinit(*retval, BoxPGetDatum(box),
01195                       entry->rel, entry->page, entry->offset, FALSE);
01196
01197         PG_RETURN_POINTER(retval);
01198     }
01199
01200     PG_RETURN_POINTER(entry);
01201 }
01202
01203 #define point_point_distance(p1,p2) \
01204     DatumGetFloat8(DirectFunctionCall2(point_distance, \
01205                                        PointPGetDatum(p1), PointPGetDatum(p2)))
01206
01207 static double
01208 computeDistance(bool isLeaf, BOX *box, Point *point)
01209 {
01210     double      result = 0.0;
01211
01212     if (isLeaf)
01213     {
01214         /* simple point to point distance */
01215         result = point_point_distance(point, &box->low);
01216     }
01217     else if (point->x <= box->high.x && point->x >= box->low.x &&
01218              point->y <= box->high.y && point->y >= box->low.y)
01219     {
01220         /* point inside the box */
01221         result = 0.0;
01222     }
01223     else if (point->x <= box->high.x && point->x >= box->low.x)
01224     {
01225         /* point is over or below box */
01226         Assert(box->low.y <= box->high.y);
01227         if (point->y > box->high.y)
01228             result = point->y - box->high.y;
01229         else if (point->y < box->low.y)
01230             result = box->low.y - point->y;
01231         else
01232             elog(ERROR, "inconsistent point values");
01233     }
01234     else if (point->y <= box->high.y && point->y >= box->low.y)
01235     {
01236         /* point is to left or right of box */
01237         Assert(box->low.x <= box->high.x);
01238         if (point->x > box->high.x)
01239             result = point->x - box->high.x;
01240         else if (point->x < box->low.x)
01241             result = box->low.x - point->x;
01242         else
01243             elog(ERROR, "inconsistent point values");
01244     }
01245     else
01246     {
01247         /* closest point will be a vertex */
01248         Point       p;
01249         double      subresult;
01250
01251         result = point_point_distance(point, &box->low);
01252
01253         subresult = point_point_distance(point, &box->high);
01254         if (result > subresult)
01255             result = subresult;
01256
01257         p.x = box->low.x;
01258         p.y = box->high.y;
01259         subresult = point_point_distance(point, &p);
01260         if (result > subresult)
01261             result = subresult;
01262
01263         p.x = box->high.x;
01264         p.y = box->low.y;
01265         subresult = point_point_distance(point, &p);
01266         if (result > subresult)
01267             result = subresult;
01268     }
01269
01270     return result;
01271 }
01272
01273 static bool
01274 gist_point_consistent_internal(StrategyNumber strategy,
01275                                bool isLeaf, BOX *key, Point *query)
01276 {
01277     bool        result = false;
01278
01279     switch (strategy)
01280     {
01281         case RTLeftStrategyNumber:
01282             result = FPlt(key->low.x, query->x);
01283             break;
01284         case RTRightStrategyNumber:
01285             result = FPgt(key->high.x, query->x);
01286             break;
01287         case RTAboveStrategyNumber:
01288             result = FPgt(key->high.y, query->y);
01289             break;
01290         case RTBelowStrategyNumber:
01291             result = FPlt(key->low.y, query->y);
01292             break;
01293         case RTSameStrategyNumber:
01294             if (isLeaf)
01295             {
01296                 /* key.high must equal key.low, so we can disregard it */
01297                 result = (FPeq(key->low.x, query->x) &&
01298                           FPeq(key->low.y, query->y));
01299             }
01300             else
01301             {
01302                 result = (FPle(query->x, key->high.x) &&
01303                           FPge(query->x, key->low.x) &&
01304                           FPle(query->y, key->high.y) &&
01305                           FPge(query->y, key->low.y));
01306             }
01307             break;
01308         default:
01309             elog(ERROR, "unknown strategy number: %d", strategy);
01310     }
01311
01312     return result;
01313 }
01314
01315 #define GeoStrategyNumberOffset     20
01316 #define PointStrategyNumberGroup    0
01317 #define BoxStrategyNumberGroup      1
01318 #define PolygonStrategyNumberGroup  2
01319 #define CircleStrategyNumberGroup   3
01320
01321 Datum
01322 gist_point_consistent(PG_FUNCTION_ARGS)
01323 {
01324     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01325     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
01326     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
01327     bool        result;
01328     StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
01329
01330     switch (strategyGroup)
01331     {
01332         case PointStrategyNumberGroup:
01333             result = gist_point_consistent_internal(strategy % GeoStrategyNumberOffset,
01334                                                     GIST_LEAF(entry),
01335                                                     DatumGetBoxP(entry->key),
01336                                                     PG_GETARG_POINT_P(1));
01337             *recheck = false;
01338             break;
01339         case BoxStrategyNumberGroup:
01340             {
01341                 /*
01342                  * The only operator in this group is point <@ box (on_pb), so
01343                  * we needn't examine strategy again.
01344                  *
01345                  * For historical reasons, on_pb uses exact rather than fuzzy
01346                  * comparisons.  We could use box_overlap when at an internal
01347                  * page, but that would lead to possibly visiting child pages
01348                  * uselessly, because box_overlap uses fuzzy comparisons.
01349                  * Instead we write a non-fuzzy overlap test.  The same code
01350                  * will also serve for leaf-page tests, since leaf keys have
01351                  * high == low.
01352                  */
01353                 BOX        *query,
01354                            *key;
01355
01356                 query = PG_GETARG_BOX_P(1);
01357                 key = DatumGetBoxP(entry->key);
01358
01359                 result = (key->high.x >= query->low.x &&
01360                           key->low.x <= query->high.x &&
01361                           key->high.y >= query->low.y &&
01362                           key->low.y <= query->high.y);
01363                 *recheck = false;
01364             }
01365             break;
01366         case PolygonStrategyNumberGroup:
01367             {
01368                 POLYGON    *query = PG_GETARG_POLYGON_P(1);
01369
01370                 result = DatumGetBool(DirectFunctionCall5(
01371                                                         gist_poly_consistent,
01372                                                       PointerGetDatum(entry),
01373                                                      PolygonPGetDatum(query),
01374                                       Int16GetDatum(RTOverlapStrategyNumber),
01375                                                0, PointerGetDatum(recheck)));
01376
01377                 if (GIST_LEAF(entry) && result)
01378                 {
01379                     /*
01380                      * We are on leaf page and quick check shows overlapping
01381                      * of polygon's bounding box and point
01382                      */
01383                     BOX        *box = DatumGetBoxP(entry->key);
01384
01385                     Assert(box->high.x == box->low.x
01386                            && box->high.y == box->low.y);
01387                     result = DatumGetBool(DirectFunctionCall2(
01388                                                               poly_contain_pt,
01389                                                      PolygonPGetDatum(query),
01390                                                 PointPGetDatum(&box->high)));
01391                     *recheck = false;
01392                 }
01393             }
01394             break;
01395         case CircleStrategyNumberGroup:
01396             {
01397                 CIRCLE     *query = PG_GETARG_CIRCLE_P(1);
01398
01399                 result = DatumGetBool(DirectFunctionCall5(
01400                                                       gist_circle_consistent,
01401                                                       PointerGetDatum(entry),
01402                                                       CirclePGetDatum(query),
01403                                       Int16GetDatum(RTOverlapStrategyNumber),
01404                                                0, PointerGetDatum(recheck)));
01405
01406                 if (GIST_LEAF(entry) && result)
01407                 {
01408                     /*
01409                      * We are on leaf page and quick check shows overlapping
01410                      * of polygon's bounding box and point
01411                      */
01412                     BOX        *box = DatumGetBoxP(entry->key);
01413
01414                     Assert(box->high.x == box->low.x
01415                            && box->high.y == box->low.y);
01416                     result = DatumGetBool(DirectFunctionCall2(
01417                                                            circle_contain_pt,
01418                                                       CirclePGetDatum(query),
01419                                                 PointPGetDatum(&box->high)));
01420                     *recheck = false;
01421                 }
01422             }
01423             break;
01424         default:
01425             elog(ERROR, "unknown strategy number: %d", strategy);
01426             result = false;     /* keep compiler quiet */
01427     }
01428
01429     PG_RETURN_BOOL(result);
01430 }
01431
01432 Datum
01433 gist_point_distance(PG_FUNCTION_ARGS)
01434 {
01435     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
01436     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
01437     double      distance;
01438     StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;
01439
01440     switch (strategyGroup)
01441     {
01442         case PointStrategyNumberGroup:
01443             distance = computeDistance(GIST_LEAF(entry),
01444                                        DatumGetBoxP(entry->key),
01445                                        PG_GETARG_POINT_P(1));
01446             break;
01447         default:
01448             elog(ERROR, "unknown strategy number: %d", strategy);
01449             distance = 0.0;     /* keep compiler quiet */
01450     }
01451
01452     PG_RETURN_FLOAT8(distance);
01453 }
```