LCOV - code coverage report
Current view: top level - src/backend/utils/adt - geo_spgist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 296 310 95.5 %
Date: 2019-06-19 14:06:47 Functions: 33 33 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * geo_spgist.c
       4             :  *    SP-GiST implementation of 4-dimensional quad tree over boxes
       5             :  *
       6             :  * This module provides SP-GiST implementation for boxes using quad tree
       7             :  * analogy in 4-dimensional space.  SP-GiST doesn't allow indexing of
       8             :  * overlapping objects.  We are making 2D objects never-overlapping in
       9             :  * 4D space.  This technique has some benefits compared to traditional
      10             :  * R-Tree which is implemented as GiST.  The performance tests reveal
      11             :  * that this technique especially beneficial with too much overlapping
      12             :  * objects, so called "spaghetti data".
      13             :  *
      14             :  * Unlike the original quad tree, we are splitting the tree into 16
      15             :  * quadrants in 4D space.  It is easier to imagine it as splitting space
      16             :  * two times into 4:
      17             :  *
      18             :  *              |      |
      19             :  *              |      |
      20             :  *              | -----+-----
      21             :  *              |      |
      22             :  *              |      |
      23             :  * -------------+-------------
      24             :  *              |
      25             :  *              |
      26             :  *              |
      27             :  *              |
      28             :  *              |
      29             :  *
      30             :  * We are using box datatype as the prefix, but we are treating them
      31             :  * as points in 4-dimensional space, because 2D boxes are not enough
      32             :  * to represent the quadrant boundaries in 4D space.  They however are
      33             :  * sufficient to point out the additional boundaries of the next
      34             :  * quadrant.
      35             :  *
      36             :  * We are using traversal values provided by SP-GiST to calculate and
      37             :  * to store the bounds of the quadrants, while traversing into the tree.
      38             :  * Traversal value has all the boundaries in the 4D space, and is capable
      39             :  * of transferring the required boundaries to the following traversal
      40             :  * values.  In conclusion, three things are necessary to calculate the
      41             :  * next traversal value:
      42             :  *
      43             :  *  (1) the traversal value of the parent
      44             :  *  (2) the quadrant of the current node
      45             :  *  (3) the prefix of the current node
      46             :  *
      47             :  * If we visualize them on our simplified drawing (see the drawing above);
      48             :  * transferred boundaries of (1) would be the outer axis, relevant part
      49             :  * of (2) would be the up right part of the other axis, and (3) would be
      50             :  * the inner axis.
      51             :  *
      52             :  * For example, consider the case of overlapping.  When recursion
      53             :  * descends deeper and deeper down the tree, all quadrants in
      54             :  * the current node will be checked for overlapping.  The boundaries
      55             :  * will be re-calculated for all quadrants.  Overlap check answers
      56             :  * the question: can any box from this quadrant overlap with the given
      57             :  * box?  If yes, then this quadrant will be walked.  If no, then this
      58             :  * quadrant will be skipped.
      59             :  *
      60             :  * This method provides restrictions for minimum and maximum values of
      61             :  * every dimension of every corner of the box on every level of the tree
      62             :  * except the root.  For the root node, we are setting the boundaries
      63             :  * that we don't yet have as infinity.
      64             :  *
      65             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
      66             :  * Portions Copyright (c) 1994, Regents of the University of California
      67             :  *
      68             :  * IDENTIFICATION
      69             :  *          src/backend/utils/adt/geo_spgist.c
      70             :  *
      71             :  *-------------------------------------------------------------------------
      72             :  */
      73             : 
      74             : #include "postgres.h"
      75             : 
      76             : #include "access/spgist.h"
      77             : #include "access/spgist_private.h"
      78             : #include "access/stratnum.h"
      79             : #include "catalog/pg_type.h"
      80             : #include "utils/float.h"
      81             : #include "utils/fmgroids.h"
      82             : #include "utils/fmgrprotos.h"
      83             : #include "utils/geo_decls.h"
      84             : 
      85             : /*
      86             :  * Comparator for qsort
      87             :  *
      88             :  * We don't need to use the floating point macros in here, because this
      89             :  * is only going to be used in a place to effect the performance
      90             :  * of the index, not the correctness.
      91             :  */
      92             : static int
      93     1365160 : compareDoubles(const void *a, const void *b)
      94             : {
      95     1365160 :     float8      x = *(float8 *) a;
      96     1365160 :     float8      y = *(float8 *) b;
      97             : 
      98     1365160 :     if (x == y)
      99      267052 :         return 0;
     100     1098108 :     return (x > y) ? 1 : -1;
     101             : }
     102             : 
     103             : typedef struct
     104             : {
     105             :     float8      low;
     106             :     float8      high;
     107             : } Range;
     108             : 
     109             : typedef struct
     110             : {
     111             :     Range       left;
     112             :     Range       right;
     113             : } RangeBox;
     114             : 
     115             : typedef struct
     116             : {
     117             :     RangeBox    range_box_x;
     118             :     RangeBox    range_box_y;
     119             : } RectBox;
     120             : 
     121             : /*
     122             :  * Calculate the quadrant
     123             :  *
     124             :  * The quadrant is 8 bit unsigned integer with 4 least bits in use.
     125             :  * This function accepts BOXes as input.  They are not casted to
     126             :  * RangeBoxes, yet.  All 4 bits are set by comparing a corner of the box.
     127             :  * This makes 16 quadrants in total.
     128             :  */
     129             : static uint8
     130      581488 : getQuadrant(BOX *centroid, BOX *inBox)
     131             : {
     132      581488 :     uint8       quadrant = 0;
     133             : 
     134      581488 :     if (inBox->low.x > centroid->low.x)
     135      490412 :         quadrant |= 0x8;
     136             : 
     137      581488 :     if (inBox->high.x > centroid->high.x)
     138      499456 :         quadrant |= 0x4;
     139             : 
     140      581488 :     if (inBox->low.y > centroid->low.y)
     141      313936 :         quadrant |= 0x2;
     142             : 
     143      581488 :     if (inBox->high.y > centroid->high.y)
     144      316140 :         quadrant |= 0x1;
     145             : 
     146      581488 :     return quadrant;
     147             : }
     148             : 
     149             : /*
     150             :  * Get RangeBox using BOX
     151             :  *
     152             :  * We are turning the BOX to our structures to emphasize their function
     153             :  * of representing points in 4D space.  It also is more convenient to
     154             :  * access the values with this structure.
     155             :  */
     156             : static RangeBox *
     157       10104 : getRangeBox(BOX *box)
     158             : {
     159       10104 :     RangeBox   *range_box = (RangeBox *) palloc(sizeof(RangeBox));
     160             : 
     161       10104 :     range_box->left.low = box->low.x;
     162       10104 :     range_box->left.high = box->high.x;
     163             : 
     164       10104 :     range_box->right.low = box->low.y;
     165       10104 :     range_box->right.high = box->high.y;
     166             : 
     167       10104 :     return range_box;
     168             : }
     169             : 
     170             : /*
     171             :  * Initialize the traversal value
     172             :  *
     173             :  * In the beginning, we don't have any restrictions.  We have to
     174             :  * initialize the struct to cover the whole 4D space.
     175             :  */
     176             : static RectBox *
     177         500 : initRectBox(void)
     178             : {
     179         500 :     RectBox    *rect_box = (RectBox *) palloc(sizeof(RectBox));
     180         500 :     float8      infinity = get_float8_infinity();
     181             : 
     182         500 :     rect_box->range_box_x.left.low = -infinity;
     183         500 :     rect_box->range_box_x.left.high = infinity;
     184             : 
     185         500 :     rect_box->range_box_x.right.low = -infinity;
     186         500 :     rect_box->range_box_x.right.high = infinity;
     187             : 
     188         500 :     rect_box->range_box_y.left.low = -infinity;
     189         500 :     rect_box->range_box_y.left.high = infinity;
     190             : 
     191         500 :     rect_box->range_box_y.right.low = -infinity;
     192         500 :     rect_box->range_box_y.right.high = infinity;
     193             : 
     194         500 :     return rect_box;
     195             : }
     196             : 
     197             : /*
     198             :  * Calculate the next traversal value
     199             :  *
     200             :  * All centroids are bounded by RectBox, but SP-GiST only keeps
     201             :  * boxes.  When we are traversing the tree, we must calculate RectBox,
     202             :  * using centroid and quadrant.
     203             :  */
     204             : static RectBox *
     205       80832 : nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
     206             : {
     207       80832 :     RectBox    *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
     208             : 
     209       80832 :     memcpy(next_rect_box, rect_box, sizeof(RectBox));
     210             : 
     211       80832 :     if (quadrant & 0x8)
     212       40416 :         next_rect_box->range_box_x.left.low = centroid->left.low;
     213             :     else
     214       40416 :         next_rect_box->range_box_x.left.high = centroid->left.low;
     215             : 
     216       80832 :     if (quadrant & 0x4)
     217       40416 :         next_rect_box->range_box_x.right.low = centroid->left.high;
     218             :     else
     219       40416 :         next_rect_box->range_box_x.right.high = centroid->left.high;
     220             : 
     221       80832 :     if (quadrant & 0x2)
     222       40416 :         next_rect_box->range_box_y.left.low = centroid->right.low;
     223             :     else
     224       40416 :         next_rect_box->range_box_y.left.high = centroid->right.low;
     225             : 
     226       80832 :     if (quadrant & 0x1)
     227       40416 :         next_rect_box->range_box_y.right.low = centroid->right.high;
     228             :     else
     229       40416 :         next_rect_box->range_box_y.right.high = centroid->right.high;
     230             : 
     231       80832 :     return next_rect_box;
     232             : }
     233             : 
     234             : /* Can any range from range_box overlap with this argument? */
     235             : static bool
     236        7200 : overlap2D(RangeBox *range_box, Range *query)
     237             : {
     238       13552 :     return FPge(range_box->right.high, query->low) &&
     239        6352 :         FPle(range_box->left.low, query->high);
     240             : }
     241             : 
     242             : /* Can any rectangle from rect_box overlap with this argument? */
     243             : static bool
     244        4224 : overlap4D(RectBox *rect_box, RangeBox *query)
     245             : {
     246        7200 :     return overlap2D(&rect_box->range_box_x, &query->left) &&
     247        2976 :         overlap2D(&rect_box->range_box_y, &query->right);
     248             : }
     249             : 
     250             : /* Can any range from range_box contain this argument? */
     251             : static bool
     252        1184 : contain2D(RangeBox *range_box, Range *query)
     253             : {
     254        1984 :     return FPge(range_box->right.high, query->high) &&
     255         800 :         FPle(range_box->left.low, query->low);
     256             : }
     257             : 
     258             : /* Can any rectangle from rect_box contain this argument? */
     259             : static bool
     260         768 : contain4D(RectBox *rect_box, RangeBox *query)
     261             : {
     262        1184 :     return contain2D(&rect_box->range_box_x, &query->left) &&
     263         416 :         contain2D(&rect_box->range_box_y, &query->right);
     264             : }
     265             : 
     266             : /* Can any range from range_box be contained by this argument? */
     267             : static bool
     268       10384 : contained2D(RangeBox *range_box, Range *query)
     269             : {
     270       20248 :     return FPle(range_box->left.low, query->high) &&
     271       18000 :         FPge(range_box->left.high, query->low) &&
     272       26284 :         FPle(range_box->right.low, query->high) &&
     273        7764 :         FPge(range_box->right.high, query->low);
     274             : }
     275             : 
     276             : /* Can any rectangle from rect_box be contained by this argument? */
     277             : static bool
     278        6720 : contained4D(RectBox *rect_box, RangeBox *query)
     279             : {
     280       10384 :     return contained2D(&rect_box->range_box_x, &query->left) &&
     281        3664 :         contained2D(&rect_box->range_box_y, &query->right);
     282             : }
     283             : 
     284             : /* Can any range from range_box to be lower than this argument? */
     285             : static bool
     286        9088 : lower2D(RangeBox *range_box, Range *query)
     287             : {
     288       16288 :     return FPlt(range_box->left.low, query->low) &&
     289        7200 :         FPlt(range_box->right.low, query->low);
     290             : }
     291             : 
     292             : /* Can any range from range_box not extend to the right side of the query? */
     293             : static bool
     294       16192 : overLower2D(RangeBox *range_box, Range *query)
     295             : {
     296       31136 :     return FPle(range_box->left.low, query->high) &&
     297       14944 :         FPle(range_box->right.low, query->high);
     298             : }
     299             : 
     300             : /* Can any range from range_box to be higher than this argument? */
     301             : static bool
     302       23232 : higher2D(RangeBox *range_box, Range *query)
     303             : {
     304       41248 :     return FPgt(range_box->left.high, query->high) &&
     305       18016 :         FPgt(range_box->right.high, query->high);
     306             : }
     307             : 
     308             : /* Can any range from range_box not extend to the left side of the query? */
     309             : static bool
     310       20608 : overHigher2D(RangeBox *range_box, Range *query)
     311             : {
     312       39584 :     return FPge(range_box->left.high, query->low) &&
     313       18976 :         FPge(range_box->right.high, query->low);
     314             : }
     315             : 
     316             : /* Can any rectangle from rect_box be left of this argument? */
     317             : static bool
     318        6208 : left4D(RectBox *rect_box, RangeBox *query)
     319             : {
     320        6208 :     return lower2D(&rect_box->range_box_x, &query->left);
     321             : }
     322             : 
     323             : /* Can any rectangle from rect_box does not extend the right of this argument? */
     324             : static bool
     325        9792 : overLeft4D(RectBox *rect_box, RangeBox *query)
     326             : {
     327        9792 :     return overLower2D(&rect_box->range_box_x, &query->left);
     328             : }
     329             : 
     330             : /* Can any rectangle from rect_box be right of this argument? */
     331             : static bool
     332       17536 : right4D(RectBox *rect_box, RangeBox *query)
     333             : {
     334       17536 :     return higher2D(&rect_box->range_box_x, &query->left);
     335             : }
     336             : 
     337             : /* Can any rectangle from rect_box does not extend the left of this argument? */
     338             : static bool
     339       11328 : overRight4D(RectBox *rect_box, RangeBox *query)
     340             : {
     341       11328 :     return overHigher2D(&rect_box->range_box_x, &query->left);
     342             : }
     343             : 
     344             : /* Can any rectangle from rect_box be below of this argument? */
     345             : static bool
     346        2880 : below4D(RectBox *rect_box, RangeBox *query)
     347             : {
     348        2880 :     return lower2D(&rect_box->range_box_y, &query->right);
     349             : }
     350             : 
     351             : /* Can any rectangle from rect_box does not extend above this argument? */
     352             : static bool
     353        6400 : overBelow4D(RectBox *rect_box, RangeBox *query)
     354             : {
     355        6400 :     return overLower2D(&rect_box->range_box_y, &query->right);
     356             : }
     357             : 
     358             : /* Can any rectangle from rect_box be above of this argument? */
     359             : static bool
     360        5696 : above4D(RectBox *rect_box, RangeBox *query)
     361             : {
     362        5696 :     return higher2D(&rect_box->range_box_y, &query->right);
     363             : }
     364             : 
     365             : /* Can any rectangle from rect_box does not extend below of this argument? */
     366             : static bool
     367        9280 : overAbove4D(RectBox *rect_box, RangeBox *query)
     368             : {
     369        9280 :     return overHigher2D(&rect_box->range_box_y, &query->right);
     370             : }
     371             : 
     372             : /* Lower bound for the distance between point and rect_box */
     373             : static double
     374        1160 : pointToRectBoxDistance(Point *point, RectBox *rect_box)
     375             : {
     376             :     double      dx;
     377             :     double      dy;
     378             : 
     379        1160 :     if (point->x < rect_box->range_box_x.left.low)
     380        1040 :         dx = rect_box->range_box_x.left.low - point->x;
     381         120 :     else if (point->x > rect_box->range_box_x.right.high)
     382           0 :         dx = point->x - rect_box->range_box_x.right.high;
     383             :     else
     384         120 :         dx = 0;
     385             : 
     386        1160 :     if (point->y < rect_box->range_box_y.left.low)
     387         384 :         dy = rect_box->range_box_y.left.low - point->y;
     388         776 :     else if (point->y > rect_box->range_box_y.right.high)
     389         708 :         dy = point->y - rect_box->range_box_y.right.high;
     390             :     else
     391          68 :         dy = 0;
     392             : 
     393        1160 :     return HYPOT(dx, dy);
     394             : }
     395             : 
     396             : 
     397             : /*
     398             :  * SP-GiST config function
     399             :  */
     400             : Datum
     401          36 : spg_box_quad_config(PG_FUNCTION_ARGS)
     402             : {
     403          36 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
     404             : 
     405          36 :     cfg->prefixType = BOXOID;
     406          36 :     cfg->labelType = VOIDOID;    /* We don't need node labels. */
     407          36 :     cfg->canReturnData = true;
     408          36 :     cfg->longValuesOK = false;
     409             : 
     410          36 :     PG_RETURN_VOID();
     411             : }
     412             : 
     413             : /*
     414             :  * SP-GiST choose function
     415             :  */
     416             : Datum
     417      503070 : spg_box_quad_choose(PG_FUNCTION_ARGS)
     418             : {
     419      503070 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
     420      503070 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
     421      503070 :     BOX        *centroid = DatumGetBoxP(in->prefixDatum),
     422      503070 :                *box = DatumGetBoxP(in->leafDatum);
     423             : 
     424      503070 :     out->resultType = spgMatchNode;
     425      503070 :     out->result.matchNode.restDatum = BoxPGetDatum(box);
     426             : 
     427             :     /* nodeN will be set by core, when allTheSame. */
     428      503070 :     if (!in->allTheSame)
     429      494268 :         out->result.matchNode.nodeN = getQuadrant(centroid, box);
     430             : 
     431      503070 :     PG_RETURN_VOID();
     432             : }
     433             : 
     434             : /*
     435             :  * SP-GiST pick-split function
     436             :  *
     437             :  * It splits a list of boxes into quadrants by choosing a central 4D
     438             :  * point as the median of the coordinates of the boxes.
     439             :  */
     440             : Datum
     441         876 : spg_box_quad_picksplit(PG_FUNCTION_ARGS)
     442             : {
     443         876 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     444         876 :     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
     445             :     BOX        *centroid;
     446             :     int         median,
     447             :                 i;
     448         876 :     float8     *lowXs = palloc(sizeof(float8) * in->nTuples);
     449         876 :     float8     *highXs = palloc(sizeof(float8) * in->nTuples);
     450         876 :     float8     *lowYs = palloc(sizeof(float8) * in->nTuples);
     451         876 :     float8     *highYs = palloc(sizeof(float8) * in->nTuples);
     452             : 
     453             :     /* Calculate median of all 4D coordinates */
     454       88096 :     for (i = 0; i < in->nTuples; i++)
     455             :     {
     456       87220 :         BOX        *box = DatumGetBoxP(in->datums[i]);
     457             : 
     458       87220 :         lowXs[i] = box->low.x;
     459       87220 :         highXs[i] = box->high.x;
     460       87220 :         lowYs[i] = box->low.y;
     461       87220 :         highYs[i] = box->high.y;
     462             :     }
     463             : 
     464         876 :     qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
     465         876 :     qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
     466         876 :     qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
     467         876 :     qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
     468             : 
     469         876 :     median = in->nTuples / 2;
     470             : 
     471         876 :     centroid = palloc(sizeof(BOX));
     472             : 
     473         876 :     centroid->low.x = lowXs[median];
     474         876 :     centroid->high.x = highXs[median];
     475         876 :     centroid->low.y = lowYs[median];
     476         876 :     centroid->high.y = highYs[median];
     477             : 
     478             :     /* Fill the output */
     479         876 :     out->hasPrefix = true;
     480         876 :     out->prefixDatum = BoxPGetDatum(centroid);
     481             : 
     482         876 :     out->nNodes = 16;
     483         876 :     out->nodeLabels = NULL;      /* We don't need node labels. */
     484             : 
     485         876 :     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     486         876 :     out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
     487             : 
     488             :     /*
     489             :      * Assign ranges to corresponding nodes according to quadrants relative to
     490             :      * the "centroid" range
     491             :      */
     492       88096 :     for (i = 0; i < in->nTuples; i++)
     493             :     {
     494       87220 :         BOX        *box = DatumGetBoxP(in->datums[i]);
     495       87220 :         uint8       quadrant = getQuadrant(centroid, box);
     496             : 
     497       87220 :         out->leafTupleDatums[i] = BoxPGetDatum(box);
     498       87220 :         out->mapTuplesToNodes[i] = quadrant;
     499             :     }
     500             : 
     501         876 :     PG_RETURN_VOID();
     502             : }
     503             : 
     504             : /*
     505             :  * Check if result of consistent method based on bounding box is exact.
     506             :  */
     507             : static bool
     508      261360 : is_bounding_box_test_exact(StrategyNumber strategy)
     509             : {
     510      261360 :     switch (strategy)
     511             :     {
     512             :         case RTLeftStrategyNumber:
     513             :         case RTOverLeftStrategyNumber:
     514             :         case RTOverRightStrategyNumber:
     515             :         case RTRightStrategyNumber:
     516             :         case RTOverBelowStrategyNumber:
     517             :         case RTBelowStrategyNumber:
     518             :         case RTAboveStrategyNumber:
     519             :         case RTOverAboveStrategyNumber:
     520      216676 :             return true;
     521             : 
     522             :         default:
     523       44684 :             return false;
     524             :     }
     525             : }
     526             : 
     527             : /*
     528             :  * Get bounding box for ScanKey.
     529             :  */
     530             : static BOX *
     531      515000 : spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
     532             : {
     533      515000 :     switch (sk->sk_subtype)
     534             :     {
     535             :         case BOXOID:
     536      251252 :             return DatumGetBoxP(sk->sk_argument);
     537             : 
     538             :         case POLYGONOID:
     539      263748 :             if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
     540       44684 :                 *recheck = true;
     541      263748 :             return &DatumGetPolygonP(sk->sk_argument)->boundbox;
     542             : 
     543             :         default:
     544           0 :             elog(ERROR, "unrecognized scankey subtype: %d", sk->sk_subtype);
     545             :             return NULL;
     546             :     }
     547             : }
     548             : 
     549             : /*
     550             :  * SP-GiST inner consistent function
     551             :  */
     552             : Datum
     553        5488 : spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
     554             : {
     555        5488 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     556        5488 :     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
     557             :     int         i;
     558             :     MemoryContext old_ctx;
     559             :     RectBox    *rect_box;
     560             :     uint8       quadrant;
     561             :     RangeBox   *centroid,
     562             :               **queries;
     563             : 
     564             :     /*
     565             :      * We are saving the traversal value or initialize it an unbounded one, if
     566             :      * we have just begun to walk the tree.
     567             :      */
     568        5488 :     if (in->traversalValue)
     569        4988 :         rect_box = in->traversalValue;
     570             :     else
     571         500 :         rect_box = initRectBox();
     572             : 
     573        5488 :     if (in->allTheSame)
     574             :     {
     575             :         /* Report that all nodes should be visited */
     576         436 :         out->nNodes = in->nNodes;
     577         436 :         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     578        3924 :         for (i = 0; i < in->nNodes; i++)
     579        3488 :             out->nodeNumbers[i] = i;
     580             : 
     581         436 :         if (in->norderbys > 0 && in->nNodes > 0)
     582             :         {
     583           0 :             double     *distances = palloc(sizeof(double) * in->norderbys);
     584             :             int         j;
     585             : 
     586           0 :             for (j = 0; j < in->norderbys; j++)
     587             :             {
     588           0 :                 Point      *pt = DatumGetPointP(in->orderbys[j].sk_argument);
     589             : 
     590           0 :                 distances[j] = pointToRectBoxDistance(pt, rect_box);
     591             :             }
     592             : 
     593           0 :             out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
     594           0 :             out->distances[0] = distances;
     595             : 
     596           0 :             for (i = 1; i < in->nNodes; i++)
     597             :             {
     598           0 :                 out->distances[i] = palloc(sizeof(double) * in->norderbys);
     599           0 :                 memcpy(out->distances[i], distances,
     600           0 :                        sizeof(double) * in->norderbys);
     601             :             }
     602             :         }
     603             : 
     604         436 :         PG_RETURN_VOID();
     605             :     }
     606             : 
     607             :     /*
     608             :      * We are casting the prefix and queries to RangeBoxes for ease of the
     609             :      * following operations.
     610             :      */
     611        5052 :     centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
     612        5052 :     queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
     613       10104 :     for (i = 0; i < in->nkeys; i++)
     614             :     {
     615        5052 :         BOX        *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
     616             : 
     617        5052 :         queries[i] = getRangeBox(box);
     618             :     }
     619             : 
     620             :     /* Allocate enough memory for nodes */
     621        5052 :     out->nNodes = 0;
     622        5052 :     out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     623        5052 :     out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
     624        5052 :     if (in->norderbys > 0)
     625         132 :         out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
     626             : 
     627             :     /*
     628             :      * We switch memory context, because we want to allocate memory for new
     629             :      * traversal values (next_rect_box) and pass these pieces of memory to
     630             :      * further call of this function.
     631             :      */
     632        5052 :     old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
     633             : 
     634       85884 :     for (quadrant = 0; quadrant < in->nNodes; quadrant++)
     635             :     {
     636       80832 :         RectBox    *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
     637       80832 :         bool        flag = true;
     638             : 
     639      141192 :         for (i = 0; i < in->nkeys; i++)
     640             :         {
     641       80832 :             StrategyNumber strategy = in->scankeys[i].sk_strategy;
     642             : 
     643       80832 :             switch (strategy)
     644             :             {
     645             :                 case RTOverlapStrategyNumber:
     646        4224 :                     flag = overlap4D(next_rect_box, queries[i]);
     647        4224 :                     break;
     648             : 
     649             :                 case RTContainsStrategyNumber:
     650         768 :                     flag = contain4D(next_rect_box, queries[i]);
     651         768 :                     break;
     652             : 
     653             :                 case RTSameStrategyNumber:
     654             :                 case RTContainedByStrategyNumber:
     655        6720 :                     flag = contained4D(next_rect_box, queries[i]);
     656        6720 :                     break;
     657             : 
     658             :                 case RTLeftStrategyNumber:
     659        6208 :                     flag = left4D(next_rect_box, queries[i]);
     660        6208 :                     break;
     661             : 
     662             :                 case RTOverLeftStrategyNumber:
     663        9792 :                     flag = overLeft4D(next_rect_box, queries[i]);
     664        9792 :                     break;
     665             : 
     666             :                 case RTRightStrategyNumber:
     667       17536 :                     flag = right4D(next_rect_box, queries[i]);
     668       17536 :                     break;
     669             : 
     670             :                 case RTOverRightStrategyNumber:
     671       11328 :                     flag = overRight4D(next_rect_box, queries[i]);
     672       11328 :                     break;
     673             : 
     674             :                 case RTAboveStrategyNumber:
     675        5696 :                     flag = above4D(next_rect_box, queries[i]);
     676        5696 :                     break;
     677             : 
     678             :                 case RTOverAboveStrategyNumber:
     679        9280 :                     flag = overAbove4D(next_rect_box, queries[i]);
     680        9280 :                     break;
     681             : 
     682             :                 case RTBelowStrategyNumber:
     683        2880 :                     flag = below4D(next_rect_box, queries[i]);
     684        2880 :                     break;
     685             : 
     686             :                 case RTOverBelowStrategyNumber:
     687        6400 :                     flag = overBelow4D(next_rect_box, queries[i]);
     688        6400 :                     break;
     689             : 
     690             :                 default:
     691           0 :                     elog(ERROR, "unrecognized strategy: %d", strategy);
     692             :             }
     693             : 
     694             :             /* If any check is failed, we have found our answer. */
     695       80832 :             if (!flag)
     696       20472 :                 break;
     697             :         }
     698             : 
     699       80832 :         if (flag)
     700             :         {
     701       60360 :             out->traversalValues[out->nNodes] = next_rect_box;
     702       60360 :             out->nodeNumbers[out->nNodes] = quadrant;
     703             : 
     704       60360 :             if (in->norderbys > 0)
     705             :             {
     706        1160 :                 double     *distances = palloc(sizeof(double) * in->norderbys);
     707             :                 int         j;
     708             : 
     709        1160 :                 out->distances[out->nNodes] = distances;
     710             : 
     711        2320 :                 for (j = 0; j < in->norderbys; j++)
     712             :                 {
     713        1160 :                     Point      *pt = DatumGetPointP(in->orderbys[j].sk_argument);
     714             : 
     715        1160 :                     distances[j] = pointToRectBoxDistance(pt, next_rect_box);
     716             :                 }
     717             :             }
     718             : 
     719       60360 :             out->nNodes++;
     720             :         }
     721             :         else
     722             :         {
     723             :             /*
     724             :              * If this node is not selected, we don't need to keep the next
     725             :              * traversal value in the memory context.
     726             :              */
     727       20472 :             pfree(next_rect_box);
     728             :         }
     729             :     }
     730             : 
     731             :     /* Switch back */
     732        5052 :     MemoryContextSwitchTo(old_ctx);
     733             : 
     734        5052 :     PG_RETURN_VOID();
     735             : }
     736             : 
     737             : /*
     738             :  * SP-GiST inner consistent function
     739             :  */
     740             : Datum
     741      509948 : spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
     742             : {
     743      509948 :     spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
     744      509948 :     spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
     745      509948 :     Datum       leaf = in->leafDatum;
     746      509948 :     bool        flag = true;
     747             :     int         i;
     748             : 
     749             :     /* All tests are exact. */
     750      509948 :     out->recheck = false;
     751             : 
     752             :     /* leafDatum is what it is... */
     753      509948 :     out->leafValue = in->leafDatum;
     754             : 
     755             :     /* Perform the required comparison(s) */
     756      927784 :     for (i = 0; i < in->nkeys; i++)
     757             :     {
     758      509948 :         StrategyNumber strategy = in->scankeys[i].sk_strategy;
     759      509948 :         BOX        *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
     760             :                                                         &out->recheck);
     761      509948 :         Datum       query = BoxPGetDatum(box);
     762             : 
     763      509948 :         switch (strategy)
     764             :         {
     765             :             case RTOverlapStrategyNumber:
     766       24212 :                 flag = DatumGetBool(DirectFunctionCall2(box_overlap, leaf,
     767             :                                                         query));
     768       24212 :                 break;
     769             : 
     770             :             case RTContainsStrategyNumber:
     771        5604 :                 flag = DatumGetBool(DirectFunctionCall2(box_contain, leaf,
     772             :                                                         query));
     773        5604 :                 break;
     774             : 
     775             :             case RTContainedByStrategyNumber:
     776       33888 :                 flag = DatumGetBool(DirectFunctionCall2(box_contained, leaf,
     777             :                                                         query));
     778       33888 :                 break;
     779             : 
     780             :             case RTSameStrategyNumber:
     781        8688 :                 flag = DatumGetBool(DirectFunctionCall2(box_same, leaf,
     782             :                                                         query));
     783        8688 :                 break;
     784             : 
     785             :             case RTLeftStrategyNumber:
     786       32128 :                 flag = DatumGetBool(DirectFunctionCall2(box_left, leaf,
     787             :                                                         query));
     788       32128 :                 break;
     789             : 
     790             :             case RTOverLeftStrategyNumber:
     791       65252 :                 flag = DatumGetBool(DirectFunctionCall2(box_overleft, leaf,
     792             :                                                         query));
     793       65252 :                 break;
     794             : 
     795             :             case RTRightStrategyNumber:
     796       86608 :                 flag = DatumGetBool(DirectFunctionCall2(box_right, leaf,
     797             :                                                         query));
     798       86608 :                 break;
     799             : 
     800             :             case RTOverRightStrategyNumber:
     801       73712 :                 flag = DatumGetBool(DirectFunctionCall2(box_overright, leaf,
     802             :                                                         query));
     803       73712 :                 break;
     804             : 
     805             :             case RTAboveStrategyNumber:
     806       37280 :                 flag = DatumGetBool(DirectFunctionCall2(box_above, leaf,
     807             :                                                         query));
     808       37280 :                 break;
     809             : 
     810             :             case RTOverAboveStrategyNumber:
     811       72900 :                 flag = DatumGetBool(DirectFunctionCall2(box_overabove, leaf,
     812             :                                                         query));
     813       72900 :                 break;
     814             : 
     815             :             case RTBelowStrategyNumber:
     816       17252 :                 flag = DatumGetBool(DirectFunctionCall2(box_below, leaf,
     817             :                                                         query));
     818       17252 :                 break;
     819             : 
     820             :             case RTOverBelowStrategyNumber:
     821       52424 :                 flag = DatumGetBool(DirectFunctionCall2(box_overbelow, leaf,
     822             :                                                         query));
     823       52424 :                 break;
     824             : 
     825             :             default:
     826           0 :                 elog(ERROR, "unrecognized strategy: %d", strategy);
     827             :         }
     828             : 
     829             :         /* If any check is failed, we have found our answer. */
     830      509948 :         if (!flag)
     831       92112 :             break;
     832             :     }
     833             : 
     834      509948 :     if (flag && in->norderbys > 0)
     835             :     {
     836        6084 :         Oid         distfnoid = in->orderbys[0].sk_func.fn_oid;
     837             : 
     838        6084 :         out->distances = spg_key_orderbys_distances(leaf, false,
     839             :                                                     in->orderbys, in->norderbys);
     840             : 
     841             :         /* Recheck is necessary when computing distance to polygon */
     842        6084 :         out->recheckDistances = distfnoid == F_DIST_POLYP;
     843             :     }
     844             : 
     845      509948 :     PG_RETURN_BOOL(flag);
     846             : }
     847             : 
     848             : 
     849             : /*
     850             :  * SP-GiST config function for 2-D types that are lossy represented by their
     851             :  * bounding boxes
     852             :  */
     853             : Datum
     854          18 : spg_bbox_quad_config(PG_FUNCTION_ARGS)
     855             : {
     856          18 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
     857             : 
     858          18 :     cfg->prefixType = BOXOID;    /* A type represented by its bounding box */
     859          18 :     cfg->labelType = VOIDOID;    /* We don't need node labels. */
     860          18 :     cfg->leafType = BOXOID;
     861          18 :     cfg->canReturnData = false;
     862          18 :     cfg->longValuesOK = false;
     863             : 
     864          18 :     PG_RETURN_VOID();
     865             : }
     866             : 
     867             : /*
     868             :  * SP-GiST compress function for polygons
     869             :  */
     870             : Datum
     871       44000 : spg_poly_quad_compress(PG_FUNCTION_ARGS)
     872             : {
     873       44000 :     POLYGON    *polygon = PG_GETARG_POLYGON_P(0);
     874             :     BOX        *box;
     875             : 
     876       44000 :     box = (BOX *) palloc(sizeof(BOX));
     877       44000 :     *box = polygon->boundbox;
     878             : 
     879       44000 :     PG_RETURN_BOX_P(box);
     880             : }

Generated by: LCOV version 1.13