LCOV - code coverage report
Current view: top level - src/backend/utils/adt - geo_spgist.c (source / functions) Hit Total Coverage
Test: PostgreSQL 18devel Lines: 335 341 98.2 %
Date: 2024-10-10 04:14:55 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-2024, 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     2045570 : compareDoubles(const void *a, const void *b)
      94             : {
      95     2045570 :     float8      x = *(float8 *) a;
      96     2045570 :     float8      y = *(float8 *) b;
      97             : 
      98     2045570 :     if (x == y)
      99      398420 :         return 0;
     100     1647150 :     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      871738 : getQuadrant(BOX *centroid, BOX *inBox)
     131             : {
     132      871738 :     uint8       quadrant = 0;
     133             : 
     134      871738 :     if (inBox->low.x > centroid->low.x)
     135      735642 :         quadrant |= 0x8;
     136             : 
     137      871738 :     if (inBox->high.x > centroid->high.x)
     138      749208 :         quadrant |= 0x4;
     139             : 
     140      871738 :     if (inBox->low.y > centroid->low.y)
     141      470916 :         quadrant |= 0x2;
     142             : 
     143      871738 :     if (inBox->high.y > centroid->high.y)
     144      474222 :         quadrant |= 0x1;
     145             : 
     146      871738 :     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       16164 : getRangeBox(BOX *box)
     158             : {
     159       16164 :     RangeBox   *range_box = (RangeBox *) palloc(sizeof(RangeBox));
     160             : 
     161       16164 :     range_box->left.low = box->low.x;
     162       16164 :     range_box->left.high = box->high.x;
     163             : 
     164       16164 :     range_box->right.low = box->low.y;
     165       16164 :     range_box->right.high = box->high.y;
     166             : 
     167       16164 :     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         816 : initRectBox(void)
     178             : {
     179         816 :     RectBox    *rect_box = (RectBox *) palloc(sizeof(RectBox));
     180         816 :     float8      infinity = get_float8_infinity();
     181             : 
     182         816 :     rect_box->range_box_x.left.low = -infinity;
     183         816 :     rect_box->range_box_x.left.high = infinity;
     184             : 
     185         816 :     rect_box->range_box_x.right.low = -infinity;
     186         816 :     rect_box->range_box_x.right.high = infinity;
     187             : 
     188         816 :     rect_box->range_box_y.left.low = -infinity;
     189         816 :     rect_box->range_box_y.left.high = infinity;
     190             : 
     191         816 :     rect_box->range_box_y.right.low = -infinity;
     192         816 :     rect_box->range_box_y.right.high = infinity;
     193             : 
     194         816 :     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      134016 : nextRectBox(RectBox *rect_box, RangeBox *centroid, uint8 quadrant)
     206             : {
     207      134016 :     RectBox    *next_rect_box = (RectBox *) palloc(sizeof(RectBox));
     208             : 
     209      134016 :     memcpy(next_rect_box, rect_box, sizeof(RectBox));
     210             : 
     211      134016 :     if (quadrant & 0x8)
     212       67008 :         next_rect_box->range_box_x.left.low = centroid->left.low;
     213             :     else
     214       67008 :         next_rect_box->range_box_x.left.high = centroid->left.low;
     215             : 
     216      134016 :     if (quadrant & 0x4)
     217       67008 :         next_rect_box->range_box_x.right.low = centroid->left.high;
     218             :     else
     219       67008 :         next_rect_box->range_box_x.right.high = centroid->left.high;
     220             : 
     221      134016 :     if (quadrant & 0x2)
     222       67008 :         next_rect_box->range_box_y.left.low = centroid->right.low;
     223             :     else
     224       67008 :         next_rect_box->range_box_y.left.high = centroid->right.low;
     225             : 
     226      134016 :     if (quadrant & 0x1)
     227       67008 :         next_rect_box->range_box_y.right.low = centroid->right.high;
     228             :     else
     229       67008 :         next_rect_box->range_box_y.right.high = centroid->right.high;
     230             : 
     231      134016 :     return next_rect_box;
     232             : }
     233             : 
     234             : /* Can any range from range_box overlap with this argument? */
     235             : static bool
     236       10800 : overlap2D(RangeBox *range_box, Range *query)
     237             : {
     238       20328 :     return FPge(range_box->right.high, query->low) &&
     239        9528 :         FPle(range_box->left.low, query->high);
     240             : }
     241             : 
     242             : /* Can any rectangle from rect_box overlap with this argument? */
     243             : static bool
     244        6336 : overlap4D(RectBox *rect_box, RangeBox *query)
     245             : {
     246       10800 :     return overlap2D(&rect_box->range_box_x, &query->left) &&
     247        4464 :         overlap2D(&rect_box->range_box_y, &query->right);
     248             : }
     249             : 
     250             : /* Can any range from range_box contain this argument? */
     251             : static bool
     252        1776 : contain2D(RangeBox *range_box, Range *query)
     253             : {
     254        2976 :     return FPge(range_box->right.high, query->high) &&
     255        1200 :         FPle(range_box->left.low, query->low);
     256             : }
     257             : 
     258             : /* Can any rectangle from rect_box contain this argument? */
     259             : static bool
     260        1152 : contain4D(RectBox *rect_box, RangeBox *query)
     261             : {
     262        1776 :     return contain2D(&rect_box->range_box_x, &query->left) &&
     263         624 :         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       21000 : contained2D(RangeBox *range_box, Range *query)
     269             : {
     270       40776 :     return FPle(range_box->left.low, query->high) &&
     271       36504 :         FPge(range_box->left.high, query->low) &&
     272       57504 :         FPle(range_box->right.low, query->high) &&
     273       15900 :         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       13440 : contained4D(RectBox *rect_box, RangeBox *query)
     279             : {
     280       21000 :     return contained2D(&rect_box->range_box_x, &query->left) &&
     281        7560 :         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       13632 : lower2D(RangeBox *range_box, Range *query)
     287             : {
     288       24432 :     return FPlt(range_box->left.low, query->low) &&
     289       10800 :         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       24288 : overLower2D(RangeBox *range_box, Range *query)
     295             : {
     296       46704 :     return FPle(range_box->left.low, query->high) &&
     297       22416 :         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       34848 : higher2D(RangeBox *range_box, Range *query)
     303             : {
     304       61872 :     return FPgt(range_box->left.high, query->high) &&
     305       27024 :         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       30912 : overHigher2D(RangeBox *range_box, Range *query)
     311             : {
     312       59376 :     return FPge(range_box->left.high, query->low) &&
     313       28464 :         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        9312 : left4D(RectBox *rect_box, RangeBox *query)
     319             : {
     320        9312 :     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       14688 : overLeft4D(RectBox *rect_box, RangeBox *query)
     326             : {
     327       14688 :     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       26304 : right4D(RectBox *rect_box, RangeBox *query)
     333             : {
     334       26304 :     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       16992 : overRight4D(RectBox *rect_box, RangeBox *query)
     340             : {
     341       16992 :     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        4320 : below4D(RectBox *rect_box, RangeBox *query)
     347             : {
     348        4320 :     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        9600 : overBelow4D(RectBox *rect_box, RangeBox *query)
     354             : {
     355        9600 :     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        8544 : above4D(RectBox *rect_box, RangeBox *query)
     361             : {
     362        8544 :     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       13920 : overAbove4D(RectBox *rect_box, RangeBox *query)
     368             : {
     369       13920 :     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       13202 : pointToRectBoxDistance(Point *point, RectBox *rect_box)
     375             : {
     376             :     double      dx;
     377             :     double      dy;
     378             : 
     379       13202 :     if (point->x < rect_box->range_box_x.left.low)
     380       10224 :         dx = rect_box->range_box_x.left.low - point->x;
     381        2978 :     else if (point->x > rect_box->range_box_x.right.high)
     382         576 :         dx = point->x - rect_box->range_box_x.right.high;
     383             :     else
     384        2402 :         dx = 0;
     385             : 
     386       13202 :     if (point->y < rect_box->range_box_y.left.low)
     387        6384 :         dy = rect_box->range_box_y.left.low - point->y;
     388        6818 :     else if (point->y > rect_box->range_box_y.right.high)
     389        6210 :         dy = point->y - rect_box->range_box_y.right.high;
     390             :     else
     391         608 :         dy = 0;
     392             : 
     393       13202 :     return HYPOT(dx, dy);
     394             : }
     395             : 
     396             : 
     397             : /*
     398             :  * SP-GiST config function
     399             :  */
     400             : Datum
     401          72 : spg_box_quad_config(PG_FUNCTION_ARGS)
     402             : {
     403          72 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
     404             : 
     405          72 :     cfg->prefixType = BOXOID;
     406          72 :     cfg->labelType = VOIDOID;    /* We don't need node labels. */
     407          72 :     cfg->canReturnData = true;
     408          72 :     cfg->longValuesOK = false;
     409             : 
     410          72 :     PG_RETURN_VOID();
     411             : }
     412             : 
     413             : /*
     414             :  * SP-GiST choose function
     415             :  */
     416             : Datum
     417      754702 : spg_box_quad_choose(PG_FUNCTION_ARGS)
     418             : {
     419      754702 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
     420      754702 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
     421      754702 :     BOX        *centroid = DatumGetBoxP(in->prefixDatum),
     422      754702 :                *box = DatumGetBoxP(in->leafDatum);
     423             : 
     424      754702 :     out->resultType = spgMatchNode;
     425      754702 :     out->result.matchNode.restDatum = BoxPGetDatum(box);
     426             : 
     427             :     /* nodeN will be set by core, when allTheSame. */
     428      754702 :     if (!in->allTheSame)
     429      741426 :         out->result.matchNode.nodeN = getQuadrant(centroid, box);
     430             : 
     431      754702 :     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        1310 : spg_box_quad_picksplit(PG_FUNCTION_ARGS)
     442             : {
     443        1310 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     444        1310 :     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
     445             :     BOX        *centroid;
     446             :     int         median,
     447             :                 i;
     448        1310 :     float8     *lowXs = palloc(sizeof(float8) * in->nTuples);
     449        1310 :     float8     *highXs = palloc(sizeof(float8) * in->nTuples);
     450        1310 :     float8     *lowYs = palloc(sizeof(float8) * in->nTuples);
     451        1310 :     float8     *highYs = palloc(sizeof(float8) * in->nTuples);
     452             : 
     453             :     /* Calculate median of all 4D coordinates */
     454      131622 :     for (i = 0; i < in->nTuples; i++)
     455             :     {
     456      130312 :         BOX        *box = DatumGetBoxP(in->datums[i]);
     457             : 
     458      130312 :         lowXs[i] = box->low.x;
     459      130312 :         highXs[i] = box->high.x;
     460      130312 :         lowYs[i] = box->low.y;
     461      130312 :         highYs[i] = box->high.y;
     462             :     }
     463             : 
     464        1310 :     qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
     465        1310 :     qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
     466        1310 :     qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
     467        1310 :     qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
     468             : 
     469        1310 :     median = in->nTuples / 2;
     470             : 
     471        1310 :     centroid = palloc(sizeof(BOX));
     472             : 
     473        1310 :     centroid->low.x = lowXs[median];
     474        1310 :     centroid->high.x = highXs[median];
     475        1310 :     centroid->low.y = lowYs[median];
     476        1310 :     centroid->high.y = highYs[median];
     477             : 
     478             :     /* Fill the output */
     479        1310 :     out->hasPrefix = true;
     480        1310 :     out->prefixDatum = BoxPGetDatum(centroid);
     481             : 
     482        1310 :     out->nNodes = 16;
     483        1310 :     out->nodeLabels = NULL;      /* We don't need node labels. */
     484             : 
     485        1310 :     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     486        1310 :     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      131622 :     for (i = 0; i < in->nTuples; i++)
     493             :     {
     494      130312 :         BOX        *box = DatumGetBoxP(in->datums[i]);
     495      130312 :         uint8       quadrant = getQuadrant(centroid, box);
     496             : 
     497      130312 :         out->leafTupleDatums[i] = BoxPGetDatum(box);
     498      130312 :         out->mapTuplesToNodes[i] = quadrant;
     499             :     }
     500             : 
     501        1310 :     PG_RETURN_VOID();
     502             : }
     503             : 
     504             : /*
     505             :  * Check if result of consistent method based on bounding box is exact.
     506             :  */
     507             : static bool
     508      392040 : is_bounding_box_test_exact(StrategyNumber strategy)
     509             : {
     510      392040 :     switch (strategy)
     511             :     {
     512      325014 :         case RTLeftStrategyNumber:
     513             :         case RTOverLeftStrategyNumber:
     514             :         case RTOverRightStrategyNumber:
     515             :         case RTRightStrategyNumber:
     516             :         case RTOverBelowStrategyNumber:
     517             :         case RTBelowStrategyNumber:
     518             :         case RTAboveStrategyNumber:
     519             :         case RTOverAboveStrategyNumber:
     520      325014 :             return true;
     521             : 
     522       67026 :         default:
     523       67026 :             return false;
     524             :     }
     525             : }
     526             : 
     527             : /*
     528             :  * Get bounding box for ScanKey.
     529             :  */
     530             : static BOX *
     531      791130 : spg_box_quad_get_scankey_bbox(ScanKey sk, bool *recheck)
     532             : {
     533      791130 :     switch (sk->sk_subtype)
     534             :     {
     535      395508 :         case BOXOID:
     536      395508 :             return DatumGetBoxP(sk->sk_argument);
     537             : 
     538      395622 :         case POLYGONOID:
     539      395622 :             if (recheck && !is_bounding_box_test_exact(sk->sk_strategy))
     540       67026 :                 *recheck = true;
     541      395622 :             return &DatumGetPolygonP(sk->sk_argument)->boundbox;
     542             : 
     543           0 :         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        9096 : spg_box_quad_inner_consistent(PG_FUNCTION_ARGS)
     554             : {
     555        9096 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     556        9096 :     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        9096 :     if (in->traversalValue)
     569        8280 :         rect_box = in->traversalValue;
     570             :     else
     571         816 :         rect_box = initRectBox();
     572             : 
     573        9096 :     if (in->allTheSame)
     574             :     {
     575             :         /* Report that all nodes should be visited */
     576         720 :         out->nNodes = in->nNodes;
     577         720 :         out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     578        6480 :         for (i = 0; i < in->nNodes; i++)
     579        5760 :             out->nodeNumbers[i] = i;
     580             : 
     581         720 :         if (in->norderbys > 0 && in->nNodes > 0)
     582             :         {
     583          92 :             double     *distances = palloc(sizeof(double) * in->norderbys);
     584             :             int         j;
     585             : 
     586         184 :             for (j = 0; j < in->norderbys; j++)
     587             :             {
     588          92 :                 Point      *pt = DatumGetPointP(in->orderbys[j].sk_argument);
     589             : 
     590          92 :                 distances[j] = pointToRectBoxDistance(pt, rect_box);
     591             :             }
     592             : 
     593          92 :             out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
     594          92 :             out->distances[0] = distances;
     595             : 
     596         736 :             for (i = 1; i < in->nNodes; i++)
     597             :             {
     598         644 :                 out->distances[i] = palloc(sizeof(double) * in->norderbys);
     599         644 :                 memcpy(out->distances[i], distances,
     600         644 :                        sizeof(double) * in->norderbys);
     601             :             }
     602             :         }
     603             : 
     604         720 :         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        8376 :     centroid = getRangeBox(DatumGetBoxP(in->prefixDatum));
     612        8376 :     queries = (RangeBox **) palloc(in->nkeys * sizeof(RangeBox *));
     613       16164 :     for (i = 0; i < in->nkeys; i++)
     614             :     {
     615        7788 :         BOX        *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i], NULL);
     616             : 
     617        7788 :         queries[i] = getRangeBox(box);
     618             :     }
     619             : 
     620             :     /* Allocate enough memory for nodes */
     621        8376 :     out->nNodes = 0;
     622        8376 :     out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
     623        8376 :     out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
     624        8376 :     if (in->norderbys > 0)
     625         996 :         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        8376 :     old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
     633             : 
     634      142392 :     for (quadrant = 0; quadrant < in->nNodes; quadrant++)
     635             :     {
     636      134016 :         RectBox    *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
     637      134016 :         bool        flag = true;
     638             : 
     639      226518 :         for (i = 0; i < in->nkeys; i++)
     640             :         {
     641      124608 :             StrategyNumber strategy = in->scankeys[i].sk_strategy;
     642             : 
     643      124608 :             switch (strategy)
     644             :             {
     645        6336 :                 case RTOverlapStrategyNumber:
     646        6336 :                     flag = overlap4D(next_rect_box, queries[i]);
     647        6336 :                     break;
     648             : 
     649        1152 :                 case RTContainsStrategyNumber:
     650        1152 :                     flag = contain4D(next_rect_box, queries[i]);
     651        1152 :                     break;
     652             : 
     653       13440 :                 case RTSameStrategyNumber:
     654             :                 case RTContainedByStrategyNumber:
     655       13440 :                     flag = contained4D(next_rect_box, queries[i]);
     656       13440 :                     break;
     657             : 
     658        9312 :                 case RTLeftStrategyNumber:
     659        9312 :                     flag = left4D(next_rect_box, queries[i]);
     660        9312 :                     break;
     661             : 
     662       14688 :                 case RTOverLeftStrategyNumber:
     663       14688 :                     flag = overLeft4D(next_rect_box, queries[i]);
     664       14688 :                     break;
     665             : 
     666       26304 :                 case RTRightStrategyNumber:
     667       26304 :                     flag = right4D(next_rect_box, queries[i]);
     668       26304 :                     break;
     669             : 
     670       16992 :                 case RTOverRightStrategyNumber:
     671       16992 :                     flag = overRight4D(next_rect_box, queries[i]);
     672       16992 :                     break;
     673             : 
     674        8544 :                 case RTAboveStrategyNumber:
     675        8544 :                     flag = above4D(next_rect_box, queries[i]);
     676        8544 :                     break;
     677             : 
     678       13920 :                 case RTOverAboveStrategyNumber:
     679       13920 :                     flag = overAbove4D(next_rect_box, queries[i]);
     680       13920 :                     break;
     681             : 
     682        4320 :                 case RTBelowStrategyNumber:
     683        4320 :                     flag = below4D(next_rect_box, queries[i]);
     684        4320 :                     break;
     685             : 
     686        9600 :                 case RTOverBelowStrategyNumber:
     687        9600 :                     flag = overBelow4D(next_rect_box, queries[i]);
     688        9600 :                     break;
     689             : 
     690           0 :                 default:
     691           0 :                     elog(ERROR, "unrecognized strategy: %d", strategy);
     692             :             }
     693             : 
     694             :             /* If any check is failed, we have found our answer. */
     695      124608 :             if (!flag)
     696       32106 :                 break;
     697             :         }
     698             : 
     699      134016 :         if (flag)
     700             :         {
     701      101910 :             out->traversalValues[out->nNodes] = next_rect_box;
     702      101910 :             out->nodeNumbers[out->nNodes] = quadrant;
     703             : 
     704      101910 :             if (in->norderbys > 0)
     705             :             {
     706       13110 :                 double     *distances = palloc(sizeof(double) * in->norderbys);
     707             :                 int         j;
     708             : 
     709       13110 :                 out->distances[out->nNodes] = distances;
     710             : 
     711       26220 :                 for (j = 0; j < in->norderbys; j++)
     712             :                 {
     713       13110 :                     Point      *pt = DatumGetPointP(in->orderbys[j].sk_argument);
     714             : 
     715       13110 :                     distances[j] = pointToRectBoxDistance(pt, next_rect_box);
     716             :                 }
     717             :             }
     718             : 
     719      101910 :             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       32106 :             pfree(next_rect_box);
     728             :         }
     729             :     }
     730             : 
     731             :     /* Switch back */
     732        8376 :     MemoryContextSwitchTo(old_ctx);
     733             : 
     734        8376 :     PG_RETURN_VOID();
     735             : }
     736             : 
     737             : /*
     738             :  * SP-GiST inner consistent function
     739             :  */
     740             : Datum
     741      849360 : spg_box_quad_leaf_consistent(PG_FUNCTION_ARGS)
     742             : {
     743      849360 :     spgLeafConsistentIn *in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
     744      849360 :     spgLeafConsistentOut *out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
     745      849360 :     Datum       leaf = in->leafDatum;
     746      849360 :     bool        flag = true;
     747             :     int         i;
     748             : 
     749             :     /* All tests are exact. */
     750      849360 :     out->recheck = false;
     751             : 
     752             :     /*
     753             :      * Don't return leafValue unless told to; this is used for both box and
     754             :      * polygon opclasses, and in the latter case the leaf datum is not even of
     755             :      * the right type to return.
     756             :      */
     757      849360 :     if (in->returnData)
     758        5826 :         out->leafValue = leaf;
     759             : 
     760             :     /* Perform the required comparison(s) */
     761     1487514 :     for (i = 0; i < in->nkeys; i++)
     762             :     {
     763      783342 :         StrategyNumber strategy = in->scankeys[i].sk_strategy;
     764      783342 :         BOX        *box = spg_box_quad_get_scankey_bbox(&in->scankeys[i],
     765             :                                                         &out->recheck);
     766      783342 :         Datum       query = BoxPGetDatum(box);
     767             : 
     768      783342 :         switch (strategy)
     769             :         {
     770       36318 :             case RTOverlapStrategyNumber:
     771       36318 :                 flag = DatumGetBool(DirectFunctionCall2(box_overlap, leaf,
     772             :                                                         query));
     773       36318 :                 break;
     774             : 
     775        8406 :             case RTContainsStrategyNumber:
     776        8406 :                 flag = DatumGetBool(DirectFunctionCall2(box_contain, leaf,
     777             :                                                         query));
     778        8406 :                 break;
     779             : 
     780       69252 :             case RTContainedByStrategyNumber:
     781       69252 :                 flag = DatumGetBool(DirectFunctionCall2(box_contained, leaf,
     782             :                                                         query));
     783       69252 :                 break;
     784             : 
     785       13032 :             case RTSameStrategyNumber:
     786       13032 :                 flag = DatumGetBool(DirectFunctionCall2(box_same, leaf,
     787             :                                                         query));
     788       13032 :                 break;
     789             : 
     790       48192 :             case RTLeftStrategyNumber:
     791       48192 :                 flag = DatumGetBool(DirectFunctionCall2(box_left, leaf,
     792             :                                                         query));
     793       48192 :                 break;
     794             : 
     795       97878 :             case RTOverLeftStrategyNumber:
     796       97878 :                 flag = DatumGetBool(DirectFunctionCall2(box_overleft, leaf,
     797             :                                                         query));
     798       97878 :                 break;
     799             : 
     800      129912 :             case RTRightStrategyNumber:
     801      129912 :                 flag = DatumGetBool(DirectFunctionCall2(box_right, leaf,
     802             :                                                         query));
     803      129912 :                 break;
     804             : 
     805      110568 :             case RTOverRightStrategyNumber:
     806      110568 :                 flag = DatumGetBool(DirectFunctionCall2(box_overright, leaf,
     807             :                                                         query));
     808      110568 :                 break;
     809             : 
     810       55920 :             case RTAboveStrategyNumber:
     811       55920 :                 flag = DatumGetBool(DirectFunctionCall2(box_above, leaf,
     812             :                                                         query));
     813       55920 :                 break;
     814             : 
     815      109350 :             case RTOverAboveStrategyNumber:
     816      109350 :                 flag = DatumGetBool(DirectFunctionCall2(box_overabove, leaf,
     817             :                                                         query));
     818      109350 :                 break;
     819             : 
     820       25878 :             case RTBelowStrategyNumber:
     821       25878 :                 flag = DatumGetBool(DirectFunctionCall2(box_below, leaf,
     822             :                                                         query));
     823       25878 :                 break;
     824             : 
     825       78636 :             case RTOverBelowStrategyNumber:
     826       78636 :                 flag = DatumGetBool(DirectFunctionCall2(box_overbelow, leaf,
     827             :                                                         query));
     828       78636 :                 break;
     829             : 
     830           0 :             default:
     831           0 :                 elog(ERROR, "unrecognized strategy: %d", strategy);
     832             :         }
     833             : 
     834             :         /* If any check is failed, we have found our answer. */
     835      783342 :         if (!flag)
     836      145188 :             break;
     837             :     }
     838             : 
     839      849360 :     if (flag && in->norderbys > 0)
     840             :     {
     841       86544 :         Oid         distfnoid = in->orderbys[0].sk_func.fn_oid;
     842             : 
     843       86544 :         out->distances = spg_key_orderbys_distances(leaf, false,
     844             :                                                     in->orderbys, in->norderbys);
     845             : 
     846             :         /* Recheck is necessary when computing distance to polygon */
     847       86544 :         out->recheckDistances = distfnoid == F_DIST_POLYP;
     848             :     }
     849             : 
     850      849360 :     PG_RETURN_BOOL(flag);
     851             : }
     852             : 
     853             : 
     854             : /*
     855             :  * SP-GiST config function for 2-D types that are lossy represented by their
     856             :  * bounding boxes
     857             :  */
     858             : Datum
     859          26 : spg_bbox_quad_config(PG_FUNCTION_ARGS)
     860             : {
     861          26 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
     862             : 
     863          26 :     cfg->prefixType = BOXOID;    /* A type represented by its bounding box */
     864          26 :     cfg->labelType = VOIDOID;    /* We don't need node labels. */
     865          26 :     cfg->leafType = BOXOID;
     866          26 :     cfg->canReturnData = false;
     867          26 :     cfg->longValuesOK = false;
     868             : 
     869          26 :     PG_RETURN_VOID();
     870             : }
     871             : 
     872             : /*
     873             :  * SP-GiST compress function for polygons
     874             :  */
     875             : Datum
     876       66004 : spg_poly_quad_compress(PG_FUNCTION_ARGS)
     877             : {
     878       66004 :     POLYGON    *polygon = PG_GETARG_POLYGON_P(0);
     879             :     BOX        *box;
     880             : 
     881       66004 :     box = (BOX *) palloc(sizeof(BOX));
     882       66004 :     *box = polygon->boundbox;
     883             : 
     884       66004 :     PG_RETURN_BOX_P(box);
     885             : }

Generated by: LCOV version 1.14