LCOV - code coverage report
Current view: top level - src/backend/access/spgist - spgkdtreeproc.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 137 145 94.5 %
Date: 2019-09-19 23:07:04 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * spgkdtreeproc.c
       4             :  *    implementation of k-d tree over points for SP-GiST
       5             :  *
       6             :  *
       7             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       8             :  * Portions Copyright (c) 1994, Regents of the University of California
       9             :  *
      10             :  * IDENTIFICATION
      11             :  *          src/backend/access/spgist/spgkdtreeproc.c
      12             :  *
      13             :  *-------------------------------------------------------------------------
      14             :  */
      15             : 
      16             : #include "postgres.h"
      17             : 
      18             : #include "access/spgist.h"
      19             : #include "access/spgist_private.h"
      20             : #include "access/stratnum.h"
      21             : #include "catalog/pg_type.h"
      22             : #include "utils/builtins.h"
      23             : #include "utils/float.h"
      24             : #include "utils/geo_decls.h"
      25             : 
      26             : 
      27             : Datum
      28          18 : spg_kd_config(PG_FUNCTION_ARGS)
      29             : {
      30             :     /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
      31          18 :     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
      32             : 
      33          18 :     cfg->prefixType = FLOAT8OID;
      34          18 :     cfg->labelType = VOIDOID;    /* we don't need node labels */
      35          18 :     cfg->canReturnData = true;
      36          18 :     cfg->longValuesOK = false;
      37          18 :     PG_RETURN_VOID();
      38             : }
      39             : 
      40             : static int
      41      387668 : getSide(double coord, bool isX, Point *tst)
      42             : {
      43      387668 :     double      tstcoord = (isX) ? tst->x : tst->y;
      44             : 
      45      387668 :     if (coord == tstcoord)
      46       21452 :         return 0;
      47      366216 :     else if (coord > tstcoord)
      48       95888 :         return 1;
      49             :     else
      50      270328 :         return -1;
      51             : }
      52             : 
      53             : Datum
      54      387668 : spg_kd_choose(PG_FUNCTION_ARGS)
      55             : {
      56      387668 :     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
      57      387668 :     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
      58      387668 :     Point      *inPoint = DatumGetPointP(in->datum);
      59             :     double      coord;
      60             : 
      61      387668 :     if (in->allTheSame)
      62           0 :         elog(ERROR, "allTheSame should not occur for k-d trees");
      63             : 
      64             :     Assert(in->hasPrefix);
      65      387668 :     coord = DatumGetFloat8(in->prefixDatum);
      66             : 
      67             :     Assert(in->nNodes == 2);
      68             : 
      69      387668 :     out->resultType = spgMatchNode;
      70      387668 :     out->result.matchNode.nodeN =
      71      387668 :         (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
      72      387668 :     out->result.matchNode.levelAdd = 1;
      73      387668 :     out->result.matchNode.restDatum = PointPGetDatum(inPoint);
      74             : 
      75      387668 :     PG_RETURN_VOID();
      76             : }
      77             : 
      78             : typedef struct SortedPoint
      79             : {
      80             :     Point      *p;
      81             :     int         i;
      82             : } SortedPoint;
      83             : 
      84             : static int
      85      205084 : x_cmp(const void *a, const void *b)
      86             : {
      87      205084 :     SortedPoint *pa = (SortedPoint *) a;
      88      205084 :     SortedPoint *pb = (SortedPoint *) b;
      89             : 
      90      205084 :     if (pa->p->x == pb->p->x)
      91        5908 :         return 0;
      92      199176 :     return (pa->p->x > pb->p->x) ? 1 : -1;
      93             : }
      94             : 
      95             : static int
      96      211316 : y_cmp(const void *a, const void *b)
      97             : {
      98      211316 :     SortedPoint *pa = (SortedPoint *) a;
      99      211316 :     SortedPoint *pb = (SortedPoint *) b;
     100             : 
     101      211316 :     if (pa->p->y == pb->p->y)
     102        3612 :         return 0;
     103      207704 :     return (pa->p->y > pb->p->y) ? 1 : -1;
     104             : }
     105             : 
     106             : 
     107             : Datum
     108         460 : spg_kd_picksplit(PG_FUNCTION_ARGS)
     109             : {
     110         460 :     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
     111         460 :     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
     112             :     int         i;
     113             :     int         middle;
     114             :     SortedPoint *sorted;
     115             :     double      coord;
     116             : 
     117         460 :     sorted = palloc(sizeof(*sorted) * in->nTuples);
     118       70716 :     for (i = 0; i < in->nTuples; i++)
     119             :     {
     120       70256 :         sorted[i].p = DatumGetPointP(in->datums[i]);
     121       70256 :         sorted[i].i = i;
     122             :     }
     123             : 
     124         460 :     qsort(sorted, in->nTuples, sizeof(*sorted),
     125             :           (in->level % 2) ? x_cmp : y_cmp);
     126         460 :     middle = in->nTuples >> 1;
     127         460 :     coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
     128             : 
     129         460 :     out->hasPrefix = true;
     130         460 :     out->prefixDatum = Float8GetDatum(coord);
     131             : 
     132         460 :     out->nNodes = 2;
     133         460 :     out->nodeLabels = NULL;      /* we don't need node labels */
     134             : 
     135         460 :     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
     136         460 :     out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
     137             : 
     138             :     /*
     139             :      * Note: points that have coordinates exactly equal to coord may get
     140             :      * classified into either node, depending on where they happen to fall in
     141             :      * the sorted list.  This is okay as long as the inner_consistent function
     142             :      * descends into both sides for such cases.  This is better than the
     143             :      * alternative of trying to have an exact boundary, because it keeps the
     144             :      * tree balanced even when we have many instances of the same point value.
     145             :      * So we should never trigger the allTheSame logic.
     146             :      */
     147       70716 :     for (i = 0; i < in->nTuples; i++)
     148             :     {
     149       70256 :         Point      *p = sorted[i].p;
     150       70256 :         int         n = sorted[i].i;
     151             : 
     152       70256 :         out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
     153       70256 :         out->leafTupleDatums[n] = PointPGetDatum(p);
     154             :     }
     155             : 
     156         460 :     PG_RETURN_VOID();
     157             : }
     158             : 
     159             : Datum
     160        4000 : spg_kd_inner_consistent(PG_FUNCTION_ARGS)
     161             : {
     162        4000 :     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
     163        4000 :     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
     164             :     double      coord;
     165             :     int         which;
     166             :     int         i;
     167             :     BOX         bboxes[2];
     168             : 
     169             :     Assert(in->hasPrefix);
     170        4000 :     coord = DatumGetFloat8(in->prefixDatum);
     171             : 
     172        4000 :     if (in->allTheSame)
     173           0 :         elog(ERROR, "allTheSame should not occur for k-d trees");
     174             : 
     175             :     Assert(in->nNodes == 2);
     176             : 
     177             :     /* "which" is a bitmask of children that satisfy all constraints */
     178        4000 :     which = (1 << 1) | (1 << 2);
     179             : 
     180        7080 :     for (i = 0; i < in->nkeys; i++)
     181             :     {
     182        3080 :         Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
     183             :         BOX        *boxQuery;
     184             : 
     185        3080 :         switch (in->scankeys[i].sk_strategy)
     186             :         {
     187             :             case RTLeftStrategyNumber:
     188         560 :                 if ((in->level % 2) != 0 && FPlt(query->x, coord))
     189          24 :                     which &= (1 << 1);
     190         560 :                 break;
     191             :             case RTRightStrategyNumber:
     192         448 :                 if ((in->level % 2) != 0 && FPgt(query->x, coord))
     193          16 :                     which &= (1 << 2);
     194         448 :                 break;
     195             :             case RTSameStrategyNumber:
     196          24 :                 if ((in->level % 2) != 0)
     197             :                 {
     198           8 :                     if (FPlt(query->x, coord))
     199           8 :                         which &= (1 << 1);
     200           0 :                     else if (FPgt(query->x, coord))
     201           0 :                         which &= (1 << 2);
     202             :                 }
     203             :                 else
     204             :                 {
     205          16 :                     if (FPlt(query->y, coord))
     206           8 :                         which &= (1 << 1);
     207           8 :                     else if (FPgt(query->y, coord))
     208           8 :                         which &= (1 << 2);
     209             :                 }
     210          24 :                 break;
     211             :             case RTBelowStrategyNumber:
     212         832 :                 if ((in->level % 2) == 0 && FPlt(query->y, coord))
     213         168 :                     which &= (1 << 1);
     214         832 :                 break;
     215             :             case RTAboveStrategyNumber:
     216         816 :                 if ((in->level % 2) == 0 && FPgt(query->y, coord))
     217         280 :                     which &= (1 << 2);
     218         816 :                 break;
     219             :             case RTContainedByStrategyNumber:
     220             : 
     221             :                 /*
     222             :                  * For this operator, the query is a box not a point.  We
     223             :                  * cheat to the extent of assuming that DatumGetPointP won't
     224             :                  * do anything that would be bad for a pointer-to-box.
     225             :                  */
     226         400 :                 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
     227             : 
     228         400 :                 if ((in->level % 2) != 0)
     229             :                 {
     230         200 :                     if (FPlt(boxQuery->high.x, coord))
     231          60 :                         which &= (1 << 1);
     232         140 :                     else if (FPgt(boxQuery->low.x, coord))
     233           0 :                         which &= (1 << 2);
     234             :                 }
     235             :                 else
     236             :                 {
     237         200 :                     if (FPlt(boxQuery->high.y, coord))
     238          20 :                         which &= (1 << 1);
     239         180 :                     else if (FPgt(boxQuery->low.y, coord))
     240          20 :                         which &= (1 << 2);
     241             :                 }
     242         400 :                 break;
     243             :             default:
     244           0 :                 elog(ERROR, "unrecognized strategy number: %d",
     245             :                      in->scankeys[i].sk_strategy);
     246             :                 break;
     247             :         }
     248             : 
     249        3080 :         if (which == 0)
     250           0 :             break;              /* no need to consider remaining conditions */
     251             :     }
     252             : 
     253             :     /* We must descend into the children identified by which */
     254        4000 :     out->nNodes = 0;
     255             : 
     256             :     /* Fast-path for no matching children */
     257        4000 :     if (!which)
     258           0 :         PG_RETURN_VOID();
     259             : 
     260        4000 :     out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
     261             : 
     262             :     /*
     263             :      * When ordering scan keys are specified, we've to calculate distance for
     264             :      * them.  In order to do that, we need calculate bounding boxes for both
     265             :      * children nodes.  Calculation of those bounding boxes on non-zero level
     266             :      * require knowledge of bounding box of upper node.  So, we save bounding
     267             :      * boxes to traversalValues.
     268             :      */
     269        4000 :     if (in->norderbys > 0)
     270             :     {
     271             :         BOX         infArea;
     272             :         BOX        *area;
     273             : 
     274        1000 :         out->distances = (double **) palloc(sizeof(double *) * in->nNodes);
     275        1000 :         out->traversalValues = (void **) palloc(sizeof(void *) * in->nNodes);
     276             : 
     277        1000 :         if (in->level == 0)
     278             :         {
     279          12 :             float8      inf = get_float8_infinity();
     280             : 
     281          12 :             infArea.high.x = inf;
     282          12 :             infArea.high.y = inf;
     283          12 :             infArea.low.x = -inf;
     284          12 :             infArea.low.y = -inf;
     285          12 :             area = &infArea;
     286             :         }
     287             :         else
     288             :         {
     289         988 :             area = (BOX *) in->traversalValue;
     290             :             Assert(area);
     291             :         }
     292             : 
     293        1000 :         bboxes[0].low = area->low;
     294        1000 :         bboxes[1].high = area->high;
     295             : 
     296        1000 :         if (in->level % 2)
     297             :         {
     298             :             /* split box by x */
     299         464 :             bboxes[0].high.x = bboxes[1].low.x = coord;
     300         464 :             bboxes[0].high.y = area->high.y;
     301         464 :             bboxes[1].low.y = area->low.y;
     302             :         }
     303             :         else
     304             :         {
     305             :             /* split box by y */
     306         536 :             bboxes[0].high.y = bboxes[1].low.y = coord;
     307         536 :             bboxes[0].high.x = area->high.x;
     308         536 :             bboxes[1].low.x = area->low.x;
     309             :         }
     310             :     }
     311             : 
     312       12000 :     for (i = 1; i <= 2; i++)
     313             :     {
     314        8000 :         if (which & (1 << i))
     315             :         {
     316        7388 :             out->nodeNumbers[out->nNodes] = i - 1;
     317             : 
     318        7388 :             if (in->norderbys > 0)
     319             :             {
     320        1980 :                 MemoryContext oldCtx = MemoryContextSwitchTo(in->traversalMemoryContext);
     321        1980 :                 BOX        *box = box_copy(&bboxes[i - 1]);
     322             : 
     323        1980 :                 MemoryContextSwitchTo(oldCtx);
     324             : 
     325        1980 :                 out->traversalValues[out->nNodes] = box;
     326             : 
     327        1980 :                 out->distances[out->nNodes] = spg_key_orderbys_distances(BoxPGetDatum(box), false,
     328             :                                                                          in->orderbys, in->norderbys);
     329             :             }
     330             : 
     331        7388 :             out->nNodes++;
     332             :         }
     333             :     }
     334             : 
     335             :     /* Set up level increments, too */
     336        4000 :     out->levelAdds = (int *) palloc(sizeof(int) * 2);
     337        4000 :     out->levelAdds[0] = 1;
     338        4000 :     out->levelAdds[1] = 1;
     339             : 
     340        4000 :     PG_RETURN_VOID();
     341             : }
     342             : 
     343             : /*
     344             :  * spg_kd_leaf_consistent() is the same as spg_quad_leaf_consistent(),
     345             :  * since we support the same operators and the same leaf data type.
     346             :  * So we just borrow that function.
     347             :  */

Generated by: LCOV version 1.13