Header And Logo

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

Data Structures | Typedefs | Functions

spgkdtreeproc.c File Reference

#include "postgres.h"
#include "access/gist.h"
#include "access/spgist.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/geo_decls.h"
Include dependency graph for spgkdtreeproc.c:

Go to the source code of this file.

Data Structures

struct  SortedPoint

Typedefs

typedef struct SortedPoint SortedPoint

Functions

Datum spg_kd_config (PG_FUNCTION_ARGS)
static int getSide (double coord, bool isX, Point *tst)
Datum spg_kd_choose (PG_FUNCTION_ARGS)
static int x_cmp (const void *a, const void *b)
static int y_cmp (const void *a, const void *b)
Datum spg_kd_picksplit (PG_FUNCTION_ARGS)
Datum spg_kd_inner_consistent (PG_FUNCTION_ARGS)

Typedef Documentation

typedef struct SortedPoint SortedPoint

Function Documentation

static int getSide ( double  coord,
bool  isX,
Point tst 
) [static]

Definition at line 39 of file spgkdtreeproc.c.

References Point::x, and Point::y.

Referenced by spg_kd_choose().

{
    double      tstcoord = (isX) ? tst->x : tst->y;

    if (coord == tstcoord)
        return 0;
    else if (coord > tstcoord)
        return 1;
    else
        return -1;
}

Datum spg_kd_choose ( PG_FUNCTION_ARGS   ) 

Definition at line 52 of file spgkdtreeproc.c.

References spgChooseIn::allTheSame, Assert, spgChooseIn::datum, DatumGetFloat8, DatumGetPointP, elog, ERROR, getSide(), spgChooseIn::hasPrefix, spgChooseIn::level, spgChooseOut::matchNode, spgChooseIn::nNodes, PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum, spgChooseIn::prefixDatum, spgChooseOut::result, and spgChooseOut::resultType.

{
    spgChooseIn *in = (spgChooseIn *) PG_GETARG_POINTER(0);
    spgChooseOut *out = (spgChooseOut *) PG_GETARG_POINTER(1);
    Point      *inPoint = DatumGetPointP(in->datum);
    double      coord;

    if (in->allTheSame)
        elog(ERROR, "allTheSame should not occur for k-d trees");

    Assert(in->hasPrefix);
    coord = DatumGetFloat8(in->prefixDatum);

    Assert(in->nNodes == 2);

    out->resultType = spgMatchNode;
    out->result.matchNode.nodeN =
        (getSide(coord, in->level % 2, inPoint) > 0) ? 0 : 1;
    out->result.matchNode.levelAdd = 1;
    out->result.matchNode.restDatum = PointPGetDatum(inPoint);

    PG_RETURN_VOID();
}

Datum spg_kd_config ( PG_FUNCTION_ARGS   ) 

Definition at line 26 of file spgkdtreeproc.c.

References spgConfigOut::canReturnData, spgConfigOut::labelType, spgConfigOut::longValuesOK, PG_GETARG_POINTER, PG_RETURN_VOID, and spgConfigOut::prefixType.

{
    /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
    spgConfigOut *cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

    cfg->prefixType = FLOAT8OID;
    cfg->labelType = VOIDOID;   /* we don't need node labels */
    cfg->canReturnData = true;
    cfg->longValuesOK = false;
    PG_RETURN_VOID();
}

Datum spg_kd_inner_consistent ( PG_FUNCTION_ARGS   ) 

Definition at line 158 of file spgkdtreeproc.c.

References spgInnerConsistentIn::allTheSame, Assert, DatumGetBoxP, DatumGetFloat8, DatumGetPointP, elog, ERROR, FPgt, FPlt, spgInnerConsistentIn::hasPrefix, BOX::high, i, spgInnerConsistentIn::level, spgInnerConsistentOut::levelAdds, BOX::low, spgInnerConsistentIn::nkeys, spgInnerConsistentOut::nNodes, spgInnerConsistentIn::nNodes, spgInnerConsistentOut::nodeNumbers, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, spgInnerConsistentIn::prefixDatum, RTAboveStrategyNumber, RTBelowStrategyNumber, RTContainedByStrategyNumber, RTLeftStrategyNumber, RTRightStrategyNumber, RTSameStrategyNumber, spgInnerConsistentIn::scankeys, ScanKeyData::sk_argument, ScanKeyData::sk_strategy, Point::x, and Point::y.

{
    spgInnerConsistentIn *in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
    spgInnerConsistentOut *out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
    double      coord;
    int         which;
    int         i;

    Assert(in->hasPrefix);
    coord = DatumGetFloat8(in->prefixDatum);

    if (in->allTheSame)
        elog(ERROR, "allTheSame should not occur for k-d trees");

    Assert(in->nNodes == 2);

    /* "which" is a bitmask of children that satisfy all constraints */
    which = (1 << 1) | (1 << 2);

    for (i = 0; i < in->nkeys; i++)
    {
        Point      *query = DatumGetPointP(in->scankeys[i].sk_argument);
        BOX        *boxQuery;

        switch (in->scankeys[i].sk_strategy)
        {
            case RTLeftStrategyNumber:
                if ((in->level % 2) != 0 && FPlt(query->x, coord))
                    which &= (1 << 1);
                break;
            case RTRightStrategyNumber:
                if ((in->level % 2) != 0 && FPgt(query->x, coord))
                    which &= (1 << 2);
                break;
            case RTSameStrategyNumber:
                if ((in->level % 2) != 0)
                {
                    if (FPlt(query->x, coord))
                        which &= (1 << 1);
                    else if (FPgt(query->x, coord))
                        which &= (1 << 2);
                }
                else
                {
                    if (FPlt(query->y, coord))
                        which &= (1 << 1);
                    else if (FPgt(query->y, coord))
                        which &= (1 << 2);
                }
                break;
            case RTBelowStrategyNumber:
                if ((in->level % 2) == 0 && FPlt(query->y, coord))
                    which &= (1 << 1);
                break;
            case RTAboveStrategyNumber:
                if ((in->level % 2) == 0 && FPgt(query->y, coord))
                    which &= (1 << 2);
                break;
            case RTContainedByStrategyNumber:

                /*
                 * For this operator, the query is a box not a point.  We
                 * cheat to the extent of assuming that DatumGetPointP won't
                 * do anything that would be bad for a pointer-to-box.
                 */
                boxQuery = DatumGetBoxP(in->scankeys[i].sk_argument);

                if ((in->level % 2) != 0)
                {
                    if (FPlt(boxQuery->high.x, coord))
                        which &= (1 << 1);
                    else if (FPgt(boxQuery->low.x, coord))
                        which &= (1 << 2);
                }
                else
                {
                    if (FPlt(boxQuery->high.y, coord))
                        which &= (1 << 1);
                    else if (FPgt(boxQuery->low.y, coord))
                        which &= (1 << 2);
                }
                break;
            default:
                elog(ERROR, "unrecognized strategy number: %d",
                     in->scankeys[i].sk_strategy);
                break;
        }

        if (which == 0)
            break;              /* no need to consider remaining conditions */
    }

    /* We must descend into the children identified by which */
    out->nodeNumbers = (int *) palloc(sizeof(int) * 2);
    out->nNodes = 0;
    for (i = 1; i <= 2; i++)
    {
        if (which & (1 << i))
            out->nodeNumbers[out->nNodes++] = i - 1;
    }

    /* Set up level increments, too */
    out->levelAdds = (int *) palloc(sizeof(int) * 2);
    out->levelAdds[0] = 1;
    out->levelAdds[1] = 1;

    PG_RETURN_VOID();
}

Datum spg_kd_picksplit ( PG_FUNCTION_ARGS   ) 

Definition at line 106 of file spgkdtreeproc.c.

References DatumGetPointP, spgPickSplitIn::datums, Float8GetDatum(), spgPickSplitOut::hasPrefix, SortedPoint::i, i, spgPickSplitOut::leafTupleDatums, spgPickSplitIn::level, spgPickSplitOut::mapTuplesToNodes, spgPickSplitOut::nNodes, spgPickSplitOut::nodeLabels, spgPickSplitIn::nTuples, SortedPoint::p, palloc(), PG_GETARG_POINTER, PG_RETURN_VOID, PointPGetDatum, spgPickSplitOut::prefixDatum, qsort, x_cmp(), Point::y, and y_cmp().

{
    spgPickSplitIn *in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
    spgPickSplitOut *out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
    int         i;
    int         middle;
    SortedPoint *sorted;
    double      coord;

    sorted = palloc(sizeof(*sorted) * in->nTuples);
    for (i = 0; i < in->nTuples; i++)
    {
        sorted[i].p = DatumGetPointP(in->datums[i]);
        sorted[i].i = i;
    }

    qsort(sorted, in->nTuples, sizeof(*sorted),
          (in->level % 2) ? x_cmp : y_cmp);
    middle = in->nTuples >> 1;
    coord = (in->level % 2) ? sorted[middle].p->x : sorted[middle].p->y;

    out->hasPrefix = true;
    out->prefixDatum = Float8GetDatum(coord);

    out->nNodes = 2;
    out->nodeLabels = NULL;     /* we don't need node labels */

    out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
    out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);

    /*
     * Note: points that have coordinates exactly equal to coord may get
     * classified into either node, depending on where they happen to fall in
     * the sorted list.  This is okay as long as the inner_consistent function
     * descends into both sides for such cases.  This is better than the
     * alternative of trying to have an exact boundary, because it keeps the
     * tree balanced even when we have many instances of the same point value.
     * So we should never trigger the allTheSame logic.
     */
    for (i = 0; i < in->nTuples; i++)
    {
        Point      *p = sorted[i].p;
        int         n = sorted[i].i;

        out->mapTuplesToNodes[n] = (i < middle) ? 0 : 1;
        out->leafTupleDatums[n] = PointPGetDatum(p);
    }

    PG_RETURN_VOID();
}

static int x_cmp ( const void *  a,
const void *  b 
) [static]

Definition at line 83 of file spgkdtreeproc.c.

References SortedPoint::p, and Point::x.

Referenced by spg_kd_picksplit(), and spg_quad_picksplit().

{
    SortedPoint *pa = (SortedPoint *) a;
    SortedPoint *pb = (SortedPoint *) b;

    if (pa->p->x == pb->p->x)
        return 0;
    return (pa->p->x > pb->p->x) ? 1 : -1;
}

static int y_cmp ( const void *  a,
const void *  b 
) [static]

Definition at line 94 of file spgkdtreeproc.c.

References SortedPoint::p, and Point::y.

Referenced by spg_kd_picksplit(), and spg_quad_picksplit().

{
    SortedPoint *pa = (SortedPoint *) a;
    SortedPoint *pb = (SortedPoint *) b;

    if (pa->p->y == pb->p->y)
        return 0;
    return (pa->p->y > pb->p->y) ? 1 : -1;
}