Header And Logo

PostgreSQL
| The world's most advanced open source database.

spgkdtreeproc.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * spgkdtreeproc.c
00004  *    implementation of k-d tree over points for SP-GiST
00005  *
00006  *
00007  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00008  * Portions Copyright (c) 1994, Regents of the University of California
00009  *
00010  * IDENTIFICATION
00011  *          src/backend/access/spgist/spgkdtreeproc.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 
00016 #include "postgres.h"
00017 
00018 #include "access/gist.h"        /* for RTree strategy numbers */
00019 #include "access/spgist.h"
00020 #include "catalog/pg_type.h"
00021 #include "utils/builtins.h"
00022 #include "utils/geo_decls.h"
00023 
00024 
00025 Datum
00026 spg_kd_config(PG_FUNCTION_ARGS)
00027 {
00028     /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
00029     spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);
00030 
00031     cfg->prefixType = FLOAT8OID;
00032     cfg->labelType = VOIDOID;   /* we don't need node labels */
00033     cfg->canReturnData = true;
00034     cfg->longValuesOK = false;
00035     PG_RETURN_VOID();
00036 }
00037 
00038 static int
00039 getSide(double coord, bool isX, Point *tst)
00040 {
00041     double      tstcoord = (isX) ? tst->x : tst->y;
00042 
00043     if (coord == tstcoord)
00044         return 0;
00045     else if (coord > tstcoord)
00046         return 1;
00047     else
00048         return -1;
00049 }
00050 
00051 Datum
00052 spg_kd_choose(PG_FUNCTION_ARGS)
00053 {
00054     spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
00055     spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
00056     Point      *inPoint = DatumGetPointP(in->datum);
00057     double      coord;
00058 
00059     if (in->allTheSame)
00060         elog(ERROR, "allTheSame should not occur for k-d trees");
00061 
00062     Assert(in->hasPrefix);
00063     coord = DatumGetFloat8(in->prefixDatum);
00064 
00065     Assert(in->nNodes == 2);
00066 
00067     out->resultType = spgMatchNode;
00068     out->result.matchNode.nodeN =
00069         (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
00070     out->result.matchNode.levelAdd = 1;
00071     out->result.matchNode.restDatum = PointPGetDatum(inPoint);
00072 
00073     PG_RETURN_VOID();
00074 }
00075 
00076 typedef struct SortedPoint
00077 {
00078     Point      *p;
00079     int         i;
00080 } SortedPoint;
00081 
00082 static int
00083 x_cmp(const void *a, const void *b)
00084 {
00085     SortedPoint *pa = (SortedPoint *) a;
00086     SortedPoint *pb = (SortedPoint *) b;
00087 
00088     if (pa->p->x == pb->p->x)
00089         return 0;
00090     return (pa->p->x > pb->p->x) ? 1 : -1;
00091 }
00092 
00093 static int
00094 y_cmp(const void *a, const void *b)
00095 {
00096     SortedPoint *pa = (SortedPoint *) a;
00097     SortedPoint *pb = (SortedPoint *) b;
00098 
00099     if (pa->p->y == pb->p->y)
00100         return 0;
00101     return (pa->p->y > pb->p->y) ? 1 : -1;
00102 }
00103 
00104 
00105 Datum
00106 spg_kd_picksplit(PG_FUNCTION_ARGS)
00107 {
00108     spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
00109     spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
00110     int         i;
00111     int         middle;
00112     SortedPoint *sorted;
00113     double      coord;
00114 
00115     sorted = palloc(sizeof(*sorted) * in->nTuples);
00116     for (i = 0; i < in->nTuples; i++)
00117     {
00118         sorted[i].p = DatumGetPointP(in->datums[i]);
00119         sorted[i].i = i;
00120     }
00121 
00122     qsort(sorted, in->nTuples, sizeof(*sorted),
00123           (in->level % 2) ? x_cmp : y_cmp);
00124     middle = in->nTuples >> 1;
00125     coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;
00126 
00127     out->hasPrefix = true;
00128     out->prefixDatum = Float8GetDatum(coord);
00129 
00130     out->nNodes = 2;
00131     out->nodeLabels = NULL;     /* we don't need node labels */
00132 
00133     out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
00134     out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
00135 
00136     /*
00137      * Note: points that have coordinates exactly equal to coord may get
00138      * classified into either node, depending on where they happen to fall in
00139      * the sorted list.  This is okay as long as the inner_consistent function
00140      * descends into both sides for such cases.  This is better than the
00141      * alternative of trying to have an exact boundary, because it keeps the
00142      * tree balanced even when we have many instances of the same point value.
00143      * So we should never trigger the allTheSame logic.
00144      */
00145     for (i = 0; i < in->nTuples; i++)
00146     {
00147         Point      *p = sorted[i].p;
00148         int         n = sorted[i].i;
00149 
00150         out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
00151         out->leafTupleDatums[n] = PointPGetDatum(p);
00152     }
00153 
00154     PG_RETURN_VOID();
00155 }
00156 
00157 Datum
00158 spg_kd_inner_consistent(PG_FUNCTION_ARGS)
00159 {
00160     spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
00161     spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
00162     double      coord;
00163     int         which;
00164     int         i;
00165 
00166     Assert(in->hasPrefix);
00167     coord = DatumGetFloat8(in->prefixDatum);
00168 
00169     if (in->allTheSame)
00170         elog(ERROR, "allTheSame should not occur for k-d trees");
00171 
00172     Assert(in->nNodes == 2);
00173 
00174     /* "which" is a bitmask of children that satisfy all constraints */
00175     which = (1 << 1) | (1 << 2);
00176 
00177     for (i = 0; i < in->nkeys; i++)
00178     {
00179         Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
00180         BOX        *boxQuery;
00181 
00182         switch (in->scankeys[i].sk_strategy)
00183         {
00184             case RTLeftStrategyNumber:
00185                 if ((in->level % 2) != 0 && FPlt(query->x, coord))
00186                     which &= (1 << 1);
00187                 break;
00188             case RTRightStrategyNumber:
00189                 if ((in->level % 2) != 0 && FPgt(query->x, coord))
00190                     which &= (1 << 2);
00191                 break;
00192             case RTSameStrategyNumber:
00193                 if ((in->level % 2) != 0)
00194                 {
00195                     if (FPlt(query->x, coord))
00196                         which &= (1 << 1);
00197                     else if (FPgt(query->x, coord))
00198                         which &= (1 << 2);
00199                 }
00200                 else
00201                 {
00202                     if (FPlt(query->y, coord))
00203                         which &= (1 << 1);
00204                     else if (FPgt(query->y, coord))
00205                         which &= (1 << 2);
00206                 }
00207                 break;
00208             case RTBelowStrategyNumber:
00209                 if ((in->level % 2) == 0 && FPlt(query->y, coord))
00210                     which &= (1 << 1);
00211                 break;
00212             case RTAboveStrategyNumber:
00213                 if ((in->level % 2) == 0 && FPgt(query->y, coord))
00214                     which &= (1 << 2);
00215                 break;
00216             case RTContainedByStrategyNumber:
00217 
00218                 /*
00219                  * For this operator, the query is a box not a point.  We
00220                  * cheat to the extent of assuming that DatumGetPointP won't
00221                  * do anything that would be bad for a pointer-to-box.
00222                  */
00223                 boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);
00224 
00225                 if ((in->level % 2) != 0)
00226                 {
00227                     if (FPlt(boxQuery->high.x, coord))
00228                         which &= (1 << 1);
00229                     else if (FPgt(boxQuery->low.x, coord))
00230                         which &= (1 << 2);
00231                 }
00232                 else
00233                 {
00234                     if (FPlt(boxQuery->high.y, coord))
00235                         which &= (1 << 1);
00236                     else if (FPgt(boxQuery->low.y, coord))
00237                         which &= (1 << 2);
00238                 }
00239                 break;
00240             default:
00241                 elog(ERROR, "unrecognized strategy number: %d",
00242                      in->scankeys[i].sk_strategy);
00243                 break;
00244         }
00245 
00246         if (which == 0)
00247             break;              /* no need to consider remaining conditions */
00248     }
00249 
00250     /* We must descend into the children identified by which */
00251     out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
00252     out->nNodes = 0;
00253     for (i = 1; i <= 2; i++)
00254     {
00255         if (which & (1 << i))
00256             out->nodeNumbers[out->nNodes++] = i - 1;
00257     }
00258 
00259     /* Set up level increments, too */
00260     out->levelAdds = (int *) palloc(sizeof(int) * 2);
00261     out->levelAdds[0] = 1;
00262     out->levelAdds[1] = 1;
00263 
00264     PG_RETURN_VOID();
00265 }
00266 
00267 /*
00268  * spg_kd_leaf_consistent() is the same as spg_quad_leaf_consistent(),
00269  * since we support the same operators and the same leaf data type.
00270  * So we just borrow that function.
00271  */